# Fast and Attributed Change Detection on Dynamic Graphs with Density of States

arXiv: https://arxiv.org/abs/2305.08750 · HTML: https://mlsanity.com/paper/2305.08750/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 15 May 2023.

## Builds on (most cited first, 8 of 8)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Laplacian Change Point Detection for Dynamic Graphs](https://mlsanity.com/paper/2007.01229/) (2020)
- [Detecting change points in the large-scale structure of evolving networks](https://mlsanity.com/paper/1403.0989/) (2014)
- [Network Density of States](https://mlsanity.com/paper/1905.09758/) (2019)
- [Fast Change Point Detection on Dynamic Social Networks](https://mlsanity.com/paper/1705.07325/) (2017)
- [Fast Attributed Graph Embedding via Density of States](https://mlsanity.com/paper/2110.05228/) (2021)
- [Density of States Graph Kernels](https://mlsanity.com/paper/2010.11341/) (2020)

## Built on by (most cited first, 1 of 1)

- [Hallucination Detox: Sensitivity Dropout (SenD) for Large Language Model Training](https://mlsanity.com/paper/2410.15460/) (2024)

## Abstract (arXiv)

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