OpenRaiser/Intern-Atlas huggingface dataset:
Learning Sparse Latent Graph Representations for Anomaly Detection in Multivariate Time Series
Authors: Siho Han, Simon S. Woo
Venue: KDD
Year: 2022

Anomaly detection in high-dimensional time series is typically tackled using either reconstruction- or forecasting-based algorithms due to their abilities to learn compressed data representations and model temporal dependencies, respectively. However, most existing methods disregard the relationships between features, information that would be extremely useful when incorporated into a model. In this work, we introduce Fused Sparse Autoencoder and Graph Net (FuSAGNet), which jointly optimizes reconstruction and forecasting while explicitly modeling the relationships within multivariate time series. Our approach combines Sparse Autoencoder and Graph Neural Network, the latter of which predicts future time series behavior from sparse latent representations learned by the former as well as graph structures learned through recurrent feature embedding. Experimenting on three real-world cyber-physical system datasets, we empirically demonstrate that the proposed method enhances the overall anomaly detection performance, outperforming baseline approaches. Moreover, we show that mining sparse latent patterns from high-dimensional time series improves the robustness of the graph-based forecasting model. Lastly, we conduct visual analyses to investigate the interpretability of both recurrent feature embeddings and sparse latent representations.
Reinforcement Learning Enhances the Experts: Large-scale COVID-19 Vaccine Allocation with Multi-factor Contact Network
Authors: Qianyue Hao, Wenzhen Huang, Fengli Xu, Kun Tang, Yong Li 0008
Venue: KDD
Year: 2022

In the fight against the COVID-19 pandemic, vaccines are the most critical resource but are still in short supply around the world. Therefore, efficient vaccine allocation strategies are urgently called for, especially in large-scale metropolis where uneven health risk is manifested in nearby neighborhoods. However, there exist several key challenges in solving this problem: (1) great complexity in the large scale scenario adds to the difficulty in experts' vaccine allocation decision making; (2) heterogeneous information from all aspects in the metropolis' contact network makes information utilization difficult in decision making; (3) when utilizing the strong decision-making ability of reinforcement learning (RL) to solve the problem, poor explainability limits the credibility of the RL strategies. In this paper, we propose a reinforcement learning enhanced experts method. We deal with the great complexity via a specially designed algorithm aggregating blocks in the metropolis into communities and we hierarchically integrate RL among the communities and experts solution within each community. We design a self-supervised contact network representation algorithm to fuse the heterogeneous information for efficient vaccine allocation decision making. We conduct extensive experiments in three metropolis with real-world data and prove that our method outperforms the best baseline, reducing 9.01% infections and 12.27% deaths.We further demonstrate the explainability of the RL model, adding to its credibility and also enlightening the experts in turn.
Three-Stage Root Cause Analysis for Logistics Time Efficiency via Explainable Machine Learning
Authors: Shiqi Hao, Yang Liu 0064, Yu Wang, Yuan Wang 0058, Wenming Zhe
Venue: KDD
Year: 2022

The performance of logistics highly depends on the time efficiency, and hence, plenty of efforts have been devoted to ensuring the on-time delivery in modern logistics industry. However, the delay in logistics transportation and delivery can still happen due to various practical issues, which significantly impact the quality of logistics service. In order to address this issue, this work investigates the root causes impacting the time efficiency, thereby facilitating the operation of logistics systems such that resources can be appropriately allocated to improve the performance. The proposed solution comprises three stages, where statistical methods are employed in the first stage to analyze the pattern of on-time delivery rate and detect the abnormalities induced by non-ideality of operations. Subsequently, a machine learning model is trained to capture the underlying correlations between time efficiency and potential impacting factors. Finally, explainable machine learning techniques are utilized to quantify the contributions of the impacting factors to the time efficiency, thereby recognizing the root causes. The proposed method is comprehensively studied on the real JD Logistics data through experiments, where it can identify the root causes that impact the time efficiency of logistics delivery with high accuracy. Furthermore, it is also demonstrated to outperform the baselines including a recent state-of-the-art method.
Scalable Online Disease Diagnosis via Multi-Model-Fused Actor-Critic Reinforcement Learning
Authors: Weijie He, Ting Chen
Venue: KDD
Year: 2022

