A Simple and Effective Method for Anomaly Detection on Attributed Graphs via Feature Consistency

Anomaly detection on attributed graphs aims to identify rare nodes that deviate significantly from the majority of nodes. Although recent graph self-supervised learning methods have demonstrated great potential, their complex training and detection schemes may lead to suboptimal efficiency and effectiveness. In this study, we propose a simple and effective anomaly detection method for attributed graphs, based on the intuition that normal nodes can retain strong consistency between their attributes and links when compared to abnormal nodes. Our method measures the underlying consistency between the attributes and links of each node by transforming them into a common subspace through subspace projection and alignment. The resulting consistency measure serves as an indicator for quantifying the abnormality of nodes. As a natural combination with minimal additional overhead, our method further exploits the reconstruction errors of node attributes resulting from subspace projection to formulate a more complete and powerful anomaly indicator. Despite its simplicity, the experimental results demonstrate that the proposed method can achieve competitive or superior performance in a fully unsupervised manner. Moreover, we extend our method using deep learning techniques, leading to significant improvements over state-of-the-art methods on benchmark attributed graph datasets.