# Joint Community Detection and Rotational Synchronization via Semidefinite Programming

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 62 references that are in the map.
- First posted on arXiv 13 May 2021.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [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)
- [Message Passing Least Squares Framework and its Application to Rotation Synchronization](https://mlsanity.com/paper/2007.13638/) (2020)
- [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)
- [A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group](https://mlsanity.com/paper/2009.07514/) (2020)
- [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)
- [A semidefinite program for unbalanced multisection in the stochastic block model](https://mlsanity.com/paper/1507.05605/) (2015)
- [Multi-Frequency Phase Synchronization](https://mlsanity.com/paper/1901.08235/) (2019)
- [Provable Estimation of the Number of Blocks in Block Models](https://mlsanity.com/paper/1705.08580/) (2017)
- [Unsupervised Co-Learning on G-Manifolds Across Irreducible Representations](https://mlsanity.com/paper/1906.02707/) (2019)
- [Representation Theoretic Patterns in Multi-Frequency Class Averaging for Three-Dimensional Cryo-Electron Microscopy](https://mlsanity.com/paper/1906.01082/) (2019)
- [Multi-Frequency Vector Diffusion Maps](https://mlsanity.com/paper/1906.02605/) (2019)
- [Maximizing robustness of point-set registration by leveraging non-convexity](https://mlsanity.com/paper/2004.08772/) (2020)
- [A Representation Theory Perspective on Simultaneous Alignment and Classification](https://mlsanity.com/paper/1607.03464/) (2016)

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

- [Optimal Orthogonal Group Synchronization and Rotation Group Synchronization](https://mlsanity.com/paper/2109.13491/) (2021)
- [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)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)

## Abstract (arXiv)

In the presence of heterogeneous data, where randomly rotated objects fall into multiple underlying categories, it is challenging to simultaneously classify them into clusters and synchronize them based on pairwise relations. This gives rise to the joint problem of community detection and synchronization. We propose a series of semidefinite relaxations, and prove their exact recovery when extending the celebrated stochastic block model to this new setting where both rotations and cluster identities are to be determined. Numerical experiments demonstrate the efficacy of our proposed algorithms and confirm our theoretical result which indicates a sharp phase transition for exact recovery.