## Fast Computation of Graph Kernels

S. Vishwanathan, K. Borgwardt,
and N. N. Schraudolph. **
Fast Computation of Graph Kernels**. In * Advances
in Neural Information Processing Systems (NIPS)*, pp. 1449–1456, MIT
Press, Cambridge, MA, 2007.

Long version

### Download

249.4kB | 87.1kB | 232.5kB |

### 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(n^3)$ worst-case time. This includes kernels whose previous worst-case time complexity was $O(n^6)$, such as the geometric kernels of Gärtner 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.

### BibTeX Entry

@inproceedings{VisBorSch07, author = {S.~V.~N. Vishwanathan and Karsten Borgwardt and Nicol N. Schraudolph}, title = {\href{http://nic.schraudolph.org/pubs/VisBorSch07.pdf}{ Fast Computation of Graph Kernels}}, pages = {1449--1456}, editor = {Bernhard Sch\"olkopf and John C. Platt and Thomas Hofmann}, booktitle = nips, volume = 19, publisher = {MIT Press}, address = {Cambridge, MA}, year = 2007, b2h_type = {Top Conferences}, b2h_topic = {Kernel Methods, Bioinformatics}, b2h_note = {<a href="b2hd-VisSchKonBor10.html">Long version</a>}, 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(n^3)$ worst-case time. This includes kernels whose previous worst-case time complexity was $O(n^6)$, 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. }}