ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness

Jingcan Duan, Bin Xiao, Siwei Wang, Haifang Zhou, Xinwang Liu

TL;DR

This paper introduces ARISE, a novel framework for detecting anomalies in attributed networks that explicitly considers substructures. By focusing on dense substructures as potential indicators of anomalies and combining this with graph contrastive learning for attribute analysis, ARISE achieves state-of-the-art performance in identifying both topological and attribute anomalies.

What Problem Does This Paper Address?

Attributed networks, which combine network structure with node attributes, are increasingly used to model complex real-world scenarios like fraud detection and network intrusion. Anomaly detection in these networks aims to identify nodes that deviate from normal patterns. Existing methods often struggle to effectively detect "topology anomalies," which are characterized by collective anomalous behavior within dense substructures, even if individual nodes have normal attributes. These methods tend to focus on individual node attributes or simple neighborhood comparisons, overlooking the collective nature of these topological anomalies. This paper addresses this gap by proposing a method that specifically targets and leverages these substructures for anomaly detection.

Methods

ARISE is a multi-component framework designed to detect both topology and attribute anomalies simultaneously.

  • Topology Anomaly Detection: This module introduces a novel substructure-aware approach. It first uses a density-based algorithm (specifically, a k-core method) to identify "suspicious regions" – high-density substructures that might contain topology anomalies. Within these substructures, the anomaly degree of nodes is evaluated by their average node-pair similarity. Lower similarity suggests a higher probability of anomaly.
  • Attribute Anomaly Detection: This module employs a graph contrastive learning scheme. It constructs positive pairs (target node and its subgraph) and negative pairs (target node and an irrelevant subgraph) to learn robust node embeddings. These embeddings are crucial for accurately measuring attribute similarity and are also leveraged by the topology anomaly detection module.
  • Anomaly Score Calculation: The framework fuses the scores from both modules. The topology anomaly score is derived from the reciprocal of the average node-pair similarity within substructures, with a multi-size substructure scoring strategy. The attribute anomaly score is based on the similarity between node embeddings and their contrastive subgraphs. Finally, an aggregator combines these scores, using a weighted sum, to produce a final anomaly score for each node.

Datasets

The paper evaluates ARISE on six commonly used benchmark datasets for attributed network anomaly detection:

  • Cora
  • CiteSeer
  • DBLP
  • Citation
  • ACM
  • PubMed

These datasets are described as typically having no inherent anomalies, so the authors inject both topology and attribute anomalies to create a controlled experimental setup.

Key Insights and Ideas

  • Substructure Awareness is Key for Topology Anomalies: The core insight is that topology anomalies often manifest as collective behaviors within dense substructures, not just isolated node deviations. ARISE's focus on identifying and analyzing these substructures is a significant departure from previous methods.
  • Graph Contrastive Learning Benefits Both Tasks: The use of graph contrastive learning not only improves the detection of attribute anomalies but also provides better node embeddings that enhance the accuracy of topology anomaly detection.
  • Fusion is Crucial for Comprehensive Detection: Combining topology and attribute anomaly scores through a weighted fusion strategy leads to superior overall performance compared to relying on either type of anomaly detection alone.

Key Results

ARISE demonstrates significant improvements over state-of-the-art methods across various metrics:

  • AUC and AUPRC: ARISE achieves substantial gains, with AUC improvements up to 7.30% and AUPRC gains up to 17.46% on benchmark datasets, indicating its superior ability to distinguish anomalies from normal nodes.
  • Precision@K: The model performs competitively or better than existing methods in identifying true anomalies within the top-ranked nodes.
  • Robustness to Anomaly Injection: ARISE shows resilience even when anomaly injection methods are made more challenging, outperforming competitors.
  • Efficiency: ARISE achieves its performance gains without a significant increase in computational complexity compared to other advanced methods.

Limitations and Future Work

  • Anomaly Injection Method: While the paper uses a standard method for injecting topology anomalies, it also explores a more challenging "drop-out" method, noting that this makes detection harder and presents a future research direction.
  • Fusion Strategy: The paper investigates different fusion strategies (Max, Sum, Weight) and finds that a weighted approach is generally the most comprehensive, though not always the absolute best in every specific scenario.
  • Future Work: The authors suggest further exploring how to better aggregate topology and attribute anomaly scores to minimize information loss and potentially improve detection even further. They also mention that more sophisticated substructure discovery algorithms could be integrated into their framework.

Summary updated

BibTeX
@article{duan2024arise,
  author = {Jingcan Duan and Bin Xiao and Siwei Wang and Haifang Zhou and Xinwang Liu},
  title = {{ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2024},
  doi = {10.1109/tnnls.2023.3312655},
}
Figure