A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
Not on the map. Why?
Abstract (arXiv)
Community detection and orthogonal group synchronization are both fundamental problems with a variety of important applications in science and engineering. In this work, we consider the joint problem of community detection and orthogonal group synchronization which aims to recover the communities and perform synchronization simultaneously. To this end, we propose a simple algorithm that consists of a spectral decomposition step followed by a blockwise column pivoted QR factorization (CPQR). The proposed algorithm is efficient and scales linearly with the number of edges in the graph. We also leverage the recently developed `leave-one-out' technique to establish a near-optimal guarantee for exact recovery of the cluster memberships and stable recovery of the orthogonal transforms. Numerical experiments demonstrate the efficiency and efficacy of our algorithm and confirm our theoretical characterization of it.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 30 of its 81 references that are in the map. First posted on arXiv 25 Dec 2021.
Builds on
30 of 81 references.
References · 30
- 2015An Introduction to Matrix Concentration Inequalitiescited by 391
- 2014Exact Recovery in the Stochastic Block Modelcited by 77
- 2013Spectral redemption: clustering sparse networkscited by 54
- 2013Community detection thresholds and the weak Ramanujan propertycited by 47
- 2017Spectral Method and Regularized MLE Are Both Optimal for Top-K Rankingcited by 46
- 2013A Proof Of The Block Model Threshold Conjecturecited by 35
- 2015Achieving Optimal Misclassification Proportion in Stochastic Block Modelcited by 35
- 2014Achieving Exact Cluster Recovery Threshold via Semidefinite Programmingcited by 32
- 2017Near-optimal bounds for phase synchronizationcited by 32
- 2014On semidefinite relaxations for the block modelcited by 22
- 2014Community detection in sparse networks via Grothendieck's inequalitycited by 21
- 2020Strong Consistency, Graph Laplacians, and the Stochastic Block Modelcited by 20
18 more
- 2020Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methodscited by 18
- 2013Global registration of multiple point clouds using semidefinite programmingcited by 17
- 2013Rotationally Invariant Image Representation for Viewing Direction Classification in Cryo-EMcited by 17
- 2014A simple SVD algorithm for finding hidden partitionscited by 17
- 2017Unperturbed: spectral analysis beyond Davis-Kahancited by 16
- 2014Accurate Community Detection in the Stochastic Block Model via Spectral Algorithmscited by 13
- 2015Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensionscited by 13
- 2015Random Laplacian matrices and convex relaxationscited by 13
- 2020Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysiscited by 10
- 2015A semidefinite program for unbalanced multisection in the stochastic block modelcited by 7
- 2019Multi-Frequency Phase Synchronizationcited by 7
- 2019Unsupervised Co-Learning on G-Manifolds Across Irreducible Representationscited by 5
- 2019Representation Theoretic Patterns in Multi-Frequency Class Averaging for Three-Dimensional Cryo-Electron Microscopycited by 4
- 2019Multi-Frequency Vector Diffusion Mapscited by 4
- 2021Joint Community Detection and Rotational Synchronization via Semidefinite Programmingcited by 4
- 2021Optimal Orthogonal Group Synchronization and Rotation Group Synchronizationcited by 4
- 2016Robust and efficient multi-way spectral clusteringcited by 3
- 2016A Representation Theory Perspective on Simultaneous Alignment and Classificationcited by 2
Built on by
Citing papers per year: 2021: 1; 2022: 1; 2023: 0; 2024: 0; 2025: 1.
3 papers.