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

Redefining the Graph Edit Distance

  • Datos identificativos

    Identificador: imarina:9230881
    Autores:
    Serratosa, Francesc
    Resumen:
    Graph edit distance has been used since 1983 to compare objects in machine learning when these objects are represented by attributed graphs instead of vectors. In these cases, the graph edit distance is usually applied to deduce a distance between attributed graphs. This distance is defined as the minimum amount of edit operations (deletion, insertion and substitution of nodes and edges) needed to transform a graph into another. Since now, it has been stated that the distance properties have to be applied [(1) non-negativity (2) symmetry (3) identity and (4) triangle inequality] to the involved edit operations in the process of computing the graph edit distance to make the graph edit distance a metric. In this paper, we show that there is no need to impose the triangle inequality in each edit operation. This is an important finding since in pattern recognition applications, the classification ratio usually maximizes in the edit operation combinations (deletion, insertion and substitution of nodes and edges) that the triangle inequality is not fulfilled.
  • Otros:

    Autor según el artículo: Serratosa, Francesc
    Departamento: Enginyeria Informàtica i Matemàtiques
    Autor/es de la URV: Serratosa Casanelles, Francesc d'Assís
    Palabras clave: Learning Graph edit distance Distance definition Attributed graphs
    Resumen: Graph edit distance has been used since 1983 to compare objects in machine learning when these objects are represented by attributed graphs instead of vectors. In these cases, the graph edit distance is usually applied to deduce a distance between attributed graphs. This distance is defined as the minimum amount of edit operations (deletion, insertion and substitution of nodes and edges) needed to transform a graph into another. Since now, it has been stated that the distance properties have to be applied [(1) non-negativity (2) symmetry (3) identity and (4) triangle inequality] to the involved edit operations in the process of computing the graph edit distance to make the graph edit distance a metric. In this paper, we show that there is no need to impose the triangle inequality in each edit operation. This is an important finding since in pattern recognition applications, the classification ratio usually maximizes in the edit operation combinations (deletion, insertion and substitution of nodes and edges) that the triangle inequality is not fulfilled.
    Acceso a la licencia de uso: https://creativecommons.org/licenses/by/3.0/es/
    Direcció de correo del autor: francesc.serratosa@urv.cat
    Identificador del autor: 0000-0001-6112-5913
    Fecha de alta del registro: 2024-10-12
    Versión del articulo depositado: info:eu-repo/semantics/publishedVersion
    Enlace a la fuente original: https://link.springer.com/article/10.1007/s42979-021-00792-5
    URL Documento de licencia: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referencia al articulo segun fuente origial: Sn Computer Science. 2 (6): Article numbre 438-
    Referencia de l'ítem segons les normes APA: Serratosa, Francesc (2021). Redefining the Graph Edit Distance. Sn Computer Science, 2(6), Article numbre 438-. DOI: 10.1007/s42979-021-00792-5
    DOI del artículo: 10.1007/s42979-021-00792-5
    Entidad: Universitat Rovira i Virgili
    Año de publicación de la revista: 2021
    Tipo de publicación: Journal Publications
  • Palabras clave:

    Learning
    Graph edit distance
    Distance definition
    Attributed graphs
  • Documentos:

  • Cerca a google

    Search to google scholar