Optimal Cluster Recovery in the Labeled Stochastic Block Model
We consider the problem of community detection or clustering in the labeled Stochastic Block Model (LSBM) with a finite number K of clusters of sizes linearly growing with the global population of items n. Every pair of items is labeled independently at random, and label appears with probability p(i, j, ) between two items in clusters indexed by i and j, respectively. The objective is to reconstruct the clusters from the observation of these random labels. Clustering under the SBM and their extensions has attracted much attention recently. Most existing work aimed at characterizing the set of parameters such that it is possible to infer clusters either positively correlated with the true clusters, or with a vanishing proportion of misclassified items, or exactly matching the true clusters. We find the set of parameters such that there exists a clustering algorithm with at most s misclassified items in average under the general LSBM and for any s = o(n), which solves one open problem raised in [2]. We further develop an algorithm, based on simple spectral methods, that achieves this fundamental performance limit within O(npolylog(n)) computations and without the a-priori knowledge of the model parameters.
This paper explores the fundamental recovery limits of community recovery in a generalized version of the stochastic block model, where each community has size linear in n.  The measurements between each pair of vertices can be one of L labels, which allows to model the SBM, the planted clique problem, and many others using a unified model.  The focus is exact recovery or strong recovery (for which one expects the portion of misclassified nodes to be asymptotically zero).   The theoretical results are quite strong, which generalize many of the prior works along this direction.  The model is also of a lot of interest to multiple communities, so the contribution is timely and important.  I think this is worth being accepted to NIPS.    Despite the strong theory,  I am not completely satisfied by the way this paper is written.  There are many key assumptions / metrics that have not been given enough interpretation,  so it is hard for non-experts to understand what these results / conditions really mean.  The main algorithms are not described in the main text, and there are no simulations carried out (so it's hard to see how much practical relevance the theory bears).  I hope that the authors can consider my comments when revising their paper.  
 1.  The key conditions (A1) and (A2) need more interpretation. How critical are these assumptions?  Are they coming from computational considerations or statistical considerations? Will the fundamental information limits change without these two assumptions?    2.  The authors start by introducing "labels" in the SBMs but defer all motivations / applications to much later.  I think the paper would read better if the authors at least describe some concrete applications right after (or before) describing the mathematical setup. This would be particularly beneficial for those who are non-experts in this field.   3.  Some interpretation of the divergence metric D_{L+} is missing, as this is the most important metric that dictates the recovery limits.  This metric is not easy to parse especially for those who have not read [2,3].  It might be nice to give some simple examples to interpret it.  4.  The achievability part (i.e. Theorem 2) operates upon another assumption (A3), but I do think this additional assumption needs further interpretation as well.    5.  I understand that Algorithms 1 and 2 are deferred to the supplemental materials due to space limitation,  but I think these are very crucial for the paper and deserve a place in the main text (at least I think presenting the procedures is more helpful than elaborating the proof techniques in such a short conference paper).    6.  There is no simulation carried out in this paper,  so it is hard to see how well the derived information limits match practice (e.g. how large does n need to be in order for the practical phase transition to match the theoretical prediction).