Graph Classification and Clustering Based on Vector Space Embedding (Series in Machine Perception and Artificial Intelligence)

✍ Scribed by Kaspar Riesen, Horst Bunke

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

✦ Synopsis

This book is concerned with a fundamentally novel approach to graph-based pattern recognition based on vector space embedding of graphs. It aims at condensing the high representational power of graphs into a computationally efficient and mathematically convenient feature vector. This volume utilizes the dissimilarity space representation originally proposed by Duin and Pekalska to embed graphs in real vector spaces. Such an embedding gives one access to all algorithms developed in the past for feature vectors, which has been the predominant representation formalism in pattern recognition and related areas for a long time.

✦ Table of Contents

Contents......Page 12
Preface......Page 8
Acknowledgments......Page 10
1.1 Pattern Recognition......Page 16
1.2 Learning Methodology......Page 18
1.3 Statistical and Structural Pattern Recognition......Page 21
1.4 Dissimilarity Representation for Pattern Recognition......Page 24
1.5 Summary and Outline......Page 27
2. Graph Matching......Page 30
2.1 Graph and Subgraph......Page 32
2.2 Exact Graph Matching......Page 34
2.3 Error-tolerant Graph Matching......Page 42
2.4 Summary and Broader Perspective......Page 47
3. Graph Edit Distance......Page 50
3.1 Basic Definition and Properties......Page 52
3.1.1 Conditions on Edit Cost Functions......Page 54
3.1.2 Examples of Edit Cost Functions......Page 56
3.2 Exact Computation of GED......Page 59
3.3 Efficient Approximation Algorithms......Page 61
3.3.1 Bipartite Graph Matching......Page 62
3.3.2 Graph Edit Distance Computation by Means of Munkres' Algorithm......Page 67
3.4.1 Nearest-Neighbor Classification......Page 70
3.4.2 Graph Data Set......Page 71
3.4.3 Experimental Setup and Validation of the Meta Parameters......Page 72
3.4.4 Results and Discussion......Page 73
3.5 Summary......Page 78
4. Graph Data......Page 80
4.1.1 Letter Graphs......Page 81
4.1.2 Digit Graphs......Page 83
4.1.3 GREC Graphs......Page 86
4.1.4 Fingerprint Graphs......Page 89
4.1.5 AIDS Graphs......Page 92
4.1.6 Mutagenicity Graphs......Page 93
4.1.7 Protein Graphs......Page 94
4.1.8 Webpage Graphs......Page 96
4.2 Evaluation of Graph Edit Distance......Page 98
4.3 Data Visualization......Page 107
4.4 Summary......Page 110
5.1 Overview and Primer on Kernel Theory......Page 112
5.2 Kernel Functions......Page 113
5.3 Feature Map vs. Kernel Trick......Page 119
5.4.1 Support Vector Machine (SVM)......Page 125
5.4.2 Principal Component Analysis (PCA)......Page 132
5.4.3 k-Means Clustering......Page 137
5.5 Graph Kernels......Page 140
5.6 Experimental Evaluation......Page 144
5.7 Summary......Page 146
6. Graph Embedding Using Dissimilarities......Page 148
6.1.1 Graph Embedding Techniques......Page 150
6.1.2 Dissimilarities as a Representation Formalism......Page 152
6.2.1 General Embedding Procedure and Properties......Page 154
6.2.2 Relation to Kernel Methods......Page 157
6.2.3 Relation to Lipschitz Embeddings......Page 159
6.2.4 The Problem of Prototype Selection......Page 161
6.3 Prototype Selection Strategies......Page 163
6.4 Prototype Reduction Schemes......Page 172
6.5 Feature Selection Algorithms......Page 178
6.6 Defining the Reference Sets for Lipschitz Embeddings......Page 185
6.7 Ensemble Methods......Page 186
6.8 Summary......Page 188
7. Classification Experiments with Vector Space Embedded Graphs......Page 190
7.1 Nearest-Neighbor Classifiers Applied to Vector Space Embedded Graphs......Page 191
7.2.1.1 Experimental Setup and Validation of the Meta Parameters......Page 196
7.2.1.2 Results and Discussion......Page 198
7.2.2.1 Experimental Setup and Validation of the Meta Parameters......Page 207
7.2.2.2 Results and Discussion......Page 208
7.2.3.1 Experimental Setup and Validation of the Meta Parameters......Page 210
7.2.3.2 Results and Discussion......Page 215
7.2.4.1 Experimental Setup and Validation of the Meta Parameters......Page 220
7.2.4.2 Results and Discussion......Page 222
7.2.5.1 Experimental Setup and Validation of the Meta Parameters......Page 225
7.2.5.2 Results and Discussion......Page 227
7.3 Summary and Discussion......Page 229
8. Clustering Experiments with Vector Space Embedded Graphs......Page 236
8.1 Experimental Setup and Validation of the Meta parameters......Page 237
8.2 Results and Discussion......Page 241
8.3 Summary and Discussion......Page 246
9. Conclusions......Page 250
Appendix A Validation of Cost Parameters......Page 262
Appendix B Visualization of Graph Data......Page 270
Appendix C Classifier Combination......Page 274
Appendix D Validation of a k-NN classifier in the Embedding Space......Page 278
Appendix E Validation of a SVM classifier in the Embedding Space......Page 288
Appendix F Validation of Lipschitz Embeddings......Page 292
Appendix G Validation of Feature Selection Algorithms and PCA Reduction......Page 304
Appendix H Validation of Classifier Ensemble......Page 308
Appendix I Validation of Kernel k-Means Clustering......Page 310
Appendix J Confusion Matrices......Page 320
Bibliography......Page 324
Index......Page 344