论文检索

Kounianhua Du, Jizheng Chen, Jianghao Lin, Yunjia Xi, Hangyu Wang, Xinyi Dai, Bo Chen 0023, Ruiming Tang, Weinan Zhang 0001

Recommender systems play important roles in various applications such as e-commerce, social media, etc. Conventional recommendation methods usually model the collaborative signals within the tabular representation space. Despite the personalization modeling and the efficiency, the latent semantic dependencies are omitted. Methods that introduce semantics into recommendation then emerge, injecting knowledge from the semantic representation space where the general language understanding are compressed. However, existing semantic-enhanced recommendation methods focus on aligning the two spaces, during which the representations of the two spaces tend to get close while the unique patterns are discarded and not well explored. In this paper, we propose DisCo to Disentangle the unique patterns from the two representation spaces and Collaborate the two spaces for recommendation enhancement, where both the specificity and the consistency of the two spaces are captured. Concretely, we propose 1) a dual-side attentive network to capture the intra-domain patterns and the inter-domain patterns, 2) a sufficiency constraint to preserve the task-relevant information of each representation space and filter out the noise, and 3) a disentanglement constraint to avoid the model from discarding the unique information. These modules strike a balance between disentanglement and collaboration of the two representation spaces to produce informative pattern vectors, which could serve as extra features and be appended to arbitrary recommendation backbones for enhancement. Experiment results validate the superiority of our method against different models and the compatibility of DisCo over different backbones. Various ablation studies and efficiency analysis are also conducted to justify each model component.

Huaming Du, Long Shi 0002, Xingyan Chen, Yu Zhao 0019, Hegui Zhang, Carl Yang 0001, Fuzhen Zhuang, Gang Kou

Temporal graph representation learning has drawn considerable attention in recent years. Most existing works mainly focus on modeling local structural dependencies of temporal graphs. However, underestimating the inherent global structural role information in many real-world temporal graphs inevitably leads to sub-optimal graph representations. To overcome this shortcoming, we propose a novel Role-based Temporal Graph Convolution Network (RTGCN) that fully leverages the global structural role information in temporal graphs. Specifically, RTGCN can effectively capture the static global structural roles by using hypergraph convolution neural networks. To capture the evolution of nodes' structural roles, we further design structural role-based gated recurrent units. Finally, we integrate structural role proximity in our objective function to preserve global structural similarity, further promoting temporal graph representation learning. Experimental results on multiple real-world datasets demonstrate that RTGCN consistently outperforms state-of-the-art temporal graph representation learning methods by significant margins in various temporal link prediction and node classification tasks. Specifically, RTGCN achieves AUC improvement of up to 5.1% for link prediction and F1 improvement of up to 6.2% for new link prediction. In addition, RTGCN achieves AUC improvement up to 4.6% for node classification and 2.7% for structural role classification.

Andrew F. Dreher, Etienne Vouga, Donald S. Fussell

There are many applications for which we want to learn a latent scale for subjective properties, such as the excitement of a photo or the legibility of a font; however, obtaining human-labeled data is costly and time-consuming. One oft-used method for acquiring these labels, despite the cost being quadratic in the number of items, is the method of pairwise comparisons since this method minimizes the effect of biases and generally can be used effectively outside of a controlled environment. Crowdsourcing appears to be a panacea since online platforms provide affordable access to numerous people, but these participants, judges, vary in diligence and expertise. Several methods have been proposed to assign weights to judges based on their responses relative to everyone else, the goal being to reduce exposure to poor performers, hopefully upgrading the quality of the data. Our research focuses on two natural extensions to the Bradley-Terry-Luce formulation of scaling that jointly optimize for both scale value and judge weights. While both methods appear to perform at least as well as the unweighted formulation on average with well-behaved judges, we report a previously unknown flaw, revealing that the resultant judge weights should not be interpreted as reliabilities. Consequently, these values should not be leveraged for decisions about the judges, such as for active sampling or to validate the participant pool.

Zheng Dong 0006, Renhe Jiang, Haotian Gao, Hangchen Liu, Jinliang Deng, Qingsong Wen, Xuan Song 0001

