Hybrid-Order Anomaly Detection on Attributed Networks

Anomaly detection on attributed networks has received an increasing amount of attention in recent years. Despite the success, most of the existing methods only focus on detecting the abnormal nodes while fail to detect the abnormal subgraphs. In this paper, we define a new problem of hybrid-order anomaly detection on attributed networks, which aims to detect both of the abnormal nodes and subgraphs. To this end, a new deep learning model called Hybrid-Order Graph Attention Network (HO-GAT) is developed, which is able to simultaneously detect the abnormal nodes and motif instances in an attributed network. In order to model the mutual influence between nodes and motif instances, the learning procedures of the node representation and the motif instance representation are integrated into a unified graph attention network with a novel hybrid-order self-attention mechanism. After learning the node representation and the motif instance representation, two decoders are respectively designed to reconstruct the attribute information of the nodes and motif instances, and the hybrid-order topological structure among nodes and motif instances. And finally, the reconstruction errors are utilized as the abnormal score of nodes and motif instances respectively. Extensive experiments conducted on real-world datasets have confirmed the effectiveness of the HO-GAT method.