OpenRaiser/Intern-Atlas huggingface dataset:
Algorithmic fairness on graphs: Methods and trends
Authors: Jian Kang 0008, Hanghang Tong
Venue: Conference KDD 2022
Year: 2022

Graph is a ubiquitous type of data that appears in many real-world applications, including social network analysis, recommendations and financial security. Important as it is, decades of research have developed plentiful computational models to mine graphs. Despite its prosperity, concerns with respect to the potential algorithmic discrimination have been grown recently. Algorithmic fairness on graphs, which aims to mitigate bias introduced or amplified during the graph mining process, is an attractive yet challenging research topic. The first challenge corresponds to the theoretical challenge, where the non-IID nature of graph data may not only invalidate the basic assumption behind many existing studies in fair machine learning, but also introduce new fairness definition(s) based on the inter-correlation between nodes rather than the existing fairness definition(s) in fair machine learning. The second challenge regarding its algorithmic aspect aims to understand how to balance the trade-off between model accuracy and fairness. This tutorial aims to (1) comprehensively review the state-of-the-art techniques to enforce algorithmic fairness on graphs and (2) enlighten the open challenges and future directions. We believe this tutorial could benefit researchers and practitioners from the areas of data mining, artificial intelligence and social science.
Everything perturbed all at once: Enabling differentiable graph attacks
Authors: Haoran Liu, Bokun Wang, Jianling Wang, Xiangjue Dong, Tianbao Yang, James Caverlee
Venue: Conference WWW 2024
Year: 2024

While revolutionizing social networks, recommendation systems, and online web services, graph neural networks are vulnerable to adversarial attacks. Recent state-of-the-art adversarial attacks rely on gradient-based meta-learning to selectively perturb a single edge with the highest attack score until they reach the budget constraint. While effective in identifying vulnerable links, these methods are plagued by high computational costs. By leveraging continuous relaxation and parameterization of the graph structure, we propose a novel attack method -- DGA to efficiently generate effective attacks and meanwhile eliminate the need for costly retraining. Compared to the state-of-the-art, DGA achieves nearly equivalent attack performance with 6 times less training time and 11 times smaller GPU memory footprint on different benchmark datasets. Additionally, we provide extensive experimental analyses of the transferability of DGA among different graph models, as well as its robustness against widely-used defense mechanisms.
Multiscale representation enhanced temporal flow fusion model for long-term workload forecasting
Authors: Shiyu Wang, Zhixuan Chu, Yinbo Sun, Yu Liu, Yuliang Guo, Yang Chen, Huiyang Jian, Lintao Ma, Xingyu Lu, Jun Zhou
Venue: Conference CIKM 2024
Year: 2024

Accurate workload forecasting is critical for efficient resource management in cloud computing systems, enabling effective scheduling and autoscaling. Despite recent advances with transformer-based forecasting models, challenges remain due to the non-stationary, nonlinear characteristics of workload time series and the long-term dependencies. In particular, inconsistent performance between long-term history and near-term forecasts hinders long-range predictions. This paper proposes a novel framework leveraging self-supervised multiscale representation learning to capture both long-term and near-term workload patterns. The long-term history is encoded through multiscale representations while the near-term observations are modeled via temporal flow fusion. These representations of different scales are fused using an attention mechanism and characterized with normalizing flows to handle non-Gaussian/non-linear distributions of time series. Extensive experiments on 9 benchmarks demonstrate superiority over existing methods.
Personalized imputation on wearable-sensory time series via knowledge transfer
Authors: Xian Wu, Stephen M. Mattingly, Shayan Mirjafari, Chao Huang, Nitesh V. Chawla
Venue: Conference CIKM 2020
Year: 2020

