{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:42:07Z","timestamp":1757612527714,"version":"3.44.0"},"reference-count":88,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>\n            Graph Edit Distance (GED) is a widely recognized metric for measuring graph similarity, yet its NP-complete nature poses challenges for fast and accurate computation. This paper introduces FGWAlign, an Optimal Transport (OT)-based approach for graph alignment and GED computation. We take the first step to theoretically demonstrate and that computing GED can be transformed into optimizing a particular OT variant\u2014the Fused Gromov-Wasserstein distance. Tailored to the GED problem structure, we further implement three key enhancements to the standard FGW solver: (1) a random exploration scheme to better locate the global optimum, (2) a diverse projection strategy for post-processing the transportation plan to escape local optima, and (3) a novel extension to accommodate multi-relational graphs with edge labels. With\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (|\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            ||\n            <jats:italic toggle=\"yes\">E<\/jats:italic>\n            |) time complexity and\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (|\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            |\n            <jats:sup>2<\/jats:sup>\n            ) space complexity, where |\n            <jats:italic toggle=\"yes\">V<\/jats:italic>\n            | and |\n            <jats:italic toggle=\"yes\">E<\/jats:italic>\n            | are the maximum number of nodes and edges between the two compared graphs, FGWAlign achieves a superior balance of efficiency, accuracy, and scalability. Empirical results show that, compared with 12 representative GED computation methods across different categories on 4 real-world graph datasets, FGWAlign reduces computation errors by over 80% and achieves 15\u201360\u00d7 speedup. It also demonstrates promising resutls on downstream applications including labeled graph alignment and graph-level anomaly detection, highlighting its versatility. FGWAlign opens up promising avenues for future applications in graph data management.\n          <\/jats:p>","DOI":"10.14778\/3748191.3748221","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3641-3654","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond"],"prefix":"10.14778","volume":"18","author":[{"given":"Jianheng","family":"Tang","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Xi","family":"Zhao","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Lemin","family":"Kong","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Jia","family":"Li","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology (Guangzhou)"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"4th International Conference on Pattern Recognition Applications and Methods","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 4th International Conference on Pattern Recognition Applications and Methods 2015."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1109\/34.211474","article-title":"A linear programming approach for the weighted graph matching problem","volume":"15","author":"Almohamad HA","year":"1993","unstructured":"HA Almohamad and Salih O Duffuaa. 1993. A linear programming approach for the weighted graph matching problem. IEEE Transactions on pattern analysis and machine intelligence 15, 5 (1993), 522\u2013525.","journal-title":"IEEE Transactions on pattern analysis and machine intelligence"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the VLDB Endowment 15","author":"Bai Jiyang","year":"2022","unstructured":"Jiyang Bai and Peixiang Zhao. 2022. TaGSim: type-aware graph similarity learning and computation. Proceedings of the VLDB Endowment 15, 2 (2022)."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the twelfth ACM international conference on web search and data mining. 384\u2013392","author":"Bai Yunsheng","year":"2019","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 Proceedings of the twelfth ACM international conference on web search and data mining. 384\u2013392."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s00778-019-00544-1","article-title":"Comparing heuristics for graph edit distance computation","volume":"29","author":"Blumenthal David B","year":"2020","unstructured":"David B Blumenthal, Nicolas Boria, Johann Gamper, S\u00e9bastien Bougleux, and Luc Brun. 2020. Comparing heuristics for graph edit distance computation. The VLDB journal 29, 1 (2020), 419\u2013458.","journal-title":"The VLDB journal"},{"key":"e_1_2_1_6_1","volume-title":"International Workshop on Graph-Based Representations in Pattern Recognition. Springer, 211\u2013221","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 International Workshop on Graph-Based Representations in Pattern Recognition. Springer, 211\u2013221."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 2011 SIGGRAPH Asia conference. 1\u201312","author":"Bonneel Nicolas","year":"2011","unstructured":"Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. 2011. Displacement interpolation using Lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asia conference. 1\u201312."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.patrec.2016.10.001","article-title":"Graph edit distance as a quadratic assignment problem","volume":"87","author":"Bougleux Sebastien","year":"2017","unstructured":"Sebastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Ga\u00fcz\u00e8re, and Mario Vento. 2017. Graph edit distance as a quadratic assignment problem. Pattern Recognition Letters 87 (2017), 38\u201346.","journal-title":"Pattern Recognition Letters"},{"key":"e_1_2_1_9_1","volume-title":"A graph distance metric based on the maximal common subgraph. Pattern recognition letters 19, 3\u20134","author":"Bunke Horst","year":"1998","unstructured":"Horst Bunke and Kim Shearer. 1998. A graph distance metric based on the maximal common subgraph. Pattern recognition letters 19, 3\u20134 (1998), 255\u2013259."},{"key":"e_1_2_1_10_1","volume-title":"SCCC 2001. 21st International Conference of the Chilean Computer Science Society. 33\u201340","author":"Bustos B.","year":"2001","unstructured":"B. Bustos, G. Navarro, and E. Chavez. 2001. Pivot selection techniques for proximity searching in metric spaces. In SCCC 2001. 21st International Conference of the Chilean Computer Science Society. 33\u201340. 10.1109\/SCCC.2001.972629"},{"key":"e_1_2_1_11_1","volume-title":"2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 793\u2013804","author":"Chang Lijun","year":"2020","unstructured":"Lijun Chang, Xing Feng, Xuemin Lin, Lu Qin, Wenjie Zhang, and Dian Ouyang. 2020. Speeding up GED verification for graph similarity search. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 793\u2013804."},{"key":"e_1_2_1_12_1","volume-title":"International Conference on Machine Learning. PMLR, 1542\u20131553","author":"Chen Liqun","year":"2020","unstructured":"Liqun Chen, Zhe Gan, Yu Cheng, Linjie Li, Lawrence Carin, and Jingjing Liu. 2020. Graph optimal transport for cross-domain alignment. In International Conference on Machine Learning. PMLR, 1542\u20131553."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3709673","article-title":"Computing Approximate Graph Edit Distance via Optimal Transport","volume":"3","author":"Cheng Qihao","year":"2025","unstructured":"Qihao Cheng, Da Yan, Tianhao Wu, Zhongyi Huang, and Qin Zhang. 2025. Computing Approximate Graph Edit Distance via Optimal Transport. Proceedings of the ACM on Management of Data 3, 1 (2025), 1\u201326.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_14_1","volume-title":"European conference on Computer vision. Springer, 492\u2013505","author":"Cho Minsu","year":"2010","unstructured":"Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. 2010. Reweighted random walks for graph matching. In European conference on Computer vision. Springer, 492\u2013505."},{"key":"e_1_2_1_15_1","volume-title":"Weinberger (Eds.)","volume":"26","author":"Cuturi Marco","year":"2013","unstructured":"Marco Cuturi. 2013. Sinkhorn Distances: Lightspeed Computation of Optimal Transport. In Advances in Neural Information Processing Systems, C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (Eds.), Vol. 26. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2013\/file\/af21d0c97db2e27e13572cbf59eb343d-Paper.pdf"},{"key":"e_1_2_1_16_1","volume-title":"2022 IEEE International Conference on Data Mining (ICDM). IEEE, 915\u2013920","author":"Ding Qijie","year":"2022","unstructured":"Qijie Ding, Daokun Zhang, and Jie Yin. 2022. Conflict-aware pseudo labeling via optimal transport for entity alignment. In 2022 IEEE International Conference on Data Mining (ICDM). IEEE, 915\u2013920."},{"key":"e_1_2_1_17_1","volume-title":"Graph-Based Representations in Pattern Recognition: 8th IAPR-TC-15 International Workshop, GbRPR 2011, M\u00fcnster, Germany, May 18\u201320, 2011. Proceedings 8. Springer, 102\u2013111","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 Graph-Based Representations in Pattern Recognition: 8th IAPR-TC-15 International Workshop, GbRPR 2011, M\u00fcnster, Germany, May 18\u201320, 2011. Proceedings 8. Springer, 102\u2013111."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.patcog.2014.07.015","article-title":"Approximation of graph edit distance based on Hausdorff matching","volume":"48","author":"Fischer Andreas","year":"2015","unstructured":"Andreas Fischer, Ching Y Suen, Volkmar Frinken, Kaspar Riesen, and Horst Bunke. 2015. Approximation of graph edit distance based on Hausdorff matching. Pattern Recognition 48, 2 (2015), 331\u2013343.","journal-title":"Pattern Recognition"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Pot: Python optimal transport","volume":"22","author":"Flamary R\u00e9mi","year":"2021","unstructured":"R\u00e9mi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aur\u00e9lie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al. 2021. Pot: Python optimal transport. Journal of Machine Learning Research 22, 78 (2021), 1\u20138.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 426\u2013435","author":"Gao Ji","year":"2021","unstructured":"Ji Gao, Xiao Huang, and Jundong Li. 2021. Unsupervised graph alignment with wasserstein distance discriminator. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 426\u2013435."},{"key":"e_1_2_1_21_1","volume-title":"A survey of graph edit distance. Pattern Analysis and applications 13","author":"Gao Xinbo","year":"2010","unstructured":"Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. 2010. A survey of graph edit distance. Pattern Analysis and applications 13 (2010), 113\u2013129."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"1410","DOI":"10.1021\/acs.jcim.8b00820","article-title":"Ligand-based virtual screening using graph edit distance as molecular similarity measure","volume":"59","author":"Garcia-Hernandez Carlos","year":"2019","unstructured":"Carlos Garcia-Hernandez, Alberto Fernandez, and Francesc Serratosa. 2019. Ligand-based virtual screening using graph edit distance as molecular similarity measure. Journal of chemical information and modeling 59, 4 (2019), 1410\u20131421.","journal-title":"Journal of chemical information and modeling"},{"key":"e_1_2_1_23_1","volume-title":"International Conference on Machine Learning. PMLR, 5616\u20135627","author":"Gasteiger Johannes","year":"2021","unstructured":"Johannes Gasteiger, Marten Lienen, and Stephan G\u00fcnnemann. 2021. Scalable optimal transport in high dimensions for graph distances, embedding alignment, and more. In International Conference on Machine Learning. PMLR, 5616\u20135627."},{"key":"e_1_2_1_24_1","volume-title":"2016 IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 265\u2013276","author":"Gouda Karam","year":"2016","unstructured":"Karam Gouda and Mosab Hassaan. 2016. CSI_GED: An efficient approach for graph edit similarity computation. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 265\u2013276."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 27th ACM international conference on information and knowledge management. 117\u2013126","author":"Heimann Mark","year":"2018","unstructured":"Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. 2018. Regal: Representation learning-based graph alignment. In Proceedings of the 27th ACM international conference on information and knowledge management. 117\u2013126."},{"key":"e_1_2_1_26_1","first-page":"1881","article-title":"Network alignment with holistic embeddings","volume":"35","author":"Huynh Thanh Trung","year":"2021","unstructured":"Thanh Trung Huynh, Chi Thang Duong, Thanh Tam Nguyen, Vinh Tong Van, Abdul Sattar, Hongzhi Yin, and Quoc Viet Hung Nguyen. 2021. Network alignment with holistic embeddings. IEEE Transactions on Knowledge and Data Engineering 35, 2 (2021), 1881\u20131894.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_27_1","volume-title":"German conference on bioinformatics","author":"Ibragimov Rashid","year":"2013","unstructured":"Rashid Ibragimov, Maximilian Malek, Jiong Guo, and Jan Baumbach. 2013. Gedevo: an evolutionary graph edit distance algorithm for biological network alignment. In German conference on bioinformatics 2013. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_28_1","volume-title":"DGOR\/NSOR: Papers of the 16th Annual Meeting of DGOR in Cooperation with NSOR\/Vortr\u00e4ge der 16","author":"Jonker Roy","year":"1988","unstructured":"Roy Jonker and Ton Volgenant. 1988. A shortest augmenting path algorithm for dense and sparse linear assignment problems. In DGOR\/NSOR: Papers of the 16th Annual Meeting of DGOR in Cooperation with NSOR\/Vortr\u00e4ge der 16. Jahrestagung der DGOR zusammen mit der NSOR. Springer, 622\u2013622."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"1200","DOI":"10.1109\/TPAMI.2006.152","article-title":"A binary linear programming formulation of the graph edit distance","volume":"28","author":"Justice Derek","year":"2006","unstructured":"Derek Justice and Alfred Hero. 2006. A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence 28, 8 (2006), 1200\u20131214.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Sunghwan Kim Jie Chen Tiejun Cheng Asta Gindulyte Jia He Siqian He Qingliang Li Benjamin A Shoemaker Paul A Thiessen Bo Yu et al. 2023. Pub-Chem 2023 update. Nucleic acids research 51 D1 (2023) D1373\u2013D1380.","DOI":"10.1093\/nar\/gkac956"},{"key":"e_1_2_1_31_1","volume-title":"2019 IEEE International Conference on Data Mining (ICDM). IEEE, 349\u2013358","author":"Kriege Nils M","year":"2019","unstructured":"Nils M Kriege, Pierre-Louis Giscard, Franka Bause, and Richard C Wilson. 2019. Computing optimal assignments in linear time for approximate graph matching. In 2019 IEEE International Conference on Data Mining (ICDM). IEEE, 349\u2013358."},{"key":"e_1_2_1_32_1","volume-title":"International Conference on Computer Vision. IEEE, 1482\u20131489","author":"Leordeanu Marius","year":"2005","unstructured":"Marius Leordeanu and Martial Hebert. 2005. A spectral technique for correspondence problems using pairwise constraints. In International Conference on Computer Vision. IEEE, 1482\u20131489."},{"key":"e_1_2_1_33_1","volume-title":"An integer projected fixed point method for graph matching and map inference. Advances in neural information processing systems 22","author":"Leordeanu Marius","year":"2009","unstructured":"Marius Leordeanu, Martial Hebert, and Rahul Sukthankar. 2009. An integer projected fixed point method for graph matching and map inference. Advances in neural information processing systems 22 (2009)."},{"key":"e_1_2_1_34_1","volume-title":"Anthony Man-Cho So, and Jose Blanchet","author":"Li Jiajin","year":"2022","unstructured":"Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, and Jose Blanchet. 2022. Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data. arXiv:2205.08115 [cs.LG] https:\/\/arxiv.org\/abs\/2205.08115"},{"key":"e_1_2_1_35_1","volume-title":"The Eleventh International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=0jxPyVWmiiF","author":"Li Jiajin","year":"2023","unstructured":"Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, and Jose Blanchet. 2023. A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data. In The Eleventh International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=0jxPyVWmiiF"},{"key":"e_1_2_1_36_1","volume-title":"International Symposium on Algorithms and Computation. Springer, 74\u201382","author":"Lin Chih-Long","year":"1994","unstructured":"Chih-Long Lin. 1994. Hardness of approximating graph transformation problem. In International Symposium on Algorithms and Computation. Springer, 74\u201382."},{"key":"e_1_2_1_37_1","volume-title":"Kai Ming Ting, and Zhi-Hua Zhou","author":"Liu Fei Tony","year":"2008","unstructured":"Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. 2008. Isolation forest. In 2008 eighth ieee international conference on data mining. IEEE, 413\u2013422."},{"key":"e_1_2_1_38_1","unstructured":"Junbin Liu Ya Liu Wing-Kin Ma Mingjie Shao and Anthony Man-Cho So. 2024. Extreme Point Pursuit - Part I: A Framework for Constant Modulus Optimization. arXiv:2403.06506 [eess.SP]"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 1503\u20131512","author":"Liu Junfeng","year":"2023","unstructured":"Junfeng Liu, Min Zhou, Shuai Ma, and Lujia Pan. 2023. MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 1503\u20131512."},{"key":"e_1_2_1_40_1","first-page":"10","volume-title":"Proc. ACM Manag. Data 2, 4, Article 199 (Sept.","author":"Liu Wei","year":"2024","unstructured":"Wei Liu, Wei Zhang, Haiyan Zhao, and Zhi Jin. 2024. GABoost: Graph Alignment Boosting via Local Optimum Escape. Proc. ACM Manag. Data 2, 4, Article 199 (Sept. 2024), 26 pages. 10.1145\/3677135"},{"key":"e_1_2_1_41_1","volume-title":"Leo Yu Zhang, and Shirui Pan","author":"Liu Yixin","year":"2023","unstructured":"Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. 2023. Towards self-interpretable graph-level anomaly detection. In Advances in Neural Information Processing Systems, Vol. 36."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.223"},{"key":"e_1_2_1_43_1","volume-title":"An Accurate Unsupervised Method for Joint Entity Alignment and Dangling Entity Detection. In Findings of the Association for Computational Linguistics: ACL 2022","author":"Luo Shengxuan","year":"2022","unstructured":"Shengxuan Luo and Sheng Yu. 2022. An Accurate Unsupervised Method for Joint Entity Alignment and Dangling Entity Detection. In Findings of the Association for Computational Linguistics: ACL 2022, Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (Eds.). Association for Computational Linguistics, Dublin, Ireland, 2330\u20132339. 10.18653\/v1\/2022.findings-acl.183"},{"volume-title":"Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 704\u2013714","author":"Ma Rongrong","key":"e_1_2_1_44_1","unstructured":"Rongrong Ma, Guansong Pang, Ling Chen, and Anton van den Hengel. 2022. Deep graph-level anomaly detection by glocal knowledge distillation. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 704\u2013714."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1016\/j.patrec.2019.06.024","article-title":"Combining graph edit distance and triplet networks for offline signature verification","volume":"125","author":"Maergner Paul","year":"2019","unstructured":"Paul Maergner, Vinaychandran Pondenkandath, Michele Alberti, Marcus Liwicki, Kaspar Riesen, Rolf Ingold, and Andreas Fischer. 2019. Combining graph edit distance and triplet networks for offline signature verification. Pattern Recognition Letters 125 (2019), 527\u2013533.","journal-title":"Pattern Recognition Letters"},{"key":"e_1_2_1_46_1","first-page":"139","article-title":"One-class SVMs for document classification","author":"Manevitz Larry M","year":"2001","unstructured":"Larry M Manevitz and Malik Yousef. 2001. One-class SVMs for document classification. Journal of machine Learning research 2, Dec (2001), 139\u2013154.","journal-title":"Journal of machine Learning research 2"},{"key":"e_1_2_1_47_1","volume-title":"2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops. IEEE, 256\u2013263","author":"M\u00e9moli Facundo","year":"2009","unstructured":"Facundo M\u00e9moli. 2009. Spectral Gromov-Wasserstein distances for shape matching. In 2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops. IEEE, 256\u2013263."},{"key":"e_1_2_1_48_1","volume-title":"ICML Workshop.","author":"Morris Christopher","year":"2020","unstructured":"Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. 2020. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML Workshop."},{"key":"e_1_2_1_49_1","volume-title":"SSPR 2006 and SPR 2006, Hong Kong, China, August 17\u201319, 2006. Proceedings. Springer, 163\u2013172","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 Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshops, SSPR 2006 and SPR 2006, Hong Kong, China, August 17\u201319, 2006. Proceedings. Springer, 163\u2013172."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s10994-015-5517-9","article-title":"Propagation kernels: efficient graph kernels from propagated information","volume":"102","author":"Neumann Marion","year":"2016","unstructured":"Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. 2016. Propagation kernels: efficient graph kernels from propagated information. Machine Learning 102 (2016), 209\u2013245.","journal-title":"Machine Learning"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the AAAI conference on Artificial Intelligence","volume":"31","author":"Nikolentzos Giannis","year":"2017","unstructured":"Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2017. Matching node embeddings for graph similarity. In Proceedings of the AAAI conference on Artificial Intelligence, Vol. 31."},{"key":"e_1_2_1_52_1","unstructured":"Shichao Pei Lu Yu and Xiangliang Zhang. 2019. Improving cross-lingual entity alignment via optimal transport. In IJCAI."},{"key":"e_1_2_1_53_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\u20131540.","DOI":"10.24963\/ijcai.2021\/212"},{"key":"e_1_2_1_54_1","volume-title":"International Conference on Machine Learning. PMLR, 2664\u20132672","author":"Peyr\u00e9 Gabriel","year":"2016","unstructured":"Gabriel Peyr\u00e9, Marco Cuturi, and Justin Solomon. 2016. Gromov-Wasserstein averaging of kernel and distance matrices. In International Conference on Machine Learning. PMLR, 2664\u20132672."},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","first-page":"1817","DOI":"10.14778\/3594512.3594514","article-title":"Computing Graph Edit Distance via Neural Graph Matching","volume":"16","author":"Piao Chengzhi","year":"2023","unstructured":"Chengzhi Piao, Tingyang Xu, Xiangguo Sun, Yu Rong, Kangfei Zhao, and Hong Cheng. 2023. Computing Graph Edit Distance via Neural Graph Matching. Proceedings of the VLDB Endowment 16, 8 (2023), 1817\u20131829.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2062\u20132072","author":"Qin Zongyue","year":"2020","unstructured":"Zongyue Qin, Yunsheng Bai, and Yizhou Sun. 2020. GHashing: Semantic graph hashing for approximate similarity search in graph databases. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2062\u20132072."},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22","author":"Qiu Chen","year":"2022","unstructured":"Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph. 2022. Raising the Bar in Graph-level Anomaly Detection. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22. 2196\u20132203."},{"key":"e_1_2_1_58_1","volume-title":"Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing 27, 7","author":"Riesen Kaspar","year":"2009","unstructured":"Kaspar Riesen and Horst Bunke. 2009. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision computing 27, 7 (2009), 950\u2013959."},{"key":"e_1_2_1_59_1","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. 21\u201324."},{"key":"e_1_2_1_60_1","volume-title":"Graph-Based Representations in Pattern Recognition: 6th IAPR-TC-15 International Workshop, GbRPR 2007, Alicante, Spain, June 11\u201313, 2007. Proceedings 6. Springer, 1\u201312","author":"Riesen Kaspar","year":"2007","unstructured":"Kaspar Riesen, Michel Neuhaus, and Horst Bunke. 2007. Bipartite graph matching for computing the edit distance of graphs. In Graph-Based Representations in Pattern Recognition: 6th IAPR-TC-15 International Workshop, GbRPR 2007, Alicante, Spain, June 11\u201313, 2007. Proceedings 6. Springer, 1\u201312."},{"key":"e_1_2_1_61_1","volume-title":"A distance measure between attributed relational graphs for pattern recognition","author":"Sanfeliu Alberto","year":"1983","unstructured":"Alberto Sanfeliu and King-Sun Fu. 1983. A distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics 3 (1983), 353\u2013362."},{"key":"e_1_2_1_62_1","article-title":"Weisfeiler-lehman graph kernels","volume":"12","author":"Shervashidze Nino","year":"2011","unstructured":"Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. 2011. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12, 9 (2011).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2897824.2925903","article-title":"Entropic metric alignment for correspondence problems","volume":"35","author":"Solomon Justin","year":"2016","unstructured":"Justin Solomon, Gabriel Peyr\u00e9, Vladimir G Kim, and Suvrit Sra. 2016. Entropic metric alignment for correspondence problems. ACM Transactions on Graphics (ToG) 35, 4 (2016), 1\u201313.","journal-title":"ACM Transactions on Graphics (ToG)"},{"key":"e_1_2_1_64_1","volume-title":"2023 IEEE 39th International Conference on Data Engineering (ICDE). 1638\u20131651","author":"Tang Jianheng","year":"2023","unstructured":"Jianheng Tang, Weiqi Zhang, Jiajin Li, Kangfei Zhao, Fugee Tsung, and Jia Li. 2023. Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). 1638\u20131651. 10.1109\/ICDE55515.2023.00129"},{"key":"e_1_2_1_65_1","volume-title":"Findings of the Association for Computational Linguistics: ACL 2023","author":"Tang Jianheng","year":"1865","unstructured":"Jianheng Tang, Kangfei Zhao, and Jia Li. [n.d.]. A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignment. In Findings of the Association for Computational Linguistics: ACL 2023. 3320\u20133334. 10.18653\/v1\/2023.findings-acl.205"},{"key":"e_1_2_1_66_1","volume-title":"International Conference on Machine Learning. PMLR, 6275\u20136284","author":"Titouan Vayer","year":"2019","unstructured":"Vayer Titouan, Nicolas Courty, Romain Tavenard, and R\u00e9mi Flamary. 2019. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning. PMLR, 6275\u20136284."},{"key":"e_1_2_1_67_1","volume-title":"Johannes S\u00f6ding, and Martin Steinegger.","author":"Kempen Michel Van","year":"2023","unstructured":"Michel Van Kempen, Stephanie S Kim, Charlotte Tumescheit, Milot Mirdita, Jeongjae Lee, Cameron LM Gilchrist, Johannes S\u00f6ding, and Martin Steinegger. 2023. Fast and accurate protein structure search with Foldseek. Nature Biotechnology (2023), 1\u20134."},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Mihaly Varadi Stephen Anyango Mandar Deshpande Sreenath Nair Cindy Natassia Galabina Yordanova David Yuan Oana Stroe Gemma Wood Agata Laydon et al. 2022. AlphaFold Protein Structure Database: massively expanding the structural coverage of protein-sequence space with high-accuracy models. Nucleic acids research 50 D1 (2022) D439\u2013D444.","DOI":"10.1093\/nar\/gkab1061"},{"key":"e_1_2_1_69_1","first-page":"1201","article-title":"Graph kernels","volume":"11","author":"Vishwanathan S Vichy N","year":"2010","unstructured":"S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. 2010. Graph kernels. The Journal of Machine Learning Research 11 (2010), 1201\u20131242.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_2_1_70_1","volume-title":"GTCAlign: Global Topology Consistency-based Graph Alignment","author":"Wang Chenxu","year":"2023","unstructured":"Chenxu Wang, Peijing Jiang, Xiangliang Zhang, Pinghui Wang, Tao Qin, and Xiaohong Guan. 2023. GTCAlign: Global Topology Consistency-based Graph Alignment. IEEE Transactions on Knowledge and Data Engineering (2023)."},{"key":"e_1_2_1_71_1","first-page":"1","article-title":"Pygmtools: A Python Graph Matching Toolkit","volume":"25","author":"Wang Runzhong","year":"2024","unstructured":"Runzhong Wang, Ziao Guo, Wenzheng Pan, Jiale Ma, Yikai Zhang, Nan Yang, Qi Liu, Longxuan Wei, Hanxue Zhang, Chang Liu, Zetian Jiang, Xiaokang Yang, and Junchi Yan. 2024. Pygmtools: A Python Graph Matching Toolkit. Journal of Machine Learning Research 25, 33 (2024), 1\u20137. https:\/\/jmlr.org\/papers\/v25\/23-0572.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_72_1","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition. 5241\u20135250","author":"Wang Runzhong","year":"2021","unstructured":"Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang. 2021. Combinatorial learning of graph edit distance via dynamic embedding. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition. 5241\u20135250."},{"key":"e_1_2_1_73_1","volume-title":"2012 IEEE 28th International Conference on Data Engineering. IEEE, 210\u2013221","author":"Wang Xiaoli","year":"2012","unstructured":"Xiaoli Wang, Xiaofeng Ding, Anthony KH Tung, Shanshan Ying, and Hai Jin. 2012. An efficient graph indexing method. In 2012 IEEE 28th International Conference on Data Engineering. IEEE, 210\u2013221."},{"key":"e_1_2_1_74_1","doi-asserted-by":"crossref","first-page":"2833","DOI":"10.1016\/j.patcog.2008.03.011","article-title":"A study of graph spectra for comparing graphs and trees","volume":"41","author":"Wilson Richard C","year":"2008","unstructured":"Richard C Wilson and Ping Zhu. 2008. A study of graph spectra for comparing graphs and trees. Pattern Recognition 41, 9 (2008), 2833\u20132841.","journal-title":"Pattern Recognition"},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 2240\u20132249","author":"Xin Kexuan","year":"2022","unstructured":"Kexuan Xin, Zequn Sun, Wen Hua, Wei Hu, Jianfeng Qu, and Xiaofang Zhou. 2022. Large-scale Entity Alignment via Knowledge Graph Merging, Partitioning and Embedding. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 2240\u20132249."},{"key":"e_1_2_1_76_1","volume-title":"International conference on machine learning. PMLR, 6932\u20136941","author":"Xu Hongteng","year":"2019","unstructured":"Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. 2019. Gromov-wasserstein learning for graph matching and node embedding. In International conference on machine learning. PMLR, 6932\u20136941."},{"key":"e_1_2_1_77_1","volume-title":"Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 1365\u20131374","author":"Yanardag Pinar","year":"2015","unstructured":"Pinar Yanardag and SVN Vishwanathan. 2015. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 1365\u20131374."},{"key":"e_1_2_1_78_1","volume-title":"Noah: Neural-optimized A Search Algorithm for Graph Edit Distance Computation. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 576\u2013587","author":"Yang Lei","year":"2021","unstructured":"Lei Yang and Lei Zou. 2021. Noah: Neural-optimized A Search Algorithm for Graph Edit Distance Computation. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 576\u2013587."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311908"},{"key":"e_1_2_1_80_1","volume-title":"A normalized Levenshtein distance metric","author":"Yujian Li","year":"2007","unstructured":"Li Yujian and Liu Bo. 2007. A normalized Levenshtein distance metric. IEEE transactions on pattern analysis and machine intelligence 29, 6 (2007), 1091\u20131095."},{"key":"e_1_2_1_81_1","volume-title":"On entity alignment at scale. The VLDB Journal","author":"Zeng Weixin","year":"2022","unstructured":"Weixin Zeng, Xiang Zhao, Xinyi Li, Jiuyang Tang, and Wei Wang. 2022. On entity alignment at scale. The VLDB Journal (2022), 1\u201325."},{"key":"e_1_2_1_82_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.14778\/1687627.1687631","article-title":"Comparing stars: On approximating graph edit distance","volume":"2","author":"Zeng Zhiping","year":"2009","unstructured":"Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. 2009. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment 2, 1 (2009), 25\u201336.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_83_1","volume-title":"Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 1345\u20131354","author":"Zhang Si","year":"2016","unstructured":"Si Zhang and Hanghang Tong. 2016. Final: Fast attributed network alignment. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 1345\u20131354."},{"key":"e_1_2_1_84_1","volume-title":"On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data","author":"Zhao Lingxiao","year":"2021","unstructured":"Lingxiao Zhao and Leman Akoglu. 2021. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data (2021)."},{"key":"e_1_2_1_85_1","doi-asserted-by":"crossref","first-page":"169","DOI":"10.14778\/2732232.2732236","article-title":"A partition-based approach to structure similarity search","volume":"7","author":"Zhao Xiang","year":"2013","unstructured":"Xiang Zhao, Chuan Xiao, Xuemin Lin, Qing Liu, and Wenjie Zhang. 2013. A partition-based approach to structure similarity search. Proceedings of the VLDB Endowment 7, 3 (2013), 169\u2013180.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_86_1","volume-title":"2012 IEEE 28th international conference on data engineering. IEEE, 834\u2013845","author":"Zhao Xiang","year":"2012","unstructured":"Xiang Zhao, Chuan Xiao, Xuemin Lin, and Wei Wang. 2012. Efficient graph similarity joins with edit distance constraints. In 2012 IEEE 28th international conference on data engineering. IEEE, 834\u2013845."},{"key":"e_1_2_1_87_1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s00778-017-0487-0","article-title":"Efficient structure similarity searches: a partition-based approach","volume":"27","author":"Zhao Xiang","year":"2018","unstructured":"Xiang Zhao, Chuan Xiao, Xuemin Lin, Wenjie Zhang, and Yang Wang. 2018. Efficient structure similarity searches: a partition-based approach. The VLDB Journal 27, 1 (2018), 53\u201378.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_88_1","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1109\/TKDE.2014.2349924","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. IEEE Transactions on Knowledge and Data Engineering 27, 4 (2014), 964\u2013978.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:55:20Z","timestamp":1756994120000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":88,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748221"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748221","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}