Semidefinite ranking on graphs

We consider the problem of ranking the vertices of an undirected graph given some preference relation. This ranking on graphs problem has been tackled before using spectral relaxations in [1]. Their approach is strongly related to the spectral relaxation made in spectral clustering algorithms. One problem with spectral relaxations that has been found in clustering is that even on simple toy graphs the spectral solution can be arbitrarily far from the optimal one [2]. It has recently been shown that semidefinite relaxations offer in many cases better solutions than spectral ones for clustering [3] and transductive classification [4]. We therefore investigate semidefinite relaxations of ranking on graphs.