NAAST-GNN: Neighborhood Adaptive Aggregation and Spectral Tuning for Graph Anomaly Detection

Ronghui Guo, Xiaowang Zhang, Zhizhi Yu, Minghui Zou, Sai Zhang, Zhiyong FengIJCAI 2025 · DOI

Graph Anomaly Detection (GAD) is a critical task in identifying fraudulent activities in financial networks or malicious actors in social media. A primary challenge in GAD is heterophily, where anomalous nodes deliberately connect to normal nodes to mask their behavior. While heterophily is often cited as the root cause of poor Graph Neural Network (GNN) performance, this paper argues that the issue is more complex, stemming from specific neighborhood distribution patterns.

The Challenge: Beyond Simple Heterophily

The authors identify two key hurdles that global heterophily metrics fail to capture: Inter-class Overlap, where normal and anomalous nodes share nearly identical neighborhood distributions, and Intra-class Dispersion, where nodes within the same class exhibit wildly different connection patterns.

Neighborhood distributions across four datasets showing overlap and dispersion.

As shown in the density plots above, datasets like YelpChi exhibit significant overlap, while T-Social demonstrates high dispersion. A static, global aggregation strategy cannot effectively distinguish nodes under these conditions.

Methodology: The NAAST-GNN Framework

To address these challenges, the authors propose NAAST-GNN (Neighborhood Adaptive Aggregation and Spectral Tuning). The model employs an iterative framework where classification probabilities from the previous epoch inform the current epoch's processing, creating a self-correcting mechanism.

The NAAST-GNN architecture featuring spatial adaptive aggregation and spectral tuning.

1. Neighborhood Adaptive Aggregation (Spatial Domain)

This module dynamically adjusts edge weights based on predicted labels. If a node is likely an anomaly, the model prioritizes messages from other predicted anomalies. Conversely, predicted normal nodes favor connections to their own kind. This targeted filtering helps resolve inter-class overlap by emphasizing class-relevant signals over noisy connections.

2. Spectral Tuning Module (Spectral Domain)

Recognizing that different nodes require different frequency components to be distinguishable, this module combines Low-Pass (LP) and High-Pass (HP) filters. LP filters capture smooth, homophilous signals, while HP filters capture sharp, heterophilous signals. The balance is determined by the node's local neighborhood distribution, allowing the model to handle intra-class dispersion effectively.

Evaluation and Key Results

NAAST-GNN was evaluated on four real-world benchmarks: YelpChi, Amazon, T-Finance, and the massive T-Social dataset (5.7 million nodes). The results demonstrate that NAAST-GNN consistently outperforms state-of-the-art baselines like BWGNN and CARE-GNN:

  • YelpChi: Achieved an 81.36% F1-Macro and 92.95% AUC, beating the best baseline by over 1%.
  • T-Social: On this massive scale, it showed a significant jump, outperforming baselines by 4.26% in F1-Macro.
  • Robustness: The model remains robust in label-scarce environments, outperforming competitors even when trained on only 1% of the data.

Conclusion

NAAST-GNN shifts the GAD paradigm from global heterophily metrics to local neighborhood distributions. By synergizing spatial adaptive aggregation and spectral tuning within an iterative framework, it effectively tackles the problems of overlap and dispersion. Future work includes extending this adaptive logic to dynamic graphs and exploring more complex polynomial filters for further spectral refinement.

Summary updated

BibTeX
@inproceedings{guo2025naast,
  author = {Ronghui Guo and Xiaowang Zhang and Zhizhi Yu and Minghui Zou and Sai Zhang and Zhiyong Feng},
  title = {{NAAST-GNN: Neighborhood Adaptive Aggregation and Spectral Tuning for Graph Anomaly Detection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/317},
}
Figure