In this article, we propose fast subtree kernels on graphs. On graphs with n nodes and m edges and maximum degree d, these kernels comparing subtrees of height h can be computed in O(mh), whereas the classic subtree kernel by Ramon & G{\"a}rtner scales as O(n24dh). Key to this efficiency is the observation that the Weisfeiler-Lehman test of isomorphism from graph theory elegantly computes a subtree kernel as a byproduct. Our fast subtree kernels can deal with labeled graphs, scale up easily to large graphs and outperform state-of-the-art graph kernels on several classification benchmark datasets in terms of accuracy and runtime.
| Author(s): | Shervashidze, N. and Borgwardt, KM. |
| Book Title: | Advances in Neural Information Processing Systems 22 |
| Journal: | Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009 |
| Pages: | 1660-1668 |
| Year: | 2009 |
| Day: | 0 |
| Editors: | Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta |
| Publisher: | Curran |
| Bibtex Type: | Conference Paper (inproceedings) |
| Address: | Red Hook, NY, USA |
| Event Name: | 23rd Annual Conference on Neural Information Processing Systems (NIPS 2009) |
| Event Place: | Vancouver, BC, Canada |
| Digital: | 0 |
| Electronic Archiving: | grant_archive |
| ISBN: | 978-1-615-67911-9 |
| Language: | en |
| Organization: | Max-Planck-Gesellschaft |
| School: | Biologische Kybernetik |
| Links: | |
BibTex
@inproceedings{6080,
title = {Fast subtree kernels on graphs},
journal = {Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009},
booktitle = {Advances in Neural Information Processing Systems 22},
abstract = {In this article, we propose fast subtree kernels on graphs. On graphs with n nodes and m edges and maximum degree d, these kernels comparing subtrees of height h can be computed in O(mh), whereas the classic subtree kernel by Ramon & G{\"a}rtner scales as O(n24dh). Key to this efficiency is the observation that the Weisfeiler-Lehman test of isomorphism from graph theory elegantly computes a
subtree kernel as a byproduct. Our fast subtree kernels can deal with labeled graphs, scale up easily to large graphs and outperform state-of-the-art graph kernels on several classification benchmark datasets in terms of accuracy and runtime.},
pages = {1660-1668},
editors = {Bengio, Y. , D. Schuurmans, J. Lafferty, C. Williams, A. Culotta},
publisher = {Curran},
organization = {Max-Planck-Gesellschaft},
school = {Biologische Kybernetik},
address = {Red Hook, NY, USA},
year = {2009},
slug = {6080},
author = {Shervashidze, N. and Borgwardt, KM.}
}