For those seeking healthcare advice online, AI based dialogue agents capable of interacting with patients to perform automatic disease diagnosis are a viable option. This application necessitates efficient inquiry of relevant disease symptoms in order to make accurate diagnosis recommendations. This can be formulated as a problem of sequential feature (symptom) selection and classification for which reinforcement learning (RL) approaches have been proposed as a natural solution. They perform well when the feature space is small, that is, the number of symptoms and diagnosable disease categories is limited, but they frequently fail in assignments with a large number of features. To address this challenge, we propose a Multi-Model-Fused Actor-Critic (MMF-AC) RL framework that consists of a generative actor network and a diagnostic critic network. The actor incorporates a Variational AutoEncoder (VAE) to model the uncertainty induced by partial observations of features, thereby facilitating in making appropriate inquiries. In the critic network, a supervised diagnosis model for disease predictions is involved to precisely estimate the state-value function. Furthermore, inspired by the medical concept of differential diagnosis, we combine the generative and diagnosis models to create a novel reward shaping mechanism to address the sparse reward problem in large search spaces. We conduct extensive experiments on both synthetic and real-world datasets for empirical evaluations. The results demonstrate that our approach outperforms state-of-the-art methods in terms of diagnostic accuracy and interaction efficiency while also being more effectively scalable to large search spaces. Besides, our method is adaptable to both categorical and continuous features, making it ideal for online applications.
Partial Label Learning with Semantic Label Representations
Authors: Shuo He 0001, Lei Feng 0006, Fengmao Lv, Wen Li 0001, Guowu Yang
Venue: KDD
Year: 2022

Partial-label learning (PLL) solves the problem where each training instance is assigned a candidate label set, among which only one is the ground-truth label. The core of PLL is to learn efficient feature representations to facilitate label disambiguation. However, existing PLL methods only learn plain representations by coarse supervision, which is incapable of capturing sufficiently distinguishable representations, especially when confronted with the knotty label ambiguity, i.e., certain candidate labels share similar visual patterns. In this paper, we propose a novel framework partial label learning with semantic label representations dubbed ParSE, which consists of two synergistic processes, including visual-semantic representation learning and powerful label disambiguation. In the former process, we propose a novel weighted calibration rank loss that has two implications. First, it implies a progressive calibration strategy that utilizes the disambiguated label confidence to weight the similarity between each image feature embedding and its corresponding semantic label representations of all candidates. Second, it also considers the ranking relationship between candidate and non-candidate ones. Based on learned visual-semantic representations, subsequent label disambiguation is desirably endowed with more powerful abilities. Experiments on benchmarks show that ParSE outperforms state-of-the-art counterparts.
Core-periphery Partitioning and Quantum Annealing
Authors: Catherine F. Higham, Desmond J. Higham, Francesco Tudisco
Venue: KDD
Year: 2022

We propose a new kernel that quantifies success for the task of computing a core-periphery partition for an undirected network. Finding the associated optimal partitioning may be expressed in the form of a quadratic unconstrained binary optimization (QUBO) problem, to which a state-of-the-art quantum annealer may be applied. We therefore make use of the new objective function to (a) judge the performance of a quantum annealer, and (b) compare this approach with existing heuristic core-periphery partitioning methods. The quantum annealing is performed on a commercially available D-Wave machine. The QUBO problem involves a full matrix even when the underlying network is sparse. Hence, we develop and test a sparsified version of the original QUBO which increases the available problem dimension for the quantum annealer. Results are provided on both synthetic and real data sets, and we conclude that the QUBO/quantum annealing approach offers benefits in terms of optimizing this new quantity of interest.
AdaAX: Explaining Recurrent Neural Networks by Learning Automata with Adaptive States
Authors: Dat Hong, Alberto Maria Segre, Tong Wang
Venue: KDD
Year: 2022

