论文检索

Shoujin Wang, Wentao Wang, Xiuzhen Zhang 0001, Yan Wang 0002, Huan Liu 0001, Fang Chen 0001

In the era of information explosion, news recommender systems are crucial for users to effectively and efficiently discover their interested news. However, most of the existing news recommender systems face two major issues, hampering recommendation quality. Firstly, they often oversimplify users' reading interests, neglecting their hierarchical nature, spanning from high-level event (e.g., US Election) related interests to low-level news article-specifc interests. Secondly, existing work often assumes a simplistic context, disregarding the prevalence of fake news and political bias under the real-world context. This oversight leads to recommendations of biased or fake news, posing risks to individuals and society. To this end, this paper addresses these gaps by introducing a novel framework, the Hierarchical and Disentangling Interest learning framework (HDInt). HDInt incorporates a hierarchical interest learning module and a disentangling interest learning module. The former captures users' high- and low-level interests, enhancing next-news recommendation accuracy. The latter effectively separates polarity and veracity information from news contents and model them more specifcally, promoting fairness- and truth-aware reading interest learning for unbiased and true news recommendations. Extensive experiments on two real-world datasets demonstrate HDInt's superiority over state-of-the-art news recommender systems in delivering accurate, unbiased, and true news recommendations.

Ruijia Wang, Haoran Dai, Cheng Yang 0002, Le Song, Chuan Shi 0001

Graph neural networks (GNNs) have revolutionized molecule representation learning by modeling molecules as graphs, with atoms represented as nodes and chemical bonds as edges. Despite their progress, they struggle with out-of-distribution scenarios, such as changes in size or scaffold of molecules with identical properties. Some studies attempt to mitigate this issue through graph invariant learning, which penalizes prediction variance across environments to learn invariant representations. But in the realm of molecules, core functional groups forming privileged substructures dominate molecular properties and remain invariant across distribution shifts. This highlights the need for integrating this prior knowledge and ensuring the environment split compatible with molecule invariant learning. To bridge this gap, we propose a novel framework named MILI. Specifically, we first formalize molecule invariant learning based on privileged substructure identification and introduce substructure invariance constraint. Building on this foundation, we theoretically establish two criteria for environment splits conducive to molecule invariant learning. Inspired by these criteria, we develop a dual-head graph neural network. A shared identifier identifies privileged substructures, while environment and task heads generate predictions based on variant and privileged substructures. Through the interaction of two heads, the environments are split and optimized to meet our criteria. The unified MILI guarantees that molecule invariant learning and environment split achieve mutual enhancement from theoretical analysis and network design. Extensive experiments across eight benchmarks validate the effectiveness of MILI compared to state-of-the-art baselines.

Rui Wang 0118, Xudong Mou, Renyu Yang, Kai Gao, Pin Liu, Chongwei Liu, Tianyu Wo, Xudong Liu 0001

Detecting time-series anomalies is extremely intricate due to the rarity of anomalies and imbalanced sample categories, which often result in costly and challenging anomaly labeling. Most of the existing approaches largely depend on assumptions of normality, overlooking labeled abnormal samples. While anomaly assumptions based methods can incorporate prior knowledge of anomalies for data augmentation in training classifiers, the adopted random or coarse-grained augmentation approaches solely focus on pointwise anomalies and lack cutting-edge domain knowledge, making them less likely to achieve better performance. This paper introduces CutAddPaste, a novel anomaly assumption-based approach for detecting time-series anomalies. It primarily employs a data augmentation strategy to generate pseudo anomalies, by exploiting prior knowledge of anomalies as much as possible. At the core of CutAddPaste is cutting patches from random positions in temporal subsequence samples, adding linear trend terms, and pasting them into other samples, so that it can well approximate a variety of anomalies, including point and pattern anomalies. Experiments on standard benchmark datasets demonstrate that our method outperforms the state-of-the-art approaches.

Kun Wang 0056, Guibin Zhang, Xinnan Zhang, Junfeng Fang, Xun Wu, Guohao Li 0001, Shirui Pan, Wei Huang 0034, Yuxuan Liang 0002

