Header logo is

Graph Kernels

2010

Article

ei


We present a unified framework to study graph kernels, special cases of which include the random walk (G{\"a}rtner et al., 2003; Borgwardt et al., 2005) and marginalized (Kashima et al., 2003, 2004; Mahét 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(n6) to O(n3). 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(dn3) 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(n4) in the infinite-dimensional case; on sparse graphs these algorithms only take O(n2) 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 certain 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 kernel of Fr{\"o}hlich et al. (2006) yet provably positive semi-definite.

Author(s): Vishwanathan, SVN. and Schraudolph, NN. and Kondor, R. and Borgwardt, KM.
Journal: Journal of Machine Learning Research
Volume: 11
Pages: 1201--1242
Year: 2010
Month: April
Day: 0

Department(s): Empirical Inference
Bibtex Type: Article (article)

Digital: 0

Links: PDF
Web

BibTex

@article{VishwanathanSKB2010,
  title = {Graph Kernels},
  author = {Vishwanathan, SVN. and Schraudolph, NN. and Kondor, R. and Borgwardt, KM.},
  journal = {Journal of Machine Learning Research},
  volume = {11},
  pages = {1201--1242},
  month = apr,
  year = {2010},
  month_numeric = {4}
}