Statistical and Machine Learning Approaches for Network Analysis

Chapter 8

Graph Kernels

Matthias Rupp

Graph kernels are formal similarity measures defined directly on graphs. Because they are positive semidefinite functions, they correspond to inner products. This property makes them suitable for use with kernel-based machine learning algorithms, such as support vector machines and Gaussian processes. In this chapter, I present different types of graph kernels (based on random walks, shortest paths, tree patterns, cyclic patterns, graphlets, and optimal assignments), give an overview of successful applications in bio-and cheminformatics, and discuss advantages and limitations of kernels between graphs.