OpenRaiser/Intern-Atlas huggingface dataset:
A Graph Learning Based Framework for Billion-Scale Offline User Identification
Authors: Daixin Wang, Zujian Weng, Zhengwei Wu, Zhiqiang Zhang 0012, Peng Cui 0001, Hongwei Zhao, Jun Zhou 0011
Venue: KDD
Year: 2022

Offline user identification is a scenario that users use their bio-information like faces as identification in offline venues, which has been applied in many offline scenarios such as verification in banks, check-in in hotels and making a purchase in offline merchants. In such a scenario, designing an identification approach to do extremely accurate offline user identification is critical. Most scenarios use faces to identify users and previous algorithms are mainly based on visual features and computer-vision models. However, due to the large variations such as pose, illumination and occlusions in offline scenarios, it remains a challenging problem for existing computer-vision algorithms to get a satisfying accuracy in real-world scenarios. Furthermore, billion-scale candidate users also require high efficiency and high accuracy for the approach.
Towards Representation Alignment and Uniformity in Collaborative Filtering
Authors: Chenyang Wang 0003, Yuanqing Yu, Weizhi Ma, Min Zhang 0006, Chong Chen 0001, Yiqun Liu 0001, Shaoping Ma
Venue: KDD
Year: 2022

Collaborative filtering (CF) plays a critical role in the development of recommender systems. Most CF methods utilize an encoder to embed users and items into the same representation space, and the Bayesian personalized ranking (BPR) loss is usually adopted as the objective function to learn informative encoders. Existing studies mainly focus on designing more powerful encoders (e.g., graph neural network) to learn better representations. However, few efforts have been devoted to investigating the desired properties of representations in CF, which is important to understand the rationale of existing CF methods and design new learning objectives. In this paper, we measure the representation quality in CF from the perspective of alignment and uniformity on the hypersphere. We first theoretically reveal the connection between the BPR loss and these two properties. Then, we empirically analyze the learning dynamics of typical CF methods in terms of quantified alignment and uniformity, which shows that better alignment or uniformity both contribute to higher recommendation performance. Based on the analyses results, a learning objective that directly optimizes these two properties is proposed, named DirectAU. We conduct extensive experiments on three public datasets, and the proposed learning framework with a simple matrix factorization model leads to significant performance improvements compared to state-of-the-art CF methods.
Learning to Discover Causes of Traffic Congestion with Limited Labeled Data
Authors: Mudan Wang, Huan Yan 0003, Hongjie Sui, Fan Zuo, Yue Liu 0020, Yong Li 0008
Venue: KDD
Year: 2022

Traffic congestion incurs long delay in travel time, which seriously affects our daily travel experiences. Exploring why traffic congestion occurs is significantly important to effectively address the problem of traffic congestion and improve user experience. Traditional approaches to mine the congestion causes depend on human efforts, which is time consuming and cost-intensive. Hence, we aim to discover the known and unknown causes of traffic congestion in a systematic way. However, to achieve it, there are three challenges: 1) traffic congestion is affected by several factors with complex spatio-temporal relations; 2) the amount of congestion data with known causes is small due to the limitation of human label; 3) more unknown congestion causes are unexplored since several factors contribute to traffic congestion. To address above challenges, we design a congestion cause discovery system consisting of two modules: 1) congestion feature extraction, which extracts the important features influencing congestion; and 2) congestion cause discovery, which utilize a deep semi-supervised learning based method to discover the causes of traffic congestion with limited labeled causes. Specifically, it first leverages a few labeled data as prior knowledge to pre-train the model. Then, the k-means algorithm is performed to produce the clusters. Extensive experiments show that the performance of our proposed method is superior to the baselines. Additionally, our system is deployed and used in the practical production environment at Amap.
Partial Label Learning with Discrimination Augmentation
Authors: Wei Wang 0373, Min-Ling Zhang
Venue: KDD
Year: 2022

