This project develops a multi-scale anomaly detection algorithm for time-varying graph data. More specifically, it is implicitly assumed that the local topology of the sequence of graphs is relatively stable, and a novel technique detects changes in the local topology at the whole graph and node level. This workflow can accommodate multiple node types and edge types (colorings) as well as directed graphs.
As an example application, network flow data is naturally represented as a time-varying sequence of graphs with nodes representing IPs and colored, directed edges encoding flows. Anomalous bittorrent traffic and ip-scanning traffic is identified with 100% true-positive rate and false positive rate bounded by 2.85%.