Reconstruction and estimation in the planted partition model

Abstract

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 (Formula presented.) nodes with two equal-sized clusters, with an between-class edge probability of (Formula presented.) and a within-class edge probability of (Formula presented.). Although most of the literature on this model has focused on the case of increasing degrees (ie. (Formula presented.) as (Formula presented.)), the sparse case (Formula presented.) is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová 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 (Formula presented.) and (Formula presented.), then Decelle et al. conjectured that it is possible to cluster in a way correlated with the true partition if (Formula presented.), and impossible if (Formula presented.). By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if (Formula presented.) for some sufficiently large (Formula presented.). We prove half of their prediction, showing that it is indeed impossible to cluster if (Formula presented.). Furthermore we show that it is impossible even to estimate the model parameters from the graph when (Formula presented.); on the other hand, we provide a simple and efficient algorithm for estimating (Formula presented.) and (Formula presented.) when (Formula presented.). 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.