Timezone: »

 
Poster
Scalable kernels for graphs with continuous attributes
Aasa Feragen · Niklas Kasenburg · Jens Petersen · Marleen de Bruijne · Karsten Borgwardt

Sun Dec 08 02:00 PM -- 06:00 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »
While graphs with continuous node attributes arise in many applications, state-of-the-art graph kernels for comparing continuous-attributed graphs suffer from a high runtime complexity; for instance, the popular shortest path kernel scales as $\mathcal{O}(n^4)$, where $n$ is the number of nodes. In this paper, we present a class of path kernels with computational complexity $\mathcal{O}(n^2 (m + \delta^2))$, where $\delta$ is the graph diameter and $m$ the number of edges. Due to the sparsity and small diameter of real-world graphs, these kernels scale comfortably to large graphs. In our experiments, the presented kernels outperform state-of-the-art kernels in terms of speed and accuracy on classification benchmark datasets.
[ PDF] 

Author Information

Aasa Feragen (MPI Tübingen & University of Copenhagen)
Niklas Kasenburg (MPI Tübingen & University of Copenhagen)
Jens Petersen (University of Copenhagen)
Marleen de Bruijne (Erasmus MC/University of Copenhagen)
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

More from the Same Authors