Partial label learning is a weakly supervised learning framework where each training example is associated with multiple candidate labels, among which only one is valid. Existing works on partial label learning mainly focus on classification model induction by disambiguating candidate label sets in the output space. Nevertheless, the feature representations of partial label training examples may be less informative of the ground-truth labels, which may result in negative influences on the disambiguation process. To circumvent this difficulty, the first attempt towards discrimination augmentation for partial label learning is investigated in this paper. The feature space is enriched with confidence-rated class prototype features to replenish discriminative characteristics of the underlying ground-truth labels for partial label training examples. Specially, an optimization formulation is proposed to jointly optimize the class prototype and estimate the labeling confidence over partial label training examples, which enforces both global consistency in the feature space and local consistency in the label space. We show that the class prototypes and the labeling confidence can be solved via alternating optimization. Extensive experiments on synthetic as well as real-world data sets validate the effectiveness of the proposed approach for improving the generalization performance of state-of-the-art partial label learning algorithms.
NENYA: Cascade Reinforcement Learning for Cost-Aware Failure Mitigation at Microsoft 365
Authors: Lu Wang 0029, Pu Zhao 0004, Chao Du, Chuan Luo 0002, Mengna Su, Fangkai Yang, Yudong Liu, Qingwei Lin, Min Wang, Yingnong Dang, Hongyu Zhang 0002, Saravan Rajmohan, Dongmei Zhang 0001
Venue: KDD
Year: 2022

Large-scale distributed systems, such as Microsoft 365's database system, require timely mitigation solutions to address failures and improve service availability and reliability. Still, mitigation actions can be costly as they may cause temporal performance degradation and even incur monetary expenses. Mitigation actions can be either administrated in a reactive fashion to contain detected failures or a proactive fashion to reduce potential failures. The proactive mitigation approach typically relies on a two-stage strategy: the prediction model will firstly identify instances (such as databases or disks) with high failure risk, then appropriate mitigation actions chosen by engineers or an automatic bandit learning model can be applied. As information is not fully shared across those two stages, important factors such as mitigation costs and states of instances are often ignored in one of those two stages. To address these issues, we propose NENYA, an end-to-end mitigation solution for a large-scale database system powered by a novel cascade reinforcement learning model. By taking the states of databases as input, NENYA directly outputs mitigation actions and is optimized based on jointly cumulative feedback on mitigation costs and failure rates. As the overwhelming majority of databases do not require mitigation actions, NENYA utilizes a novel cascade decision structure to firstly reliably filter out such databases and then focus on choosing appropriate mitigation actions for the rest. Extensive offline and online experiments have shown that our methods can outperform existing practices in reducing both failure rates of databases and mitigation costs. NENYA has been integrated into Microsoft 365, a productive platform, with sounding success.
Streaming Graph Neural Networks with Generative Replay
Authors: Junshan Wang, Wenhao Zhu, Guojie Song, Liang Wang 0001
Venue: KDD
Year: 2022

Training Graph Neural Networks (GNNs) incrementally is a particularly urgent problem, because real-world graph data usually arrives in a streaming fashion, and inefficiently updating of the models results in out-of-date embeddings, thus degrade its performance in downstream tasks. Traditional incremental learning methods will gradually forget old knowledge when learning new patterns, which is the catastrophic forgetting problem. Although saving and revisiting historical graph data alleviates the problem, the storage limitation in real-world applications reduces the amount of saved data, causing GNN to forget other knowledge. In this paper, we propose a streaming GNN based on generative replay, which can incrementally learn new patterns while maintaining existing knowledge without accessing historical data. Specifically, our model consists of the main model (GNN) and an auxiliary generative model. The generative model based on random walks with restart can learn and generate fake historical samples (i.e., nodes and their neighborhoods), which can be trained with real data to avoid the forgetting problem. Besides, we also design an incremental update algorithm for the generative model to maintain the graph distribution and for GNN to capture the current patterns. Our model is evaluated on different streaming data sets. The node classification results prove that our model can update the model efficiently and achieve comparable performance to model retraining. Code is available at https://github.com/Junshan-Wang/SGNN-GR.
Connecting the Hosts: Street-Level IP Geolocation with Graph Neural Networks
Authors: Zhiyuan Wang 0006, Fan Zhou 0002, Wenxuan Zeng, Goce Trajcevski, Chunjing Xiao, Yong Wang 0046, Kai Chen 0005
Venue: KDD
Year: 2022

