Can Edge Addition Be Safe and Effective? Adjacency-Centered Augmentation via Langevin and SDE Diffusion for Self-Supervised Graph Anomaly Detection
Can Edge Addition Be Safe and Effective? Adjacency-Centered Augmentation via Langevin and SDE Diffusion for Self-Supervised Graph Anomaly Detection
Haokai Gao, Menghua Jiang, Xuantao Yang, Jiale Liu, Yubin Li, Yuncheng Jiang
Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence
Main Track. Pages 2626-2634.
https://doi.org/10.24963/ijcai.2026/292
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
Keywords:
Data Mining: Anomaly/outlier detection
Data Mining: Mining graphs
Machine Learning: Self-supervised Learning
