Fast Computation of Graph Kernels

S. Vishwanathan, K. Borgwardt, and N. N. Schraudolph. Fast Computation of Graph Kernels. In Advances in Neural Information Processing Systems (NIPS), pp. 1449–1456, MIT Press, Cambridge, MA, 2007.
Long version

Download

249.4kB	87.1kB	232.5kB

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(n^3)$ worst-case time. This includes kernels whose previous worst-case time complexity was $O(n^6)$, 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 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.

BibTeX Entry

@inproceedings{VisBorSch07,
     author = {S.~V.~N. Vishwanathan and Karsten Borgwardt
               and Nicol N. Schraudolph},
      title = {\href{http://nic.schraudolph.org/pubs/VisBorSch07.pdf}{
               Fast Computation of Graph Kernels}},
      pages = {1449--1456},
     editor = {Bernhard Sch\"olkopf and John C. Platt and Thomas Hofmann},
  booktitle =  nips,
     volume =  19,
  publisher = {MIT Press},
    address = {Cambridge, MA},
       year =  2007,
   b2h_type = {Top Conferences},
  b2h_topic = {Kernel Methods, Bioinformatics},
   b2h_note = {<a href="b2hd-VisSchKonBor10.html">Long version</a>},
   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(n^3)$
    worst-case time. This includes kernels whose previous worst-case
    time complexity was $O(n^6)$, 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.
}}