Riesen K. Structural Pattern Recognition with Graph Edit Distance. Approximation Algorithms and Applications

Springer, 2015. — 164.The present book is concerned with the use of graphs in the field of structural pattern recognition. In fact, graphs are recognized as versatile alternative to feature vectors and thus, they found widespread application in pattern recognition and related fields (yet, the present book is actually focused on the field of pattern recognition only). In the last four decades, a huge number of procedures for graph distance computation, which is actually a basic requirement for pattern recognition, have been proposed in the literature. Graph edit distance, introduced about 30 years ago, is still one of the most flexible graph distance models available and subject of various recent research activities.
The objective of the present book is twofold. First, it gives a general and thorough introduction into the field of structural pattern recognition with a particular focus on graph edit distance (including a survey of graph edit distance applications that emerged during the last decade). Second, it presents a comprehensive compilation of diverse novel methods related to graph edit distance that have been developed and researched in the course of a recent research project that has been conducted under my supervision.Part I Foundations and Applications of Graph Edit Distance
Introduction and Basic Concepts
Graph Edit Distance
Bipartite Graph Edit Distance
Part II Recent Developments and Research on Graph Edit Distance
Improving the Distance Accuracy of Bipartite Graph Edit Distance
Learning Exact Graph Edit Distance
Speeding Up Bipartite Graph Edit Distance
Conclusions and Future Work
A: Experimental Evaluation of Sorted Beam Search
B: Data Sets