The research results have been accepted by AAAI 2025. The first author of the paper is Yang Xiao, a master's student at Nanyang Technological University's School of Computing and Data Science (CCDS), under the guidance of Professor Miao Chunyan, whose main research interest is graph neural networks. The corresponding author of the paper is Xuejiao Zhao, a Wallenberg-NTU President Postdoctoral Fellow at NTU's Lily Research Centre; Shen Zhiqi is a senior lecturer and senior Research Fellow at the School of Computing and Data Science, Nanyang Technological University.

• Title: A Generalizable Anomaly Detection Method in Dynamic Graphs
• The thesis links: https://arxiv.org/abs/2412.16447
• Code: https://github.com/YXNTU/GeneralDyG

Research background and problem description

With the wide application of dynamic graph data, it has demonstrated powerful modeling capabilities in social networks, e-commerce and network security. However, compared with static graphs, dynamic graphs bring greater challenges to data analysis due to the dynamic evolution of nodes and edges, especially in anomaly detection. Anomaly detection is critical to system security and data integrity, and is designed to identify unusual events that significantly deviate from normal patterns, such as fraudulent transactions, social media spam, and network intrusions. Detecting these anomalies in time is crucial to system reliability and security.

Some progress has been made in dynamic graph anomaly detection methods based on deep learning, such as the use of graph neural networks to extract structural information or the capture of time dependence through time series models. However, there are still significant shortcomings in the generality of these methods. Specifically, they are often difficult to adapt to different data sets and task scenarios, and it is difficult to efficiently capture complex local and global features in dynamic graphs. In addition, some methods have high computational cost when dealing with large-scale dynamic graphs, and the coding of abnormal events is not accurate enough, resulting in a significant decrease in detection performance in new scenes.

Method design

In this paper, a general method (GeneralDyg) is proposed to solve the challenges of data distribution, difficulty in capturing dynamic features and computing cost in anomaly detection of dynamic graphs. Firstly, in order to deal with the problem of diverse data distribution, we extract the key information of nodes, edges and their topologies, so as to adapt to the complex feature distribution of different data sets. Secondly, in order to solve the problem of dynamic feature capture, we combine global temporal dynamics and local structural changes to deeply model multi-scale dynamic patterns in dynamic graphs. Finally, to reduce computational costs, we built a lightweight framework that efficiently captures key dynamic features while significantly improving computational efficiency.

As shown in Figure 1, this methodology consists of three parts, each of which provides a solution to the above challenges:

(a) Time ego-graph sampling module, which can effectively cope with the limitation of computing resources by constructing a compact subgraph structure; (b) Graph neural network extraction module, which comprehensively captures the diversity and complex structure of nodes and edges of dynamic graphs; (c) Time-aware Transformer module for effective integration of global and local dynamic features.

Figure 1: The overall architecture of the dynamic graph exception detection framework GeneralDyG

(a) The Time ego-graph sampling module aims to effectively alleviate the computational pressure caused by the large-scale data of dynamic graphs by constructing a compact subgraph structure. Specifically, based on the central event, the module extracts the history of its surrounding interaction through k-hop algorithm to form a time ego-graph. The design of k-hop algorithm takes into account the temporal order and topological relationship between events to ensure that the sampling process takes into account both temporal dynamics and structural characteristics. In addition, in order to capture hierarchical relationships between events, the module introduces special tags (such as hierarchical tag symbols) to separate interaction information at different levels. These tags help the Transformer module better identify and learn from hierarchical dynamics in time series. In addition, the module controls the size of the sample by limiting the range of k, thus striking a balance between information integrity and computational efficiency. This design significantly reduces computational complexity while preserving dynamic structure information.

(b) Based on the time ego-graph, this paper designs a new graph neural network (TensGNN) to extract rich structural information. TensGNN implements the propagation and update of feature information by alternately applying node layer and edge layer, thus building a strong association between node feature and edge feature. Specifically, the node layer uses the adjacency matrix of nodes and a specific Laplacian matrix for convolution operations, while updating the node representation in combination with edge characteristics. Accordingly, the edge layer updates the feature representation of the edge based on the adjacency of the edge and the state of the node. This alternate stacking approach allows you to better capture local and global features in the dynamic graph. In addition, the module introduces lightweight operators to avoid redundant calculations and maintain high computational efficiency on large-scale data sets.

(c) Time-aware Transformer module: Finally, GeneralDyG integrates time series and structural features through the time-aware Transformer module. In the self-attention mechanism, the model uses Query and Key respectively to encode the topological information of the graph, while the Value is retained as the original event feature to ensure the accuracy of anomaly detection. Through this module, the model can effectively capture the global time dependence and local dynamic changes in dynamic graphs, so as to achieve accurate modeling of complex anomaly patterns.

Experimental verification

This paper conducted experimental evaluation at two levels, node level and edge level, using four real data sets: SWaT and WADI for node level anomaly detection, and Bitcoin-Alpha and Bitcoin-OTC for edge level anomaly detection.

We compared GeneralDyG to 20 mainstream baseline methods covering both graph embedding (e.g. node2vec, DeepWalk) and anomaly detection (e.g. TADDY, SAD, GDN). The model performance was evaluated by AUC, AP and F1, and systematically tested at different anomaly ratios (1%, 5%, 10%). The results show that GeneralDyG is significantly superior to existing methods on all datasets, demonstrating excellent generality and detection capabilities, as shown in Figure 2.

Figure 2 Comparison of edge anomaly detection performance on Bitcoin-Alpha and Bitcoin-OTC datasets.

Sum up

In summary, we propose a general anomaly detection method GeneralDyg on dynamic graphs, which solves the three core problems of diverse data distribution, difficult dynamic feature capture and computational cost. GeneralDyG shows excellent universality and robustness, and provides an efficient and universal solution for anomaly detection on dynamic graphs. Please refer to the original article for details of the method process and experimental results.