Francesc Serratosa
Graph edit distance or graph edit pseudo-distance?
Serratosa, Francesc; Cort�s, Xavier; Moreno, Carlos-Francisco
Authors
Contributors
Antonio Robles-Kelly
Editor
Marco Loog
Editor
Battista Biggio
Editor
Francisco Escolano
Editor
Richard Wilson
Editor
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
Presentation Conference Type | Conference Paper (published) |
---|---|
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) |
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 |
Peer Reviewed | Peer Reviewed |
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 |
Files
SERRATOSA 2016 Graph edit
(1.8 Mb)
PDF
You might also like
Few-shot symbol detection in engineering drawings.
(2024)
Journal Article
Two-layer ensemble of deep learning models for medical image segmentation.
(2024)
Journal Article
Downloadable Citations
About OpenAIR@RGU
Administrator e-mail: publications@rgu.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search