mlsanityData to 14 Oct 2026

Joint Community Detection and Rotational Synchronization via Semidefinite Programming

arXiv 2105.06031 ↗First posted 13 May 2021stat.ML cs.LG cs.SIcited by 4

Not on the map. Why?

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.

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

22 of 62 references.

References · 22

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  2. 2017Community Detection and Stochastic Block Modelscited by 319
  3. 2013Consistency of spectral clustering in stochastic block modelscited by 129
  4. 2014Exact Recovery in the Stochastic Block Modelcited by 78
  5. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  6. 2013A Proof Of The Block Model Threshold Conjecturecited by 36
  7. 2014Achieving Exact Cluster Recovery Threshold via Semidefinite Programmingcited by 33
  8. 2016Nonconvex phase synchronizationcited by 30
  9. 2020Message Passing Least Squares Framework and its Application to Rotation Synchronizationcited by 22
  10. 2020Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methodscited by 18
  11. 2013Rotationally Invariant Image Representation for Viewing Direction Classification in Cryo-EMcited by 17
  12. 2020A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Groupcited by 15
10 more
  1. 2015Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensionscited by 13
  2. 2018Convex Relaxation Methods for Community Detectioncited by 11
  3. 2015A semidefinite program for unbalanced multisection in the stochastic block modelcited by 7
  4. 2019Multi-Frequency Phase Synchronizationcited by 7
  5. 2017Provable Estimation of the Number of Blocks in Block Modelscited by 6
  6. 2019Unsupervised Co-Learning on G-Manifolds Across Irreducible Representationscited by 5
  7. 2019Representation Theoretic Patterns in Multi-Frequency Class Averaging for Three-Dimensional Cryo-Electron Microscopycited by 4
  8. 2019Multi-Frequency Vector Diffusion Mapscited by 4
  9. 2020Maximizing robustness of point-set registration by leveraging non-convexitycited by 3
  10. 2016A Representation Theory Perspective on Simultaneous Alignment and Classificationcited by 2

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 1.

4 papers.

  1. 2021Optimal Orthogonal Group Synchronization and Rotation Group Synchronizationcited by 4
  2. 2021A Spectral Method for Joint Community Detection and Orthogonal Group Synchronizationcited by 3
  3. 2021Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Methodcited by 2
  4. 2022Multi-Frequency Joint Community Detection and Phase Synchronizationcited by 0