Spatiotemporal time series forecasting plays a key role in a wide range of real-world applications. While significant progress has been made in this area, fully capturing and leveraging spatiotemporal heterogeneity remains a fundamental challenge. Therefore, we propose a novel Heterogeneity-Informed Meta-Parameter Learning scheme. Specifically, our approach implicitly captures spatiotemporal heterogeneity through learning spatial and temporal embeddings, which can be viewed as a clustering process. Then, a novel spatiotemporal meta-parameter learning paradigm is proposed to learn spatiotemporal-specific parameters from meta-parameter pools, which is informed by the captured heterogeneity. Based on these ideas, we develop a Heterogeneity-Informed Spatiotemporal Meta-Network (HimNet) for spatiotemporal time series forecasting. Extensive experiments on five widely-used benchmarks demonstrate our method achieves state-of-the-art performance while exhibiting superior interpretability. Our code is available at https://github.com/XDZhelheim/HimNet.

Yushun Dong, Binchi Zhang, Zhenyu Lei 0004, Na Zou 0001, Jundong Li

Graph Neural Networks (GNNs) have been increasingly deployed in a plethora of applications. However, the graph data used for training may contain sensitive personal information of the involved individuals. Once trained, GNNs typically encode such information in their learnable parameters. As a consequence, privacy leakage may happen when the trained GNNs are deployed and exposed to potential attackers. Facing such a threat, machine unlearning for GNNs has become an emerging technique that aims to remove certain personal information from a trained GNN. Among these techniques, certified unlearning stands out, as it provides a solid theoretical guarantee of the information removal effectiveness. Nevertheless, most of the existing certified unlearning methods for GNNs are only designed to handle node and edge unlearning requests. Meanwhile, these approaches are usually tailored for either a specific design of GNN or a specially designed training objective. These disadvantages significantly jeopardize their flexibility. In this paper, we propose a principled framework named IDEA to achieve flexible and certified unlearning for GNNs. Specifically, we first instantiate four types of unlearning requests on graphs, and then we propose an approximation approach to flexibly handle these unlearning requests over diverse GNNs. We further provide theoretical guarantee of the effectiveness for the proposed approach as a certification. Different from existing alternatives, IDEA is not designed for any specific GNNs or optimization objectives to perform certified unlearning, and thus can be easily generalized. Extensive experiments on real-world datasets demonstrate the superiority of IDEA in multiple key perspectives.

Manh Tuan Do, Kijung Shin

People usually interact in groups, and such groups may appear on different platforms. For instance, people often create various group chats on messaging apps (e.g., Facebook Messenger and WhatsApp) to communicate with families, friends, or colleagues. How do we identify the same people across the two platforms based on the information about the groups? This gives rise to the hypergraph alignment problem, whose objective is to find the correspondences between the sets of nodes of two hypergraphs. In a hypergraph, a node represents a person, and each hyperedge represents a group of several people. In addition, the two sets of hyperedges in the two hypergraphs can vary significantly in scales as people may use different apps at different time periods. In this work, we propose and tackle the problem of unsupervised hypergraph alignment. Given two hypergraphs with potentially different scales and without any side information or prior ground-truth correspondences, we develop ØurMethod, a learning framework, to find node correspondences across the two hypergraphs. ØurMethod directly addresses each challenge of the problem. In particular, it (a) extracts node features from the hypergraph topology, (b) employs contrastive learning, as a "supervised pseudo-alignment'' task to pre-train the learning model (c) applies topological augmentation to help a generative adversarial network to align the two embedding spaces from the two hypergraphs. The purpose of augmentation is to add virtual hyperedges from one hypergraph in order to the other to resolve the scale difference and share information across the two hypergraphs. Our extensive experiments on 12 real-world datasets demonstrate the significant and consistent superiority of ØurMethod over the baseline approaches.

Yucheng Ding, Chaoyue Niu, Fan Wu 0006, Shaojie Tang 0001, Chengfei Lyu, Guihai Chen

