OpenRaiser/Intern-Atlas huggingface dataset:
Machine Unlearning in Gradient Boosting Decision Trees
Authors: Huawei Lin 0001, Jun Woo Chung, Yingjie Lao, Weijie Zhao 0001
Venue: KDD
Year: 2023

Various machine learning applications take users' data to train the models. Recently enforced legislation requires companies to remove users' data upon requests, i.e.,the right to be forgotten. In the context of machine learning, the trained model potentially memorizes the training data. Machine learning algorithms have to be able to unlearn the user data that are requested to delete to meet the requirement. Gradient Boosting Decision Trees (GBDT) is a widely deployed model in many machine learning applications. However, few studies investigate the unlearning on GBDT. This paper proposes a novel unlearning framework for GBDT. To the best of our knowledge, this is the first work that considers machine unlearning on GBDT. It is not straightforward to transfer the unlearning methods of DNN to GBDT settings. We formalized the machine unlearning problem and its relaxed version. We propose an unlearning framework that efficiently and effectively unlearns a given collection of data without retraining the model from scratch. We introduce a collection of techniques, including random split point selection and random partitioning layers training, to the training process of the original tree models to ensure that the trained model requires few subtree retrainings during the unlearning. We investigate the intermediate data and statistics to store as an auxiliary data structure during the training so that we can immediately determine if a subtree is required to be retrained without touching the original training dataset. Furthermore, a lazy update technique is proposed as a trade-off between unlearning time and model functionality. We experimentally evaluate our proposed methods on public datasets. The empirical results confirm the effectiveness of our framework.
International Workshop on Multimodal Learning - 2023 Theme: Multimodal Learning with Foundation Models
Authors: Yuan Ling, Fanyou Wu, Shujing Dong, Yarong Feng, George Karypis, Chandan K. Reddy
Venue: KDD
Year: 2023

The recent advancements in machine learning and artificial intelligence (particularly foundation models such as BERT, GPT-3, T5, ResNet, etc.) have demonstrated remarkable capabilities and driven significant revolutionary changes to the way we make inferences from complex data. These models represent a fundamental shift in the way data are approached and offer exciting new research directions and opportunities for multimodal learning and data fusion. Given the potential of foundation models to transform the field of multimodal learning, there is a need to bring together experts and researchers to discuss the latest developments in this area, exchange ideas, and identify key research questions and challenges that need to be addressed. By hosting this workshop, we aim to create a forum for researchers to share their insights and expertise on multimodal data fusion and learning using foundation models, and to explore potential new research directions and applications in the rapidly evolving field. We expect contributions from interdisciplinary researchers to study and model interactions between (but not limited to) modalities of language, graphs, time-series, vision, tabular data, sensors, and more. Our workshop will emphasize interdisciplinary work and aim at seeding cross-team collaborations around new tasks, datasets, and models.
FLOOD: A Flexible Invariant Learning Framework for Out-of-Distribution Generalization on Graphs
Authors: Yang Liu 0200, Xiang Ao 0001, Fuli Feng, Yunshan Ma 0002, Kuan Li, Tat-Seng Chua, Qing He 0003
Venue: KDD
Year: 2023

Graph Neural Networks (GNNs) have achieved remarkable success in various domains but most of them are developed under the in-distribution assumption. Under out-of-distribution (OOD) settings, they suffer from the distribution shift between the training set and the test set and may not generalize well to the test distribution. Several methods have tried the invariance principle to improve the generalization of GNNs in OOD settings. However, in previous solutions, the graph encoder is immutable after the invariant learning and cannot be adapted to the target distribution flexibly. Confronting the distribution shift, a flexible encoder with refinement to the target distribution can generalize better on the test set than the stable invariant encoder. To remedy these weaknesses, we propose a Flexible invariant Learning framework for Out-Of-Distribution generalization on graphs (FLOOD), which comprises two key components, invariant learning and bootstrapped learning. The invariant learning component constructs multiple environments from graph data augmentation and learns invariant representation under risk extrapolation. Besides, the bootstrapped learning component is devised to be trained in a self-supervised way with a shared graph encoder with the invariant learning part. During the test phase, the shared encoder is flexible to be refined with the bootstrapped learning on the test set. Extensive experiments are conducted for both transductive and inductive node classification tasks. The results demonstrate that FLOOD consistently outperforms other graph OOD generalization methods and effectively improves the generalization ability.
QTIAH-GNN: Quantity and Topology Imbalance-aware Heterogeneous Graph Neural Network for Bankruptcy Prediction
Authors: Yucheng Liu, Zipeng Gao, Xiangyang Liu, Pengfei Luo, Yang Yang 0074, Hui Xiong 0001
Venue: KDD
Year: 2023

