{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T05:46:08Z","timestamp":1780638368555,"version":"3.54.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Australian Research Council Fundings","award":["DP220103731"],"award-info":[{"award-number":["DP220103731"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Graph edit distance (GED) is an important metric for measuring the distance or similarity between two graphs. It is defined as the minimum number of edit operations required to transform one graph into another. Computing the exact GED between two graphs is an NP-hard problem. With the success of deep learning across various application domains, graph neural networks have also been recently utilized to predict the GED between graphs. However, the existing studies on learning-based methods have two significant limitations. (1)~The development of deep learning models for GED prediction has been explored in various research fields (e.g., databases, machine learning, information retrieval, and computer vision), yet cross-field evaluations have been quite limited. (2)~More importantly, all these advancements have been evaluated against a simple combinatorial heuristic baseline, with their models shown to outperform it. In this paper, we aim to bridge this knowledge gap. We first conduct a holistic review of the existing learning-based methods, categorizing them into non-interpretable and interpretable GED prediction approaches, while highlighting their overarching design principles and relationships among these models. Secondly, we present a simple yet effective combinatorial heuristic algorithm App-BMao for GED estimation, adapted from an existing exact GED computation algorithm. App-BMao provides interpretable GED estimation with controlled time and space complexity. Extensive empirical evaluations on three widely used datasets show that the new heuristic algorithm App-BMao outperforms all existing learning-based approaches for both interpretable and non-interpretable GED prediction.<\/jats:p>","DOI":"10.1145\/3725304","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-24","source":"Crossref","is-referenced-by-count":1,"title":["Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2782-4331","authenticated-orcid":false,"given":"Mouyi","family":"Xu","sequence":"first","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6830-3900","authenticated-orcid":false,"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. PyTorch Geometric. https:\/\/pytorch-geometric.readthedocs.io\/en\/latest\/generated\/torch_geometric.datasets. GEDDataset.html?highlight=geddataset#torch_geometric.datasets.GEDDataset"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2016.10.004"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5220\/0005209202710278"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489513"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290967"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5720"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--70362--1_18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00544-1"},{"key":"e_1_2_1_9_1","volume-title":"Blumenthal and Johann Gamper","author":"David","year":"2017","unstructured":"David B. Blumenthal and Johann Gamper. 2017. Exact Computation of Graph Edit Distance for Uniform and Nonuniform Metric Edit Costs. In Proc. of GbRPR'17. 211--221."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18224-7_19"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00074"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3153523"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90017-5"},{"key":"e_1_2_1_14_1","volume-title":"Proc. of SIGIR'21","author":"Doan Khoa D.","unstructured":"Khoa D. Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K. Reddy. 2021. Interpretable Graph Similarity Computation via Differentiable Optimal Alignment of Node Embeddings. In Proc. of SIGIR'21. 665--674."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20844-7_11"},{"key":"e_1_2_1_16_1","volume-title":"Proc. of SSSPR'14","volume":"8621","author":"Ga\u00fcz\u00e8re Benoit","year":"2014","unstructured":"Benoit Ga\u00fcz\u00e8re, S\u00e9bastien Bougleux, Kaspar Riesen, and Luc Brun. 2014. Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks. In Proc. of SSSPR'14, Vol. 8621. 73--82."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498246"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01588-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02278710"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.152"},{"key":"e_1_2_1_21_1","volume-title":"Proc. of ICLR'17","author":"Thomas","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In Proc. of ICLR'17."},{"key":"e_1_2_1_22_1","volume-title":"The Hungarian method for the assignment problem. Naval research logistics quarterly 2, 1--2","author":"Kuhn Harold W","year":"1955","unstructured":"Harold W Kuhn. 1955. The Hungarian method for the assignment problem. Naval research logistics quarterly 2, 1--2 (1955), 83--97."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.24963\/IJCAI.2021\/212"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594514"},{"key":"e_1_2_1_26_1","volume-title":"Proc. of NIPS'21","author":"Qin Can","year":"2021","unstructured":"Can Qin, Handong Zhao, LichenWang, HuanWang, Yulun Zhang, and Yun Fu. 2021. Slow Learning and Fast Inference: Efficient Graph Similarity Computation via Knowledge Distillation. In Proc. of NIPS'21. 14110--14121."},{"key":"e_1_2_1_27_1","volume-title":"Proc. of NIPS'22","author":"Ranjan Rishabh","year":"2022","unstructured":"Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkat Chakravarthy, Yogish Sabharwal, and Sayan Ranu. 2022. GREED: a neural framework for learning graph distance functions. In Proc. of NIPS'22. Article 1636, 13 pages."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2008.04.004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38221-5_15"},{"key":"e_1_2_1_30_1","volume-title":"Proc. of MLG'07","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 Proc. of MLG'07."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1983.6313167"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2014.04.015"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021800141550010X"},{"key":"e_1_2_1_34_1","volume-title":"Proc. of NIPS'13","author":"Socher Richard","unstructured":"Richard Socher, Danqi Chen, Christopher D. Manning, and Andrew Y. Ng. 2013. Reasoning With Neural Tensor Networks for Knowledge Base Completion. In Proc. of NIPS'13. 926--934."},{"key":"e_1_2_1_35_1","volume-title":"Proc. of ICLR'18","author":"Velickovic Petar","year":"2018","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph Attention Networks. In Proc. of ICLR'18."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR46437.2021.00520"},{"key":"e_1_2_1_37_1","volume-title":"Weinberger","author":"Wu Felix","year":"2019","unstructured":"Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. 2019. Simplifying Graph Convolutional Networks. In Proc. of ICML'19, Vol. 97. 6861--6871."},{"key":"e_1_2_1_38_1","volume-title":"Proc. of ICLR'19","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In Proc. of ICLR'19."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00056"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3422484"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687631"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467328"},{"key":"e_1_2_1_43_1","volume-title":"Proc. of NIPS'22","author":"Zhuo Wei","year":"2022","unstructured":"Wei Zhuo and Guang Tan. 2022. Efficient graph similarity computation with alignment regularization. In Proc. of NIPS'22. Article 2188, 13 pages."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:57:36Z","timestamp":1774983456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725304"],"URL":"https:\/\/doi.org\/10.1145\/3725304","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}