Tesis doctoralsDepartament d'Enginyeria Informàtica i Matemàtiques

Learning the Graph Edit Distance through embedding the graph matching

  • Dades identificatives

    Identificador:  TDX:3092
    Autors:  Ahmed Algabli, Shaima
    Resum:
    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.
  • Altres:

    Editor: Universitat Rovira i Virgili
    Data: 2020-06-17
    Identificador: http://hdl.handle.net/10803/669612
    Departament/Institut: Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili.
    Idioma: eng
    Autor: Ahmed Algabli, Shaima
    Director: Serratosa Casanelles, Francesc
    Font: TDX (Tesis Doctorals en Xarxa)
    Format: 126 p., application/pdf
  • Paraules clau:

    Learning Cost
    Embedding
    Graph Edit Distance
    Enginyeria i arquitectura
  • Documents:

  • Cerca a google

    Search to google scholar