# Multi-Frequency Joint Community Detection and Phase Synchronization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 16 Jun 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [Message-passing algorithms for synchronization problems over compact groups](https://mlsanity.com/paper/1610.04583/) (2016)
- [Global registration of multiple point clouds using semidefinite programming](https://mlsanity.com/paper/1306.5226/) (2013)
- [Rotationally Invariant Image Representation for Viewing Direction Classification in Cryo-EM](https://mlsanity.com/paper/1309.7643/) (2013)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization](https://mlsanity.com/paper/1603.00211/) (2016)
- [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)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions](https://mlsanity.com/paper/1502.07738/) (2015)
- [Convex Relaxation Methods for Community Detection](https://mlsanity.com/paper/1810.00315/) (2018)
- [Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method](https://mlsanity.com/paper/2106.05644/) (2021)
- [Non-unique games over compact groups and orientation estimation in cryo-EM](https://mlsanity.com/paper/1505.03840/) (2015)
- [A semidefinite program for unbalanced multisection in the stochastic block model](https://mlsanity.com/paper/1507.05605/) (2015)
- [Strong Consistency of Spectral Clustering for Stochastic Block Models](https://mlsanity.com/paper/1710.06191/) (2017)
- [Multi-Frequency Phase Synchronization](https://mlsanity.com/paper/1901.08235/) (2019)
- [Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups](https://mlsanity.com/paper/1308.5207/) (2013)
- [Exponential error rates of SDP for block models: Beyond Grothendieck's inequality](https://mlsanity.com/paper/1705.08391/) (2017)
- [Joint Community Detection and Rotational Synchronization via Semidefinite Programming](https://mlsanity.com/paper/2105.06031/) (2021)
- [Robust and efficient multi-way spectral clustering](https://mlsanity.com/paper/1609.08251/) (2016)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2112.14204/) (2021)

## Abstract (arXiv)

This paper studies the joint community detection and phase synchronization problem on the textitstochastic block model with relative phase, where each node is associated with an unknown phase angle. This problem, with a variety of real-world applications, aims to recover the cluster structure and associated phase angles simultaneously. We show this problem exhibits a textit``multi-frequency'' structure by closely examining its maximum likelihood estimation (MLE) formulation, whereas existing methods are not originated from this perspective. To this end, two simple yet efficient algorithms that leverage the MLE formulation and benefit from the information across multiple frequencies are proposed. The former is a spectral method based on the novel multi-frequency column-pivoted QR factorization. The factorization applied to the top eigenvectors of the observation matrix provides key information about the cluster structure and associated phase angles. The second approach is an iterative multi-frequency generalized power method, where each iteration updates the estimation in a matrix-multiplication-then-projection manner. Numerical experiments show that our proposed algorithms significantly improve the ability of exactly recovering the cluster structure and the accuracy of the estimated phase angles, compared to state-of-the-art algorithms.