Subgraph centralization: A necessary step for graph anomaly detection

• Main Authors: ZHUANG, Zhong, TING, Kai Ming, PANG, Guansong, SONG, Shuaibin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Databases and Information Systems; Graphics and Human Computer Interfaces
• Online Access: https://ink.library.smu.edu.sg/sis_research/8006; https://ink.library.smu.edu.sg/context/sis_research/article/9009/viewcontent/1.9781611977653.ch79.pdf
• Institution: Singapore Management University

Abstract Graph anomaly detection has attracted a lot of interest recently. Despite their successes, existing detectors have at least two of the three weaknesses: (a) high computational cost which limits them to small-scale networks only; (b) existing treatment of subgraphs produces suboptimal detection accuracy; and (c) unable to provide an explanation as to why a node is anomalous, once it is identified. We identify that the root cause of these weaknesses is a lack of a proper treatment for subgraphs. A treatment called Subgraph Centralization for graph anomaly detection is proposed to address all the above weaknesses. Its importance is shown in two ways. First, we present a simple yet effective new framework called Graph-Centric Anomaly Detection (GCAD). The key advantages of GCAD over existing detectors including deep-learning detectors are: (i) better anomaly detection accuracy; (ii) linear time complexity with respect to the number of nodes; and (iii) it is a generic framework that admits an existing point anomaly detector to be used to detect node anomalies in a network. Second, we show that Subgraph Centralization can be incorporated into two existing detectors to overcome the above-mentioned weaknesses.