Joint community detection and rotational synchronization via semidefinite programming

DOI10.1137/21M1419702MaRDI QIDQ5097498zbMATH OpenOpenAlexWikidataFDO

Authors Yifeng Fan, Yuehaw Khoo, Zhizhen Zhao

Publication date 25 August 2022

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.06031

zbMATH Keywords

community detectionsemidefinite programmingstochastic block modelsynchronization

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Statistical aspects of big data and data science (62R07) Semidefinite programming (90C22)

Abstract: 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.

Recommendations

• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• An extension of the angular synchronization problem to the heterogeneous setting
• Exact and stable recovery of rotations for robust synchronization
• Phase transitions in semidefinite relaxations
• On semidefinite relaxations for the block model

Cites work

• 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
• An introduction to matrix concentration inequalities
• An introduction to random matrices
• Angular synchronization by eigenvectors and semidefinite programming
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Community detection and stochastic block models: recent developments
• Community detection thresholds and the weak Ramanujan property
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Consistency of spectral clustering in stochastic block models
• Convex relaxation methods for community detection
• Exact Recovery in the Stochastic Block Model
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 1993745 (Why is no real title available?)
• scientific article; zbMATH DE number 6026126 (Why is no real title available?)
• Indirect Blockmodeling of 3-Way Networks
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• Nonconvex phase synchronization
• Reconstruction and estimation in the planted partition model
• Representation theoretic patterns in multi-frequency class averaging for three-dimensional cryo-electron microscopy
• Semidefinite Programming
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• The dimension-free structure of nonhomogeneous random matrices
• The orthogonal Weingarten formula in compact form
• The random matrix theory of the classical compact groups
• The solution of some random NP-hard problems in polynomial expected time
• The spectral norm of random lifts of matrices
• The Structure and Function of Complex Networks
• User-friendly tail bounds for sums of random matrices
• Vector diffusion maps and the connection Laplacian
• Viewing angle classification of cryo-electron microscopy images using eigenvectors

Cited in

(5)

• An extension of the angular synchronization problem to the heterogeneous setting
• Synchronization overZ₂and community detection in signed multiplex networks with constraints
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• Tightness of SDP and Burer-Monteiro factorization for phase synchronization in a high-noise regime

This page was built for publication: Joint community detection and rotational synchronization via semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5097498)