A Survey on Rank Aggregation

1 Introduction

Rank aggregation (RA), a fundamental technique to combine multiple basic rankings from various rankers into a single consensus one, has wide applications in society, economy, and science [Akritidis et al., 2022]. RA was originally designed to solve the problem of inconsistent voting for political candidates [Borda, 1781]. Since then, numerous research efforts have been devoted to addressing issues related to world university rankings in social choice [Zhang et al., 2021] [Feng et al., 2023], gene sequences combination in bioinformatics [Li et al., 2019] [Wang et al., 2022], detection results aggregation in spam filtering [Liu et al., 2007], and search results fusion in document retrieval [Farah and Vanderpooten, 2007] [Wu, 2013], person re-identification (re-ID) [Yu et al., 2020] [Huang et al., 2022], metasearch [Renda and Straccia, 2003] [Desarkar et al., 2016] and recommendation systems [Oliveira et al., 2020].

∗Corresponding author.

Because of the broad interests and fundamental importance of the RA technique, several inspiring review articles [Lin, 2010] [Li et al., 2019] [Oliveira et al., 2020] [Wang et al., 2022] have been published in this field. As the earliest review, [Lin, 2010] provides a systematic overview of unsupervised RA literature at the time with a special focus on biological applications. To investigate the performance, the author conducts an experimental evaluation of 9 unsupervised RA methods on a cancer gene dataset. Thereafter, [Li et al., 2019] and [Wang et al., 2022] further summarize the latest unsupervised RA methods in bioinformatics, and evaluate methods' performance in a series of larger genomic experiments. Meanwhile, [Oliveira et al., 2020] exclusively focuses on RA studies in the field of recommendation systems, and conducts comparative experiments of RA methods in movie recommendation. In general, existing surveys tend to review RA works in a specific field, and primarily concentrate on unsupervised RA methods. However, recent RA studies have achieved significant progress in novel approaches and applications, which have not been thoroughly reviewed in time. Therefore, we argue that conducting a systematic review of classical algorithms and recent advances is urgently necessary to provide up-to-date guidance for future research.

Compared to previous RA surveys, our work makes the following differences and contributions:

• A systematic and up-to-date overview. We provide the first comprehensive review of existing RA techniques, including classic methods in not only unsupervised and supervised RA but also semi-supervised RA which is ignored by previous RA surveys. Moreover, we discuss state-of-the-art progress in research and applications.
• A fine-grained taxonomy. Based on the types of studied relationships, we further subdivide unsupervised RA into item-item, item-ranking, and ranking-ranking methods. Based on the levels of data granularities, we further subdivide supervised RA into point-wise, pair-wise, and list-wise methods.
• The largest evaluations across multiple fields. We

conduct, for the first time as far as we know, the largest scale of experimental evaluation, including 27 RA methods on 7 public datasets from person re-ID, recommendation systems, bioinformatics, and social choice.

• Open questions and future perspectives. We discuss two open questions in the current RA research and application, and share our perspective about future trends, i.e., active learning in interactive RA and RA-based adversarial defense, in the context of the state-of-the-art research progress.
• Open-source algorithm RA-Lib toolkit with public benchmarks. We integrate all RA algorithm code experimentally evaluated in this paper together with relevant benchmark datasets into a toolbox, which is released open-source on GitHub 1 for researchers.

2 Preliminary

In this section, we first discuss key challenges in RA study. On this basis, we give a comprehensive and fine-grained taxonomy of RA methods. Then, we define the problem of RA and explain the basic notation used throughout this article.

2.1 Challenges

RA aims to combine basic rankings from multiple rankers. Early RA strategies, like average fusion or heuristic-based fusion [Borda, 1781] [Reilly, 2002] are unsupervised methods; their core challenge is to effectively determine the quality of different basic rankings without external supervision, in order to produce an optimal fusion result. Although unsupervised methods are easy to implement and prevalent in RA research, their performance is difficult to improve due to the lack of supervision [Liu et al., 2007].

To address this drawback, researchers turn to introduce external supervision to guide the RA process [Pujari and Kanawati, 2012] [Wang et al., 2013]. Provided with highquality training data, supervised RA methods can generally achieve better results than their unsupervised counterparts; however, the challenge posed by the high cost of data collection and labeling also limits the performance of supervised RA methods.

