SerialRank: Spectral Ranking using Seriation
We describe a seriation algorithm for ranking a set of n items given pairwise comparisons between these items. Intuitively, the algorithm assigns similar rankings to items that compare similarly with all others. It does so by constructing a similarity matrix from pairwise comparisons, using seriation methods to reorder this matrix and construct a ranking. We first show that this spectral seriation algorithm recovers the true ranking when all pairwise comparisons are observed and consistent with a total order. We then show that ranking reconstruction is still exact even when some pairwise comparisons are corrupted or missing, and that seriation based spectral ranking is more robust to noise than other scoring methods. An additional benefit of the seriation formulation is that it allows us to solve semi-supervised ranking problems. Experiments on both synthetic and real datasets demonstrate that seriation based spectral ranking achieves competitive and in some cases superior performance compared to classical ranking methods.
Thanks for the replies to my questions. Of course, I do agree that my example is somewhat specific, although I still believe that it's meaningful with regard the general question regarding the information (not) represented by the similarity relation. I more or less agree on the other answers, although my doubts are not completely dispelled. In summary, I still think the paper puts forward an interesting idea and therefore encourage the authors to continue in this direction, even if the paper might not yet be ready for a publication on the level of the NIPS conference. Original review:The idea of reducing the problem of ranking to a problem of similarity analysis appears to be interesting, however, it is not sufficiently well justified in the paper. What exactly is the connection between the preference relation C and the similarity relation S? Do they represent the same information? If not, what information is added or removed, and why is this an advantage? In the case of a single pairwise preference a > b, represented by the relationC=  +1  +1 -1  +1 , one obtains a symmetric similarity relation, which means that the information about the direction of the preference is completely lost. Another example: If we have the chain of preferences a > b, b > c, c > d, i.e., the matrixc=   1     1     0     0    -1     1     1     0     0    -1     1     1     0     0    -1     1 , then (unless I made a mistake somewhere) the second-smallest eigenvalue of the Laplacian of S is not unique, and none of the eigenvectors corresponds to the ranking a > b > c > d one would expect to find. The reason could be grounded in the problem that the conversion of preferences into similarities does not capture implicit connections via transitivity. Instead, a non-observed preference contributes to the similarity between two items (by adding 1/2 according to (2)), just like a draw (which, in contrast to a non-observation, is indeed a confirmation of similarity). In this example, the similarity relation iss =    3.0000    2.0000    1.5000    2.0000    2.0000    3.5000    2.0000    1.5000    1.5000    2.0000    3.5000    2.0000    2.0000    1.5000    2.0000    3.0000As can be seen, a and d are quite similar, and in fact, a is more similar to d than to c (although it should be the other way around). This is because there is no comparison at all between these items, neither a direct one nor an indirect one via a third item. If we add the preference d > a to the above chain, we create a cycle, which makes it impossible to produce a reasonable ranking. Again, the second-smallest eigenvalue is not unique, but nevertheless, both Fiedler vectors suggest some ranking. Dies that make sense?The formal results in section 4 about robustness are technically interesting, however, they refer to very specific cases and compare to very specific alternative methods. For example, it's true that for a single pairwise inversion, the simple Borda count will produce ties. However, there are many other methods that can easily resolve the problem. Condition (7) is difficult to understand. The experiments are again interesting, however, I fail to see a clear advantage of the proposed method (for example, in comparison to BTL). By the way, in connection with the regularity assumptions specified in Definition 2.1 (R-matrix), you might be interested in recent work on ranking based on pairwise preferences induced by statistical rank models such as Mallows or Plackett-Luce. As has been shown, these models imply strong regularity of the pairwise preferences, and the C-matrix they induce is Toeplitz [1,2].References:[1] W. Cheng, E. Hüllermeier, W. Waegeman and V. Welker. Label Ranking with Partial Abstention based on Thresholded Probabilistic Models. NIPS-2012, Lake Tahoe, Nevada, USA.[2] R. Busa-Fekete, E. Hüllermeier, B. Szörenyi. Preference-based rank elicitation: The case of Mallows. ICML 2014.