Multi-Level Anomaly Detection on Time-Varying Graph Data
  This work presents a novel modeling and analysis framework for graph
sequences which addresses the challenge of detecting and contextualizing
anomalies in labelled, streaming graph data. We introduce 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.
Specifically, probability models describing coarse subgraphs are built by
aggregating probabilities at finer levels, and these closely related
hierarchical models simultaneously detect deviations from expectation. 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 greater than 0.786.
