{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:38:03Z","timestamp":1778279883074,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:p>\n            Graph edit distance (GED) computation is a fundamental NP-hard problem in graph theory. Given a graph pair (\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ), GED is defined as the minimum number of primitive operations converting\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            to\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            . Early studies focus on search-based inexact algorithms such as A*-beam search, and greedy algorithms using bipartite matching due to its NP-hardness. They can obtain a sub-optimal solution by constructing an edit path (the sequence of operations that converts\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            to\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ). Recent studies convert the GED between a given graph pair (\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            ) into a similarity score in the range (0, 1) by a well designed function. Then machine learning models (mostly based on graph neural networks) are applied to predict the similarity score. They achieve a much higher numerical precision than the sub-optimal solutions found by classical algorithms. However, a major limitation is that these machine learning models cannot generate an edit path. They treat the GED computation as a pure regression task to bypass its intrinsic complexity, but ignore the essential task of converting\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            to\n            <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            . This severely limits the interpretability and usability of the solution.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we propose a novel deep learning framework that solves the GED problem in a two-step manner: 1) The proposed graph neural network GEDGNN is in charge of predicting the GED value and a matching matrix; and 2) A post-processing algorithm based on\n            <jats:italic>k<\/jats:italic>\n            -best matching is used to derive\n            <jats:italic>k<\/jats:italic>\n            possible node matchings from the matching matrix generated by GEDGNN. The best matching will finally lead to a high-quality edit path. Extensive experiments are conducted on three real graph data sets and synthetic power-law graphs to demonstrate the effectiveness of our framework. Compared to the best result of existing GNN-based models, the mean absolute error (MAE) on GED value prediction decreases by 4.9% ~ 74.3%. Compared to the state-of-the-art searching algorithm Noah, the MAE on GED value based on edit path reduces by 53.6% ~ 88.1%.\n          <\/jats:p>","DOI":"10.14778\/3594512.3594514","type":"journal-article","created":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T00:28:36Z","timestamp":1687480116000},"page":"1817-1829","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Computing Graph Edit Distance via Neural Graph Matching"],"prefix":"10.14778","volume":"16","author":[{"given":"Chengzhi","family":"Piao","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tingyang","family":"Xu","sequence":"additional","affiliation":[{"name":"Tencent AI Lab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiangguo","family":"Sun","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Rong","sequence":"additional","affiliation":[{"name":"Tencent AI Lab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kangfei","family":"Zhao","sequence":"additional","affiliation":[{"name":"Tencent AI Lab"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489513"},{"key":"e_1_2_1_2_1","unstructured":"Yunsheng Bai Hao Ding Song Bian Ting Chen Yizhou Sun and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. In WSDM. 384--392.  Yunsheng Bai Hao Ding Song Bian Ting Chen Yizhou Sun and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. In WSDM. 384--392."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"3219","DOI":"10.1609\/aaai.v34i04.5720","article-title":"Learning-based efficient graph similarity computation via multi-scale convolutional set matching","volume":"34","author":"Bai Yunsheng","year":"2020","unstructured":"Yunsheng Bai , Hao Ding , Ken Gu , Yizhou Sun , and Wei Wang . 2020 . Learning-based efficient graph similarity computation via multi-scale convolutional set matching . In AAAI , Vol. 34. 3219 -- 3226 . Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. 2020. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In AAAI, Vol. 34. 3219--3226.","journal-title":"AAAI"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2018.05.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(97)00060-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(97)00179-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Lijun Chang Xing Feng Xuemin Lin Lu Qin Wenjie Zhang and Dian Ouyang. 2020. Speeding Up GED Verification for Graph Similarity Search. In ICDE. 793--804.  Lijun Chang Xing Feng Xuemin Lin Lu Qin Wenjie Zhang and Dian Ouyang. 2020. Speeding Up GED Verification for Graph Similarity Search. In ICDE. 793--804.","DOI":"10.1109\/ICDE48307.2020.00074"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90017-5"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Chaoqi Chen Weiping Xie Wenbing Huang Yu Rong Xinghao Ding Yue Huang Tingyang Xu and Junzhou Huang. 2019. Progressive Feature Alignment for Unsupervised Domain Adaptation. In CVPR. 627--636.  Chaoqi Chen Weiping Xie Wenbing Huang Yu Rong Xinghao Ding Yue Huang Tingyang Xu and Junzhou Huang. 2019. Progressive Feature Alignment for Unsupervised Domain Adaptation. In CVPR. 627--636.","DOI":"10.1109\/CVPR.2019.00072"},{"key":"e_1_2_1_10_1","volume-title":"Speeding up graph edit distance computation through fast bipartite matching","author":"Fankhauser Stefan","unstructured":"Stefan Fankhauser , Kaspar Riesen , and Horst Bunke . 2011. Speeding up graph edit distance computation through fast bipartite matching . In GbRPR. Springer , 102--111. Stefan Fankhauser, Kaspar Riesen, and Horst Bunke. 2011. Speeding up graph edit distance computation through fast bipartite matching. In GbRPR. Springer, 102--111."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2015.02.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Karam Gouda and Mosab Hassaan. 2016. CSI_GED: An efficient approach for graph edit similarity computation. In ICDE. 265--276.  Karam Gouda and Mosab Hassaan. 2016. CSI_GED: An efficient approach for graph edit similarity computation. In ICDE. 265--276.","DOI":"10.1109\/ICDE.2016.7498246"},{"key":"e_1_2_1_13_1","unstructured":"Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS. 1024--1034.  Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS. 1024--1034."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"108167","DOI":"10.1016\/j.patcog.2021.108167","article-title":"GLMNet: Graph Learning-Matching Networks for Feature Matching","volume":"121","author":"Jiang Bo","year":"2022","unstructured":"Bo Jiang , Pengfei Sun , Jin Tang , and Bin Luo . 2022 . GLMNet: Graph Learning-Matching Networks for Feature Matching . Pattern Recognition 121 (2022), 108167 . Bo Jiang, Pengfei Sun, Jin Tang, and Bin Luo. 2022. GLMNet: Graph Learning-Matching Networks for Feature Matching. Pattern Recognition 121 (2022), 108167.","journal-title":"Pattern Recognition"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02278710"},{"key":"e_1_2_1_16_1","unstructured":"Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In ICLR.  Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In ICLR."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_18_1","unstructured":"Yujia Li Chenjie Gu Thomas Dullien Oriol Vinyals and Pushmeet Kohli. 2019. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. In ICML. 3835--3845.  Yujia Li Chenjie Gu Thomas Dullien Oriol Vinyals and Pushmeet Kohli. 2019. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. In ICML. 3835--3845."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Yongjiang Liang and Peixiang Zhao. 2017. Similarity Search in Graph Databases: A Multi-Layered Indexing Approach. In ICDE. 783--794.  Yongjiang Liang and Peixiang Zhao. 2017. Similarity Search in Graph Databases: A Multi-Layered Indexing Approach. In ICDE. 783--794.","DOI":"10.1109\/ICDE.2017.129"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Zhehan Liang Yu Rong Chenxin Li Yunlong Zhang Yue Huang Tingyang Xu Xinghao Ding and Junzhou Huang. 2021. Unsupervised Large-Scale Social Network Alignment via Cross Network Embedding. In CIKM. 1008--1017.  Zhehan Liang Yu Rong Chenxin Li Yunlong Zhang Yue Huang Tingyang Xu Xinghao Ding and Junzhou Huang. 2021. Unsupervised Large-Scale Social Network Alignment via Cross Network Embedding. In CIKM. 1008--1017.","DOI":"10.1145\/3459637.3482310"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-020-00733-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Michel Neuhaus Kaspar Riesen and Horst Bunke. 2006. Fast suboptimal algorithms for the computation of graph edit distance. In SPR-SSPR. 163--172.  Michel Neuhaus Kaspar Riesen and Horst Bunke. 2006. Fast suboptimal algorithms for the computation of graph edit distance. In SPR-SSPR. 163--172.","DOI":"10.1007\/11815921_17"},{"key":"e_1_2_1_23_1","unstructured":"Benjamin Paassen Daniele Grattarola Daniele Zambon Cesare Alippi and Barbara Hammer. 2021. Graph Edit Networks. In ICLR.  Benjamin Paassen Daniele Grattarola Daniele Zambon Cesare Alippi and Barbara Hammer. 2021. Graph Edit Networks. In ICLR."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.10.011"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2008.04.004"},{"key":"e_1_2_1_26_1","first-page":"12559","article-title":"Self-Supervised Graph Transformer on Large-Scale Molecular Data","volume":"33","author":"Rong Yu","year":"2020","unstructured":"Yu Rong , Yatao Bian , Tingyang Xu , Weiyang Xie , Ying WEI , Wenbing Huang , and Junzhou Huang . 2020 . Self-Supervised Graph Transformer on Large-Scale Molecular Data . In NeurIPS , Vol. 33. 12559 -- 12571 . Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying WEI, Wenbing Huang, and Junzhou Huang. 2020. Self-Supervised Graph Transformer on Large-Scale Molecular Data. In NeurIPS, Vol. 33. 12559--12571.","journal-title":"NeurIPS"},{"key":"e_1_2_1_27_1","unstructured":"Yu Rong Wenbing Huang Tingyang Xu and Junzhou Huang. 2019. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In ICLR.  Yu Rong Wenbing Huang Tingyang Xu and Junzhou Huang. 2019. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In ICLR."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Hanchen Wang Rong Hu Ying Zhang Lu Qin Wei Wang and Wenjie Zhang. 2022. Neural Subgraph Counting with Wasserstein Estimator. In SIGMOD. 160--175.  Hanchen Wang Rong Hu Ying Zhang Lu Qin Wei Wang and Wenjie Zhang. 2022. Neural Subgraph Counting with Wasserstein Estimator. In SIGMOD. 160--175.","DOI":"10.1145\/3514221.3526163"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Xiaoli Wang Xiaofeng Ding Anthony K.H. Tung Shanshan Ying and Hai Jin. 2012. An Efficient Graph Indexing Method. In ICDE. 210--221.  Xiaoli Wang Xiaofeng Ding Anthony K.H. Tung Shanshan Ying and Hai Jin. 2012. An Efficient Graph Indexing Method. In ICDE. 210--221.","DOI":"10.1109\/ICDE.2012.28"},{"key":"e_1_2_1_30_1","unstructured":"Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2019. How powerful are graph neural networks?. In ICLR.  Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2019. How powerful are graph neural networks?. In ICLR."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"10603","DOI":"10.1609\/aaai.v35i12.17268","article-title":"Hierarchical Graph Capsule Network","volume":"35","author":"Yang Jinyu","year":"2021","unstructured":"Jinyu Yang , Peilin Zhao , Yu Rong , Chaochao Yan , Chunyuan Li , Hehuan Ma , and Junzhou Huang . 2021 . Hierarchical Graph Capsule Network . In AAAI , Vol. 35. 10603 -- 10611 . Jinyu Yang, Peilin Zhao, Yu Rong, Chaochao Yan, Chunyuan Li, Hehuan Ma, and Junzhou Huang. 2021. Hierarchical Graph Capsule Network. In AAAI, Vol. 35. 10603--10611.","journal-title":"AAAI"},{"key":"e_1_2_1_32_1","volume-title":"Noah: Neural-optimized A* Search Algorithm for Graph Edit Distance Computation. In ICDE. 576--587.","author":"Yang Lei","year":"2021","unstructured":"Lei Yang and Lei Zou . 2021 . Noah: Neural-optimized A* Search Algorithm for Graph Edit Distance Computation. In ICDE. 576--587. Lei Yang and Lei Zou. 2021. Noah: Neural-optimized A* Search Algorithm for Graph Edit Distance Computation. In ICDE. 576--587."},{"key":"e_1_2_1_33_1","unstructured":"Dezhong Yao Yuhong Gu Gao Cong Hai Jin and Xinqiao Lv. 2022. Entity Resolution with Hierarchical Graph Attention Networks. In SIGMOD. 429--442.  Dezhong Yao Yuhong Gu Gao Cong Hai Jin and Xinqiao Lv. 2022. Entity Resolution with Hierarchical Graph Attention Networks. In SIGMOD. 429--442."},{"key":"e_1_2_1_34_1","volume-title":"Qiyan Li, Hao Zhang, and Yu Rong.","author":"Zhao Kangfei","year":"2023","unstructured":"Kangfei Zhao , Jeffrey Xu Yu , Qiyan Li, Hao Zhang, and Yu Rong. 2023 . Learned sketch for subgraph counting: a holistic approach. The VLDB Journal ( 2023), 1--26. Kangfei Zhao, Jeffrey Xu Yu, Qiyan Li, Hao Zhang, and Yu Rong. 2023. Learned sketch for subgraph counting: a holistic approach. The VLDB Journal (2023), 1--26."},{"key":"e_1_2_1_35_1","volume-title":"Hao Zhang, Qiyan Li, and Yu Rong.","author":"Zhao Kangfei","year":"2021","unstructured":"Kangfei Zhao , Jeffrey Xu Yu , Hao Zhang, Qiyan Li, and Yu Rong. 2021 . A Learned Sketch for Subgraph Counting. In SIGMOD. 2142--2155. Kangfei Zhao, Jeffrey Xu Yu, Hao Zhang, Qiyan Li, and Yu Rong. 2021. A Learned Sketch for Subgraph Counting. In SIGMOD. 2142--2155."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0306-1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0487-0"},{"key":"e_1_2_1_38_1","first-page":"964","article-title":"Efficient graph similarity search over large graph databases","volume":"27","author":"Zheng Weiguo","year":"2014","unstructured":"Weiguo Zheng , Lei Zou , Xiang Lian , Dong Wang , and Dongyan Zhao . 2014 . Efficient graph similarity search over large graph databases . TKDE 27 , 4 (2014), 964 -- 978 . Weiguo Zheng, Lei Zou, Xiang Lian, Dong Wang, and Dongyan Zhao. 2014. Efficient graph similarity search over large graph databases. TKDE 27, 4 (2014), 964--978.","journal-title":"TKDE"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3594512.3594514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T00:35:18Z","timestamp":1687480518000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3594512.3594514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4]]},"references-count":38,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10.14778\/3594512.3594514"],"URL":"https:\/\/doi.org\/10.14778\/3594512.3594514","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,4]]},"assertion":[{"value":"2023-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}