Exploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models
The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in community detection under the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental limits of recovery. In this paper, we consider the SBM in its full generality, where there is no restriction on the number and sizes of communities or how they grow with the number of nodes, as well as on the connectivity probabilities inside or across communities. For such stochastic block models, we provide guarantees for exact recovery via a semidefinite program as well as upper and lower bounds on SBM parameters for exact recoverability. Our results exploit the tradeoffs among the various parameters of heterogenous SBM and provide recovery guarantees for many new interesting SBM configurations.
The paper focuses on a heterogeneous extension of the well-known stochastic block models, by considering the case where the communities might vary significantly in both size and connectivity. The authors develop sufficient recovery conditions for both convex relaxation approaches and a modified maximum likelihood estimate,  as well as some general lower bounds.  A few concrete examples have been provided to illustrate their results. In particular, the paper is able to accommodate the scenario where some communities have vanishingly small size.   The results are interesting, which provide a practically relevant extension of the prior work. In particular, I like the examples listed in Section 3,  which help the readers develop a better understanding of the tradeoff in heterogeneous SBM.    The flip side: the paper falls short of providing explanation for the key conditions presented in their main theorems (e.g. Theorem 1).  While both upper and lower bounds on the performance of MLE have been presented, I couldn't find discussion concerning the gap between these bounds,  making it difficult for me to evaluate the tightness of these results.  Also, I think the paper would benefit from some numerical experiments. 
 1.  It would be good to provide some operational meaning of the notion "relative density".   2.  Some interpretation about the sufficient recovery condition in Theorem 1 is missing. What does the recovery condition mean?  For example, the first condition might be interpreted as the mean difference (or signal strength) being larger than the variation.  In general,  I hope that the authors can try their best to provide intuition for each of the key conditions, which would be very helpful for the readers.   3. Around Equation (2.5), the authors turn their attention from the original maximum likelihood estimate to a modified MLE independent of the parameters.  While this modified version is perhaps a more practically appealing algorithm,  I'm wondering whether there is any statistical loss that occurs due to this modification. It would be good to provide some comparisons (either positive or negative).   4.  The lower bound in Theorem 4 also needs some interpretation.  At first glance it looks quite different from the sufficient recovery condition given in Theorem 3.  The authors might want to discuss the tightness of both Theorem 3 and Theorem 4 -- do they match at least for some special cases?    5.  While the paper is mostly concerned with the scaling results,  can the authors comment on the possibility of obtaining tight pre-constants?  6.  Page 5,  the expression "sufficient conditions for when the exact recovery is impossible" doesn't read well; perhaps just "necessary conditions for exact recovery".    7.  One of the main results is the power of convex relaxation even when some communities have very small sizes.  Can the authors provide some numerical experiments using convex programming to illustrate the practical relevance of the theoretical prediction?