Hop-Count Based Self-supervised Anomaly Detection on Attributed Networks

A number of approaches for anomaly detection on attributed networks have been proposed. However, most of them suffer from two major limitations: (1) they rely on unsupervised approaches which are intrinsically less effective due to the lack of supervisory signals of what information is relevant for capturing anomalies, and (2) they rely only on using local, e.g., one- or two-hop away node neighbourhood information, but ignore the more global context. Since anomalous nodes differ from normal nodes in structures and attributes, it is intuitive that the distance between anomalous nodes and their neighbors should be larger than that between normal nodes and their (also normal) neighbors if we remove the edges connecting anomalous and normal nodes. Thus, estimating hop counts based on both global and local contextual information can help us to construct an anomaly indicator. Following this intuition, we propose a hop-count based model (HCM) that achieves that. Our approach includes two important learning components: (1) Self-supervised learning task of predicting the shortest path length between a pair of nodes, and (2) Bayesian learning to train HCM for capturing uncertainty in learned parameters and avoiding overfitting. Extensive experiments on real-world attributed networks demonstrate that HCM consistently outperforms state-of-the-art approaches.