Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method
arXiv:2106.05644
Abstract
In this paper, we study the problem of exact community recovery in the symmetric stochastic block model, where a graph of vertices is randomly generated by partitioning the vertices into equal-sized communities and then connecting each pair of vertices with probability that depends on their community memberships. Although the maximum-likelihood formulation of this problem is discrete and non-convex, we propose to tackle it directly using projected power iterations with an initialization that satisfies a partial recovery condition. Such an initialization can be obtained by a host of existing methods. We show that in the logarithmic degree regime of the considered problem, the proposed method can exactly recover the underlying communities at the information-theoretic limit. Moreover, with a qualified initialization, it runs in time, which is competitive with existing state-of-the-art methods. We also present numerical results of the proposed method to support and complement our theoretical development.
arXiv commentThis paper has been accepted to ICML 2021
References in corpus (8)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Stochastic blockmodels and community structure in networks
- Generalized power method for sparse principal component analysis
- Nonconvex phase synchronization
- Near-optimal bounds for phase synchronization
- Community Detection in the Labelled Stochastic Block Model
- Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms