ABSTRACT
This chapter reviews a number of exact and error-tolerant graph distance measures. It focuses on the graph edit distance (GED), which is recognized as one of the most flexible and universal error-tolerant matching paradigm. The chapter reviews the GED from three different points of view, namely, theory, algorithms, and applications. It introduces fundamental concepts related to GED, and gives an introduction to GED computation. The chapter reviews in detail exact and approximate methods for GED computation and finishes by introducing one of the most recent approximate algorithms for GED computation, which is based on bipartite graph matching. It concentrates on three basic applications: the weighted mean of a pair of graphs, graph embedding into vector spaces, and the median graph computation problem. The chapter ends by giving some conclusions and pointing to future directions in GED theory and practice.
