{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T15:42:55Z","timestamp":1758123775760,"version":"3.44.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:p>Subgraph counting is a fundamental problem in graph analytics with broad applications, yet remains computationally intractable due to its #P-hardness. To address this, numerous approximate solutions have been proposed, though they often suffer from limited efficiency and accuracy. In this paper, we introduce FlowSC, a novel approach that achieves both high accuracy and efficiency in subgraph counting. Our method starts with an enhanced candidate filtering algorithm, which significantly improves the pruning capability of bipartite graph-based techniques with minimal overhead. Building on this, we propose a bottom-up flow-learning model based on a new Graph Neural Network (GNN) architecture. By employing a carefully designed message-passing mechanism, the model explicitly controls the direction, range, and iterations of information flow, enabling a simulation of the candidate tree-based counting process. This mechanism is further empowered by a customized message aggregation technique, alongside a pretraining strategy that facilitates model training. Extensive experiments show that FlowSC can achieve up to 4 orders of magnitude improvement in accuracy and 3\u00d7 improvement in efficiency over the baselines across datasets, while scaling to billion-edge graphs.<\/jats:p>","DOI":"10.14778\/3742728.3742758","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:32:53Z","timestamp":1756906373000},"page":"2695-2708","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach"],"prefix":"10.14778","volume":"18","author":[{"given":"Qiuyu","family":"Guo","sequence":"first","affiliation":[{"name":"Guangzhou University, University of New South Wales"}]},{"given":"Jianye","family":"Yang","sequence":"additional","affiliation":[{"name":"Guangzhou University, PengCheng Laboratory"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales"}]},{"given":"Hanchen","family":"Wang","sequence":"additional","affiliation":[{"name":"University of New South Wales"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"International Conference on machine learning. PMLR, 21\u201329","author":"Abu-El-Haija Sami","year":"2019","unstructured":"Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on machine learning. PMLR, 21\u201329."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of SIGMOD. 1421\u20131432","author":"Angles Renzo","year":"2018","unstructured":"Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Peter Boncz, George Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan Sequeda, et al. 2018. G-CORE: A core for future graph query languages. In Proceedings of SIGMOD. 1421\u20131432."},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Gup: Fast subgraph matching by guard-based pruning","volume":"1","author":"Arai Junya","year":"2023","unstructured":"Junya Arai, Yasuhiro Fujiwara, and Makoto Onizuka. 2023. Gup: Fast subgraph matching by guard-based pruning. Proceedings of SIGMOD 1, 2 (2023), 1\u201326.","journal-title":"Proceedings of SIGMOD"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of SIGMOD. 1371\u20131382","author":"Aref Molham","year":"2015","unstructured":"Molham Aref, Balder Ten Cate, Todd J Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L Veldhuizen, and Geoffrey Washburn. 2015. Design and implementation of the LogicBlox system. In Proceedings of SIGMOD. 1371\u20131382."},{"key":"e_1_2_1_5_1","volume-title":"Yoshua. In International Conference on Learning Representations.","author":"Graph","year":"2018","unstructured":"Graph attention networks. 2018. Veli\u010dkovi\u0107, Petar and Cucurull, Guillem and Casanova, Arantxa and Romero, Adriana and Lio, Pietro and Bengio, Yoshua. In International Conference on Learning Representations."},{"volume-title":"Proceedings of SIGMOD. 1447\u20131462","author":"Bhattarai Bibek","key":"e_1_2_1_6_1","unstructured":"Bibek Bhattarai, Hang Liu, and H. Howie Huang. 2019. CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching. In Proceedings of SIGMOD. 1447\u20131462."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of SIGMOD. 1199\u20131214","author":"Bi Fei","year":"2016","unstructured":"Fei Bi, Lijun Chang, Xuemin Lin, Lu Qin, and Wenjie Zhang. 2016. Efficient Subgraph Matching by Postponing Cartesian Products. In Proceedings of SIGMOD. 1199\u20131214."},{"key":"e_1_2_1_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 (2013)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of VLDB. 1651\u20131663","author":"Bressan Marco","year":"2019","unstructured":"Marco Bressan, Stefano Leucci, and Alessandro Panconesi. 2019. Motivo: Fast Motif Counting via Succinct Color Coding and Adaptive Sampling. In Proceedings of VLDB. 1651\u20131663."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of SIGMOD. 18\u201335","author":"Cai Walter","year":"2019","unstructured":"Walter Cai, Magdalena Balazinska, and Dan Suciu. 2019. Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities. In Proceedings of SIGMOD. 18\u201335."},{"volume-title":"Data management of protein interaction networks","author":"Cannataro Mario","key":"e_1_2_1_11_1","unstructured":"Mario Cannataro and Pietro H Guzzi. 2012. Data management of protein interaction networks. Vol. 17."},{"key":"e_1_2_1_12_1","volume-title":"Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247","author":"Chen Jie","year":"2018","unstructured":"Jie Chen, Tengfei Ma, and Cao Xiao. 2018. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247 (2018)."},{"volume-title":"Proceedings of ICDM. 71\u201380","author":"Chen Xiaowei","key":"e_1_2_1_13_1","unstructured":"Xiaowei Chen and John C. S. Lui. 2016. Mining Graphlet Counts in Online Social Networks. In Proceedings of ICDM. 71\u201380."},{"key":"e_1_2_1_14_1","volume-title":"Can graph neural networks count substructures? Advances in neural information processing systems 33","author":"Chen Zhengdao","year":"2020","unstructured":"Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. 2020. Can graph neural networks count substructures? Advances in neural information processing systems 33 (2020), 10383\u201310395."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","article-title":"A (sub)graph isomorphism algorithm for matching large graphs","volume":"26","author":"Cordella L.P.","year":"2004","unstructured":"L.P. Cordella, P. Foggia, C. Sansone, and M. Vento. 2004. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 10 (2004), 1367\u20131372.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_1_16_1","volume-title":"International Conference on Machine Learning.","author":"Dwivedi Vijay Prakash","year":"2021","unstructured":"Vijay Prakash Dwivedi and Xavier Bresson. 2021. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of ICDT. 8\u201321","author":"Fan Wenfei","year":"2012","unstructured":"Wenfei Fan. 2012. Graph Pattern Matching Revised for Social Network Analysis. In Proceedings of ICDT. 8\u201321."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal Flow Through a Network","volume":"8","author":"Ford L. R.","year":"1956","unstructured":"L. R. Ford and D. R. Fulkerson. 1956. Maximal Flow Through a Network. Canadian Journal of Mathematics 8 (1956), 399\u2013404.","journal-title":"Canadian Journal of Mathematics"},{"key":"e_1_2_1_19_1","volume-title":"Inductive representation learning on large graphs. Advances in neural information processing systems 30","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of SIGMOD. 1429\u20131446","author":"Han Myoungji","year":"2019","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 Proceedings of SIGMOD. 1429\u20131446."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of SIGMOD. 337\u2013348","author":"Han Wook-Shin","year":"2013","unstructured":"Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. 2013. Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In Proceedings of SIGMOD. 337\u2013348."},{"key":"e_1_2_1_22_1","volume-title":"International Conference on Web Information Systems Engineering. Springer, 235\u2013244","author":"Harris Stephen","year":"2005","unstructured":"Stephen Harris and Nigel Shadbolt. 2005. SPARQL query processing with conventional relational database systems. In International Conference on Web Information Systems Engineering. Springer, 235\u2013244."},{"key":"e_1_2_1_23_1","volume-title":"Singh","author":"He Huahai","year":"2008","unstructured":"Huahai He and Ambuj K. Singh. 2008. Graphs-at-a-Time: Query Language and Access Methods for Graph Databases. In Proceedings of SIGMOD. 405\u2013418."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1093\/bioinformatics\/btt717","article-title":"A combinatorial approach to graphlet counting","volume":"30","author":"Ho\u010devar Toma\u017e","year":"2014","unstructured":"Toma\u017e Ho\u010devar and Janez Dem\u0161ar. 2014. A combinatorial approach to graphlet counting. Bioinformatics 30, 4 (2014), 559\u2013565.","journal-title":"Bioinformatics"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"e0171428","DOI":"10.1371\/journal.pone.0171428","article-title":"Combinatorial algorithm for counting small induced graphs and orbits","volume":"12","author":"Ho\u010devar Toma\u017e","year":"2017","unstructured":"Toma\u017e Ho\u010devar and Janez Dem\u0161ar. 2017. Combinatorial algorithm for counting small induced graphs and orbits. PloS one 12, 2 (2017), e0171428.","journal-title":"PloS one"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of ICDE. IEEE, 2625\u20132638","author":"Hou Wenzhe","year":"2024","unstructured":"Wenzhe Hou, Xiang Zhao, and Bo Tang. 2024. LearnSC: An Efficient and Unified Learning-Based Framework for Subgraph Counting Problem. In Proceedings of ICDE. IEEE, 2625\u20132638."},{"key":"e_1_2_1_27_1","volume-title":"Counting Graph Substructures with Graph Neural Networks. In International Conference on Learning Representations.","author":"Kanatsoulis Charilaos","year":"2024","unstructured":"Charilaos Kanatsoulis and Alejandro Ribeiro. 2024. Counting Graph Substructures with Graph Neural Networks. In International Conference on Learning Representations."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of SIGMOD. 925\u2013937","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 Proceedings of SIGMOD. 925\u2013937."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of SIGMOD. 964\u2013976","author":"Kim Kyoungmin","year":"2021","unstructured":"Kyoungmin Kim, Hyeonji Kim, George Fletcher, and Wook Shin Han. 2021. Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation. In Proceedings of SIGMOD. 964\u2013976."},{"key":"e_1_2_1_30_1","volume-title":"International Conference on Learning Representations.","author":"Kipf Thomas N","year":"2017","unstructured":"Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations."},{"key":"e_1_2_1_31_1","volume-title":"Structure-Aware Transformer for Graph Representation Learning. In International Conference on Learning Representations.","author":"Kreuzer Dexiong","year":"2023","unstructured":"Dexiong Kreuzer, Dominique Beaini, Will Hamilton, Genevieve Letarte, and Prudencio Tossou. 2023. Structure-Aware Transformer for Graph Representation Learning. In International Conference on Learning Representations."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Conference on World Wide Web. 591\u2013600","author":"Kwak Haewoon","year":"2010","unstructured":"Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In Proceedings of the International Conference on World Wide Web. 591\u2013600."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"974","DOI":"10.14778\/2794367.2794368","article-title":"Scalable subgraph enumeration in mapreduce","volume":"8","author":"Lai Longbin","year":"2015","unstructured":"Longbin Lai, Lu Qin, Xuemin Lin, and Lijun Chang. 2015. Scalable subgraph enumeration in mapreduce. Proceedings of VLDB 8, 10 (2015), 974\u2013985.","journal-title":"Proceedings of VLDB"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.14778\/3021924.3021937","article-title":"Scalable distributed subgraph enumeration","volume":"10","author":"Lai Longbin","year":"2016","unstructured":"Longbin Lai, Lu Qin, Xuemin Lin, Ying Zhang, Lijun Chang, and Shiyu Yang. 2016. Scalable distributed subgraph enumeration. Proceedings of VLDB 10, 3 (2016), 217\u2013228.","journal-title":"Proceedings of VLDB"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of SIGMOD. 615\u2013629","author":"Li Feifei","year":"2016","unstructured":"Feifei Li, Bin Wu, Ke Yi, and Zhuoyue Zhao. 2016. Wander Join: Online Aggregation via Random Walks. In Proceedings of SIGMOD. 615\u2013629."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of SIGKDD. 1959\u20131969","author":"Liu Xin","year":"2020","unstructured":"Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. 2020. Neural subgraph isomorphism counting. In Proceedings of SIGKDD. 1959\u20131969."},{"key":"e_1_2_1_37_1","volume-title":"Towards Subgraph Isomorphism Counting with Graph Kernels. arXiv preprint arXiv:2405.07497","author":"Liu Xin","year":"2024","unstructured":"Xin Liu, Weiqi Wang, Jiaxin Bai, and Yangqiu Song. 2024. Towards Subgraph Isomorphism Counting with Graph Kernels. arXiv preprint arXiv:2405.07497 (2024)."},{"key":"e_1_2_1_38_1","volume-title":"International Conference on Machine Learning. PMLR, 22454\u201322472","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 International Conference on Machine Learning. PMLR, 22454\u201322472."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of ICDE","author":"Ma Ziyi","year":"2024","unstructured":"Ziyi Ma, Jianye Yang, Xu Zhou, Guoqing Xiao, Jianhua Wang, Liang Yang, Kenli Li, and Xuemin Lin. 2024. Efficient Multi-Query Oriented Continuous Subgraph Matching. Proceedings of ICDE (2024), 3230\u20133243."},{"key":"e_1_2_1_40_1","volume-title":"International Conference on Distributed Computing Systems Workshops. IEEE, 92\u201398","author":"Marcus Dror","year":"2010","unstructured":"Dror Marcus and Yuval Shavitt. 2010. Efficient counting of network motifs. In International Conference on Distributed Computing Systems Workshops. IEEE, 92\u201398."},{"key":"e_1_2_1_41_1","volume-title":"31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5\u20138","volume":"25","author":"Marx D\u00e1niel","year":"2014","unstructured":"D\u00e1niel Marx and Michal Pilipczuk. 2014. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5\u20138, 2014, Lyon, France (LIPIcs), Vol. 25. 542\u2013553."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of ICDE. 984\u2013994","author":"Neumann Thomas","year":"2011","unstructured":"Thomas Neumann and Guido Moerkotte. 2011. Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins. In Proceedings of ICDE. 984\u2013994."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 111\u2013124","author":"Ngo Hung Q","year":"2018","unstructured":"Hung Q Ngo. 2018. Worst-case optimal join algorithms: Techniques, results, and open problems. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 111\u2013124."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of SIGKDD. 2051\u20132059","author":"Park Himchan","year":"2018","unstructured":"Himchan Park and Min-Soo Kim. 2018. EvoGraph: An effective and efficient graph upscaling method for preserving graph properties. In Proceedings of SIGKDD. 2051\u20132059."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"974","DOI":"10.1093\/bioinformatics\/btl030","article-title":"Efficient estimation of graphlet frequency distributions in protein-protein interaction networks","volume":"22","author":"Pr\u017eulj N","year":"2006","unstructured":"N Pr\u017eulj, Derek G Corneil, and Igor Jurisica. 2006. Efficient estimation of graphlet frequency distributions in protein-protein interaction networks. Bioinformatics 22, 8 (2006), 974\u2013980.","journal-title":"Bioinformatics"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"364","DOI":"10.14778\/1453856.1453899","article-title":"Taming verification hardness: an efficient algorithm for testing subgraph isomorphism","volume":"1","author":"Shang Haichuan","year":"2008","unstructured":"Haichuan Shang, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2008. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. In Proceedings of VLDB, Vol. 1. 364\u2013375.","journal-title":"Proceedings of VLDB"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of VLDB. 1697\u20131709","author":"Shin Wonseok","year":"2024","unstructured":"Wonseok Shin, Siwoo Song, Kunsoo Park, and Wook-Shin Han. 2024. Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach. In Proceedings of VLDB. 1697\u20131709."},{"key":"e_1_2_1_48_1","volume-title":"New specifications for exponential random graph models. Sociological methodology 36, 1","author":"Snijders Tom AB","year":"2006","unstructured":"Tom AB Snijders, Philippa E Pattison, Garry L Robins, and Mark S Handcock. 2006. New specifications for exponential random graph models. Sociological methodology 36, 1 (2006), 99\u2013153."},{"volume-title":"Proceedings of WWW. 1043\u20131052","author":"Stefanoni Giorgio","key":"e_1_2_1_49_1","unstructured":"Giorgio Stefanoni, Boris Motik, and Egor V. Kostylev. 2018. Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation. In Proceedings of WWW. 1043\u20131052."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of SIGMOD. 1083\u20131098","author":"Sun Shixuan","year":"2020","unstructured":"Shixuan Sun and Qiong Luo. 2020. In-Memory Subgraph Matching: An In-depth Study. In Proceedings of SIGMOD. 1083\u20131098."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","first-page":"176","DOI":"10.14778\/3425879.3425888","article-title":"Rapid-match: 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. Rapid-match: A holistic approach to subgraph query processing. In Proceedings of VLDB, Vol. 14. 176\u2013188.","journal-title":"Proceedings of VLDB"},{"key":"e_1_2_1_52_1","volume-title":"Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:2012.03174","author":"Tahmasebi Behrooz","year":"2020","unstructured":"Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. 2020. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:2012.03174 (2020)."},{"key":"e_1_2_1_53_1","volume-title":"An Algorithm for Subgraph Isomorphism. J. ACM","author":"Ullmann J. R.","year":"1976","unstructured":"J. R. Ullmann. 1976. An Algorithm for Subgraph Isomorphism. J. ACM (1976), 31\u201342."},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1089\/cmb.2009.0029","article-title":"Graphlet kernels for prediction of functional residues in protein structures","volume":"17","author":"Vacic Vladimir","year":"2010","unstructured":"Vladimir Vacic, Lilia M Iakoucheva, Stefano Lonardi, and Predrag Radivojac. 2010. Graphlet kernels for prediction of functional residues in protein structures. Journal of Computational Biology 17, 1 (2010), 55\u201372.","journal-title":"Journal of Computational Biology"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of SIGMOD. 160\u2013175","author":"Wang Hanchen","year":"2022","unstructured":"Hanchen Wang, Rong Hu, Ying Zhang, Lu Qin, Wei Wang, and Wenjie Zhang. 2022. Neural Subgraph Counting with Wasserstein Estimator. In Proceedings of SIGMOD. 160\u2013175."},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1109\/TKDE.2023.3279920","article-title":"Neural similarity search on supergraph containment","volume":"36","author":"Wang Hanchen","year":"2023","unstructured":"Hanchen Wang, Jianke Yu, Xiaoyang Wang, Chen Chen, Wenjie Zhang, and Xuemin Lin. 2023. Neural similarity search on supergraph containment. Transactions on Knowledge and Data Engineering 36, 1 (2023), 281\u2013295.","journal-title":"Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of ICDE. IEEE, 245\u2013258","author":"Wang Hanchen","year":"2022","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 Proceedings of ICDE. IEEE, 245\u2013258."},{"key":"e_1_2_1_58_1","first-page":"1","article-title":"Neural Attributed Community Search at Billion Scale","volume":"1","author":"Wang Jianwei","year":"2024","unstructured":"Jianwei Wang, Kai Wang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2024. Neural Attributed Community Search at Billion Scale. In Proceedings of SIGMOD, Vol. 1. 1\u201325.","journal-title":"Proceedings of SIGMOD"},{"key":"e_1_2_1_59_1","volume-title":"International Conference on Learning Representations.","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations."},{"key":"e_1_2_1_60_1","volume-title":"International conference on machine learning. PMLR, 5453\u20135462","author":"Xu Keyulu","year":"2018","unstructured":"Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning. PMLR, 5453\u20135462."},{"key":"e_1_2_1_61_1","volume-title":"Efficiently counting substructures by subgraph gnns without running gnn on subgraphs. arXiv preprint arXiv:2303.10576","author":"Yan Zuoyu","year":"2023","unstructured":"Zuoyu Yan, Junru Zhou, Liangcai Gao, Zhi Tang, and Muhan Zhang. 2023. Efficiently counting substructures by subgraph gnns without running gnn on subgraphs. arXiv preprint arXiv:2303.10576 (2023)."},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","first-page":"2791","DOI":"10.14778\/3681954.3681963","article-title":"TC-Match: Fast Time-constrained Continuous Subgraph Matching","volume":"17","author":"Yang Jianye","year":"2024","unstructured":"Jianye Yang, Sheng Fang, Zhaoquan Gu, Ziyi Ma, Xuemin Lin, and Zhihong Tian. 2024. TC-Match: Fast Time-constrained Continuous Subgraph Matching. Proceedings of VLDB 17 (2024), 2791\u20132804.","journal-title":"Proceedings of VLDB"},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the SIGKDD workshop on mining data semantics. 1\u20138.","author":"Yang Jaewon","year":"2012","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In Proceedings of the SIGKDD workshop on mining data semantics. 1\u20138."},{"key":"e_1_2_1_64_1","first-page":"1","article-title":"Fast continuous subgraph matching over streaming graphs via backtracking reduction","volume":"1","author":"Yang Rongjian","year":"2023","unstructured":"Rongjian Yang, Zhijie Zhang, Weiguo Zheng, and Jeffrey Xu Yu. 2023. Fast continuous subgraph matching over streaming graphs via backtracking reduction. Proceedings of SIGMOD 1, 1 (2023), 1\u201326.","journal-title":"Proceedings of SIGMOD"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of SIGMOD. 2049\u20132062","author":"Yang Zhengyi","year":"2021","unstructured":"Zhengyi Yang, Longbin Lai, Xuemin Lin, Kongzhang Hao, and Wenjie Zhang. 2021. Huge: An efficient and scalable subgraph enumeration system. In Proceedings of SIGMOD. 2049\u20132062."},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","first-page":"1628","DOI":"10.14778\/3654621.3654630","article-title":"Efficient Exact Subgraph Matching via GNN-Based Path Dominance Embedding","volume":"17","author":"Ye Yutong","year":"2024","unstructured":"Yutong Ye, Xiang Lian, and Mingsong Chen. 2024. Efficient Exact Subgraph Matching via GNN-Based Path Dominance Embedding. Proceedings of VLDB 17, 7 (2024), 1628\u20131641.","journal-title":"Proceedings of VLDB"},{"key":"e_1_2_1_67_1","unstructured":"Chengxuan Ying Tianle Cai Shengjie Luo Shuxin Zheng Guolin Ke Di He Yanming Shen and Tie-Yan Liu. 2021. Do Transformers Really Perform Bad for Graph Representation?. In Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"37","author":"Yu Xingtong","year":"2023","unstructured":"Xingtong Yu, Zemin Liu, Yuan Fang, and Xinming Zhang. 2023. Learning to count isomorphisms with graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 4845\u20134853."},{"key":"e_1_2_1_69_1","volume-title":"Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931","author":"Zeng Hanqing","year":"2019","unstructured":"Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2019. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931 (2019)."},{"key":"e_1_2_1_70_1","first-page":"1","article-title":"A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction","volume":"2","author":"Zhang Zhijie","year":"2024","unstructured":"Zhijie Zhang, Yujie Lu, Weiguo Zheng, and Xuemin Lin. 2024. A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction. In Proceedings of SIGMOD, Vol. 2. 1\u201329.","journal-title":"Proceedings of SIGMOD"},{"key":"e_1_2_1_71_1","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1007\/s00778-023-00781-5","article-title":"Learned sketch for subgraph counting: a holistic approach","volume":"32","author":"Zhao Kangfei","year":"2023","unstructured":"Kangfei Zhao, Jeffrey Xu Yu, Qiyan Li, Hao Zhang, and Yu Rong. 2023. Learned sketch for subgraph counting: a holistic approach. The VLDB Journal 32, 5 (2023), 937\u2013962.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_72_1","volume-title":"Proceedings of SIGMOD. 2142\u20132155","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 Proceedings of SIGMOD. 2142\u20132155."},{"key":"e_1_2_1_73_1","volume-title":"Proceedings of SIGMOD. 1525\u20131539","author":"Zhao Zhuoyue","year":"2018","unstructured":"Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. 2018. Random Sampling over Joins Revisited. In Proceedings of SIGMOD. 1525\u20131539."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3742728.3742758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T13:37:12Z","timestamp":1756906632000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3742728.3742758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":73,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["10.14778\/3742728.3742758"],"URL":"https:\/\/doi.org\/10.14778\/3742728.3742758","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,4]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}