A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
From MaRDI portal
Abstract: 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.
Recommendations
- Joint community detection and rotational synchronization via semidefinite programming
- Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
- A unified approach to synchronization problems over subgroups of the orthogonal group
- Improved performance guarantees for orthogonal group synchronization via generalized power method
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
Cites work
- scientific article; zbMATH DE number 6381735 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 6026126 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Krylov--Schur algorithm for large eigenproblems
- A Simple SVD Algorithm for Finding Hidden Partitions
- A fast randomized algorithm for the approximation of matrices
- A proof of the block model threshold conjecture
- A representation theory perspective on simultaneous alignment and classification
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Achieving optimal misclassification proportion in stochastic block models
- An \(\ell_{\infty}\) eigenvector perturbation bound and its application
- An introduction to matrix concentration inequalities
- An introduction to random matrices
- Angular synchronization by eigenvectors and semidefinite programming
- Clustering by passing messages between data points
- Community detection in sparse networks via Grothendieck's inequality
- Community detection thresholds and the weak Ramanujan property
- Computing localized representations of the Kohn-Sham subspace via randomization and refinement
- Concentration inequalities. A nonasymptotic theory of independence
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Entrywise eigenvector analysis of random matrices with low expected rank
- Exact Recovery in the Stochastic Block Model
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Global registration of multiple point clouds using semidefinite programming
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- High-dimensional probability. An introduction with applications in data science
- Indirect Blockmodeling of 3-Way Networks
- Joint community detection and rotational synchronization via semidefinite programming
- Least squares quantization in PCM
- Near-optimal bounds for phase synchronization
- Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
- On semidefinite relaxations for the block model
- Optimal orthogonal group synchronization and rotation group synchronization
- Random Laplacian matrices and convex relaxations
- Reconstruction and estimation in the planted partition model
- Representation theoretic patterns in multi-frequency class averaging for three-dimensional cryo-electron microscopy
- SCDM-k: localized orbitals for solids via selected columns of the density matrix
- Simple, direct and efficient multi-way spectral clustering
- Some Metric Inequalities in the Space of Matrices
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Spectral redemption in clustering sparse networks
- Spectral synchronization of multiple views in \(\mathrm{SE}(3)\)
- Spectral techniques applied to sparse random graphs
- Strong consistency, graph Laplacians, and the stochastic block model
- The Rotation of Eigenvectors by a Perturbation. III
- The dimension-free structure of nonhomogeneous random matrices
- The solution of some random NP-hard problems in polynomial expected time
- Uniform Bounds for Invariant Subspace Perturbations
- Unitary Triangularization of a Nonsymmetric Matrix
- Unperturbed: spectral analysis beyond Davis-Kahan
- Viewing angle classification of cryo-electron microscopy images using eigenvectors
Cited in
(5)- Joint community detection and rotational synchronization via semidefinite programming
- Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
- Higher-order group synchronization
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
- A unified approach to synchronization problems over subgroups of the orthogonal group
This page was built for publication: A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166053)
