Abstract:
In this article, we propose fast subtree kernels on graphs. On graphs with nn nodes and mm edges and maximum degree dd, these kernels comparing subtrees of height hh can be computed in O(m h)O(m h), whereas the classic subtree kernel by Ramon \& G\"artner scales as O(n2 4d h)O(n2 4d h). 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.
Live content is unavailable. Log in and register to view live content