English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Graph Kernels

Vishwanathan, S., Schraudolph, N., Kondor, R., & Borgwardt, K. (2010). Graph Kernels. Journal of Machine Learning Research, 11, 1201-1242.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-C0B0-C Version Permalink: http://hdl.handle.net/21.11116/0000-0002-7703-5
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Vishwanathan, SVN, Author
Schraudolph, NN, Author
Kondor, R, Author
Borgwardt, KM1, 2, Author              
Affiliations:
1Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497794              
2Former Research Group Machine Learning and Computational Biology, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_2528696              

Content

show
hide
Free keywords: -
 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é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öhlich et al. (2006) yet provably positive semi-definite.

Details

show
hide
Language(s):
 Dates: 2010-04
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: BibTex Citekey: VishwanathanSKB2010
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Journal of Machine Learning Research
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Brookline, MA : Microtome Publishing
Pages: - Volume / Issue: 11 Sequence Number: - Start / End Page: 1201 - 1242 Identifier: ISSN: 1532-4435
CoNE: https://pure.mpg.de/cone/journals/resource/111002212682020