Author, as appears in the article.: Serratosa, Francesc

Department: Enginyeria Informàtica i Matemàtiques

URV's Author/s: Serratosa Casanelles, Francesc d'Assís

Abstract: 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.

licence for use: https://creativecommons.org/licenses/by/3.0/es/

Author's mail: francesc.serratosa@urv.cat

Author identifier: 0000-0001-6112-5913

Record's date: 2023-09-30

Papper version: info:eu-repo/semantics/publishedVersion

Link to the original source: https://link.springer.com/article/10.1007/s42979-021-00792-5

Licence document URL: http://repositori.urv.cat/ca/proteccio-de-dades/

Papper original source: 2 (6): Article numbre 438-

APA: Serratosa, Francesc (2021). Redefining the Graph Edit Distance. Sn Computer Science, 2(6), Article numbre 438-. DOI: 10.1007/s42979-021-00792-5

Article's DOI: 10.1007/s42979-021-00792-5

Entity: Universitat Rovira i Virgili

Journal publication year: 2021

Publication Type: Journal Publications