When we rst started working on the problem of making the kernel machine approach applicable to the classication of graphs a couple of years ago, our eorts were mainly driven by the fact that kernel methods had led to impressive performance results on many data sets. It didn't take us long to appreciate the sheer elegance of how dicult pattern recognition problems can be addressed by means of kernel machines, which is particularly the case for complex data structures such as graphs. To witness researchers from a large variety of domains bring together new perspectives on kernel machines and their applications has always been exciting. We are very delighted that we have been given the opportunity to address a few extremely interesting open issues in such a rapidly evolving research eld. In this book, which is an extended and revised version of the rst author's PhD thesis, we present the major results of our work related to graph kernels. We give an introduction to the general problem, discuss theoretical issues of graph matching and kernel machines, present a number of error-tolerant graph kernels applicable to a wide variety of dierent graphs, and give an experimental evaluation on real-world data.