Similar to general machine learning problems, the tradeoff between low-cost and high-performance persists in RA research. Unsupervised and supervised methods essentially make an either-or choice, where the former prioritizes lowcost while the latter prioritizes high-performance, each with inherent drawbacks in practice. To overcome this dilemma, a more realistic approach and also a more difficult challenge is to find a well-proportioned balance between cost and performance.

2.2 Taxonomy

Based on the above discussion, we propose a systematic and fine-grained taxonomy that reflects the overall landscape of RA study in Figure 1. We generally divide the existing RA methods into unsupervised, supervised, and semi-supervised methods.

1 https://github.com/nercms-mmap/RankAggregation-Lib

Unsupervised RA has evolved into the majority of RA methods during the development of RA. Numerous unsupervised RA methods have their special fusion strategies. Based on the types of studied relationships, unsupervised RA methods are subdivided into item-item, item-ranking and rankingranking methods. Moreover, item-ranking methods, based on the differences in the underlying mathematical models, can be subdivided into probabilistic model and statistics-based methods.

In supervised RA, we categorize supervised RA methods into three classes: point-wise, pair-wise, and list-wise methods, based on the levels of data granularities. The existing list-wise methods can be further subdivided into metricdriven, evolutionary, neural network-based, and interactive methods, according to their methodological principles or characteristics.

Semi-supervised RA methods are not further subdivided because of the limited amount of related work.

2.3 ProblemFormulation

Given a set of M items to be sorted U = {u1, u2, ..., uM}, we define a basic ranking R = {ui ≥ uj ≥ . . . ≥ uh} as an ordered list of items, where i, j, h ∈ {1, . . . ,M} and i ̸= j ̸= h. Note that R does not necessarily rank all items in U. We denote by Rt (ui) the position (or rank) of item ui under ranking Rt . If Rt (ui) < Rt (uj), we say ui is more relevant than uj in Rt . For a set of N basic rankings R = {R1 , R2 , ..., RN }, the objective of RA is to find a function f to combine these basic rankings in R into a consensus ranking R∗ , i.e., R∗ = f(R). For RA methods that aim to calculate the final score of items, we define S as the scoring function and S(ui) as the score of item ui.

3 Unsupervised RAMethods

3.1 Item-ItemMethods

The item-item methods investigate the preference relationship between items to produce the final result. Condorcet [de Condorcet, 1785] proposes a Condorcet procedure based on pairwise comparisons of items, where one item beats, ties, or loses to the other item. The score of an item ui in the Condorcet procedure is determined by the number of its "victories" against all the other items in basic rankings. A victory for ui is achieved if the majority of the basic rankings rank ui higher than any other item uj̸=i. For example, for a set of items {u1, u2, u3}, the Condorcet procedure conducts pairwise comparisons among these items: if u1 beats u2, u1 beats u3 and u3 beats u2, then the score is {2, 0, 1}, so we get the preference among these items and fuse these preference into a ranking R = {u1 ≥ u3 ≥ u2}.

[Saari and Merlin, 1996] computes Copeland scores of items based on the disparity between the count of items they surpass and the count of items they are surpassed by:

where | · | returns the set cardinality. The consensus ranking is generated by arranging the items according to their Copeland scores, and items with identical scores are considered ties. Similarly, Outranking [Farah and Vanderpooten, 2007] proposes a comparison method to generate the consensus ranking based on majority opinions, where an item in a higher position in the consensus ranking must have a majority of preferences and, meanwhile, a minority of objections.

Besides, there are several graph-based comparison methods. [Desarkar et al., 2016] treats basic rankings as preference graphs and items as nodes. They calculate node weights through pairwise comparisons of items and then sort the aggregated graphs based on node weights. [Xiao et al., 2021] proposes a competitive graph (CG) method, which ranks a node in the graph to the consensus ranking by calculating its ratio between out- and in-degrees, representing the number of items above and below the node, respectively.

3.2 Item-RankingMethods

As the most popular class of methods in RA, item-ranking methods utilize positional information of items in basic rankings to produce the consensus ranking. Relevant works can be further subdivided into probabilistic model methods and statistics-based methods.

Probabilistic Model Methods. Probabilistic model methods condense the positional information of items across all basic rankings into a probability model. [Dwork et al., 2001] introduces the Markov chain (MC) to model items' positional information, where each item is modeled as a state. Then a (homogeneous) MC for a basic ranking consists of a set of states S = {u1, u2, ..., uM} and a transition probability matrix P ∈ RM×M . In general, the start state of the system is chosen according to some initial distribution, e.g., the uniform distribution on S. The core idea of [Dwork et al., 2001] is to use the stationary distribution of MC to define the final consensus ranking. Depending on different ways to construct P, there are 4 different RA implementations:

