{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:32:37Z","timestamp":1791916357515,"version":"4.3.4"},"reference-count":101,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Shanghai Science and Technology Innovation Action Plan","award":["No. 21511100401"],"award-info":[{"award-number":["No. 21511100401"]}]},{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. U23A20496"],"award-info":[{"award-number":["No. U23A20496"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021171","name":"GuangDong Basic and Applied Basic Research Foundation","doi-asserted-by":"crossref","award":["No. 2019B1515120048"],"award-info":[{"award-number":["No. 2019B1515120048"]}],"id":[{"id":"10.13039\/501100021171","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Subgraph matching is a fundamental problem in graph analysis. In recent years, many subgraph matching algorithms have been proposed, making it pressing and challenging to compare their performance and identify their strengths and weaknesses. We observe that (1) The embedding enumeration in the classic filtering-ordering-enumerating framework dominates the overall performance, and thus enhancing the backtracking paradigm is becoming a current research trend; (2) Simply changing the limitation of output size results in a substantial variation in the ranking of different methods, leading to biased performance evaluation; (3) The techniques employed at different stages of subgraph matching interact with each other, making it less feasible to replace and evaluate a single technique in isolation. Therefore, a comprehensive survey and experimental study of subgraph matching is necessary to identify the current trends, ensure unbiasedness, and investigate the potential interactions. In this paper, we comprehensively review the methods in the current trend and experimentally confirm their advantage over prior approaches. We unbiasedly evaluate the performance of these algorithms by using an effective metric, namely embeddings per second. To fully investigate the interactions between various techniques, we select 10 representative techniques for each stage and evaluate all the feasible combinations.<\/jats:p>","DOI":"10.1145\/3639315","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-29","source":"Crossref","is-referenced-by-count":38,"title":["A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-9936-776X","authenticated-orcid":false,"given":"Zhijie","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6384-5548","authenticated-orcid":false,"given":"Yujie","family":"Lu","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1200-7368","authenticated-orcid":false,"given":"Weiguo","family":"Zheng","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Antai College of Economics and Management, Shanghai Jiaotong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the VLDB Endowment","author":"Ammar Khaled","year":"2018","unstructured":"Khaled Ammar, Frank McSherry, Semih Salihoglu, and Manas Joglekar. 2018. Distributed evaluation of subgraph queries using worstcase optimal lowmemory dataflows. Proceedings of the VLDB Endowment (2018)."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589312"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data","author":"Bhattarai Bibek","unstructured":"Bibek Bhattarai, Hang Liu, and H. Howie Huang. 2019. CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching. In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands) (SIGMOD '19). Association for Computing Machinery, New York, NY, USA, 1447--1462."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1887854.1887873"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471--2105--14-S7-S13"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 26th International Conference on Neural Information Processing Systems -","volume":"2","author":"Bordes Antoine","year":"2013","unstructured":"Antoine Bordes, Nicolas Usunier, Alberto Garcia-Dur\u00e1n, Jason Weston, and Oksana Yakhnenko. 2013. Translating Embeddings for Modeling Multi-Relational Data. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2 (Lake Tahoe, Nevada) (NIPS'13). Curran Associates Inc., Red Hook, NY, USA, 2787--2795."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2696940"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/320434.320440"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447818.3460359"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00052"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471--2105--11--96"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274578"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476369"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1937.10503522"},{"key":"e_1_2_2_22_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1990","unstructured":"Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0076911"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3035564"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0097896"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588692"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2019.000--6"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00129"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.02.018"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.02.018"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the 24th International Conference on Parallel Architectures and Compilation Techniques (PACT '15)","author":"Khorasani Farzad","unstructured":"Farzad Khorasani, Rajiv Gupta, and Laxmi N. Bhuyan. 2015. Scalable SIMD-Efficient Graph Processing on GPUs. In Proceedings of the 24th International Conference on Parallel Architectures and Compilation Techniques (PACT '15). 39--50."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457265"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915209"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809985"},{"key":"e_1_2_2_41_1","volume-title":"Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong.","author":"Kim Kyoungmin","year":"2018","unstructured":"Kyoungmin Kim, In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong. 2018. TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data. In Proceedings of the 2018 International Conference on Management of Data. 411--426."},{"key":"e_1_2_2_42_1","volume-title":"Shared Memory Parallel Subgraph Enumeration. 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)","author":"Kimmig Raphael","year":"2017","unstructured":"Raphael Kimmig, Henning Meyerhenke, and Darren Strash. 2017. Shared Memory Parallel Subgraph Enumeration. 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) (2017), 519--529."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767909"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339494"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.fss.2019.02.021"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2875262"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_2_2_52_1","first-page":"1","article-title":"When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases","volume":"61","author":"McCreesh Ciaran","year":"2018","unstructured":"Ciaran McCreesh, Patrick Prosser, Christine Solnon, and James Trimble. 2018. When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases. J. Artif. Int. Res. 61, 1 (jan 2018), 723--759.","journal-title":"J. Artif. Int. Res."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457395"},{"key":"e_1_2_2_56_1","volume-title":"Distribution-free multiple comparisons","author":"Nemenyi Peter Bjorn","unstructured":"Peter Bjorn Nemenyi. 1963. Distribution-free multiple comparisons. Princeton University."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0405--2"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3433652"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3164135.3164139"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2023.3"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_2_70_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Shi Tianhui","year":"2020","unstructured":"Tianhui Shi, Mingshu Zhai, Yi Xu, and Jidong Zhai. 2020. GraphPi: High Performance Graph Pattern Matching through Effective Redundancy Elimination. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Atlanta, Georgia) (SC '20). IEEE Press, Article 100, 14 pages."},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(77)90029-7"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00029"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00028"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551803"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589326"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68204-4_22"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_2_82_1","unstructured":"T. Veldhuizen. 2014. Triejoin: A Simple Worst-Case Optimal Join Algorithm. In ICDT."},{"key":"e_1_2_2_83_1","volume-title":"Leapfrog triejoin: a worst-case optimal join algorithm. arXiv preprint arXiv:1210.0481","author":"Veldhuizen Todd L","year":"2012","unstructured":"Todd L Veldhuizen. 2012. Leapfrog triejoin: a worst-case optimal join algorithm. arXiv preprint arXiv:1210.0481 (2012)."},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","unstructured":"Carletti Vincenzo Pasquale Foggia Pierluigi Ritrovato Mario Vento and Vincenzo Vigilante. 2019. A Parallel Algorithm for Subgraph Isomorphism. 141--151. https:\/\/doi.org\/10.1007\/978--3-030--20081--7_14","DOI":"10.1007\/978--3-030--20081--7_14"},{"key":"e_1_2_2_85_1","volume-title":"Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation","author":"Wang Kai","year":"2018","unstructured":"Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018. RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on a Single Machine. In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (Carlsbad, CA, USA) (OSDI'18). USENIX Association, USA, 763--782."},{"key":"e_1_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00021"},{"key":"e_1_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3076246"},{"key":"e_1_2_2_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476214"},{"key":"e_1_2_2_89_1","volume-title":"FASI: FPGA-friendly Subgraph Isomorphism on Massive Graphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE).","author":"Xunbin Su","year":"2023","unstructured":"Su Xunbin, Lin Yinnian, and Lei Zou. 2023. FASI: FPGA-friendly Subgraph Isomorphism on Massive Graphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE)."},{"key":"e_1_2_2_90_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000056"},{"key":"e_1_2_2_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2912566"},{"key":"e_1_2_2_92_1","volume-title":"Pregel: A Distributed Graph Computing Framework with Effective Message Reduction","author":"Yan Da","year":"2014","unstructured":"Da Yan, James Cheng, Kai Xing, Yi Lu, Wilfred Ng, and Yingyi Bu. 2014. Pregel: A Distributed Graph Computing Framework with Effective Message Reduction. The Chinese University of Hong Kong, Hong Kong, China. http:\/\/www.cse.cuhk.edu.hk\/pregelplus\/"},{"key":"e_1_2_2_93_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00122"},{"key":"e_1_2_2_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_2_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588695"},{"key":"e_1_2_2_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457237"},{"key":"e_1_2_2_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00112"},{"key":"e_1_2_2_98_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00082"},{"key":"e_1_2_2_99_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00082"},{"key":"e_1_2_2_100_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00064"},{"key":"e_1_2_2_101_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases","author":"Zhao Peixiang","unstructured":"Peixiang Zhao, Jeffrey Xu Yu, and Philip S. Yu. 2007. Graph Indexing: Tree Delta &gt;= Graph. In Proceedings of the 33rd International Conference on Very Large Data Bases (Vienna, Austria) (VLDB '07). VLDB Endowment, 938--949."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:14:57Z","timestamp":1755789297000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":101,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639315"],"URL":"https:\/\/doi.org\/10.1145\/3639315","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}