Research map / Adversarial robustness and security / Attacks on text and graphs
Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions
Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna, Prathamesh Patil
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add LP-based pruning of inconsistent-cycle edges before Accelerated Spectral Ranking | ASR on single-cut-corrupted BTL data · Synthetic, exact probabilities (n=50) | L1 error of recovered weights | Improved |
| add LP-based pruning before ASR | ASR on single-cut-corrupted BTL data · Synthetic, sampled comparisons (L = log n / eps^2, eps = 5%) | L1 error of recovered weights | Improved |
| increase corruption rate gamma from 5% to 25% for non-robust ASR and HMM | ASR and HMM · Synthetic data | L1 error of recovered weights | Hurt |
| increase corruption rate gamma towards the upper end of 5%-25% for LP pruning | LP Pruning + ASR · Synthetic data | L1 error of recovered weights | Mixed |
| add LP-based pruning before ASR | ASR · Irish dataset (n=12, p=0.3 subsampled, alpha=0.02) | L1 error of recovered weights | Improved |
| add LP-based pruning before ASR | ASR · Sushi dataset (n=16, p=0.3 subsampled, alpha=0.02) | L1 error of recovered weights | Improved |
| use robust LP pruning at corruption rates beyond the theoretical limit gamma <= log(np)/(125 log n) | LP Pruning + ASR · Real and synthetic data | L1 error of recovered weights | Improved |
| corrupt only the edges crossing a single cut (scale S up with alpha=0.02) | non-robust BTL estimators ASR and HMM · Single cut corruption (Example 1) | identifiability of true weights | Hurt |
| restrict per-vertex corruption rate to at most 1/4 - eps on Erdos-Renyi graphs | BTL weight identifiability · Erdos-Renyi comparison graphs | unique identifiability: 1/4 - eps | Improved |
| increase corruption rate per vertex above 1/4 + eps | BTL weight identifiability · Erdos-Renyi comparison graphs | unique identifiability: 1/4 + eps | Hurt |
| use datasets GIF and Youtube instead of full-ranking datasets | Real-data corruption experiments · GIF, Youtube | structural robustness to corruption | Hurt |
Closest papers by meaning
- Sequential Manipulation Against Rank Aggregation: Theory and Algorithm (TPAMI 2024 · similarity 0.91)
- Byzantine Spectral Ranking (NeurIPS 2022 · similarity 0.90)
- A Tale of HodgeRank and Spectral Method: Target Attack Against Rank Aggregation Is the Fixed Point of Adversarial Game (TPAMI 2022 · similarity 0.90)
- Poisoning Attack Against Estimating From Pairwise Comparisons (TPAMI 2021 · similarity 0.87)
- Perturbation-Invariant Adversarial Training for Neural Ranking Models: Improving the Effectiveness-Robustness Trade-Off (AAAI 2024 · similarity 0.86)
- Selective Preference Aggregation (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
