{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T00:52:10Z","timestamp":1783385530341,"version":"3.54.6"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>\n            The graph edit distance (GED) is among the most widely used graph similarity measures in practice. It asks for a minimum cost edit path between two given labeled graphs\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">H<\/jats:italic>\n            , where the edit path is defined as a sequence of operations (e.g., node and edge insertions, deletions or substitutions) that successively transform the graph\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            into\n            <jats:italic toggle=\"yes\">H.<\/jats:italic>\n          <\/jats:p>\n          <jats:p>In this work, we suggest a new ILP formulation (FORI) based on orienting the corresponding edge variables. Moreover, we suggest enhancing two state-of-the-art ILP formulations by incorporating additional inequalities. We theoretically compare the strength of the formulations with respect to their Linear Programming relaxations. The result is a hierarchy with (FORI) at the top.<\/jats:p>\n          <jats:p>Our extensive evaluation on widely used benchmark sets shows that our improved formulations run significantly faster than the previous ones. These allow to solve to proven optimality all the reference instances from common databases, such as the IAM Graph Database, many of which were prohibitive with state-of-the-art methods. Moreover, we are able to compute the GED of a small pattern and a large graph such as CORA and PUBMED, having up to 19,717 nodes and 44,327 edges.<\/jats:p>","DOI":"10.14778\/3749646.3749726","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4737-4749","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Enhancing Graph Edit Distance Computation: Stronger and Orientation-Based ILP Formulations"],"prefix":"10.14778","volume":"18","author":[{"given":"Andrea","family":"D'Ascenzo","sequence":"first","affiliation":[{"name":"Luiss University, Rome, Italy and Gran Sasso Science Institute, L'Aquila, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julian","family":"Meffert","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[{"name":"University of Bonn, Bonn, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrizio","family":"Rossi","sequence":"additional","affiliation":[{"name":"University of L'Aquila, L'Aquila, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2017.10.007"},{"key":"e_1_2_1_2_1","volume-title":"An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems. In ICPRAM 2015 - Proceedings of the International Conference on Pattern Recognition Applications and Methods","volume":"1","author":"Abu-Aisheh Zeina","year":"2015","unstructured":"Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, and Patrick Martineau. 2015. An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems. In ICPRAM 2015 - Proceedings of the International Conference on Pattern Recognition Applications and Methods, Volume 1, Lisbon, Portugal, 10\u201312 January, 2015, Maria De Marsico, M\u00e1rio A. T. Figueiredo, and Ana L. N. Fred (Eds.). SciTePress, 271\u2013278."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489513"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-019-00544-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.PATREC.2018.05.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.PATREC.2016.10.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00074"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3153523"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.KNOSYS.2018.10.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"M. Conforti G. Cornu\u00e9jols and G. Zambelli. 2014. Integer Programming. Springer International Publishing.","DOI":"10.1007\/978-3-319-11008-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21534-6_5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446097"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData50022.2020.9378349"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10044-008-0141-Y"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498246"},{"key":"e_1_2_1_16_1","unstructured":"Gurobi Optimization LLC. 2023. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_1_17_1","volume-title":"Graph Edit Distance Evaluation Datasets: Pitfalls and Mitigation. In The Third Learning on Graphs Conference. https:\/\/openreview.net\/forum?id=guapIeLs02 Virtual Event), November 26","author":"Jain Eeshaan","year":"2024","unstructured":"Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, and Abir De. 2024. Graph Edit Distance Evaluation Datasets: Pitfalls and Mitigation. In The Third Learning on Graphs Conference. https:\/\/openreview.net\/forum?id=guapIeLs02 Virtual Event), November 26.29, 2024."},{"key":"e_1_2_1_18_1","volume-title":"Graph Edit Distance with General Costs Using Neural Set Divergence. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.","author":"Jain Eeshaan","year":"2024","unstructured":"Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, and Abir De. 2024. Graph Edit Distance with General Costs Using Neural Set Divergence. In The Thirty-eighth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.152"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.PATREC.2023.03.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.PATCOG.2017.07.029"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58325-4_168"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.24963\/IJCAI.2020\/74"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Andrea Lodi and Andrea Tramontani. 2013. Performance variability in mixed-integer programming. In Theory driven by influential applications. INFORMS 1\u201312.","DOI":"10.1287\/educ.2013.0112"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1142\/6523"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2022.11.119"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594514"},{"key":"e_1_2_1_28_1","first-page":"22518","article-title":"Greed: A neural framework for learning graph distance functions","volume":"35","author":"Ranjan Rishabh","year":"2022","unstructured":"Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. 2022. Greed: A neural framework for learning graph distance functions. Advances in Neural Information Processing Systems 35 (2022), 22518\u201322530.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci900035z"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27252-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89689-0_33"},{"key":"e_1_2_1_32_1","volume-title":"MLG 2007, Firence, Italy, August 1\u20133, 2007, Proceedings, Paolo Frasconi, Kristian Kersting, and Koji Tsuda (Eds.). http:\/\/mlg07","author":"Riesen Kaspar","year":"2007","unstructured":"Kaspar Riesen, Stefan Fankhauser, and Horst Bunke. 2007. Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic. In Mining and Learning with Graphs, MLG 2007, Firence, Italy, August 1\u20133, 2007, Proceedings, Paolo Frasconi, Kristian Kersting, and Koji Tsuda (Eds.). http:\/\/mlg07.dsi.unifi.it\/pdf\/02_Riesen.pdf"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx481"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/NAR\/GKH081"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR46437.2021.00520"},{"key":"e_1_2_1_36_1","volume-title":"Integer programming","author":"Wolsey Laurence A","unstructured":"Laurence A Wolsey. 2020. Integer programming. John Wiley & Sons."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2024.110697"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3054775"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687631"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467328"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749726","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:20:45Z","timestamp":1757042445000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749726"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749726"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749726","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}