Label noise is a common challenge in large datasets, as it can significantly degrade the generalization ability of deep neural networks. Most existing studies focus on noisy labels in computer vision; however, graph models encompass both node features and graph topology as input, and become more susceptible to label noise through message-passing mechanisms. Recently, only a few works have been proposed to tackle the label noise on graphs. One significant limitation is that they operate under the assumption that the graph exhibits homophily and that the labels are distributed smoothly. However, real-world graphs can exhibit varying degrees of heterophily, or even be dominated by heterophily, which results in the inadequacy of the current methods. In this paper, we study graph label noise in the context of arbitrary heterophily, with the aim of rectifying noisy labels and assigning labels to previously unlabeled nodes. We begin by conducting two empirical analyses to explore the impact of graph homophily on graph label noise. Following observations, we propose a efficient algorithm, denoted as R2LP. Specifically, R2LP is an iterative algorithm with three steps: (1) reconstruct the graph to recover the homophily property, (2) utilize label propagation to rectify the noisy labels, (3) select high-confidence labels to retain for the next iteration. By iterating these steps, we obtain a set of ''correct'' labels, ultimately achieving high accuracy in the node classification task. The theoretical analysis is also provided to demonstrate its remarkable denoising effect. Finally, we perform experiments on ten benchmark datasets with different levels of graph heterophily and various types of noise. In these experiments, we compare the performance of R2LP against ten typical baseline methods. Our results illustrate the superior performance of the proposed øurs. The code and data of this paper can be accessed at: https://github.com/cy623/R2LP.git.
论文检索
输入标题、作者或关键词，从 642 篇学术成果中精准定位
Co-Neighbor Encoding Schema: A Light-cost Structure Encoding Method for Dynamic Link Prediction
PDF ↗Structure encoding has proven to be the key feature to distinguishing links in a graph. However, Structure encoding in the temporal graph keeps changing as the graph evolves, repeatedly computing such features can be time-consuming due to the high-order subgraph construction. We develop the Co-Neighbor Encoding Schema (CNES) to address this issue. Instead of recomputing the feature by the link, CNES stores information in the memory to avoid redundant calculations. Besides, unlike the existing memory-based dynamic graph learning method that stores node hidden states, we introduce a hashtable-based memory to compress the adjacency matrix for efficient structure feature construction and updating with vector computation in parallel. Furthermore, CNES introduces a Temporal-Diverse Memory to generate long-term and short-term structure encoding for neighbors with different structural information. A dynamic graph learning framework, Co-Neighbor Encoding Network (CNE-N), is proposed using the aforementioned techniques. Extensive experiments on thirteen public datasets verify the effectiveness and efficiency of the proposed method.
Personalized decision making requires the knowledge of potential outcomes under different treatments, and confidence intervals about the potential outcomes further enrich this decision-making process and improve its reliability in high-stakes scenarios. Predicting potential outcomes along with its uncertainty in a counterfactual world poses the foundamental challenge in causal inference. Existing methods that construct confidence intervals for counterfactuals either rely on the assumption of strong ignorability that completely ignores hidden confounders, or need access to un-identifiable lower and upper bounds that characterize the difference between observational and interventional distributions. In this paper, to overcome these limitations, we first propose a novel approach wTCP-DR based on transductive weighted conformal prediction, which provides confidence intervals for counterfactual outcomes with marginal converage guarantees, even under hidden confounding. With less restrictive assumptions, our approach requires access to a fraction of interventional data (from randomized controlled trials) to account for the covariate shift from observational distributoin to interventional distribution. Theoretical results explicitly demonstrate the conditions under which our algorithm is strictly advantageous to the naive method that only uses interventional data. Since transductive conformal prediction is notoriously costly, we propose wSCP-DR, a two-stage variant of wTCP-DR, based on split conformal prediction with same marginal coverage guarantees but at a significantly lower computational cost. After ensuring valid intervals on counterfactuals, it is straightforward to construct intervals for individual treatment effects (ITEs). We demonstrate our method across synthetic and real-world data, including recommendation systems, to verify the superiority of our methods compared against state-of-the-art baselines in terms of both coverage and efficiency. Our code can be found at https://github.com/rguo12/KDD24-Conformal.
Shopping Trajectory Representation Learning with Pre-training for E-commerce Customer Understanding and Recommendation
PDF ↗Understanding customer behavior is crucial for improving service quality in large-scale E-commerce. This paper proposes C-STAR, a new framework that learns compact representations from customer shopping journeys, with good versatility to fuel multiple downstream customer-centric tasks. We define the notion of shopping trajectory that encompasses customer interactions at the level of product categories, capturing the overall flow of their browsing and purchase activities. C-STAR excels at modeling both inter-trajectory distribution similarity-the structural similarities between different trajectories, and intra-trajectory semantic correlation-the semantic relationships within individual ones. This coarse-to-fine approach ensures informative trajectory embeddings for representing customers. To enhance embedding quality, we introduce a pre-training strategy that captures two intrinsic properties within the pre-training data. Extensive evaluation on large-scale industrial and public datasets demonstrates the effectiveness of C-STAR across three diverse customer-centric tasks. These tasks empower customer profiling and recommendation services for enhancing personalized shopping experiences on our E-commerce platform.
Maximum-Entropy Regularized Decision Transformer with Reward Relabelling for Dynamic Recommendation
PDF ↗Reinforcement learning-based recommender systems have recently gained popularity. However, due to the typical limitations of simulation environments (e.g., data inefficiency), most of the work cannot be broadly applied in all domains. To counter these challenges, recent advancements have leveraged offline reinforcement learning methods, notable for their data-driven approach utilizing offline datasets. A prominent example of this is the Decision Transformer. Despite its popularity, the Decision Transformer approach has inherent drawbacks, particularly evident in recommendation methods based on it. This paper identifies two key shortcomings in existing Decision Transformer-based methods: a lack of stitching capability and limited effectiveness in online adoption. In response, we introduce a novel methodology named Max-Entropy enhanced Decision Transformer with Reward Relabeling for Offline RLRS (EDT4Rec). Our approach begins with a max entropy perspective, leading to the development of a max-entropy enhanced exploration strategy. This strategy is designed to facilitate more effective exploration in online environments. Additionally, to augment the model's capability to stitch sub-optimal trajectories, we incorporate a unique reward relabeling technique. To validate the effectiveness and superiority of EDT4Rec, we have conducted comprehensive experiments across six real-world offline datasets and in an online simulator.
To counter the side effect brought by the proliferation of social media platforms, hate speech detection (HSD) plays a vital role in halting the dissemination of toxic online posts at an early stage. However, given the ubiquitous topical communities on social media, a trained HSD classifier can easily become biased towards specific targeted groups (e.g.,female andblack people), where a high rate of either false positive or false negative results can significantly impair public trust in the fairness of content moderation mechanisms, and eventually harm the diversity of online society. Although existing fairness-aware HSD methods can smooth out some discrepancies across targeted groups, they are mostly specific to a narrow selection of targets that are assumed to be known and fixed. This inevitably prevents those methods from generalizing to real-world use cases where new targeted groups constantly emerge (e.g., new forums created on Reddit) over time. To tackle the defects of existing HSD practices, we propose Generalizable target-aware Fairness (GetFair), a new method for fairly classifying each post that contains diverse and even unseen targets during inference. To remove the HSD classifier's spurious dependence on target-related features, GetFair trains a series of filter functions in an adversarial pipeline, so as to deceive the discriminator that recovers the targeted group from filtered post embeddings. To maintain scalability and generalizability, we innovatively parameterize all filter functions via a hypernetwork. Taking a target's pretrained word embedding as input, the hypernetwork generates the weights used by each target-specific filter on-the-fly without storing dedicated filter parameters. In addition, a novel semantic gap alignment scheme is imposed on the generation process, such that the produced filter function for an unseen target is rectified by its semantic affinity with existing targets used for training. Finally, experiments are conducted on two benchmark HSD datasets, showing advantageous performance of GetFair on out-of-sample targets among baselines.
Large language models (LLMs) have achieved impressive success across various domains, but their capability in understanding and resolving complex graph problems is less explored. To bridge this gap, we introduce GraphInstruct, a novel instruction-tuning dataset aimed at enabling language models to tackle a broad spectrum of graph problems through explicit reasoning paths. Utilizing GraphInstruct, we build GraphWiz, an open-source language model capable of solving various graph computational problems while generating clear reasoning processes. To further enhance the model's performance and reliability, we integrate the Direct Preference Optimization (DPO) framework within the graph problem-solving context. The improved model, GraphWiz-DPO, achieves an average accuracy of 65% across nine tasks with different complexity levels, surpassing GPT-4 which has an average accuracy of 43.8%. Our study also investigates the relationship between training data volume and model performance, emphasizing the risk of overfitting as data volume increases. Additionally, we explore the transferability of the proposed model across different tasks and datasets, demonstrating its robust zero-shot generalization capability. GraphWiz offers a new blueprint and valuable insights for developing LLMs specialized in graph reasoning and problem-solving.
Calibration of Time-Series Forecasting: Detecting and Adapting Context-Driven Distribution Shift
PDF ↗Recent years have witnessed the success of introducing deep learning models to time series forecasting. From a data generation perspective, we illustrate that existing models are susceptible to distribution shifts driven by temporal contexts, whether observed or unobserved. Such context-driven distribution shift (CDS) introduces biases in predictions within specific contexts and poses challenges for conventional training paradigms. In this paper, we introduce a universal calibration methodology for the detection and adaptation of CDS with a trained model. To this end, we propose a novel CDS detector, termed the "residual-based CDS detector" or "Reconditionor", which quantifies the model's vulnerability to CDS by evaluating the mutual information between prediction residuals and their corresponding contexts. A high Reconditionor score indicates a severe susceptibility, thereby necessitating model adaptation. In this circumstance, we put forth a straightforward yet potent adapter framework for model calibration, termed the "sample-level contextualized adapter" or "SOLID". This framework involves the curation of a contextually similar dataset to the provided test sample and the subsequent fine-tuning of the model's prediction layer with a limited number of steps. Our theoretical analysis demonstrates that this adaptation strategy can achieve an optimal bias-variance trade-off. Notably, our proposed Reconditionor and SOLID are model-agnostic and readily adaptable to a wide range of models. Extensive experiments show that SOLID consistently enhances the performance of current forecasting models on real-world datasets, especially on cases with substantial CDS detected by the proposed Reconditionor, thus validating the effectiveness of the calibration approach.
Sequential recommendation (SR) and multi-behavior sequential recommendation (MBSR) both come from real-world scenarios. Compared with SR, MBSR takes into account the dependencies of different behaviors. We find that most existing works on MBSR are studied in the context of e-commerce scenarios. In terms of the data format of the behavior types, we observe that the conventional label-formatted data carries limited information and is inadequate for scenarios like social media. With this observation, we introducebehavior set and extend MBSR to behavior set-informed sequential recommendation (BSSR). In BSSR, behavior dependencies become more complex and personalized, and user interest arousal may lack explicit contextual associations. To delve into the dynamics inhered within a behavior set and adaptively tailor recommendation lists upon its variability, we propose a novel solution called Explicit and Implicit modeling via Dual-Path Transformer (EIDP) for BSSR. Our EIDP adopts a dual-path architecture, distinguishing between explicit modeling path (EMP) and implicit modeling path (IMP) based on whether to directly incorporate the behavior representations. EMP features the personalized behavior set-wise transition pattern extractor (PBS-TPE) as its core component. It couples behavioral representations with both the items and positions to explore intra-behavior dynamics within a behavior set at a fine granularity. IMP utilizes light multi-head self-attention blocks (L-MSAB) as encoders under specific behavior types. The obtained multi-view representations are then aggregated by cross-behavior attention fusion (CBAF), using the behavior set of the next time step as a guidance to extract collaborative semantics at the behavioral level. Extensive experiments on two real-world datasets demonstrate the effectiveness of our EIDP. We release the implementation code at: https://github.com/OshiNoCSMA/EIDP.
With the expansion and growth of cities, profiling urban areas with the advent of multi-modal urban datasets (e.g., points-of-interest and street view imagery) has become increasingly important in urban planing and management. Particularly, street view images have gained popularity for understanding the characteristics of urban areas due to its abundant visual information and inherent correlations with human activities. In this study, we define a street segment represented by multiple street view images as the minimum spatial unit for analysis and predict its functional and socioeconomic indicators, which presents several challenges in modeling spatial distributions of images on a street and the spatial topology (adjacency) of streets. Meanwhile, Large Language Models are capable of understanding imagery data based on its extraordinary knowledge base and unveil a remarkable opportunity for profiling streets with images. In view of the challenges and opportunity, we present a semi-supervised Urban Street Profiling Model (USPM) based on street view imagery and spatial adjacency of urban streets. Specifically, given a street with multiple images, we first employ a newly designed spatial context-based contrastive learning method to generate feature vectors of images and then apply the LSTM-based fusion method to encode multiple images on a street to yield the street visual representation; we then create the descriptions of street scenes for street view images based on the SPHINX (a large language model) and produce the street textual representation; finally, we build an urban street graph based on spatial topology (adjacency) and employ a semi-supervised graph learning algorithm to further encode the street representations for prediction. We conduct thorough experiments with real-world datasets to assess the proposed USPM. The experimental results demonstrate that USPM considerably outperforms baseline methods in two urban prediction tasks.
Heterogeneous information networks (HIN) have gained increasing popularity in recent years for capturing complex relations between diverse types of nodes. Meta-structures are proposed as a useful tool to identify the important patterns in HINs, but hand-crafted meta-structures pose significant challenges for scaling up, drawing wide research attention towards developing automatic search algorithms. Previous efforts primarily focused on searching for meta-structures with good empirical performance, overlooking the importance of human comprehensibility and generalizability. To address this challenge, we draw inspiration from the emergent reasoning abilities of large language models (LLMs). We propose ReStruct, a meta-structure search framework that integrates LLM reasoning into the evolutionary procedure. ReStruct uses a grammar translator to encode the meta-structures into natural language sentences, and leverages the reasoning power of LLMs to evaluate their semantic feasibility. Besides, ReStruct also employs performance-oriented evolutionary operations. These two competing forces allow ReStruct to jointly optimize the semantic explainability and empirical performance of meta-structures. Furthermore, ReStruct contains a differential LLM explainer to generate and refine natural language explanations for the discovered meta-structures by reasoning through the search history. Experiments on eight representative HIN datasets demonstrate that ReStruct achieves state-of-the-art performance in both recommendation and node classification tasks. Moreover, a survey study involving 73 graduate students shows that the discovered meta-structures and generated explanations by ReStruct are substantially more comprehensible. Our code and questionnaire are available at https://github.com/LinChen-65/ReStruct.
Clustering is one of the most commonly used techniques for unsupervised data analysis. As real data sets are usually composed of numerical and categorical features that are heterogeneous in nature, the heterogeneity in the distance metric and feature coupling prevents deep representation learning from achieving satisfactory clustering accuracy. Currently, supervised Quaternion Representation Learning (QRL) has achieved remarkable success in efficiently learning informative representations of coupled features from multiple views derived endogenously from the original data. To inherit the advantages of QRL for unsupervised heterogeneous feature representation learning, we propose a deep QRL model that works in an encoder-decoder manner. To ensure that the implicit couplings of heterogeneous feature data can be well characterized by representation learning, a hierarchical coupling encoding strategy is designed to convert the data set into an attributed graph to be the input of QRL. We also integrate the clustering objective into the model training to facilitate a joint optimization of the representation and clustering. Extensive experimental evaluations illustrate the superiority of the proposed Quaternion Graph Representation Learning (QGRL) method in terms of clustering accuracy and robustness to various data sets composed of arbitrary combinations of numerical and categorical features. The source code is opened at https://github.com/Juny-Chen/QGRL.git.
Data organized in tabular format is ubiquitous in real-world applications, and users often craft tables with biased feature definitions and flexibly set prediction targets of their interests. Thus, a rapid development of a robust, effective, dataset-versatile, user-friendly tabular prediction approach is highly desired. While Gradient Boosting Decision Trees (GBDTs) and existing deep neural networks (DNNs) have been extensively utilized by professional users, they present several challenges for casual users, particularly: (i) the dilemma of model selection due to their different dataset preferences, and (ii) the need for heavy hyperparameter searching, failing which their performances are deemed inadequate. In this paper, we delve into this question: Can we develop a deep learning model that serves as a sure bet solution for a wide range of tabular prediction tasks, while also being user-friendly for casual users? We delve into three key drawbacks of deep tabular models, encompassing: (P1) lack of rotational variance property, (P2) large data demand, and (P3) over-smooth solution. We propose ExcelFormer, addressing these challenges through a semi-permeable attention module that effectively constrains the influence of less informative features to break the DNNs' rotational invariance property (for P1), data augmentation approaches tailored for tabular data (for P2), and attentive feedforward network to boost the model fitting capability (for P3). These designs collectively make ExcelFormer a sure bet solution for diverse tabular datasets. Extensive and stratified experiments conducted on real-world datasets demonstrate that our model outperforms previous approaches across diverse tabular data prediction tasks, and this framework can be friendly to casual users, offering ease of use without the heavy hyperparameter tuning. The codes are available at https://github.com/whatashot/excelformer.
Signed networks, characterized by edges labeled as either positive or negative, offer nuanced insights into interaction dynamics beyond the capabilities of unsigned graphs. Central to this is the task of identifying the maximum balanced subgraph, crucial for applications like polarized community detection in social networks and portfolio analysis in finance. Traditional models, however, are limited by an assumption of perfect partitioning, which fails to mirror the complexities of real-world data. Addressing this gap, we introduce an innovative generalized balanced subgraph model that incorporates tolerance for imbalance. Our proposed region-based heuristic algorithm, tailored for this NP -hard problem, strikes a balance between low time complexity and high-quality outcomes. Comparative experiments validate its superior performance against leading solutions, delivering enhanced effectiveness (notably larger subgraph sizes) and efficiency (achieving up to 100× speedup) in both traditional and generalized contexts.
Slow task detection is a critical problem in cloud operation and maintenance since it is highly related to user experience and can bring substantial liquidated damages. Most anomaly detection methods detect it from a single-task aspect. However, considering millions of concurrent tasks in large-scale cloud computing clusters, it becomes impractical and inefficient. Moreover, single-task slowdowns are very common and do not necessarily indicate a malfunction of a cluster due to its violent fluctuation nature in a virtual environment. Thus, we shift our attention to cluster-wide task slowdowns by utilizing the duration time distribution of tasks across a cluster, so that the computation complexity is not relevant to the number of tasks. The task duration time distribution often exhibits compound periodicity and local exceptional fluctuations over time. Though transformer-based methods are one of the most powerful methods to capture these time series normal variation patterns, we empirically find and theoretically explain the flaw of the standard attention mechanism in reconstructing subperiods with low amplitude when dealing with compound periodicity. To tackle these challenges, we propose SORN (i.e., Skimming Off subperiods in descending amplitude order and Reconstructing Non-slowing fluctuation), which consists of a Skimming Attention mechanism to reconstruct the compound periodicity and a Neural Optimal Transport module to distinguish cluster-wide slowdowns from other exceptional fluctuations. Furthermore, since anomalies in the training set are inevitable in a practical scenario, we propose a picky loss function, which adaptively assigns higher weights to reliable time slots in the training set. Extensive experiments demonstrate that SORN outperforms state-of-the-art methods on multiple real-world industrial datasets.
We consider a recommender system that takes into account the interplay between recommendations, the evolution of user interests, and harmful content. We model the impact of recommendations on user behavior, particularly the tendency to consume harmful content. We seek recommendation policies that establish a tradeoff between maximizing click-through rate (CTR) and mitigating harm. We establish conditions under which the user profile dynamics have a stationary point, and propose algorithms for finding an optimal recommendation policy at stationarity. We experiment on a semi-synthetic movie recommendation setting initialized with real data and observe that our policies outperform baselines at simultaneously maximizing CTR and mitigating harm.
Scientific papers of a large scale on the Internet encompass a wealth of data and knowledge, attracting the attention of numerous researchers. To fully utilize these knowledge, Retrieval-Augmented Large Language Models (LLMs) usually leverage large-scale scientific corpus to train and then retrieve relevant passages from external memory to improve generation, which have demonstrated outstanding performance. However, existing methods can only capture one-dimension fragmented textual information without incorporating hierarchical structural knowledge, eg. the deduction relationship of abstract and main body, which makes it difficult to grasp the central thought of papers. To tackle this problem, we propose a hierarchical context augmentation method, which helps Retrieval-Augmented LLMs to autoregressively learn the structure knowledge of scientific papers. Specifically, we utilize the document tree to represent the hierarchical relationship of a paper and enhance the structure information of scientific context from three aspects: scale, format and global information. First, we think each top-bottom path of document tree is a logical independent context, which can be used to largely increase the scale of extracted structural corpus. Second, we propose a novel label-based format to represent the structure of context in textual sequences, unified between training and inference. Third, we introduce the global information of retrieved passages to further enhance the structure of context. Extensive experiments on three scientific tasks show that the proposed method significantly improves the performance of Retrieval-Augmented LLMs on all tasks. Besides, our method achieves start-of-art performance in Question Answer task and outperforms ChatGPT. Moreover, it also brings considerate gains with irrelevant retrieval passages, illustrating its effectiveness on practical application scenarios.
Graph Neural Networks (GNNs) have achieved great success in Knowledge Graph Completion (KGC) by modelling how entities and relations interact in recent years. However, the explanation of the predicted facts has not caught the necessary attention. Proper explanations for the results of GNN-based KGC models increase model transparency and help researchers develop more reliable models. Existing practices for explaining KGC tasks rely on instance/subgraph-based approaches, while in some scenarios, paths can provide more user-friendly and interpretable explanations. Nonetheless, the methods for generating path-based explanations for KGs have not been well-explored. To address this gap, we propose Power-Link, the first path-based KGC explainer that explores GNN-based models. We design a novel simplified graph-powering technique, which enables the generation of path-based explanations with a fully parallelisable and memory-efficient training scheme. We further introduce three new metrics for quantitative evaluation of the explanations, together with a qualitative human evaluation. Extensive experiments demonstrate that Power-Link outperforms the SOTA baselines in interpretability, efficiency, and scalability. The code is available at https://github.com/OUTHIM/power-link
Graph Neural Networks (GNNs) have demonstrated powerful capabilities in reasoning within Knowledge Graphs (KGs), gathering increasing attention. Our idea stems from the observation that the prior work typically employs hand-designed or sample-designed paradigms in the process of message propagation, engaging a set of adjacent entities at each step of propagation. As a result, such methods struggle with the increasing number of entities involved as propagation steps extend. Moreover, they neglect the message interactions between adjacent entities and propagation relations in KG reasoning, leading to semantic inconsistency during the message aggregation phase. To address these issues, we introduce a novel knowledge graph embedding method through a diffusion process, termed DiffusionE. Specifically, we reformulate the message propagation in knowledge reasoning as a diffusion process, regarding the message semantics as the diffusion signal. In this sense, guided by semantic information, messages can be transmitted between nodes effectively and adaptively. Furthermore, the theoretical analysis suggests our method can leverage an optimal diffusivity for message propagation in the semantic interactions of KGs. It shows that DiffusionE effectively leverages message interactions between entities and propagation relations, ensuring semantic consistency in KG reasoning. Comprehensive experiments reveal that our method attains state-of-the-art performance compared to prior work on several well-established benchmarks.