Towards Multiple Missing Values-resistant Unsupervised Graph Anomaly Detection

Abstract Unsupervised graph anomaly detection (GAD) has received increasing attention in recent years. It aims to identify anomalous data patterns using only unlabeled node information from graph-structured data. However, prevailing unsupervised GAD methods typically assume complete node attributes and structural information-a condition that is seldom satisfied in real-world scenarios due to privacy constraints, collection errors, or dynamic node arrivals. Standard imputation strategies risk "repairing" rare anomalous nodes so that they appear normal, thereby introducing imputation bias into the detection process. Moreover, when both node attributes and edges are missing simultaneously, estimation errors in one view can contaminate the other, causing cross-view interference that further degrades detection performance. To address these challenges, we propose M²V-UGAD, a multiple-missing-values-resistant unsupervised GAD framework for incomplete graphs. Specifically, we introduce a dual-pathway encoder that independently reconstructs missing node attributes and graph structure, preventing errors in one view from propagating to the other. The two pathways are then fused and regularized within a joint latent space such that normal nodes occupy a compact inner manifold while anomalies lie on an outer shell. Finally, to mitigate imputation bias, we sample latent codes just outside the normal region and decode them into realistic node features and subgraphs, yielding hard negative examples that sharpen the decision boundary. Experiments on seven public benchmarks show that M²V-UGAD consistently outperforms existing unsupervised GAD methods across a range of missing rates.