Multi-Level Anomaly Detection on Streaming Graph Data.
Robert A. Bridges, John P. Collins, Erik M. Ferragut, Jason A. Laska, Blair D. Sullivan · arXiv (Cornell University) · 2014
As a natural structure for representing entities and in-teractions, graphs are commonly used in many domains. Because of inherent complexity, converting graph data to meaningful information through analysis or visual-ization is often challenging. Identifying patterns and aberrations in graph data can pinpoint areas of inter-est, provide context for deeper understanding, and en-able discovery in many applications. This work presents a novel modeling and analysis framework for graph sequences. The framework ad-dresses the issues of modeling, detecting anomalies at multiple scales, and enabling understanding of graph data. A new graph model, generalizing the BTER model of Seshadhri et al. by adding flexibility to com-munity structure, is introduced and used to perform multi-scale graph anomaly detection. Specifically, prob-ability models describing coarse subgraphs are built by aggregating probabilities at finer levels, and these closely related hierarchical models simultaneously de-tect deviations from expectation. This technique pro-vides insight into the graph’s structure and internal con-text that may shed light on a detected event. Addition-ally, this multi-scale analysis facilitates intuitive visu-alizations by allowing users to narrow focus from an anomalous graph to particular subgraphs causing the anomaly. For evaluation, two hierarchical anomaly de-tectors are tested against a baseline on a series of sam-pled graphs. The superior hierarchical detector outper-forms the baseline, and changes in community struc-ture are accurately detected at the node, subgraph, and graph levels. To illustrate the accessibility of informa-tion made possible via this technique, a prototype vi-sualization tool, informed by the multi-scale analysis is tested on NCAA football data. Teams and confer-ences exhibiting changes in membership are identified with greater than 92 % precision and recall. Screenshots of an interactive visualization, allowing users to probe into selected communities, are given.