# Community Recovery in the Geometric Block Model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 53 references that are in the map.
- First posted on arXiv 22 Jun 2022.

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

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Memory in network flows and its effects on spreading dynamics and community detection](https://mlsanity.com/paper/1305.4807/) (2013)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [Recovering communities in the general stochastic block model without knowing the parameters](https://mlsanity.com/paper/1506.03729/) (2015)
- [Community Detection on Euclidean Random Graphs](https://mlsanity.com/paper/1706.09942/) (2017)
- [The Geometric Block Model](https://mlsanity.com/paper/1709.05510/) (2017)
- [Connectivity in Random Annulus Graphs and the Geometric Block Model](https://mlsanity.com/paper/1804.05013/) (2018)
- [Random geometric graphs with general connection functions](https://mlsanity.com/paper/1411.3617/) (2014)

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

- [Multi-Community Spectral Clustering for Geometric Graphs](https://mlsanity.com/paper/2508.00893/) (2025)
- [Spectral graph clustering with inhomogeneous latent geometry](https://mlsanity.com/paper/2608.11321/) (2026)

## Abstract (arXiv)

To capture the inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a Geometric Block Model. The geometric block model builds on the random geometric graphs (Gilbert, 1961), one of the basic models of random graphs for spatial networks, in the same way that the well-studied stochastic block model builds on the ErdHos-R'enyi random graphs. It is also a natural extension of random community models inspired by the recent theoretical and practical advancements in community detection. To analyze the geometric block model, we first provide new connectivity results for random annulus graphs which are generalizations of random geometric graphs. The connectivity properties of geometric graphs have been studied since their introduction, and analyzing them has been more difficult than their ErdHos-R'enyi counterparts due to correlated edge formation. We then use the connectivity results of random annulus graphs to provide necessary and sufficient conditions for efficient recovery of communities for the geometric block model. We show that a simple triangle-counting algorithm to detect communities in the geometric block model is near-optimal. For this we consider the following two regimes of graph density. In the regime where the average degree of the graph grows logarithmically with the number of vertices, we show that our algorithm performs extremely well, both theoretically and practically. In contrast, the triangle-counting algorithm is far from being optimum for the stochastic block model in the logarithmic degree regime. We simulate our results on both real and synthetic datasets to show superior performance of both the new model as well as our algorithm.