Recurrent neural networks (RNN) are widely used for handling sequence data. However, their black-box nature makes it difficult for users to interpret the decision-making process. We propose a new method to construct deterministic finite automata to explain RNN. In an automaton, states are abstracted from hidden states produced by the RNN, and the transitions represent input symbols. Thus, users can follow the paths of transitions, called patterns, to understand how a prediction is produced. Existing methods for extracting automata partition the hidden state space at the beginning of the extraction, which often leads to solutions that are either inaccurate or too large in size to comprehend. Unlike previous methods, our approach allows the automata states to be formed adaptively during the extraction. Instead of defining patterns on pre-determined clusters, our proposed model, AdaAX, identifies small sets of hidden states determined by patterns with finer granularity in data. Then these small sets are gradually merged to form states, allowing users to trade fidelity for lower complexity. Experiments show that our automata can achieve higher fidelity while being significantly smaller in size than baseline methods on synthetic and complex real datasets.
Low-rank Nonnegative Tensor Decomposition in Hyperbolic Space
Authors: Bo Hui 0001, Wei-Shinn Ku
Venue: KDD
Year: 2022

Tensor decomposition aims to factorize an input tensor into a number of latent factors. Due to the low-rank nature of tensor in real applications, the latent factors can be used to perform tensor completion in numerous tasks, such as knowledge graph completion and timely recommendation. However, existing works solve the problem in Euclidean space, where the tensor is decomposed into Euclidean vectors. Recent studies show that hyperbolic space is roomier than Euclidean space. With the same dimension, a hyperbolic vector can represent richer information (e.g., hierarchical structure) than a Euclidean vector. In this paper, we propose to decompose tensor in hyperbolic space. Considering that the most popular optimization tools (e.g, SGD, Adam) have not been generalized in hyperbolic space, we design an adaptive optimization algorithm according to the distinctive property of hyperbolic manifold. To address the non-convex property of the problem, we adopt gradient ascent in our optimization algorithm to avoid getting trapped in local optimal landscapes. We conduct experiments on various tensor completion tasks and the result validates the superiority of our method over these baselines that solve the problem in Euclidean space.
Flexible Modeling and Multitask Learning using Differentiable Tree Ensembles
Authors: Shibal Ibrahim, Hussein Hazimeh 0001, Rahul Mazumder
Venue: KDD
Year: 2022

Decision tree ensembles are widely used and competitive learning models. Despite their success, popular toolkits for learning tree ensembles have limited modeling capabilities. For instance, these toolkits support a limited number of loss functions and are restricted to single task learning. We propose a flexible framework for learning tree ensembles, which goes beyond existing toolkits to support arbitrary loss functions, missing responses, and multi-task learning. Our framework builds on differentiable (a.k.a. soft) tree ensembles, which can be trained using first-order methods. However, unlike classical trees, differentiable trees are difficult to scale. We therefore propose a novel tensor-based formulation of differentiable trees that allows for efficient vectorization on GPUs. We introduce FASTEL: a new toolkit (based on Tensorflow 2) for learning differentiable tree ensembles. We perform experiments on a collection of 28 real open-source and proprietary datasets, which demonstrate that our framework can lead to 100x more compact and 23% more expressive tree ensembles than those obtained by popular toolkits.
Rax: Composable Learning-to-Rank Using JAX
Authors: Rolf Jagerman, Xuanhui Wang, Honglei Zhuang, Zhen Qin 0001, Michael Bendersky, Marc Najork
Venue: KDD
Year: 2022

Rax is a library for composable Learning-to-Rank (LTR) written entirely in JAX. The goal of Rax is to facilitate easy prototyping of LTR systems by leveraging the flexibility and simplicity of JAX. Rax provides a diverse set of popular ranking metrics and losses that integrate well with the rest of the JAX ecosystem. Furthermore, Rax implements a system of ranking-specific function transformations which allows fine-grained customization of ranking losses and metrics. Most notably Rax provides approx_t12n: a function transformation (t12n) that can transform any of our ranking metrics into an approximate and differentiable form that can be optimized. This provides a systematic way to directly optimize neural ranking models for ranking metrics that are not easily optimizable in other libraries. We empirically demonstrate the effectiveness of Rax by benchmarking neural models implemented using Flax and trained using Rax on two popular LTR benchmarks: WEB30K and Istella. Furthermore, we show that integrating ranking losses with T5, a large language model, can improve overall ranking performance on the MS MARCO passage ranking task. We are sharing the Rax library with the open source community as part of the larger JAX ecosystem at https://github.com/google/rax.
A Fully Differentiable Set Autoencoder
Authors: Nikita Janakarajan, Jannis Born, Matteo Manica
Venue: KDD
Year: 2022

