Fast Computation of Graph Kernels
2007
Conference Paper
ei
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
Web |
BibTex @inproceedings{VishwanathanBS2007, 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}, doi = {}, month_numeric = {9} } |