LEADER 05331nam 2200757Ia 450 001 9910777303003321 005 20230721031230.0 010 $a1-281-91905-5 010 $a9786611919054 010 $a981-277-020-8 035 $a(CKB)1000000000412081 035 $a(EBL)1193191 035 $a(SSID)ssj0000290382 035 $a(PQKBManifestationID)11225459 035 $a(PQKBTitleCode)TC0000290382 035 $a(PQKBWorkID)10423115 035 $a(PQKB)10903229 035 $a(WSP)00006523 035 $a(Au-PeEL)EBL1193191 035 $a(CaPaEBR)ebr10255827 035 $a(CaONFJC)MIL191905 035 $a(OCoLC)850162656 035 $a(MiAaPQ)EBC1193191 035 $a(EXLCZ)991000000000412081 100 $a20070818d2007 uy 0 101 0 $aeng 135 $aurcn||||||||| 181 $ctxt 182 $cc 183 $acr 200 10$aBridging the gap between graph edit distance and kernel machines$b[electronic resource] /$fMichel Neuhaus, Horst Bunke 210 $aSingapore ;$aHackensack, NJ $cWorld Scientific$dc2007 215 $a1 online resource (244 p.) 225 1 $aSeries in machine perception and artificial intelligence ;$vv. 68 300 $aExtended and revised version of the first author's PhD thesis. 311 $a981-270-817-0 320 $aIncludes bibliographical references (p. 221-230) and index. 327 $aPreface; Contents; 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 Classification 327 $a3.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 Classification Revisited; 5. Graph Kernels; 5.1 Kernel Machines for Graph Matching 327 $a5.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 327 $a6.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 327 $aA.3 Diatom Data Set A.4 Fingerprint Data Set; A.5 Molecule Data Set; Bibliography; Index 330 $aIn 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 410 0$aSeries in machine perception and artificial intelligence ;$vv. 68. 606 $aPattern recognition systems 606 $aMatching theory 606 $aMachine learning 606 $aKernel functions 606 $aGraph theory 615 0$aPattern recognition systems. 615 0$aMatching theory. 615 0$aMachine learning. 615 0$aKernel functions. 615 0$aGraph theory. 676 $a003.52 676 $a003/.52 676 $a006.4 700 $aNeuhaus$b Michel$01482416 701 $aBunke$b Horst$028587 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910777303003321 996 $aBridging the gap between graph edit distance and kernel machines$93700002 997 $aUNINA