{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T05:12:29Z","timestamp":1775538749040,"version":"3.50.1"},"reference-count":114,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2326141;2417750;2411294"],"award-info":[{"award-number":["2326141;2417750;2411294"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    Subgraph matching is a fundamental problem in graph analysis with a wide range of real-world applications. As subgraph matching techniques evolve, the existing mainstream\n                    <jats:italic toggle=\"yes\">filter-order-enumeration<\/jats:italic>\n                    framework falls short in two aspects: (i) this\n                    <jats:italic toggle=\"yes\">filter-order-enumeration<\/jats:italic>\n                    perspective overlooks an emerging line of compiler-based approaches with caching and validation-based orderings. (ii) The recent rise of complex pruning techniques has shifted the focus of core optimizations beyond filtering and enumeration. This paper advocates the need for a comprehensive survey that not only thoroughly discusses the compiler-based approaches (i.e., cache-based methods and their ordering techniques), but also reframes algorithm-level optimizations such that the role of pruning is adequately addressed.\n                  <\/jats:p>\n                  <jats:p>This survey revisits 17 representative exploration-based subgraph matching methods-including both algorithm-level techniques and compiler-based ones-and establishes two optimization pillars, i.e., redundancy reduction and order generation, that can inherently summarize all these efforts. This newly established perspective permits us to systematically organize various optimization techniques and analyze how they interact with each other in the same implementation framework. Our contributions are: (i) Cache-, filter-, and prune-based strategies can remove both overlapping and different redundancies, sending our performance up to 1.81\u00d7 faster than existing state-of-the-art (SOTA) settings, and (ii) heuristic and validation-based orderings, though grounded in fundamentally different design principles, often converge to similar behavior, leading to comparable performance in practice. Finally, (iii) we provide empirical guidance on when and how different strategies are most effective across diverse graph scenarios.<\/jats:p>","DOI":"10.1145\/3771791","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-30","source":"Crossref","is-referenced-by-count":0,"title":["A Comprehensive Survey of Subgraph Matching: [Experiments &amp; Analysis]"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0270-5408","authenticated-orcid":false,"given":"Haolin","family":"Jiang","sequence":"first","affiliation":[{"name":"Rutgers, The State University of New Jersey, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3528-6868","authenticated-orcid":false,"given":"Santosh","family":"Pandey","sequence":"additional","affiliation":[{"name":"University of South Florida, Tampa, Florida, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6323-7388","authenticated-orcid":false,"given":"Hang","family":"Liu","sequence":"additional","affiliation":[{"name":"Rutgers, The State University of New Jersey, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_1_2_1","volume-title":"Beni Egressy, Andreea Anghel, and Kubilay Atasu.","author":"Altman Erik","year":"2023","unstructured":"Erik Altman, Jovan Blanu\u0161a, Luc Von Niederh\u00e4usern, Beni Egressy, Andreea Anghel, and Kubilay Atasu. 2023. Realistic Synthetic Financial Transactions for Anti-Money Laundering Models. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track. https:\/\/openreview.net\/forum?id=XZf2bnMBag"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3184470.3184473"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589312"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3488932.3523261"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3664476.3664494"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456253"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677052.3698674"},{"key":"e_1_2_1_12_1","volume-title":"Juan Sebastian Chavez Palan, and Adam Szava","author":"Bonato Anthony","year":"2024","unstructured":"Anthony Bonato, Juan Sebastian Chavez Palan, and Adam Szava. 2024. Enhancing Anti-Money Laundering Efforts with Network-Based Algorithms. arXiv:2409.00823 [cs.SI] https:\/\/arxiv.org\/abs\/2409.00823"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16001-1_20"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118103746"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2696940"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3567955.3567956"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3575693.3575743"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503222.3507730"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447818.3460359"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00052"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598591"},{"key":"e_1_2_1_23_1","volume-title":"SubgraphMatchingSurvey: A Survey and Benchmarking of Subgraph Matching Algorithms. https:\/\/github.com\/JackChuengQAQ\/SubgraphMatchingSurvey\/","author":"Chueng Jack","year":"2025","unstructured":"Jack Chueng. 2025. SubgraphMatchingSurvey: A Survey and Benchmarking of Subgraph Matching Algorithms. https:\/\/github.com\/JackChuengQAQ\/SubgraphMatchingSurvey\/. Accessed: July 2025."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3470496.3527388"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210259.3210261"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_1_28_1","volume-title":"Serious and Organised Crime Threat Assessment (SOCTA)","year":"2021","unstructured":"Europol. 2021. Serious and Organised Crime Threat Assessment (SOCTA) 2021. Technical Report. European Union Agency for Law Enforcement Cooperation (Europol), The Hague, Netherlands. https:\/\/www.europol.europa.eu\/cms\/sites\/default\/files\/documents\/socta2021_1.pdf Accessed: 2025-03-31."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274578"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.81"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0076850"},{"key":"e_1_2_1_32_1","unstructured":"Chuangyi Gui Xiaofei Liao Long Zheng and Hai Jin. [n.d.]. Cyclosa: Redundancy-Free Graph Pattern Mining via Set Dataflow. ([n.d.])."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT52795.2021.00030"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389699"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3035564"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3552326.3567489"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587144"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00057"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3313726"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00321"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588692"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00129"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.02.018"},{"key":"e_1_2_1_48_1","unstructured":"Arijit Khan Xiangyu Ke and Yinghui Wu. 2025. Graph Data Management and Graph Machine Learning: Synergies and Opportunities. arXiv:2502.00529 [cs.DB] https:\/\/arxiv.org\/abs\/2502.00529"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457265"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00749-x"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915209"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196917"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkae1059"},{"key":"e_1_2_1_54_1","first-page":"1115","volume-title":"Proceedings of the 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011","author":"Klein K.","year":"2011","unstructured":"K. Klein, N. Kriege, and P. Mutzel. 2011. CT-Index: Fingerprint-Based Graph Indexing Combining Cycles and Trees. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering, ICDE 2011, Hannover, Germany, April 11-16, 2011. IEEE, 1115-1126."},{"key":"e_1_2_1_55_1","unstructured":"Longbin Lai Lu Qin Xuemin Lin and Lijun Chang. [n.d.]. Scalable Subgraph Enumeration in MapReduce. ([n.d.])."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2022.105677"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-024-07968-y"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638507"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113297"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT58117.2023.00026"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709665"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00250"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT52795.2021.00028"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469379.3469383"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Amine Mhedhbi and Semih Salihoglu. 2019. Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins. arXiv:1903.02076 [cs.DB] https:\/\/arxiv.org\/abs\/1903.02076","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457395"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_2_1_71_1","volume-title":"openGraphMatching: A Python Package for Graph Matching. https:\/\/pypi.org\/project\/openGraphMatching\/","author":"Developers GraphMatching","year":"2025","unstructured":"openGraphMatching Developers. 2025. openGraphMatching: A Python Package for Graph Matching. https:\/\/pypi.org\/project\/openGraphMatching\/. Accessed: July 2025."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.10.005"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl030"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00248"},{"key":"e_1_2_1_76_1","volume-title":"SubgraphMatching: A Research-Oriented Subgraph Matching Framework. https:\/\/github.com\/RapidsAtHKUST\/SubgraphMatching\/","author":"HKUST.","year":"2025","unstructured":"RapidsAtHKUST. 2025. SubgraphMatching: A Research-Oriented Subgraph Matching Framework. https:\/\/github.com\/RapidsAtHKUST\/SubgraphMatching\/. Accessed: July 2025."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342272"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0968-2"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3613213"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00104"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE65448.2025.00093"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13321-020-00478-9"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00163"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00028"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2980257"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551803"},{"key":"e_1_2_1_92_1","volume-title":"Efficient subgraph matching on billion node graphs. arXiv preprint arXiv:1205.6691","author":"Sun Zhao","year":"2012","unstructured":"Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li. 2012. Efficient subgraph matching on billion node graphs. arXiv preprint arXiv:1205.6691 (2012)."},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3470496.3527437"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_96_1","volume-title":"Proc. International Conference on Database Theory.","author":"Veldhuizen Todd L","year":"2014","unstructured":"Todd L Veldhuizen. 2014. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory."},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526163"},{"key":"e_1_2_1_98_1","unstructured":"Huiju Wang Zhengkui Wang Kian-Lee Tan Chee-Yong Chan Qi Fan and Xiao Yue. 2017. VCExplorer: A Interactive Graph Exploration Framework Based on Hub Vertices with Graph Consolidation. arXiv:1709.06745 [cs.DB] https:\/\/arxiv.org\/abs\/1709.06745"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00023"},{"key":"e_1_2_1_100_1","unstructured":"Kai Wang Zhiqiang Zuo John Thorpe Tien Quang Nguyen and Guoqing Harry Xu. [n.d.]. RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine. ([n.d.])."},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-023-43597-1"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00021"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00058"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476214"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588695"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457237"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.14778\/3654621.3654630"},{"key":"e_1_2_1_108_1","unstructured":"Kaiqiang Yu Kaixin Wang Cheng Long Laks Lakshmanan and Reynold Cheng. 2025. Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach. arXiv:2502.11557 [cs.DB] https:\/\/arxiv.org\/abs\/2502.11557"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494129"},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00112"},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516384"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00082"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639315"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3771791","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T04:31:31Z","timestamp":1775536291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3771791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":114,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3771791"],"URL":"https:\/\/doi.org\/10.1145\/3771791","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}