Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs
Abstract
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/β(Ξ»π) up to logarithmic and dynamic-range factors, where Ξ»π is the algebraic connectivity of the count-weighted observation graph. This guarantee is graph-monotone since Ξ»π 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.
Related
- Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
- Convergence and acceleration of a nonlinear fixed-point iteration for computing the Fitness Centrality of general graphs
- Product Pitt inequalities and signed Boas equivalences for general monotone functions
- Weak and strong convergence of a general splitting approach for monotone multioperator inclusions
- Asymptotics of Nonparametric Estimation under General Non-monotone MAR Missingness: A Nonparametric Maximum Likelihood Approach
BibTeX
@misc{yang2026graphmonotone,
title = {{Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs}},
author = {Yuepeng Yang and Cong Ma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09030},
eprint = {2610.09030},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09030},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs
AU - Yuepeng Yang
AU - Cong Ma
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.09030
UR - https://arxiv.org/abs/2610.09030
AB - 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/β(Ξ»_π) up to logarithmic and dynamic-range factors, where Ξ»_π is the algebraic connectivity of the count-weighted observation graph. This guarantee is graph-monotone since Ξ»_π 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.
ER -