Timezone: »

 
Oral
Fast Subtree Kernels on Graphs
Nino Shervashidze · Karsten Borgwardt

Wed Dec 09 04:50 PM -- 05:10 PM (PST) @
in Oral session 8: Probabilistic Models and Kernels »
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.

Author Information

Nino Shervashidze (INRIA, Laboratoire d'Informatique de l'ENS)
Karsten Borgwardt (ETH Zurich)

Karsten Borgwardt is Professor of Data Mining at ETH Zürich, at the Department of Biosystems located in Basel. His work has won several awards, including the NIPS 2009 Outstanding Paper Award, the Krupp Award for Young Professors 2013 and a Starting Grant 2014 from the ERC-backup scheme of the Swiss National Science Foundation. Since 2013, he is heading the Marie Curie Initial Training Network for "Machine Learning for Personalized Medicine" with 12 partner labs in 8 countries (http://www.mlpm.eu). The business magazine "Capital" listed him as one of the "Top 40 under 40" in Science in/from Germany in 2014, 2015 and 2016. For more information, visit: https://www.bsse.ethz.ch/mlcb

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors