Byzantine Spectral Ranking
Authors: Arnhav Datar
Arun Rajkumar
John Augustine
Venue: NeurIPS 2022 Accept (2022)
Keywords: ranking
learning to rank
pairwise comparisons
Byzantine

Abstract: We study the problem of rank aggregation where the goal is to obtain a global ranking by aggregating pair-wise comparisons of voters over a set of items. We consider an adversarial setting where the voters are partitioned into two sets. The first set votes in a stochastic manner according to the popular score-based Bradley-Terry-Luce (BTL) model for pairwise comparisons. The second set comprises malicious Byzantine voters trying to deteriorate the ranking. We consider a strongly-adversarial scenario where the Byzantine voters know the BTL scores, the votes of the good voters, the algorithm, and can collude with each other. We first show that the popular spectral ranking based Rank-Centrality algorithm, though optimal for the BTL model, does not perform well even when a small constant fraction of the voters are Byzantine.

We introduce the Byzantine Spectral Ranking Algorithm (and a faster variant of it), which produces a reliable ranking when the number of good voters exceeds the number of Byzantine voters. We show that no algorithm can produce a satisfactory ranking with probability > 1/2 for all BTL weights when there are more Byzantine voters than good voters, showing that our algorithm works for all possible population fractions. We support our theoretical results with experimental results on synthetic and real datasets to demonstrate the failure of the Rank-Centrality algorithm under several adversarial scenarios and how the proposed Byzantine Spectral Ranking algorithm is robust in obtaining good rankings.

