{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T15:55:12Z","timestamp":1726329312035},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,8]]},"abstract":"Subgraphs are obtained by extracting a subset of vertices and a subset of edges from the associated original graphs, and many graph properties are known to be inherited by subgraphs. Subgraphs can be applied in many areas such as social networks, recommender systems, biochemistry and fraud discovery. Researchers from various communities have paid a great deal of attention to investigate numerous subgraph problems, by proposing algorithms that mainly extract important structures of a given graph. There are however some limitations that should be addressed, with regard to the efficiency, effectiveness and scalability of these traditional algorithms. As a consequence, machine learning techniques---one of the most latest trends---have recently been employed in the database community to address various subgraph problems considering that they have been shown to be beneficial in dealing with graph-related problems. We discuss learning-based approaches for four well known subgraph problems in this tutorial, namely subgraph isomorphism, maximum common subgraph, community detection and community search problems. We give a general description of each proposed model, and analyse its design and performance. To allow further investigations on relevant subgraph problems, we suggest some potential future directions in this area. We believe that this work can be used as one of the primary resources, for researchers who intend to develop learning models in solving problems that are closely related to subgraphs.<\/jats:p>","DOI":"10.14778\/3611540.3611571","type":"journal-article","created":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T15:32:37Z","timestamp":1694791957000},"page":"3864-3867","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Machine Learning for Subgraph Extraction: Methods, Applications and Challenges"],"prefix":"10.14778","volume":"16","author":[{"given":"Kai Siong","family":"Yow","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Nanyang Technological University"}]},{"given":"Ningyi","family":"Liao","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Nanyang Technological University"}]},{"given":"Siqiang","family":"Luo","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Nanyang Technological University"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Guangdong-Hong Kong-Macau Joint Laboratory and HKU Musketeers Foundation Institute of Data Science, The University of Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2023,9,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"E. Acar T. G. Kolda and D. M. Dunlavy. 2011. All-at-once optimization for coupled matrix and tensor factorizations. Preprint. arXiv:1105.34226. E. Acar T. G. Kolda and D. M. Dunlavy. 2011. All-at-once optimization for coupled matrix and tensor factorizations. Preprint. arXiv:1105.34226."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_3_1","unstructured":"Y. Bai D. Xu Y. Sun and W. Wang. 2020. GLSearch: Maximum Common Subgraph Detection via Learning to Search. In ICML. 588--598. Y. Bai D. Xu Y. Sun and W. Wang. 2020. GLSearch: Maximum Common Subgraph Detection via Learning to Search. In ICML. 588--598."},{"key":"e_1_2_1_4_1","volume-title":"Graph theory with applications","author":"Bondy J. A.","unstructured":"J. A. Bondy and U. S. R Murty . 1976. Graph theory with applications . The Macmillan Press Ltd , New York . J. A. Bondy and U. S. R Murty. 1976. Graph theory with applications. The Macmillan Press Ltd, New York."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(97)00060-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmb.2007.03.013"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447704"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975321.79"},{"key":"e_1_2_1_12_1","unstructured":"F. Harary and R. Z. Norman. 1953. Graph theory as a mathematical model in social science. University of Michigan Institute for Social Research Ann Arbor. F. Harary and R. Z. Norman. 1953. Graph theory as a mathematical model in social science. University of Michigan Institute for Social Research Ann Arbor."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1511\/2000.1.9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514070"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"Representation learning for dynamic graphs: A survey","volume":"21","author":"Kazemi S. M.","year":"2020","unstructured":"S. M. Kazemi , R. Goel , K. Jain , I. Kobyzev , A. Sethi , P. Forsyth , and P. Poupart . 2020 . Representation learning for dynamic graphs: A survey . Journal of Machine Learning Research 21 , 70 (2020), 1 -- 73 . S. M. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, P. Forsyth, and P. Poupart. 2020. Representation learning for dynamic graphs: A survey. Journal of Machine Learning Research 21, 70 (2020), 1--73.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"X. Liu H. Pan M. He Y.u Song X. Jiang and L. Shang. 2020. Neural Subgraph Isomorphism Counting. In SIGKDD. 1959--1969. X. Liu H. Pan M. He Y.u Song X. Jiang and L. Shang. 2020. Neural Subgraph Isomorphism Counting. In SIGKDD. 1959--1969.","DOI":"10.1145\/3394486.3403247"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence 34","author":"Liu Y.","year":"2020","unstructured":"Y. Liu , C. M. Li , H. Jiang , and K. He . 2020. A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems . Proceedings of the AAAI Conference on Artificial Intelligence 34 , 03 ( 2020 ), 2392--2399. Y. Liu, C. M. Li, H. Jiang, and K. He. 2020. A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems. Proceedings of the AAAI Conference on Artificial Intelligence 34, 03 (2020), 2392--2399."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"C. McCreesh P. Prosser and J. Trimble. 2017. A Partitioning Algorithm for Maximum Common Subgraph Problems. In 26th IJCAI. 712--719. C. McCreesh P. Prosser and J. Trimble. 2017. A Partitioning Algorithm for Maximum Common Subgraph Problems. In 26th IJCAI. 712--719.","DOI":"10.24963\/ijcai.2017\/99"},{"key":"e_1_2_1_20_1","unstructured":"M. Mohri A. Rostamizadeh and A. Talwalkar. 2018. Foundations of machine learning. MIT Press. M. Mohri A. Rostamizadeh and A. Talwalkar. 2018. Foundations of machine learning. MIT Press."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-021-00155-3"},{"key":"e_1_2_1_22_1","volume-title":"SAS SUGI Proceedings: Customer Intelligence.","author":"Pinheiro C. A. R.","year":"2012","unstructured":"C. A. R. Pinheiro . 2012 . Community detection to identify fraud events in telecommunications networks . In SAS SUGI Proceedings: Customer Intelligence. C. A. R. Pinheiro. 2012. Community detection to identify fraud events in telecommunications networks. In SAS SUGI Proceedings: Customer Intelligence."},{"key":"e_1_2_1_23_1","volume-title":"Approximation Ratios of Graph Neural Networks for Combinatorial Problems. In Advances in Neural Information Processing Systems","volume":"32","author":"Sato R.","unstructured":"R. Sato , M. Yamada , and H. Kashima . 2019 . Approximation Ratios of Graph Neural Networks for Combinatorial Problems. In Advances in Neural Information Processing Systems , Vol. 32 . R. Sato, M. Yamada, and H. Kashima. 2019. Approximation Ratios of Graph Neural Networks for Combinatorial Problems. In Advances in Neural Information Processing Systems, Vol. 32."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the First International Workshop on Deep Learning for Graphs (DLG '19)","author":"Shchur O.","unstructured":"O. Shchur and S. G\u00fcnnemann . 2019. Overlapping Community Detection with Graph Neural Networks . In Proceedings of the First International Workshop on Deep Learning for Graphs (DLG '19) . 1--7. O. Shchur and S. G\u00fcnnemann. 2019. Overlapping Community Detection with Graph Neural Networks. In Proceedings of the First International Workshop on Deep Learning for Graphs (DLG '19). 1--7."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"M. Sozio and A. Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In SIGKDD. 939--948. M. Sozio and A. Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In SIGKDD. 939--948.","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2021.3051021"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"H. Wang R. Hu Y. Zhang L. Qin W. Wang and W. Zhang. 2022. Neural Subgraph Counting with Wasserstein Estimator. In SIGMOD. 160--175. H. Wang R. Hu Y. Zhang L. Qin W. Wang and W. Zhang. 2022. Neural Subgraph Counting with Wasserstein Estimator. In SIGMOD. 160--175.","DOI":"10.1145\/3514221.3526163"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Sixth ACM WSDM. 587--596","author":"Yang J.","unstructured":"J. Yang and J. Leskovec . 2013. Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach . In Proceedings of the Sixth ACM WSDM. 587--596 . J. Yang and J. Leskovec. 2013. Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach. In Proceedings of the Sixth ACM WSDM. 587--596."},{"key":"e_1_2_1_29_1","unstructured":"K. S. Yow G. E. Farr and K. J. Morgan. 2018. Tutte invariants for alternating dimaps. Preprint. arXiv:1803.05539. K. S. Yow G. E. Farr and K. J. Morgan. 2018. Tutte invariants for alternating dimaps. Preprint. arXiv:1803.05539."},{"key":"e_1_2_1_30_1","unstructured":"K. S. Yow N. Liao S. Luo R. Cheng C. Ma and X. Han. 2023. A Survey on Machine Learning Solutions for Graph Pattern Extraction. Preprint. arXiv:2204.01057v3. K. S. Yow N. Liao S. Luo R. Cheng C. Ma and X. Han. 2023. A Survey on Machine Learning Solutions for Graph Pattern Extraction. Preprint. arXiv:2204.01057v3."},{"key":"e_1_2_1_31_1","unstructured":"K. S. Yow and S. Luo. 2022. Learning-Based Approaches for Graph Problems: A Survey. Preprint. arXiv:2204.01057v2. K. S. Yow and S. Luo. 2022. Learning-Based Approaches for Graph Problems: A Survey. Preprint. arXiv:2204.01057v2."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-021-02347-0"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"K. Zhao J. X. Yu H. Zhang Q. Li and Y. Rong. 2021. A Learned Sketch for Subgraph Counting. In SIGMOD. 2142--2155. K. Zhao J. X. Yu H. Zhang Q. Li and Y. Rong. 2021. A Learned Sketch for Subgraph Counting. In SIGMOD. 2142--2155.","DOI":"10.1145\/3448016.3457289"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611540.3611571","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T15:39:37Z","timestamp":1694792377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611540.3611571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":33,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.14778\/3611540.3611571"],"URL":"http:\/\/dx.doi.org\/10.14778\/3611540.3611571","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,8]]},"assertion":[{"value":"2023-09-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}