Joint Community Detection and Rotational Synchronization via Semidefinite Programming

• URL: http://arxiv.org/abs/2105.06031v2
• Date: Thu, 14 Sep 2023 06:09:09 GMT
• Title: Joint Community Detection and Rotational Synchronization via Semidefinite Programming
• Authors: Yifeng Fan, Yuehaw Khoo and Zhizhen Zhao
• Abstract summary: 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. We propose a series of semidefinite relaxations, and prove their exact recovery when extending the celebrated block model to this new setting. Numerical experiments demonstrate the efficacy of our proposed algorithms and confirm our theoretical result which indicates a sharp phase transition for exact recovery.
• Score: 17.845257705485533
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Time-series Generation by Contrastive Imitation [87.51882102248395]
  We study a generative framework that seeks to combine the strengths of both: Motivated by a moment-matching objective to mitigate compounding error, we optimize a local (but forward-looking) transition policy. At inference, the learned policy serves as the generator for iterative sampling, and the learned energy serves as a trajectory-level measure for evaluating sample quality.
  arXiv  Detail & Related papers  (2023-11-02T16:45:25Z)
• Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models [61.10851158749843]
  Key insights can be obtained by discovering lead-lag relationships inherent in the data. We develop a clustering-driven methodology for robust detection of lead-lag relationships in lagged multi-factor models.
  arXiv  Detail & Related papers  (2023-05-11T10:30:35Z)
• Rotation Synchronization via Deep Matrix Factorization [24.153207403324917]
  We focus on the formulation of rotation synchronization via neural networks. Inspired by deep matrix completion, we express rotation synchronization in terms of matrix factorization with a deep neural network. Our formulation exhibits implicit regularization properties and, more importantly, is unsupervised.
  arXiv  Detail & Related papers  (2023-05-09T08:46:05Z)
• Neighbour Consistency Guided Pseudo-Label Refinement for Unsupervised Person Re-Identification [80.98291772215154]
  Unsupervised person re-identification (ReID) aims at learning discriminative identity features for person retrieval without any annotations. Recent advances accomplish this task by leveraging clustering-based pseudo labels. We propose a Neighbour Consistency guided Pseudo Label Refinement framework.
  arXiv  Detail & Related papers  (2022-11-30T09:39:57Z)
• Predicting the State of Synchronization of Financial Time Series using Cross Recurrence Plots [75.20174445166997]
  This study introduces a new method for predicting the future state of synchronization of the dynamics of two financial time series. We adopt a deep learning framework for methodologically addressing the prediction of the synchronization state. We find that the task of predicting the state of synchronization of two time series is in general rather difficult, but for certain pairs of stocks attainable with very satisfactory performance.
  arXiv  Detail & Related papers  (2022-10-26T10:22:28Z)
• Multi-Frequency Joint Community Detection and Phase Synchronization [22.683901672480353]
  This paper studies the joint community detection and phase synchronization problem on the textitstochastic block model with relative phase We show this problem exhibits a textitmulti-frequency'' structure by closely examining its maximum likelihood estimation (MLE) formulation. Two simple yet efficient algorithms that leverage the MLE formulation and benefit from the information across multiple frequencies are proposed.
  arXiv  Detail & Related papers  (2022-06-16T23:08:27Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization [20.413250472034143]
  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 data points. We also leverage the recently developed leave-one-out' technique to establish a near-optimal guarantee for exact recovery of the cluster memberships.
  arXiv  Detail & Related papers  (2021-12-25T07:38:14Z)
• Learning Iterative Robust Transformation Synchronization [71.73273007900717]
  We propose to use graph neural networks (GNNs) to learn transformation synchronization. In this work, we avoid handcrafting robust loss functions, and propose to use graph neural networks (GNNs) to learn transformation synchronization.
  arXiv  Detail & Related papers  (2021-11-01T07:03:14Z)
• Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods [0.7614628596146599]
  Group synchronization asks to recover group elements from their pairwise measurements. spectral methods have enjoyed great popularity due to their efficiency and convenience. For permutation group synchronization under random corruption, we show that the widely-used two-step procedure can recover all the group elements exactly.
  arXiv  Detail & Related papers  (2020-08-12T14:20:16Z)
• Mixture Representation Learning with Coupled Autoencoders [1.589915930948668]
  We propose an unsupervised variational framework using multiple interacting networks called cpl-mixVAE. In this framework, the mixture representation of each network is regularized by imposing a consensus constraint on the discrete factor. We use the proposed method to jointly uncover discrete and continuous factors of variability describing gene expression in a single-cell transcriptomic dataset.
  arXiv  Detail & Related papers  (2020-07-20T04:12:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.