Bridging the Gap Between Graph Edit Distance and Kernel Machines.
Title:
Bridging the Gap Between Graph Edit Distance and Kernel Machines.
Author:
Neuhaus, Michel.
ISBN:
9789812770202
Personal Author:
Physical Description:
1 online resource (244 pages)
Series:
Series in Machine Perception and Artificial Intelligence ; v.68
Series in Machine Perception and Artificial Intelligence
Contents:
Contents -- Preface -- 1. Introduction -- 2. Graph Matching -- 2.1 Graph and Subgraph -- 2.2 Exact Graph Matching -- 2.3 Error-Tolerant Graph Matching -- 3. Graph Edit Distance -- 3.1 Definition -- 3.2 Edit Cost Functions -- 3.2.1 Conditions on Edit Costs -- 3.2.2 Examples of Edit Costs -- 3.3 Exact Algorithm -- 3.4 Efficient Approximate Algorithm -- 3.4.1 Algorithm -- 3.4.2 Experimental Results -- 3.5 Quadratic Programming Algorithm -- 3.5.1 Algorithm -- 3.5.1.1 Quadratic Programming -- 3.5.1.2 Fuzzy Edit Path -- 3.5.1.3 Quadratic Programming Edit Path Optimization -- 3.5.2 Experimental Results -- 3.6 Nearest-Neighbor Classi cation -- 3.7 An Application: Data-Level Fusion of Graphs -- 3.7.1 Fusion of Graphs -- 3.7.2 Experimental Results -- 4. Kernel Machines -- 4.1 Learning Theory -- 4.1.1 Empirical Risk Minimization -- 4.1.2 Structural Risk Minimization -- 4.2 Kernel Functions -- 4.2.1 Valid Kernels -- 4.2.2 Feature Space Embedding and Kernel Trick -- 4.3 Kernel Machines -- 4.3.1 Support Vector Machine -- 4.3.2 Kernel Principal Component Analysis -- 4.3.3 Kernel Fisher Discriminant Analysis -- 4.3.4 Using Non-Positive De nite Kernel Functions -- 4.4 Nearest-Neighbor Classi cation Revisited -- 5. Graph Kernels -- 5.1 Kernel Machines for Graph Matching -- 5.2 Related Work -- 5.3 Trivial Similarity Kernel from Edit Distance -- 5.4 Kernel from Maximum-Similarity Edit Path -- 5.5 Diffusion Kernel from Edit Distance -- 5.6 Zero Graph Kernel from Edit Distance -- 5.7 Convolution Edit Kernel -- 5.8 Local Matching Kernel -- 5.9 Random Walk Edit Kernel -- 6. Experimental Results -- 6.1 Line Drawing and Image Graph Data Sets -- 6.1.1 Letter Line Drawing Graphs -- 6.1.2 Image Graphs -- 6.1.3 Diatom Graphs -- 6.2 Fingerprint Graph Data Set -- 6.2.1 Biometric Person Authentication -- 6.2.2 Fingerprint Classification -- 6.2.3 Fingerprint Graphs.
6.3 Molecule Graph Data Set -- 6.4 Experimental Setup -- 6.5 Evaluation of Graph Edit Distance -- 6.5.1 Letter Graphs -- 6.5.2 Image Graphs -- 6.5.3 Diatom Graphs -- 6.5.4 Fingerprint Graphs -- 6.5.5 Molecule Graphs -- 6.6 Evaluation of Graph Kernels -- 6.6.1 Trivial Similarity Kernel from Edit Distance -- 6.6.2 Kernel from Maximum-Similarity Edit Path -- 6.6.3 Diffusion Kernel from Edit Distance -- 6.6.4 Zero Graph Kernel from Edit Distance -- 6.6.5 Convolution Edit Kernel -- 6.6.6 Local Matching Kernel -- 6.6.7 Random Walk Edit Kernel -- 6.7 Summary and Discussion -- 7. Conclusions -- Appendix A Graph Data Sets -- A.1 Letter Data Set -- A.2 Image Data Set -- A.3 Diatom Data Set -- A.4 Fingerprint Data Set -- A.5 Molecule Data Set -- Bibliography -- Index.
Abstract:
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.
Local Note:
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2017. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
Genre:
Added Author:
Electronic Access:
Click to View