On Graph Kernels

  • S V N Vishwanathan (Vishy) | Australian National University

We consider the following two problems: a) How can we best compare two graphs? and b) How can we compare two nodes in a given graph? We present some algorithms based on the notion of random walks and diffusion and show that the two questions are intimately related. A naive algorithm requires O(n6) time. Through extensions of linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) and reduction to a Sylvester equation, we construct an algorithm that improves the time complexity to O(n3). When the graphs are sparse, conjugate gradient solvers or fixed-point iterations bring our algorithm into the sub-cubic domain. Experiments on graphs from bioinformatics and other application domains show that our algorithms are often more than a thousand times faster than previous approaches.

Speaker Details

S V N Vishwanathan (vishy) obtained his Masters and PhD degree from IISc Bangalore in 2000 and 2002 respectively. Currently he is a principal researcher with National ICT Australia (http://www.nicta.com.au) and an adjunct research fellow at the Australian National University (http://www.anu.edu.au). His research interests are at the intersection of machine learning, algorithms, convex analysis, and optimization.

    • Portrait of Jeff Running

      Jeff Running

Watch Next