English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Fast Computation of Graph Kernels

Vishwanathan, S., Borgwardt, K., & Schraudolph, N. (2007). Fast Computation of Graph Kernels. In Advances in Neural Information Processing Systems 19 (pp. 1449-1456). Cambridge, MA, USA: MIT Press.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-CBDF-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-CBE0-2
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Vishwanathan, SVN, Author
Borgwardt, KM1, Author           
Schraudolph, N, Author
Schölkopf, Editor
B., Editor
Platt, J., Editor
Hofmann, T., Editor
Affiliations:
1Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497794              

Content

show
hide
Free keywords: -
 Abstract: Using extensions of linear algebra concepts to Reproducing Kernel Hilbert Spaces (RKHS), we define a unifying framework for random walk kernels on graphs. Reduction to a Sylvester equation allows us to compute many of these kernels in O(n3) worst-case time. This includes kernels whose previous worst-case time complexity was O(n6), such as the geometric kernels of G¨artner et al. [1] and the marginal graph kernels of Kashima et al. [2]. Our algebra in RKHS allow us to exploit sparsity in directed and undirected graphs more effectively than previous methods, yielding sub-cubic computational complexity when combined with conjugate gradient solvers or fixed-point iterations. Experiments on graphs from bioinformatics and other application domains show that our algorithms are often more than 1000 times faster than existing approaches.

Details

show
hide
Language(s):
 Dates: 2007-09
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: ISBN: 0-262-19568-2
URI: http://nips.cc/Conferences/2006/
BibTex Citekey: VishwanathanBS2007
 Degree: -

Event

show
hide
Title: Twentieth Annual Conference on Neural Information Processing Systems (NIPS 2006)
Place of Event: Vancouver, BC, Canada
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: Advances in Neural Information Processing Systems 19
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Cambridge, MA, USA : MIT Press
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1449 - 1456 Identifier: -