Neural networks can leverage self-supervision to learn integrated representations across multiple data modalities. This makes them suitable to uncover complex relationships between vastly different data types, thus lowering the dependency on labor-intensive feature engineering methods. Leveraging deep representation learning, we propose a generic, robust and systematic model that is able to combine multiple data modalities in a permutation and modes-number-invariant fashion, both fundamental properties to properly face changes in data type content and availability. To this end, we treat each multi-modal data sample as a set and utilise autoencoders to learn a fixed size, permutation invariant representation that can be used in any decision making process. We build upon previous work that demonstrates the feasibility of presenting a set as an input to autoencoders through content-based attention mechanisms. However, since model inputs and outputs are permutation invariant, we develop an end-to-end architecture that approximates the solution of a linear sum assignment problem, i.e., a minimum-cost bijective mapping problem, to ensure a match between the elements of the input and the output set for effective loss calculation. We demonstrate the model capability to learn a combined representation while preserving individual mode characteristics focusing on the task of reconstructing multi-omic cancer data. The code is made publicly available on Github https://github.com/PaccMann/fdsa ).
Frontiers of Graph Neural Networks with DIG
Authors: Shuiwang Ji, Meng Liu 0015, Yi Liu 0059, Youzhi Luo, Limei Wang, Yaochen Xie, Zhao Xu 0005, Haiyang Yu 0005
Venue: KDD
Year: 2022

This tutorial is proposed based upon the recently released open-source library Dive into Graphs (DIG) along with hands-on code examples. DIG is a turnkey library that considers four frontiers in graph deep learning, including self-supervised learning of GNNs, 3D GNNs, explainability of GNNs, and graph generation. It provides data interfaces, common algorithms, and evaluation metrics for each direction. It has 255,000+ visitors, 11,000+ installations, and 1,100+ stars within a year and is becoming a robust and dominant ecosystem for graph neural network research. In this tutorial, we will review representative methodologies for these four directions and show hands-on code examples to demonstrate how to effortlessly implement benchmarks using DIG. This tutorial targets a broad audience working on or interested in various research themes. To encourage audience participation, we will promote our tutorial in advance on social media, reading groups, and library contribution community. We anticipate this tutorial would attract more researchers to these interesting and promising topics, leading to a more active community, eventually generating both scientific values and real-world impacts.
Analyzing Online Transaction Networks with Network Motifs
Authors: Jiawei Jiang 0001, Yusong Hu, Xiaosen Li, Wen Ouyang, Zhitao Wang, Fangcheng Fu, Bin Cui 0001
Venue: KDD
Year: 2022

Network motif is a kind of frequently occurring subgraph that reflects local topology in graphs. Although network motif has been studied in graph analytics, e.g., social network and biological network, it is yet unclear whether network motif is useful for analyzing online transaction network that is generated in applications such as instant messaging and e-commerce. In this work, we analyze online transaction networks from the perspective of network motif. We define vertex features based on size-2 and size-3 motifs, and introduce motif-based centrality measurements. We further design motif-based vertex embedding that integrates weighted motif counts and centrality measurements. Afterward, we implement a distributed framework for motif detection in large-scale online transaction networks. To understand the effectiveness of motif for analyzing online transaction network, we study the statistical distribution of motifs in various kinds of graphs in Tencent and assess the benefit of motif-based embedding in a range of downstream graph analytical tasks. Empirical results show that our proposed method can efficiently find motifs in large-scale graphs, help interpretability, and benefit downstream tasks.
Selective Cross-City Transfer Learning for Traffic Prediction via Source City Region Re-Weighting
Authors: Yilun Jin, Kai Chen 0005, Qiang Yang 0001
Venue: KDD
Year: 2022

