Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- This paper investigates an interesting and practical problem, ranking aggregation in adversarial settings. 
- This paper provides formal analyses of the adversarial vulnerability of a popular ranking aggregation method with clear intuitions.
- This paper proposes a simple yet effective fix for Rank-Centrality in the assumed adversarial setting.
- This paper is clearly written and easy to follow.

Weaknesses:
- 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.
- The proposed algorithm seems to rely on the above assumption to detect adversarial voters, which undermines the practical applicability of the proposed algorithm.
- 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?
questions: Please see the weaknesses.
limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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).
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. 

Weaknesses: 

1. 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.

2. 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.

3. 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.

Overall 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.  
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

1. The popular rank-centrality algorithm is not robust to adversarial corruptions.
2. 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
3. No algorithm can recover the true parameters if 50% or more voters are adversarial.

The authors illustrate the results with simulations under various adversarial models.
strengths_and_weaknesses: Strengths:

- 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.
- The theory is comprehensive and addresses several important questions:
    - how does rank centrality cope with adversarial inputs?
    - how can we do better?
    - what is the limit?
- 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)$).
- 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.

In 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.

I 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.
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?
2. 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?

Another way to meaningfully compare to Agarwal et al. (in the G(n,p) case) is to set:

- $k = \ell$, $p = c \log n / n$ in the results of this paper,
- $k = 1$, $p = \ell c \log n / n$ in the results of Agarwal et al,

and let $\ell$ grow. In that case:

- in the latter setting, the corruption model of Agarwal et al. matches that of this paper (since there is only one voter per edge)
- 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).

How 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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. 

Weaknesses: Introduction is very dense with a lot of technical notation; more motivation and insights rather than technical descriptions would be helpful.

Notation 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.

Supplemental material is not referenced in the main paper, though all proofs and extra experiments are there. 

In 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. 

Experiments would be stronger if the convergence time of BSR vs. RC is reported to observe the prediction performance vs. time trade-off.

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.
review_title: null

Meta-review: metareview: This is a nice paper that deals with byzantine corruption in the BTL model. It  first shows that rank centrality performs quite poorly (btw  how does the maximum likelihood estimator, which is known to be minimax optimal in the non-adversarial setting, perform in the Byzantine setting?). The paper then presents algorithms for ranking when the majority of workers are non-adversarial (which is unsurprisingly necessary for any algorithm). We all agree that this paper should be accepted, although different reviewers have different levels of excitement about the paper. A persistent concern seems to be absence of proper comparison with Agarwal et al. and weak-ish bounds. Nevertheless, this paper is above bar and I recommend acceptance.


confidence: Certain
Decision: Accept