• MC1: if the current state is itemui, then the next state is chosen uniformly from the multiset of all items uj that were ranked higher than or equal to ui by some ranking that ranked ui, i.e., chose the next state uniformly from the multiset QMC1 i = ∪Nt=1 {uj : Rt (uj) ≤ Rt (ui)};
• MC2: if the current state is itemui, then the next state is chosen by first picking a ranking Rt uniformly from R containing ui, then picking an uj uniformly from the set QMC2 Rt ,i = {uj : Rt (uj) ≤ Rt (ui)};
• MC3: if the current state is item ui, then the next state is chosen as follows: first pick a ranking Rt uniformly from all the R containing ui, then uniformly pick an uj that was ranked by Rt . if Rt (uj)<Rt (ui) then go to uj , else stay in ui;
• MC4: if the current state is itemui, then the next state is chosen as follows: first, pick an item uj uniformly from S. If Rt (uj)<Rt (ui) for the majority of the rankings Rt ∈ R that ranked both ui and uj, then go to uj, else stay in ui.

Statistics-based Methods. In general, statistics-based methods utilize a certain statistic to measure the position of the item and use this to get the consensus ranking. [Fox and Shaw, 1994] proposes Comb* family to aggregate all basic rankings to a consensus one. In the Comb* family, the item ui in the basic ranking Rt is scored by:

where the Len(·) returns the number of items in Rt . After computing the scores, the Comb* family traverses all basic rankings and assigns to each item ui its lowest score (CombMIN), highest score (CombMAX), or arithmetic sum (CombSUM) across all basic rankings as its S(ui) in the consensus ranking. CombANZ and CombMNZ are CombSUM's variants, in which CombANZ is obtained by dividing CombSUM by the number of rankings that include ui, while CombMNZ multiplies CombSUM by the number of rankings that include ui. The Comb* family fusion methods are shown in Table 1.

Fagin [Fagin et al., 2003] proposes the Median method. For each item, they calculate the median position of all basic rankings, and sort all items in descending order based on their median position. BordaCount [Borda, 1781] is the most widely used statistics-based RA method. BordaCount uses the length of ranking to linearly calculate the Borda score of item ui in basic rankings:

The items are then sorted in descending order of their scores to generate the consensus ranking.

Dowdall [Reilly, 2002] designs a reciprocal form score function for RA, which is able to reduce the differences between items when aggregated in the case of a large number of items. The score function of Dowdall is as follows:

after scoring items, it arranges the items ui in descending order based on their scores to generate the consensus ranking. RRF [Cormack et al., 2009] introduces an algorithm that adds a constant k to the denominator of the score function of Dowdall and is able to perform stably with fewer item aggregations. The score function of RRF is as follows:

3.3 Ranking-RankingMethods

The ranking-ranking methods are based on the relationship among various rankings for aggregation. In general, rankingranking methods obtain the consensus ranking by a userdefined ranking objective function. iRANK [Wei et al., 2010] propose an unsupervised learning framework that allows two basic rankings to "teach" each other before being combined, to boost the performance of the consensus ranking R∗ . ER [Mohammadi and Rezaei, 2020] proposes a method that iteratively solves the consensus ranking based on halfquadratic theory such that the consensus ranking R∗ minimizes the distance to each basic ranking. [Chatterjee et al., 2018] introduces a method based on similarity, which computes the similarity matrix between the basic rankings and selects the two rankings with the closest similarity in each round for weighted aggregation, ultimately producing R∗ .

HPA [Fujita et al., 2020] proposes a similarity-based method, which firstly generates a pseudo-answer ¯R by the simplest mean RA of basic rankings. It then calculates the similarity score between the basic ranking and the pseudoanswer ¯R. Finally, HPA selects the top-K most similar basic rankings RK for aggregation.

where sim(·) computes the similarity score as the fusion weight. Besides, [Fujita et al., 2020] further introduces a similarity-based method named PostNDCG, which compares the similarity between basis rankings and selects the ranking with the highest similarity to all other rankings as the consensus ranking. Recently, DIBRA [Akritidis et al., 2022] utilizes an innovative approach based on the cosine distance metric to iteratively update weights in basic rankings. It assigns scores to items in each ranking, creating M-dimensional score vectors. DIBRA involves calculating the cosine distance between pairs of basic rankings to identify relevant items, with higher scores indicating greater relevance. By iterating through all rankings, DIBRA determines a consensus ranking.