Pinpointing the geographic location of an IP address is important for a range of location-aware applications spanning from targeted advertising to fraud prevention. The majority of traditional measurement-based and recent learning-based methods either focus on the efficient employment of topology or utilize data mining to find clues of the target IP in publicly available sources. Motivated by the limitations in existing works, we propose a novel framework named GraphGeo, which provides a complete processing methodology for street-level IP geolocation with the application of graph neural networks. It incorporates IP hosts knowledge and kinds of neighborhood relationships into the graph to infer spatial topology for high-quality geolocation prediction. We explicitly consider and alleviate the negative impact of uncertainty caused by network jitter and congestion, which are pervasive in complicated network environments. Extensive evaluations across three large-scale real-world datasets demonstrate that GraphGeo significantly reduces the geolocation errors compared to the state-of-the-art methods. Moreover, the proposed framework has been deployed on the web platform as an online service for 6 months.
SagDRE: Sequence-Aware Graph-Based Document-Level Relation Extraction with Adaptive Margin Loss
Authors: Ying Wei, Qi Li 0012
Venue: KDD
Year: 2022

Relation extraction (RE) is an important task for many natural language processing applications. Document-level relation extraction task aims to extract the relations within a document and poses many challenges to the RE tasks as it requires reasoning across sentences and handling multiple relations expressed in the same document. Existing state-of-the-art document-level RE models use the graph structure to better connect long-distance correlations. In this work, we propose SagDRE model, which further considers and captures the original sequential information from the text. The proposed model learns sentence-level directional edges to capture the information flow in the document and uses the token-level sequential information to encode the shortest paths from one entity to the other. In addition, we propose an adaptive margin loss to address the long-tailed multi-label problem of document-level RE tasks, where multiple relations can be expressed in a document for an entity pair and there are a few popular relations. The loss function aims to encourage separations between positive and negative classes. The experimental results on datasets from various domains demonstrate the effectiveness of the proposed methods.
Graph2Route: A Dynamic Spatial-Temporal Graph Neural Network for Pick-up and Delivery Route Prediction
Authors: Haomin Wen, Youfang Lin, Xiaowei Mao, Fan Wu, Yiji Zhao, Haochen Wang, Jianbin Zheng 0003, Lixia Wu, Haoyuan Hu, Huaiyu Wan
Venue: KDD
Year: 2022

Pick-up and delivery (P&D) services such as food delivery have achieved explosive growth in recent years by providing customers with daily-life convenience. Though many service providers have invested considerably in routing tools, more and more practitioners realize that significant deviations exist between workers' actual routes and planned ones. So it is not wise to feed "optimal routes" as workers' actual service routes into downstream tasks (e.g., arrival-time prediction and order dispatching), whose performances count on the accuracy of route prediction, i.e., to predict the future service route of a worker's unfinished tasks. Therefore, to meet the rising calling for route prediction models that can capture workers' future routing behaviors, in this paper, we formulate the Pick-up and Delivery Route Prediction task (PDRP task for short) from the graph perspective for the first time, then propose a dynamic spatial-temporal graph-based model, named Graph2Route. Unlike previous sequence-based models, our model leverages the underlying graph structure and features into the encoding and decoding process. Moreover, the dynamic graph-based nature can spontaneously describe the evolving relationship between different problem instances. As a result, abundant decision context information and various spatial-temporal information of node/edge can be fully utilized in Graph2Route to improve the prediction performance. Offline experiments over two real-world industry-scale datasets under different P&D services (i.e., food delivery and package pick-up) and online A/B test demonstrate the superiority of our proposed model.
Robust Time Series Analysis and Applications: An Industrial Perspective
Authors: Qingsong Wen, Linxiao Yang, Tian Zhou 0004, Liang Sun 0001
Venue: KDD
Year: 2022

