PaperlayerView exact revision on arXiv

Source-linked AI summary

Rank Centrality: Ranking from Pair-wise Comparisons

Sahand Negahban, Sewoong Oh, Devavrat Shah

arXiv:1209.1688v4cs.LGstat.ML

TL;DR

The paper asks how to obtain global rankings and preference-intensity scores from partial pair-wise comparisons. It proposes Rank Centrality, an iterative spectral algorithm interpreted through a random walk, and analyzes its finite-sample accuracy under the BTL model. Its error bound is near-optimal up to logarithmic factors, with performance depending on the comparison graph’s spectral structure.

  • Problem

    The paper studies how to infer item rankings and preference-intensity scores from pair-wise comparisons rather than complete orderings.

  • Method

    Rank Centrality is an iterative spectral ranking algorithm whose scores are stationary probabilities of a random walk on the comparison graph.

  • Results

    Rank Centrality’s error bound is near-optimal up to logarithmic factors, and its performance depends on the comparison graph’s spectral gap.

  • Takeaways & Limitations

    When the comparison graph has a positive spectral gap, Rank Centrality can learn the underlying BTL scores with high probability using graph-structure-dependent sample bounds.

  • Takeaways & Limitations

    The paper notes that its first-order method has a tunable step size and that the implementation did not attempt to optimize it.

Abstract

from arXiv · show

