# Robustness of Community Detection to Random Geometric Perturbations

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

## Key facts

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

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

- [Robustness of shallow graph embedding methods for community detection](https://mlsanity.com/paper/2405.00636/) (2024)
- [Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models](https://mlsanity.com/paper/2108.04729/) (2021)

## Abstract (arXiv)

We consider the stochastic block model where connection between vertices is perturbed by some latent (and unobserved) random geometric graph. The objective is to prove that spectral methods are robust to this type of noise, even if they are agnostic to the presence (or not) of the random graph. We provide explicit regimes where the second eigenvector of the adjacency matrix is highly correlated to the true community vector (and therefore when weak/exact recovery is possible). This is possible thanks to a detailed analysis of the spectrum of the latent random graph, of its own interest.