Training-free Graph Anomaly Detection: A Simple Approach via Singular Value Decomposition

Graph anomaly detection (GAD) is essential for identifying irregular behavior within graphs. Recent advances in GAD rely on deep learning techniques and have shown promise. However, prior deep learning-based GAD methods suffer from various limitations such as low accuracy, long training time, and limited scalability. To tackle these limitations, we propose TFGAD, a training-free graph anomaly detection approach. Our main idea is to process node attributes and local structures separately using distinct matrices, which are optimally determined via singular value decomposition, thus eliminating the need for additional training. For anomaly detection, we propose a lightweight scoring function that combines the reconstruction errors of node attributes with the projection lengths of local structures to quantify node abnormalities. Extensive experiments demonstrate that TFGAD significantly outperforms state-of-the-art deep learning-based baselines while reducing runtime and memory overhead. The results highlight TFGAD's potential as an effective and efficient solution for GAD, particularly in scenarios where computational resources are constrained.