Articles producció científica> Enginyeria Informàtica i Matemàtiques

Learning the Graph Edit Costs Based on a Learning Model Applied to Sub-optimal Graph Matching

  • Dades identificatives

    Identificador: imarina:6285542
    Autors:
    Santacruz, PepSerratosa, Francesc
    Resum:
    Attributed graphs are used to represent patterns composed of several parts in pattern recognition. The nature of these patterns can be diverse, from images, to handwritten characters, maps or fingerprints. Graph edit distance has become an important tool in structural pattern recognition since it allows us to measure the dissimilarity of attributed graphs. It is based on transforming one graph into another through some edit operations such as substitution, deletion and insertion of nodes and edges. It has two main constraints: it requires an adequate definition of the costs of these operations and its computation cost is exponential with regard to the number of nodes. In this paper, we first present a general framework to automatically learn these edit costs considering graph edit distance is computed in a sub-optima way. Then, we specify this framework in two different models based on neural networks and probability density functions. An exhaustive practical validation on 14 public databases, which have different features such as the size of the graphs, the number of attributes or the number of graphs per class have been performed. This validation shows that with the learned edit costs, the accuracy is higher than with some manually imposed costs or other costs automatically learned by previous methods.
  • Altres:

    Autor segons l'article: Santacruz, Pep; Serratosa, Francesc
    Departament: Enginyeria Informàtica i Matemàtiques
    Autor/s de la URV: Serratosa Casanelles, Francesc d'Assís
    Paraules clau: Probability density function Neural network Learning the graph edit costs Graph embedding into vector Graph edit distance
    Resum: Attributed graphs are used to represent patterns composed of several parts in pattern recognition. The nature of these patterns can be diverse, from images, to handwritten characters, maps or fingerprints. Graph edit distance has become an important tool in structural pattern recognition since it allows us to measure the dissimilarity of attributed graphs. It is based on transforming one graph into another through some edit operations such as substitution, deletion and insertion of nodes and edges. It has two main constraints: it requires an adequate definition of the costs of these operations and its computation cost is exponential with regard to the number of nodes. In this paper, we first present a general framework to automatically learn these edit costs considering graph edit distance is computed in a sub-optima way. Then, we specify this framework in two different models based on neural networks and probability density functions. An exhaustive practical validation on 14 public databases, which have different features such as the size of the graphs, the number of attributes or the number of graphs per class have been performed. This validation shows that with the learned edit costs, the accuracy is higher than with some manually imposed costs or other costs automatically learned by previous methods.
    Àrees temàtiques: Software Neurosciences Neuroscience (miscellaneous) Neuroscience (all) Interdisciplinar General neuroscience Engenharias iv Computer science, artificial intelligence Computer networks and communications Ciência da computação Artificial intelligence
    Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/
    ISSN: 1370-4621
    Adreça de correu electrònic de l'autor: francesc.serratosa@urv.cat
    Identificador de l'autor: 0000-0001-6112-5913
    Data d'alta del registre: 2024-10-12
    Versió de l'article dipositat: info:eu-repo/semantics/acceptedVersion
    Enllaç font original: https://link.springer.com/article/10.1007%2Fs11063-019-10121-w
    URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referència a l'article segons font original: Neural Processing Letters. 51 (1): 881-904
    Referència de l'ítem segons les normes APA: Santacruz, Pep; Serratosa, Francesc (2020). Learning the Graph Edit Costs Based on a Learning Model Applied to Sub-optimal Graph Matching. Neural Processing Letters, 51(1), 881-904. DOI: 10.1007/s11063-019-10121-w
    DOI de l'article: 10.1007/s11063-019-10121-w
    Entitat: Universitat Rovira i Virgili
    Any de publicació de la revista: 2020
    Tipus de publicació: Journal Publications
  • Paraules clau:

    Artificial Intelligence,Computer Networks and Communications,Computer Science, Artificial Intelligence,Neuroscience (Miscellaneous),Neurosciences,Software
    Probability density function
    Neural network
    Learning the graph edit costs
    Graph embedding into vector
    Graph edit distance
    Software
    Neurosciences
    Neuroscience (miscellaneous)
    Neuroscience (all)
    Interdisciplinar
    General neuroscience
    Engenharias iv
    Computer science, artificial intelligence
    Computer networks and communications
    Ciência da computação
    Artificial intelligence
  • Documents:

  • Cerca a google

    Search to google scholar