Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Efficient graph kernels by randomization

: Neumann, M.; Patricia, N.; Garnett, R.; Kersting, K.


Flach, P.A.; Bie, T.; Cristianini, N.:
Machine learning and knowledge discovery in databases. European conference, ECML PKDD 2012. Pt.1 : Bristol, UK, September 24-28, 2012; proceedings
Berlin: Springer, 2012 (Lecture Notes in Computer Science 7523)
ISBN: 978-3-642-33459-7
ISBN: 3-642-33459-8
ISBN: 978-3-642-33460-3
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD) <2012, Bristol>
Fraunhofer IAIS ()

Learning from complex data is becoming increasingly important, and graph kernels have recently evolved into a rapidly developing branch of learning on structured data. However, previously proposed kernels rely on having discrete node label information. In this paper, we explore the power of continuous node-level features for propagation-based graph kernels. Specifically, propagation kernels exploit node label distributions from propagation schemes like label propagation, which naturally enables the construction of graph kernels for partially labeled graphs. In order to efficiently extract graph features from continuous node label distributions, and in general from continuous vector-valued node attributes, we utilize randomized techniques, which easily allow for deriving similarity measures based on propagated information. We show that propagation kernels utilizing locality-sensitive hashing reduce the runtime of existing graph kernels by several orders of magnitude. We evaluate the performance of various propagation kernels on real-world bioinformatics and image benchmark datasets.