Graph edit distance or graph edit pseudo-distance?

Abstract

Graph Edit Distance has been intensively used since its appearance in 1983. This distance is very appropriate if we want to compare a pair of attributed graphs from any domain and obtain not only a distance, but also the best correspondence between nodes of the involved graphs. In this paper, we want to analyse if the Graph Edit Distance can be really considered a distance or a pseudo-distance, since some restrictions of the distance function are not fulfilled. Distinguishing between both cases is important because the use of a distance is a restriction in some methods to return exact instead of approximate results. This occurs, for instance, in some graph retrieval techniques. Experimental validation shows that in most of the cases, it is not appropriate to denominate the Graph Edit Distance as a distance, but a pseudo-distance instead, since the triangle inequality is not fulfilled. Therefore, in these cases, the graph retrieval techniques not always return the optimal graph.

Citation

SERRATOSA, F., CORTÉS, X., and MORENO, C.-F. 2016. Graph edit distance or graph edit pseudo-distance? In Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F. and Wilson, R. (eds.). Structural, syntactic, and statistical pattern recognition: proceedings of the 2016 Joint International Association of Pattern Recognition (IAPR) International workshops on Statistical techniques in pattern recognition (SPR) and Structural and syntactic pattern recognition (SSPR) (S+SSPR 2020), 29 November - 2 December 2016, Merida, Mexico. Lecture notes in computer science, 10029. Cham: Springer [online], pages 530-540. Available from: https://doi.org/10.1007/978-3-319-49055-7_47

• Conference Name: 2016 Joint International Association of Pattern Recognition (IAPR) International workshops on Statistical techniques in pattern recognition (SPR) and Structural and syntactic pattern recognition (SSPR) (S+SSPR 2020)
• Conference Location: Merida, Mexico
• Start Date: Nov 29, 2016
• End Date: Dec 2, 2016
• Acceptance Date: Jun 1, 2016
• Online Publication Date: Nov 5, 2016
• Publication Date: Dec 31, 2016
• Deposit Date: Jun 5, 2020
• Publicly Available Date: Jun 30, 2020
• Publisher: Springer
• Pages: 530-540
• Series Title: Lecture notes in computer science
• Series Number: 10029
• Series ISSN: 0302-9743
• Book Title: Structural, syntactic, and statistical pattern recognition: proceedings of the 2016 Joint International Association of Pattern Recognition (IAPR) International workshops on Statistical techniques in pattern recognition (SPR) and Structural and syntactic p
• ISBN: 9783319490540
• DOI: https://doi.org/10.1007/978-3-319-49055-7_47
• Keywords: Graph edit distance; Edit cost; Distance function
• Public URL: https://rgu-repository.worktribe.com/output/924228