Graph Classification and Clustering Based on Vector Space Embedding

The following section are included:

• Preface

• Acknowledgments

• Contents

The following sections are included:

• Pattern Recognition

• Learning Methodology

• Statistical and Structural Pattern Recognition

• Dissimilarity Representation for Pattern Recognition

• Summary and Outline

The following sections are included:

• Graph and Subgraph

• Exact Graph Matching

• Error-tolerant Graph Matching

• Summary and Broader Perspective

The following sections are included:

• Basic Definition and Properties
  • Conditions on Edit Cost Functions
  • Examples of Edit Cost Functions

• Exact Computation of GED

• Efficient Approximation Algorithms
  • Bipartite Graph Matching
  • Graph Edit Distance Computation by Means of Munkres’ Algorithm

• Exact vs. Approximate Graph Edit Distance -An Experimental Evaluation
  • Nearest-Neighbor Classification
  • Graph Data Set
  • Experimental Setup and Validation of the Meta Parameters
  • Results and Discussion

• Summary

The following sections are included:

• Graph Data Sets
  • Letter Graphs
  • Digit Graphs
  • GREC Graphs
  • Fingerprint Graphs
  • AIDS Graphs
  • Mutagenicity Graphs
  • Protein Graphs
  • Webpage Graphs

• Evaluation of Graph Edit Distance

• Data Visualization

• Summary

The following sections are included:

• Overview and Primer on Kernel Theory

• Kernel Functions

• Feature Map vs. Kernel Trick

• Kernel Machines
  • Support Vector Machine (SVM)
  • Principal Component Analysis (PCA)
  • k-Means Clustering

• Graph Kernels

• Experimental Evaluation

• Summary

The following sections are included:

• Related Work
  • Graph Embedding Techniques
  • Dissimilarities as a Representation Formalism

• Graph Embedding Using Dissimilarities
  • General Embedding Procedure and Properties
  • Relation to Kernel Methods
  • Relation to Lipschitz Embeddings
  • The Problem of Prototype Selection

• Prototype Selection Strategies

• Prototype Reduction Schemes

• Feature Selection Algorithms

• Defining the Reference Sets for Lipschitz Embeddings

• Ensemble Methods

• Summary

The following sections are included:

• Nearest-Neighbor Classifiers Applied to Vector Space Embedded Graphs

• Support Vector Machines Applied to Vector Space Embedded Graphs
  • Prototype Selection
    • Experimental Setup and Validation of the Meta Parameters
    • Results and Discussion
  • Prototype Reduction Schemes
    • Experimental Setup and Validation of the Meta Parameters
    • Results and Discussion
  • Feature Selection and Dimensionality Reduction
    • Experimental Setup and Validation of the Meta Parameters
    • Results and Discussion
  • Lipschitz Embeddings
    • Experimental Setup and Validation of the Meta Parameters
    • Results and Discussion
  • Ensemble Methods
    • Experimental Setup and Validation of the Meta Parameters
    • Results and Discussion

• Summary and Discussion

The following sections are included:

• Experimental Setup and Validation of the Meta Parameters

• Results and Discussion

• Summary and Discussion

The present book addresses the issue of graph based pattern recognition. A graph consists of a set of nodes which are possibly connected by edges. In the general case, relevant features of the underlying patterns are stored as labels attached to both nodes and edges. In fact, graphs are a versatile alternative to feature vectors, and are known to be a powerful and flexible representation formalism. The representational power of graphs is due to their ability to represent not only feature values but also binary relationships among different parts of an object. Feature vectors offer no direct possibility to capture such structural characteristics. Consequently, in applications where the patterns at hand are composed of several objects, i.e. in cases where structure plays an important role in the underlying patterns, graphs are definitely more appropriate than vectorial pattern descriptions. The flexibility of graphs stems from the fact that there are no size or labeling restrictions that constrain the representation of a given object. In contrast to feature vectors, where each pattern is represented by a constant number of numerical attributes, graphs allow us to adopt their size and complexity with respect to the size and complexity of the patterns to be modeled…

The following section are included:

• Appendix A: Validation of Cost Parameters

• Appendix B: Visualization of Graph Data

• Appendix C: Classifier Combination

• Appendix D: Validation of a k-NN classifier in the Embedding Space

• Appendix E: Validation of a SVM classifier in theEmbedding Space

• Appendix F: Validation of Lipschitz Embeddings

• Appendix G: Validation of Feature Selection Algorithms and PCA Reduction

• Appendix H: Validation of Classifier Ensemble

• Appendix I: Validation of Kernel k-Means Clustering

• Appendix J: Confusion Matrices

• Bibliography

• Index