OpenRaiser/Intern-Atlas huggingface dataset:
Causal Attention for Interpretable and Generalizable Graph Classification
Authors: Yongduo Sui, Xiang Wang 0010, Jiancan Wu, Min Lin, Xiangnan He 0001, Tat-Seng Chua
Venue: KDD
Year: 2022

In graph classification, attention- and pooling-based graph neural networks (GNNs) prevail to extract the critical features from the input graph and support the prediction. They mostly follow the paradigm of learning to attend, which maximizes the mutual information between the attended graph and the ground-truth label. However, this paradigm makes GNN classifiers recklessly absorb all the statistical correlations between input features and labels in the training data, without distinguishing the causal and noncausal effects of features. Instead of underscoring the causal features, the attended graphs are prone to visit the noncausal features as the shortcut to predictions. Such shortcut features might easily change outside the training distribution, thereby making the GNN classifiers suffer from poor generalization.
Optimizing Long-Term Efficiency and Fairness in Ride-Hailing via Joint Order Dispatching and Driver Repositioning
Authors: Jiahui Sun, Haiming Jin, Zhaoxing Yang, Lu Su 0001, Xinbing Wang
Venue: KDD
Year: 2022

The ride-hailing service offered by mobility-on-demand platforms, such as Uber and Didi Chuxing, has greatly facilitated people's traveling and commuting, and become increasingly popular in recent years. Efficiency (e.g., gross merchandise volume) has always been an important metric for such platforms. However, only focusing on the efficiency inevitably ignores the fairness of driver incomes, which could impair the sustainability of the overall ride-hailing system in the long run. To optimize the aforementioned two essential metrics, order dispatching and driver repositioning play an important role, as they impact not only the immediate, but also the future order-serving outcomes of drivers. Thus, in this paper, we aim to exploit joint order dispatching and driver repositioning to optimize both the long-term efficiency and fairness for ride-hailing platforms. To address this problem, we propose a novel multi-agent reinforcement learning framework, referred to as JDRL, to help drivers make distributed order selection and repositioning decisions. Specifically, to cope with the variable action space, JDRL segments the action space into a fixed number of action groups, and fixes the policy output dimension for order selection as the number of action groups. In terms of the fairness criterion, JDRL adopts the max-min fairness, and augments the vanilla policy gradient to an iterative training algorithm that alternates between a minimization step and a policy improvement step to maximize both the worst and the overall performance of agents. In addition, we provide the theoretical convergence guarantee of our JDRL training algorithm even under non-convex policy networks and stochastic gradient updating. Extensive experiments are conducted with three public real-world ride-hailing order datasets, including over 2 million orders in Haikou, China, over 5 million orders in Chengdu, China, and over 6 million orders in New York City, USA. Experimental results show that JDRL demonstrates a consistent advantage compared to state-of-the-art baselines in terms of both efficiency and fairness. To the best of our knowledge, this is the first work that exploits joint order dispatching and driver repositioning to optimize both the long-term efficiency and fairness in a ride-hailing system.
GPPT: Graph Pre-training and Prompt Tuning to Generalize Graph Neural Networks
Authors: Mingchen Sun, Kaixiong Zhou, Xin He 0003, Ying Wang 0009, Xin Wang 0035
Venue: KDD
Year: 2022

