Statistically Inspired Discrepancy Detection for Anomalous Spatio-Temporal Graphs

Abstract Anomaly detection in dynamic graphs is a critical topic with applications in many fields, such as fraud detection and network security. This paper tackles the difficulties in locating abnormalities in time-varying graphs by presenting a novel divide-and-conquer method. We combine Graph Convolutional Networks (GCN) and Recurrent Neural Networks (RNN) to predict future node values on temporal graphs, followed by a macro and micro-level analysis. At the macro level, we present a novel algorithm to extract correlation-based subgraphs. The values obtained for each subgraph allow us to concentrate on subgraphs that show significant anomalies, effectively minimizing the challenges in node-level anomaly detection. This is followed by a micro-level analysis of the node contributions and temporal properties within the identified anomalous subgraphs. By combining macro and micro-level analysis with a machine learning-based approach, our method provides an efficient approach for zoning in on anomalies, significantly speeding up computation.