Skip to yearly menu bar Skip to main content


Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method

Sijin Chen · Xiwei Cheng · Anthony Man-Cho So

MR1 & MR2 - Number 121
[ ]
Sat 4 May 6 a.m. PDT — 8:30 a.m. PDT

Abstract: This paper proposes a Generalized Power Method (GPM) to simultaneously solve the joint problem of community detection and group synchronization in a direct non-convex manner, in contrast to the existing method of semidefinite programming (SDP). Under a natural extension of stochastic block model (SBM), our theoretical analysis proves that the proposed algorithm is able to exactly recover the ground truth in $O(n\log^2 n)$ time for problems of size $n$, sharply outperforming the $O(n^{3.5})$ runtime of SDP. Moreover, we give a lower bound of model parameters as a sufficient condition for the exact recovery of GPM. The new bound breaches the information-theoretic limit for pure community detection under SBM, thus demonstrating the superiority of our simultaneous optimization algorithm over any two-stage method that performs the two tasks in succession. We also conduct numerical experiments on GPM and SDP to corroborate our theoretical analysis.

Live content is unavailable. Log in and register to view live content