Despite the promising representation learning of graph neural networks (GNNs), the supervised training of GNNs notoriously requires large amounts of labeled data from each application. An effective solution is to apply the transfer learning in graph: using easily accessible information to pre-train GNNs, and fine-tuning them to optimize the downstream task with only a few labels. Recently, many efforts have been paid to design the self-supervised pretext tasks, and encode the universal graph knowledge among the various applications. However, they rarely notice the inherent training objective gap between the pretext and downstream tasks. This significant gap often requires costly fine-tuning for adapting the pre-trained model to downstream problem, which prevents the efficient elicitation of pre-trained knowledge and then results in poor results. Even worse, the naive pre-training strategy usually deteriorates the downstream task, and damages the reliability of transfer learning in graph data. To bridge the task gap, we propose a novel transfer learning paradigm to generalize GNNs, namely graph pre-training and prompt tuning (GPPT). Specifically, we first adopt the masked edge prediction, the most simplest and popular pretext task, to pre-train GNNs. Based on the pre-trained model, we propose the graph prompting function to modify the standalone node into a token pair, and reformulate the downstream node classification looking the same as edge prediction. The token pair is consisted of candidate label class and node entity. Therefore, the pre-trained GNNs could be applied without tedious fine-tuning to evaluate the linking probability of token pair, and produce the node classification decision. The extensive experiments on eight benchmark datasets demonstrate the superiority of GPPT, delivering an average improvement of 4.29% in few-shot graph analysis and accelerating the model convergence up to 4.32X. The code is available in: https://github.com/MingChen-Sun/GPPT.
Learning Optimal Priors for Task-Invariant Representations in Variational Autoencoders
Authors: Hiroshi Takahashi, Tomoharu Iwata, Atsutoshi Kumagai, Sekitoshi Kanai, Masanori Yamada, Yuki Yamanaka, Hisashi Kashima
Venue: KDD
Year: 2022

The variational autoencoder (VAE) is a powerful latent variable model for unsupervised representation learning. However, it does not work well in case of insufficient data points. To improve the performance in such situations, the conditional VAE (CVAE) is widely used, which aims to share task-invariant knowledge with multiple tasks through the task-invariant latent variable. In the CVAE, the posterior of the latent variable given the data point and task is regularized by the task-invariant prior, which is modeled by the standard Gaussian distribution. Although this regularization encourages independence between the latent variable and task, the latent variable remains dependent on the task. To reduce this task-dependency, the previous work introduced an additional regularizer. However, its learned representation does not work well on the target tasks. In this study, we theoretically investigate why the CVAE cannot sufficiently reduce the task-dependency and show that the simple standard Gaussian prior is one of the causes. Based on this, we propose a theoretical optimal prior for reducing the task-dependency. In addition, we theoretically show that unlike the previous work, our learned representation works well on the target tasks. Experiments on various datasets show that our approach obtains better task-invariant representations, which improves the performances of various downstream applications such as density estimation and classification.
CognitionNet: A Collaborative Neural Network for Play Style Discovery in Online Skill Gaming Platform
Authors: Rukma Talwadker, Surajit Chakrabarty, Aditya Pareek, Tridib Mukherjee, Deepak Saini
Venue: KDD
Year: 2022

Games are one of the safest source of realizing self-esteem and relaxation at the same time. An online gaming platform typically has massive data coming in, e.g., in-game actions, player moves, clickstreams, transactions etc. It is rather interesting, as something as simple as data on gaming moves can help create a psychological imprint of the user at that moment, based on her impulsive reactions and response to a situation in the game. Mining this knowledge can: (a) immediately help better explain observed and predicted player behavior; and (b) consequently propel deeper understanding towards players' experience, growth and protection.
Beyond Traditional Characterizations in the Age of Data: Big Models, Scalable Algorithms, and Meaningful Solutions
Authors: Shang-Hua Teng
Venue: KDD
Year: 2022

What are data and network models? What are efficient algorithms? What are meaningful solutions? Big Data, Network Sciences, and Machine Learning have fundamentally challenged the basic characterizations in computing, from the conventional graph-theoretical modeling of networks to the traditional polynomial-time worst-case measures of efficiency:
Clustering with Fair-Center Representation: Parameterized Approximation Algorithms and Heuristics
Authors: Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, Michal Osadnik
Venue: KDD
Year: 2022

