{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:00Z","timestamp":1779174840118,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Given two input graphs, finding the largest subgraph that occurs in both, i.e., finding the maximum common subgraph, is a fundamental operator for evaluating the similarity between two graphs in graph data analysis. Existing works for solving the problem are of either theoretical or practical interest, but not both. Specifically, the algorithms with a theoretical guarantee on the running time are known to be not practically efficient; algorithms following the recently proposed backtracking framework called McSplit, run fast in practice but do not have any theoretical guarantees. In this paper, we propose a new backtracking algorithm called RRSplit, which at once achieves better practical efficiency and provides a non-trivial theoretical guarantee on the worst-case running time. To achieve the former, we develop a series of reductions and upper bounds for reducing redundant computations, i.e., the time for exploring some unpromising branches of exploration that hold no maximum common subgraph. To achieve the latter, we formally prove that RRSplit incurs a worst-case time complexity which matches the best-known complexity for the problem. Finally, we conduct extensive experiments on four benchmark graph collections, and the results demonstrate that our algorithm outperforms the practical state-of-the-art by several orders of magnitude.<\/jats:p>","DOI":"10.1145\/3725404","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:22:29Z","timestamp":1750281749000},"page":"1-27","source":"Crossref","is-referenced-by-count":1,"title":["Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1153-2902","authenticated-orcid":false,"given":"Kaiqiang","family":"Yu","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6650-2850","authenticated-orcid":false,"given":"Kaixin","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing University of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9775-4241","authenticated-orcid":false,"given":"Laks","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia, Vancouver, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9480-9809","authenticated-orcid":false,"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.11.007"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13321-020-00462-3"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589312"},{"key":"e_1_2_2_4_1","volume-title":"International Conference on Machine Learning. PMLR, 588--598","author":"Bai Yunsheng","year":"2021","unstructured":"Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. 2021. Glsearch: Maximum common subgraph detection via learning to search. In International Conference on Machine Learning. PMLR, 588--598."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_2_8_1","volume-title":"A subgraph isomorphism algorithm and its application to biochemical data. BMC bioinformatics","author":"Bonnici Vincenzo","year":"2013","unstructured":"Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC bioinformatics, Vol. 14 (2013), 1--13."},{"key":"e_1_2_2_9_1","volume-title":"On a relation between graph edit distance and maximum common subgraph. Pattern recognition letters","author":"Bunke H.","year":"1997","unstructured":"H. Bunke. 1997. On a relation between graph edit distance and maximum common subgraph. Pattern recognition letters, Vol. 18, 8 (1997), 689--694."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00074"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2018.10.002"},{"key":"e_1_2_2_12_1","volume-title":"Coverage and error models of protein-protein interaction data by directed graph analysis. Genome biology","author":"Chiang Tony","year":"2007","unstructured":"Tony Chiang, Denise Scholtens, Deepayan Sarkar, Robert Gentleman, and Wolfgang Huber. 2007. Coverage and error models of protein-protein interaction data by directed graph analysis. Genome biology, Vol. 8 (2007), 1--14."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330216"},{"key":"e_1_2_2_14_1","volume-title":"Carlo Sansone, and Mario Vento","author":"Cordella Luigi P","year":"2004","unstructured":"Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence, Vol. 26, 10 (2004), 1367--1372."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/wcms.5"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498246"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings, Part VI 14","author":"Hati Avik","year":"2016","unstructured":"Avik Hati, Subhasis Chaudhuri, and Rajbabu Velmurugan. 2016. Image co-segmentation using maximum common subgraph matching and region co-growing. In Computer Vision--ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11--14, 2016, Proceedings, Part VI 14. Springer, 736--752."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.11137"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588692"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55210-3_198"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457265"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00749-x"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2023.03.002"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.588"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1515\/jib-2017-0014"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575586"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273574"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i03.5619"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i4.25519"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44953-1_23"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/99"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380120103"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData47090.2019.9006538"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-015-0874-z"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966913.1966986"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594514"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2010.29"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.jcim.0c00741"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2014.05.019"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2980257"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589326"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2021.102558"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_73"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87477-5_39"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2009.01.004"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2023.3236028"},{"key":"e_1_2_2_53_1","unstructured":"Kaiqiang Yu Kaixin Wang Cheng Long Laks Lakshmanan and Reynold Cheng. 2025. Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach (Technical report). https:\/\/arxiv.org\/pdf\/2502.11557."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00284"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2022\/265"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:59:51Z","timestamp":1774983591000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725404"],"URL":"https:\/\/doi.org\/10.1145\/3725404","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}