Graph Neural Networks (GNNs) have become pivotal tools for a range of graph-based learning tasks. Notably, most current GNN architectures operate under the assumption of homophily, whether explicitly or implicitly. While this underlying assumption is frequently adopted, it is not universally applicable, which can result in potential shortcomings in learning effectiveness. In this paper, or the first time, we transfer the prevailing concept of "one node one receptive field" to the heterophilic graph. By constructing a proxy label predictor, we enable each node to possess a latent prediction distribution, which assists connected nodes in determining whether they should aggregate their associated neighbors. Ultimately, every node can have its own unique aggregation hop and pattern, much like each snowflake is unique and possesses its own characteristics. Based on observations, we innovatively introduce the Heterophily Snowflake Hypothesis and provide an effective solution to guide and facilitate research on heterophilic graphs and beyond. We conduct comprehensive experiments including (1) main results on 10 graphs with varying heterophily ratios across 10 backbones; (2) scalability on various deep GNN backbones (SGC, JKNet, etc.) across various large number of layers (2,4,6,8,16,32 layers); (3) comparison with conventional snowflake hypothesis; (4) efficiency comparison with existing graph pruning algorithms. Our observations show that our framework acts as a versatile operator for diverse tasks. It can be integrated into various GNN frameworks, boosting performance in-depth and offering an explainable approach to choosing the optimal network depth. The source code is available at https://github.com/bingreeky/HeteroSnoH.

Kun Wang 0056, Guohao Li 0001, Shilong Wang 0002, Guibin Zhang, Kai Wang 0036, Yang You 0001, Junfeng Fang, Xiaojiang Peng, Yuxuan Liang 0002, Yang Wang 0015

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

Junxiang Wang, Guangji Bai, Wei Cheng 0002, Zhengzhang Chen, Liang Zhao 0002, Haifeng Chen

Time series domain adaptation stands as a pivotal and intricate challenge with diverse applications, including but not limited to human activity recognition, sleep stage classification, and machine fault diagnosis. Despite the numerous domain adaptation techniques proposed to tackle this complex problem, they primarily focus on domain adaptation from a single source domain. Yet, it is more crucial to investigate domain adaptation from multiple domains due to the potential for greater improvements. To address this, three important challenges need to be overcome: 1). The lack of exploration to utilize domain-specific information for domain adaptation, 2). The difficulty to learn domain-specific information that changes over time, and 3). The difficulty to evaluate learned domain-specific information. In order to tackle these challenges simultaneously, in this paper, we introduce PrOmpt-based domaiN Discrimination (POND), the first framework to utilize prompts for time series domain adaptation. Specifically, to address Challenge 1, we extend the idea of prompt tuning to time series analysis and learn prompts to capture common and domain-specific information from all source domains. To handle Challenge 2, we introduce a conditional module for each source domain to generate prompts from time series input data. For Challenge 3, we propose two criteria to select good prompts, which are used to choose the most suitable source domain for domain adaptation. The efficacy and robustness of our proposed POND model are extensively validated through experiments across 50 scenarios encompassing four datasets. Experimental results demonstrate that our proposed POND model outperforms all state-of-the-art comparison methods by up to 66% on the F1-score.

Jingwei Wang 0002, Qianyue Hao, Wenzhen Huang, Xiaochen Fan, Zhentao Tang, Bin Wang 0034, Jianye Hao, Yong Li 0008

In large-scale metropolis, it is critical to efficiently allocate various resources such as electricity, medical care, and transportation to meet the living demands of citizens, according to the spatio-temporal distributions of resources and demands. Previous researchers have done plentiful work on such problems by leveraging Multi-Agent Reinforcement Learning (MARL) methods, where multiple agents cooperatively regulate and allocate the resources to meet the demands. However, facing the great number of agents in large cities, existing MARL methods lack efficient parameter sharing strategies among agents to reduce computational complexity. There remain two primary challenges in efficient parameter sharing: (1) during the RL training process, the behavior of agents changes significantly, limiting the performance of group parameter sharing based on fixed role division decided before training; (2) the behavior of agents forms complicated action trajectories, where their role characteristics are implicit, adding difficulty to dynamically adjusting agent role divisions during the training process. In this paper, we propose Dynamic Parameter Sharing (DyPS) to solve the above challenges. We design self-supervised learning tasks to extract the implicit behavioral characteristics from the action trajectories of agents. Based on the obtained behavioral characteristics, we propose a hierarchical MARL framework capable of dynamically revising the agent role divisions during the training process and thus shares parameters among agents with the same role, reducing computational complexity. In addition, our framework can be combined with various typical MARL algorithms, including IPPO, MAPPO, etc. We conduct 7 experiments in 4 representative resource allocation scenarios, where extensive results demonstrate our method's superior performance, outperforming the state-of-the-art baseline methods by up to 31%. Our source codes are available at https://github.com/tsinghua-fib-lab/DyPS.

