{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T02:50:17Z","timestamp":1783738217232,"version":"3.55.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Subgraph matching, which finds subgraphs isomorphic to a query, is crucial for information retrieval from data represented as a graph. To avoid redundant explorations in the data, existing methods restrict the search space by extracting candidate vertices and edges that may constitute isomorphic subgraphs. However, expensive computation is still required because candidate vertices induce many non-isomorphic subgraphs. In this paper, we propose GuP, a subgraph matching algorithm with pruning based on guards. A guard represents a pattern of intermediate search states that never lead to isomorphic subgraphs. By attaching a guard to each candidate vertex and edge, GuP adaptively filters out unnecessary candidates depending on the search state at each step. The experimental results show that GuP effectively reduces the search space and can answer difficult queries that state-of-the-art methods cannot answer within a practical time frame.<\/jats:p>","DOI":"10.1145\/3589312","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-26","source":"Crossref","is-referenced-by-count":40,"title":["GuP: Fast Subgraph Matching by Guard-based Pruning"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5681-5941","authenticated-orcid":false,"given":"Junya","family":"Arai","sequence":"first","affiliation":[{"name":"Nippon Telegraph and Telephone Corporation, Musashino-shi, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-1118","authenticated-orcid":false,"given":"Yasuhiro","family":"Fujiwara","sequence":"additional","affiliation":[{"name":"Nippon Telegraph and Telephone Corporation, Atsugi-shi, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5559-8300","authenticated-orcid":false,"given":"Makoto","family":"Onizuka","sequence":"additional","affiliation":[{"name":"Osaka University, Suita-shi, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data, 1447--1462","author":"Bhattarai Bibek","unstructured":"Bibek Bhattarai, Hang Liu, and H. Howie Huang. 2019. CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching. Proceedings of the 2019 International Conference on Management of Data, 1447--1462."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1887854.1887873"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247574"},{"key":"e_1_2_2_7_1","first-page":"726","article-title":"Graph theory in the information age","volume":"57","author":"Chung Fan","year":"2010","unstructured":"Fan Chung. 2010. Graph theory in the information age. Notices of the American Mathematical Society, Vol. 57 (2010), 726--732.","journal-title":"Notices of the American Mathematical Society"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_2_9_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition 3rd ed.).","edition":"3"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 14th International Joint Conference on Artificial Intelligence -","volume":"1","author":"Eugene","unstructured":"Eugene C. Freuder and Richard J. Wallace. 1995. Generalizing Inconsistency Learning for Constraint Satisfaction. Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 1, 563--569."},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the Canadian Artificial Intelligence Conference","author":"Gaschnig J.","year":"1978","unstructured":"J. Gaschnig. 1978. Experimental case studies of backtrack vs. Waltz-type vs. new algorithms for satisficing assignment problems. Proceedings of the Canadian Artificial Intelligence Conference (1978), 268--277."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1618595.1618597"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0076911"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, 405--418","author":"He Huahai","unstructured":"Huahai He and Ambuj K. Singh. 2008. Graphs-at-a-time: Query Language and Access Methods for Graph Databases. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, 405--418."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402747"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45349-0_19"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of 20th International Conference on Extending Database Technology, 25--36","author":"Katsarou Foteini","year":"2017","unstructured":"Foteini Katsarou, Nikos Ntarmos, and Peter Triantafillou. 2017. Subgraph Querying with Parallel Use of Query Rewritings and Alternative Algorithms. Proceedings of 20th International Conference on Extending Database Technology, 25--36."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00749-x"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data, 1231--1245","author":"Kim Hyeonji","unstructured":"Hyeonji Kim, Juneyoung Lee, Sourav S. Bhowmick, Wook-Shin Han, JeongHoon Lee, Seongyun Ko, and Moath H. A. Jarrah. 2016. DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine. Proceedings of the 2016 International Conference on Management of Data, 1231--1245."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809985"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Ciaran McCreesh and Patrick Prosser. 2015. A Parallel Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs Gilles Pesant (Ed.). Principles and Practice of Constraint Programming 295--312.","DOI":"10.1007\/978-3-319-23219-5_21"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Ciaran McCreesh Patrick Prosser and James Trimble. 2020. The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants Fabio Gadducci and Timo Kehrer (Eds.). Graph Transformation 316--324.","DOI":"10.1007\/978-3-030-51372-6_19"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_2_29_1","volume-title":"2011 Federated Conference on Computer Science and Information Systems (FedCSIS), 69--75","author":"Michalak Krzysztof","year":"2011","unstructured":"Krzysztof Michalak and Jerzy Korczak. 2011. Graph mining approach to suspicious transaction detection. 2011 Federated Conference on Computer Science and Information Systems (FedCSIS), 69--75."},{"key":"e_1_2_2_30_1","volume-title":"Hybrid algorithms for the constraint satisfaction problem. Computational intelligence","author":"Prosser Patrick","year":"1993","unstructured":"Patrick Prosser. 1993. Hybrid algorithms for the constraint satisfaction problem. Computational intelligence, Vol. 9 (1993), 268--299."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_2_32_1","unstructured":"Francesca Rossi Peter van Beek and Toby Walsh. 2006. Handbook of Constraint Programming."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(77)90029-7"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2980257"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536349.2536352"},{"key":"e_1_2_2_40_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\/10.1145\/3589312","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:13Z","timestamp":1750178773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589312"],"URL":"https:\/\/doi.org\/10.1145\/3589312","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}