Structural pattern recognition with graph edit distance. Approximation algorithms and applications (Q518686)

The use of pattern recognition and classification is fundamental to many automated electronic systems in use today. Its applications range from military defence to medical diagnosis, from biometrics to machine learning, from bioinformatics to home entertainment, and more. Because of such diversity of applications various approaches to the problem of pattern recognition arose. One of the approaches is structural pattern recognition. The book presents the use of graphs in the field of structural pattern recognition. The author focuses on the graph edit distance, and sets two objectives in the book. The first objective is that the book should give a general and thorough introduction to the field of structural pattern recognition with a particular focus on graph edit distance. And the second objective is that it should present a comprehensive compilation of diverse novel methods related to graph edit distance that have been developed and investigated in the course of recent research. Both objectives are achieved in the book. In Chapter 1 -- which opens the first part of the book -- the author firstly introduces pattern recognition as a computer science discipline and outlines the major differences between statistical and structural pattern recognition. Next, graph-based pattern representation is formally introduced and complemented by a list of applications where graphs are employed. The rest of the chapter is devoted to formal introductions of diverse graph matching definitions and a brief survey of existing graph matching methodologies. Chapter 2 gives a formal definition of graph edit distance and introduces some basic properties of this distance model. Moreover, it presents an overview of how the cost model can be chosen in a certain graph edit distance application. Then, the exact computation of graph edit distance based on a tree search algorithm is outlined. The chapter ends with a brief review of three general approaches to graph edit distance-based pattern recognition. In Chapter 3, the problem of graph edit distance is reformulated into a quadratic assignment problem, which builds the basis for an approximation algorithm -- the bipartite graph edit distance algorithm (BP-GED). The algorithm gives rise to an upper and a lower bound to the exact edit distance. The introduced bounds are empirically evaluated on four standard graph sets. At the end of the chapter the author gives a brief survey of pattern recognition applications that make use of the proposed approximation algorithm. The second part of the book starts with Chapter 4. In this chapter, the author concentrates on extensions of BP-GED to obtain more accurate approximation of the distance. The first extension is based on post-processing of the search procedure. Various strategies are proposed to obtain this aim, i.e., iterative search, floating search, genetic search, greedy search, genetic search with swap strategy and beam search. The second extension takes more structural information into account when the basic assignment problem is solved on the local substructures of the graph. For this aim, node centrality measures are used. Both extensions are evaluated using different graph sets. In Chapter 5, two more approaches to reducing the approximation error are introduced. In the first approach, the exact edit distance is estimated using the distance bounds obtained using the BP-GED and regression analysis. In the second approach, a novel methodology that is able to predict incorrect node operations is introduced. The approaches introduced in the chapter are experimentally evaluated on various graph datasets. Chapter 6 is devoted to the problem of speeding up the BP-GED algorithm. The author introduces and compares several different strategies to speed up one of the steps in the algorithm. The introduced strategies are the following: the tie break strategy, refined greedy assignment, greedy assignment regarding loss, order of node processing and greedy sort assignment. The book ends with some conclusions and directions for future work, which are presented in Chapter 7. In the two appendices, the author describes the experimental evaluation of the sorted beam search (Appendix A) and the different data sets that were used in the research (Appendix B). The book is written in a very accessible fashion. The author gives many examples presenting the notations and problems considered. The book is suitable for graduate students and is an ideal reference for researchers and professionals interested in graph edit distance and its applications in pattern recognition.