Graph Anomaly Detection Based on Steiner Connectivity and Density

Detecting “hotspots” and “anomalies” is a recurring problem with a wide range of applications, such as social network analysis, epidemiology, finance, and biosurveillance, among others. Networks are a common abstraction in these applications for representing complex relationships. Typically, these networks are dynamic-, i.e., they evolve over time. A number of methods have been proposed for anomaly detection in such dynamic network data sets, which are primarily based on changes in network properties. We provide a survey of the various formulations of anomaly detection in dynamic networks with a focus on “window-based” methods. Window-based methods first define a time window of past network snapshots to model normal behavior and then mark a snapshot as anomalous if it has significantly different patterns from those observed in the time window. We describe two classes of techniques: 1) generalizations of Steiner connectivity; and 2) dense subgraph mining. Both have been used extensively in window-based graph anomaly detection. We summarize the key problem formulations that have been studied using these approaches, and we describe details of some of the main techniques.