The analysis of wearable-sensory time series data (e.g., heart rate records) benefits many applications (e.g., activity recognition, disease diagnosis). However, sensor measurements usually contain missing values due to various factors (e.g., user behavior, lack of charging), which may degrade the performance of downstream analytical tasks (e.g., regression, prediction). Thus, time series imputation is desired, which is capable of making sensory time series complete. Existing time series imputation methods generally employ various deep neural network models (e.g., GRU and GAN) to fill missing values by leveraging temporal patterns extracted from the contextual observations. Despite their effectiveness, we argue that most existing models can only achieve sub-optimal imputation performance due to the fact that they are inherently limited in sharing only one single set of model parameters to perform imputation on all individuals. Relying on one set of parameters limits the expressiveness of the imputation model as such models are bound to fail in capturing various complex personal characteristics. Therefore, most existing models tend to achieve inferior imputation performance, especially when a long duration of missing values, i.e., a large gap, is observed in the time series data. To address the limitation, this work develops a new imputation framework--Personalized Wearable-Sensory Time Series Imputation framework (PTSI) to provide a fully personalized treatment for time series imputation via effective knowledge transfer. In particular, PTSI first leverages a meta-learning paradigm to learn a well-generalized initialization to facilitate the adaption process for each user. To make the time series imputation be reflective of an individual's unique characteristics, we further endow PTSI with the capability of learning personalized model parameters, which is achieved by designing a parameter initialization modulating component. Extensive experiments on real-world human heart rate datasets demonstrate that our PTSI framework outperforms various state-of-the-art methods by a large margin consistently.
Re-weighting negative samples for model-agnostic matching
Authors: Jiazhen Lou, Hong Wen, Fuyu Lv, Jing Zhang, Tengfei Yuan, Zhao Li
Venue: Conference SIGIR 2022
Year: 2022

Recommender Systems (RS), as an efficient tool to discover users' interested items from a very large corpus, has attracted more and more attention from academia and industry. As the initial stage of RS, large-scale matching is fundamental yet challenging. A typical recipe is to learn user and item representations with a two-tower architecture and then calculate the similarity score between both representation vectors, which however still struggles in how to properly deal with negative samples. In this paper, we find that the common practice that randomly sampling negative samples from the entire space and treating them equally is not an optimal choice, since the negative samples from different sub-spaces at different stages have different importance to a matching model. To address this issue, we propose a novel method named Unbiased Model-Agnostic Matching Approach (UMA$^2$). It consists of two basic modules including 1) General Matching Model (GMM), which is model-agnostic and can be implemented as any embedding-based two-tower models; and 2) Negative Samples Debias Network (NSDN), which discriminates negative samples by borrowing the idea of Inverse Propensity Weighting (IPW) and re-weighs the loss in GMM. UMA$^2$ seamlessly integrates these two modules in an end-to-end multi-task learning framework. Extensive experiments on both real-world offline dataset and online A/B test demonstrate its superiority over state-of-the-art methods.
Enhancing pre-ranking performance: Tackling intermediary challenges in multi-stage cascading recommendation systems
Authors: Jianping Wei, Yujie Zhou, Zhengwei Wu, Ziqi Liu
Venue: Conference KDD 2024
Year: 2024

Large-scale search engines and recommendation systems utilize a three-stage cascading architecture-recall, pre-ranking, and ranking-to deliver relevant results within stringent latency limits. The pre-ranking stage is crucial for filtering a large number of recalled items into a manageable set for the ranking stage, greatly affecting the system's performance. Pre-ranking faces two intermediary challenges: Sample Selection Bias (SSB) arises when training is based on ranking stage feedback but the evaluation is on a broader recall dataset. Also, compared to the ranking stage, simpler pre-rank models may perform worse and less consistently. Traditional methods to tackle SSB issues include using all recall results and treating unexposed portions as negatives for training, which can be costly and noisy. To boost performance and consistency, some pre-ranking feature interaction enhancers don't fully fix consistency issues, while methods like knowledge distillation in ranking models ignore exposure bias. Our proposed framework targets these issues with three integral modules: Sample Selection, Domain Adaptation, and Unbiased Distillation. Sample Selection filters recall results to mitigate SSB and compute costs. Domain Adaptation enhances model robustness by assigning pseudo-labels to unexposed samples. Unbiased Distillation uses exposure-independent scores from Domain Adaptation to implement unbiased distillation for the pre-ranking model. The framework focuses on optimizing pre-ranking while maintaining training efficiency. We introduce new metrics for pre-ranking evaluation, while experiments confirm the effectiveness of our framework. Our framework is also deployed in real industrial systems.
Cmdiagnostor: An ambiguity-aware root cause localization approach based on call metric data
Authors: Qingyang Yu, Changhua Pei, Bowen Hao, Mingjie Li, Zeyan Li, Shenglin Zhang, Xianglin Lu, Rui Wang, Jiaqi Li, Zhenyu Wu, Dan Pei
Venue: Conference WWW 2023
Year: 2023