We study a variant of classical clustering formulations in the context of algorithmic fairness, known as diversity-aware clustering. In this variant we are given a collection of facility subsets, and a solution must contain at least a specified number of facilities from each subset while simultaneously minimizing the clustering objective (k-median or k-means). We investigate the fixed-parameter tractability of these problems and show several negative hardness and inapproximability results, even when we afford exponential running time with respect to some parameters.
Incremental Cognitive Diagnosis for Intelligent Education
Authors: Shiwei Tong, Jiayu Liu 0001, Yuting Hong, Zhenya Huang, Le Wu, Qi Liu 0003, Wei Huang 0002, Enhong Chen, Dan Zhang
Venue: KDD
Year: 2022

Cognitive diagnosis, aiming at providing an approach to reveal the proficiency level of learners on knowledge concepts, plays an important role in intelligent education area and has recently received more and more attention. Although a number of works have been proposed in recent years, most of contemporary works acquire the traits parameters of learners and items in a transductive way, which are only suitable for stationary data. However, in the real scenario, the data is collected online, where learners, test items and interactions usually grow continuously, which can rarely meet the stationary condition. To this end, we propose a novel framework, Incremental Cognitive Diagnosis (ICD), to tailor cognitive diagnosis into the online scenario of intelligent education. Specifically, we first design a Deep Trait Network (DTN), which acquires the trait parameters in an inductive way rather than a transductive way. Then, we propose an Incremental Update Algorithm (IUA) to balance the effectiveness and training efficiency. We carry out Turning Point (TP) analysis to reduce update frequency, where we derive the minimum update condition based on the monotonicity theory of cognitive diagnosis. Meanwhile, we use a momentum update strategy on the incremental data to decrease update time without sacrificing effectiveness. Moreover, to keep the trait parameters as stable as possible, we refine the loss function in the incremental updating stage. Last but no least, our ICD is a general framework which can be applied to most of contemporary cognitive diagnosis models. To the best of our knowledge, this is the first attempt to investigate the incremental cognitive diagnosis problem with theoretical results about the update condition and a tailored incremental learning strategy. Extensive experiments demonstrate the effectiveness and robustness of our method.
Aligning Dual Disentangled User Representations from Ratings and Textual Content
Authors: Nhu-Thuat Tran, Hady W. Lauw
Venue: KDD
Year: 2022

Classical recommendation methods typically render user representation as a single vector in latent space. Oftentimes, a user's interactions with items are influenced by several hidden factors. To better uncover these hidden factors, we seek disentangled representations. Existing disentanglement methods for recommendations are mainly concerned with user-item interactions alone. To further improve not only the effectiveness of recommendations but also the interpretability of the representations, we propose to learn a second set of disentangled user representations from textual content and to align the two sets of representations with one another. The purpose of this coupling is two-fold. For one benefit, we leverage textual content to resolve sparsity of user-item interactions, leading to higher recommendation accuracy. For another benefit, by regularizing factors learned from user-item interactions with factors learned from textual content, we map uninterpretable dimensions from user representation into words. An attention-based alignment is introduced to align and enrich hidden factors representations. A series of experiments conducted on four real-world datasets show the efficacy of our methods in improving recommendation quality.
Dense Feature Tracking of Atmospheric Winds with Deep Optical Flow
Authors: Thomas J. Vandal, Kate Duffy, Will McCarty, Akira Sewnath, Ramakrishna R. Nemani
Venue: KDD
Year: 2022