Many billion-scale large language models (LLMs) have been released for resource-constraint mobile devices to provide local LLM inference service when cloud-based powerful LLMs are not available. However, the capabilities of current on-device LLMs still lag behind those of cloud-based LLMs, and how to effectively and efficiently enhance on-device LLM inference becomes a practical requirement. We thus propose to collect the user's historical interactions with the cloud-based LLM and build an external datastore on the mobile device for enhancement using nearest neighbors search. Nevertheless, the full datastore improves the quality of token generation at the unacceptable expense of much slower generation speed. To balance performance and efficiency, we propose to select an optimal subset of the full datastore within the given size limit, the optimization objective of which is proven to be submodular. We further design an offline algorithm, which selects the subset after the construction of the full datastore, as well as an online algorithm, which performs selection over the stream and can be flexibly scheduled. We theoretically analyze the performance guarantee and the time complexity of the offline and the online designs to demonstrate effectiveness and scalability. We finally take three ChatGPT related dialogue datasets and four different on-device LLMs for evaluation. Evaluation results show that the proposed designs significantly enhance LLM performance in terms of perplexity while maintaining fast token generation speed. Practical overhead testing on the smartphone reveal the efficiency of on-device datastore subset selection from memory usage and computation overhead.

Xueying Ding, Yue Zhao 0016, Leman Akoglu

Deep neural network based Outlier Detection (DOD) has seen a recent surge of attention thanks to the many advances in deep learning. In this paper, we consider a critical-yet-understudied challenge with unsupervised DOD, that is, effective hyperparameter (HP) tuning/model selection. While several prior work report the sensitivity of OD models to HP settings, the issue is ever so critical for the modern DOD models that exhibit a long list of HPs. We introduce HYPER for tuning DOD models, tackling two fundamental challenges: (1) validation without supervision (due to lack of labeled outliers), and (2) efficient search of the HP/model space (due to exponential growth in the number of HPs). A key idea is to design and train a novel hypernetwork (HN) that maps HPs onto optimal weights of the main DOD model. In turn, HYPER capitalizes on a single HN that can dynamically generate weights for many DOD models (corresponding to varying HPs), which offers significant speed-up. In addition, it employs meta-learning on historical OD tasks with labels to train a proxy validation function, likewise trained with our proposed HN efficiently. Extensive experiments on different OD tasks show that HYPER achieves competitive performance against 8 baselines with significant efficiency gains.

Kaize Ding, Xiaoxiao Ma 0002, Yixin Liu 0001, Shirui Pan

Graph neural networks (GNNs) based on message passing have achieved remarkable performance in graph machine learning. By combining it with the power of pseudo labeling, one can further push forward the performance on the task of semi-supervised node classification. However, most existing works assume that the training node labels are purely noise-free, while this strong assumption usually does not hold in practice. GNNs will overfit the noisy training labels and the adverse effects of mislabeled nodes can be exaggerated by being propagated to the remaining nodes through the graph structure, exacerbating the model failure. Worse still, the noisy pseudo labels could also largely undermine the model's reliability without special treatment. In this paper, we revisit the role of (1) message passing and (2) pseudo labels in the studied problem and try to address two denoising subproblems from the model architecture and algorithm perspective, respectively. Specifically, we first develop a label-noise robust GNN that discards the coupled message-passing scheme. Despite its simple architecture, this learning backbone prevents overfitting to noisy labels and also inherently avoids the noise propagation issue. Moreover, we propose a novel reliable graph pseudo labeling algorithm that can effectively leverage the knowledge of unlabeled nodes while mitigating the adverse effects of noisy pseudo labels. Based on those novel designs, we can attain exceptional effectiveness and efficiency in solving the studied problem. We conduct extensive experiments on benchmark datasets for semi-supervised node classification with different levels of label noise and show new state-of-the-art performance. The code is available at https://github.com/DND-NET/DND-NET.

Yue Deng 0004, Asadullah Hill Galib, Pang-Ning Tan, Lifeng Luo

