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

arXiv: https://arxiv.org/abs/2112.14204 · HTML: https://mlsanity.com/paper/2112.14204/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 28 Dec 2021.

## Builds on (most cited first, 18 of 18)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [Rotationally Invariant Image Representation for Viewing Direction Classification in Cryo-EM](https://mlsanity.com/paper/1309.7643/) (2013)
- [On the low-rank approach for semidefinite programs arising in synchronization and community detection](https://mlsanity.com/paper/1602.04426/) (2016)
- [On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization](https://mlsanity.com/paper/1603.00211/) (2016)
- [A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group](https://mlsanity.com/paper/2009.07514/) (2020)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms](https://mlsanity.com/paper/1412.7335/) (2014)
- [Community Detection in Networks with Node Features](https://mlsanity.com/paper/1509.01173/) (2015)
- [Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method](https://mlsanity.com/paper/2106.05644/) (2021)
- [Multi-Frequency Vector Diffusion Maps](https://mlsanity.com/paper/1906.02605/) (2019)
- [Joint Community Detection and Rotational Synchronization via Semidefinite Programming](https://mlsanity.com/paper/2105.06031/) (2021)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)

## Built on by (most cited first, 2 of 2)

- [NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization](https://mlsanity.com/paper/2604.07372/) (2026)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)

## Abstract (arXiv)

This paper proposes a Generalized Power Method (GPM) to tackle the problem of community detection and group synchronization simultaneously in a direct non-convex manner. Under the stochastic group block model (SGBM), theoretical analysis indicates that the algorithm is able to exactly recover the ground truth in O(nlog2n) time, sharply outperforming the benchmark method of semidefinite programming (SDP) in O(n3.5) time. Moreover, a lower bound of parameters is given as a necessary condition for exact recovery of GPM. The new bound breaches the information-theoretic threshold for pure community detection under the stochastic block model (SBM), thus demonstrating the superiority of our simultaneous optimization algorithm over the trivial two-stage method which performs the two tasks in succession. We also conduct numerical experiments on GPM and SDP to evidence and complement our theoretical analysis.