MEGAD: A Memory-Efficient Framework for Large-Scale Attributed Graph Anomaly Detection

Yifan Zhang, Haolong Xiang, Xiaolong Xu, Zishun Rui, Xiaoyong Li, Lianyong Qi, Fei Dai

Abstract

Graph Anomaly Detection (GAD) is critical for identifying malicious activities in complex networks. However, existing Graph Autoencoder (GAE) methods face significant scalability challenges due to the quadratic memory complexity of reconstructing full adjacency matrices. We present MEGAD, a memory-efficient framework that leverages node-level sampling and a weighted reconstruction strategy to achieve state-of-the-art performance on graphs with millions of nodes while maintaining a constant memory footprint.

Introduction

Graph Anomaly Detection (GAD) is essential for identifying fraud, network intrusions, and system failures in domains ranging from social networks to financial systems. Modern deep learning approaches, particularly Graph Autoencoders (GAEs), have become the standard due to their ability to capture both structural relationships and node attributes.

However, GAEs suffer from a major scalability bottleneck: the "memory wall." Standard GAEs attempt to reconstruct the entire $N \times N$ adjacency matrix. For a graph with a million nodes, this matrix contains a trillion entries, far exceeding the VRAM capacity of modern GPUs. While subgraph sampling is often used to mitigate this, it frequently results in "lossy" representations that degrade detection accuracy. MEGAD addresses this by introducing a node-level reconstruction strategy that preserves precision without the massive memory overhead.

The MEGAD Framework

MEGAD decomposes the anomaly detection process into three modular stages: pre-training, training, and testing.

The MEGAD framework overview, detailing the three-stage process: Pre-training for initial embeddings, Training with node-level reconstruction and distribution diffusion, and Testing using a forest-based detector.

1. Pre-training

The process begins by generating initial node embeddings using flexible algorithms like node2vec. This provides a structural baseline for the subsequent refinement stages.

2. Training: Node-Level Reconstruction and Distribution Diffusion

Instead of reconstructing the full graph, MEGAD employs two innovative loss functions:

  • Node-level Reconstruction: The model samples specific edges and their 1-hop and 2-hop neighborhoods. It introduces a Weight Coefficient ($\alpha$) to handle the "noise" inherent in anomalies. By calculating node similarity, the model down-weights outliers during training, preventing them from corrupting the learned representation of "normal" behavior.
  • Distribution Diffusion: This step refines embeddings to enhance separability in the latent space. A shallow regression model identifies the most informative dimensions of the embedding, optimizing the latent space for the final detector.

3. Testing

The refined embeddings are passed to LSHiForest (Locality Sensitive Hashing Isolation Forest). This ensemble-based model is highly efficient at identifying outliers in high-dimensional spaces, providing the final anomaly scores.

Experimental Evaluation

MEGAD was evaluated across six datasets, ranging from small-scale (Disney, 124 nodes) to ultra-large-scale (DGraph, 3.7 million nodes).

Key Results

  • Memory Stability: While competing methods like DOMINANT and GAAN encountered Out-of-Memory (OOM) errors on large datasets, MEGAD maintained a stable memory footprint of approximately 3GB, regardless of graph size.
  • Detection Accuracy: On the Weibo dataset, MEGAD achieved an AUC-ROC of 95.0%, significantly outperforming the next best deep learning method (91.9%).
  • Scalability: On the 3.7-million-node DGraph financial dataset, MEGAD was one of the few frameworks capable of completion, achieving a 58.9% AUC-ROC while others either crashed or exceeded 24-hour time limits.
Visualization of node distribution and the similarity matrix. The separation between the normal cluster (blue) and outliers (red) demonstrates the effectiveness of the embedding refinement process.

Discussion and Conclusion

MEGAD demonstrates that the "memory wall" in graph learning is optional. By decoupling embedding learning from anomaly scoring and using batched, edge-centric reconstruction, the framework achieves high precision with minimal VRAM. The introduction of the $\alpha$ coefficient allows the model to self-correct, ensuring that outliers do not skew the definition of normality.

Future work may involve integrating Large Language Models (LLMs) to better interpret complex node attributes, such as text descriptions, further enhancing detection capabilities in attribute-rich environments. While MEGAD introduces new hyperparameters that require tuning, its ability to handle multi-million node graphs makes it a robust solution for real-world, large-scale applications.

Summary updated

Abstract

Graph anomaly detection (GAD), with its ability to accurately identify anomalous patterns in graph data, plays a vital role in areas such as network security, social media platforms, and fraud detection. Graph autoencoder-based methods are widely used for GAD due to their efficiency and effectiveness in capturing complex patterns and learning meaningful representations. However, the above methods are constrained by hardware memory, hindering the detection for large-scale graph data. In this paper, we propose a Memory-Efficient framework for large-scale attributed Graph Anomaly Detection (MEGAD). Specifically, MEGAD first generates node embeddings and then refines them through a lightweight joint optimization model, ensuring minimal memory overhead. The optimized embeddings are subsequently fed into a detector to compute anomaly scores. Extensive experiments demonstrate that our framework achieves comparable accuracy to state-of-the-art methods across multiple datasets while significantly reducing memory consumption on large-scale graphs.
BibTeX
@inproceedings{zhang2025megad,
  author = {Yifan Zhang and Haolong Xiang and Xiaolong Xu and Zishun Rui and Xiaoyong Li and Lianyong Qi and Fei Dai},
  title = {{MEGAD: A Memory-Efficient Framework for Large-Scale Attributed Graph Anomaly Detection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/406},
}
Figure