{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:03:01Z","timestamp":1775595781440,"version":"3.50.1"},"reference-count":130,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"National Natural Science Foundation of China","award":["U24B20143"],"award-info":[{"award-number":["U24B20143"]}]},{"name":"National Natural Science Foundation of China","award":["62372030"],"award-info":[{"award-number":["62372030"]}]},{"name":"State Key Laboratory of Complex &amp; Critical Software Environment","award":["&#x2a;"],"award-info":[{"award-number":["&#x2a;"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>\n                    This paper presents an ML-based method for SubIso, the graph pattern matching problem. Given a graph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    and a pattern\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    , SubIso aims to enumerate all subgraphs of\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    that are isomorphic to\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    . We show that SubIso is EnumP-complete, where EnumP is the enumeration counterpart of NP. We then study revisions VF3\n                    <jats:sub>M<\/jats:sub>\n                    of the classical VF3 algorithm by incorporating an ML oracle \u213b. The model \u213b predicts candidate matches, while VF3\n                    <jats:sub>M<\/jats:sub>\n                    verifies them, thereby reducing costly backtracking. We examine whether VF3\n                    <jats:sub>M<\/jats:sub>\n                    is (a) output-polynomial, i.e., its runtime is polynomial in the sizes of input and output; (b) consistent, i.e., its accuracy reaches 100% with error-free predictions from \u213b; and (c) \u03b2-robust, i.e., it guarantees accuracy of at least \u03b2 even with arbitrarily bad predictions.\n                  <\/jats:p>\n                  <jats:p>\n                    We establish several results, positive and negative. On the negative side, we show that it is impossible for VF3\n                    <jats:sub>M<\/jats:sub>\n                    to be both output polynomial and \u03b2-robust with a positive constant \u03b2 unless P = fewP, a problem as hard as P = NP. On the positive side, we develop three versions of VF3\n                    <jats:sub>M<\/jats:sub>\n                    that are (a) consistent, and (b) either 1-robust or output polynomial with a high probability. We also train a model \u213b for VF3\n                    <jats:sub>M<\/jats:sub>\n                    . Using real-life and synthetic data, we show that VF3\n                    <jats:sub>M<\/jats:sub>\n                    is up to 15.75x--21x faster than VF3, with F1-score 0.98.\n                  <\/jats:p>","DOI":"10.1145\/3786648","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-28","source":"Crossref","is-referenced-by-count":0,"title":["Enumerating Graph Pattern Matches with ML Oracles"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5149-2656","authenticated-orcid":false,"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"Beihang University, Beijing, China, Shenzhen Institute of Computing Sciences, Shenzhen, China, and University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2416-9476","authenticated-orcid":false,"given":"Yixuan","family":"Luo","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4919-8989","authenticated-orcid":false,"given":"Ping","family":"Lu","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5701-5279","authenticated-orcid":false,"given":"Xiaoke","family":"Zhu","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Computing Sciences, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2021. DBLP collaboration network. https:\/\/snap.stanford.edu\/data\/com-DBLP.html."},{"key":"e_1_2_1_2_1","unstructured":"2025. LiveJournal. https:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html."},{"key":"e_1_2_1_3_1","unstructured":"2025. Pokec. http:\/\/snap.stanford.edu\/data\/soc-pokec.html."},{"key":"e_1_2_1_4_1","unstructured":"2025. vf3lib. https:\/\/github.com\/MiviaLab\/vf3lib."},{"key":"e_1_2_1_5_1","volume-title":"Sandeep Silwal, and Ali Vakilian.","author":"Aamand Anders","year":"2023","unstructured":"Anders Aamand, Justin Y. Chen, Huy L\u00ea Nguyen, Sandeep Silwal, and Ali Vakilian. 2023. Improved Frequency Estimation Algorithms with and without Predictions. In NeurIPS."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSRE.2007.916269"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Shubhangi Agarwal Sourav Dutta and Arnab Bhattacharya. 2021. VerSaChI: Finding Statistically Significant Subgraph Matches using Chebyshev's Inequality. In CIKM. 2812--2816.","DOI":"10.1145\/3459637.3482217"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Shubhangi Agarwal Sourav Dutta and Arnab Bhattacharya. 2024. VeNoM: Approximate Subgraph Matching with Enhanced Neighbourhood Structural Information. In COMAD\/CODS. 18--26.","DOI":"10.1145\/3632410.3632459"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217075"},{"key":"e_1_2_1_10_1","unstructured":"Keerti Anand Rong Ge Amit Kumar and Debmalya Panigrahi. 2021. A Regression Approach to Learning-Augmented Online Algorithms. In NeurIPS. 30504--30517."},{"key":"e_1_2_1_11_1","first-page":"303","article-title":"Customizing ML Predictions for Online Algorithms","volume":"119","author":"Anand Keerti","year":"2020","unstructured":"Keerti Anand, Rong Ge, and Debmalya Panigrahi. 2020. Customizing ML Predictions for Online Algorithms. In ICML, Vol. 119. 303--313.","journal-title":"ICML"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.14117"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.14820"},{"key":"e_1_2_1_14_1","first-page":"952","article-title":"Paging with Succinct Predictions","volume":"202","author":"Antoniadis Antonios","year":"2023","unstructured":"Antonios Antoniadis, Joan Boyar, Marek Eli\u00e1s, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, and Bertrand Simon. 2023. Paging with Succinct Predictions. In ICML, Vol. 202. 952--968.","journal-title":"ICML"},{"key":"e_1_2_1_15_1","first-page":"969","article-title":"Mixing Predictions for Online Metric Algorithms","volume":"202","author":"Antoniadis Antonios","year":"2023","unstructured":"Antonios Antoniadis, Christian Coester, Marek Eli\u00e1s, Adam Polak, and Bertrand Simon. 2023. Mixing Predictions for Online Metric Algorithms. In ICML, Vol. 202. 969--983.","journal-title":"ICML"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Junya Arai Yasuhiro Fujiwara and Makoto Onizuka. 2023. GuP: Fast Subgraph Matching by Guard-based Pruning. In SIGMOD.","DOI":"10.1145\/3589312"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725355"},{"key":"e_1_2_1_18_1","unstructured":"Xingjian Bai and Christian Coester. 2023. Sorting with Predictions. In NeurIPS."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Thomas B\u00e4recke and Marcin Detyniecki. 2007. Combining exhaustive and approximate methods for improved sub-graph matching. In Progress in Pattern Recognition. 17--26.","DOI":"10.1007\/978-1-84628-945-3_2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01572-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Fei Bi Lijun Chang Xuemin Lin Lu Qin and Wenjie Zhang. 2016. Efficient Subgraph Matching by Postponing Cartesian Products. In SIGMOD. 1199--1214.","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_23_1","volume-title":"S-7","author":"Bonnici Vincenzo","year":"2013","unstructured":"Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis E. Shasha, and Alfredo Ferro. 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform. 14, S-7 (2013), S13."},{"key":"e_1_2_1_24_1","volume-title":"Mikkelsen","author":"Boyar Joan","year":"2017","unstructured":"Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. 2017. Online Algorithms with Advice: A Survey. ACM Comput. Surv. 50, 2 (2017), 19:1--19:34."},{"key":"e_1_2_1_25_1","volume-title":"Larsen","author":"Boyar Joan","year":"2018","unstructured":"Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. 2018. Relative Worst-Order Analysis: A Survey. In Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovic on the Occasion of His 60th Birthday. 216--230."},{"key":"e_1_2_1_26_1","volume-title":"Kevin Chen-Chuan Chang, and Reynold Cheng","author":"Cao Hongtai","year":"2024","unstructured":"Hongtai Cao, Qihao Wang, Xiaodong Li, Matin Najafi, Kevin Chen-Chuan Chang, and Reynold Cheng. 2024. Large Subgraph Matching: A Comprehensive and Efficient Approach for Heterogeneous Graphs. In ICDE. 2972--2985."},{"key":"e_1_2_1_27_1","volume-title":"On The Complexity of Enumeration. CoRR abs\/1703.01928","author":"Capelli Florent","year":"2017","unstructured":"Florent Capelli and Yann Strozecki. 2017. On The Complexity of Enumeration. CoRR abs\/1703.01928 (2017). http:\/\/arxiv.org\/abs\/1703.01928"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58961-9_12"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2696940"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781003456285"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.38094\/jastt20165"},{"key":"e_1_2_1_32_1","volume-title":"Professional CUDA c programming","author":"Cheng John","unstructured":"John Cheng, Max Grossman, and Ty McKercher. 2014. Professional CUDA c programming. John Wiley & Sons."},{"key":"e_1_2_1_33_1","volume-title":"The Sample Complexity of Revenue Maximization. CoRR abs\/1502.00963","author":"Cole Richard","year":"2015","unstructured":"Richard Cole and Tim Roughgarden. 2015. The Sample Complexity of Revenue Maximization. CoRR abs\/1502.00963 (2015). arXiv:1502.00963 http:\/\/arxiv.org\/abs\/1502.00963"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Stephen A. Cook. 1971. The Complexity of Theorem-Proving Procedures. In STOC. 151--158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_35_1","volume-title":"ACM Conference on Electronic Commerce (EC). 71--78","author":"Nikhil","unstructured":"Nikhil R. Devanur and Thomas P. Hayes. 2009. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In ACM Conference on Electronic Commerce (EC). 71--78."},{"key":"e_1_2_1_36_1","first-page":"2687","article-title":"Learning Online Algorithms with Distributional Advice","volume":"139","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. 2021. Learning Online Algorithms with Distributional Advice. In ICML, Vol. 139. 2687--2696.","journal-title":"ICML"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018972125742"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Michael Dinitz Sungjin Im Thomas Lavastida Benjamin Moseley and Sergei Vassilvitskii. 2022. Algorithms with Prediction Portfolios. In NeurIPS.","DOI":"10.52202\/068431-1474"},{"key":"e_1_2_1_39_1","volume-title":"PARSEC: PARallel Subgraph Enumeration in CUDA. In IPDPS. 168--178.","author":"Dodeja Vibhor","year":"2022","unstructured":"Vibhor Dodeja, Mohammad Almasri, Rakesh Nagi, Jinjun Xiong, and Wen-Mei Hwu. 2022. PARSEC: PARallel Subgraph Enumeration in CUDA. In IPDPS. 168--178."},{"key":"e_1_2_1_40_1","first-page":"8078","article-title":"Online Algorithms with Costly Predictions","volume":"206","author":"Drygala Marina","year":"2023","unstructured":"Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. 2023. Online Algorithms with Costly Predictions. In AISTATS, Vol. 206. 8078--8101.","journal-title":"AISTATS"},{"key":"e_1_2_1_41_1","unstructured":"Keyu Duan Zirui Liu Peihao Wang Wenqing Zheng Kaixiong Zhou Tianlong Chen Xia Hu and Zhangyang Wang. 2022. A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking. In NeurIPS."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Sourav Dutta Pratik Nayek and Arnab Bhattacharya. 2017. Neighbor-Aware Search for Approximate Labeled Graph Matching using the Chi-Square Statistics. In WWW. 1281--1290.","DOI":"10.1145\/3038912.3052561"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915232"},{"key":"e_1_2_1_44_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_45_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael","unstructured":"Michael Garey and David Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_1_46_1","volume-title":"Computational complexity - A conceptual perspective","author":"Goldreich Oded","unstructured":"Oded Goldreich. 2008. Computational complexity - A conceptual perspective. Cambridge University Press."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9875-7"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Themistoklis Gouleakis Konstantinos Lakis and Golnoosh Shahkarami. 2023. Learning-Augmented Algorithms for Online TSP on the Line. In AAAI. 11989--11996.","DOI":"10.1609\/aaai.v37i10.26414"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Wentian Guo Yuchen Li Mo Sha Bingsheng He Xiaokui Xiao and Kian-Lee Tan. 2020. GPU-Accelerated Subgraph Enumeration on Partitioned Graphs. In SIGMOD. 1067--1082.","DOI":"10.1145\/3318464.3389699"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3035564"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Anupam Gupta Debmalya Panigrahi Bernardo Subercaseaux and Kevin Sun. 2022. Augmenting Online Algorithms with ?-Accurate Predictions. In NeurIPS.","DOI":"10.52202\/068431-0154"},{"key":"e_1_2_1_52_1","unstructured":"William L. Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS. 1024--1034."},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Myoungji Han Hyunjoon Kim Geonmo Gu Kunsoo Park and Wook-Shin Han. 2019. Efficient Subgraph Matching: Harmonizing Dynamic Programming Adaptive Matching Order and Failing Set Together. In SIGMOD. 1429--1446.","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489499"},{"key":"e_1_2_1_55_1","volume-title":"FAST: A Scalable Subgraph Matching Framework over Large Graphs. In HPEC. 1--7.","author":"He Jiezhong","year":"2022","unstructured":"Jiezhong He, Zhouyang Liu, Yixin Chen, Hengyue Pan, Zhen Huang, and Dongsheng Li. 2022. FAST: A Scalable Subgraph Matching Framework over Large Graphs. In HPEC. 1--7."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.004"},{"key":"e_1_2_1_57_1","unstructured":"Intel Corporation. 2013. Intel\u00ae Advanced Vector Extensions 2 (Intel\u00ae AVX2). https:\/\/www.intel.com\/content\/www\/us\/en\/docs\/intrinsics-guide\/index.html."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007270"},{"key":"e_1_2_1_59_1","volume-title":"Jean-Philippe Thiran, and Maria Gabrani.","author":"Jaume Guillaume","year":"2019","unstructured":"Guillaume Jaume, An-phi Nguyen, Mar\u00eda Rodr\u00edguez Mart\u00ednez, Jean-Philippe Thiran, and Maria Gabrani. 2019. edGNN: A Simple and Powerful GNN for Directed Labeled Graphs. CoRR abs\/1904.08745 (2019)."},{"key":"e_1_2_1_60_1","unstructured":"Zhihao Jia Sina Lin Mingyu Gao Matei Zaharia and Alex Aiken. 2020. Improving the Accuracy Scalability and Performance of Graph Neural Networks with Roc. In MLSys."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548774"},{"key":"e_1_2_1_62_1","volume-title":"IVE: Accelerating Enumeration-Based Subgraph Matching via Exploring Isolated Vertices. In ICDE. 4208--4221.","author":"Jiang Zite","year":"2024","unstructured":"Zite Jiang, Shuai Zhang, Xingzhong Hou, Mengting Yuan, and Haihang You. 2024. IVE: Accelerating Enumeration-Based Subgraph Matching via Exploring Isolated Vertices. In ICDE. 4208--4221."},{"key":"e_1_2_1_63_1","unstructured":"Elias B. Khalil Hanjun Dai Yuyu Zhang Bistra Dilkina and Le Song. 2017. Learning Combinatorial Optimization Algorithms over Graphs. In NeurIPS. 6348--6358."},{"key":"e_1_2_1_64_1","volume-title":"Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching. In SIGMOD. 925--937.","author":"Kim Hyunjoon","year":"2021","unstructured":"Hyunjoon Kim, Yunyoung Choi, Kunsoo Park, Xuemin Lin, Seok-Hee Hong, and Wook-Shin Han. 2021. Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching. In SIGMOD. 925--937."},{"key":"e_1_2_1_65_1","unstructured":"Minsu Kim Jinkyoo Park and Joungho Kim. 2021. Learning Collaborative Policies to Solve NP-hard Routing Problems. In NeurIPS. 10418--10430."},{"key":"e_1_2_1_66_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis.","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In SIGMOD. 489--504."},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Jon Kleinberg and Christos Faloutsos. 2005. Graphs over time: Densification laws shrinking diameters and possible explanations. In SIGKDD.","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407843"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648176"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2566618"},{"key":"e_1_2_1_71_1","doi-asserted-by":"crossref","unstructured":"Xin Liu and Yangqiu Song. 2022. Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching. In AAAI. 7594--7602.","DOI":"10.1609\/aaai.v36i7.20725"},{"key":"e_1_2_1_72_1","first-page":"22454","article-title":"D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching","volume":"202","author":"Liu Xuanzhou","year":"2023","unstructured":"Xuanzhou Liu, Lin Zhang, Jiaqi Sun, Yujiu Yang, and Haiqin Yang. 2023. D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching. In ICML, Vol. 202. 22454--22472.","journal-title":"ICML"},{"key":"e_1_2_1_73_1","volume-title":"Competitive caching with machine learned advice. CoRR abs\/1802.05399","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii. 2018. Competitive caching with machine learned advice. CoRR abs\/1802.05399 (2018). arXiv:1802.05399 http:\/\/arxiv.org\/abs\/1802.05399"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2025.3540787"},{"key":"e_1_2_1_75_1","unstructured":"Yining Ma Jingwen Li Zhiguang Cao Wen Song Le Zhang Zhenghua Chen and Jing Tang. 2021. Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer. In NeurIPS. 11096--11107."},{"key":"e_1_2_1_76_1","first-page":"23484","article-title":"Applied Online Algorithms with Heterogeneous Predictors","volume":"202","author":"Maghakian Jessica","year":"2023","unstructured":"Jessica Maghakian, Russell Lee, Mohammad Hajiesmaili, Jian Li, Ramesh K. Sitaraman, and Zhenhua Liu. 2023. Applied Online Algorithms with Heterogeneous Predictors. In ICML, Vol. 202. 23484--23497.","journal-title":"ICML"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2912087"},{"key":"e_1_2_1_78_1","volume-title":"Tawkir Ahmed Fakir, and Hans-Arno Jacobsen","author":"Merkel Nikolai","year":"2023","unstructured":"Nikolai Merkel, Ruben Mayer, Tawkir Ahmed Fakir, and Hans-Arno Jacobsen. 2023. Partitioner Selection with EASE to Optimize Distributed Graph Processing. In ICDE. 2400--2414."},{"key":"e_1_2_1_79_1","doi-asserted-by":"crossref","unstructured":"Azalia Mirhoseini Anna Goldie Mustafa Yazgan Joe Wenjie Jiang Ebrahim M. Songhori Shen Wang Young-Joon Lee Eric Johnson Omkar Pathak Azade Nazi Jiwoo Pak Andy Tong Kavya Srinivasa William Hang Emre Tuncer Quoc V. Le James Laudon Richard Ho Roger Carpenter and Jeff Dean. 2021. A graph placement methodology for fast chip design. Nature 594 7862 (2021) 207--212.","DOI":"10.1038\/s41586-021-03544-w"},{"key":"e_1_2_1_80_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher and Sergei Vassilvitskii. 2020. Algorithms with Predictions. In Beyond the Worst-Case Analysis of Algorithms. 646--662.","DOI":"10.1017\/9781108637435.037"},{"key":"e_1_2_1_81_1","volume-title":"Revenue Optimization with Approximate Bid Predictions. CoRR abs\/1706.04732","author":"Medina Andr\u00e9s Mu\u00f1oz","year":"2017","unstructured":"Andr\u00e9s Mu\u00f1oz Medina and Sergei Vassilvitskii. 2017. Revenue Optimization with Approximate Bid Predictions. CoRR abs\/1706.04732 (2017). arXiv:1706.04732 http:\/\/arxiv.org\/abs\/1706.04732"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2018-1634"},{"key":"e_1_2_1_83_1","doi-asserted-by":"crossref","unstructured":"Iv\u00e1n Olmos Jes\u00fas A. Gonz\u00e1lez and Mauricio Osorio. 2007. Reductions between the Subgraph Isomorphism Problem and Hamiltonian and SAT Problems. In CONIELECOMP. 20.","DOI":"10.1109\/CONIELECOMP.2007.30"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1910.00039"},{"key":"e_1_2_1_85_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H","unstructured":"Christos H Papadimitriou. 2003. Computational Complexity. John Wiley and Sons Ltd."},{"key":"e_1_2_1_86_1","unstructured":"Manish Purohit Zoya Svitkina and Ravi Kumar. 2018. Improving Online Algorithms via ML Predictions. In NeurIPS. 9684--9693."},{"key":"e_1_2_1_87_1","volume-title":"DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. In NeurIPS.","author":"Qiu Ruizhong","year":"2022","unstructured":"Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. 2022. DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. In NeurIPS."},{"key":"e_1_2_1_88_1","first-page":"198","article-title":"Approximate Sub-graph Matching over Knowledge Graph","volume":"341","author":"Ren Jiyuan","year":"2020","unstructured":"Jiyuan Ren, Yangfu Liu, Yi Shen, Zhe Wang, and Zhen Luo. 2020. Approximate Sub-graph Matching over Knowledge Graph. In MobiCASE, Vol. 341. 198--208.","journal-title":"MobiCASE"},{"key":"e_1_2_1_89_1","doi-asserted-by":"crossref","unstructured":"Dhruv Rohatgi. 2020. Near-Optimal Bounds for Online Caching with Machine Learned Advice. In SODA. 1834--1845.","DOI":"10.1137\/1.9781611975994.112"},{"key":"e_1_2_1_90_1","volume-title":"Soumen Chakrabarti, and Abir De.","author":"Roy Indradyumna","year":"2022","unstructured":"Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. 2022. Interpretable Neural Subgraph Matching for Graph Retrieval. In AAAI. 8115--8123."},{"key":"e_1_2_1_91_1","first-page":"593","article-title":"Modeling Relational Data with Graph Convolutional Networks","volume":"10843","author":"Schlichtkrull Michael Sejr","year":"2018","unstructured":"Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018. Modeling Relational Data with Graph Convolutional Networks. In ESWC, Vol. 10843. 593--607.","journal-title":"ESWC"},{"key":"e_1_2_1_92_1","volume-title":"Enumeration: Algorithms and Complexity. Ph. D. Dissertation. Universiteit Utrecht.","author":"Schmidt Johannes","year":"2009","unstructured":"Johannes Schmidt. 2009. Enumeration: Algorithms and Complexity. Ph. D. Dissertation. Universiteit Utrecht."},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639299"},{"key":"e_1_2_1_94_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_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725323"},{"key":"e_1_2_1_96_1","doi-asserted-by":"crossref","unstructured":"Dave Steinkrau Patrice Y. Simard and Ian Buck. 2005. Using GPUs for Machine Learning Algorithms. In ICDAR. 1115--1119.","DOI":"10.1109\/ICDAR.2005.251"},{"key":"e_1_2_1_97_1","first-page":"532","article-title":"On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation","volume":"53","author":"Strozecki Yann","year":"2013","unstructured":"Yann Strozecki. 2013. On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation. TCS 53, 4 (2013), 532--568.","journal-title":"TCS"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9442-z"},{"key":"e_1_2_1_99_1","first-page":"32859","article-title":"Revisiting Sampling for Combinatorial Optimization","volume":"202","author":"Sun Haoran","year":"2023","unstructured":"Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. 2023. Revisiting Sampling for Combinatorial Optimization. In ICML, Vol. 202. 32859--32874.","journal-title":"ICML"},{"key":"e_1_2_1_100_1","first-page":"176","article-title":"RapidMatch: A Holistic Approach to Subgraph Query Processing","volume":"14","author":"Sun Shixuan","year":"2020","unstructured":"Shixuan Sun, Xibo Sun, Yulin Che, Qiong Luo, and Bingsheng He. 2020. RapidMatch: A Holistic Approach to Subgraph Query Processing. PVLDB 14, 2 (2020), 176--188.","journal-title":"PVLDB"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589326"},{"key":"e_1_2_1_102_1","volume-title":"DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. In NeurIPS.","author":"Sun Zhiqing","year":"2023","unstructured":"Zhiqing Sun and Yiming Yang. 2023. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. In NeurIPS."},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2024.103162"},{"key":"e_1_2_1_104_1","doi-asserted-by":"crossref","unstructured":"Yuya Tatsugi and Akira Nukada. 2022. Accelerating data transfer between host and device using idle GPU. In GPGPU@PPoPP. 2:1--2:6.","DOI":"10.1145\/3530390.3532732"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3264-1"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2020.2990722"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807360"},{"key":"e_1_2_1_109_1","unstructured":"Ivan Vendrov Ryan Kiros Sanja Fidler and Raquel Urtasun. 2016. Order-Embeddings of Images and Language. In ICLR."},{"key":"e_1_2_1_110_1","doi-asserted-by":"crossref","unstructured":"Hanchen Wang Ying Zhang Lu Qin Wei Wang Wenjie Zhang and Xuemin Lin. 2022. Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching. In ICDE. 245--258.","DOI":"10.1109\/ICDE53745.2022.00023"},{"key":"e_1_2_1_111_1","doi-asserted-by":"crossref","unstructured":"Yiyuan Wang Chenghou Jin Shaowei Cai and Qingwei Lin. 2023. PathLAD: An Improved Exact Algorithm for Subgraph Isomorphism Problem. In IJCAI.","DOI":"10.24963\/ijcai.2023\/626"},{"key":"e_1_2_1_112_1","unstructured":"Bo Tang Wenzhe Hou Xiang Zhao. 2025. OptMatch: An Effcient and Generic Neural Network-assisted Subgraph Matching Approach. In ICDE."},{"key":"e_1_2_1_113_1","unstructured":"Rajesh Wunnava and Taylor Riggan. 2020. Building a customer identity graph with Amazon Neptune. https:\/\/aws.amazon.com\/blogs\/database\/building-a-customer-identity-graph-with-amazon-neptune\/. Accessed: 2025--10--25."},{"key":"e_1_2_1_114_1","doi-asserted-by":"crossref","unstructured":"Chenyang Xu and Benjamin Moseley. 2022. Learning-Augmented Algorithms for Online Steiner Tree. In AAAI. 8744--8752.","DOI":"10.1609\/aaai.v36i8.20854"},{"key":"e_1_2_1_115_1","unstructured":"Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In ICLR. OpenReview.net."},{"key":"e_1_2_1_116_1","first-page":"694","article-title":"Efficient Subgraph Matching Algorithm with Graph Neural Network","volume":"62","author":"Xue Xin","year":"2025","unstructured":"Xin Xue, Tianchen Zhu, Qingyun Sun, Haoyi Zhou, and Jianxin Li. 2025. Efficient Subgraph Matching Algorithm with Graph Neural Network. Journal of Computer Research and Development, 62, 3 (2025), 694--708.","journal-title":"Journal of Computer Research and Development"},{"key":"e_1_2_1_117_1","unstructured":"Haoran Ye Jiarui Wang Zhiguang Cao Helan Liang and Yong Li. 2023. DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization. In NeurIPS."},{"key":"e_1_2_1_118_1","doi-asserted-by":"publisher","DOI":"10.14778\/3654621.3654630"},{"key":"e_1_2_1_119_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2402.14367"},{"key":"e_1_2_1_120_1","unstructured":"Rex Ying Zhaoyu Lou Jiaxuan You Chengtao Wen Arquimedes Canedo and Jure Leskovec. 2020. Neural subgraph matching. arXiv preprint arXiv:2007.03092."},{"key":"e_1_2_1_121_1","volume-title":"Rex Ying, and Jure Leskovec.","author":"You Jiaxuan","year":"2021","unstructured":"Jiaxuan You, Jonathan Michael Gomes Selman, Rex Ying, and Jure Leskovec. 2021. Identity-aware Graph Neural Networks. In AAAI. 10737--10745."},{"key":"e_1_2_1_122_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009122115"},{"key":"e_1_2_1_123_1","volume-title":"Puay Siew Tan, and Chi Xu","author":"Zhang Cong","year":"2020","unstructured":"Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu. 2020. Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning. In NeurIPS."},{"key":"e_1_2_1_124_1","volume-title":"Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems 36","author":"Zhang Dinghuai","year":"2023","unstructured":"Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. 2023. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems 36 (2023), 11952--11969."},{"key":"e_1_2_1_125_1","doi-asserted-by":"crossref","unstructured":"Lizhi Zhang Zhiquan Lai Shengwei Li Yu Tang Feng Liu and Dongsheng Li. 2021. 2PGraph: Accelerating GNN Training over Large Graphs on GPU Clusters. In CLUSTER. 103--113.","DOI":"10.1109\/Cluster48925.2021.00036"},{"key":"e_1_2_1_126_1","first-page":"1185","article-title":"SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs","volume":"3","author":"Zhang Shijie","year":"2010","unstructured":"Shijie Zhang, Jiong Yang, and Wei Jin. 2010. SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs. PVLDB 3, 1 (2010), 1185--1194.","journal-title":"PVLDB"},{"key":"e_1_2_1_127_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611483"},{"key":"e_1_2_1_128_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009122115.002"},{"key":"e_1_2_1_129_1","volume-title":"Hao Zhang, Qiyan Li, and Yu Rong.","author":"Zhao Kangfei","year":"2021","unstructured":"Kangfei Zhao, Jeffrey Xu Yu, Hao Zhang, Qiyan Li, and Yu Rong. 2021. A Learned Sketch for Subgraph Counting. In SIGMOD. 2142--2155."},{"key":"e_1_2_1_130_1","first-page":"247","article-title":"Approximate Subgraph Matching Query over Large Graph","volume":"9784","author":"Zhao Yu","year":"2016","unstructured":"Yu Zhao, Chunhong Zhang, Tingting Sun, Yang Ji, Zheng Hu, and Xiaofeng Qiu. 2016. Approximate Subgraph Matching Query over Large Graph. In BigCom, Vol. 9784. 247--256.","journal-title":"BigCom"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786648","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:00:40Z","timestamp":1775592040000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786648"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":130,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786648"],"URL":"https:\/\/doi.org\/10.1145\/3786648","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}