The availability of online services is vital as its strong relevance to revenue and user experience. To ensure online services’ availability, quickly localizing the root causes of system failures is crucial. Given the high resource consumption of traces, call metric data are widely used by existing approaches to construct call graphs in practice. However, ambiguous correspondences between upstream and downstream calls may exist and result in exploring unexpected edges in the constructed call graph. Conducting root cause localization on this graph may lead to misjudgments of real root causes. To the best of our knowledge, we are the first to investigate such ambiguity, which is overlooked in the existing literature. Inspired by the law of large numbers and the Markov properties of network traffic, we propose a regression-based method (named AmSitor) to address this problem effectively. Based on AmSitor, we propose an ambiguity-aware root cause localization approach based on Call Metric Data named CMDiagnostor, containing metric anomaly detection, ambiguity-free call graph construction, root cause exploration, and candidate root cause ranking modules. The comprehensive experimental evaluations conducted on real-world datasets show that our CMDiagnostor can outperform the state-of-the-art approaches by 14% on the top-5 hit rate. Moreover, AmSitor can also be applied to existing baseline approaches separately to improve their performances one step further. The source code is released at https://github.com/NetManAIOps/CMDiagnostor.
On the sensitivity of individual fairness: Measures and robust algorithms
Authors: Xinyu He, Jian Kang, Ruizhong Qiu, Fei Wang, Jose Sepulveda, Hanghang Tong
Venue: Conference CIKM 2024
Year: 2024

Algorithmic fairness has been receiving increasing attention in recent years. Among others, individual fairness, with its root in the dictionary definition of fairness, offers a fine-grained fairness notion. At the algorithmic level, individual fairness can often be operationalized as a convex regularization term with respect to a similarity matrix. Appealing as it might be, a notorious challenge of individual fairness lies in how to find appropriate distance or similarity measure, which largely remains open to date. Consequently, the similarity or distance measure used in almost any individually fair algorithm is likely to be imperfect due to various reasons such as imprecise prior/domain knowledge, noise, or even adversaries. In this paper, we take an important step towards resolving this fundamental challenge and ask: how sensitive is the individually fair learning algorithm with respect to the given similarities? How can we make the learning results robust with respect to the imperfection of the given similarity measure? First (Soul-M), we develop a sensitivity measure to characterize how the learning outcomes of an individually fair learning algorithm change in response to the change of the given similarity measure. Second (Soul-A ), based on the proposed sensitive measure, we further develop a robust individually fair algorithm by adversarial learning that optimizes the similarity matrix to defend against L_∞ attack. A unique advantage of our sensitivity measure and robust algorithm lies in that they are applicable to a broad range of learning models as long as the objective function is twice differentiable. We conduct extensive experiments to demonstrate the efficacy of our methods.
AIM: Attributing, interpreting, mitigating data unfairness
Authors: Zhining Liu 0002, Ruizhong Qiu, Zhichen Zeng 0001, Yada Zhu, Hendrik F. Hamann, Hanghang Tong
Venue: Conference KDD 2024
Year: 2024

