# Dynamic Spectral Clustering with Provable Approximation Guarantee

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 19 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds](https://mlsanity.com/paper/2111.03980/) (2021)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (2017)
- [Expander Decomposition and Pruning: Faster, Stronger, and Simpler](https://mlsanity.com/paper/1812.08958/) (2018)
- [Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary](https://mlsanity.com/paper/2004.08432/) (2020)
- [Efficient Eigen-updating for Spectral Graph Clustering](https://mlsanity.com/paper/1301.1318/) (2013)
- [Fast Approximate Spectral Clustering for Dynamic Networks](https://mlsanity.com/paper/1706.03591/) (2017)

## Abstract (arXiv)

This paper studies clustering algorithms for dynamically evolving graphs Gt, in which new edges (and potential new vertices) are added into a graph, and the underlying cluster structure of the graph can gradually change. The paper proves that, under some mild condition on the cluster-structure, the clusters of the final graph GT of nT vertices at time T can be well approximated by a dynamic variant of the spectral clustering algorithm. The algorithm runs in amortised update time O(1) and query time o(nT). Experimental studies on both synthetic and real-world datasets further confirm the practicality of our designed algorithm.