{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T12:18:10Z","timestamp":1771935490792,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T00:00:00Z","timestamp":1697846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF of China","award":["61925203"],"award-info":[{"award-number":["61925203"]}]},{"name":"NSF of China","award":["U22B2021"],"award-info":[{"award-number":["U22B2021"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,10,21]]},"DOI":"10.1145\/3583780.3614959","type":"proceedings-article","created":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T07:45:26Z","timestamp":1697874326000},"page":"1503-1512","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8205-4564","authenticated-orcid":false,"given":"Junfeng","family":"Liu","sequence":"first","affiliation":[{"name":"Beihang University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4088-1266","authenticated-orcid":false,"given":"Min","family":"Zhou","sequence":"additional","affiliation":[{"name":"Huawei Noah's Ark Lab, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4050-0443","authenticated-orcid":false,"given":"Shuai","family":"Ma","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8988-4740","authenticated-orcid":false,"given":"Lujia","family":"Pan","sequence":"additional","affiliation":[{"name":"Huawei Noah's Ark Lab, Shenzhen, China"}]}],"member":"320","published-online":{"date-parts":[[2023,10,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","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. 271--278. 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. 271--278.","DOI":"10.5220\/0005209202710278"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489513"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","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.","DOI":"10.1145\/3289600.3290967"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","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. 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. 3219--3226.","DOI":"10.1609\/aaai.v34i04.5720"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00544-1"},{"key":"e_1_3_2_1_6_1","first-page":"211","article-title":"Exact Computation of Graph Edit Distance for Uniform and Non-uniform Metric Edit Costs","volume":"10310","author":"Blumenthal David B.","year":"2017","unstructured":"David B. Blumenthal and Johann Gamper . 2017 . Exact Computation of Graph Edit Distance for Uniform and Non-uniform Metric Edit Costs . In GbRPR , Vol. 10310. 211 -- 221 . David B. Blumenthal and Johann Gamper. 2017. Exact Computation of Graph Edit Distance for Uniform and Non-uniform Metric Edit Costs. In GbRPR, Vol. 10310. 211--221.","journal-title":"GbRPR"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2018.05.002"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.jcim.8b00820"},{"key":"e_1_3_2_1_9_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_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3153523"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2018.10.002"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Minsu Cho Karteek Alahari and Jean Ponce. 2013. Learning graphs to match. In ICCV. 25--32. Minsu Cho Karteek Alahari and Jean Ponce. 2013. Learning graphs to match. In ICCV. 25--32.","DOI":"10.1109\/ICCV.2013.11"},{"key":"e_1_3_2_1_13_1","first-page":"2292","article-title":"Sinkhorn distances: Lightspeed computation of optimal transport","volume":"26","author":"Cuturi Marco","year":"2013","unstructured":"Marco Cuturi . 2013 . Sinkhorn distances: Lightspeed computation of optimal transport . NeurIPS , Vol. 26 (2013), 2292 -- 2300 . Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. NeurIPS, Vol. 26 (2013), 2292--2300.","journal-title":"NeurIPS"},{"key":"e_1_3_2_1_14_1","volume-title":"Graph Neural Networks with Learnable Structural and Positional Representations. In International Conference on Learning Representations.","author":"Dwivedi Vijay Prakash","year":"2022","unstructured":"Vijay Prakash Dwivedi , Anh Tuan Luu , Thomas Laurent , Yoshua Bengio , and Xavier Bresson . 2022 . Graph Neural Networks with Learnable Structural and Positional Representations. In International Conference on Learning Representations. Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2022. Graph Neural Networks with Learnable Structural and Positional Representations. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_15_1","first-page":"102","article-title":"Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching","volume":"6658","author":"Fankhauser Stefan","year":"2011","unstructured":"Stefan Fankhauser , Kaspar Riesen , and Horst Bunke . 2011 . Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching . In GbRPR , Vol. 6658. 102 -- 111 . Stefan Fankhauser, Kaspar Riesen, and Horst Bunke. 2011. Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching. In GbRPR, Vol. 6658. 102--111.","journal-title":"GbRPR"},{"key":"e_1_3_2_1_16_1","volume-title":"Deep Graph Matching Consensus. In International Conference on Learning Representations.","author":"Fey Matthias","unstructured":"Matthias Fey , Jan Eric Lenssen , Christopher Morris , Jonathan Masci , and Nils M. Kriege . 2020 . Deep Graph Matching Consensus. In International Conference on Learning Representations. Matthias Fey, Jan Eric Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege. 2020. Deep Graph Matching Consensus. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_2_1_18_1","volume-title":"Inves: Incremental Partitioning-Based Verification for Graph Similarity Search. In EDBT. 229--240.","author":"Kim Jongik","year":"2019","unstructured":"Jongik Kim , Dong-Hoon Choi , and Chen Li . 2019 . Inves: Incremental Partitioning-Based Verification for Graph Similarity Search. In EDBT. 229--240. Jongik Kim, Dong-Hoon Choi, and Chen Li. 2019. Inves: Incremental Partitioning-Based Verification for Graph Similarity Search. In EDBT. 229--240."},{"key":"e_1_3_2_1_19_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2016","unstructured":"Thomas N. Kipf and Max Welling . 2016 . Semi-Supervised Classification with Graph Convolutional Networks. CoRR , Vol. abs\/ 1609 .02907 (2016). Thomas N. Kipf and Max Welling. 2016. Semi-Supervised Classification with Graph Convolutional Networks. CoRR, Vol. abs\/1609.02907 (2016)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-014-9734-0"},{"key":"e_1_3_2_1_21_1","volume-title":"Big-align: Fast bipartite graph alignment. In ICDM. 389--398.","author":"Koutra Danai","year":"2013","unstructured":"Danai Koutra , Hanghang Tong , and David Lubensky . 2013 . Big-align: Fast bipartite graph alignment. In ICDM. 389--398. Danai Koutra, Hanghang Tong, and David Lubensky. 2013. Big-align: Fast bipartite graph alignment. In ICDM. 389--398."},{"key":"e_1_3_2_1_22_1","first-page":"4465","article-title":"Distance encoding: Design provably more powerful neural networks for graph representation learning","volume":"33","author":"Li Pan","year":"2020","unstructured":"Pan Li , Yanbang Wang , Hongwei Wang , and Jure Leskovec . 2020 . Distance encoding: Design provably more powerful neural networks for graph representation learning . NeurIPS , Vol. 33 (2020), 4465 -- 4478 . Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. 2020. Distance encoding: Design provably more powerful neural networks for graph representation learning. NeurIPS, Vol. 33 (2020), 4465--4478.","journal-title":"NeurIPS"},{"key":"e_1_3_2_1_23_1","volume-title":"ICML","volume":"97","author":"Li Yujia","year":"2019","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 , Vol. 97 . 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, Vol. 97. 3835--3845."},{"key":"e_1_3_2_1_24_1","volume-title":"GraphiT: Encoding Graph Structure in Transformers. CoRR","author":"Mialon Gr\u00e9","year":"2021","unstructured":"Gr\u00e9 goire Mialon , Dexiong Chen , Margot Selosse , and Julien Mairal . 2021. GraphiT: Encoding Graph Structure in Transformers. CoRR , Vol. abs\/ 2106 .05667 ( 2021 ). Gr\u00e9 goire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. 2021. GraphiT: Encoding Graph Structure in Transformers. CoRR, Vol. abs\/2106.05667 (2021)."},{"key":"e_1_3_2_1_25_1","volume-title":"Fast Suboptimal Algorithms for the Computation of Graph Edit Distance. In IAPR Workshops","volume":"4109","author":"Neuhaus Michel","year":"2006","unstructured":"Michel Neuhaus , Kaspar Riesen , and Horst Bunke . 2006 . Fast Suboptimal Algorithms for the Computation of Graph Edit Distance. In IAPR Workshops , Vol. 4109 . 163--172. Michel Neuhaus, Kaspar Riesen, and Horst Bunke. 2006. Fast Suboptimal Algorithms for the Computation of Graph Edit Distance. In IAPR Workshops, Vol. 4109. 163--172."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Yun Peng Byron Choi and Jianliang Xu. 2021. Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints. In IJCAI. 1534--1540. Yun Peng Byron Choi and Jianliang Xu. 2021. Graph Edit Distance Learning via Modeling Optimum Matchings with Constraints. In IJCAI. 1534--1540.","DOI":"10.24963\/ijcai.2021\/212"},{"key":"e_1_3_2_1_27_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 . NeurIPS , Vol. 35 (2022), 22518 -- 22530 . Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. 2022. Greed: A neural framework for learning graph distance functions. NeurIPS, Vol. 35 (2022), 22518--22530.","journal-title":"NeurIPS"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2008.04.004"},{"key":"e_1_3_2_1_29_1","first-page":"142","article-title":"A Novel Software Toolkit for Graph Edit Distance Computation","volume":"7877","author":"Riesen Kaspar","year":"2013","unstructured":"Kaspar Riesen , Sandro Emmenegger , and Horst Bunke . 2013 . A Novel Software Toolkit for Graph Edit Distance Computation . In GbRPR , Vol. 7877. 142 -- 151 . Kaspar Riesen, Sandro Emmenegger, and Horst Bunke. 2013. A Novel Software Toolkit for Graph Edit Distance Computation. In GbRPR, Vol. 7877. 142--151.","journal-title":"GbRPR"},{"key":"e_1_3_2_1_30_1","unstructured":"Kaspar Riesen Stefan Fankhauser and Horst Bunke. 2007. Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic. In MLG. 21--24. Kaspar Riesen Stefan Fankhauser and Horst Bunke. 2007. Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic. In MLG. 21--24."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Runzhong Wang Ziao Guo Shaofei Jiang Xiaokang Yang and Junchi Yan. 2023. Deep Learning of Partial Graph Matching via Differentiable Top-K. In CVPR. 6272--6281. Runzhong Wang Ziao Guo Shaofei Jiang Xiaokang Yang and Junchi Yan. 2023. Deep Learning of Partial Graph Matching via Differentiable Top-K. In CVPR. 6272--6281.","DOI":"10.1109\/CVPR52729.2023.00607"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Runzhong Wang Junchi Yan and Xiaokang Yang. 2019. Learning Combinatorial Embedding Networks for Deep Graph Matching. In ICCV. 3056--3065. Runzhong Wang Junchi Yan and Xiaokang Yang. 2019. Learning Combinatorial Embedding Networks for Deep Graph Matching. In ICCV. 3056--3065.","DOI":"10.1109\/ICCV.2019.00315"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Runzhong Wang Tianqi Zhang Tianshu Yu Junchi Yan and Xiaokang Yang. 2021. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR. 5241--5250. Runzhong Wang Tianqi Zhang Tianshu Yu Junchi Yan and Xiaokang Yang. 2021. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In CVPR. 5241--5250.","DOI":"10.1109\/CVPR46437.2021.00520"},{"key":"e_1_3_2_1_34_1","first-page":"20520","article-title":"Differentiable top-k with optimal transport","volume":"33","author":"Xie Yujia","year":"2020","unstructured":"Yujia Xie , Hanjun Dai , Minshuo Chen , Bo Dai , Tuo Zhao , Hongyuan Zha , Wei Wei , and Tomas Pfister . 2020 . Differentiable top-k with optimal transport . NeurIPS , Vol. 33 (2020), 20520 -- 20531 . Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. 2020. Differentiable top-k with optimal transport. NeurIPS, Vol. 33 (2020), 20520--20531.","journal-title":"NeurIPS"},{"key":"e_1_3_2_1_35_1","volume-title":"Hancock","author":"Yan Junchi","year":"2020","unstructured":"Junchi Yan , Shuang Yang , and Edwin R . Hancock . 2020 . Learning for Graph Matching and Related Combinatorial Optimization Problems. In IJCAI. 4988--4996. Junchi Yan, Shuang Yang, and Edwin R. Hancock. 2020. Learning for Graph Matching and Related Combinatorial Optimization Problems. In IJCAI. 4988--4996."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Pinar Yanardag and S. V. N. Vishwanathan. 2015. Deep Graph Kernels. In SIGKDD. 1365--1374. Pinar Yanardag and S. V. N. Vishwanathan. 2015. Deep Graph Kernels. In SIGKDD. 1365--1374.","DOI":"10.1145\/2783258.2783417"},{"key":"e_1_3_2_1_37_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_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Menglin Yang Min Zhou Lujia Pan and Irwin King. 2023. \u03baHGCN: Tree-likeness Modeling via Continuous and Discrete Curvature Learning. In SIGKDD. 2965--2977. Menglin Yang Min Zhou Lujia Pan and Irwin King. 2023. \u03baHGCN: Tree-likeness Modeling via Continuous and Discrete Curvature Learning. In SIGKDD. 2965--2977.","DOI":"10.1145\/3580305.3599532"},{"key":"e_1_3_2_1_39_1","first-page":"28877","article-title":"Do transformers really perform badly for graph representation","volume":"34","author":"Ying Chengxuan","year":"2021","unstructured":"Chengxuan Ying , Tianle Cai , Shengjie Luo , Shuxin Zheng , Guolin Ke , Di He , Yanming Shen , and Tie-Yan Liu . 2021 . Do transformers really perform badly for graph representation ? NeurIPS , Vol. 34 (2021), 28877 -- 28888 . Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. 2021. Do transformers really perform badly for graph representation? NeurIPS, Vol. 34 (2021), 28877--28888.","journal-title":"NeurIPS"},{"key":"e_1_3_2_1_40_1","volume-title":"International Conference on Learning Representations.","author":"Yu Tianshu","year":"2020","unstructured":"Tianshu Yu , Runzhong Wang , Junchi Yan , and Baoxin Li . 2020 . Learning deep graph matching with channel-independent embedding and Hungarian attention . In International Conference on Learning Representations. Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. 2020. Learning deep graph matching with channel-independent embedding and Hungarian attention. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Zhen Zhang Jiajun Bu Martin Ester Zhao Li Chengwei Yao Zhi Yu and Can Wang. 2021. H2MN: Graph Similarity Learning with Hierarchical Hypergraph Matching Networks. In SIGKDD. 2274--2284. Zhen Zhang Jiajun Bu Martin Ester Zhao Li Chengwei Yao Zhi Yu and Can Wang. 2021. H2MN: Graph Similarity Learning with Hierarchical Hypergraph Matching Networks. In SIGKDD. 2274--2284.","DOI":"10.1145\/3447548.3467328"},{"key":"e_1_3_2_1_42_1","first-page":"30181","article-title":"Efficient Graph Similarity Computation with Alignment Regularization","volume":"35","author":"Zhuo Wei","year":"2022","unstructured":"Wei Zhuo and Guang Tan . 2022 . Efficient Graph Similarity Computation with Alignment Regularization . NeurIPS , Vol. 35 , 30181 -- 30193 . Wei Zhuo and Guang Tan. 2022. Efficient Graph Similarity Computation with Alignment Regularization. NeurIPS, Vol. 35, 30181--30193.","journal-title":"NeurIPS"}],"event":{"name":"CIKM '23: The 32nd ACM International Conference on Information and Knowledge Management","location":"Birmingham United Kingdom","acronym":"CIKM '23","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGIR ACM Special Interest Group on Information Retrieval"]},"container-title":["Proceedings of the 32nd ACM International Conference on Information and Knowledge Management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583780.3614959","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583780.3614959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:44Z","timestamp":1750178204000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583780.3614959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,21]]},"references-count":42,"alternative-id":["10.1145\/3583780.3614959","10.1145\/3583780"],"URL":"https:\/\/doi.org\/10.1145\/3583780.3614959","relation":{},"subject":[],"published":{"date-parts":[[2023,10,21]]},"assertion":[{"value":"2023-10-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}