4 Supervised RAMethods

Given high-quality training data, supervised RA methods generally deliver superior performance. Note that many supervised RA methods generate the consensus ranking R∗ through a weighted fusion, thereby aiming to find an optimal fusing weight for R. We define the weight vector as w = [w1,w2, ...,wN]⊤, where weight wt is assigned to Rt . Thus, R∗ = ∑Rt∈R wtRt .

4.1 Point-wise Methods

[Liu et al., 2007] sets up a general framework for supervised RA, in which learning is formalized as an optimization, which minimizes the disagreements between the consensus ranking R∗ and the ground truth that is transferred to a pairwise comparison matrix. Based on this framework, the authors develop supervised versions of BordaCount and MC methods. [Volkovs and Zemel, 2014] incorporates Normalized Discounted Cumulative Gain (NDCG) [Ye et al., 2021]

to construct a loss function and combine it with the Conditional Random Field (CRF) framework. They employ the gradient descent optimization method to train the parameter θ = {αt, βp t , βn t }Nt=1 for each basic ranking, which is used to calculate the ranking score of item:

where the binary unary potentials φt(ui) takes the value 1 only when item ui is not ranked by Rt and 0 in all other cases. For pairwise potentials ϕt, if Rt (ui) < Rt (uj), ϕt(ui, uj) is non-zero. Otherwise, ϕt(uj, ui) is non-zero. The weights βp t and βn t control how much emphasis is given to positive and negative preferences, respectively.

4.2 Pair-wise Methods

[Xu et al., 2021] proposes a deep framework to predict the preference of each item pair while improving the consistency with overall basic rankings as much as possible. [Wu, 2013] proposes a supervised variant of [de Condorcet, 1785], referred to as the weighted Condorcet method, which incorporates a training approach based on Linear Discriminant Analysis (LDA) to optimize the fusing weights w for R. For each item pair (ui, uj), according to whether ui is better than uj in the ground truth, we can classify all item pairs into two classes. At the same time, each item pair has a feature vector [h1, h2, ..., hN]⊤. If Rt (ui) < Rt (uj), ht = 1, otherwise ht = -1. We want to distinguish the item pairs of the two classes by a linear combination of n features:

where w is learned by LDA.

4.3 List-wise Methods

List-wise methods focus on the characteristics or attributes of the basic rankings, currently dominating over supervised RA.

Metric-Driven Methods. Using metrics like NDCG, mAP [Ye et al., 2021], and so on, metric-driven methods aim to find the optimal fusing weights w for R. The implementation has two ways: either by using the metric to assess the quality of basic rankings, thereby assigning greater weights to the better ones like wBorda [Pujari and Kanawati, 2012], or by directly optimizing a specific metric to enhance the effectiveness of consensus ranking [Wang et al., 2013].

Evolutionary Methods. Evolutionary algorithms simulate the natural selection, crossover, and mutation process of individuals in the population to find the best individual, which represents the optimal scheme. In [Vargas Mu˜noz et al., 2015], the individual is represented by a binary tree that defines the aggregate function f(R) with the FFP1 function proposed in [Fan et al., 2004] as the fitness function. AggrankDE [Bałchanowski and Boryczka, 2022] uses the differential evolution algorithm to address the RA problem. It represents an individual as fusing weights w for R, with Average Precision (AP) as the fitness function. Mutation generates a new individual w ′ by combining three randomly selected individuals wj, wh, and wk: w ′ = wj + λ(wh -wk), where the parameter λ controls the amplification of the differential variation (wh -wk).

Neural Network-based Methods.This type of method uses neural networks to optimize aggregation. [Qi et al., 2020] utilizes the Lovasz Bregman (LB) divergence to create a linear structured convex function and a nested structured concave function to aggregate outputs of distributed deep neural network-based models. CSRA [Yu et al., 2020] considers both the quality of basic rankings and the difficulty of each query, and combines the two to train a neural network to predict the fusing weights w for R. At the same time, this method uses the simplest mean fusion [Burges et al., 2011] to construct ground truth without priori information, which, to some extent, overcomes the dependence of supervised methods on labeled data.

