Skip navigation
Skip navigation

Fast computation of graph kernels

Vishwanathan, S; Borgwardt, Karsten; Schraudolph, Nicol

Description

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ärtner et al. [1] and the marginal graph kernels of Kashima et al. [2]. Our algebra in RKHS allow us to exploit sparsity in directed...[Show more]

CollectionsANU Research Publications
Date published: 2007
Type: Conference paper
URI: http://hdl.handle.net/1885/37170
Source: Advances in Neural Information Processing Systems 19

Download

File Description SizeFormat Image
01_Vishwanathan_Fast_computation_of_graph_2007.pdf379.9 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator