Research map / Learning theory and algorithms / Clustering
Dynamic Spectral Clustering with Provable Approximation Guarantee
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a dynamic spectral clustering algorithm for evolving graphs with edge and vertex insertions that maintains a cluster-preserving sparsifier and a contracted super-vertex graph, giving provable conductance guarantees with O(1) amortised update and sublinear query time.
Problem
Clustering dynamically evolving graphs where edges and vertices are inserted and the number of clusters can change, with provable approximation guarantees and fast updates and queries.
Approach
Dynamically maintain a degree-proportional sampled sparsifier (resampling edges when endpoint degrees change significantly) and a small contracted graph of super-vertices for the current clusters, so spectral clustering on the contracted graph reveals new cluster structure in sublinear query time.
Key results
- On SBM with 300,000 vertices and up to 490M edges, the algorithm runs over 100 times faster than repeated spectral clustering with comparable clustering quality (per abstract).
- On the synthetic dynamic SBM, spectral clustering on the contracted graph takes less than 1 second versus about 100 seconds on the full graph G_T, with ARI close to optimal.
- Spectral gaps of the contracted graph track those of the full graph within a comparable range across time steps in the reported tables.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the dynamically updated contracted graph instead of clustering the full graph | Dynamic spectral clustering · Dynamic SBM, increasing clusters | runtime: around 100 seconds -> less than 1 second | Helped |
| Use the dynamically updated contracted graph instead of clustering the full graph | Dynamic spectral clustering · Dynamic SBM, increasing clusters | ARI | Hurt |
| Use the dynamically updated contracted graph instead of clustering G_T or H_T | Dynamic spectral clustering · Dynamic SBM, decreasing clusters | runtime | Helped |
| Use the dynamically updated contracted graph instead of clustering G_T or H_T | Dynamic spectral clustering · Dynamic SBM, decreasing clusters | ARI | No clear effect |
| Use dynamic sparsifiers and contracted graphs rather than repeated spectral clustering | Dynamic spectral clustering · MNIST and EMNIST dynamic clustering | runtime | Helped |
| Use dynamic sparsifiers and contracted graphs rather than repeated spectral clustering | Dynamic spectral clustering · MNIST and EMNIST dynamic clustering | ARI | No clear effect |
Limitations
- Theoretical guarantees require strong assumptions: lambda_{k+1} = Omega(1) and low k-way expansion with polylog factors at every query time.
- Experiments are on a single-machine Python implementation with modest real-world datasets (MNIST, EMNIST).
- Requires a number of new edges per step bounded by polylog and polynomial total edge count, limiting the regime of analysis.
Experimental setup
Datasets: synthetic stochastic block model graphs MNIST EMNIST letters
Benchmarks: synthetic dynamic SBM MNIST kNN graph EMNIST letters kNN graph
Metrics: Adjusted Rand Index running time spectral gap ratio
Baselines: spectral clustering on full graph G_T spectral clustering on sparsifier H_T
Builds on: spectral clustering (Peng et al.) SZ cluster-preserving sparsifier (Spielman-Srivastava style) higher-order Cheeger inequality
Closest papers by meaning
- Fast Approximate Spectral Clustering for Dynamic Networks (ICML 2018 · similarity 0.93)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.90)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.89)
- Sparse-pivot: Dynamic correlation clustering for node insertions (ICML 2025 · similarity 0.88)
- Dynamic Similarity Graph Construction with Kernel Density Estimation (ICML 2025 · similarity 0.86)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.