Interactive Methods. In the real world, pre-labeled datasets are hardly available, prohibiting fully-supervised RA methods from practical applications. To address this problem, [Huang et al., 2022] utilizes a small amount of supervisory information from users' feedback to supervise the RA method to produce better results. Based on positive (relevant) samples labeled by users, [Huang et al., 2022] proposes two implementations to adjust the fusing weight w for R: IRAR and IRAS. IRAR denotes that the samples are selected based on the position of the item in the ranking, while the IRAS is the item's score. IRAR increases weights for rankings that rank positive samples higher, while IRAS modifies w according to the variance in scores of positive samples, utilizing the standard deviation to reflect the consistency of users' feedback.

5 Semi-supervised RAMethods

As the challenges in the RA field discussed above, semisupervised methods aim to find a better balance between high-performance and low-cost. [Chen et al., 2008] and [Hoi and Jin, 2008] propose two semi-supervised RA methods, both aim to find an appropriate fusing weight w for R by using a small amount of available labeled data. [Hoi and Jin, 2008] develops a novel query-dependent solution, in which the w is different based on different characteristics of queries. They use the graph Laplacian matrix to represent the similarity relationships between objects and combine it with a ranking loss function to optimize the w.

[Chen et al., 2008] proposes SSRA to learn w by minimizing disagreement between consensus ranking and basic rankings while satisfying preference constraints. The scores given by basic rankings to each item are stored in a M × N matrix M. Let Σ be the limited set of labeled preference pairs, serving as the constraints. If (ui, uj) ∈ Σ, then item ui is ranked higher than item uj. So, the preference constraints can be given by the inequality:

where M(i) is the i-th row of the matrix M. Then, [Chen et al., 2008] measures the similarity of each basic ranking to all other rankings in R. A ranking that is agreed with more other rankings has higher quality. Let p = [p1, p2, ..., pN]⊤ denote the quality vector for R. The optimal w should minimize the distance to p with constraints defined by Eq.(9):

where λw is a regularizer about w.

6 Experiments

6.1 Datasets

