Fast and Attributed Change Detection on Dynamic Graphs with Density of
  States
Shenyang Huang Jacob Danovitch Guillaume Rabusseau Reihaneh Rabbany
How can we detect traffic disturbances from international flight
transportation logs or changes to collaboration dynamics in academic networks?
These problems can be formulated as detecting anomalous change points in a
dynamic graph. Current solutions do not scale well to large real-world graphs,
lack robustness to large amounts of node additions/deletions, and overlook
changes in node attributes. To address these limitations, we propose a novel
spectral method: Scalable Change Point Detection (SCPD). SCPD generates an
embedding for each graph snapshot by efficiently approximating the distribution
of the Laplacian spectrum at each step. SCPD can also capture shifts in node
attributes by tracking correlations between attributes and eigenvectors.
Through extensive experiments using synthetic and real-world data, we show that
SCPD (a) achieves state-of-the art performance, (b) is significantly faster
than the state-of-the-art methods and can easily process millions of edges in a
few CPU minutes, (c) can effectively tackle a large quantity of node
attributes, additions or deletions and (d) discovers interesting events in
large real-world graphs. The code is publicly available at
https://github.com/shenyangHuang/SCPD.git