# Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 28 references that are in the map.
- First posted on arXiv 6 Oct 2026.

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

- [Top-K Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal](https://mlsanity.com/paper/1603.04153/) (2016)
- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions](https://mlsanity.com/paper/2609.26326/) (2026)
- [Maximum Likelihood Estimation for Entity Ranking under Iterative Synthetic Data Augmentation](https://mlsanity.com/paper/2609.32987/) (2026)

## Abstract (arXiv)

Pairwise comparisons are widely used to infer latent scores and identify top-ranked items. Although sharp statistical guarantees are available under uniform sampling, real data often induce irregular comparison graphs with heterogeneous observation counts across pairs. In this paper, we study an arbitrary fixed comparison graph under the Bradley--Terry--Luce model with minimal assumptions. We prove that both the standard maximum likelihood estimator and Rank Centrality achieve a high-probability entrywise error rate of order 1/√λD up to logarithmic and dynamic-range factors, where λD is the algebraic connectivity of the count-weighted observation graph. This guarantee is graph-monotone since λD cannot decrease when additional comparisons are added. Under heterogeneous sampling, where comparison pairs are sampled independently with unequal probabilities, our guarantee improves existing error bounds or requires weaker assumptions. We further extend our analysis to show that both estimators are robust against outcome-adaptive augmentation, where an adversary can choose additional comparison pairs after observing the initial outcomes.