Community detection and stochastic block models: recent developments

By Emmanuel Abbe. Foundations and Trends in Communications and Information Theory, 2017

1,389 citations recorded by the source corpus.

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences. This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds. The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

Subfields: Computer Science Applications, Epidemiology, Transportation

View Paper: https://www.semanticscholar.org/paper/98c5afa2c7a3130ed0788aa1d5be1d62a9b10eca

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Science Applications

In Epidemiology

In Transportation

Citations in the corpus

Structure-Aware Transformer for Graph Representation Learning (2022, methodology): “PATTERN and CLUSTER Dwivedi et al. (2020) are synthetic datasets that were created using Stochastic Block Models (Abbe, 2018).”
A Generalization of Transformer Networks to Graphs (2020, methodology): “2012), PATTERN and CLUSTER (Abbe 2017) from a recent GNN benchmark (Dwivedi et al.”
Residual Gated Graph ConvNets (2017, neutral): “Identifying Abbe (2017).”
A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks (2017, background): “An active research area in Theoretical Computer Science and Statistics is to understand the interplay between those statistical and computational detection thresholds; see [1] and references therein for an instance of this program in the community detection problem, or [3; 8; 5] for examples of stat”
Community Detection with Graph Neural Networks (2017, methodology): “…regime; spectral approaches using the Laplacian in its various (un)normalized forms and the adjacency matrix, as well as SDP methods cannot detect communities in this regime(Abbe, 2017) due to large ﬂuctuations in the degree distribution that prevent eigenvectors form concentrating on the clusters.”
A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning (2021, background): “, evolutionary computation [39], statistical inference [40] or deep learning [41].”
Supervised Community Detection with Line Graph Neural Networks (2017, methodology): “For k = 2, it has been shown that when SNR < 1, detection is not solvable, and therefore SNR = 1 is both the computational and the information theoretic threshold (Abbe, 2017).”
Adaptive Universal Generalized PageRank Graph Neural Network (2020, background): “One possible alternative for the homophily measure is the Chernoff-Hellinger divergence Abbe (2017) of the empirical edge probability matrix B; here Bij is the empirical probability of an edge with one end node labeled i and the other labeled j.”
Gradient Coding Using the Stochastic Block Model (2018, background): “However, the converse does not necessarily hold [13].”
Rethinking Graph Neural Architecture Search from Message-passing (2021, methodology): “PATTERN [5] and CLUSTER [5] are node classiﬁcation tasks generated via Stochastic Block Models [1], which are used to model communities in social networks by modulating the intra-and extra-communities connections.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Finally, the spectral method has been applied to many other problems beyond the ones discussed here, including but not limited to community detection [133], [134], phase synchronization [9], joint alignment [11], ranking from pairwise comparisons [72], [135], [136], tensor estimation [137]–[140].”
Benchmarking Graph Neural Networks (2023, methodology): “The pattern and embedded graphs are generated with the stochastic block model (SBM) (Abbe, 2017).”
Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss (2021, background): “The eigenvalue problems are closely related to graph partitioning as shown in spectral graph theory (Chung and Graham, 1997) for both worst-case graphs (Cheeger, 1969, Kannan et al., 2004, Lee et al., 2014, Louis et al., 2011) and random graphs (Abbe, 2017, Lei et al., 2015, McSherry, 2001).”