Jingchao Wang 0002, Zhengnan Deng, Tongxu Lin, Wenyuan Li 0007, Shaobin Ling

Deep graph prompt tuning (DeepGPT), which only tunes a set of continuous prompts for graph transformers, significantly decreases the storage usage during training. However, DeepGPT is limited by its uniform prompts to input graphs with various structures. This is because different graph structures dictate various feature interactions between nodes, while the uniform prompts are not dynamic to tailor the feature transformation for the graph topology. In this paper, we propose a Topo-specific Graph Prompt Tuning (TGPT ), which provides topo-specific prompts tailored to the topological structures of input graphs. Specifically, TGPT learns trainable embeddings for graphlets and frequencies, where graphlets are fundamental sub-graphs that describe the structure around specific nodes. Based on the statistic data about graphlets of input graph, topo-specific prompts are generated by graphlet embeddings and frequency embeddings. The topo-specific prompts include node-level topo-specific prompts for specified nodes, a graph-level topo-specific prompt for the entire graph, and a task-specific prompt to learn task-related information. They are all inserted into specific graph nodes to perform feature transformation, providing specified feature transformation for input graphs with different topological structures. Extensive experiments show that our method outperforms existing lightweight fine-tuning methods and DeepGPT in molecular graph classification and regression with comparable parameters.

Jiajie Wang, Zhiyuan Jerry Lin, Wen Chen

In contemporary data-driven environments, the generation and processing of multivariate time series data is an omnipresent challenge, often complicated by time delays between different time series. These delays, originating from a multitude of sources like varying data transmission dynamics, sensor interferences, and environmental changes, introduce significant complexities. Traditional Time Delay Estimation methods, which typically assume a fixed constant time delay, may not fully capture these variabilities, compromising the precision of predictive models in diverse settings. To address this issue, we introduce the Time Series Model Bootstrap (TSMB), a versatile framework designed to handle potentially varying or even nondeterministic time delays in time series modeling. Contrary to traditional approaches that hinge on the assumption of a single, consistent time delay, TSMB adopts a non-parametric stance, acknowledging and incorporating time delay uncertainties. TSMB significantly bolsters the performance of models that are trained and make predictions using this framework, making it highly suitable for a wide range of dynamic and interconnected data environments. Our comprehensive evaluations, conducted on real-world datasets with different types of time delays, confirm the adaptability and effectiveness of TSMB in multiple contexts. These include, but are not limited to, power and occupancy forecasting in intelligent infrastructures, air quality monitoring, and intricate processes like mineral processing. Further diagnostic analyses strengthen the case for the TSMB estimator's robustness, underlining its significance in scenarios where ambiguity in time delays can have a significant impact on the predictive task.

Jiachuan Wang, Shimin Di, Lei Chen 0002, Charles Wang Wai Ng

Recently, emergence has received widespread attention from the research community along with the success of large-scale models. Different from the literature, we hypothesize a key factor that promotes the performance during the increase of scale: the reduction of monosemantic neurons that can only form one-to-one correlations with specific features. Monosemantic neurons tend to be sparser and have negative impacts on the performance in large models. Inspired by this insight, we propose an intuitive idea to identify monosemantic neurons and inhibit them. However, achieving this goal is a non-trivial task as there is no unified quantitative evaluation metric and simply banning monosemantic neurons does not promote polysemanticity in neural networks. Therefore, we first propose a new metric to measure the monosemanticity of neurons with the guarantee of efficiency for online computation, then introduce a theoretically supported method to suppress monosemantic neurons and proactively promote the ratios of polysemantic neurons in training neural networks. We validate our conjecture that monosemanticity brings about performance change at different model scales on a variety of neural networks and benchmark datasets in different areas, including language, image, and physics simulation tasks. Further experiments validate our analysis and theory regarding the inhibition of monosemanticity.

