Learning the Graph Edit Distance through embedding the graph matching

Identifier:  TDX:3092

Handle: https://hdl.handle.net/20.500.11797/TDX3092

Authors:  Ahmed Algabli, Shaima

Abstract:
Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the model, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, biomedics, and network analysis, and so on .The first part of this thesis presents a general method to automatically learn the edit costs involved in the Graph Edit Distance. The method is based on embedding pairs of graphs and their ground-truth node-tonode mapping into a Euclidean space. In this way, the learning algorithm does not need to compute any Error-Tolerant Graph Matching, which is the main drawback of other methods due to its intrinsic exponential computational complexity. Nevertheless, the learning method has the main restriction that edit costs have to be constant. Then we test this method with several graph databases and also we apply it to perform image registration. In the second part of the thesis, this method is particularized to fingerprint verification. The two main differences with respect to the other method are that we only define the substitution edit costs on the nodes. Thus, we assume graphs do not have edges. And also, the learning method is not based on a linear classification but on a linear regression.