Neuhaus M., Bunke H. Bridging the Gap Between Graph Edit Distance and Kernel Machines

World Scientific, 2007. — 245 p.When we first started working on the problem of making the kernel machine approach applicable to the classification of graphs a couple of years ago, our efforts 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 difficult 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 field. In this book, which is an extended and revised version of the first author's Ph.D. 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 different graphs, and give an experimental evaluation on real-world data.Graph Matching
Graph Edit Distance
Kernel Machines
Graph Kernels
Experimental ResultsA: Graph Data Sets