# Robust Group Synchronization via Cycle-Edge Message Passing

arXiv: https://arxiv.org/abs/1912.11347 · HTML: https://mlsanity.com/paper/1912.11347/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2019.

## Built on by (most cited first, 19 of 19)

- [Robust Group Synchronization via Quadratic Programming](https://mlsanity.com/paper/2206.08994/) (2022)
- [Snapshot of Algebraic Vision](https://mlsanity.com/paper/2210.11443/) (2022)
- [Fast, Accurate and Memory-Efficient Partial Permutation Synchronization](https://mlsanity.com/paper/2203.16505/) (2022)
- [Sequential Manipulation Against Rank Aggregation: Theory and Algorithm](https://mlsanity.com/paper/2407.01916/) (2024)
- [Scalable Cluster-Consistency Statistics for Robust Multi-Object Matching](https://mlsanity.com/paper/2201.04797/) (2022)
- [Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization](https://mlsanity.com/paper/2407.04260/) (2024)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Cycle-Sync: Robust Global Camera Pose Estimation through Enhanced Cycle-Consistent Synchronization](https://mlsanity.com/paper/2511.02329/) (2025)
- [Robust Angular Synchronization via Directed Graph Neural Networks](https://mlsanity.com/paper/2310.05842/) (2023)
- [Certifiably Optimal Anisotropic Rotation Averaging](https://mlsanity.com/paper/2503.07353/) (2025)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Higher-Order Group Synchronization](https://mlsanity.com/paper/2505.21932/) (2025)
- [On the Robustness of Multi-View Rotation Averaging](https://mlsanity.com/paper/2102.05454/) (2021)
- [Multiple Rotation Averaging with Constrained Reweighting Deep Matrix Factorization](https://mlsanity.com/paper/2409.09790/) (2024)
- [TriDE: Triangle-Consistent Translation Directions for Global Camera Pose Estimation](https://mlsanity.com/paper/2605.06889/) (2026)
- [TriP: A Triangle Puzzle Approach to Robust Translation Averaging](https://mlsanity.com/paper/2605.07143/) (2026)
- [CertBind from Multimodal Connectivity to Certifiable Retrieval Decisions](https://mlsanity.com/paper/2608.06516/) (2026)
- [Recovery Theory for Projected Power Iterations in Permutation Synchronization](https://mlsanity.com/paper/2609.09502/) (2026)
- [GeoCond: A Conditioning-Aware Reliability Adapter for Feed-Forward 3D Reconstruction](https://mlsanity.com/paper/2609.18465/) (2026)

## Abstract (arXiv)

We propose a general framework for solving the group synchronization problem, where we focus on the setting of adversarial or uniform corruption and sufficiently small noise. Specifically, we apply a novel message passing procedure that uses cycle consistency information in order to estimate the corruption levels of group ratios and consequently solve the synchronization problem in our setting. We first explain why the group cycle consistency information is essential for effectively solving group synchronization problems. We then establish exact recovery and linear convergence guarantees for the proposed message passing procedure under a deterministic setting with adversarial corruption. These guarantees hold as long as the ratio of corrupted cycles per edge is bounded by a reasonable constant. We also establish the stability of the proposed procedure to sub-Gaussian noise. We further establish exact recovery with high probability under a common uniform corruption model.