Atmospheric winds are a key physical phenomenon impacting natural hazards, energy transport, ocean currents, large-scale circulation, and ecosystem fluxes. Observing winds is a complex process and presents a large gap in NASA's Earth Observation System. Atmospheric motion vectors (AMVs) aim to fill this gap by making numerical estimates of cloud movement between sequences of multi-spectral satellite images, tracking clouds and water vapor. Recent imaging hardware and software advancements have enabled the use of numerical optical flow techniques to produce accurate and dense vector fields outperforming traditional methods. This work presents WindFlow as the first machine learning based system for feature tracking atmospheric motion using optical flow. Due to the lack of large-scale satellite-based observations, we leverage high-resolution numerical simulations from NASA's GEOS-5 Nature Run to perform supervised learning and transfer to satellite images. We demonstrate that our approach using deep learning based optical flow scales to ultra-high-resolution images of size 2881x5760 with less than 1 m/s bias and 2.5 m/s average error. Four network and learning architectures are compared and it is found that recurrent all-pairs field transforms (RAFT) produces the lowest errors on all metrics for wind speed and direction. Results on held out numerical outputs show RAFT's good performance in each of the spatial, temporal, and physical dimensions. A comparison between WindFlow and an operational AMV product against rawinsonde observations shows that RAFT transfers across simulations and thermal infrared satellite observations. This work shows that machine learning based optical flow is an efficient approach to generating robust feature tracking for AMVs consistently over large regions.
Invariant Preference Learning for General Debiasing in Recommendation
Authors: Zimu Wang, Yue He 0001, Jiashuo Liu, Wenchao Zou, Philip S. Yu, Peng Cui 0001
Venue: KDD
Year: 2022

