Back to Search Start Over

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

Authors :
Wang, Peng
Liu, Huikang
Zhou, Zirui
So, Anthony Man-Cho
Publication Year :
2021

Abstract

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 \ge 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 $\mathcal{O}(n\log^2n/\log\log 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.<br />Comment: This paper has been accepted to ICML 2021

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2106.05644
Document Type :
Working Paper