An Efficient Framework for Detecting Evolving Anomalous Subgraphs in Dynamic Networks

Evolving anomalous subgraphs detection in dynamic networks is an important and challenging problem that has arisen in multiple applications and is NP-hard in general. The evolving characteristic makes most existing methods incapable to tackle this problem effectively and efficiently, as it involves huge search spaces and continuous changes of evolving connected subgraphs, especially when the data are free of distributions. This paper presents a generic efficient framework, namely dynamic evolving anomalous subgraphs scanning (dGraphScan), to address this problem. We generalize traditional nonparametric scan statistics, and propose a large class of scan statistic functions for measuring the significance of evolving subgraphs in dynamic networks. Furthermore, we make a number of computational studies to optimize this large class of nonparametric scan statistic functions. Specifically, we first decompose each scan statistic function as a sequence of subproblems with provable guarantees, and then propose efficient approximation algorithms for tackling each subproblem, while analyzing their theoretical properties and providing rigorous approximation guarantees. Extensive experiments on three real-world datasets demonstrate that our general framework performs superior over state-of-the-art methods.