# Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2020.

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

- [FedGCN: Convergence-Communication Tradeoffs in Federated Training of Graph Convolutional Networks](https://mlsanity.com/paper/2201.12433/) (2022)
- [Spectral embedding for dynamic networks with stability guarantees](https://mlsanity.com/paper/2106.01282/) (2021)
- [Entropic Optimal Transport in Random Graphs](https://mlsanity.com/paper/2201.03949/) (2022)
- [Interferometric Graph Transform for Community Labeling](https://mlsanity.com/paper/2106.05875/) (2021)
- [Nonparametric estimation of time-varying network connections by multi-stage smoothing](https://mlsanity.com/paper/2605.06862/) (2026)
- [When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors](https://mlsanity.com/paper/2610.13765/) (2026)

## Abstract (arXiv)

In this paper, we analyse classical variants of the Spectral Clustering (SC) algorithm in the Dynamic Stochastic Block Model (DSBM). Existing results show that, in the relatively sparse case where the expected degree grows logarithmically with the number of nodes, guarantees in the static case can be extended to the dynamic case and yield improved error bounds when the DSBM is sufficiently smooth in time, that is, the communities do not change too much between two time steps. We improve over these results by drawing a new link between the sparsity and the smoothness of the DSBM: the more regular the DSBM is, the more sparse it can be, while still guaranteeing consistent recovery. In particular, a mild condition on the smoothness allows to treat the sparse case with bounded degree. We also extend these guarantees to the normalized Laplacian, and as a by-product of our analysis, we obtain to our knowledge the best spectral concentration bound available for the normalized Laplacian of matrices with independent Bernoulli entries.