Disease surveillance, traffic management, and weather forecasting are some of the key applications that could benefit from block maxima forecasting of a time series as the extreme block maxima values often signify events of critical importance such as disease outbreaks, traffic gridlock, and severe weather conditions. As the use of deep neural network models for block maxima forecasting increases, so does the need for explainable AI methods that could unravel the inner workings of such black box models. To fill this need, this paper presents a novel counterfactual explanation framework for block maxima forecasting models. Unlike existing methods, our proposed framework, DiffusionCF, combines deep anomaly detection with a conditional diffusion model to identify unusual patterns in the time series that could help explain the forecasted extreme block maxima. Experimental results on several real-world datasets demonstrate the superiority of DiffusionCF over other baseline methods when evaluated according to various metrics, particularly their informativeness and closeness. Our data and codes are available at https://github.com/yue2023cs/DiffusionCF.

Thomas Decker 0004, Alexander Koebler, Michael Lebacher, Ingo Thon, Volker Tresp, Florian Buettner 0001

Monitoring and maintaining machine learning models are among the most critical challenges in translating recent advances in the field into real-world applications. However, current monitoring methods lack the capability of provide actionable insights answering the question of why the performance of a particular model really degraded. In this work, we propose a novel approach to explain the behavior of a black-box model under feature shifts by attributing an estimated performance change to interpretable input characteristics. We refer to our method that combines concepts from Optimal Transport and Shapley Values as Explanatory Performance Estimation (XPE). We analyze the underlying assumptions and demonstrate the superiority of our approach over several baselines on different data sets across various data modalities such as images, audio, and tabular data. We also indicate how the generated results can lead to valuable insights, enabling explanatory model monitoring by revealing potential root causes for model deterioration and guiding toward actionable countermeasures.

Siddhartha Shankar Das, S. M. Ferdous, Mahantesh M. Halappanavar, Edoardo Serra, Alex Pothen

We propose AGS-GNN, a novel attribute-guided sampling algorithm for Graph Neural Networks (GNNs). AGS-GNN exploits the node features and the connectivity structure of a graph while simultaneously adapting for both homophily and heterophily in graphs. In homophilic graphs, vertices of the same class are more likely to be adjacent, but vertices of different classes tend to be adjacent in heterophilic graphs. GNNs have been successfully applied to homophilic graphs, but their utility to heterophilic graphs remains challenging. The state-of-the-art GNNs for heterophilic graphs use the full neighborhood of a node instead of sampling it, and hence do not scale to large graphs and are not inductive. We develop dual-channel sampling techniques based on feature-similarity and feature-diversity to select subsets of neighbors for a node that capture adaptive information from homophilic and heterophilic neighborhoods. Currently, AGS-GNN is the only algorithm that explicitly controls homophily in the sampled subgraph through similar and diverse neighborhood samples. For diverse neighborhood sampling, we employ submodularity, a novel contribution in this context. We pre-compute the sampling distribution in parallel, achieving the desired scalability. Using an extensive dataset consisting of 35 small (< 100K nodes) and large (- 100K nodes) homophilic and heterophilic graphs, we demonstrate the superiority of AGS-GNN compared to the state-of-the-art approaches. AGS-GNN achieves test accuracy comparable to the best-performing heterophilic GNNs, even outperforming methods that use the entire graph for node classification. AGS-GNN converges faster than methods that sample neighborhoods randomly, and can be incorporated into existing GNN models that employ node or graph sampling.

Sunhao Dai, Yuqi Zhou 0001, Liang Pang 0001, Weihao Liu 0001, Xiaolin Hu 0001, Yong Liu 0018, Xiao Zhang 0034, Gang Wang 0056, Jun Xu 0001

