Header logo is

Fast Computation of Graph Kernels


Conference Paper


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.

Author(s): Vishwanathan, SVN. and Borgwardt, KM. and Schraudolph, N.
Book Title: Advances in Neural Information Processing Systems 19
Pages: 1449-1456
Year: 2007
Month: September
Day: 0
Editors: Sch{\"o}lkopf, B. , J. Platt, T. Hofmann
Publisher: MIT Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: Twentieth Annual Conference on Neural Information Processing Systems (NIPS 2006)
Event Place: Vancouver, BC, Canada

Address: Cambridge, MA, USA
Digital: 0
ISBN: 0-262-19568-2

Links: PDF


  title = {Fast Computation of Graph Kernels},
  author = {Vishwanathan, SVN. and Borgwardt, KM. and Schraudolph, N.},
  booktitle = {Advances in Neural Information Processing Systems 19},
  pages = {1449-1456},
  editors = {Sch{\"o}lkopf, B. , J. Platt, T. Hofmann},
  publisher = {MIT Press},
  address = {Cambridge, MA, USA},
  month = sep,
  year = {2007},
  month_numeric = {9}