Hewen Wang, Renchi Yang, Xiaokui Xiao

Graph representation learning (GRL) is to encode graph elements into informative vector representations, which can be used in downstream tasks for analyzing graph-structured data and has seen extensive applications in various domains. However, the majority of extant studies on GRL are geared towards generating node representations, which cannot be readily employed to perform edge-based analytics tasks in edge-attributed bipartite graphs (EABGs) that pervade the real world, e.g., spam review detection in customer-product reviews and identifying fraudulent transactions in user-merchant networks. Compared to node-wise GRL, learning edge representations (ERL) on such graphs is challenging due to the need to incorporate the structure and attribute semantics from the perspective of edges while considering the separate influence of two heterogeneous node sets U and V in bipartite graphs. To our knowledge, despite its importance, limited research has been devoted to this frontier, and existing workarounds all suffer from sub-par results. Motivated by this, this paper designs EAGLE, an effective ERL method for EABGs. Building on an in-depth and rigorous theoretical analysis, we propose the factorized feature propagation (FFP) scheme for edge representations with adequate incorporation of long-range dependencies of edges/features without incurring tremendous computation overheads. We further ameliorate FFP as a dual-view FFP by taking into account the influences from nodes in U and V severally in ERL. Extensive experiments on 5 real datasets showcase the effectiveness of the proposed EAGLE models in semi-supervised edge classification tasks. In particular, EAGLE can attain a considerable gain of at most 38.11% in AP and 1.86% in AUC when compared to the best baselines.

Haozhao Wang, Peirong Zheng, Xingshuo Han, Wenchao Xu 0001, Ruixuan Li 0001, Tianwei Zhang 0004

Federated Learning (FL) suffers from severe performance degradation due to the data heterogeneity among clients. Some existing work suggests that the fundamental reason is that data heterogeneity can cause local model drift, and therefore proposes to calibrate the direction of local updates to solve this problem. Though effective, existing methods generally take the model as a whole, which lacks a deep understanding of how the neurons within deep classification models evolve during local training to form model drift. In this paper, we bridge this gap by performing an intuitive and theoretical analysis of the activation changes of each neuron during local training. Our analysis shows that the high activation of some neurons on the samples of a certain class will be reduced during local training when these samples are not included in the client, which we call neuron drift, thus leading to the performance reduction of this class. Motivated by this, we propose a novel and simple algorithm called FedNLR, which utilizes Neuron-wise Learning Rates during the FL local training process. The principle behind this is to enhance the learning of neurons bound to local classes on local data knowledge while reducing the decay of non-local classes knowledge stored in neurons. Experimental results demonstrate that FedNLR achieves state-of-the-art performance on federated learning with popular deep neural networks.

Haosen Wang, Can Xu 0005, Chenglong Shi, Pengfei Zheng, Shiming Zhang, Minhao Cheng, Hongyang Chen 0001

Self-supervised learning (SSL) has become one of the most popular learning paradigms and has achieved remarkable success in the graph field. Recently, a series of pre-training studies on heterogeneous graphs (HGs) using SSL have been proposed considering the heterogeneity of real-world graph data. However, verification of the robustness of heterogeneous graph pre-training is still a research gap. Most existing researches focus on supervised attacks on graphs, which are limited to a specific scenario and will not work when labels are not available. In this paper, we propose a novel unsupervised heterogeneous graph rewriting attack via node clustering (HGAC) that can effectively attack HG pre-training models without using labels. Specifically, a heterogeneous edge rewriting strategy is designed to ensure the rationality and concealment of the attacks. Then, a tailored heterogeneous graph contrastive learning (HGCL) is used as a surrogate model. Moreover, we leverage node clustering results of the clean HGs as the pseudo-labels to guide the optimization of structural attacks. Extensive experiments exhibit powerful attack performances of our HGAC on various downstream tasks (i.e., node classification, node clustering, metapath prediction, and visualization) under poisoning attack and evasion attack.

Haohui Wang, Baoyu Jing, Kaize Ding, Yada Zhu, Wei Cheng 0002, Si Zhang, Yonghui Fan, Liqing Zhang 0002, Dawei Zhou 0003

