# Multi-Community Spectral Clustering for Geometric Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 32 references that are in the map.
- First posted on arXiv 27 Jul 2025.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Community Detection on Euclidean Random Graphs](https://mlsanity.com/paper/1706.09942/) (2017)
- [The Geometric Block Model](https://mlsanity.com/paper/1709.05510/) (2017)
- [Higher-Order Spectral Clustering for Geometric Graphs](https://mlsanity.com/paper/2009.11353/) (2020)
- [Exact Community Recovery in the Geometric SBM](https://mlsanity.com/paper/2307.11196/) (2023)
- [Community Recovery in the Geometric Block Model](https://mlsanity.com/paper/2206.11303/) (2022)
- [Sharp exact recovery threshold for two-community Euclidean random graphs](https://mlsanity.com/paper/2501.14830/) (2025)

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

- [Spectral graph clustering with inhomogeneous latent geometry](https://mlsanity.com/paper/2608.11321/) (2026)

## Abstract (arXiv)

In this paper, we consider the soft geometric block model (SGBM) with a fixed number k ≥ 2 of homogeneous communities in the dense regime, and we introduce a spectral clustering algorithm for community recovery on graphs generated by this model. Given such a graph, the algorithm produces an embedding into ℝk-1 using the eigenvectors associated with the k-1 eigenvalues of the adjacency matrix of the graph that are closest to a value determined by the parameters of the model. It then applies k-means clustering to the embedding. We prove weak consistency and show that a simple local refinement step ensures strong consistency. A key ingredient is an application of a non-standard version of Davis-Kahan theorem to control eigenspace perturbations when eigenvalues are not simple. We also analyze the limiting spectrum of the adjacency matrix, using a combination of combinatorial and matrix techniques.