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/\sqrt{\lambda_{\mathcal{D}}}$ up to logarithmic and dynamic-range factors, where $\lambda_{\mathcal{D}}$ is the algebraic connectivity of the count-weighted observation graph. This guarantee is graph-monotone since $\lambda_{\mathcal{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.