Skip navigation
Skip navigation

Fast computation of graph kernels

Vishwanathan, S; Borgwardt, Karsten; Schraudolph, Nicol


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
Source: Advances in Neural Information Processing Systems 19


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:  23 August 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator