{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T21:49:19Z","timestamp":1771710559330,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/s42979-021-00792-5","type":"journal-article","created":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T10:03:01Z","timestamp":1630404181000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Redefining the Graph Edit Distance"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6112-5913","authenticated-orcid":false,"given":"Francesc","family":"Serratosa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,31]]},"reference":[{"issue":"4","key":"792_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0167-8655(83)90033-8","volume":"1","author":"H Bunke","year":"1983","unstructured":"Bunke H, Allermann G. Inexact graph matching for structural pattern recognition. Pattern Recogn Lett. 1983;1(4):245\u201353.","journal-title":"Pattern Recogn Lett"},{"issue":"3","key":"792_CR2","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","volume":"13","author":"A Sanfeliu","year":"1983","unstructured":"Sanfeliu A, Fu KS. A Distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern. 1983;13(3):353\u201362.","journal-title":"IEEE Trans Syst Man Cybern"},{"issue":"3","key":"792_CR3","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1016\/S0031-3203(01)00066-8","volume":"35","author":"A Sanfeliu","year":"2002","unstructured":"Sanfeliu A, Alqu\u00e9zar R, Andrade J, Climent J, Serratosa F, Verg\u00e9s J. Graph-based representations and techniques for image processing and image analysis. Pattern Recogn. 2002;35(3):639\u201350.","journal-title":"Pattern Recogn"},{"issue":"3","key":"792_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte D, Foggia P, Sansone C, Vento M. Thirty years of graph matching in pattern recognition. Int J Pattern Recognit Artif Intell. 2004;18(3):265\u201398.","journal-title":"Int J Pattern Recognit Artif Intell"},{"key":"792_CR5","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.patcog.2014.01.002","volume":"48","author":"M Vento","year":"2015","unstructured":"Vento M. A long trip in the charming world of graphs for pattern recognition. Pattern Recognit. 2015;48:291\u2013301.","journal-title":"Pattern Recognit"},{"issue":"3","key":"792_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s10044-012-0284-8","volume":"16","author":"L Livi","year":"2013","unstructured":"Livi L, Rizzi A. The graph matching problem. Pattern Anal Appl. 2013;16(3):253\u201383.","journal-title":"Pattern Anal Appl"},{"issue":"1","key":"792_CR7","doi-asserted-by":"publisher","first-page":"1450001","DOI":"10.1142\/S0218001414500013","volume":"28","author":"P Foggia","year":"2014","unstructured":"Foggia P, Percannella G, Vento M. Graph matching and learning in Pattern Recognition in the last 10 years. Int J Pattern Recognit Artif Intell. 2014;28(1):1450001 (40 pages).","journal-title":"Int J Pattern Recognit Artif Intell"},{"issue":"5","key":"792_CR8","doi-asserted-by":"publisher","first-page":"1260004","DOI":"10.1142\/S021800141260004X","volume":"26","author":"A Sol\u00e9","year":"2012","unstructured":"Sol\u00e9 A, Serratosa F, Sanfeliu A. On the graph edit distance cost: properties and applications. Int J Pattern Recognit Artif Intell. 2012;26(5):1260004 (21 pages).","journal-title":"Int J Pattern Recognit Artif Intell"},{"key":"792_CR9","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.patrec.2015.08.003","volume":"65","author":"F Serratosa","year":"2015","unstructured":"Serratosa F, Cort\u00e9s X. Graph Edit Distance: moving from global to local structure to solve the graph-matching problem. Pattern Recogn Lett. 2015;65:204\u201310.","journal-title":"Pattern Recogn Lett"},{"issue":"1","key":"792_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10044-008-0141-y","volume":"13","author":"X Gao","year":"2010","unstructured":"Gao X, Xiao B, Tao D, Li X. A survey of graph edit distance. Pattern Anal Appl. 2010;13(1):113\u201329.","journal-title":"Pattern Anal Appl"},{"key":"792_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.patrec.2020.07.010","volume":"138","author":"F Serratosa","year":"2020","unstructured":"Serratosa F. A general model to define the substitution, insertion and deletion graph edit costs based on an embedded space. Pattern Recogn Lett. 2020;138:115\u201322.","journal-title":"Pattern Recogn Lett"},{"key":"792_CR12","volume-title":"Structural pattern recognition with graph edit distance. Approximation algorithms and applications","author":"K Riesen","year":"2015","unstructured":"Riesen K. Structural pattern recognition with graph edit distance. Approximation algorithms and applications. Springer; 2015."},{"key":"792_CR13","doi-asserted-by":"publisher","first-page":"2493","DOI":"10.1016\/j.eswa.2012.10.071","volume":"40","author":"F Serratosa","year":"2013","unstructured":"Serratosa F, Cort\u00e9s X, Sol\u00e9-Ribalta A. Component retrieval based on a database of graphs for hand-written electronic-scheme digitalisation. Expert Syst Appl. 2013;40:2493\u2013502.","journal-title":"Expert Syst Appl"},{"issue":"3","key":"792_CR14","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1142\/S0218001404003253","volume":"18","author":"A Sanfeliu","year":"2004","unstructured":"Sanfeliu A, Serratosa F, Alqu\u00e9zar R. Second-order random graphs for modelling sets of attributed graphs and their application to object learning and recognition. Int J Pattern Recognit Artif Intell. 2004;18(3):375\u201396.","journal-title":"Int J Pattern Recognit Artif Intell"},{"issue":"3","key":"792_CR15","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1016\/S0031-3203(02)00107-3","volume":"36","author":"F Serratosa","year":"2003","unstructured":"Serratosa F, Alqu\u00e9zar R, Sanfeliu A. Function-Described Graphs for modelling objects represented by attributed graphs. Pattern Recogn. 2003;36(3):781\u201398.","journal-title":"Pattern Recogn"},{"issue":"6","key":"792_CR16","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1142\/S0218001402001915","volume":"16","author":"F Serratosa","year":"2002","unstructured":"Serratosa F, Alqu\u00e9zar R, Sanfeliu A. Synthesis of function-described graphs and clustering of attributed graphs. Int J Pattern Recognit Artif Intell. 2002;16(6):621\u201355.","journal-title":"Int J Pattern Recognit Artif Intell"},{"issue":"1","key":"792_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/TIT.1967.1053964","volume":"13","author":"TM Cover","year":"1967","unstructured":"Cover TM, Hart PE. Nearest neighbours pattern classification. IEEE Trans Inf Theory. 1967;13(1):21\u20137.","journal-title":"IEEE Trans Inf Theory"},{"key":"792_CR18","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.patcog.2019.01.043","volume":"90","author":"F Serratosa","year":"2019","unstructured":"Serratosa F. Graph edit distance: restrictions to be a metric. Pattern Recogn. 2019;90:250\u20136.","journal-title":"Pattern Recogn"},{"issue":"2","key":"792_CR19","doi-asserted-by":"publisher","first-page":"1650005","DOI":"10.1142\/S0218001416500051","volume":"30","author":"X Cort\u00e9s","year":"2016","unstructured":"Cort\u00e9s X, Serratosa F. Learning graph matching substitution weights based on the ground truth node correspondence. Int J Pattern Recognit Artif Intell. 2016;30(2):1650005 (22 pages).","journal-title":"Int J Pattern Recognit Artif Intell"},{"key":"792_CR20","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.patrec.2015.01.009","volume":"56","author":"X Cort\u00e9s","year":"2015","unstructured":"Cort\u00e9s X, Serratosa F. Learning graph-matching edit-costs based on the optimality of the oracle\u2019s node correspondences. Pattern Recogn Lett. 2015;56:22\u20139.","journal-title":"Pattern Recogn Lett"},{"key":"792_CR21","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/j.patrec.2018.08.026","volume":"112","author":"S Algabli","year":"2018","unstructured":"Algabli S, Serratosa F. Embedding the node-to-node mappings to learn the Graph edit distance parameters. Pattern Recogn Lett. 2018;112:353\u201360.","journal-title":"Pattern Recogn Lett"},{"key":"792_CR22","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1007\/s11063-019-10121-w","volume":"51","author":"P Santacruz","year":"2020","unstructured":"Santacruz P, Serratosa F. Learning the graph edit costs based on a learning model applied to sub-optimal graph matching. Neural Process Lett. 2020;51:881\u2013904.","journal-title":"Neural Process Lett"},{"key":"792_CR23","doi-asserted-by":"publisher","first-page":"106275","DOI":"10.1016\/j.knosys.2020.106275","volume":"105","author":"D Conte","year":"2020","unstructured":"Conte D, Serratosa F. Interactive online learning for graph matching using active strategies. Knowl Based Syst. 2020;105:106275.","journal-title":"Knowl Based Syst"},{"key":"792_CR24","first-page":"90","volume":"24","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D. Computers and intractability: a guide to the theory of NP-completeness. Siam Rev. 1979;24:90.","journal-title":"Siam Rev"},{"key":"792_CR25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.patrec.2015.07.010","volume":"65","author":"M Ferrer","year":"2015","unstructured":"Ferrer M, Serratosa F, Riesen K. Improving Bipartite graph matching by assessing the assignment confidence. Pattern Recogn Lett. 2015;65:29\u201336.","journal-title":"Pattern Recogn Lett"},{"key":"792_CR26","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.patrec.2014.04.015","volume":"45","author":"F Serratosa","year":"2014","unstructured":"Serratosa F. Fast computation of bipartite graph matching. Pattern Recogn Lett. 2014;45:244\u201350.","journal-title":"Pattern Recogn Lett"},{"issue":"2","key":"792_CR27","doi-asserted-by":"publisher","first-page":"1550010","DOI":"10.1142\/S021800141550010X","volume":"29","author":"F Serratosa","year":"2015","unstructured":"Serratosa F. Speeding up Fast bipartite Graph Matching trough a new cost matrix. Int J Pattern Recognit Artif Intell. 2015;29(2):1550010 (17 pages).","journal-title":"Int J Pattern Recognit Artif Intell"},{"key":"792_CR28","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.imavis.2015.06.005","volume":"40","author":"F Serratosa","year":"2015","unstructured":"Serratosa F. Computation of graph edit distance: reasoning about optimality and speed-up. Image Vis Comput. 2015;40:38\u201348.","journal-title":"Image Vis Comput"},{"key":"792_CR29","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.patrec.2018.04.003","volume":"134","author":"P Santacruz","year":"2020","unstructured":"Santacruz P, Serratosa F. Error-tolerant graph matching in linear computational cost using an initial small partial matching. Pattern Recognit Lett. 2020;134:10\u20139.","journal-title":"Pattern Recognit Lett"},{"issue":"2","key":"792_CR30","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P Hart","year":"1968","unstructured":"Hart P, Nilsson N, Raphael B. A formal basis for the heuristic determination of minimum cost paths. Trans Syst Sci Cybern. 1968;4(2):100\u20137.","journal-title":"Trans Syst Sci Cybern"},{"key":"792_CR31","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW. The Hungarian method for the assignment problem. Nav Res Log Q. 1955;2:83\u201397.","journal-title":"Nav Res Log Q"},{"key":"792_CR32","first-page":"519","volume":"10029","author":"C Moreno-Garcia","year":"2016","unstructured":"Moreno-Garcia C, Cort\u00e9s X, Serratosa F. A graph repository for learning error-tolerant graph matching. Syn Struct Pattern Recognit SSPR2016 LNCS. 2016;10029:519\u201329.","journal-title":"Syn Struct Pattern Recognit SSPR2016 LNCS"},{"key":"792_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61265-7","volume-title":"General Topology I: basic concepts and constructions dimension theory, encyclopaedia of mathematical sciences","author":"AV Arkhangel'skii","year":"1990","unstructured":"Arkhangel\u2019skii AV, Pontryagin LS. General Topology I: basic concepts and constructions dimension theory, encyclopaedia of mathematical sciences. Springer; 1990."},{"issue":"3","key":"792_CR34","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1109\/TSMCB.2005.846635","volume":"35","author":"M Neuhaus","year":"2005","unstructured":"Neuhaus M, Bunke H. Self-organizing maps for learning the edit costs in graph matching. IEEE Trans Syst Man Cyber Part B (Cybernetics). 2005;35(3):503\u201314.","journal-title":"IEEE Trans Syst Man Cyber Part B (Cybernetics)"},{"key":"792_CR35","doi-asserted-by":"crossref","unstructured":"Riesen K, Bunke H. IAM graph database repository for graph based pattern recognition and machine learning. In: Structural Syntactic and Statistical Pattern Recognition. Lecture Notes in Computer Science book series (LNCS, volume 5342); 2008, p. 287\u201397.","DOI":"10.1007\/978-3-540-89689-0_33"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00792-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-021-00792-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00792-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T13:31:28Z","timestamp":1636983088000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-021-00792-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,31]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["792"],"URL":"https:\/\/doi.org\/10.1007\/s42979-021-00792-5","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,31]]},"assertion":[{"value":"17 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Open access funding note missed in the original publication. Now, it has been added in the section Funding","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"438"}}