A Survey on Rank Aggregation

Siyi Wang, Qi Deng, Shiwei Feng, Hong Zhang, Chao Liang

Abstract

Rank Aggregation (RA) is the mathematical framework used to fuse disparate, often conflicting, ranked lists into a single consensus ranking. While rooted in 18th-century social choice theory, RA has become critical in modern fields such as bioinformatics, computer vision, and recommendation systems. This paper provides a comprehensive roadmap of the RA landscape, introducing a fine-grained taxonomy that categorizes methods into unsupervised, supervised, and semi-supervised approaches. By benchmarking 27 algorithms across seven diverse datasets, the study highlights the trade-offs between computational cost and performance, identifies the robustness of classical statistical methods, and showcases the potential of interactive, quantum-inspired techniques.

Introduction

Imagine trying to determine the "best" movie of the year. One critic provides a list, an algorithm generates another, and user votes offer a third. These sources rarely agree. Rank Aggregation (RA) addresses this by synthesizing these conflicting inputs into a "master" list. Despite its long history, modern RA research remains fragmented, often focusing on unsupervised methods while neglecting supervised or interactive alternatives. This survey bridges these gaps with a unified taxonomy and a rigorous, large-scale evaluation using the newly released RA-Lib toolkit.

Taxonomy of Rank Aggregation

The authors categorize RA methods into a three-tiered taxonomy based on their data processing mechanisms:

  1. Unsupervised RA: These methods operate without ground-truth training data. They include Item-Item methods (e.g., Condorcet) focusing on pairwise comparisons, Item-Ranking methods (e.g., Borda Count, Reciprocal Rank Fusion) utilizing specific positions, and Ranking-Ranking methods (e.g., HPA) that assess similarity between entire lists.
  2. Supervised RA: These leverage labeled training data to learn optimal combination strategies, categorized by granularity into Point-wise, Pair-wise, and List-wise approaches. This category includes modern neural network and evolutionary algorithms.
  3. Semi-supervised & Interactive RA: This "middle ground" includes Interactive RA (IRA), which utilizes minimal real-time user feedback to significantly enhance consensus accuracy without requiring massive pre-labeled datasets.
A comprehensive taxonomy of Rank Aggregation (RA) methods, categorizing them into unsupervised, supervised, and semi-supervised approaches.

Experimental Setup and Datasets

The study evaluates 27 methods across seven public datasets spanning four distinct fields:

  • Person Re-identification (re-ID): Market1501, DukeMTMC-reID, and CUHK03.
  • Recommendation Systems: MovieLens 1M.
  • Bioinformatics: NSCLC (lung cancer gene data).
  • Social Choice: World University Ranking 2022 (WUR 2022).

Key Results and Insights

The benchmarking process revealed several critical insights into the performance and resilience of various RA strategies:

  • The Power of Interaction: The QI-IRA (Quantum-inspired Interactive RA) method emerged as a top performer. By incorporating a small amount of user feedback, it frequently outperformed fully supervised methods that require significantly more training data.
  • Unsupervised Resilience: Simple statistical approaches like Borda Count and RRF remain remarkably robust across different fields, often proving difficult to beat despite their lack of training.
  • The "Noise" Trap: Probabilistic models like Markov Chains (MC) performed poorly on noisy datasets like MovieLens, as they assume a level of consistency that real-world user data often lacks.
  • Ranking-Ranking Superiority: In computer vision tasks, methods that treat rankings as entities to be compared (e.g., HPA) showed superior performance, suggesting the relationship between rankers is as vital as the items themselves.
Performance comparison of 27 RA algorithms across seven diverse datasets, highlighting the superior performance of supervised and interactive methods.

In supervised settings, QI-IRA(3,1) achieved the highest accuracy on nearly all re-ID and recommendation datasets, reaching a 97.83% Rank@1 on Market1501. For social choice tasks like university rankings, statistics-based methods like Dowdall were superior due to their ability to handle impartial social voting requirements.

Future Directions

The authors identify two primary areas for future research:

  1. Efficiency via Active Learning: To address the inefficiency of subjective user judgment in Interactive RA, the integration of Active Learning (AL) could allow algorithms to proactively request the most helpful feedback.
  2. Adversarial Defense: RA shows promise in making Deep Neural Networks more robust by aggregating outputs from different hidden layers to defend against adversarial attacks. However, ensuring the RA process itself is not vulnerable to structural mismatches remains an open challenge.

Summary updated

BibTeX
@inproceedings{wang2024survey,
  author = {Siyi Wang and Qi Deng and Shiwei Feng and Hong Zhang and Chao Liang},
  title = {{A Survey on Rank Aggregation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure