A Survey on Rank Aggregation

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

Abstract

Rank Aggregation (RA) is a fundamental task involving the combination of multiple, often conflicting, ranked lists into a single consensus ranking. This paper provides a much-needed update to the field by introducing a systematic taxonomy that categorizes RA methods into unsupervised, supervised, and semi-supervised approaches. We conduct an extensive benchmark of 27 algorithms across seven diverse real-world datasets, ranging from social choice to bioinformatics. Our evaluation, supported by the open-source RA-Lib toolkit, reveals key insights into the robustness of classic methods and the superior performance of modern interactive frameworks.

Introduction

In fields ranging from social choice and bioinformatics to search engines and recommendation systems, we often face a "too many cooks" problem. Different "rankers" (algorithms or humans) provide different ordered lists of items. Rank Aggregation (RA) is the art of combining these multiple conflicting rankings into a single, optimal consensus. While RA has been studied since the 18th century, recent years have seen an explosion of deep learning and interactive approaches. This paper addresses the lack of a systematic, cross-domain overview and the absence of a large-scale comparative evaluation of modern RA techniques.

Methodology

The authors propose a new taxonomy to categorize the vast landscape of RA, organizing methods by learning paradigm and data granularity.

Taxonomy of Rank Aggregation methods categorized by learning paradigm and data granularity.
  1. Unsupervised RA: These methods do not require "ground truth" labels. They are further divided into Item-Item (pairwise preferences), Item-Ranking (item positions like Borda Count), and Ranking-Ranking (global similarity weighting).
  2. Supervised RA: These use training data to learn weights for different rankers, categorized by data granularity (Point-wise, Pair-wise, or List-wise). Interactive RA is a modern subset where the system learns from real-time user feedback to refine the consensus.
  3. Semi-supervised RA: A middle ground designed to balance high performance with the high cost of data labeling by using a small amount of labeled data alongside a large unlabeled set.

To facilitate this study, the authors introduced RA-Lib, an open-source toolkit containing the 27 algorithms and benchmarks used in their study.

Experimental Setup

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

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

Key Results and Insights

The benchmarking results provide a comprehensive view of the current state of RA, highlighting the strengths and weaknesses of various paradigms.

Performance comparison of 27 RA methods across seven diverse datasets, highlighting the dominance of interactive methods.
  • The Robustness of Simplicity: Surprisingly, classic unsupervised methods like Borda Count and Mean fusion remain remarkably robust across different domains, often performing nearly as well as complex supervised models.
  • Markov Chains vs. Noise: Markov Chain (MC) methods perform exceptionally well in clean environments (like re-ID) but fail dramatically in noisy environments (like MovieLens).
  • The Power of Interaction: Interactive methods, specifically QI-IRA(3,1), achieved the best results in most categories. By incorporating minimal user feedback, these models can "course-correct" more effectively than static supervised models.
  • Domain Sensitivity: In the World University Rankings, statistics-based methods like Dowdall proved superior, highlighting that the optimal algorithm is highly dependent on the nature of the underlying data.

Conclusion and Future Work

While supervised methods generally lead in accuracy, their dependence on high-quality labeled data makes them less portable across different fields. The authors identify two major frontiers for the field: integrating Active Learning to improve the efficiency of user feedback in interactive RA, and exploring RA as a defense mechanism for Deep Neural Networks against adversarial attacks by aggregating outputs from different hidden layers.

Summary updated

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