Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für biologische Kybernetik     Collection: Biologische Kybernetik     Display Documents



ID: 548507.0, MPI für biologische Kybernetik / Biologische Kybernetik
Fast subtree kernels on graphs
Authors:Shervashidze, N.; Borgwardt, K.M.
Editors:Bengio, Y.; Schuurmans, D.; Lafferty, J.; Williams, C.; Culotta, A.
Date of Publication (YYYY-MM-DD):2010-04
Title of Proceedings:Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009
Start Page:1660
End Page:1668
Physical Description:9
Audience:Not Specified
Intended Educational Use:No
Abstract / Description: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.
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Holger Fischer
Affiliations:MPI für biologische Kybernetik/Empirical Inference (Dept. Schölkopf)
Identifiers:LOCALID:6080
URL:http://books.nips.cc/nips22.html
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.