# Improved theoretical guarantee for rank aggregation via spectral method

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 7 Sep 2023.

## Builds on (most cited first, 15 of 15)

- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Uncertainty quantification in the Bradley-Terry-Luce model](https://mlsanity.com/paper/2110.03874/) (2021)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [Minimax Rates and Efficient Algorithms for Noisy Sorting](https://mlsanity.com/paper/1710.10388/) (2017)
- [Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization](https://mlsanity.com/paper/1504.01070/) (2015)
- [Spectral Ranking using Seriation](https://mlsanity.com/paper/1406.5370/) (2014)
- [Ranking and synchronization from pairwise measurements via SVD](https://mlsanity.com/paper/1906.02746/) (2019)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Ranking a set of objects: a graph based least-square approach](https://mlsanity.com/paper/2002.11590/) (2020)

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

- [Bridging Domains with Approximately Shared Features](https://mlsanity.com/paper/2403.06424/) (2024)
- [A theoretical guarantee for SyncRank](https://mlsanity.com/paper/2509.22766/) (2025)

## Abstract (arXiv)

Given pairwise comparisons between multiple items, how to rank them so that the ranking matches the observations? This problem, known as rank aggregation, has found many applications in sports, recommendation systems, and other web applications. As it is generally NP-hard to find a global ranking that minimizes the mismatch (known as the Kemeny optimization), we focus on the Erd"os-R'enyi outliers (ERO) model for this ranking problem. Here, each pairwise comparison is a corrupted copy of the true score difference. We investigate spectral ranking algorithms that are based on unnormalized and normalized data matrices. The key is to understand their performance in recovering the underlying scores of each item from the observed data. This reduces to deriving an entry-wise perturbation error bound between the top eigenvectors of the unnormalized/normalized data matrix and its population counterpart. By using the leave-one-out technique, we provide a sharper ℓ∞-norm perturbation bound of the eigenvectors and also derive an error bound on the maximum displacement for each item, with only Omega(nlog n) samples. Our theoretical analysis improves upon the state-of-the-art results in terms of sample complexity, and our numerical experiments confirm these theoretical findings.