Recently, the emergence of large language models (LLMs) has revolutionized the paradigm of information retrieval (IR) applications, especially in web search, by generating vast amounts of human-like texts on the Internet. As a result, IR systems in the LLM era are facing a new challenge: the indexed documents are now not only written by human beings but also automatically generated by the LLMs. How these LLM-generated documents influence the IR systems is a pressing and still unexplored question. In this work, we conduct a quantitative evaluation of IR models in scenarios where both human-written and LLM-generated texts are involved. Surprisingly, our findings indicate that neural retrieval models tend to rank LLM-generated documents higher. We refer to this category of biases in neural retrievers towards the LLM-generated content as the source bias. Moreover, we discover that this bias is not confined to the first-stage neural retrievers, but extends to the second-stage neural re-rankers. Then, in-depth analyses from the perspective of text compression indicate that LLM-generated texts exhibit more focused semantics with less noise, making it easier for neural retrieval models to semantic match. To mitigate the source bias, we also propose a plug-and-play debiased constraint for the optimization objective, and experimental results show its effectiveness. Finally, we discuss the potential severe concerns stemming from the observed source bias and hope our findings can serve as a critical wake-up call to the IR community and beyond. To facilitate future explorations of IR in the LLM era, the constructed two new benchmarks are available at https://github.com/KID-22/Source-Bias.

Shuang Cui, Kai Han 0003, Shaojie Tang 0001, Feng Li 0002, Jun Luo 0001

Submodular optimization has been identified as a powerful tool for many data mining applications, where a representative subset of moderate size needs to be extracted from a large-scale dataset. In scenarios where data points possess sensitive attributes such as age, gender, or race, it becomes imperative to integrate fairness measures into submodular optimization to mitigate bias and discrimination. In this paper, we study the fundamental problem of fair submodular maximization subject to a knapsack constraint and propose the first streaming algorithm for it with provable performance guarantees for both monotone and non-monotone submodular functions. As a byproduct, we also propose a streaming algorithm for submodular maximization subject to a partition matroid and a knapsack constraint, significantly improving the performance bounds achieved by previous work. We conduct extensive experiments on real-world applications such as movie recommendation, image summarization, and maximum coverage in social networks. The experimental results strongly demonstrate the superiority of our proposed algorithms in terms of both fairness and utility.

Jiajun Cui, Hong Qian, Bo Jiang 0016, Wei Zhang 0056

Knowledge tracing (KT) is a crucial task in intelligent education, focusing on predicting students' performance on given questions to trace their evolving knowledge. The advancement of deep learning in this field has led to deep-learning knowledge tracing (DLKT) models that prioritize high predictive accuracy. However, many existing DLKT methods overlook the fundamental goal of tracking students' dynamical knowledge mastery. These models do not explicitly model knowledge mastery tracing processes or yield unreasonable results that educators find difficulty to comprehend and apply in real teaching scenarios. In response, our research conducts a preliminary analysis of mainstream KT approaches to highlight and explain such unreasonableness. We introduce GRKT, a graph-based reasonable knowledge tracing method to address these issues. By leveraging graph neural networks, our approach delves into the mutual influences of knowledge concepts, offering a more accurate representation of how the knowledge mastery evolves throughout the learning process. Additionally, we propose a fine-grained and psychological three-stage modeling process as knowledge retrieval, memory strengthening, and knowledge learning/forgetting, to conduct a more reasonable knowledge tracing process. Comprehensive experiments demonstrate that GRKT outperforms eleven baselines across three datasets, not only enhancing predictive accuracy but also generating more reasonable knowledge tracing results. This makes our model a promising advancement for practical implementation in educational settings. The source code is available at https://github.com/JJCui96/GRKT.

Erica Coppolillo, Giuseppe Manco 0001, Aristides Gionis

Providing recommendations that are both relevant and diverse is a key consideration of modern recommender systems. Optimizing both of these measures presents a fundamental trade-off, as higher diversity typically comes at the cost of relevance, resulting in lower user engagement. Existing recommendation algorithms try to resolve this trade-off by combining the two measures, relevance and diversity, into one aim and then seeking recommendations that optimize the combined objective, for a given number of items. Traditional approaches, however, do not consider the user interaction with the suggested items. In this paper, we put the user at the central stage, and build on the interplay between relevance, diversity, and user behavior. In contrast to applications where the goal is solely to maximize engagement, we focus on scenarios aiming at maximizing the total amount of knowledge encountered by the user. We use diversity as a surrogate for the amount of knowledge obtained by the user while interacting with the system, and we seek to maximize diversity. We propose a probabilistic user-behavior model in which users keep interacting with the recommender system as long as they receive relevant suggestions, but they may stop if the relevance of the recommended items drops. Thus, for a recommender system to achieve a high-diversity measure, it will need to produce recommendations that are both relevant and diverse. Finally, we propose a novel recommendation strategy that combines relevance and diversity by a copula function. We conduct an extensive evaluation of the proposed methodology over multiple datasets, and we show that our strategy outperforms several state-of-the-art competitors. Our implementation is publicly available at https://github.com/EricaCoppolillo/EXPLORE.