In the context of long-tail classification on graphs, the vast majority of existing work primarily revolves around the development of model debiasing strategies, intending to mitigate class imbalances and enhance the overall performance. Despite the notable success, there is very limited literature that provides a theoretical tool for characterizing the behaviors of long-tail classes in graphs and gaining insight into generalization performance in real-world scenarios. To bridge this gap, we propose a generalization bound for long-tail classification on graphs by formulating the problem in the fashion of multi-task learning, i.e., each task corresponds to the prediction of one particular class. Our theoretical results show that the generalization performance of long-tail classification is dominated by the overall loss range and the task complexity. Building upon the theoretical findings, we propose a novel generic framework HierTail for long-tail classification on graphs. In particular, we start with a hierarchical task grouping module that allows us to assign related tasks into hypertasks and thus control the complexity of the task space; then, we further design a balanced contrastive learning module to adaptively balance the gradients of both head and tail classes to control the loss range across all tasks in a unified fashion. Extensive experiments demonstrate the effectiveness of HierTail in characterizing long-tail classes on real graphs, which achieves up to 12.9% improvement over the leading baseline method in balanced accuracy.

Hanzhi Wang 0001

We propose a simple and optimal algorithm, BackMC, for local PageRank estimation in undirected graphs: given an arbitrary target node t in an undirected graph G comprising n nodes and m edges, BackMC accurately estimates the PageRank score of node t while assuring a small relative error and a high success probability. The worst-case computational complexity of BackMC is upper bounded by O(1/dmin ⋅ min(dt, m1/2)), where dmin denotes the minimum degree of G, and dt denotes the degree of t, respectively. Compared to the previously best upper bound of O(log n ⋅ min(dt, m1/2)) (VLDB '23), which is derived from a significantly more complex algorithm and analysis, our BackMC improves the computational complexity for this problem by a factor of Θ(log n/dmin) with a much simpler algorithm. Furthermore, we establish a matching lower bound of Ω(1/dmin ⋅ min(dt, m1/2)) for any algorithm that attempts to solve the problem of local PageRank estimation, demonstrating the theoretical optimality of our BackMC. We conduct extensive experiments on various large-scale real-world and synthetic graphs, where BackMC consistently shows superior performance.

Guolong Wang 0001, Xun Wu, Zheng Qin 0003, Liangliang Shi

Video moment retrieval (VMR) is a cutting-edge vision-language task locating a segment in a video according to the query. Though the methods have achieved significant performance, they assume that training and testing samples share the same action types, hindering real-world application. In this paper, we specifically consider a new problem: video moment retrieval by queries with unseen actions. We propose a plug-and-play structure, Routing Evidence (RE), with multiple evidence-learning heads and dynamically route one to locate a sentence with an unseen action. Each evidence-learning head estimates the uncertainty while regressing timestamps. We formulate the evidence distribution by a Normal-Inverse Gamma function and design a router to select the most appropriate distribution for a sample. Empirically, we study the efficacy of RE on three updated databases where training and testing samples contain different action types. We find that RE outperforms other state-of-the-art methods with a more robust predictor. Code and data will be available at https://github.com/dieuroi/Routing-Evidence.

Fan Wang 0020, Chaochao Chen 0001, Weiming Liu 0005, Tianhao Fan, Xinting Liao, Yanchao Tan, Lianyong Qi, Xiaolin Zheng

Estimating individual treatment effects (ITE) from observational data is challenging due to the absence of counterfactuals and the treatment selection bias. Prevalent ITE estimation methods tackle these challenges by aligning the treated and controlled distributions in the representational space. However, two critical issues have long been overlooked: (1)Mini-batch sampling sensitivity (MSS) issue, where representation distribution alignment at a mini-batch level is vulnerable to poor sampling cases, such as data imbalance and outliers; (2)Inconsistent representation learning (IRL) issue, where representation learning within a unified backbone network suffers from inconsistent gradient update directions due to the distribution skew between different treatment groups. To resolve these issues, we propose CE-RCFR, a Robust CounterFactual Regression framework for Consensus-Enabled causal effect estimation, including a relaxed distribution discrepancy regularizer (RDDR) module and a consensus-enabled aggregator (CEA) module. Specifically, for the robust representation alignment perspective, RDDR addresses the MSS issue by minimizing unbalanced optimal transport divergence between different treatment groups with a relaxed marginal constraint. For the accurate representation optimization perspective, CEA addresses the IRL issue by resolving the consistent gradient update directions on shared parameters within the backbone network. Extensive experiments demonstrate that CE-RCFR significantly outperforms the state-of-the-art methods in treatment effect estimations.

Dingrong Wang, Hitesh Sapkota, Zhiqiang Tao, Qi Yu 0001

Prior research on neural architecture search (NAS) for adversarial robustness has revealed that a lightweight and adversarially robust sub-network could exist in a non-robust large teacher network. Such a sub-network is generally discovered based on heuristic rules to perform neural architecture search. However, heuristic rules are inadequate to handle diverse adversarial attacks and different "teacher" network capacity. To address this key challenge, we propose Reinforced Compressive Neural Architecture Search (RC-NAS), aiming to achieve Versatile Adversarial Robustness. Specifically, we define novel task settings that compose datasets, adversarial attacks, and teacher network configuration. Given diverse tasks, we develop an innovative dual-level training paradigm that consists of a meta-training and a fine-tuning phase to effectively expose the RL agent to diverse attack scenarios (in meta-training), and make it adapt quickly to locate an optimal sub-network (in fine-tuning) for previously unseen scenarios. Experiments show that our framework could achieve adaptive compression towards different initial teacher networks, datasets, and adversarial attacks, resulting in more lightweight and adversarially robust architectures. We also provide a theoretical analysis to explain why the reinforcement learning (RL)-guided adversarial architectural search helps adversarial robustness over standard adversarial training methods.

Danqing Wang, Antonis Antoniades, Kha-Dinh Luong, Edwin Zhang, Mert Kosan, Jiachen Li, Ambuj K. Singh, William Yang Wang, Lei Li 0005

Counterfactual explanations of Graph Neural Networks (GNNs) offer a powerful way to understand data that can naturally be represented by a graph structure. Furthermore, in many domains, it is highly desirable to derive data-driven global explanations or rules that can better explain the high-level properties of the models and data in question. However, evaluating global counterfactual explanations is hard in real-world datasets due to a lack of human-annotated ground truth, which limits their use in areas like molecular sciences. Additionally, the increasing scale of these datasets provides a challenge for random search-based methods. In this paper, we develop a novel global explanation model RLHEX for molecular property prediction. It aligns the counterfactual explanations with human-defined principles, making the explanations more interpretable and easy for experts to evaluate. RLHEX includes a VAE-based graph generator to generate global explanations and an adapter to adjust the latent representation space to human-defined principles. Optimized by Proximal Policy Optimization (PPO), the global explanations produced by RLHEX cover 4.12% more input graphs and reduce the distance between the counterfactual explanation set and the input set by 0.47% on average across three molecular datasets. RLHEX provides a flexible framework to incorporate different human-designed principles into the counterfactual explanation generation process, aligning these explanations with domain expertise. The code and data are released at https://github.com/dqwang122/RLHEX.

Chenhao Wang 0007, Lisi Chen 0001, Shuo Shang, Christian S. Jensen, Panos Kalnis

A trajectory is a sequence of timestamped point locations that captures the movement of an object such as a vehicle. Such trajectories encode complex spatial and temporal patterns and provide rich information about object mobility and the underlying infrastructures, typically road networks, within which the movements occur. A trajectory dataset is evolving when new trajectories are included continuously. The ability to detect anomalous trajectories in online fashion in this setting is fundamental and challenging functionality that has many applications, e.g., location-based services. State-of-the-art solutions determine anomalies based on the shapes or routes of trajectories, ignoring potential anomalies caused by different sampling rates or time offsets. We propose a multi-scale model, termed MST-OATD, for anomalous streaming trajectory detection that considers both the spatial and temporal aspects of trajectories. The model's multi-scale capabilities aim to enable extraction of trajectory features at multiple scales. In addition, to improve model evolvability and to contend with changes in trajectory patterns, the model is equipped with a learned ranking model that updates the training set as new trajectories are included. Experiments on real datasets offer evidence that the model can outperform state-of-the-art solutions and is capable of real-time anomaly detection. Further, the learned ranking model achieves promising results when updating the training set with newly arrived trajectories.