Analytical Models and Methods for Anomaly Detection in Dynamic, Attributed Graphs

When working with large-scale network data, the interconnected entities often have additional descriptive information. The additional metadata may provide insight that can be exploited for detection of anomalous events. This chapter provides an overview of anomaly detection techniques in dynamic, attributed graphs, with a specific focus on detection within backgrounds based on random graph models. This kind of analysis can be applied for a variety of background models, including those with dynamic topologies and where vertices and edges have attributes. A spectral framework for anomalous subgraph detection in random background models is described in detail, including an implementation in R that exploits structure in the random graph models for computationally tractable analysis of graph residuals. Detection results, both in simulation and in real data, demonstrate the power of this approach and the advantage of accounting for dynamics and attributes when analyzing graph data.