We conduct benchmarking experiments on 4 popular re-ID datasets, i.e., Market1501 [Zheng et al., 2015], DukeMTMCreID [Ristani et al., 2016] and CUHK03 detected and labeled [Li et al., 2014], 1 recommendation system dataset, i.e., MovieLens 1M [Harper and Konstan, 2015], 1 bioinformatics dataset, i.e., NSCLC [Wang et al., 2022] and 1 social choice dataset, i.e., World University Ranking in 2022 (WUR 2022) [Feng et al., 2023]. For the quantitative evaluation, we utilize the ranking metrics Rank@1 (R@1 for short) and mAP [Ye et al., 2021] on re-ID datasets, Rank@1 and mAP@10 (mAP' for short) in recommendation system [Oliveira et al., 2020], Recall@400 (r@400 for short) and Recall@800 (r@800 for short) [Wang et al., 2022] in bioinformatics, and Normality (Nor for short) and Impartiality (Im-p for short) in social choice [Feng et al., 2023]. The smaller normality and impartiality are, the better. For all other metrics, the larger the value, the better. All these metrics are in the form of percentages (%), except for normality and impartiality.

6.2 Experiment Setup

All experiments are conducted on a server equipped with 2 Intel Xeon Silver 4215 (2.50GHz) and 4 Nvidia RTX A6000. Specifically, the MC1-4 methods are difficult to test on the full Market1501 and DukeMTMC-reID datasets, so we cut off top-K items from basic rankings and aggregate to be the new MC1-4 (top-K). Besides, there is no labeled data in the NSCLC and the WUR 2022 dataset, so we do not measure supervised and semi-supervised RA methods on them.

Considering the practical situation, we fixed n = 1 and only examined the cases m = 1 and 3 in interactive methods during the experiment. Due to limitations of space, readers are referred to the project's homepage on GitHub for more detailed experimental setups, including the generation of basic rankings and the setting of the model parameters.

6.3 Result and Discussion

The result of these RA methods on 7 datasets is shown in Table 2, from which we have the following observations. Overall, unsupervised RA methods can be better applied to datasets in different fields because they do not require supervisory information, and the performance of some unsupervised methods is very close to supervised methods. For supervised methods, there exists at least one that outperforms all other unsupervised methods on the MovieLens 1M and 4 re-ID datasets. The semi-supervised method ranks among the top on the MovieLens 1M and 4 re-ID datasets; despite not being the best, it shows better robustness.

It is remarkable that some unsupervised methods show good performance and robustness on 7 different source datasets, such as Borda, ER, CG, RRF, iRANK, and Mean. The ranking-ranking methods usually achieve a good performance in our experiments, especially for HPA and DIBRA. The HPA method even ranks in the top three of all methods in terms of mAP metrics on both Market1501 and DukeMTMCreID datasets, with 94.74% and 89.09%, respectively. However, when considering the WUR 2022 dataset, statisticsbased methods are superior. Moreover, MC4 obtains the top-2 performance among all unsupervised RA methods on all re-ID datasets for the R@1, especially ranks first on DukeMTMC-reID and CUHK03 (labeled) with 92.46% and 88%, respectively. However, there has been a dramatic decline in the performance of all MC methods on MovieLens 1M. This can be attributed to a lot of noise among basic rankings on MovieLens 1M, and MC methods are not a good choice in such environments.

In supervised RA, QI-IRA(3,1) [Hu et al., 2024] ranks first in the performance of R@1 and mAP for almost all reID datasets and MovieLens 1M, except for the mAP@10 in MovieLens 1M, which lost out to the CRF by 0.41% and the R@1 in DukeMTMC-reID, which lost out to the IRAS(3,1) by 0.32%. This can be attributed to the flexible interaction with a small amount of user feedback, which enhances the performance and robustness of the IRA method. Notice that CRF shows very high performance in the MovieLens 1M (R@1: 50.86%, mAP': 16.51%), which can be mainly attributed to the CRF framework's ability to utilize low-quality basic rankings, meaning it can offer a certain level of reverse support for the preference relations they endorse.

Furthermore, we can observe that the semi-supervised method consistently ranks at the top among all RA methods, exhibits good robustness on 4 re-ID datasets, and achieves 39.55% R@1 on MovieLens 1M. This suggests that supervised RA methods are a preferable choice when there is a significant performance difference among basic rankings and labeled data is available. However, the semi-supervised method can be considered as an alternative when the cost budget is insufficient.

7 Open Questions

7.1 Dilemma of High-Performance and Low-Cost

The earliest exploration to address the dilemma of highperformance and low-cost is semi-supervised RA [Hoi and Jin, 2008] [Chen et al., 2008]. While these methods significantly reduce data labeling costs, they still incur considerable data collection costs. Moreover, static training data are not flexible enough to adapt to changing real-world scenarios. To address this problem, [Huang et al., 2022] proposes the interactive RA. It utilizes a small amount of users' online feedback to guide the RA process and achieves the dual advantages of higher performance than unsupervised RA at a low cost. On this basis, [Hu et al., 2024] introduces quantum theory to provide a theoretical explanation for the generation and aggregation of multiple rankings, and raises a new quantum-inspired interactive RA method QI-IRA. However, the current IRA method selects samples solely depending on users' subjective judgment, which may result in low-efficient interactions for inexperienced users. The active learning (AL) technique has the ability to objectively recommend valuable feedback candidates, which can effectively address the above defects. Therefore, how to introduce AL into interactive RA is a promising research direction for interactive RA.

7.2 NewApplication of RA Technique

With the widespread applications of Deep Neural Networks (DNNs), adversarial defense for DNNs has become increasingly important. Most successful defense strategies adopt adversarial training or random input transformations that typically require retraining or finetuning the model to achieve reasonable performance. [Tiwari et al., 2022] finds that employing the RA technique to combine the network hidden layer outputs shows unexpected robustness to adversarial attacks. However, when evaluating the robustness of the model, the above work always assumes that attacks only target fixed output ports, which results in an overestimation of the robustness of the model. To address the above problem, if we can effectively eliminate the interference of structural mismatch between attack and defense, we may better utilize the RA technique to defend DNN so as to produce more robust and trusted prediction results.

8 Conclusion

In this paper, we present a comprehensive review of classical methods and recent advances in RA study. Specifically, we first elaborate on three key challenges facing RA research, i.e., improving performance, reducing cost, and striking a balance between them. On this basis, we analyze and discuss representative algorithms in unsupervised, supervised and semi-supervised RA. For each category, we summarize their common ideas and comment on their strengths and weaknesses. To compare the performance of different RA methods, we conduct the largest scale of comparative evaluation to date for 27 RA methods on 7 public datasets from re-ID, recommendation system, bioinformatics and social choice. Ultimately, we discuss open questions in the RA study and give our suggestions for future prospects.

Acknowledgements

This work is supported by the National Natural Science Foundation of China (No. 62372339). The numerical calculations in this paper have been done on the supercomputing system in the Supercomputing Center of Wuhan University.

Contribution Statement

Siyi Wang, Qi Deng, and Shiwei Feng contributed equally to this work.