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.
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.
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