Abstract
Anomaly subgraph detection is a crucial task in various real-world applications, including identifying high-risk areas, detecting river pollution, and monitoring disease outbreaks. Early traditional graph-based methods can obtain high-precision detection results in scenes with small-scale graphs and obvious anomaly features. Most existing anomaly detection methods based on deep learning primarily concentrate on identifying anomalies at the node level, while neglecting to detect anomaly groups in the internal structure. In this paper, we propose a novel end-to-end Graph Neural Network (GNN) based anomaly subgraph detection approach (ASD-HC) in graph-structured data. 1) We propose a high-order neighborhood sampling strategy to construct our node and k-order neighbor-subgraph instance pairs. 2) Anomaly features of nodes are captured through a self-supervised contrastive learning model. 3) Detecting the maximum connected anomaly subgraph is performed by integrating the Non-parameter Graph Scan statistics and a Random Walk module. We evaluate ASD-HC against five state-of-the-art baselines using five benchmark datasets. ASD-HC outperforms the baselines by over 13.01% in AUC score. Various experiments demonstrate that our approach effectively detects anomaly subgraphs within large-scale graphs.
Introduction
Most graph anomaly detection research focuses on Anomalous Node Detection (AND)—identifying individual "lone wolf" outliers. However, in many real-world scenarios like disease outbreaks, financial fraud rings, or localized pollution, anomalies appear as subgraphs: groups of interconnected nodes that collectively exhibit suspicious behavior.
Detecting these subgraphs is significantly harder than finding single nodes because of structural complexity, the exponential growth of the search space for the maximum connected anomaly subgraph, and the difficulty existing deep learning models face in capturing internal structural dependencies that define a suspicious cluster.
Methodology
The authors propose ASD-HC (Anomaly Subgraph Detection through High-order sampling Contrastive learning), which consists of three main stages:
- High-Order Neighborhood Sampling: To capture structural influence, the model uses a weight matrix derived from the $k$-th power of the adjacency matrix. This allows the model to identify "maximal influential neighbors" to construct node-subgraph pairs, capturing more complex connectivity patterns than simple random walks.
- Contrastive Learning Module: The model sets up a self-supervised task creating positive pairs (a node and its most influential $k$-order neighbor subgraph) and negative pairs. A GNN encodes these pairs, and a bilinear discriminator learns to distinguish between them. Anomalous nodes are those that deviate from their structural context, leading to high contrastive loss.
- Statistical Subgraph Detection: After calculating individual node anomaly scores, the model uses Random Walk with Restart (RWR) to group candidate anomalous nodes. It then applies Non-parametric Graph Scan (NPGS) statistics—specifically the Higher Criticism (HC) statistic—to identify the specific subgraph that maximizes the "anomalous signal" relative to a null hypothesis.
Experiments and Results
The model was evaluated on five widely used benchmark datasets: Cora, Citeseer, ACM, BlogCatalog, and Flickr. To test the model, the authors injected structural anomalies (densely connected cliques) and attribute anomalies (perturbed node features).
Key Insights
- High-Order Context: The paper demonstrates that looking at $k$-order neighbors (where $k=3$ is often optimal) provides a much richer context for what "normal" connectivity looks like compared to just looking at immediate neighbors.
- Contrastive Learning as a Proxy: By training the model to recognize the relationship between a node and its influential neighborhood, any node that deviates from this learned structural pattern naturally produces a high anomaly score.
- Bridging Deep Learning and Statistics: A key strength is using GNNs for feature extraction while relying on mathematically rigorous scan statistics (Higher Criticism) to define the boundaries of the anomaly subgraph, avoiding the "black box" problem of simple top-K selection.
Performance
ASD-HC achieved the highest AUC scores across almost all datasets. Notably, it outperformed the best baseline (ANEMONE) by 2.42% on Cora and 3.88% on ACM. In the specific task of detecting the entire anomaly subgraph, ASD-HC outperformed the specialized baseline AS-GAE by a margin of at least 13.01%.
Conclusion
ASD-HC represents a significant advancement in detecting clusters of anomalous nodes. While detecting subgraphs is more computationally intensive than node-level detection, the use of RWR and sampling strategies mitigates the search space complexity. Future work involves extending the framework to dynamic graphs to capture temporal anomalies like spreading viruses or flash crowds.
Summary updated