Spectral Ranking using Seriation
  We describe a seriation algorithm for ranking a set of 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 when some pairwise comparisons are
corrupted or missing, and that seriation based spectral ranking is more robust
to noise than classical scoring methods. Finally, we bound the ranking error
when only a random subset of the comparions are observed. 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.