The timely prediction of bankruptcy is highly desirable to guarantee an upward spiral for overall societal well-being. By extracting multifaceted information from the business interaction networks, Graph Neural Networks (GNNs) may be able to automatically make more informed predictions for bankruptcy, as compared to methods that rely heavily on abundant manpower to a large extent. Yet in real applications, bankruptcy prediction faces the key issue of quantity-imbalance: data usually comes with a long-tailed distribution wherein bankrupt corporates occupy the least of the data proportion but are our target to be identified. Apart from that, the topology-imbalance issue behind graph-structural data exacerbates prediction deterioration: feature propagation is dominated by non-bankrupt nodes through messages passing between nodes; thus, bankrupt nodes receive highly confusing information and could be easily assimilated by nearby non-bankrupt nodes. Unfortunately, the existing GNN methods are not immune to these two imbalance issues. To tackle the challenging but practically useful scenario, we propose a novel bankruptcy prediction model called the Quantity and Topology Imbalance-Aware Heterogeneous Graph Neural Network (QTIAH-GNN) to boost the final performance. Specifically, QTIAH-GNN employs the multi-hierarchy label-aware neighbor selection to conquer the topology-imbalance issue by using the class-semantic representation and the learnable parameterized similarity metric, and employs the imbalance-oriented loss to obtain the optimal tradeoff between the accuracies of the majority and minority classes. In experiments, we evaluate the proposed QTIAH-GNN on two large-scale, real-world datasets. The results show that QTIAH-GNN outperforms other state-of-the-art baselines in terms of prediction accuracy with superior efficiency and generalization ability, has stronger robustness to data imbalance, and provides meaningful model interpretation.
Enhancing Graph Representations Learning with Decorrelated Propagation
Authors: Hua Liu 0008, Haoyu Han 0001, Wei Jin 0009, Xiaorui Liu, Hui Liu 0031
Venue: KDD
Year: 2023

In recent years, graph neural networks (GNNs) have been widely used in many domains due to their powerful capability in representation learning on graph-structured data. While a majority of extant studies focus on mitigating the over-smoothing problem, recent works also reveal the limitation of GNN from a new over-correlation perspective which states that the learned representation becomes highly correlated after feature transformation and propagation in GNNs. In this paper, we thoroughly re-examine the issue of over-correlation in deep GNNs, both empirically and theoretically. We demonstrate that the propagation operator in GNNs exacerbates the feature correlation. In addition, we discovered through empirical study that existing decorrelation solutions fall short of maintaining a low feature correlation, potentially encoding redundant information. Thus, to more effectively address the over-correlation problem, we propose a decorrelated propagation scheme (DeProp) as a fundamental component to decorrelate the feature learning in GNN models, which achieves feature decorrelation at the propagation step. Comprehensive experiments on multiple real-world datasets demonstrate that DeProp can be easily integrated into prevalent GNNs, leading to significant performance enhancements. Furthermore, we find that it can be used to solve over-smoothing and over-correlation problems simultaneously and significantly outperform state-of-the-art methods on missing feature settings. The code is available at https://github.com/hualiu829/DeProp.
Fairness-Aware Continuous Predictions of Multiple Analytics Targets in Dynamic Networks
Authors: Ruifeng Liu, Qu Liu, Tingjian Ge
Venue: KDD
Year: 2023

