On Graph Kernels

Опубликовано 6 сентября 2016, 16:42

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(n^6) 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(n^3). 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.