Bridging the Gap Between Graph Edit Distance and Kernel Machines (Series in Machine Perception and Artificial Intelligence)

✍ Scribed by Michel Neuhaus, Horst Bunke

• Publisher: World Scientific Publishing Company
• Year: 2007
• Tongue: English
• Leaves: 245
• Series: Series in Machine Perception and Artificial Intelligence
• Category: Library

✦ Synopsis

In graph-based structural pattern recognition, the idea is to transform patterns into graphs and perform the analysis and recognition of patterns in the graph domain - commonly referred to as graph matching. A large number of methods for graph matching have been proposed. Graph edit distance, for instance, defines the dissimilarity of two graphs by the amount of distortion that is needed to transform one graph into the other and is considered one of the most flexible methods for error-tolerant graph matching.This book focuses on graph kernel functions that are highly tolerant towards structural errors. The basic idea is to incorporate concepts from graph edit distance into kernel functions, thus combining the flexibility of edit distance-based graph matching with the power of kernel machines for pattern recognition. The authors introduce a collection of novel graph kernels related to edit distance, including diffusion kernels, convolution kernels, and random walk kernels. From an experimental evaluation of a semi-artificial line drawing data set and four real-world data sets consisting of pictures, microscopic images, fingerprints, and molecules, the authors demonstrate that some of the kernel functions in conjunction with support vector machines significantly outperform traditional edit distance-based nearest-neighbor classifiers, both in terms of classification accuracy and running time.

✦ Table of Contents

Contents......Page 10
Preface......Page 8
1. Introduction......Page 14
2. Graph Matching......Page 20
2.1 Graph and Subgraph......Page 22
2.2 Exact Graph Matching......Page 23
2.3 Error-Tolerant Graph Matching......Page 29
3. Graph Edit Distance......Page 34
3.1 Definition......Page 35
3.2.1 Conditions on Edit Costs......Page 39
3.2.2 Examples of Edit Costs......Page 40
3.3 Exact Algorithm......Page 42
3.4.1 Algorithm......Page 44
3.4.2 Experimental Results......Page 48
3.5 Quadratic Programming Algorithm......Page 52
3.5.1.1 Quadratic Programming......Page 53
3.5.1.2 Fuzzy Edit Path......Page 55
3.5.1.3 Quadratic Programming Edit Path Optimization......Page 57
3.5.2 Experimental Results......Page 60
3.6 Nearest-Neighbor Classi cation......Page 61
3.7 An Application: Data-Level Fusion of Graphs......Page 62
3.7.1 Fusion of Graphs......Page 63
3.7.2 Experimental Results......Page 65
4. Kernel Machines......Page 70
4.1 Learning Theory......Page 71
4.1.1 Empirical Risk Minimization......Page 72
4.1.2 Structural Risk Minimization......Page 74
4.2.1 Valid Kernels......Page 81
4.2.2 Feature Space Embedding and Kernel Trick......Page 83
4.3 Kernel Machines......Page 87
4.3.1 Support Vector Machine......Page 88
4.3.2 Kernel Principal Component Analysis......Page 92
4.3.3 Kernel Fisher Discriminant Analysis......Page 95
4.3.4 Using Non-Positive De nite Kernel Functions......Page 97
4.4 Nearest-Neighbor Classi cation Revisited......Page 98
5. Graph Kernels......Page 102
5.1 Kernel Machines for Graph Matching......Page 103
5.2 Related Work......Page 107
5.3 Trivial Similarity Kernel from Edit Distance......Page 108
5.4 Kernel from Maximum-Similarity Edit Path......Page 110
5.5 Diffusion Kernel from Edit Distance......Page 112
5.6 Zero Graph Kernel from Edit Distance......Page 115
5.7 Convolution Edit Kernel......Page 120
5.8 Local Matching Kernel......Page 128
5.9 Random Walk Edit Kernel......Page 132
6. Experimental Results......Page 142
6.1.1 Letter Line Drawing Graphs......Page 143
6.1.2 Image Graphs......Page 145
6.1.3 Diatom Graphs......Page 146
6.2.1 Biometric Person Authentication......Page 147
6.2.2 Fingerprint Classification......Page 148
6.2.3 Fingerprint Graphs......Page 150
6.3 Molecule Graph Data Set......Page 156
6.4 Experimental Setup......Page 159
6.5 Evaluation of Graph Edit Distance......Page 160
6.5.1 Letter Graphs......Page 161
6.5.2 Image Graphs......Page 164
6.5.3 Diatom Graphs......Page 166
6.5.4 Fingerprint Graphs......Page 167
6.5.5 Molecule Graphs......Page 171
6.6.1 Trivial Similarity Kernel from Edit Distance......Page 173
6.6.2 Kernel from Maximum-Similarity Edit Path......Page 175
6.6.3 Diffusion Kernel from Edit Distance......Page 176
6.6.4 Zero Graph Kernel from Edit Distance......Page 179
6.6.5 Convolution Edit Kernel......Page 181
6.6.6 Local Matching Kernel......Page 185
6.6.7 Random Walk Edit Kernel......Page 186
6.7 Summary and Discussion......Page 189
7. Conclusions......Page 198
A.1 Letter Data Set......Page 206
A.2 Image Data Set......Page 212
A.3 Diatom Data Set......Page 217
A.4 Fingerprint Data Set......Page 225
A.5 Molecule Data Set......Page 228
Bibliography......Page 234
Index......Page 244