Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method

In this paper, we study the problem of exact community recovery in the symmetric stochastic block model, where a graph of n vertices is randomly generated by partitioning the vertices into K ≥ 2 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 O(nlog2n/loglog n) 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.