Time series analysis is ubiquitous and important in various areas, such as Artificial Intelligence for IT Operations (AIOps) in cloud computing, AI-powered Business Intelligence (BI) in E-commerce, Artificial Intelligence of Things (AIoT), etc. In real-world scenarios, time series data often exhibit complex patterns with trend, seasonality, outlier, and noise. In addition, as more time series data are collected and stored, how to handle the huge amount of data efficiently is crucial in many applications. We note that these significant challenges exist in various tasks like forecasting, anomaly detection, and fault cause localization. Therefore, how to design effective and efficient time series models for different tasks, which are robust to address the aforementioned challenging patterns and noise in real-world scenarios, is of great theoretical and practical interests. In this tutorial, we provide a comprehensive and organized tutorial on the state-of-the-art algorithms of robust time series analysis, ranging from traditional statistical methods to the most recent deep learning based methods. We will not only introduce the principle of time series algorithms, but also provide insights into how to apply them effectively in practical real-world industrial applications. Specifically, we organize the tutorial in a bottom-up framework. We first present preliminaries from different disciplines including robust statistics, signal processing, optimization, and deep learning. Then, we identify and discuss those most-frequently processing blocks in robust time series analysis, including periodicity detection, trend filtering, seasonal-trend decomposition, and time series similarity. Lastly, we discuss recent advances in multiple time series tasks including forecasting, anomaly detection, fault cause localization, and autoscaling, as well as practical lessons of large-scale time series applications from an industrial perspective.
Beyond Point Prediction: Capturing Zero-Inflated & Heavy-Tailed Spatiotemporal Data with Deep Extreme Mixture Models
Authors: Tyler Wilson, Andrew McDonald 0003, Asadullah Hill Galib, Pang-Ning Tan, Lifeng Luo
Venue: KDD
Year: 2022

Zero-inflated, heavy-tailed spatiotemporal data is common across science and engineering, from climate science to meteorology and seismology. A central modeling objective in such settings is to forecast the intensity, frequency, and timing of extreme and non-extreme events; yet in the context of deep learning, this objective presents several key challenges. First, a deep learning framework applied to such data must unify a mixture of distributions characterizing the zero events, moderate events, and extreme events. Second, the framework must be capable of enforcing parameter constraints across each component of the mixture distribution. Finally, the framework must be flexible enough to accommodate for any changes in the threshold used to define an extreme event after training. To address these challenges, we propose Deep Extreme Mixture Model (DEMM), fusing a deep learning-based hurdle model with extreme value theory to enable point and distribution prediction of zero-inflated, heavy-tailed spatiotemporal variables. The framework enables users to dynamically set a threshold for defining extreme events at inference-time without the need for retraining. We present an extensive experimental analysis applying DEMM to precipitation forecasting, and observe significant improvements in point and distribution prediction. All code is available at https://github.com/andrewmcdonald27/DeepExtremeMixtureModel.
Graph Neural Networks: Foundation, Frontiers and Applications
Authors: Lingfei Wu 0001, Peng Cui 0001, Jian Pei 0001, Liang Zhao 0002, Xiaojie Guo 0002
Venue: KDD
Year: 2022

