Fast subtree kernels on graphs

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(m~h)$, whereas the classic subtree kernel by Ramon \& G\"artner scales as $O(n^2~4^d~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.