Semidefinite ranking on graphs
published: Sept. 7, 2007, recorded: September 2007, views: 5051
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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 . 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 . It has recently been shown that semidefinite relaxations offer in many cases better solutions than spectral ones for clustering  and transductive classification . We therefore investigate semidefinite relaxations of ranking on graphs.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !