# Robustness of spectral methods for community detection

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

## Key facts

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

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

- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [A simpler spectral approach for clustering in directed networks](https://mlsanity.com/paper/2102.03188/) (2021)
- [Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models](https://mlsanity.com/paper/2108.04729/) (2021)
- [SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search](https://mlsanity.com/paper/2506.03657/) (2025)

## Abstract (arXiv)

The present work is concerned with community detection. Specifically, we consider a random graph drawn according to the stochastic block model~: its vertex set is partitioned into blocks, or communities, and edges are placed randomly and independently of each other with probability depending only on the communities of their two endpoints. In this context, our aim is to recover the community labels better than by random guess, based only on the observation of the graph. In the sparse case, where edge probabilities are in O(1/n), we introduce a new spectral method based on the distance matrix D(l), where D(l)ij = 1 iff the graph distance between i and j, noted d(i, j) is equal to ℓ. We show that when ℓ ~ clog(n) for carefully chosen c, the eigenvectors associated to the largest eigenvalues of D(l) provide enough information to perform non-trivial community recovery with high probability, provided we are above the so-called Kesten-Stigum threshold. This yields an efficient algorithm for community detection, since computation of the matrix D(l) can be done in O(n1+kappa) operations for a small constant kappa. We then study the sensitivity of the eigendecomposition of D(l) when we allow an adversarial perturbation of the edges of G. We show that when the considered perturbation does not affect more than O(n^varepsilon) vertices for some small varepsilon > 0, the highest eigenvalues and their corresponding eigenvectors incur negligible perturbations, which allows us to still perform efficient recovery.