A Caltech Library Service

Graph Kernels

Vishwanathan, S. V. N. and Schraudolph, Nicol N. and Kondor, Risi and Borgwardt, Karsten M. (2010) Graph Kernels. Journal of Machine Learning Research, 11 . pp. 1201-1242. ISSN 1533-7928.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 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 Fröhlich et al. (2006) yet provably positive semi-definite.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2010 S.V.N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Submitted 5/08; Revised 4/09; Published 4/10. Editor: John Lafferty. We thank Markus Hegland and Tim Sears for enlightening discussions, Alex Smola for pointing out to us that the optimal assignment kernel may fail to be p.s.d., and the anonymous reviewers for their detailed comments and suggestions which greatly helped improve this paper. This publication only reflects the authors’ views. It was supported by NICTA, funded by the Australian Government through the Backing Australia’s Ability and Centre of Excellence programs, by the IST Programme of the European Community under the PASCAL2 Network of Excellence, IST-2007-216886, by the GermanMinistry for Education, Science, Research and Technology (BMBF) under grant No. 031U112F within the BFAM (Bioinformatics for the Functional Analysis of Mammalian Genomes) project, part of the German Genome Analysis Network (NGFN), by NIH grant GM063208-05 “Tools and Data Resources in Support of Structural Genomics”, and NSF grant IIS-0916686.
Funding AgencyGrant Number
Australian Government through the Backing Australia's Ability and Centre of ExcellenceUNSPECIFIED
European CommunityIST-2007-216886
German Ministry for Education, Science, Research and Technology (BMBF)031U112F
German Genome Analysis Network (NGFN)UNSPECIFIED
Subject Keywords:linear algebra in RKHS; Sylvester equations; spectral decomposition; bioinformatics; rational kernels; transducers; semirings; random walks
Record Number:CaltechAUTHORS:20101026-090905463
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20528
Deposited By: Tony Diaz
Deposited On:03 Dec 2010 23:54
Last Modified:03 Oct 2019 02:11

Repository Staff Only: item control page