@incollection{NIPS2006_836,
title = {Fast Computation of Graph Kernels},
address = {Cambridge, MA},
author = {S V N Vishwanathan and Karsten M. Borgwardt and Nicol Schraudolph},
booktitle = {Advances in Neural Information Processing Systems 19},
editor = {B. Sch\"{o}lkopf and J. Platt and T. Hoffman},
publisher = {MIT Press},
url = {http://books.nips.cc/papers/files/nips19/NIPS2006_0836.pdf},
year = {2007},
abstract = {Using extensions of linear algebra concepts to Reproducing Kernel Hilbert Spaces (RKHS), we define a unifying framework for random walk kernels on graphs. Reduction to a Sylvester equation allows us to compute many of these kernels in O(n3) worst-case time. This includes kernels whose previous worst-case time complexity was O(n6), such as the geometric kernels of G¨artner et al. [1] and the marginal graph kernels of Kashima et al. [2]. Our algebra in RKHS allow us to exploit sparsity in directed and undirected graphs more effectively than previous methods, yielding sub-cubic computational complexity when combined with conjugate gradient solvers or fixed-point iterations. Experiments on graphs from bioinformatics and other application domains show that our algorithms are often more than 1000 times faster than existing approaches.},
keywords = {2006 graphs kernels nips structure }
}
::