Recovering Communities in the General Stochastic Block Model Without Knowing the Parameters
The stochastic block model (SBM) has recently gathered significant attention due to new threshold phenomena. However, most developments rely on the knowledge of the model parameters, or at least on the number of communities. This paper introduces efficient algorithms that do not require such knowledge and yet achieve the optimal information-theoretic tradeoffs identified in Abbe-Sandon '15. In the constant degree regime, an algorithm is developed that requires only a lower-bound on the relative sizes of the communities and achieves the optimal accuracy scaling for large degrees. This lower-bound requirement is removed for the regime of diverging degrees. For the logarithmic degree regime, this is further enhanced into a fully agnostic algorithm that simultaneously learns the model parameters, achieves the optimal CH-limit for exact recovery, and runs in quasilinear time. These provide the first algorithms affording efficiency, universality and information-theoretic optimality for strong and weak consistency in the SBM.
The paper presents two algorithms for community recovery of nodes for graphs generated from stochastic block models (SBM). Two different regimes of SBM has been considered, one with constant average degree and and another with average degree of the order log(n). For the two cases, algorithms have been proposed based on shortest path finding. Main results of the paper arebounds on partial recovery of node labels with high probability for sparse (constant degree) regime and complete recovery of node labels in semi-sparse (log(n)-average degree) regime above the information-theoretic threshold of partial and complete recovery. The error bounds are given based on the proposed algorithms and shown to be optimal. The paper builds on a previous paper (Abbe and Sanders, 2015), which presented similar algorithms and analysis but with the restriction that knowledge of model parameters were needed. In this paper those restrictions are not needed anymore.The paper along with the supplementary materials is quite mathematically rigorous. Technically, the paper is of high quality. It presents strong results on almost exact recovery and exact recovery of community labels without assuming knowledge of model parameters. However, the paper lacks a bit in numerical comparison of performance with other methods of community detection.However, the main drawback of the paper is clarity. The paper presents two different algorithms, but, the algorithms are not properly outlined in the paper. The bulk of the paper including the main algorithm statements is in the supplementary material and without reading through the supplementary material, it is very difficult to parse the paper. The paper reads like a journal paper which has been truncated to meet the page constraints. The agnostic-sphere-comparison algorithm, which is the main algorithm of the paper, need to be presented a bit more clearly, like the way it has been presented in the supplementary material. Also, note that definitions of SBM is not consistent between Theorem 1 and Corollary 1 (one use Q and another Q/n) and and the way SBM has been defined states Q as probability (in line 47, page 1), which is inconsistent with the normalizations of Q made later in the paper. The paper presents an original algorithm of approximately linear time and gives a mathematically rigorous proof that the algorithm works for community recovery for general SBM. This makes the algorithms presented in the paper as one of the state-of-the-art methods for community recovery. Algorithms based on shortest paths has been previously proposed in literature (Bhattacharyya and Bickel, 2014), but in the current paper the algorithm is much more subtle and the results obtained are tighter.The paper is significant in terms of the information theoretic bounds presented in the paper as well as the algorithms introduced. The paper can be generalized to analyze more general network models, specially for growing number of communities. But, due to the technical subtlety of the paper, I feel that the paper is more suited for a journal publication than a short conference publication.