We study a novel problem of continuously predicting a number of user-subscribed continuous analytics targets (CATs) in dynamic networks. Our architecture includes any dynamic graph neural network model as the back end applied over the network data, and per CAT front end models that return results with their confidence to users. We devise a data filtering algorithm that feeds a provably optimal subset of data in the embedding space from back end model to front end models. Secondly, to ensure fairness in terms of query result accuracy for different CATs and users, we propose a fairness metric and a fairness-aware training scheduling algorithm, along with accuracy guarantees on fairness estimation. Our experiments over five real-world datasets show that our proposed solution is effective, efficient, fair, extensible, and adaptive.
B2-Sampling: Fusing Balanced and Biased Sampling for Graph Contrastive Learning
Authors: Mengyue Liu, Yun Lin 0001, Jun Liu 0002, Bohao Liu, Qinghua Zheng, Jin Song Dong 0001
Venue: KDD
Year: 2023

Graph contrastive learning (GCL), aiming for an embedding space where semantically similar nodes are closer, has been widely applied in graph-structured data. Researchers have proposed many approaches to define positive and negative pairs (i.e., semantically similar and dissimilar pairs) on the graph, serving as labels to learn their embedding distances. Despite the effectiveness, those approaches usually suffer from two typical learning challenges. First, the number of candidate negative pairs is enormous. Thus, it is non-trivial to select representative ones to train the model in a more effective way. Second, the heuristics (e.g., graph views or meta-path patterns) to define positive and negative pairs are sometimes less reliable, causing considerable noise for both "labelled'' positive and negative pairs. In this work, we propose a novel sampling approach B2-Sampling to address the above challenges in a unified way. On the one hand, we use balanced sampling to select the most representative negative pairs regarding both the topological and embedding diversities. On the other hand, we use biased sampling to learn and correct the labels of the most error-prone negative pairs during the training. The balanced and biased samplings can be applied iteratively for discriminating and correcting training pairs, boosting the performance of GCL models. B2-Sampling is designed as a framework to support many known GCL models. Our extensive experiments on node classification, node clustering, and graph classification tasks show that B2-Sampling significantly improves the performance of GCL models with acceptable runtime overhead. Our website[11] https://sites.google.com/view/b2-sampling/home provides access to our codes and additional experiment results.
Fire: An Optimization Approach for Fast Interpretable Rule Extraction
Authors: Brian Liu 0002, Rahul Mazumder
Venue: KDD
Year: 2023

We present FIRE, Fast Interpretable Rule Extraction, an optimization-based framework to extract a small but useful collection of decision rules from tree ensembles. FIRE selects sparse representative subsets of rules from tree ensembles, that are easy for a practitioner to examine. To further enhance the interpretability of the extracted model, FIRE encourages fusing rules during selection, so that many of the selected decision rules share common antecedents. The optimization framework utilizes a fusion regularization penalty to accomplish this, along with a non-convex sparsity-inducing penalty to aggressively select rules. Optimization problems in FIRE pose a challenge to off-the-shelf solvers due to problem scale and the non-convexity of the penalties. To address this, making use of problem-structure, we develop a specialized solver based on block coordinate descent principles; our solver performs up to 40x faster than existing solvers. We show in our experiments that FIRE outperforms state-of-the-art rule ensemble algorithms at building sparse rule sets, and can deliver more interpretable models compared to existing methods.
Stationary Algorithmic Balancing For Dynamic Email Re-Ranking Problem
Authors: Jiayi Liu 0005, Jennifer Neville
Venue: KDD
Year: 2023

