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.
}}