The question of aggregating pair-wise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining a ranking, finding `scores' for each object (e.g. player's rating) is of interest for understanding the intensity of the preferences. In this paper, we propose Rank Centrality, an iterative rank aggregation algorithm for discovering scores for objects (or items) from pair-wise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the score, which we call Rank Centrality, of an object turns out to be its stationary probability under this random walk. To study the efficacy of the algorithm, we consider the popular Bradley-Terry-Luce (BTL) model (equivalent to the Multinomial Logit (MNL) for pair-wise comparisons) in which each object has an associated score which determines the probabilistic outcomes of pair-wise comparisons between objects. In terms of the pair-wise marginal probabilities, which is the main subject of this paper, the MNL model and the BTL model are identical. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, e.g. each item is compared to a subset of randomly chosen items, this leads to dependence on the number of samples that is nearly order-optimal.

1. Introduction

The paper addresses how to infer global rankings and preference-intensity scores from partial, potentially contradictory pair-wise comparisons. It introduces Rank Centrality, a computationally simple spectral method with theoretical guarantees under the BTL model and comparison-graph conditions.

  • Conclusions: Rank Centrality is described as computationally simple, always producing a solution from available data, and near-optimal under a reasonable generative model.Its theoretical justification is tied to the BTL model and to the structure of the comparison graph.
  • Problem: Pair-wise comparison data can be used to infer both an ordering of items and a score indicating preference intensity.The setting uses outcomes between item pairs rather than complete orderings, and explicit numeric scores may be unavailable or inconsistent.
  • Method: Rank Centrality is an iterative rank aggregation algorithm that takes noisy comparisons over a subset of item pairs and outputs scores for every item.It is presented as a distinct spectral-ranking approach built on eigenvector methods.
  • Theory: ω(n log n) random comparisons suffice for Rank Centrality to learn the true BTL score to arbitrary accuracy with high probability as n →∞.Fewer than Ω(n log n) random comparisons cannot even produce a consistent ranking with high probability because the comparison graph can be disconnected.
  • Theory: O(ξ−2 npoly(log n)) comparisons suffice on general comparison graphs, with the Laplacian spectral gap ξ controlling the graph-structure dependence.For Erdős-Rényi comparison graphs, ξ is strictly positive independently of n with high probability, yielding order-optimal performance.
  • Empirical results: Experiments find Rank Centrality identical to BTL maximum-likelihood estimation and better than other popular choices.The paper also states that Rank Centrality and MLE match a Cramer-Rao lower bound across the considered parameter range.

2. Model, Problem Statement and Algorithm

The paper models pair-wise outcomes with BTL scores and estimates those scores using Rank Centrality, a random walk whose stationary distribution yields item ranks.

  • 2.1. Model: Under the BTL model, each item has a positive score, and item i defeats item j with probability determined by w_i and w_j.The model assumes comparison outcomes are conditionally independent, with a fixed number k of comparisons per observed pair.
  • 2.1. Model: Because BTL scores are invariant to positive scaling, the paper represents each equivalence class by a projection onto the standard orthogonal simplex.This makes the score representation unique for measuring distances between estimated and true scores.
  • 2.1. Model: BTL pair-wise marginals are identical to those induced by the MNL model, where random orderings select remaining items proportionally to their scores.This gives pair-wise preference probability w_i/(w_i + w_j).
  • 2.2. Rank Centrality: Rank Centrality constructs a transition matrix from observed pair-wise win fractions, rescales edge weights by 1/dmax, and adds self-loops to make row sums one.The resulting random walk moves toward items in proportion to their observed preference probabilities.
  • 2.2. Rank Centrality: The algorithm assigns each item the stationary probability of this random walk, computed as the limiting distribution or top left eigenvector of P.In the ideal infinite-sample setting, the stationary distribution is proportional to the true BTL score vector when the graph is connected and includes a self-loop.
  • 2.2. Rank Centrality: A unique stationary distribution requires irreducibility, which follows when the comparison graph is connected and both directed edge weights are positive.The paper’s main result bounds the normalized distance between the estimated score vector and the underlying score vector.

3. Main Results

The main results bound Rank Centrality’s score error on general comparison graphs and show near-optimal sample complexity for Erdős–Rényi graphs. Experiments compare its error and robustness with alternative ranking methods on synthetic and real data.

  • 3.2. Rank Centrality: Error bound for random graphs: For Erdős–Rényi comparison graphs, Rank Centrality requires O(npoly(log n)) comparisons and is nearly order-optimal.The random-graph setting yields a strictly positive spectral gap under the stated regime.
  • 3.1. Rank Centrality: Error bound for general graphs: For a connected comparison graph, Theorem 1 gives a high-probability bound on Rank Centrality’s normalized error under BTL-generated outcomes.The guarantee applies when each observed pair is compared k times and k satisfies a graph- and score-dependent lower bound.
  • 3.2. Rank Centrality: Error bound for random graphs: When d = Ω(log n) and kd = ω(log n), the relative error converges to zero as n grows with high probability.The result corresponds to ω(nlog n) total samples in the stated asymptotic regime.
  • 3.1. Rank Centrality: Error bound for general graphs: O(nκ^2ξ^-2poly(log n)) comparisons suffice to learn scores well with high probability on a general graph.Here κ is the degree ratio and ξ is the Laplacian spectral gap, so graph structure enters through ξ^-2.
  • 3.3. Experimental Results: Figure 1 reports error decreasing for Rank Centrality at a rate predicted by the theory and comparable to the maximum likelihood estimator.With fixed d, Borda Count and Ratio Matrix retain strictly positive error as k increases, while transition-matrix design affects performance among Markov-chain methods.
  • 3.3. Experimental Results: On a real dataset, Rank Centrality, the ML estimator, and MC2 are less sensitive to limited comparison data than Borda Count, MC1, MC3, and MC4.The experiments also apply Rank Centrality to NASCAR drivers and ODI cricket teams.

3.4. Information-theoretic lower bound

The paper derives a minimax lower bound for estimating BTL scores under bounded dynamic range and compares it with Rank Centrality’s achievable error rate. In the stated regime, Rank Centrality’s upper bound is minimax-optimal up to logarithmic factors.

  • Minimax formulation: Theorem 3 formulates the minimax problem over all measurable estimators and BTL score vectors with dynamic range at most b.Pairs are sampled with probability d/n, and each selected pair receives k BTL comparison observations.
  • Boundary case: When b = 1, the minimax error is zero because the constant estimator (1/n)1 exactly matches every admissible score vector.The paper notes that the dynamic range is always at least one and uses this as a trivial case.
  • Optimality: For b bounded away from one and above by a constant, Theorem 3 shows that Theorem 2’s upper bound is minimax-optimal up to logarithmic factors in n.The comparison is made in the regime of bounded dynamic range.
  • Numerical comparisons: Numerical comparisons report Rank Centrality’s RMSE as almost indistinguishable from both the ML estimate and the Cramér-Rao bound across tested parameter ranges.The experiments vary k, d, and b; one stated setting uses k = 32, n = 400, d = 60, and b = 10.
  • Graph dependence: The error upper bound depends on the comparison graph’s spectral gap, with larger gaps yielding smaller estimation error.For Erdős-Rényi graphs, Theorem 2 supplies a corresponding Rank Centrality upper bound, while Theorem 3 establishes near-optimality.
  • Numerical comparisons: The Cramér-Rao comparison suggests Rank Centrality reaches the fundamental lower bound and is exactly optimal for a certain class of estimators.The paper also states that MLE achieves near-optimal performance guarantees up to a logarithmic factor.

4. Proofs

The proofs establish convergence for general comparison graphs, specialize the result to Erdős-Rényi graphs using high-probability spectral properties, and prove the minimax lower bound and finite-sample MLE analysis.

  • General graphs: Theorem 1’s convergence proof applies to general comparison graphs and uses spectral theory to obtain an error upper bound.The proof’s main technical issue is establishing the required properties of the Rank Centrality Markov chain.
  • Erdős-Rényi graphs: Theorem 2 follows by showing that Erdős-Rényi graphs satisfy the required spectral properties with high probability.This specializes the general-graph proof to the random-graph setting.
  • Lower bounds and MLE: The remaining proofs establish the information-theoretic lower bound in Theorem 3 and the finite-sample error analysis of MLE in Theorem 4.These results provide the lower-bound and estimator-comparison components of the paper’s analysis.

4.1. Proof of Theorem 1: General graph

The proof analyzes Rank Centrality through the random walk's expected transition matrix, whose stationary distribution is proportional to the weight vector. Reversibility and spectral analysis then control finite-iteration and sampling errors.

  • Expected chain: The expected transition matrix ˜P has stationary distribution ˜π proportional to the weight vector w.When the comparison graph is connected and has self loops, the chain is irreducible and aperiodic.
  • Iteration convergence: When ρ < 1, the iteration-dependent term vanishes as t grows, leaving the error between p_t and ˜π dominated by the fluctuation term.The theorem's bound holds with probability at least 1 − 4n^-C/8 after t = Ω(log n + log b + ...).
  • Sampling fluctuations: The proof requires a lower bound on the number of comparisons per edge, expressed through k and graph- and weight-dependent quantities.The stated condition includes k ≥ 4C^2b^5d_max log n(1/d_minξ)^2.
  • Sampling fluctuations: The fluctuation bound uses concentration inequalities, separating diagonal and off-diagonal components and exploiting independent comparison outcomes.The off-diagonal analysis uses row- and column-sum bounds, with separate treatment according to whether d_max is below or above log n.

4.2. Proof of Theorem 2: Random sampling

The proof of the random-sampling result combines concentration of Erdős–Rényi graph degrees with a positive spectral-gap guarantee. These properties allow the general-graph theorem to yield the stated finite-sample result.

  • Random graph properties: For an Erdős–Rényi graph with average degree d ≥ C′ log n, the degree range is controlled with high probability.Specifically, κ ≤ 3 and (1/2)d ≤ d_min ≤ d_max ≤ (3/2)d.
  • Applying Theorem 1: With these graph properties, Theorem 1 gives the desired result with probability at least 1 − 4n^-C/8 when kd ≥ 288C^2b^5 log n.The proof applies the general theorem after substituting the Erdős–Rényi degree and spectral-gap bounds.
  • Spectral gap: If d ≥ 10C^2 log n, the spectral gap satisfies ξ ≥ 1/2 with probability at least 1 − n^-Cn/(n−d)/8.This supplies the positive-gap condition needed by the general analysis.

4.3. Proof of Theorem 3: Information-theoretic lower bound

The lower-bound proof reduces score estimation to multi-way hypothesis testing over a separated packing of BTL stationary distributions. Information-theoretic inequalities then relate distinguishability to comparison sampling.

  • Testing reduction: The proof converts the stochastic inference problem into multi-way hypothesis testing using a packing set of separated stationary distributions.The constructed vectors lie on the standard orthogonal simplex and are separated by δ.
  • Testing reduction: An incorrect hypothesis index implies estimation error of at least δ/2 from the true stationary distribution.The reduction chooses the closest packed vector to the algorithm's estimate.
  • Information bound: Data processing and Fano's inequality bound the recoverable information through KL divergence between observation distributions under different BTL models.The proof explicitly uses the Markov chain L — ˜π(L) — X — π — ˆL.
  • Information bound: The KL divergence depends on the comparison-sampling design, which samples each pair with probability d/n and compares each sampled pair k times.The observations X_ij are the outcomes of the k comparisons for sampled pair (i,j).
  • Minimax lower bound: The packing construction yields a normalized minimax error lower bound involving (b − 1)/(240(b + 1)√(kd)).The construction also keeps the dynamic range at most b.
  • Packing construction: The random packing construction succeeds with strictly positive probability for n ≥ 90.Uniform concentration and union bounds establish the required separation and coordinate conditions.

4.4. Proof of Theorem 4: Finite sample analysis of MLE

The finite-sample MLE proof links a small empirical loss gradient to parameter accuracy through curvature. It establishes the needed curvature and gradient bounds using concentration and random-matrix arguments.

  • Error reduction: A small gradient of the empirical loss at θ* implies a small estimation error between θ* and θ̂ when the loss has sufficient curvature.With ∥∇L_m(θ*)∥2 ≤ c, the proof obtains ∥∆∥2 ≤ 2c/µ for ∆ = θ̂ − θ*.
  • Curvature: The curvature argument lower-bounds the quadratic sample term by 1/(3n)∥∆∥2^2.This is the key lower bound used to establish the desired parameter-error result.
  • Curvature: With m > 12n log n i.i.d. samples, the curvature lemma holds with probability at least 1 − 1/n.The proof invokes this result as Lemma 9.
  • Gradient concentration: The gradient bound is established from componentwise concentration of mean-zero variables with variance at most 1/n.Bernstein's inequality is applied to each gradient component.
  • Final bound: The resulting probability bounds include 1 − 1/n for the gradient control and a rate term proportional to √(2 log n/(nm)).These bounds are combined under the sample-size condition 12n log n < m.
  • Gradient concentration: Random-matrix concentration is applied to independent self-adjoint matrices to control the quadratic terms used in the finite-sample analysis.The argument applies the cited matrix inequality to both X_l and −X_l.

5. Discussion

The discussion presents Rank Centrality as an iterative pairwise-comparison rank-aggregation algorithm and summarizes its theoretical and empirical performance under the BTL model. Its error can be near-optimal, comparison-graph structure matters, and its empirical computational cost appears lower than MLE.

  • 5. Discussion: Rank Centrality is an iterative algorithm for rank aggregation using pair-wise comparisons, analyzed under the Bradley-Terry-Luce model.The paper compares its estimated scores with scores assumed by the BTL model.
  • 5. Discussion: Analytic finite-sample error bounds yield near-optimal sample dependence for learning scores under random pair selection.The comparison graph structure plays a crucial role in the algorithm’s performance.
  • 5. Discussion: Numerical comparisons with the Cramer-Rao lower bound suggest that Rank Centrality’s error is indistinguishable from this fundamental lower bound.The discussion presents this as evidence of stronger optimality properties than the established bounds alone provide.
  • 5. Discussion: The discussion also analyzes MLE and reports that its empirical computational cost appears higher than Rank Centrality’s.The paper notes that MLE is near order-optimal, like Rank Centrality, while emphasizing the computational comparison.

A. Proof of Lemma 1

This proof bounds a weighted ranking distance by the normalized Euclidean estimation error. It does so by relating pairwise ranking mistakes to coordinate-wise estimation deviations and using concentration and Taylor-expansion arguments.

  • A. Proof of Lemma 1: A ranking mistake between items i and j implies their score difference is bounded by the corresponding estimation deviations.For general pairs, the proof obtains |w_i − w_j| ≤ |w_i − π_i| + |w_j − π_j|.
  • A. Proof of Lemma 1: Substituting the pairwise deviation bound into the weighted distance yields an upper bound by normalized Euclidean distance.The proof explicitly states that D_w(σ) is upper bounded by the normalized Euclidean distance.
  • A. Proof of Lemma 1: Hoeffding’s bound controls the shifted-binomial comparison variable used in the argument.The proof treats C_ij as a zero-mean shifted binomial random variable and uses that it is a sum of bounded terms.
  • A. Proof of Lemma 1: A second-order Taylor expansion is applied for θ ∈ [−ln4/3, ln4/3] to complete the claimed result.The resulting display is substituted into the preceding relation.

B. Proof of Lemma 7

This proof replaces the nonsymmetric matrix L = D^-1B with the symmetric matrix L̃ = D^-1/2BD^-1/2, which has the same eigenvalues. It then uses singular-value properties to analyze the relevant spectrum.

  • B. Proof of Lemma 7: The proof introduces L̃ = D^-1/2BD^-1/2 because it has the same eigenvalues as L = D^-1B.Symmetry makes the eigenvalues of L̃ equal to its singular values up to sign.
  • B. Proof of Lemma 7: The singular values of L̃ are ordered as σ_1(L̃) ≥ σ_2(L̃) ≥ ..., with largest singular value equal to 1.The proof notes this normalization using the vector 1/√n.
  • B. Proof of Lemma 7: The spectral argument invokes a lemma for adjacency matrices of Erdős-Rényi graphs G(n,d/n) with d ≥ C log n.D is the corresponding diagonal degree matrix.
  • B. Proof of Lemma 7: Applying the established spectral bound yields the lemma’s result.The proof states that the preceding bound is applied directly to obtain the claimed result.

B.1. Proof of Lemma 13

This proof establishes spectral bounds for a random Erdős-Rényi adjacency matrix by decomposing the degree matrix and applying matrix concentration. The result holds with an explicitly stated high probability.

  • B.1. Proof of Lemma 13: The proof first establishes the needed spectral statement in two parts.It begins by focusing on the first component of the result.
  • B.1. Proof of Lemma 13: With probability at least 1 − n^−Cn/(n−d)8, the resulting spectral bound holds.The proof also states a related probability form involving 2n^−Cn/(n−d)/8.
  • B.1. Proof of Lemma 13: Lemma 14 applies to independent, random, self-adjoint matrices with zero mean and an almost-sure eigenvalue bound.The assumptions are E X_k = 0 and λ_max(X_k) ≤ R almost surely.
  • B.1. Proof of Lemma 13: The random adjacency matrix B is represented using Bernoulli variables with parameter d/n, giving R = 1 almost surely and σ_2 = d(1 − d/n).The proof sets t = C√(d log n) when applying the lemma.
  • B.1. Proof of Lemma 13: Bernstein’s inequality bounds the degree-matrix deviation, while high-probability degree and adjacency bounds control the remaining terms.The proof states ∥E∥_2 ≤ 10C√log n and uses high-probability lower and upper bounds on degrees and ∥B∥_2.
Loading 1209.1688v4…