Community Recovery in the Geometric Block Model

Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, Barna Saha

Abstract

To capture 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 (GBM). The geometric block model builds on the random geometric graphs in the same way that the well-studied stochastic block model (SBM) builds on the Erdős-Rényi random graphs. We provide new connectivity results for random annulus graphs to provide necessary and sufficient conditions for efficient recovery of communities. We show that a simple triangle-counting algorithm to detect communities in the geometric block model is near-optimal. In the regime where the average degree of the graph grows logarithmically with the number of vertices, our algorithm performs extremely well, both theoretically and practically. We also show that in the linear degree regime, our algorithm needs to store only $O(n \log n)$ edges to recover the latent communities.

Introduction: Beyond the Stochastic Block Model

For decades, the Stochastic Block Model (SBM) has been the "gold standard" for studying community detection. In an SBM, edges between nodes are formed independently based on whether they belong to the same community. However, real-world networks—social, biological, or technological—rarely behave this way. They exhibit transitivity: the real-world tendency for friends of friends to be friends.

The SBM fails to capture this "triangle-heavy" nature because of its edge-independence assumption. Furthermore, many popular algorithms designed for the SBM, such as spectral clustering, do not explicitly utilize these local motifs and can struggle in "sparse" regimes where the average number of connections per node is low (logarithmic relative to the total number of nodes). We propose the Geometric Block Model (GBM) to naturally incorporate geometry and proximity, better reflecting the transitivity of real-world data.

The Geometric Block Model (GBM)

In the GBM, nodes are assigned random positions on a $t$-dimensional sphere. An edge exists between two nodes if their geometric distance is below a certain threshold. To create communities, the threshold for nodes in the same community ($r_s$) is larger than the threshold for nodes in different communities ($r_d$).

To analyze this, we introduce and solve connectivity problems for Random Annulus Graphs (RAG)—a generalization of random geometric graphs where edges form only if the distance between nodes falls within a specific "ring" or annulus. Our theoretical contribution proves that even if "short" edges are deleted, the "long" edges in a geometric graph are often sufficient to keep the community connected—a vital insight for our recovery algorithm.

The Triangle-Counting Algorithm

The core of our approach is a simple, scalable triangle-counting algorithm. For every edge in the graph, the algorithm counts how many common neighbors the two endpoints share. In the GBM, the number of triangles an edge belongs to is a highly informative feature.

Figure 3: Distribution of common neighbors for intra-community edges (blue) versus inter-community edges (green). The clear separation in triangle counts allows the algorithm to effectively filter the graph.

In the sparse regime, an edge in the same community will belong to significantly more triangles than an edge connecting two different communities. The algorithm retains edges with high triangle counts and identifies the connected components of the remaining graph to reveal the communities.

Empirical Results and Datasets

We validated the GBM and the algorithm using both synthetic and real-world datasets, including Amazon product metadata, DBLP, and US political blogs.

Figure 1: Distribution of the average number of similar categories in the Amazon product metadata dataset, illustrating the underlying similarity structure that geometric models aim to capture.

Key results include:

  • Near-Optimal Recovery: Our triangle-counting approach is near-optimal in terms of the required graph density.
  • Superior Performance: On the Political Blogs dataset, the algorithm achieved 78.8% accuracy, significantly outperforming spectral clustering (53%).
  • Scalability: The algorithm is highly parallelizable and faster than spectral methods for large datasets. In the linear degree regime, it needs to store only $O(n \log n)$ edges to recover latent communities.
  • SBM vs. GBM Divergence: In the sparse regime, the SBM has very few triangles ($O(\log^3 n)$), making triangle-counting useless. In contrast, the GBM is "triangle-rich" ($O(n \log^2 n)$), which is why our algorithm excels where SBM-based methods fail.

Conclusion

The Geometric Block Model offers a powerful alternative to the SBM by explicitly accounting for the geometric nature of real-world networks. By leveraging local motifs like triangles, we provide a scalable and near-optimal solution for community recovery. Future work will explore non-uniform latent spaces and blind recovery where model parameters are unknown.

Summary updated

Abstract

To capture inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a \emph{Geometric Block Model}. The geometric block model builds on the \emph{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 Erd\H{o}s-R\'{en}yi 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 \emph{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 difficult 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 two regimes of graph density. In the regime where the average degree of the graph grows logarithmically with 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 also look at the regime where the average degree of the graph grows linearly with the number of vertices $n$, and hence to store the graph one needs $\Theta(n^2)$ memory. We show that our algorithm needs to store only $O(n \log n)$ edges in this regime to recover the latent communities.
BibTeX
@article{galhotra2023community,
  author = {Sainyam Galhotra and Arya Mazumdar and Soumyabrata Pal and Barna Saha},
  title = {{Community Recovery in the Geometric Block Model}},
  journal = {J. Mach. Learn. Res.},
  year = {2023},
  url = {https://openreview.net/forum?id=xQt9DHxBHp},
}
Figure