Current recommender systems have achieved great successes in online services, such as E-commerce and social media. However, they still suffer from the performance degradation in real scenarios, because various biases always occur in the generation process of user behaviors. Despite the recent development of addressing some specific type of bias, a variety of data bias, some of which are even unknown, are often mixed up in real applications. Although the uniform (or unbiased) data may help for the purpose of general debiasing, such data can either be hardly available or induce high experimental cost. In this paper, we consider a more practical setting where we aim to conduct general debiasing with the biased observational data alone. We assume that the observational user behaviors are determined by invariant preference (i.e. a user's true preference) and the variant preference (affected by some unobserved confounders). We propose a novel recommendation framework called InvPref which iteratively decomposes the invariant preference and variant preference from biased observational user behaviors by estimating heterogeneous environments corresponding to different types of latent bias. Extensive experiments, including the settings of general debiasing and specific debiasing, verify the advantages of our method.
Representative Routes Discovery from Massive Trajectories
Authors: Tingting Wang 0009, Shixun Huang, Zhifeng Bao, J. Shane Culpepper, Reza Arablouei
Venue: KDD
Year: 2022

In this work, we study how to find the k most representative routes over large scale trajectory data, which is a fundamental operation that benefits various real-world applications, such as traffic monitoring and public transportation planning. The operator is time-sensitive as it must be able to adapt the results as traffic conditions change. We first prove the NP-hardness of the problem, and then propose a range of effective approximate solutions that have rapid response times. Specifically, we first build a lookup table that stores the trajectories covered by each edge in a given road network. Rather than performing a depth-first search for all possible routes, we find a 1/η approximate solution by developing a maximum-weight algorithm. Since each edge in a route may be close to several trajectories, we further propose a coverage-first algorithm to locate the edges with the greatest coverage gain in the solution route set. By observing that in the real world each edge is connected to only a few other edges in a road network, we have developed a connect-first algorithm that finds consecutive edges for k representative routes by greedily selecting edges with the maximum marginal gain for each route. Finally, comprehensive experiments over two real-world datasets are conducted to verify the effectiveness and efficiency of our proposed algorithms, and provide evidence of the usefulness of our solution and rapid response times in traffic monitoring tasks.
Graph Neural Networks in Life Sciences: Opportunities and Solutions
Authors: Zichen Wang 0002, Vassilis N. Ioannidis, Huzefa Rangwala, Tatsuya Arai, Ryan Brand, Mufei Li, Yohei Nakayama
Venue: KDD
Year: 2022

Graphs (or networks) are ubiquitous representation in life sciences and medicine, from molecular interactions maps, signaling transduction pathways, to graphs of scientific knowledge and patient- disease-intervention relationships derived from population studies and/or real-world data, such as electronic health records and insurance claims. Recent advance in graph machine learning (ML) approaches such as graph neural networks (GNNs) has transformed a diverse set of problems relying on biomedical networks that traditionally depend on descriptive topological data analyses. Small- and macro- molecules that were not modeled as graphs also saw a bloom in GNN-based algorithms improving the state-of-the-art performance for learning their properties. Comparing to graph ML applications from other domains, life sciences offer many unique problems and nuances ranging from graph construction to graph- level, and bi-graph-level supervision tasks.
Data Science and Artificial Intelligence for Responsible Recommendations
Authors: Shoujin Wang, Ninghao Liu 0001, Xiuzhen Zhang 0001, Yan Wang 0002, Francesco Ricci 0001, Bamshad Mobasher
Venue: KDD
Year: 2022

With the advancement of data science and AI, more and more powerful and accurate recommender systems (RSs) have been developed. They provide recommendation services in various areas, including shopping, eating, travelling and entertainment. RSs have achieved a great success and benefted the society. However, most of the research on RS has focused on the improvement of the recommendation accuracy, while ignoring other important qualities, such as trustworthiness (robustness, fairness, explainability, privacy and security) and social impact (influence on users' recognition and behaviours) of the recommendations. These are important aspects and cannot be overlooked since they measure properties that determine whether the recommendation service is reliable, trustworthy and benefcial to individual users and society. In this work, responsible recommendations refer to trustworthy recommendation techniques and positive-social-impact recommendation results.
A Model-Agnostic Approach to Differentially Private Topic Mining
Authors: Han Wang 0021, Jayashree Sharma, Shuya Feng, Kai Shu, Yuan Hong 0001
Venue: KDD
Year: 2022

Topic mining extracts patterns and insights from text data (e.g., documents, emails and product reviews), which can be used in various applications such as intent detection. However, topic mining can result in severe privacy threats to the users who have contributed to the text corpus since they can be re-identified from the text data with certain background knowledge. To our best knowledge, we propose the first differentially private topic mining technique (namely TopicDP) which injects well-calibrated Gaussian noise into the matrix output of any topic mining algorithm to ensure differential privacy and good utility. Specifically, we smoothen the sensitivity for the Gaussian mechanism via sensitivity sampling, which addresses the major challenges resulted from the high sensitivity in topic mining for differential privacy. Furthermore, we theoretically prove the differential privacy guarantee under the Rényi differential privacy mechanism and the utility error bounds of TopicDP. Finally, we conduct extensive experiments on two real-word text datasets (Enron email and Amazon Reviews), and the experimental results demonstrate that TopicDP is a model-agnostic framework that can generate better privacy preserving performance for topic mining as compared against other differential privacy mechanisms.
Graph Neural Networks with Node-wise Architecture
Authors: Zhen Wang 0036, Zhewei Wei, Yaliang Li, Weirui Kuang, Bolin Ding
Venue: KDD
Year: 2022

Recently, Neural Architecture Search (NAS) for GNN has received increasing popularity as it can seek an optimal architecture for a given new graph. However, the optimal architecture is applied to all the instances (i.e., nodes, in the context of graph) equally, which might be insufficient to handle the diverse local patterns ingrained in a graph, as shown in this paper and some very recent studies. Thus, we argue the necessity of node-wise architecture search for GNN. Nevertheless, node-wise architecture cannot be realized by trivially applying NAS methods node by node due to the scalability issue and the need for determining test nodes' architectures. To tackle these challenges, we propose a framework wherein the parametric controllers decide the GNN architecture for each node based on its local patterns. We instantiate our framework with depth, aggregator and resolution controllers, and then elaborate on learning the backbone GNN model and the controllers to encourage their cooperation. Empirically, we justify the effects of node-wise architecture through the performance improvements introduced by the three controllers, respectively. Moreover, our proposed framework significantly outperforms state-of-the-art methods on five of the ten real-world datasets, where the diversity of these datasets has hindered any graph convolution-based method to lead on them simultaneously. This result further confirms that node-wise architecture can help GNNs become versatile models.