# Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 13 Apr 2023.

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

- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Uncertainty quantification in the Bradley-Terry-Luce model](https://mlsanity.com/paper/2110.03874/) (2021)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [ℓ∞-Bounds of the MLE in the BTL Model under General Comparison Graphs](https://mlsanity.com/paper/2110.10825/) (2021)
- [Asymptotic comparison of identifying constraints for Bradley-Terry models](https://mlsanity.com/paper/2205.04341/) (2022)
- [Graph Resistance and Learning from Pairwise Comparisons](https://mlsanity.com/paper/1902.00141/) (2019)
- [Community Recovery in Graphs with Locality](https://mlsanity.com/paper/1602.03828/) (2016)

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

- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries](https://mlsanity.com/paper/2605.23854/) (2026)
- [Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions](https://mlsanity.com/paper/2609.26326/) (2026)
- [Random pairing MLE for estimation of item parameters in Rasch model](https://mlsanity.com/paper/2406.13989/) (2024)
- [Bradley-Terry model under general comparison graphs](https://mlsanity.com/paper/2610.06237/) (2026)
- [Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs](https://mlsanity.com/paper/2610.09030/) (2026)

## Abstract (arXiv)

This technical report studies the problem of ranking from pairwise comparisons in the classical Bradley-Terry-Luce (BTL) model, with a focus on score estimation. For general graphs, we show that, with sufficiently many samples, maximum likelihood estimation (MLE) achieves an entrywise estimation error matching the Cram'er-Rao lower bound, which can be stated in terms of effective resistances; the key to our analysis is a connection between statistical estimation and iterative optimization by preconditioned gradient descent. We are also particularly interested in graphs with locality, where only nearby items can be connected by edges; our analysis identifies conditions under which locality does not hurt, i.e. comparing the scores between a pair of items that are far apart in the graph is nearly as easy as comparing a pair of nearby items. We further explore divide-and-conquer algorithms that can provably achieve similar guarantees even in the regime with the sparsest samples, while enjoying certain computational advantages. Numerical results validate our theory and confirm the efficacy of the proposed algorithms.