Stochastic Block Model

Follow this topic Ask about this topic

Stochastic block models study how to infer hidden communities from network edges, and provide a testbed for understanding when network structure is detectable. Common approaches include spectral and non-backtracking algorithms, belief propagation, likelihood-based inference, and extensions for directed, multilayer, temporal, or hypergraph data. Researchers evaluate these methods on sparse graphs and study tasks such as weak or exact recovery, estimating the number of communities, and using limited queries to improve labels. Recovery thresholds are understood in many settings, but an important tension remains between what is statistically possible and what efficient algorithms can achieve, especially near sparse-graph detection limits.

Latest papers

12 papers1 paper in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
Oct 6, 2026Soroor GhandaliBelief Propagation Low-Degree Polynomial Method
Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling
Aug 4, 2026Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore TraniGraph Neural Networks Graph Pooling
University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy
The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
Jul 18, 2026Aseem Raj BaranwalGraph Neural Networks Message Passing Neural Networks
Network Learning with Semi-relaxed Gromov-Wasserstein
Jun 1, 2026Charles Dufour, Ulysse Naepels, Leonardo V. SantoroGraph Structure Learning Latent Variable Models
EPFL, Institute of Mathematics Lausanne, Switzerland
Query-Limited Community Recovery in Stochastic Block Models
Jun 1, 2026Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen +1Active Learning Adaptive Sampling
1Microsoft Research, India · 2Indraprastha Institute of Information Technology, India · University of Liverpool, United Kingdom +1
Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models
May 27, 2026Simon Queric, Cédric Vincent-Cuaz, Charles Bouveyron +1Model Selection Latent Variable Models
Universit´e Cˆote d’Azur, Inria, CNRS LJAD, Maasai Nice, France · EPFL Lausanne, Switzerland · Universit´e Cˆote d’Azur, Inria, CNRS CEPAM, Maasai Nice, France
Distance-Misaligned Training in Graph Transformers and Adaptive Graph-Aware Control
Apr 24, 2026Qinhan Hou, Jing TangGraph Attention Networks Stochastic Block Model
University of Helsinki Helsinki, Finland
Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model
Apr 21, 2026Manuel Fernandez, Ludovic Stephan, Yizhe ZhuSpectral Clustering Stochastic Block Model
Department of Mathematics, University of Southern California · Univ Rennes, Ensai, CNRS, CREST-UMR 9194, F-35000 Rennes, France
How many asymmetric communities are there in multi-layer directed networks?
Feb 25, 2026Huan QingGraph Clustering Stochastic Block Model
School of Economics and Finance, Chongqing University of Technology, Chongqing, 400054, China
Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection
Feb 19, 2026Sie Hendrata Dharmawan, Peter ChinStochastic Block Model Graph Clustering
Thayer School Of Engineering · Dartmouth College · Hanover, NH, USA
Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming
Jan 7, 2026Valentine Olanubi, Phineas Agar, Brendan AmesConvex Relaxation Stochastic Block Model
University of Alabama, Department of Mathematics · Department of Mathematics, University of Alabama, Tuscaloosa, AL, USA · University of Southampton, School of Mathematical Sciences +1
Optimal Clustering of Multi-layer Networks under Mixture Block Models
Nov 27, 2023Zhongyuan Lyu, Ting Li, Dong XiaClustering Stochastic Block Model
Department of Mathematics, Hong Kong University of Science and Technology · Department of Applied Mathematics, The Hong Kong Polytechnic University

Oct 6, 2026J/K move · Enter open · S save

Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models

Soroor Ghandali

Belief Propagation Low-Degree Polynomial Method Stochastic Block Model Graph Clustering

Open paper AskPDF arXiv

We study community recovery in the sparse symmetric stochastic block model with

q

communities, average degree

d

and signal strength

λ

through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold

dλ^2=1

and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-

D

polynomial rules is the trivial risk times

1-\mathrm{Corr}_D^2

. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for

q\ge 5

there is a window below the threshold in which no low-degree rule beats the trivial risk asymptotically, while an exponential-time rule does on a set of labelings of probability

1-o(1)

. Second, the Fisher information about

λ

carried by cycle counts is a series with terms of order

k(dλ^2)^k

, convergent exactly when

dλ^2<1

; below the threshold the relative error of every unbiased cycle-based estimator of

λ^k

stays above an explicit constant, and every cycle-count test has success probability bounded below one. Third, the derivative of belief propagation at its uninformative fixed point multiplies a random perturbation by

|λ|\sqrt{d}

per iteration, and one EM step taken there leaves

λ

unchanged. A signal-to-noise computation recovers the condition

dλ^{1/χ}>1

of Chin et al. for

q=n^χ

communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to

3\times 10^5

vertices confirm the threshold for

q=2

, the hard window for

q=5

, and the many-community scaling.