- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper considers the problem of finding a maximum likelihood ranking given observed probabilities of preferring a candidate a to b for pairs of candidates. This problem is closely related to the task of Kemeny rank aggregation and the (weighted) feedback arc set problem; and the solution can be applied to solve such problems. The authors propose an exact formulation using the idea of chordless cycles to reduce the number of constraints compared to classical formulations (which have one constraint for every cycle), or formulations designed for complete inputs. The authors implement their formulation with standard solvers and study its performance on several previous works that study optimizing given pairwise comparisons.
Critical strengths
In applications where the goal is to find a maximum likelihood ranking, or aggregate ranking, and so on, it is ideal to find one that indeed is optimal for use in downstream tasks, or to make decisions. This minimizes future errors that can result, and gives a much more defensible ranking when making decisions. This paper offers a method to improve the scalability of exact solving, and allows more instances of such problems in practice to be solved exactly, instead of depending on approximations or heuristics.
Critical weaknesses
It is not clear if the results obtained generalize to have further impact beyond the observed results on the sparse datasets. In the Kemeny rank aggregation task, full rankings and top-lists as input give a complete graph of pairwise comparisons, and partial rankings as input are likely to have a comparison on most, if not all pairs. The paper suggests PFAS performs better than LO in such complete instances slightly – it would be interesting to know why, given the formulations are equivalent in theory. Therefore, it seems the results are more limited to ML applications where there are indeed sparse comparisons between candidates.
Theoretical contributions on improving the exact formulation are modest and mostly from the chordless cycles formulation; section 5 is relatively standard in optimization, there are no deeper analysis in whether effective heuristics or instance reduction steps can be applied on top to improve performance.
Unlike previous referenced work like approximation algorithms, SCO, Lehmer codes approach, which seem to be designed to be able to scale to problems with very large number of candidates (e.g. 10k-1million, or even larger), the exact solution is unlikely to do so, even though it is indeed much faster than previous formulations on sparse instances.
Therefore, while this has application to practitioners with some previous work applying this maximum likelihood ranking to actively rank candidates in practice, it seems overall too limited in impact and novelty.
Questions for authors
-
Is there any understanding for the observed improvement over LO in almost-complete, or complete instances?
-
If given say a good feasible solution like an approximation algorithm output as a starting, does it affect how much of a speedup PFAS gives over the original FAS/LO models, given these are branch-and-bound based?
3 comments
Thanks for the detailed comments, and the additional experiments studying the comparison between the implementations. I have read through them, and also the other reviews.
Overall, the other favorable reviews suggest this is indeed more relevant in practice for ML pipelines than I previously thought.
I have re-evaluated my score.
However, maybe one suggestion I would like to make (related as well to a comment from reviewer hMNN) that some presentation could be improved. While in practice the method is fast, it does not guarantee problem instances are tractable in practice, and therefore should be considered alongside previously proposed approximation/heuristic methods for when datasets scale significantly. Perhaps this should be mentioned as in some sense to me, the current exposition seems slightly to suggest that those methods are superseded by this work.
Thank you very much for your thorough review and for carefully considering our response and the other reviews! We fully agree with your suggestion. While on practical instances XRank is usually fast, there can be settings where exact optimization is intractable and heuristics will have to be used, so XRank complements rather than supersedes these methods. We now state this explicitly in the paper.
We thank the reviewer for the detailed and constructive feedback.
W1/Q1: Why is XRank faster than LO on complete instances? (Clarification of contributions)
Thank you for raising this, our new PFAS formulation is indeed equivalent to LO on complete instances. To explain the speedup, we must separate our two contributions: the new PFAS formulation (Section 3 & 4) and our improved algorithm to solve it (Section 5 & Appendix C).
New Formulation. Figure 9 isolates the effect of the formulation by running the identical XRank algorithm with each one. While LO is 158× slower than PFAS on sparse instances, it performs the same on fully complete instances (within 5%), confirming the equivalence. The slight speedup reported in Table 6 for p∈[0.9,1] comes from the non-complete instances in this range. On the other end, FAS is fastest on sparse instances, but still 1.6× slower than PFAS. This favorable mix between FAS and LO is the most important theoretical contribution of this work. The classical FAS and LO formulations have been the standard in literature since 1985, and for the first time we propose a new formulation that combines their most favorable properties, dominating both in all regimes.
Speedup from the improved algorithm to solve the formulation. Even though the PFAS and LO formulations are equivalent on fully dense instances, another contribution of XRank is a sophisticated separation and cut management algorithm, solving the same LO formulation up to 5.1x faster than the original algorithm of Grötschel et al.
The gains are therefore not limited to sparse instances. XRank is 5.1× faster than the original LO method on fully complete LOLIB/FASLIB instances, and 4.9× faster on nearly complete PrefLib voting profiles (Table 4).
W2/Q2: Analysis of heuristics and instance reductions to improve performance.
This is a very good idea, and we added the following analysis to the paper. XRank indeed uses heuristics like local search (Martí & Reinelt 2011) and LP rounding to find good solutions. We ablate their effect, and simulate what happens when each formulation is given a very good start solution (here, the optimal one):
Relative runtime (shifted geometric mean, 1s shift); 224 LOLIB/FASLIB instances.
Surprisingly, even an optimal start saves only 4-8%, because runtime is dominated by proving optimality. The speedup of PFAS over FAS and LO therefore barely changes with a good start solution.
Decomposition into strongly connected components speeds up sparse instances by 1.28× (they often split into many subproblems) but dense ones by only 1.08× (usually one component).
W3: Scaling to problems with very large number of candidates.
We fully agree that beyond 10k candidates an exact solver is not the right tool, and heuristics remain necessary. Luckily, most of the ML applications we target have at most a few hundred items. With a short time limit, however, XRank can also be used as an LP-guided heuristic on large instances. We ran it with a 2s time limit on all public instances from the suggested SCO and Lehmer papers:
Gap relative to the best known solution. One Diplomacy instance from the SCO paper is omitted, since it is not public.
Although this is not the originally intended use case of XRank, it outperforms both heuristics in every size group: even on the largest instances, with up to 5,904 items, XRank stays within 0.3% of the optimum after 2s, while the heuristics are 2–12% away. In addition, XRank returns a lower bound, so the user knows how far the ranking can be from optimal.
Impact and novelty. PFAS is the first formulation to outperform both 40-year-old standards, FAS and LO, in every regime. Combined with our algorithmic improvements, XRank makes optimal rankings cheap enough to compute routinely in most ML applications. This matters in practice: we show that the heuristics in published ML pipelines regularly select winners that no optimal ranking places first. To facilitate optimal rankings in practice, we packaged XRank as a Python library (
pip install xrank), with prebuilt wheels for Linux, macOS and Windows. It will be released on PyPI upon publication, since releasing it now could violate the double-blind rule.We thank the reviewer again and would appreciate a reconsideration of the score in light of these results.