Defining the distance between two points in 2D or even 3D Euclidean space is easy and intuitive; we have easily understood the concept from our early school years. But what about defining the dissimilarity (that is, distance) between data types that cannot be transformed into points in an n-dimensional space? For instance, spell checking/correction programs in a search engine need to define the notion of distance for strings; bioinformatics applications need to calculate the distance between DNA strings. Fortunately, the concept of edit distance (insertions, deletions, or mutations of characters to transform one string to another) is a solution out of the maze of string comparisons.

However, traditional and modern scientific fields such as pattern recognition and complex network analysis deal with even more complicated, but generic enough to be widespread, data types such as graphs. Naturally, the need to calculate the similarity (inverse of distance) between graphs is a necessary primitive for algorithms related to chemical engineering, bioinformatics, online social networks, structural pattern recognition, and many more. The concept of graph edit distance introduced some 30 years ago is a very flexible graph distance model and has been applied in very diverse fields and applications.

This book is exactly about this fascinating topic: the definition, the study of properties, and the areas of application of the graph edit distance in the realm of structural pattern recognition. Even though the presentation context of the book (that is, pattern recognition) seems limited, the truth is that the material presented can be applied as-is in any area that is using the graph as a modeling primitive.

The book’s intended audience is advanced graduate students in science and engineering, but also professionals working in relevant fields. Although it cannot be used as a textbook for teaching, its wealth of references makes it an ideal point of entry for delving into the topic of graph edit distance.