Data collected in the real world often encapsulates historical discrimination against disadvantaged groups and individuals. Existing fair machine learning (FairML) research has predominantly focused on mitigating discriminative bias in the model prediction, with far less effort dedicated towards exploring how to trace biases present in the data, despite its importance for the transparency and interpretability of FairML. To fill this gap, we investigate a novel research problem: discovering samples that reflect biases/prejudices from the training data. Grounding on the existing fairness notions, we lay out a sample bias criterion and propose practical algorithms for measuring and countering sample bias. The derived bias score provides intuitive sample-level attribution and explanation of historical bias in data. On this basis, we further design two FairML strategies via sample-bias-informed minimal data editing. They can mitigate both group and individual unfairness at the cost of minimal or zero predictive utility loss. Extensive experiments and analyses on multiple real-world datasets demonstrate the effectiveness of our methods in explaining and mitigating unfairness. Code is available at https://github.com/ZhiningLiu1998/AIM.
Causal learning empowered od prediction for urban planning
Authors: Jinwei Zeng, Guozhen Zhang, Can Rong, Jingtao Ding, Jian Yuan, Yong Li
Venue: Conference CIKM 2022
Year: 2022

Predicting future origin-destination (OD) flow is essential for urban planning since it provides feedback for planning adjustment and reference for road planning. However, OD prediction for urban planning scenarios is unique as it typically lacks training data. A common practice is to refer to data from other cities, which causes the out-of-distribution (OOD) problem. A promising solution is to leverage causal information in the data. However, there are two challenges in utilizing causal information in urban planning scenarios: (a) Urban system has numerous factors, and only part of them indicate causal information. (b) The planned city development correlates with original city characteristics, therefore bringing confounding bias to the causal modelling process. In this paper, we propose designs to solve both challenges. Specifically, we first design a causal disentangled representation module to identify causal factors in attributes. Second, we adopt a variational sample re-weighting module to reduce the confounding bias. Our proposed model outperforms seven state-of-the-art baselines on three real-world datasets, achieving an average improvement of 9.59% in the MAE metric. Further in-depth analysis shows our method's robustness across different urban planning scenarios and outstanding performance in predicting extremely large OD flows, which corroborates the contribution of our designs to the urban planning field.
Non-parametric policy gradients: a unified treatment of propositional and relational domains
Authors: Kristian Kersting, Kurt Driessens
Venue: Conference ICML 2008
Year: 2008

Policy gradient approaches are a powerful instrument for learning how to interact with the environment. Existing approaches have focused on propositional and continuous domains only. Without extensive feature engineering, it is difficult – if not impossible – to apply them within structured domains, in which e.g. there is a varying number of objects and relations among them. In this paper, we describe a non-parametric policy gradient approach – called NPPG – that overcomes this limitation. The key idea is to apply Friedmann’s gradient boosting: policies are represented as a weighted sum of regression models grown in an stage-wise optimization. Employing off-the-shelf regression learners, NPPG can deal with propositional, continuous, and relational domains in a unified way. Our experimental results show that it can even improve on established results.
Temporal dynamics-aware adversarial attacks on discrete-time dynamic graph models
Authors: Kartik Sharma, Rakshit Trivedi, Rohit Sridhar, Srijan Kumar
Venue: Conference KDD 2023
Year: 2023

Real-world graphs such as social networks, communication networks, and rating networks are constantly evolving over time. Many deep learning architectures have been developed to learn effective node representations using both graph structure and dynamics. While being crucial for practical applications, the robustness of these representation learners for dynamic graphs in the presence of adversarial attacks is highly understudied. In this work, we design a novel adversarial attack on discrete-time dynamic graph models where we desire to perturb the input graph sequence in a manner that preserves the temporal dynamics of the graph while dropping the performance of representation learners. To this end, we motivate a novel Temporal Dynamics-Aware Perturbation (TDAP) constraint, which ensures that perturbations introduced at each time step are restricted to only a small fraction of the number of changes in the graph since the previous time step. We present a theoretically-motivated Projected Gradient Descent approach for dynamic graphs to find effective perturbations under the TDAP constraint. Experiments on two tasks - dynamic link prediction and node classification, show that our approach is up to 4x more effective than the baseline methods for attacking these models. We extend our approach to a more practical online setting where graphs become available in real-time and show up to 5x superior performance over baselines We also show that our approach successfully evades state-of-the-art neural approaches for anomaly detection, thereby promoting the need to study robustness as a part of representation-learning approaches for dynamic graphs.
The snowflake hypothesis: Training and powering gnn with one node one receptive field
Authors: Kun Wang 0056, Guohao Li 0001, Shilong Wang 0002, Guibin Zhang, Kai Wang 0036, Yang You 0001, Junfeng Fang, Xiaojiang Peng, Yuxuan Liang 0002, Yang Wang 0015
Venue: Conference KDD 2024
Year: 2024