Byzantine Spectral Ranking
Arnhav Datar Indian Institute of Technology. Madras adatar@cmu. edu
Arun Rajkumar* Indian Institute Technology, Madras arunrêcse. iitm. ac in
John Augustine!
Indian Institute of Technology, Madras augustine@i tm. in
Abstract
We study the problem of rank aggregation where the goal is to obtain global ranking by aggregating pair-wise comparisons of voters over a set of objects. We consider an adversarial setting where the voters are partitioned into two sets. The first set votes in stochastic manner according to the popular score-based Bradley- Terry-Luce (BTL) model for pairwise comparisons. The second set comprises malicious Byzantine voters trying to deteriorate the ranking. We consider a strongly- adversarial scenario where the Byzantine voters know the BTL scores, the votes of the good voters, the algorithm, and can collude with each other. We first show that the popular spectral ranking based Rank- Centrality algorithm, though optimal for the BTL model, does not perform well even when a small constant fraction of the voters Byzantine.
We introduce the Byzantine Spectral Ranking Algorithm (and faster variant of it), which produces a reliable ranking when the number of good voters exceeds the number of Byzantine voters. We show that no algorithm can produce a satisfactory ranking with probability > 1/2 for all BTL weights when there are more Byzan- tine voters than good voters, showing that our algorithm works for all possible population fractions. We support our theoretical results with experimental results on synthetic and real datasets to demonstrate the failure of the Kank-Centralitg algorithm under several adversarial scenarios and how the proposed Byzantine Spectral Ranking algorithm robust obtaining good rankings.
Introduction
Rank aggregation is a fundamental task wide spectrum of learning and social contexts such as social choice (Soufiani et al.] [2014] Caplin and Nalebuff, 1991]. web search and information retrieval BBiin and Page. 1998 Dwork et 2001], recommendation systems [Baltrunas et al.) 2010 and crowd sourcing CCenn et al. 2013). Given pairwise comparison information over set of objects, the goal to identify ranking that best respects the revealed preferences. Frequently, we also interested in the scores associated with the objects deduce the intensity of the resulting preference. There have been several solutions to this problem including Spectral Ranking methods such Rank Cent-Centryl (Negahban et al. 2017 and MLE methods [Ford 1957].
The Bradley-Terry-Luce (BTI.) model (Bradley and Terry 1952 Luce 1959 has been prevalent for a vast variety of ranking algorithms. The BTL model assumes that there are n objects that are to be
"Supported part by the Robert Bosch Centre for Data Science and Artificial Intelligence, IIT Madras. Supppoteed in part by the Cryptography, Cybersecurity, and Distributed Trust PCoE and the Accenture CoE IIT Madras.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

compared and each of these objects has positive weight (w;) associated with itself. Whenever any voter is asked a query for pair, the voter claims is better than with probability w;(ww; + w,) independently at random. However, the BTL model assumes that all voters are identical and use the same probabilistic strategy for voting. Generally, in crowd-sourced settings, voters differ significantly from each other. Some of the voters may be spammers or even direct competitors of the entity ranking the objects, leading to data poisoning [Sun et al. 2021]. To model this situation, we assume that there a split in the population. We consider that there are K F good voters and IF Byzantine voters, to appropriately model the division the voters. The good voters vote according to the BTL model, while the Byzantine voters can potentially be controlled by an adversary that centrally coordinate their behavior.
1.1 Overview of our Results
We naturally initially consider the tolerance of the Rank-Centrality algorithm against a constant fraction of Byzantine voters. Negahban al. [201]] showed that for Erdös-Rényi pairwise- comparison graph G(n, p) we have
Theorem 1 (Informal from Negahban et al. Rank Cent-Centr algorithm outputs
(017 P E (1logn//) and k E 9((1) then the (x) such that with high probability
π Āl| EO
(v
log
kem
Here the true weights of the objects and k is the number of voter queries asked per edge in G. We can see that when k E (1) the RHS goes to O as n goes to cc. We show that strategy as simple as all Byzantine voters voting the reverse of the weights causes the Sank-Centrality algorithm to output weights far from true weights with high probability.
Theorem 2 (Informal). There exists strategy that the Byzantine voters can use such that the Rank-Centraie algorithm outputs distribution a such that with high probability
E 2(1))
provided there constant fraction of Byzantine voters
Even simple algorithms that output the same weights regardless of the voter's 's responses also give ((1) error. To tackle this situation, we propose Byzantine Spectral Ranking, an algorithm that runs in polynomial time to remove some of the voters such that the Cank-CCntrality algorithm can be applied. As long as the proportion of Byzantine voters is bounded strictly below 1/2, the algorithm removes some voters such that the remaining Byzantine voters are unlikely cause the Rank-Centrality algorithm to deviate significantly.
Theorem 3 (Informal). For a range of values of there exists an O(n?)-time algorithm that removes voters such that with high probability we have:
dmaz
E
k
Here dmaz is the maximum degree of the comparison graph. Finally, we also show that when F 2 K/2 there algorithm that can solve this problem for all weights with probability > 1/2, by coming up with a strategy that the Byzantine voters can use for two different weight distributions, and showing therefore that the algorithm must fail in at least one of the weight distributions.
Theorem 4 (Informal). F K/2, then there is algorithm that can for all weights (#) with probability > 0.5, give weight distribution (x") such that
#|
o(1)
Whenever say with high probability with probability 1 + for

---

1.2
Related Works
In recent times, there has been lot of work on building robust machine learning algorithms Blan-
chard et al. 2017 El Mhamdi et al. 2018 Li et al. [2000] El-Mhamdi et al. 2021 Chen et al. 2018
Wu et al. 2021 that are resilient Byzantine faults.
Ranking from pairwise comparisons has been a very active field of research and there have been multiple algorithms proposed with regard to the BTL model [Negahban et al. 2017 Agarwal et al.) 2018 Rajkumar and Agarwal| 2014 Chen and Suh 2013]. One of the most popular algorithms proposed in recent times has been the Rank-Centrality algorithm, [Negabban
al. [017]] were able
to show an apper-bound on the relative L2-error (between true weights and proposed weights) such
that the relative Lg-error goes 0 for larger n. They did this by finding the stationary distribution of matrix P which was defined as
An dmar
if if
Pij
Aman Ekgi Ack
Here Aiy is the number of times é beats) j in l queries divided by k, if (i. E E(G) else A, = 0. The pseudocode can be found in Algorithm [ They also show that their algorithm outperformed other algorithms on various datasets. As our work builds on Negahban et al. [2017) we have included primer to Rank-Centrality in the Appendix
Algorithm 1 RRan--Cenni Rank-Cennrality
Require: n objects compare, E the set of edges between these objects, A the edge weights calculated based on the voter inputs.
Ensure: A weighing of the objects such that the output weight is fairly close to input hidden weights.
1: Compute the transition matrix P according to Equation] [
2: Compute the stationary distribution æ (as the limit of p = ps P).
Besides research on adversarial attacks in ranking, there has also been research on how the robustness of the ranking algorithms when exposed to noise. (ucuringu (2016) proposed Sync-Rank, by viewing the ranking problem as instance of the group synchronization problem over the group SO(2) of planar rotations. This led to a robust algorithm for ranking from pairwise comparisons, as was verified by synthetic and real-world data. Mohajer and Suh (2016) worked on a stochastic noise model in order to find top-K rankings. They were able to show an upper-bound on the minimum number of samples required for ranking and were able to provide a linear-time algorithm that achieved the bound. However, both of these works [Cucuringu 2016 Mobajer and Suh 2016) were primarily tackling the ranking problem when there was noisy and incomplete data as opposed to an adversary who was trying to disrupt the algorithm.
Suh al. 2017] worked the adversarial ranking problem considering two cases one where the fraction of adversarial voters is known and is unknown. They got results that were asymptotically equivalent to Chen and Suh (2015)' 's Spectral-MLE algorithm despite the presence of adversarial voters. However, they worked with the significantly weaker assumption that the adversarial voters will vote exactly opposite the faithful voters (i.e. if the good voters voted that is better than wy
with probability wetwi
). Our setting is much more general in that we do not make any assumptions regarding the Byzantine voters.
wi; then the Byzantine voters voted with probability mit
Agarwal et 2020 worked on rank aggregation when edges in the graph were compromised. They were able to prove fundamental results regarding the identifiability of weights for both general graphs as well as Erdös-Réns Rényi graphs. They also came up with polynomial- timem algorithms for identifying these weights. However, their model is significantly different from ours. They assume that some of the comparisons in the comparison graphs might have been completely compromised while the others are free from any kind of corrtuption. In practice this is unlikely to happen, we assume a stronger model where every edge can have good and Byzantine voters. A detailed comparison with Agarwal et al. 2020 made in section 3.5
3

---

2 Problem Setting
Given a set of objects, our goal is the obtain a ranking from set of pairwise comparisons over the objects. We assume that the pairs to be compared are determined by an Erdōs-Rényi comparison graph ((n,, p) = E). Each edge in the graph corresponds to a pair that can be compared and we allow at most i comparisons per pair.
The pairs can be compared by voters who fall into one of two categories good or Byzantine. Out of K' total voters, F are assumed to be Byzantine. Every good voter when queried to compare pair of objects, votes stochastically according by a weight/score vector w E R& where the probability of preferring object i over object is given by wy The Byzantine voters on the other hand can vote however they wish sstochasticddeeermnnisttt wetww,
Bradley-Terry-
(BTL. preference model parametrized
To make the problem general we consider a powerful central-adversary that could potentially control all of the Byzantine voters. We assume that the Byzantine adversary knows (1) The queries asked to
the good voters and their corresponding votes (2) The comparison graph G(n, p) (3) The learning
algorithm that is used to produce the ranking (4) The underlying true BTL weights of the objects that the good voters use to produce their comparisons.
We assume that both the good voters and the byzantine voters will produce the same output when the same pair is asked to be compared multiple times by them
The goal of a learning algorithm is to use the least number of voter comparisons to output a score vector that is close to the true scores. The learning algorithm is allowed choose any voter to compare any pair of objects. However, it does not know the type of voter good or Byzantine and naturally, a good algorithm must be robust the presence of the powerful Byzantine voters. Finally, we work in the passive setting, where learning algorithm is needed to fix the pair to voter mapping apriori before the votes are collected.
3 Results for the Erdós-Rény: Graph
We focus our efforts on the Frdös-Rényi graph primarily because it has been heavily studied in the context of rankings. We pay careful attention to the E n//). We go on to find that our algorithms turned out to be exponential in terms of the degree. This makes the Erdös-Rény: Rényi graph an optimal candidate for working out our algorithms because the degrees of the Erdös-Rény: Rényi graph will also be logarithmic with high probability, therefore giving polynomial-tine algorithms.
3.1 Rank-Centrality Failure
We initially try to motivate the need for a robust version of the that even a simple strategy from Byzantine adversary will lead to an unsuitable ranking. In this scenario, the Byzantine adversary does not know the comparison graph, nor does it know the votes of good voters, and still can beat the Rank-Centralin algorithm. Formally we show that:
algorithm by showing
Theorem 5. Given n objects, let the comparison graph be G(n, p). Each pair in G is compared times by voters chosen uniformly at random amongst the K voters. If all Byzantine voters vote according to the opposite-weiie strategy in an Erdös-Rénv Rényi graph with p = C log n/n n then there exists a for which the Rank- CentraCyyy algorithm will output a π such that
π
C Clogn n
b-
F
(206 + b+ 2bC (oggg)
8 2v2b6++1
+)
K
with probability 2 1 b = maxx,j w//wy.
Here b is the skew in object weights i.e.
n P HOAKS
Tog w/e
T
Here when we say the apposite-weigh strategy we mean a strategy where the Byzantine voter will vote for i if wi S Wy otherwise will vote for j. If we carefully examine the RHS, we that the first term asymptotically converges 25- The third term is also clearly constant if there is a constant fraction of Byzantine voters. Therefore, showing the existence of a strategy that will with high
1
'This ensures that simple algorithms which query all voters to vote on the same pair multiple times and obtain a median preference will not work.

---

probability, significantly deviate the weights given by the Rank-Centralin algorithm. The detailed analysis can be found in Appendix A.2
Proof Sketch. We initially show that
| (2vb b11)
|T|
Here и is the stationary distribution of the transition matrix (P) defined in Equation I and A denotes the fluctuation of the transition matrix around its mean (P), such that A = P P. We initially prove that || will most be + dmazs since there are most dmaz terms any row or column and each term can deviate by at most 1. Following this, we show that with probability 2 nC78-T will have dmaar I 2C log 2C'oog Finally, show that ||=T will be Q(pn) with probability 2 1 n low n/8 by constructing weight-distributioo where half the weights are low and half were high. An arbitrary weight-distribution could not be used because if - ......... we would get # = 0 for all A. This because the row sum of P and P will always be 1.
3.2 Byzantine Spectral Ranking
In this section, we propose a novel algorithm called Byzantine Spectral Ranking (BSR). The BSR algorithm relies asking multiple voters multiple queries and based the collective response decides whether a voter is acting suspiciously or whether it is plausible that the voter might be good voter. For each object to be compared, k voters compare with all of the d; objects (leading to kd; comparisons for each voter). Based on the voter's responses, ensures that constant fraction of good voters remain and that if any Byzantine voters remain then these voters have votes similar good voters. Intuitively, the BSR algorithm goes over every single subset of [d:] and tries to find if the Byzantine voters have collectively voted strongly in favor or against this subset. The pseudocode can be found in Algorithm 2
take of d; objects compare it against and have
try to eliminate voters who likely be Byzantine. The BSR algorithm
Algorithm Byzantine Spectral Ranking
Require: n objects, K voters, Comparison graph G, & comparisons allowed per edge, parameter Q- Ensure: Weights (अ) for each of the objects in [n]
1: procedure Bound_SSu__Devattoonn Deviations(i. S, d, kt a))
2: Pick & voters randomly from the voter set ([L..... .., K])
3: The voters are queried to compare all objects in with
k x queries total T will be k x d matrix
4: T represents the binary representation of the voters' inputs
5:
5
V dlogg K
We show later that Q needs to be 2 1
6:
< [0]24
7:
for each & E {1, - do U TE
8:
9:
i +- Median(U)
M[]][[]]
if voter is 56 away from mn and otherwise
11: end for
max_ou out +- 8k1-Q 861-a
13: Remove voters with M [[][u] if the sum of M is 2 max_out for some &
Return leftover votes
15: end procedure
a 1 1-11-ogg log dmaz//lg
a is parameter whose value set during analysis
17: for each object to be compared do
18: votes + Bound SaanddSumm__u Deviatiivaii,ni (V), d,, k, a)
19: Using votes update P as described in Equation
20: end for
21: Compute the stationary distribution which is the limit of p P.P. P.
5

---

3.2.1 Analysis
The detailed analysis can be found in Appendix A..3 Based on the proof of the Rank- Rank-Centrality Convergence the only result which does not hold for Byzantine voters Lemma 3, where they bound the 2-norm of the A matrix. We show that:
Lemma 6. For an Erdös-Rényi graph with 2 10C² log n/n with ls E ((mp) comparisons per
edge, algorithm removes some voters such that we have:
dmaa k
log K
|| S 80 max
dinin
with probability 2 1 16n (1- 1.50%)
Proof Sketch. Sketch. proving that ae [Ciyl | > kd is bounded. Cip is defined as kAi - kpy, where Pij wy Since it is sum of d, absolute values it can be upper-bounded by considering the union bound over all 24. combinations for this sum.
Proving that ||||| is bounded with high probability turns out be equivalent
wy
We initially show that with high probability for all 2d values of & the mean(í)) that we compute in the BSR algorithm will only be (8)) away from the expected mean. This gives us a good check for whether a voter is acting out of the ordinary or not. The algorithm then filters out voters that are collectively acting out the ordinary for particular Ç. We show that at the end of these removals, the number of voters will only be a constant factor far from k. i.e. most of the good voters will be retained. Finally, we show an upper-boune bound on the row sum of the absolute values of the deviations of the remaining Byzantine voters to complete the proof.
Intuitively, we get the terms dmea/k and Vlog k/dmin in Lemma 6 by considering the maximum average deviation for the row sum that can be caused for any & by the Byzantine voters. This can be written max_ou out voters having deviation of d and the remaining & voters having deviation of Therefore we can see that the overall deviation will be 1 [max_out dd+ 6.).. kd
k). Substituting the
values of the parameters, and choosing an appropriate Q we get O (max (duuu V dmin
log k
Finally,
using lemma 6 and a few lemmas from Negahban et al. [217]] we conclude that:
Theorem 7. Given n objects, let the comparison graph be G(n. p). Each pair in G compared k times with the outcomes of comparisons produced as per the Byzantine-Bis BBT model with weights [wi, .u...... Wn.. Then there exists an algorithm such that when F < K(1 - e)/2, p 2 10C log n/n,
>> 0 and k 2 18dmaz / the following bound on the error
T
dmax k
log & dmin
< 4/2 max
holds with probability 2 6n Cn/ 16n (1-(1-)))
Remark. The BSR algorithm gives a suitable ranking in polynomial time, but is fairly slow as the complexity will be ((n509+1), which is not suitable for larger values of and C.
Remark. Our process of filtering out Byzantine voters tightly tied to the analysis of the Rank- Centrality algorithm and the procedure to remove voters may not be suitable for other algorithms. The advantage of tying the removal procedure the ranking algorithm is that we would not remove voters who may vote in an adversarial fashion, but do not significantly affect the row sum of the absolute difference between the empirical and true Markov chain transition matrices. An algorithm that tries to explicitly identify Byzantine voters might end up removing such voters too (and hence their votes for other useful pairs) which might be counter- pronttrrrroducive..
3.3 Fast Byzantine Spectral Ranking
While Algorithm 2 performs asymptotically similar to the Rank-Centrality algorithm, it is fairly slow requiring at least 0(2dmi= n) time. We now present the Fast Byzantine Spectral Rank- ing (FBSR) Algorithm for more practical settings. Essentially in previous algorithm, ensure

---

that P(EJEaL Cyyl > kdys) is upper- hoper--ounded. This takes up lot of time because essentially we iterate over all ç E [-1,1]at in the algorithm. But, this can be improved. If d, 5 logz n we can bucket the entries into / buckets (B]..... B3l) of size log2 each. Therefore an equivalent formula- tion would be to upper-bound Σi= ([ jeBs & jeB, |Cygl kd Here instead of summing up d, absolute values, we will only be summing up log, values 3 times.
Algorithm 3 Fast Byzantine Spectral Ranking
I: 1- log((2 + C'88) log n log k
2: for each object to be compared do
3: max_ mize_izze< <- log2
Can be made larger than log2
4: B
d, 5: Split (i) into / buckets such that they are equally sized and let them be [Bi...., n.....,,p. Bal
6: for bucket f to 3 do
7: votes < Bound_Sunu
Buucket size Bbucket). ), k. oi)
8:
Using votes update as described in Equation
9: end for
end for
11: Compute the stationary distribution æ which is the limit of p!+1 = P.P.. P.
Theorem 8. Given n objects, let the comparison graph be G(n. p). Each pair in G is compared times with the outcomes of comparisons produced as per the Byzantine-BTT model with weights [wi...., wn Then there exists an algorithm such that when F S K(1 e)/ p = 10C log n/n,
> O, and h 2 18(2 + C/8) logn/t n/e² the following bound on the error
log n k
log logn
I 480 max
log
holds with probability 2 1 - (6 + 240C )n-
CC/8 that runs in One²) time
The detailed analysis can be found in Appendix A.4
3.4 An Impossibility Result and optimality of FBSR
The main idea in the BSR algorithm was the estimation of accurate mean for all values of &. However, we can see that finding the mean can become very challenging if the Byzantine voters outnumber the good voters. This because the Byzantine voters can always create shifted binomial distribution and trick us into believing that entirely different value is the mean.
We answer natural question: is it even possible to find algorithms when F crosses K/2? We prove a fundamental result showing that for any ranking algorithm to give a satisfactory result, a majority of good voters will always be required. Formally show that:
Theorem 9. If F 2 K/2, then no algorithm can for all weights (i), output weights (Λ*) such that
< f(n)
with probability > 1/2, where f(n) is a function that converges to 0 goes
Proof Sketch. We prove this result by contradiction, let us suppose there is an algorithm A which give a satisfactory ranking for all weights. We consider the F = K/2 case, the case where F > K/2 can clearly be reduced to the F K/2 case.
We then consider two instances: (1) Good voters vote according to स and the Byzantine voters vote according 7'. (2) Byzantine voters vote according to स and the good voters vote according to #' We go on to claim that when F = K/2 these instances are indistinguishable to any algorithm. Since A succeeds with probability > 1/2 for any instance, we can say by using the union bound that there must be x" such that it is close to both मे and #'. We can then choose the values of म and n' such that they are far from each other and therefore showing that there no at that is close to both and H'. Giving contradiction.
7

---

The detailed proof can be found in Appendix A.5
Remark. This impossibility consequently shows that the FBSR algorithm (cf. Theorem g is optimal in terms of tolerance towards the Byzantine fraction (F/ K).
3.5 Comparison with Agarwal et al.
2020
While the setting of Agarwal ct al. 2020 is different from our setting as mentioned in Section 1.2 if
we were to consider both works in Byzantine voter setting a comparison could be made by considering an edge that has a Byzantine voter to be corrupted as per their model. Here, their algorithm ,to have valid convergence proof, needs & E 221lgg nt). This would imply that F/K E Ollg l/ log" n) for the sparse graphs and F/K E O(1/ log n) for denser graphs. Our algorithms can potentially tolerate significantly higher corruption rate of 1/2.
Another way to compare our results with Agarwal et al. 2020 would be to set lc (loo n). p (log / n//n) for our model and k' = 1,p = =pk/k'' for their model. This allocation ensures only single voter per edge for their model and equal number of comparisons in expectation. We see that their algorithm does not converge (L1 E O(Vlogn)), while our algorithms converges
[Ln E O max
log
log kk
Furthermore, our algorithm can handle a corruption rate of 1/2
log
while their algorithm can handle a corruption rate of O (log log n// log T2 5
Experimental Results
In this section, we confirm our theoretical bounds with experiments conducted on synthetic and real data. While truly Byzantine strategies might be hard to find and can even be computationally infeasible, we consider some practically possible strategies. We show the performance of Rank- Centrality against these strategies, supporting our results in section 3.1 We then proceed to show that these strategies are not as effective against the BSR/FBSR algorithm which gives better rankings.
Experimental Settings: We see that for the FBSR Algorithm to work well we need the existence of least few entries that are at a distance 2 56 from mh. However, since we are summing up log n entries we will need 56 < log n. Otherwise, the BSR algorithm will run exactly as the Rank-Centralicy algorithm. Using the value of d from Algorithm 3 and setting Q 1 and using k 2 log n we get:
25 2
log log n S log
While asymptotically true, we see that the RHS only becomes greater than the LHS when 2 1.18 x 1021, However, as our proof was designed to work against any Byzantine strategy, and at the same time the convergence derivation of Negahban et al. [2017] was fairly loose (for example, the union bound of 2d probabilities ensure the sum of absolute terms is bounded) the FBSR algorithm empirically works for variety of strategies even for significantly smaller thresholds. We applied the FBSR Algorithm with the following modifications considering the smaller i and n values: (1) setting 55- 1 / sizee( B and (2) setting max_ out as k/20. All experimental results in sections and 4 have been taken by taking the mean over 10 random trials.
Synthetic Data: We consider the following parameters in our testing (1) n 200 (2) k = 100
(3) p = 20 2og n/'n and (4) wi = Uniform(1, 11, 100). These are then normalized such that Σ म, = 1. We compare our model with the Rank- cank-Centrality algorithm on synthetic data. We consider four potential strategies used by Byzantine voters:
(1) Fixed Order Vote: The Byzantine voters vote according to some random pre-determined order. This is a fairly simple strategy that does not even require the Byzantine voters to know the स values.
Opposite Vole: The Byzantine voters vote exactly the reverse of the weights. We had shown in section 3.1 that this strategy leads to a failure for some weights.
$ theyy also come up with an algorithm for denser graphs that can handle corruption rate of 1/4, however the algorithm has worse time- complexity and requires p E n-1 for
0
8

---

uppiino PCC
Readest dur yron
0.0
530
0.6
608
3.00
010
0.21
1.0
200
Figure 1: Le vs K/K
Figure 2: T vs F/K
Figure 3: L2 v
(3) Opposite Vote Probabilistic: The Byzantine voters are equivalent to good voters, except their final answer is flipped. For example, the Byzantine voters will vote for object j with probability wy and vote for object with probability uy++" sytw;
Wi
(4) Random Subset: For each pair, the Byzantine voters either decide to behave like good voters with half probability or decide to opposite vote.
Figures D and 2 demonstrate the performance of the Rank-Centrality algorithm and the FBSR algorithm against the aforementioned strategies. For Figure [ we plot the relative L2-Error against the Byzantine Fraction (F/ K). Similar to our results in section 3.1 we see that for most strategies the relative T-g-Error for the Rank-Centrality Algorithm grows lineally with F/K. We can see that the relative L2-Error for both Fixed Order Vote and Opposite Vote strategies are fairly high for the Sonk-Centrality algorithm and that the Fixed Order Vote dominates the relative -2-Error for the FBSR algorithm. However, even though the Fixed Order Vote is the best strategy against the FBSR algorithm. The FBSR algorithm is still able to perform around two times better than the Rank-Centrality algorithm across all values of F/K.
We also confirm that our rankings are close to the actual rankings. To do this we consider Kendall's Tau Correlation (Kendall 1938) between our ranking and the actual ranking. From Figure 2 we see that for the Rank-Centrality algorithm, the Opposite Vote strategy is able to give very low values of т. When the Byzantine fraction is around 0.3 we get Kendall's s Tau Correlation close to 0 (essentially random ranking). We also see that the FBSR algorithm is able to give better results for all strategics.
To further show the convergence of the algorithms in the Byzantine-B -BTL model for larger n, we plot the relative Lg error and Kendall's Tau Correlation against the number of objects Figures and 4 for the Fixed Order Vote strategy. We consider values of F/K in [0.1, 0.2]. These results come when we have set k n. We see that for large range of the number of objects both metries have remained constant for the Rank- Centrality algorithm thus supporting our hypothesis. On the other hand, we see that as we increase the number of objects the L2-error gradually falls and the Kendall's Tau Correlation gradually increases. The rather slow descent of the relative L2-error is backed by
Theorem where we see that for larger l the relative L2 error is E O (v lng Ing 22
log
Real Data: Experimentation with real data was not straightforward, considering that most datasets do not have voter labels nor do they have voter queries as requested by the BSR algorithm (one voter always asked multiple queries of the form (i.j) where is fixed and j is varied). To get around this issue, we use complete rankings. We consider the Sushi dataset comprising 5000 voters ordering the 10 sushis from most preferred to least preferred. Given the preference order, we get 45 pairwise votes from each of the voters. Since we are assuming that we are dealing with permutations here, we assume the Byzantine voters can use the following strategies:
(1) Fixed Order Vote / Opposite Vote: Same as previously defined, but this time the entire permutation is given.
(2) Opposite Random Flips: Each Byzantine voter starts with the opposite permutation and then swaps some of the objects random.
Since the Sushi dataset has many voters we do not use our (2)nd modification mentioned above. We compute the true weights by applying the Rank-Centrality algorithm directly (thus the Rank-Centrality algorithm has a big advantage, especially for smaller weights). Figures 5 and show the Rank- Centrality algorithm and the BSR algorithm's performance. We that the BSR algorithm achieves

---

Konk Centrollty and BDK, ETIEE
Cantrrlitrlltt
075
Don Vida 1330
0.2
Duuaatc yol 1043
011
2041
020
die Wiew (68)
Oppecile fandon 1853)
stte Kondoe HKC
110
11
250
0000 3422
65n vaaz 111 a.14 BLD. 1222
5403 8:50
6220
Figure 4: vs
Figure S: Sushi: Le
Figure 6: Sushi:
lower relative Lg-crrors/Kendal's Tau Correlation for most Byzantine fractions and strategies. The comparatively small improvement in Kendall's Tau Correlation is attributed a rather small difference in the weights of the various Sushi (5 sushis have weights [0.085, 0.13).
5 Conclusion and Further Work
We studied the potential disruption that Byzantine voters can do the widely-used Rank- cent-Certrllity algorithm and proposed fast solutions to counter the same. Our algorithms and analysis techniques quite non-trivial and indicate to us the need for developing this theory further. We require E O(log n) and k E ((logn)) n)) for the success of the BSR and FBSR algorithms. However, (21). An interesting direction would be to explore whether sub-logarithmic values of k will be possible. Alternatively, a lower bound on the number required votes per edge for algorithm succeed with constant probability would also be an interesting direction.
Negahban
[2017] only required d E 2(log n) and
References
A. Agarwal, Patil, and S. Agarwal. Accelerated spectral ranking. In Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 70-79, PMLR, 10-15 Jul 2018. URL htttps://proceedinggg
mlr. wateeemmrmpprrrreeee press/v80/ agwawalwaaaaaa 18b. h8m.
A. Agarwal, S. Agarwal. S. Khanna, and P. Patil. Rank aggregation from pairwise comparisons in the presence adversarial corruptions. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 85 95. PMLR, 7 2020. URL httpss:/ mlr prrsss v1 v119/agarwa 20a. html
L. Baltrunas, T. Makcinskas, and F. Ricci. Group recommendations with rank aggregation and collaborative filtering. In Proceedings of the Fourth ACM Conference on Recommender Systems, RecSys 10, page 119-126, New York, NY, USA, 2010. Association for Computing Machinery, ISBN 605558660 1864708. 1864733
doi: 00.1145/186700,, 1864733.
URL htttps://oot orgoorgg/// 12g/10..1 1145/
P. Blanchard, F. M. El Mhamdi, R. Guerraoui, and J. Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http::::ttpccceeeteeee .nurips cttpsscccccpp/////p/ -aper .pff
R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
S. Brin and L. Page. The anatomy of large-scale hypertextual web search engine. In Proceedings of the Seventh International Conference on World Wide Web WWW7, page 107-117, NLD, 1998. Elsevier Science Publishers B. V.
10

---

A. Caplin and B. Nalebuff. Aggregation and social choice: A mean voter theorem. Econometrica, 59 (1):1-23, 1991. ISSN 00129682, 14680262. http:tt///nw.jjttoo http:://ww...ssoooorr///aaa/////
org/stabble/293223
X. Chen, P. N. Bennett, K. Collins-Thompsee and E. Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, WSDM 13, page 193-202, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781 7781450318693
doi: 10.1 00.11452233336.244444222 URL
https://doi.onn org/10. 1145/ 243355/ 2433420
Y. Chen and C. Suh. Spectral mle: Top-k rank aggregation from pairwise comparisons. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICML' 15, page 37 1-380. JMLR.org. 2015.
Y. Chen, L. Su, and J. Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. SIGMETRICS Perform. Eval. Rev., 46(1):96, jun 2018. ISSN 0163-5999. doi: 10.1145/32920400.22 19655. URL BtRp:tts::///o// org/ 10. 111111192///// 3219665
M. Cucuringu. Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigenvector and sdp synchronization. IEEE Transactions on Network Science and Engineering, 3(1):58-79, 2016. doi: 10. N0.1109/TNSE22211255533
C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation methods for the web. In
Proceedings of the 10th International Conference on World Wide Web, WWW '01, page 613-622, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581 133480. doi:
(1144//71120.37222
URL https:://oiii..... orgo 10. 1145/37199/ 372165
E. M. EI Mhamdi, R. Guerraoui, and S. Rouault. The hidden vulnerability of distributed learning in Byzantium. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3521-3530. PMLR, 10-15 Jul 2018. URL httpttttt/s//ooeeee fttttp:://prcceednngg.
.ml.eeediiinmmmm..mm..mmmmm.mm.. mlr press/ v80 //hamdaamid i 18a. html
E. M. El-Mhandi, S. Farhadkhani, R. Guerraoui, Guirguis, L.-N. Hoang, and Rouault. Col- laborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning). In M. Ranzato, A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 25044-25057, Curran Associates, Inc., 2021, URL htRRss/ttt::////t /ttp//tttt////rreeddiii neurips wttpppsccccppppp////////// (2cc333962266882226333333333
pdf
L. R. Ford. Solution of a ranking problem from binary comparisons. The American Mathematical Monthly, 6488)338-3,, 1957. ISSN 00029890, 19300972. URL http://www: jaw.rrotoorooooo stable/2308513
M. Kendall. NEW MEASURE OF RANK CORRELATION. Biometrika, 30(1-2):81-93, 1938. ISSN 0006-3444. doi: 10. 10.10993/iiomet330.-22288 URL https:://di..rrg bi biomet/30.1-2.88
J. Li, W. Abbas, and X. Koutsoukos. Byzantine resilient distributed multi-task learn- ing. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Ad- vances in Neural Information Processing Systems, volume 33, pages 18215-18225. Cur- ran Associates, Inc., 2020. URL htttttt://rccceedinngggg/ neurips pttrrippsscc//ppppe/2/////e d37
pdf
R. D. Luce. Individual Choice Behavior. John Wiley, 1959.
Mohajer and C. Suh. Active top-k ranking from noisy comparisons. 2016 54th Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 875-882, 2016.
S. Negahban, S. Oh, and D. Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1):266-25) 2017.
A. Rajkumar and S. Agarwal. A statistical convergence perspective of algorithms for rank aggregation from pairwise data. In E. Xing and T. Jebara, editors, Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 126, Bejing, China, 22-24 Jun 2014, PMLR. URI. URI. https:://// fttaps://proceedingg mlr, mll..pess// p v32/ raaaaajjaa htt/rakuuaarr jumar html

---

H. A. Soufiani, D. Parkes, and L. Xia. Computing parametric ranking models via rank- munkbreaking. In
E. P. Xing and Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 360-368, Bejing, China, 6 2014. PMIR. URL,https htt.hhttts/////tm httttt::/pproeeeingssss mlr prwpsrressssee 2/sf2///offaanm
C. Suh, V. Y. F. Tan, and R. Zhao. Adversarial top- ranking. IEEE Trans. Inf. Theor, 63 (4):2201 -2225, 4 2017. ISSN 0018-9448. doi: 10.1109/TT.2001:2259966 URL https
//doi.or//00 1100,1109/TTT /ITT. 2017 2659660
G. Sun, Y. Cong. J. Dong, Q. Wang, L. Lyu, and J. Liu. Data poisoning attacks on federated machine learning. IEEE Internet of Things Journal, 2021.
Y. Wu, H. Chen, X. Wang, C. Liu, P. Nguyen, and Y. Yesha. Tolerating adversarial attacks and byzantine faults in distributed machine learning. In 202/ IEEE International Conference on Big Data (Big Data), pages
2021. doi: 10.1 N0.119//BigDDatt2253222222 2021 1,7711676611 1583.
Updated Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "qnPSPgi2Dq1", "reviewer": "Reviewer_R2Qw", "summary": "This paper considers the problem of learning the parameters of the Bradley-Terry-Luce (BTL) model by aggregating pairwise comparisons from different voters. The paper considers a setting where some of the voters can be \\emph{Byzantine}, i.e. they can provide adversarial votes in order to force large errors in parameter estimation. The paper shows that the popular Rank Centrality algorithm can incur large error in estimation even if a small constant fraction of the voters are Byzantine. The paper then gives an algorithm that incurs low estimation error when the number of \\emph{Byzantine} voters strictly less than half of the total voters, the comparison graph is Erdos-Renyi with p = O(\\log(n)/n), and number of votes per pair is \\Omega(\\log n).", "questions": "Besides computational efficiency, is there any other issue that prevents this algorithm from being extended to graphs with larger degrees and non-ER graphs?", "limitations": "Since the algorithm needs to know the index of each voter and how they vote on various tasks, it can be challenging to use this algorithm in a setting where privacy is a concern as the algorithm can perhaps learn about voter identity based on their pairwise preferences. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The problem considered in this paper is well-motivated. In terms of technical novelty: even though the idea to filter malicious samples/votes based on median is quite well-known, I think that the idea of combining votes from several pairs and taking median over the combination is new. \n\nWeaknesses: \n\n1. The error bound is very weak as it is the max of two terms: (1) d_\\max/k and (2) \\sqrt{log(k)/d_\\min}. The second term seems problematic as the error seems to increase if we increase the # votes per pair and the best error rate possible is \\sqrt{\\log \\log n/\\log n}. This can be much worse as compared to the bounds known for the non-adversarial setting. The informal theorem on page 2 (Theorem 3) is misleading as it hides the dependence on this \\sqrt{log(k)/d_\\min} term and does not mention the restrictions on k, comparison graph etc.\n\n2. The algorithm crucially depends on assigning the tasks in a particular way that ensures that all k voters share d specific tasks. This might not be a very good assumption in practice as there might be several limitations such as lack of expertise that does not allow voters to share so many tasks.\n\n3. The algorithm only works for Erdos-Renyi graphs. It seems unlikely that the ideas in the paper will apply to more general graphs as the algorithm becomes computationally inefficient even if there is one vertex with a high degree.\n\nOverall I think that the paper has a good set of results, but falls short of making a significant impact for this problem due to the weakness of the results and strict assumptions on the comparison graph.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "l8tcgmMg3r", "reviewer": "Reviewer_gNNK", "summary": "This paper tackles the problem of learning from comparison labels in crowd-sourced settings, where multiple labelers can label a pair and some labelers may be spammers/Byzantine unlike standard/good labelers. It is assumed that the comparisons are generated by the The Bradley-Terry (BT) model and form an Erdos-Renyi graph. Main contributions begin with theoretical results showing that the state-of-the-art Rank Centrality (RC) algorithm cannot generalize its error bounds for BT model estimation from Byzantine comparison labels. Motivated by this, this paper proposes a poly-time Byzantine Spectral Ranking (BSR) algorithm that first identifies potential comparisons from Byzantine labelers by searching over the neighborhood of each node in the comparison graph and identifying labelers that significantly deviate from the median score estimate, and then applies the RC algorithm after removing Byzantine comparisons. Theoretical results show that if strictly less than half of the labelers are Byzantine, removing Byzantine comparisons via BSR improves over vanilla RC estimates with high probability. This observation is validated via experiments over a synthetic dataset and the benchmark Sushi dataset, where comparisons are generated from total rankings, using l_2 error and Kendall-Tau correlation metrics.", "questions": "Melnyk et al., Byzantine Preferential Voting (https://doi.org/10.1007/978-3-030-04612-5_22) seems to have a similar problem setting. Can the authors summarize and contrast the differences with the current paper?", "limitations": "Limitations regarding sample complexity are discussed in the conclusions, and there are no potential negative societal impacts. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The problem of learning from corrupted comparison labels is interesting and significant. The spectral ranking algorithm and following theoretical/experimental results in this setting are novel. \n\nWeaknesses: Introduction is very dense with a lot of technical notation; more motivation and insights rather than technical descriptions would be helpful.\n\nNotation is inconsistent (e.g., w or \\pi or p for scores, v or i for labeler index in Algorithm 1), with some used without introduction (e.g., N_g(i) in Algorithm 1). The value of parameter alpha is never introduced.\n\nSupplemental material is not referenced in the main paper, though all proofs and extra experiments are there. \n\nIn practice, a passive-learning algorithm that can use the comparison label of any pair from any labeler would require total rankings from each labeler, which are costly to collect. Meanwhile, the authors recognize this practical limitation. \n\nExperiments would be stronger if the convergence time of BSR vs. RC is reported to observe the prediction performance vs. time trade-off.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5LI4xVJ5LFt", "reviewer": "Reviewer_hBwN", "summary": "This paper studies parameter inference in the Bradley-Terry pairwise comparison model in the setting where a fraction of comparison outcomes can be corrupted adversarially. The theoretical results presented in the paper can be summarized as follows.\n\n1. The popular rank-centrality algorithm is not robust to adversarial corruptions.\n2. There exists a quadratic-time algorithm that is robust to adversarial corruptions: it recovers the true parameters with vanishing error in the presence of a constant fraction of adversarial voters, under suitable assumptions\n3. No algorithm can recover the true parameters if 50% or more voters are adversarial.\n\nThe authors illustrate the results with simulations under various adversarial models.", "questions": "1. Comparing the informal theorems 1 & 3 seems to imply that the algorithm presented in this paper converges faster that rank centrality ($1/\\sqrt{k}$ vs. $1/k$). Can the authors comment on that?\n2. One way to relate the results in this paper to those of Agarwal et al would be to consider every edge that has at least one byzantine voter to be corrupted (In the sense of Agarwal et al.). In that case, how do respective results compare?\n\nAnother way to meaningfully compare to Agarwal et al. (in the G(n,p) case) is to set:\n\n- $k = \\ell$, $p = c \\log n / n$ in the results of this paper,\n- $k = 1$, $p = \\ell c \\log n / n$ in the results of Agarwal et al,\n\nand let $\\ell$ grow. In that case:\n\n- in the latter setting, the corruption model of Agarwal et al. matches that of this paper (since there is only one voter per edge)\n- the number of comparisons is identical (in expectation), but they are distributed differently (fewer edges but with more voters vs more edges with fewer voters).\n\nHow do the results compare in that case?", "limitations": "Overall, limitations are discussed adequately, although that discussion could be improved by contrasting the results of this paper to those of Agarwal et al., as mentioned above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The question addressed in this work is important and of interest to the NeurIPS community. The setting studied is realistic, and might be particularly relevant to applications in crowdsourcing.\n- The theory is comprehensive and addresses several important questions:\n    - how does rank centrality cope with adversarial inputs?\n    - how can we do better?\n    - what is the limit?\n- The proposed \"fast\" variant of the algorithm has a practical running time in the regime of interest in this paper ($p = \\Theta(\\log n / n)$).\n- Overall, the contributions are well explained, the developments are rigorous, and the authors provide useful insights into the problem. The simulation results are helpful in illustrating the theory.\n\nIn my opinion, the main weakness of this paper is that it does not contrast its results to those in Agarwal et al. (2020), who address very similar questions under a slightly different corruption model. The authors acknowledge that paper in the last paragraph of the introduction, but never come back to it afterwards.\n\nI believe that the contributions in this paper might be novel and complementary to those of Agarwal et al., but I think they are similar enough to warrant a comparison, both in terms of theoretical results and in empirical simulations. For example, carefully identifying regimes where either approach gives better bounds, and running simulations that are comparable to those in Section 4 of Agarwal et al.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2df0fabcDn", "reviewer": "Reviewer_xZhK", "summary": "This paper investigates rank aggregation under the BTL model in an adversarial setting, where a fraction of voters are adversarial and always give pairwise comparisons that are opposite to the ground truth. The authors formally demonstrate that Rank-Centrality, a popular rank aggregation algorithm, can have significantly degraded performance with a small fraction of adversarial voters, assuming an Erdos-Renyi comparison graph. The authors also improve the Rank-Centrality method by proposing an algorithm that detects and removes the adversarial voters. The effectiveness of the proposed method is also empirically verified on synthetic and real data.", "questions": "Please see the weaknesses.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper investigates an interesting and practical problem, ranking aggregation in adversarial settings. \n- This paper provides formal analyses of the adversarial vulnerability of a popular ranking aggregation method with clear intuitions.\n- This paper proposes a simple yet effective fix for Rank-Centrality in the assumed adversarial setting.\n- This paper is clearly written and easy to follow.\n\nWeaknesses:\n- The adversarial setting assumes that all the adversarial voters know the ground truth pairwise comparisons and ALWAYS vote for the opposite. This setting is somewhat unrealistic.\n- The proposed algorithm seems to rely on the above assumption to detect adversarial voters, which undermines the practical applicability of the proposed algorithm.\n- In the case where there are a large fraction of adversarial voters, if the above assumption is assumed, can one directly derive a good estimate of the ranking by inverting all the observed pairwise rankings?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept