# Byzantine Spectral Ranking

arXiv: https://arxiv.org/abs/2211.07902 · HTML: https://mlsanity.com/paper/2211.07902/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 15 Nov 2022.

## Builds on (most cited first, 9 of 9)

- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Data Poisoning Attacks on Federated Machine Learning](https://mlsanity.com/paper/2004.10020/) (2020)
- [Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent](https://mlsanity.com/paper/1705.05491/) (2017)
- [Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)](https://mlsanity.com/paper/2008.00742/) (2020)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization](https://mlsanity.com/paper/1504.01070/) (2015)
- [Adversarial Top-K Ranking](https://mlsanity.com/paper/1602.04567/) (2016)
- [Byzantine Resilient Distributed Multi-Task Learning](https://mlsanity.com/paper/2010.13032/) (2020)
- [Tolerating Adversarial Attacks and Byzantine Faults in Distributed Machine Learning](https://mlsanity.com/paper/2109.02018/) (2021)

## Built on by (most cited first, 5 of 5)

- [Robust Consensus in Ranking Data Analysis: Definitions, Properties and Computational Issues](https://mlsanity.com/paper/2303.12878/) (2023)
- [Minimax Hypothesis Testing for the Bradley-Terry-Luce Model](https://mlsanity.com/paper/2410.08360/) (2024)
- [Robust Federated Inference](https://mlsanity.com/paper/2510.00310/) (2025)
- [Exploring the Robustness of Decentralized Training for Large Language Models](https://mlsanity.com/paper/2312.00843/) (2023)
- [Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries](https://mlsanity.com/paper/2606.08410/) (2026)

## Abstract (arXiv)

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.