Despite Graph Neural Networks (GNNs) demonstrating considerable promise in graph representation learning tasks, GNNs predominantly face significant issues with overfitting and over-smoothing as they go deeper as models of computer vision (CV) realm. The success of artificial intelligence in computer vision and natural language processing largely stems from its ability to train deep models effectively. We have thus conducted a systematic study on deep GNN models. Our findings indicate that the current success of deep GNNs primarily stems from (I) the adoption of innovations from CNNs, such as residual/skip connections, or (II) the tailor-made aggregation algorithms like DropEdge. However, these algorithms often lack intrinsic interpretability and indiscriminately treat all nodes within a given layer in a similar manner, thereby failing to capture the nuanced differences among various nodes. In this paper, we introduce the Snowflake Hypothesis -- a novel paradigm underpinning the concept of "one node, one receptive field''. The hypothesis draws inspiration from the unique and individualistic patterns of each snowflake, proposing a corresponding uniqueness in the receptive fields of nodes in the GNNs. We employ the simplest gradient and node-level cosine distance as guiding principles to regulate the aggregation depth for each node, and conduct comprehensive experiments including: (1) different training scheme; (2) various shallow and deep GNN backbones; (3) various numbers of layers (8, 16, 32, 64) on multiple benchmarks; (4) compare with different aggregation strategies. The observational results demonstrate that our framework can serve as a universal operator for a range of tasks, and it displays tremendous potential on deep GNNs. Code is available at: https://github.com/CunWang520/Snowhypothe.
Does knowledge localization hold true? surprising differences between entity and relation perspectives in language models
Authors: Yifan Wei, Xiaoyan Yu, Yixuan Weng, Huanhuan Ma, Yuanzhe Zhang, Jun Zhao, Kang Liu
Venue: Conference CIKM 2024
Year: 2024

Large language models encapsulate knowledge and have demonstrated superior performance on various natural language processing tasks. Recent studies have localized this knowledge to specific model parameters, such as the MLP weights in intermediate layers. This study investigates the differences between entity and relational knowledge through knowledge editing. Our findings reveal that entity and relational knowledge cannot be directly transferred or mapped to each other. This result is unexpected, as logically, modifying the entity or the relation within the same knowledge triplet should yield equivalent outcomes. To further elucidate the differences between entity and relational knowledge, we employ causal analysis to investigate how relational knowledge is stored in pre-trained models. Contrary to prior research suggesting that knowledge is stored in MLP weights, our experiments demonstrate that relational knowledge is also significantly encoded in attention modules. This insight highlights the multifaceted nature of knowledge storage in language models, underscoring the complexity of manipulating specific types of knowledge within these models.
Association analysis-based transformations for protein interaction networks: a function prediction case study
Authors: Gaurav Pandey, Michael S. Steinbach, Rohit Gupta, Tushar Garg, Vipin Kumar
Venue: Conference KDD 2007
Year: 2007

Protein interaction networks are one of the most promising types of biological data for the discovery of functional modules and the prediction of individual protein functions. However, it is known that these networks are both incomplete and inaccurate, i.e., they have spurious edges and lackbiologically valid edges. One way to handle this problem is by transforming the original interaction graph into new graphs that remove spurious edges, add biologically valid ones, and assign reliability scores to the edges constituting the final network. We investigate currently existing methods, as well as propose a robust association analysis-based method for this task. This method is based on the concept of h-confidence, which is a measure that can be used to extract groups of objects having high similarity with each other. Experimental evaluation on several protein interaction data sets show that hyperclique-based transformations enhance the performance of standard function prediction algorithms significantly, and thus have merit.