English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Fast Computation of Graph Kernels

Vishwanathan, S., Borgwardt, K., & Schraudolph, N. (2007). Fast Computation of Graph Kernels. In B. Schölkopf, J. Platt, & T. Hoffman (Eds.), 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/21.11116/0000-0002-E207-7
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
https://papers.nips.cc/paper/2973-fast-computation-of-graph-kernels.pdf (Publisher version)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Vishwanathan, SVN, Author
Borgwardt, KM1, Author           
Schraudolph, N, Author
Affiliations:
1External Organizations, ou_persistent22              

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: 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: 2006-12-04 - 2006-12-07

Legal Case

show

Project information

show

Source 1

show
hide
Title: Advances in Neural Information Processing Systems 19
Source Genre: Proceedings
 Creator(s):
Schölkopf, B1, Editor           
Platt, JC, Editor
Hoffman, T, Editor
Affiliations:
1 Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795            
Publ. Info: Cambridge, MA, USA : MIT Press
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1449 - 1456 Identifier: ISBN: 0-262-19568-2