## Graph Kernels

S. Vishwanathan, N.
N. Schraudolph, R. Kondor, and K. Borgwardt. ** Graph Kernels**.
* Journal of Machine Learning Research*,
11:1201–1242, 2010.

Short version

### Download

770.2kB | 377.1kB | 681.4kB |

### Abstract

We present a unified framework to study graph kernels, special cases of which include the random walk (Gärtner et al., 2003; Borgwardt et al., 2005) and marginalized (Kashima et al., 2003, 2004; Mahé et al., 2004) graph kernels. Through reduction to a Sylvester equation we improve the time complexity of kernel computation between unlabeled graphs with $n$ vertices from $O(n^6)$ to $O(n^3)$. We find a spectral decomposition approach even more efficient when computing entire kernel matrices. For labeled graphs we develop conjugate gradient and fixed-point methods that take $O(dn^3)$ time per iteration, where $d$ is the size of the label set. By extending the necessary linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) we obtain the same result for $d$-dimensional edge kernels, and $O(n^4)$ in the infinite-dimensional case; on sparse graphs these algorithms only take $O(n^2)$ time per iteration in all cases. Experiments on graphs from bioinformatics and other application domains show that these techniques can speed up computation of the kernel by an order of magnitude or more. We also show that rational kernels (Cortes et al., 2002, 2003, 2004) when specialized to graphs reduce to our random walk graph kernel. Finally, we relate our framework to R-convolution kernels (Haussler, 1999) and provide a kernel that is close to the optimal assignment kernel of Fröhlich et al. (2006) yet provably positive semi-definite.

### BibTeX Entry

@article{VisSchKonBor10, author = {S.~V.~N. Vishwanathan and Nicol N. Schraudolph and Risi Kondor and Karsten Borgwardt}, title = {\href{http://nic.schraudolph.org/pubs/VisSchKonBor10.pdf}{ Graph Kernels}}, pages = {1201--1242}, journal = jmlr, volume = 11, year = 2010, b2h_type = {Journal Papers}, b2h_topic = {Kernel Methods, Bioinformatics}, b2h_note = {<a href="b2hd-VisBorSch07.html">Short version</a>}, abstract = { We present a unified framework to study graph kernels, special cases of which include the random walk (G\"artner et al., 2003; Borgwardt et al., 2005) and marginalized (Kashima et al., 2003, 2004; Mah\'e et al., 2004) graph kernels. Through reduction to a Sylvester equation we improve the time complexity of kernel computation between unlabeled graphs with $n$ vertices from $O(n^6)$ to $O(n^3)$. We find a spectral decomposition approach even more efficient when computing entire kernel matrices. For labeled graphs we develop conjugate gradient and fixed-point methods that take $O(dn^3)$ time per iteration, where $d$ is the size of the label set. By extending the necessary linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) we obtain the same result for $d$-dimensional edge kernels, and $O(n^4)$ in the infinite-dimensional case; on sparse graphs these algorithms only take $O(n^2)$ time per iteration in all cases. Experiments on graphs from bioinformatics and other application domains show that these techniques can speed up computation of the kernel by an order of magnitude or more. We also show that rational kernels (Cortes et al., 2002, 2003, 2004) when specialized to graphs reduce to our random walk graph kernel. Finally, we relate our framework to R-convolution kernels (Haussler, 1999) and provide a kernel that is close to the optimal assignment kernel of Fr\"ohlich et al. (2006) yet provably positive semi-definite. }}