Email platforms need to generate personalized rankings of emails that satisfy user preferences, which may vary over time. We approach this as a recommendation problem based on three criteria: closeness (how relevant the sender and topic are to the user), timeliness (how recent the email is), and conciseness (how brief the email is). We propose MOSR (Multi-Objective Stationary Recommender), a novel online algorithm that uses an adaptive control model to dynamically balance these criteria and adapt to preference changes. We evaluate MOSR on the Enron Email Dataset, a large collection of real emails, and compare it with other baselines. The results show that MOSR achieves better performance, especially under non-stationary preferences, where users value different criteria more or less over time. We also test MOSR's robustness on a smaller down-sampled dataset that exhibits high variance in email characteristics, and show that it maintains stable rankings across different samples. Our work offers novel insights into how to design email re-ranking systems that account for multiple objectives impacting user satisfaction.
Knowledge Graph Reasoning and Its Applications
Authors: Lihui Liu, Hanghang Tong
Venue: KDD
Year: 2023

The use of knowledge graphs has gained significant traction in a wide variety of applications, ranging from recommender systems and question answering to fact checking. By leveraging the wealth of information contained within knowledge graphs, it is possible to greatly enhance various downstream tasks, making reasoning over knowledge graphs an area of increasing interest. However, despite its popularity, knowledge graph reasoning remains a challenging problem. The first major challenge of knowledge graph reasoning lies in the nature of knowledge graphs themselves. Most knowledge graphs are incomplete, meaning that they may not capture all the relevant knowledge required for reasoning. As a result, reasoning on incomplete knowledge graphs can be difficult. Additionally, real-world knowledge graphs often evolve over time, which presents an additional challenge. The second challenge of knowledge graph reasoning pertains to the input data. In some KG reasoning applications, users may be unfamiliar with the background knowledge graph, leading to the possibility of asking ambiguous questions that can make KG reasoning tasks more challenging. Moreover, some applications require iterative reasoning, where users ask several related questions in sequence, further increasing the complexity of the task. The third challenge of knowledge graph reasoning concerns the algorithmic aspect. Due to the varied properties of relations in knowledge graphs, such as transitivity, symmetry, and asymmetry, designing an all-round KG reasoning model that fits all these properties can be challenging. Furthermore, most KG reasoning models tend to focus on solving a specific problem, lacking the generalization ability required to apply to other tasks. This tutorial aims to comprehensively review different aspects of knowledge graph reasoning applications and highlight open challenges and future directions. It is intended to benefit researchers and practitioners in the fields of data mining, artificial intelligence, and social science.
Practical Synthetic Human Trajectories Generation Based on Variational Point Processes
Authors: Qingyue Long, Huandong Wang, Tong Li 0013, Lisi Huang, Kun Wang, Qiong Wu, Guangyu Li, Yanping Liang, Li Yu, Yong Li 0008
Venue: KDD
Year: 2023

Human trajectories, reflecting people's travel patterns and the range of activities, are crucial for the applications like urban planning and epidemic control. However, the real-world human trajectory data tends to be limited by user privacy or device acquisition issues, leading to its insufficient quality to support the above applications. Hence, generating human trajectory data is a crucial but challenging task, which suffers from the following two critical challenges: 1) how to capture the user distribution in human trajectories (group view), and 2) how to model the complex mobility patterns of each user trajectory (individual view). In this paper, we propose a novel human trajectories generator (named VOLUNTEER), consisting of a user VAE and a trajectory VAE, to address the above challenges. Specifically, in the user VAE, we propose to learn the user distribution with all human trajectories from a group view. In the trajectory VAE, from the individual view, we model the complex mobility patterns by decoupling travel time and dwell time to accurately simulate individual trajectories. Extensive experiments on two real-world datasets show the superiority of our model over the state-of-the-art baselines. Further application analysis in the industrial system also demonstrates the effectiveness of our model.
Physics-Guided Discovery of Highly Nonlinear Parametric Partial Differential Equations
Authors: Yingtao Luo, Qiang Liu 0006, Yuntian Chen, Wenbo Hu 0001, Tian Tian 0001, Jun Zhu 0001
Venue: KDD
Year: 2023

