# Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2015.

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

- [Looping in the Human Collaborative and Explainable Bayesian Optimization](https://mlsanity.com/paper/2310.17273/) (2023)
- [Byzantine Spectral Ranking](https://mlsanity.com/paper/2211.07902/) (2022)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Minimax Hypothesis Testing for the Bradley-Terry-Luce Model](https://mlsanity.com/paper/2410.08360/) (2024)
- [The interplay between ranking and communities in networks](https://mlsanity.com/paper/2112.12670/) (2021)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [Robust Angular Synchronization via Directed Graph Neural Networks](https://mlsanity.com/paper/2310.05842/) (2023)
- [Toward Effective Digraph Representation Learning: A Magnetic Adaptive Propagation based Approach](https://mlsanity.com/paper/2501.11817/) (2025)
- [Unrolled algorithms for group synchronization](https://mlsanity.com/paper/2207.09418/) (2022)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Synthetic Principal Component Design: Fast Covariate Balancing with Synthetic Controls](https://mlsanity.com/paper/2211.15241/) (2022)
- [Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models](https://mlsanity.com/paper/2305.06704/) (2023)
- [CURATRON: Complete and Robust Preference Data for Rigorous Alignment of Large Language Models](https://mlsanity.com/paper/2403.02745/) (2024)
- [A theoretical guarantee for SyncRank](https://mlsanity.com/paper/2509.22766/) (2025)

## Abstract (arXiv)

We consider the classic problem of establishing a statistical ranking of a set of n items given a set of inconsistent and incomplete pairwise comparisons between such items. Instantiations of this problem occur in numerous applications in data analysis (e.g., ranking teams in sports data), computer vision, and machine learning. We formulate the above problem of ranking with incomplete noisy information as an instance of the group synchronization problem over the group SO(2) of planar rotations, whose usefulness has been demonstrated in numerous applications in recent years. Its least squares solution can be approximated by either a spectral or a semidefinite programming (SDP) relaxation, followed by a rounding procedure. We perform extensive numerical simulations on both synthetic and real-world data sets, showing that our proposed method compares favorably to other algorithms from the recent literature. Existing theoretical guarantees on the group synchronization problem imply lower bounds on the largest amount of noise permissible in the ranking data while still achieving exact recovery. We propose a similar synchronization-based algorithm for the rank-aggregation problem, which integrates in a globally consistent ranking pairwise comparisons given by different rating systems on the same set of items. We also discuss the problem of semi-supervised ranking when there is available information on the ground truth rank of a subset of players, and propose an algorithm based on SDP which recovers the ranks of the remaining players. Finally, synchronization-based ranking, combined with a spectral technique for the densest subgraph problem, allows one to extract locally-consistent partial rankings, in other words, to identify the rank of a small subset of players whose pairwise comparisons are less noisy than the rest of the data, which other methods are not able to identify.