Joint Community Detection and Rotational Synchronization via Semidefinite Programming
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.
Code (1)
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method
This paper proposes a Generalized Power Method (GPM) to tackle the problem of community detection and group synchronization simultaneously in a direct non-convex manner. Under the stochastic group block model (SGBM), the…
Community DetectionStochastic Block ModelA Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
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 detecti…
Community DetectionMinimax Rates for Robust Community Detection
In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolerate an $\epsilon$-fraction of corruptions…
Community DetectionStochastic Block ModelCommunity Detection with a Subsampled Semidefinite Program
Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so …
ClusteringCommunity DetectionStochastic Block ModelA Semidefinite Program for Structured Blockmodels
Semidefinite programs have recently been developed for the problem of community detection, which may be viewed as a special case of the stochastic blockmodel. Here, we develop a semidefinite program that can be tailored …
Community Detection