Subgraph Centralization: A Necessary Step for Graph Anomaly Detection
This work addresses inefficiencies in graph anomaly detection for researchers and practitioners, offering a generic framework that improves performance, though it is incremental as it builds on existing methods.
The paper tackles the problem of graph anomaly detection by identifying subgraph treatment as a root cause of weaknesses like high computational cost and low accuracy, and proposes Subgraph Centralization to address these issues, resulting in a new framework (GCAD) that achieves better accuracy with linear time complexity.
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.