Two-stage anomaly detection algorithm via dynamic community evolution in temporal graph

摘要

Detecting anomalies from a massive amount of user behavioral data is often liken to finding a needle in a haystack. While tremendous efforts have been devoted to anomaly detection from temporal graphs, existing studies rarely consider community evolution and evolutionary paths simultaneously, and analyze those characteristics for the purpose of anomaly detection. Therefore, we propose a two-stage anomaly detection (TSAD) framework to detect anomalies. In this study, we suggest detecting the community evolution events from a sequence of snapshot graphs by constructing an evolution bipartite graph and designing community similarity scores. We then propose a novel anomaly detection method combining community evolution-based anomaly detection and evolutionary path-based anomaly detection. An anomalous score is designed to detect anomalous community evolution events by extracting the characteristics of evolution communities in the community evolution-based anomaly detection method. Moreover, to reduce the false alarm rate, we propose evolutionary path-based anomaly detection to further detect the abnormality of the identified normal evolutionary paths by extracting the characteristics of the identified anomalous evolutionary paths based on community evolution-based anomaly detection. We conduct extensive experiments on real-world datasets and demonstrate that TSAD consistently outperforms competitive baseline methods in anomaly detection.