Deep learning models have been demonstrated powerful in modeling complex spatio-temporal data for traffic prediction. In practice, effective deep traffic prediction models rely on large-scale traffic data, which is not always available in real-world scenarios. To alleviate the data scarcity issue, a promising way is to use cross-city transfer learning methods to fine-tune well-trained models from source cities with abundant data. However, existing approaches overlook the divergence between source and target cities, and thus, the trained model from source cities may contain noise or even harmful source knowledge. To address the problem, we propose CrossTReS, a selective transfer learning framework for traffic prediction that adaptively re-weights source regions to assist target fine-tuning. As a general framework for fine-tuning-based cross-city transfer learning, CrossTReS consists of a feature network, a weighting network, and a prediction model. We train the feature network with node- and edge-level domain adaptation techniques to learn generalizable spatial features for both source and target cities. We further train the weighting network via source-target joint meta-learning such that source regions helpful to target fine-tuning are assigned high weights. Finally, the prediction model is selectively trained on the source city with the learned weights to initialize target fine-tuning. We evaluate CrossTReS using real-world taxi and bike data, where under the same settings, CrossTReS outperforms state-of-the-art baselines by up to 8%. Moreover, the learned region weights offer interpretable visualization.
A Spectral Representation of Networks: The Path of Subgraphs
Authors: Shengmin Jin, Hao Tian, Jiayu Li 0002, Reza Zafarani
Venue: KDD
Year: 2022

Network representation learning has played a critical role in studying networks. One way to study a graph is to focus on its spectrum, i.e., the eigenvalue distribution of its associated matrices. Recent advancements in spectral graph theory show that spectral moments of a network can be used to capture the network structure and various graph properties. However, sometimes networks with different structures or sizes can have the same or similar spectral moments, not to mention the existence of the cospectral graphs. To address such problems, we propose a 3D network representation that relies on the spectral information of subgraphs: the Spectral Path, a path connecting the spectral moments of the network and those of its subgraphs of different sizes. We show that the spectral path is interpretable and can capture relationship between a network and its subgraphs, for which we present a theoretical foundation. We demonstrate the effectiveness of the spectral path in applications such as network visualization and network identification.
Vexation-Aware Active Learning for On-Menu Restaurant Dish Availability
Authors: Jean-François Kagy, Flip Korn, Afshin Rostamizadeh, Chris Welty
Venue: KDD
Year: 2022

Here we leverage the power of the crowd: online users who are willing to answer questions about dish availability at restaurants visited. While motivated users are happy to contribute knowledge, they are much less likely to respond to "silly'' or embarrassing questions (e.g., "DoesPizza Hut serve pizza?'' or "DoesMike's Vegan Restaurant serve steak?'')
Dynamic Graph Segmentation for Deep Graph Neural Networks
Authors: Johan Kok Zhi Kang, Suwei Yang, Suriya Venkatesan, Sien Yi Tan, Feng Cheng, Bingsheng He
Venue: KDD
Year: 2022

We present Deep network Dynamic Graph Partitioning (DDGP), a novel algorithm for optimizing the division of large graphs for mixture of expert graph neural networks. Our work is motivated from the observation that real world graphs suffer from spatial concept drift, which is detrimental to neural network training. We answer the question of how we can divide a graph, with vertices in each subgraph sharing a similar distribution, so that an expert network trained over each subgraph may yield the best learning outcome. DDGP is a two pronged algorithm that consists of cluster merging, followed by cluster boundary refinement. We used the training performance of each expert model as feedback to iteratively refine partition boundaries among subgraphs. These partitions are distinct for each model and graph network. We provide theoretical proof of convergence for DDGP boundary refinement as a guarantee for model training stability. Finally, we demonstrate experimentally that DDGP outperforms state-of-the-art graph partitioning algorithms for a regression task on multiple large real world graphs, with GraphSage and Graph Attention as our expert models.