English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Fast subtree kernels on graphs

MPS-Authors
/persons/resource/persons84919

Shervashidze,  N
Max Planck Institute for Biological Cybernetics, Max Planck Society;
Former Research Group Machine Learning and Computational Biology, Max Planck Institute for Biological Cybernetics, Max Planck Society;

/persons/resource/persons75313

Borgwardt,  KM
Max Planck Institute for Biological Cybernetics, Max Planck Society;
Former Research Group Machine Learning and Computational Biology, Max Planck Institute for Biological Cybernetics, Max Planck Society;

Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Shervashidze, N., & Borgwardt, K. (2010). Fast subtree kernels on graphs. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, & A. Culotta (Eds.), Advances in Neural Information Processing Systems 22 (pp. 1660-1668). Red Hook, NY, USA: Curran.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-C0C6-B
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ä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.