June 3, 2019
Ibrahim Chegrane (LACL - UPEC)Graph Edit Distance (GED) is a flexible and powerful technique to measure the amount of dissimilarity between two graphs. The Exact GED problem consists to find the best set of edit operations to transform one graph into the other. The allowed standard operations are substitution, deletion, and insertion; in which they are applied on both vertices and edges.
The power of GED approach appears in two folds, the first, it can be used at the same time to find the Exact and the Inexact Graph Matching where some errors are tolerated between the process of matching the two graphs. The second, the GED can easily integrate the domain specific information about object similarity by means of a specific edit cost function.
Indeed, the Exact-GED is used in various applications, especially in areas related to Pattern Recognition, such as: hand-writing recognition, person identification and authentication (example:fingerprint recognition), documents analysis, and in graph database search. Computing the Exact-GED can also be part of machine learning, Nearest-Neighbor, and data mining area.
This problem is known to be NP-hard and its complexity grows exponentially with the size of computed graphs. To compute the Exact GED, often A-Star and Branch and Bound (B\&B) algorithms are used.