Partial differential equations (PDEs) that fit scientific data can represent physical laws with explainable mechanisms for various mathematically-oriented subjects, such as physics and finance. The data-driven discovery of PDEs from scientific data thrives as a new attempt to model complex phenomena in nature, but the effectiveness of current practice is typically limited by the scarcity of data and the complexity of phenomena. Especially, the discovery of PDEs with highly nonlinear coefficients from low-quality data remains largely under-addressed. To deal with this challenge, we propose a novel physics-guided learning method, which can not only encode observation knowledge such as initial and boundary conditions but also incorporate the basic physical principles and laws to guide the model optimization. We theoretically show that our proposed method strictly reduces the coefficient estimation error of existing baselines, and is also robust against noise. Extensive experiments show that the proposed method is more robust against data noise, and can reduce the estimation error by a large margin. Moreover, all the PDEs in the experiments are correctly discovered, and for the first time we are able to discover three-dimensional PDEs with highly nonlinear coefficients.
A Look into Causal Effects under Entangled Treatment in Graphs: Investigating the Impact of Contact on MRSA Infection
Authors: Jing Ma 0002, Chen Chen 0022, Anil Vullikanti, Ritwick Mishra, Gregory Madden, Daniel Borrajo, Jundong Li
Venue: KDD
Year: 2023

Methicillin-resistant Staphylococcus aureus (MRSA) is a type of bacteria resistant to certain antibiotics, making it difficult to prevent MRSA infections. Among decades of efforts to conquer infectious diseases caused by MRSA, many studies have been proposed to estimate the causal effects of close contact (treatment) on MRSA infection (outcome) from observational data. In this problem, the treatment assignment mechanism plays a key role as it determines the patterns of missing counterfactuals --- the fundamental challenge of causal effect estimation. Most existing observational studies for causal effect learning assume that the treatment is assigned individually for each unit. However, on many occasions, the treatments are pairwisely assigned for units that are connected in graphs, i.e., the treatments of different units are entangled. Neglecting the entangled treatments can impede the causal effect estimation. In this paper, we study the problem of causal effect estimation with treatment entangled in a graph. Despite a few explorations for entangled treatments, this problem still remains challenging due to the following challenges: (1) the entanglement brings difficulties in modeling and leveraging the unknown treatment assignment mechanism; (2) there may exist hidden confounders which lead to confounding biases in causal effect estimation; (3) the observational data is often time-varying. To tackle these challenges, we propose a novel method NEAT, which explicitly leverages the graph structure to model the treatment assignment mechanism, and mitigates confounding biases based on the treatment assignment modeling. We also extend our method into a dynamic setting to handle time-varying observational data. Experiments on both synthetic datasets and a real-world MRSA dataset validate the effectiveness of the proposed method, and provide insights for future applications.
SAInf: Stay Area Inference of Vehicles using Surveillance Camera Records
Authors: Zhipeng Ma, Chuishi Meng, Huimin Ren, Sijie Ruan, Jie Bao 0003, Xiaoting Wang, Tianrui Li 0001, Yu Zheng 0004
Venue: KDD
Year: 2023

Stay area detection is one of the most important applications in trajectory data mining, which is helpful to understand human's behavior intentions. Traditional stay area detection methods are based on GPS data with relatively high sampling rate. However, because of privacy issues, accessing GPS data can be difficult in most real-world applications. Fortunately, traffic surveillance cameras have been widely deployed in urban area, and it provides us a novel way of acquiring vehicles' trajectories. All the vehicles that traverse by can be recognized and recorded in a passive way. However, the trajectory data collected in this way is extremely coarse, because the surveillance cameras are only deployed in important locations, such as crossroads. This coarse trajectory introduces two challenges for the stay area detection problem, i.e., whether and where the stay event occurs. In this paper, we design a two-stage method to solve the stay area detection problem with coarse trajectories. It first detects the stay event between a surveillance camera record pair, then uses a layer-by-layer stay area identification algorithm to infer the exact stay area. Extensive experiments based on real-world data were used to evaluate the performance of the proposed framework. Results demonstrate the proposed framework SAInf achieved a 58% performance improvement compared with SOTA methods.