{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:50Z","timestamp":1779174890251,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"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,5,26]]},"abstract":"<jats:p>Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, and possibly inaccurate results. In this paper, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM adopts a novel task-based execution engine design to ensure high concurrency, bounded memory consumption, and effective load balancing. It also supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. Our experiments show that T-FSM is orders of magnitude faster than SOTA systems for frequent subgraph pattern mining. Our system code has been released at https:\/\/github.com\/lyuheng\/T-FSM.<\/jats:p>","DOI":"10.1145\/3588928","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":19,"title":["T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4374-8161","authenticated-orcid":false,"given":"Lyuheng","family":"Yuan","sequence":"first","affiliation":[{"name":"The University of Alabama at Birmingham, Birmingham, AL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4653-0408","authenticated-orcid":false,"given":"Da","family":"Yan","sequence":"additional","affiliation":[{"name":"The University of Alabama at Birmingham, Birmingham, AL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6390-6940","authenticated-orcid":false,"given":"Wenwen","family":"Qu","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7846-2200","authenticated-orcid":false,"given":"Saugat","family":"Adhikari","sequence":"additional","affiliation":[{"name":"The University of Alabama at Birmingham, Birmingham, AL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9853-2352","authenticated-orcid":false,"given":"Jalal","family":"Khalil","sequence":"additional","affiliation":[{"name":"The University of Alabama at Birmingham, Birmingham, AL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4594-6946","authenticated-orcid":false,"given":"Xiaoling","family":"Wang","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"716","volume-title":"Scalemine: scalable parallel frequent subgraph mining in a single large graph","author":"Ehab Abdelhamid","year":"2016","unstructured":"Ehab Abdelhamid et al. \"Scalemine: scalable parallel frequent subgraph mining in a single large graph\". In: SC. 2016, pp. 716--727."},{"key":"e_1_2_2_2_1","first-page":"858","volume-title":"PAKDD","author":"Bringmann Bj\u00f6rn","year":"2008","unstructured":"Bj\u00f6rn Bringmann and Siegfried Nijssen. \"What Is Frequent in a Single Graph?\" In: PAKDD. Vol. 5012. Lecture Notes in Computer Science. Springer, 2008, pp. 858--863."},{"key":"e_1_2_2_3_1","first-page":"1514","volume-title":"Fraction-Score: A New Support Measure for Co-location Pattern Mining","author":"Kai-Ho Chan Harry","year":"2019","unstructured":"Harry Kai-Ho Chan et al. \"Fraction-Score: A New Support Measure for Co-location Pattern Mining\". In: ICDE. IEEE, 2019, pp. 1514--1525."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITB.2009.2028234"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2324796.2324831"},{"key":"e_1_2_2_7_1","first-page":"151","volume-title":"ACM","author":"Cook Stephen A.","year":"1971","unstructured":"Stephen A. Cook. \"The Complexity of Theorem-Proving Procedures\". In: STOC. ACM, 1971, pp. 151--158."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.127"},{"key":"e_1_2_2_9_1","unstructured":"DistGraph. https:\/\/github.com\/zakimjz\/DistGraph."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_2_11_1","unstructured":"Fractal. https:\/\/github.com\/dccspeed\/fractal."},{"key":"e_1_2_2_12_1","unstructured":"GraMi. https:\/\/github.com\/ehab-abdelhamid\/GraMi."},{"key":"e_1_2_2_13_1","unstructured":"GSE1730. https:\/\/www.ncbi.nlm.nih.gov\/geo\/query\/acc.cgi?acc=GSE1730."},{"key":"e_1_2_2_14_1","first-page":"1429","article-title":"Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together","author":"Myoungji Han","year":"2019","unstructured":"Myoungji Han et al. \"Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together\". In: SIGMOD. ACM, 2019, pp. 1429--1446.","journal-title":"SIGMOD. ACM"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_2_16_1","first-page":"1","article-title":"Peregrine: a pattern-aware graph mining system","volume":"13","author":"Jamshidi Kasra","year":"2020","unstructured":"Kasra Jamshidi, Rakesh Mahadasa, and Keval Vora. \"Peregrine: a pattern-aware graph mining system\". In: EuroSys. ACM, 2020, 13:1--13:16.","journal-title":"EuroSys. ACM"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2004.12.039"},{"key":"e_1_2_2_19_1","unstructured":"Online Appendix. https:\/\/github.com\/lyuheng\/T-FSM\/blob\/main\/appendix.pdf."},{"key":"e_1_2_2_20_1","unstructured":"Pangolin. https:\/\/github.com\/chenxuhao\/GraphMiner."},{"key":"e_1_2_2_21_1","unstructured":"Peregrine. https:\/\/github.com\/pdclab\/peregrine."},{"key":"e_1_2_2_22_1","first-page":"1357","volume-title":"Fractal: A General-Purpose Graph Pattern Mining System","author":"dos Santos Dias Vinicius Vitor","year":"2019","unstructured":"Vinicius Vitor dos Santos Dias et al. \"Fractal: A General-Purpose Graph Pattern Mining System\". In: SIGMOD. ACM, 2019, pp. 1357--1374."},{"key":"e_1_2_2_23_1","unstructured":"ScaleMine. https:\/\/github.com\/ehab-abdelhamid\/ScaleMine."},{"key":"e_1_2_2_24_1","first-page":"213","volume-title":"ECML PKDD.","author":"Madeleine Seeland","year":"2010","unstructured":"Madeleine Seeland et al. \"Online Structural Graph Clustering Using Frequent Subgraph Mining\". In: ECML PKDD. Vol. 6323. Lecture Notes in Computer Science. Springer, 2010, pp. 213--228."},{"key":"e_1_2_2_25_1","first-page":"1083","volume-title":"An In-depth Study","author":"Sun Shixuan","year":"2020","unstructured":"Shixuan Sun and Qiong Luo. \"In-Memory Subgraph Matching: An In-depth Study\". In: SIGMOD. 2020, pp. 1083--1098."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0466-x"},{"key":"e_1_2_2_28_1","first-page":"425","volume-title":"Teixeira et al. \"Arabesque: a system for distributed graph mining","author":"Carlos H.","year":"2015","unstructured":"Carlos H. C. Teixeira et al. \"Arabesque: a system for distributed graph mining\". In: SOSP. ACM, 2015, pp. 425--440."},{"key":"e_1_2_2_29_1","unstructured":"Twitter. https:\/\/academictorrents.com\/details\/2399616d26eeb4ae9ac3d05c7fdd98958299efa9."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_2_31_1","first-page":"763","volume-title":"RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on a Single Machine","author":"Kai Wang","year":"2018","unstructured":"Kai Wang et al. \"RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on a Single Machine\". In: OSDI. USENIX Association, 2018, pp. 763--782."},{"key":"e_1_2_2_32_1","first-page":"1","article-title":"\"cuTS: scaling subgraph isomorphism on distributed multi-GPU systems using trie based data structure","volume":"69","author":"Lizhi Xiang","year":"2021","unstructured":"Lizhi Xiang et al. \"cuTS: scaling subgraph isomorphism on distributed multi-GPU systems using trie based data structure\". In: SC. ACM, 2021, 69:1--69:14.","journal-title":"SC. ACM"},{"key":"e_1_2_2_33_1","first-page":"1369","volume-title":"G-thinker: A Distributed Framework for Mining Subgraphs in a Big Graph","author":"Da Yan","year":"2020","unstructured":"Da Yan et al. \"G-thinker: A Distributed Framework for Mining Subgraphs in a Big Graph\". In: ICDE. IEEE, 2020, pp. 1369--1380."},{"key":"e_1_2_2_34_1","first-page":"1938","volume-title":"PrefixFPM: A Parallel Framework for General-Purpose Frequent Pattern Mining","author":"Da Yan","year":"2020","unstructured":"Da Yan et al. \"PrefixFPM: A Parallel Framework for General-Purpose Frequent Pattern Mining\". In: ICDE. IEEE, 2020, pp. 1938--1941."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00687-0"},{"key":"e_1_2_2_36_1","first-page":"721","volume-title":"Graph-Based Substructure Pattern Mining","author":"Yan Xifeng","year":"2002","unstructured":"Xifeng Yan and Jiawei Han. \"gSpan: Graph-Based Substructure Pattern Mining\". In: ICDM. 2002, pp. 721--724."},{"key":"e_1_2_2_37_1","first-page":"335","volume-title":"A Frequent Structure-based Approach","author":"Yan Xifeng","year":"2004","unstructured":"Xifeng Yan, Philip S. Yu, and Jiawei Han. \"Graph Indexing: A Frequent Structure-based Approach\". In: SIGMOD. ACM, 2004, pp. 335--346."},{"key":"e_1_2_2_38_1","first-page":"139","volume-title":"Modeling Transcriptional Regulation","author":"Zongliang Yue","year":"2021","unstructured":"Zongliang Yue et al. \"Biological Network Mining\". In: Modeling Transcriptional Regulation. Springer, 2021, pp. 139--151."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687734"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588928","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588928","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588928"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588928"],"URL":"https:\/\/doi.org\/10.1145\/3588928","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}