The field of graph neural networks (GNNs) has seen rapid and incredible strides over the recent years. Graph neural networks, also known as deep learning on graphs, graph representation learning, or geometric deep learning, have become one of the fastest-growing research topics in machine learning, especially deep learning. This wave of research at the intersection of graph theory and deep learning has also influenced other fields of science, including recommendation systems, computer vision, natural language processing, inductive logic programming, program synthesis, software mining, automated planning, cybersecurity, and intelligent transportation. However, as the field rapidly grows, it has been extremely challenging to gain a global perspective of the developments of GNNs. Therefore, we feel the urgency to bridge the above gap and have a comprehensive tutorial on this fast-growing yet challenging topic. This tutorial of Graph Neural Networks (GNNs): Foundation, Frontiers and Applications will cover a broad range of topics in graph neural networks, by reviewing and introducing the fundamental concepts and algorithms of GNNs, new research frontiers of GNNs, and broad and emerging applications with GNNs. In addition, rich tutorial materials will be included and introduced to help the audience gain a systematic understanding by using our recently published book-Graph Neural Networks (GNN): Foundation, Frontiers, and Applications [12], which can easily be accessed at https://graph-neural-networks.github.io/index.html.
Geometric Policy Iteration for Markov Decision Processes
Authors: Yue Wu, Jesús A. De Loera
Venue: KDD
Year: 2022

Recently discovered polyhedral structures of the value function for finite discounted Markov decision processes (MDP) shed light on understanding the success of reinforcement learning. We investigate the value function polytope in greater detail and characterize the polytope boundary using a hyperplane arrangement. We further show that the value space is a union of finitely many cells of the same hyperplane arrangement, and relate it to the polytope of the classical linear programming formulation for MDPs. Inspired by these geometric properties, we propose a new algorithm, Geometric Policy Iteration (GPI), to solve discounted MDPs. GPI updates the policy of a single state by switching to an action that is mapped to the boundary of the value function polytope, followed by an immediate update of the value function. This new update rule aims at a faster value improvement without compromising computational efficiency. Moreover, our algorithm allows asynchronous updates of state values which is more flexible and advantageous compared to traditional policy iteration when the state set is large. We prove that the complexity of GPI achieves the best known bound O|𝓐|over 1 - γ log 1 over 1-γ of policy iteration and empirically demonstrate the strength of GPI on MDPs of various sizes.
Deep Learning on Graphs: Methods and Applications (DLG-KDD2022)
Authors: Lingfei Wu 0001, Jian Pei 0001, Jiliang Tang, Yinglong Xia, Xiaojie Guo 0002
Venue: KDD
Year: 2022

Deep Learning models are at the core of research in Artificial Intelligence research today. A tide in research for deep learning on graphs or graph neural networks. This wave of research at the intersection of graph theory and deep learning has also influenced other fields of science, including computer vision, natural language processing, program synthesis and analysis, financial security, Drug Discovery and so on. However, there are still many challenges regarding a broad range of the topics in deep learning on graphs, from methodologies to applications, and from foundations to the new frontiers of GNNs. This international workshop on "Deep Learning on Graphs: Method and Applications (DLG-KDD'22)" aims to bring together both academic researchers and industrial practitioners from different backgrounds and perspectives to above challenges.
Robust Tensor Graph Convolutional Networks via T-SVD based Graph Augmentation
Authors: Zhebin Wu, Lin Shu, Ziyue Xu 0002, Yaomin Chang, Chuan Chen 0001, Zibin Zheng
Venue: KDD
Year: 2022

Graph Neural Networks (GNNs) have exhibited their powerful ability of tackling nontrivial problems on graphs. However, as an extension of deep learning models to graphs, GNNs are vulnerable to noise or adversarial attacks due to the underlying perturbations propagating in message passing scheme, which can affect the ultimate performances dramatically. Thus, it's vital to study a robust GNN framework to defend against various perturbations. In this paper, we propose a Robust Tensor Graph Convolutional Network (RT-GCN) model to improve the robustness. On the one hand, we utilize multi-view augmentation to reduce the augmentation variance and organize them as a third-order tensor, followed by the truncated T-SVD to capture the low-rankness of the multi-view augmented graph, which improves the robustness from the perspective of graph preprocessing. On the other hand, to effectively capture the inter-view and intra-view information on the multi-view augmented graph, we propose tensor GCN (TGCN) framework and analyze the mathematical relationship between TGCN and vanilla GCN, which improves the robustness from the perspective of model architecture. Extensive experimental results have verified the effectiveness of RT-GCN on various datasets, demonstrating the superiority to the state-of-the-art models on diverse adversarial attacks for graphs.