Abstract
This work presents a modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in streaming graph data. Our goal is to detect changes at multiple levels of granularity, thereby identifying specific nodes and subgraphs causing a graph to appear anomalously. In particular, the framework detects changes in community membership, density, and node degree in a sequence of graphs where these are relatively stable. In route to this end, we introduce a new graph model, a generalization of the BTER model of Seshadhri et al., by adding flexibility to community structure, and use this model to perform multi-scale graph anomaly detection. This technique provides insight into a graph’s structure and internal context that may shed light on a detected event. Additionally, this multi-scale analysis facilitates intuitive visualizations by allowing users to narrow focus from an anomalous graph to particular subgraphs or nodes causing the anomaly. For evaluation, two hierarchical anomaly detectors are tested against a baseline Gaussian method on a series of sampled graphs. We demonstrate that our graph statistics-based approach outperforms both a distribution-based detector and the baseline in a labeled setting with community structure, and it accurately detects anomalies in synthetic and real-world datasets at the node, subgraph, and graph levels. To illustrate the accessibility of information made possible via this technique, the anomaly detector and an associated interactive visualization tool are tested on NCAA football data, where teams and conferences that moved within the league are identified with perfect recall, and precision >0.786.
Original language | English |
---|---|
Article number | 99 |
Journal | Social Network Analysis and Mining |
Volume | 6 |
Issue number | 1 |
DOIs | |
State | Published - Dec 1 2016 |
Funding
This manuscript has been authored in part by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan ( http://energy.gov/downloads/doe-public-access-plan ). Blair D. Sullivan supported in part by DARPA GRAPHS/SPAWAR Grant N66001-14-1-4063, the Gordon and Betty Moore Foundation, and the National Consortium for Data Science. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of DOE, DARPA, SSC Pacific, the Moore Foundation, or the NCDS.
Keywords
- Anomaly detection
- Graph sequence
- Visualization