Publication
Efficient Graph Kernels by Randomization
Marion Neumann; Novi Patricia; Roman Garnett; Kristian Kersting
In: Peter A. Flach; Tijl De Bie; Nello Cristianini (Hrsg.). Machine Learning and Knowledge Discovery in Databases - European Conference. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD-2012), September 24-28, Bristol, United Kingdom, Pages 378-393, Lecture Notes in Computer Science, Vol. 7523, Springer, 2012.
Abstract
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.