Martino Ciaperoni, Han Xiao 0009, Aristides Gionis

Today, as increasingly complex predictive models are developed, simple rule sets remain a crucial tool to obtain interpretable predictions and drive high-stakes decision making. However, a single rule set provides a partial representation of a learning task. An emerging paradigm in interpretable machine learning aims at exploring the Rashomon set of all models exhibiting near-optimal performance. Existing work on Rashomon-set exploration focuses on exhaustive search of the Rashomon set for particular classes of models, which can be a computationally challenging task. On the other hand, exhaustive enumeration leads to redundancy that often is not necessary, and a representative sample or an estimate of the size of the Rashomon set is sufficient for many applications. In this work, we propose, for the first time, efficient methods to explore the Rashomon set of rule-set models with or without exhaustive search. Extensive experiments demonstrate the effectiveness of the proposed methods in a variety of scenarios.

In-Koo Cho, Jonathan A. Libgober, Cheng Ding

We propose an efficient boosting algorithm for multiclass classification, called AdaBoost.Iter, that extends SAMME and AdaBoost. The algorithm iteratively applies the weak learnability condition of SAMME to eliminate classes to find the correct classificiation. The iterative weak learnability is a sufficient and necessary condition for boostability, but it is also easier to validate than the EOR criterion of AdaBoost.MM \citeMukherjeeSchapire2013. We show that the training error of AdaBoost.Iter vanishes at the exponential rate, while the generalization error converges to zero at the same rate as AdaBoost. AdaBoost.Iter numerically outperforms SAMME and achieves performance comparable to AdaBoost.MM on benchmark datasets.

Hongliang Chi, Yao Ma 0001

Graph Neural Networks (GNN) have proven successful for graph-related tasks. However, many GNNs methods require labeled data, which is challenging to obtain. To tackle this, graph contrastive learning (GCL) have gained attention. GCL learns by contrasting similar nodes (positives) and dissimilar nodes (negatives). Current GCL methods, using data augmentation for positive samples and random selection for negative samples, can be sub-optimal due to limited positive samples and the possibility of false-negative samples. In this study, we propose an enhanced objective addressing these issues. We first introduce an ideal objective with all positive and no false-negative samples, then transform it probabilistically based on sampling distributions. We next model these distributions with node similarity and derive an enhanced objective. Comprehensive experiments have shown the effectiveness of the proposed enhanced objective for a broad set of GCL models.

Zhangtao Cheng, Jienan Zhang, Xovee Xu, Goce Trajcevski, Ting Zhong, Fan Zhou 0002

Accurately predicting the popularity of multimodal user-generated content (UGC) is fundamental for many real-world applications such as online advertising and recommendation. Existing approaches generally focus on limited contextual information within individual UGCs, yet overlook the potential benefit of exploiting meaningful knowledge in relevant UGCs. In this work, we propose RAGTrans, an aspect-aware retrieval-augmented multi-modal hypergraph transformer that retrieves pertinent knowledge from a multi-modal memory bank and enhances UGC representations via neighborhood knowledge aggregation on multi-model hypergraphs. In particular, we initially retrieve relevant multimedia instances from a large corpus of UGCs via the aspect information and construct a knowledge-enhanced hypergraph based on retrieved relevant instances. This allows capturing meaningful contextual information across the data. We then design a novel bootstrapping hypergraph transformer on multimodal hypergraphs to strengthen UGC representations across modalities via customizing a propagation algorithm to effectively diffuse information across nodes and edges. Additionally, we propose a user-aware attention-based fusion module to comprise the enriched UGC representations for popularity prediction. Extensive experiments on real-world social media datasets demonstrate that RAGTrans outperforms state-of-the-art popularity prediction models across settings.