Stochastic Block Models and Reconstruction

The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on $n$ nodes with two equal-sized clusters, with an between-class edge probability of $q$ and a within-class edge probability of $p$. Although most of the literature on this model has focused on the case of increasing degrees (ie.\ $pn, qn \to \infty$ as $n \to \infty$), the sparse case $p, q = O(1/n)$ is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborov\'a based on deep, non-rigorous ideas from statistical physics gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if $p = a/n$ and $q = b/n$, then Decelle et al.\ conjectured that it is possible to cluster in a way correlated with the true partition if $(a - b)^2 > 2(a + b)$, and impossible if $(a - b)^2 < 2(a + b)$. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if $(a - b)^2 > C (a + b)$ for some sufficiently large $C$. We prove half of their prediction, showing that it is indeed impossible to cluster if $(a - b)^2 < 2(a + b)$. Furthermore we show that it is impossible even to estimate the model parameters from the graph when $(a - b)^2 < 2(a + b)$; on the other hand, we provide a simple and efficient algorithm for estimating $a$ and $b$ when $(a - b)^2 > 2(a + b)$. Following Decelle et al, our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.