Exact Recovery in the Stochastic Block Model

Emmanuel Abbe, Georgina Hall, and myself just uploaded a paper on exact recovery in the stochastic block model (SBM), this post will be about this result.

The stochastic block model (SBM) with two communities (or equivalently the planted partition model) is perhaps the simplest model of random graph exhibiting a cluster behavior. Here we’ll look at the very simple form of the model where the graph has two equally sized clusters and vertices connect with probability within clusters and across clusters.

Recently, there has been a lot of interest in understanding what happens for the regime when and are constant. A fascinating phase transition phenomena was conjectured by Decelle et al.: recovering slightly more than 50% of the vertices (i.e., beating a random guess) is possible with high probability (w.h.p.) if and only if

This was proven, roughly at the same time, by Massoulié and Mossel et al., the impossibility result was first shown by Mossel et al. here.

Motivated by this line work, we asked ourselves the natural question of determining whether the problem of recovering all of the vertices (not just over 50%) also admits a sharp threshold phenomenon, we call this problem exact recovery.

Notice that exact recovery is impossible at the regime above as an Erd\H{o}s-Rényi random graph needs at least a logarithmic expected degree in order to be connected (with high probability). In fact, for the Erd\H{o}s-Rényi ensemble , the giant component (the existence of a connected component of linear size) has a sharp threshold at , while connectivity has a sharp threshold at . To hope for exact recovery, we hence consider the regime of probabilities scaling like and , for constants . In fact, one expects at least in order to have a connected graph with high probability.

We showed that indeed this problem has a sharp threshold phenomenon. More, precisely if and are constant (and ) we showed that, if

then it is impossible to perform exact recovery (with high probability). On the other hand, if

then exact recovery is possible (with high probability), with a non-efficient algorithm. Interestingly is equivalent to

and .

Both results are obtained by analyzing the maximum likelihood estimator (similarly to a previous paper that I discussed in this blog post). Interestingly these results require sharp tail bounds for differences of binomial coefficients and the “right tail bound” is quite different from the one that the central limit theorem would suggest, I will write another blog post soon about these bounds, it might be that someone else also finds them useful.

Using an adaptation of the dual certificate techniques described in this post we were also able to show that a certain natural semidefinite programming based algorithm achieves exact recovery (with high probability) as long as

It remains to propose an algorithm that is able to perform exact recovery all the way down to the threshold. Ideas?

Advertisement