A Short Tour of Kernel Methods for Graphs
Machine learning research has – apart from some exceptions – originally concentrated on learning from data that can naturally be represented in a single table without links between the instances. Due to the needs of many real-world applications , in recent years an increasing amount of reserch has been devoted to machine learning on relational data with more complex structure. This book is then concerned with a very popular subject among this research, graphical models for relational data. In this chapter now we will give a short introduction to another popular subject, kernel methods for relational data, in particular graph spaces. Kernel Methods can loosely be characterised as learning algorithms that take as information about the data only the covariance structure of the dataset. This way we can look at two separate aspects of kernel methods almost independently, the kernel function defining the covariance structure and the kernel-based learning algorithm. Most popular kernel methods can naturally be derived from a regularised risk minimisation setting. In this setting, positive-definiteness of the kernel function has the additional benefit of rendering the optimisation problem convex such that the globally optimal solution can efficiently be found by appropriate algorithms. The relation between kernel methods and graphical models can perhaps be described best by having a brief look at Gaussian process regression. This algorithm is based on the idea of modelling the distribution of the labels of any finite dataset by a multivariate normal distribution with given covariance function and additive Gaussian noise. If the data obeys the Markov properties relative to a graph G, the