Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies real-valued input matrices to the minimum feedback arc set problem on tournaments (MFAST). The matrices are assumed to have low rank and originate from pairwise preference matrices under certain link functions. The authors present a geometrical condition that enables a polynomial-time algorithm to solve MFAST for rank-2 matrices. They apply their algorithm in experiments on learning to rank from pairwise comparisons.
main_review: Originality/Significance:
The results appear to be original and are very interesting from a complexity perspective. The proposed model and algorithm contribute significantly to both the optimization of the MFAST and tractable modeling of ranking from pairwise comparisons in practice. 

Quality:
The writing is of high quality. Due to very limited time I could not check the technical details and thus cannot judge correctness of the claims.

Clarity:
The paper is quite clear overall. Unfortunately, the authors did not number the references in the bibliography although they use number citations (they seemed to be in the right order, however).

Questions:
It would be great if the authors could point out how their results depend on the link function. In other words, are the claims still true if we simply assume an arbitrary skew-symmetric rank-2 matrix $M \in \mathbb R^{n \times n}$ ? In this case the results would be even more interesting.
limitations_and_societal_impact: The paragraph on broader impact is adequate.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focus on minimum feedback arc set problem in tournaments (MFAST) and characterizes the relation between the preference matrix rank with forbidden configuration. The authors propose a novel polynomial-time algorithm on MFAST with preference matrix rank 2. The authors further extend the setting to a block rank 2 tournament, where nodes can be clustered into several blocks and in each block, the preference matrix has rank 2. The proposed algorithm can also work on the non-tournament cases with a matrix-completion step. The experiments shows that the proposed algorithm reaches better performance than other works, in both synthetic (non-tournament) and real-world datasets.
main_review: This paper tackles an important problem and the solution provides a novel view of the classical problem. Eventhough the most theoretical contribution is restricted by the preference matrix with rank 2, the experiemnts in a flexible setting show promising results. 

Here are some questions and suggestions.
In the contribution, the authors claim that the proposed algorithm can solve MFAST problem with rank 2. However, in the synthetic experiments, the algorithm does not recover the optimal solution. Is this because the synthetic dataset is not a tournament? It might be good to include synthetic tournament experiments and analyzes the effect of preference matrix rank other than 2.

The performance metric is not normalizes, which makes it harder to compare across different datasets.

The algorithm 4 is named PairwiseBlockRank but Theorem 11 uses ParametricBlockRank. 



limitations_and_societal_impact:  The authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the minimum feedback arc set problem in certain classes of tournament graphs. In these classes, the edges of the tournament are defined by preference matrices of rank r. This study is motivated by arguing that such tournaments arise out of real-world data sets in various application domains.  

The paper gives bounds on the size of forbidden configurations for rank-r tournaments. For rank 2 tournaments, the paper identifies the exact forbidden structures. The paper also studies a restricted class, called block rank 2 tournaments, which is claimed to subsume several practical models. It gives a polynomial-time algorithm for the minimum feedback arc set problem on instances of this class. Finally, it shows an application of their work to the problem of learning how to rank from pairwise comparisons and provide some experimental results.
 

main_review: The feedback arc set problem is certainly very important. However, I am not very convinced that the restriction considered (i.e., defined by such matrices) is very interesting in terms of applications. For instance, the results are applied to the so-called local-global preference model, which is defined in the paper, but whose importance is not really clear.
 
The writing is overall OK, but sloppy at times (see below).

Overall, the paper is good, but the motivation and importance of this specific problem/model are unclear.
 
Specific Comments:

Line 55: “See” should not be capitalized.
Line 64: “as” should be removed.
Line 74: “for the same” -- > “for the problem”.
Line 115: explain what “cdf” is. 
Step 2 in Algorithm 1: a comma is missing before “(x_k, y_k)”.
Line 144: remove “as”. “w.r.t” -- > “w.r.t.”.
Line 152: “Inability” -- > “The inability”.
Line 156: a period is missing at the end of the line. 
Line 181: “present the same”, please rephrase. 
Line 183: What is “cone (U \cup V)”?
Line 219: a period is missing at the end of the line. 
Line 257: extra space after “(“.
Lines 284 and 287: a period is missing at the end of each line. 


limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The reviewers are satisfied with the author responses and agreed with acceptance. The authors incorporate reviewer feedback and additional experiments presented in the rebuttal in the final manuscript.
Decision: Accept (Poster)