Can Edge Addition Be Safe and Effective? Adjacency-Centered Augmentation via Langevin and SDE Diffusion for Self-Supervised Graph Anomaly Detection

Abstract

Edge addition is commonly considered risky in Graph Anomaly Detection (GAD), as random edge addition may induce anomaly–normal connectivity. Consequently, most existing augmentation strategies focus on feature perturbation, edge removal, or subgraph sampling, leaving edge addition largely unexplored. In contrast, we empirically find that moderate and targeted structural completion among normal nodes consistently improves GAD performance, revealing guided edge addition as an overlooked yet effective augmentation dimension. Motivated by this observation, we introduce two adjacency-centered edge generation strategies with complementary mechanisms. One performs a training-free structural completion scheme via spectrum-aware Langevin dynamics, enriching graph connectivity while preserving node features. The other models the joint evolution of node features and graph structure through a stochastic differential equation–based diffusion process, producing structurally coherent and anomaly-aware complementary graphs. Extensive experiments on 12 benchmark datasets with 7 state-of-the-art GAD models demonstrate consistent and substantial improvements in both AUROC and AUPRC. Code and appendices are available at https://github.com/GaoHaokai222/LangGen-JointSDE