Header logo is ei

Fast subtree kernels on graphs

2009

Conference Paper

ei


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

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

Event Name: 23rd Annual Conference on Neural Information Processing Systems (NIPS 2009)
Event Place: Vancouver, BC, Canada

Address: Red Hook, NY, USA
Digital: 0
ISBN: 978-1-615-67911-9
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{6080,
  title = {Fast subtree kernels on graphs},
  author = {Shervashidze, N. and Borgwardt, KM.},
  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},
  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}
}