{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:45:02Z","timestamp":1777614302845,"version":"3.51.4"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p>\n            Given a graph\n            <jats:italic>G<\/jats:italic>\n            , a motif (e.g., 3-node clique) is a fundamental building block for\n            <jats:italic>G.<\/jats:italic>\n            Recently, motif-based graph analysis has attracted much attention due to its efficacy in tasks such as clustering, ranking, and link prediction. These tasks require Network Motif Discovery (NMD) at the early stage to identify the motifs of\n            <jats:italic>G.<\/jats:italic>\n            However, existing NMD solutions have two drawbacks: (1) Lack of theoretical guarantees on the quality of the samples generated using the existing methods, and (2) inefficient algorithms, which are not scalable for large graphs. These limitations hinder the exploration of motifs for analyzing large graphs. To address the above issues, we propose a novel solution named MOSER (\n            <jats:bold>MO<\/jats:bold>\n            tif Discovery using\n            <jats:bold>SER<\/jats:bold>\n            ial Test). This novel NMD framework leverages a significance testing method known as the serial test, which differs from the existing solutions. We further propose two fast incremental subgraph counting algorithms, allowing MOSER to scale to larger graphs than ever possible before. Extensive experimental results show that using MOSER can improve the state-of-the-art up to 5 orders of magnitude in efficiency and that the motifs found by MOSER facilitate downstream tasks such as link prediction.\n          <\/jats:p>","DOI":"10.14778\/3632093.3632118","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:26:31Z","timestamp":1705749991000},"page":"591-603","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["MOSER: Scalable Network Motif Discovery Using Serial Test"],"prefix":"10.14778","volume":"17","author":[{"given":"Mohammad Matin","family":"Najafi","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}]},{"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}]},{"given":"Xiaodong","family":"Li","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia, Vancouver, Canada"}]}],"member":"320","published-online":{"date-parts":[[2024,1,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/github.com\/momatinaj\/moser\/blob\/main\/moser\/full_version.pdf."},{"key":"e_1_2_1_2_1","volume-title":"Gianmarco De Francisci Morales, and Ashraf Aboulnaga. Link prediction via higher-order motif features","author":"Abuoda Ghadeer","year":"2019","unstructured":"Ghadeer Abuoda, Gianmarco De Francisci Morales, and Ashraf Aboulnaga. Link prediction via higher-order motif features, 2019."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings 35th Annual Symposium on Foundations of CS. IEEE Comput. Soc. Press.","author":"Aldous D.","unstructured":"D. Aldous and U. Vazirani. \"go with the winners\" algorithms. In Proceedings 35th Annual Symposium on Foundations of CS. IEEE Comput. Soc. Press."},{"issue":"1","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/s00283-018-9839-x","article-title":"Markov chains and mixing times (second edition) by david a. levin and yuval peres","volume":"41","author":"Aldous David","year":"2018","unstructured":"David Aldous. Markov chains and mixing times (second edition) by david a. levin and yuval peres. The Mathematical Intelligencer, 41(1):90--91, 11 2018.","journal-title":"The Mathematical Intelligencer"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_7_1","volume-title":"Emergence of scaling in random networks. science, 286(5439):509--512","author":"Barabasi Albert-Laszlo","year":"1999","unstructured":"Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. science, 286(5439):509--512, 1999."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"issue":"4","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1093\/biomet\/76.4.633","article-title":"Generalized monte carlo significance tests","volume":"76","author":"JULIAN","year":"1989","unstructured":"JULIAN BESAG and PETER CLIFFORD. Generalized monte carlo significance tests. Biometrika, 76(4):633--642, 1989.","journal-title":"Biometrika"},{"key":"e_1_2_1_10_1","first-page":"106","volume-title":"Nemofinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs","author":"Chen Jin","year":"2006","unstructured":"Jin Chen, Wynne Hsu, Mong Lee, and See-Kiong Ng. Nemofinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs. volume 2006, pages 106--115, 01 2006."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3552490.3552508"},{"issue":"1","key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1080\/2330443X.2020.1806763","article-title":"Separating effect from significance in markov chain tests","volume":"7","author":"Chikina Maria","year":"2020","unstructured":"Maria Chikina, Alan Frieze, et al. Separating effect from significance in markov chain tests. Statistics and Public Policy, 7(1):101--114, 2020.","journal-title":"Statistics and Public Policy"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1617540114"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB)","author":"Fang Yixiang","year":"2017","unstructured":"Yixiang Fang, CK Cheng, S Luo, J Hu, and X Li. Effective community search over large spatial graphs. Proceedings of the VLDB Endowment (PVLDB), 2017."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71681-5_7"},{"key":"e_1_2_1_17_1","first-page":"64","volume-title":"Proceedings of the 2022 SIAM International Conference on Data Mining (SDM)","author":"Han Xiaolin","year":"2022","unstructured":"Xiaolin Han, Reynold Cheng, Tobias Grubenmann, Silviu Maniu, Chenhao Ma, and Xiaodong Li. Leveraging contextual graphs for stochastic weight completion in sparse road networks. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM), pages 64--72. SIAM, 2022."},{"key":"e_1_2_1_18_1","first-page":"1866","volume-title":"2020 IEEE ICDE","author":"Han Xiaolin","year":"2020","unstructured":"Xiaolin Han, Tobias Grubenmann, Reynold Cheng, Sze Chun Wong, Xiaodong Li, and Wenya Sun. Traffic incident detection: A trajectory-based approach. In 2020 IEEE ICDE, pages 1866--1869. IEEE, 2020."},{"key":"e_1_2_1_19_1","volume-title":"Graph isomorphisms in quasi-polynomial time","author":"Helfgott Harald Andr\u00e9s","year":"2017","unstructured":"Harald Andr\u00e9s Helfgott, Jitendra Bajpai, and Daniele Dona. Graph isomorphisms in quasi-polynomial time, 2017."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/978-981-10-3770-2_52","volume-title":"Advances in Computer and Computational Sciences","author":"Sarika Jain Himanshu","year":"2017","unstructured":"Himanshu and Sarika Jain. Impact of memory space optimization technique on fast network motif search algorithm. In Advances in Computer and Computational Sciences, pages 559--567. Springer Singapore, 2017."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_23_1","volume-title":"Simple markov-chain algorithms for generating bipartite graphs and tournaments. 6","author":"Kannan R","year":"1997","unstructured":"R Kannan, S Vempala, and P Tetali. Simple markov-chain algorithms for generating bipartite graphs and tournaments. 6 1997."},{"issue":"1","key":"e_1_2_1_24_1","first-page":"1","article-title":"a new algorithm for finding network motifs","volume":"10","author":"Moghadam Kashani Zahra Razaghi","year":"2009","unstructured":"Zahra Razaghi Moghadam Kashani, Hayedeh Ahrabian, Elahe Elahi, Abbas Nowzari-Dalini, Elnaz Saberi Ansari, Sahar Asadi, Shahin Mohammadi, Falk Schreiber, and Ali Masoudi-Nejad. Kavosh: a new algorithm for finding network motifs. BMC bioinformatics, 10(1):1--12, 2009.","journal-title":"BMC bioinformatics"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth163"},{"issue":"7","key":"e_1_2_1_26_1","first-page":"1","article-title":"Quatexelero: An accelerated exact network motif detection algorithm","volume":"8","author":"Khakabimamaghani Sahand","year":"2013","unstructured":"Sahand Khakabimamaghani, Iman Sharafuddin, et al. Quatexelero: An accelerated exact network motif detection algorithm. PLOS ONE, 8(7):1--15, 07 2013.","journal-title":"PLOS ONE"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_1_28_1","first-page":"377","volume-title":"2019 20th IEEE International Conference on Mobile Data Management (MDM)","author":"Durs Xiaodong Li.","year":"2019","unstructured":"Xiaodong Li. Durs: A distributed method for k-nearest neighbor search on uncertain graphs. In 2019 20th IEEE International Conference on Mobile Data Management (MDM), pages 377--378. IEEE, 2019."},{"key":"e_1_2_1_30_1","volume-title":"PVLDB","author":"Li Xiaodong","year":"2021","unstructured":"Xiaodong Li, Reynold Cheng, Kevin Chang, Caihua Shan, Chenhao Ma, and Hongtai Cao. On analyzing graphs with motif-paths. PVLDB, 2021."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 21st International Conference on Extending Database Technology (EDBT)","author":"Li Xiaodong","year":"2018","unstructured":"Xiaodong Li, Reynold Cheng, Yixiang Fang, Jiafeng Hu, and Silviu Maniu. Scalable evaluation of k-nn queries on large uncertain graphs. In Proceedings of the 21st International Conference on Extending Database Technology (EDBT), 2018."},{"key":"e_1_2_1_32_1","first-page":"3433","volume-title":"ACM CIKM 2020","author":"Li Xiaodong","year":"2020","unstructured":"Xiaodong Li, Reynold Cheng, Matin Najafi, Kevin Chen-Chuan Chang, Xiaolin Han, and Hongtai Cao. M-Cypher: A GQL framework supporting motifs. In ACM CIKM 2020, pages 3433--3436. ACM, 2020."},{"issue":"3","key":"e_1_2_1_33_1","first-page":"513","article-title":"Network motif discovery: A gpu approach","volume":"29","author":"Lin Wenqing","year":"2017","unstructured":"Wenqing Lin, Xiaokui Xiao, Xing Xie, and Xiao-Li Li. Network motif discovery: A gpu approach. IEEE TKDE, 29(3):513--528, March 2017.","journal-title":"IEEE TKDE"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_1_35_1","first-page":"1","volume-title":"The VLDB Journal","author":"Ma Chenhao","year":"2023","unstructured":"Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks VS Lakshmanan, Xiaolin Han, and Xiaodong Li. Accelerating directed densest subgraph queries with software and hardware approaches. The VLDB Journal, pages 1--24, 2023."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2014.2321150"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_38_1","volume-title":"On the uniform generation of random graphs with prescribed degree sequences. arXiv: Statistical Mechanics","author":"Milo R.","year":"2003","unstructured":"R. Milo, N. Kashtan, S. Itzkovitz, M. Newman, and U. Alon. On the uniform generation of random graphs with prescribed degree sequences. arXiv: Statistical Mechanics, 2003."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_40_1","volume-title":"March","author":"Molloy Michael","year":"1995","unstructured":"Michael Molloy and Bruce Reed. A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2--3):161--180, March 1995."},{"key":"e_1_2_1_41_1","volume-title":"Moda: an efficient algorithm for network motif discovery in biological networks. Genes & genetic systems, 84(5):385--395","author":"Omidi Saeed","year":"2009","unstructured":"Saeed Omidi, Falk Schreiber, and Ali Masoudi-Nejad. Moda: an efficient algorithm for network motif discovery in biological networks. Genes & genetic systems, 84(5):385--395, 2009."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-syb.2020.0004"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01449896"},{"key":"e_1_2_1_44_1","volume-title":"Escape: Efficiently counting all 5-vertex subgraphs, technical report. 10","author":"Pinar Ali","year":"2016","unstructured":"Ali Pinar, C. Seshadhri, and V. Vishal. Escape: Efficiently counting all 5-vertex subgraphs, technical report. 10 2016."},{"issue":"6295","key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1126\/science.aah3449","article-title":"Network analytics in the age of big data","volume":"353","author":"Pr\u017eulj Nata\u0161a","year":"2016","unstructured":"Nata\u0161a Pr\u017eulj and No\u00ebl Malod-Dognin. Network analytics in the age of big data. Science, 353(6295):123--124, 2016.","journal-title":"Science"},{"issue":"2","key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1093\/comnet\/cnu041","article-title":"A stopping criterion for markov chains when generating independent random graphs","volume":"3","author":"Ray J.","year":"2014","unstructured":"J. Ray, A. Pinar, and C. Seshadhri. A stopping criterion for markov chains when generating independent random graphs. Journal of Complex Networks, 3(2):204--220, December 2014.","journal-title":"Journal of Complex Networks"},{"key":"e_1_2_1_47_1","volume-title":"A survey on subgraph counting: Concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Surv., 54(2), mar","author":"Ribeiro Pedro","year":"2021","unstructured":"Pedro Ribeiro, Pedro Paredes, Miguel E. P. Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: Concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Surv., 54(2), mar 2021."},{"key":"e_1_2_1_48_1","first-page":"1559","volume-title":"G-tries: An efficient data structure for discovering network motifs","author":"Ribeiro Pedro","year":"2010","unstructured":"Pedro Ribeiro and Fernando Silva. G-tries: An efficient data structure for discovering network motifs. pages 1559--1566, 01 2010."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.08.007"},{"key":"e_1_2_1_50_1","volume-title":"AAAI","author":"Ryan","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analvtics and visualization. In AAAI, 2015."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366424.3382688"},{"key":"e_1_2_1_52_1","first-page":"4085","volume-title":"Proceedings of the 30th ACM CIKM","author":"Rossi Ryan A","year":"2021","unstructured":"Ryan A Rossi, Anup Rao, Sungchul Kim, Eunyee Koh, et al. From closing triangles to higher-order motif closures for better unsupervised online link prediction. In Proceedings of the 30th ACM CIKM, pages 4085--4093, 2021."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti556"},{"key":"e_1_2_1_54_1","first-page":"12","article-title":"A study of the edge-switching markov-chain method for the generation of random graphs","author":"Stauffer Alexandre","year":"2005","unstructured":"Alexandre Stauffer and Valmir Barbosa. A study of the edge-switching markov-chain method for the generation of random graphs. CORR, 12 2005.","journal-title":"CORR"},{"key":"e_1_2_1_55_1","first-page":"04","article-title":"Network motifs and their origins","volume":"15","author":"Stone Lewi","year":"2019","unstructured":"Lewi Stone, Daniel Simberloff, and Yael Artzy-Randrup. Network motifs and their origins. PLOS Computational Biology, 15, 04 2019.","journal-title":"PLOS Computational Biology"},{"key":"e_1_2_1_56_1","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1007\/BFb0091828","volume-title":"Contrained switchings in graphs","author":"Taylor R.","year":"1981","unstructured":"R. Taylor. Contrained switchings in graphs. In Lecture Notes in Mathematics, pages 314--336. Springer Berlin Heidelberg, 1981."},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 26th WWW","author":"Tsourakakis Charalampos E","year":"2017","unstructured":"Charalampos E Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. Scalable motif-aware graph clustering. In Proceedings of the 26th WWW, 2017."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.51"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2926752"},{"issue":"7","key":"e_1_2_1_60_1","doi-asserted-by":"crossref","first-page":"2100055","DOI":"10.1002\/adtp.202100055","article-title":"Drug repurposing for the treatment of covid-19: A knowledge graph approach","volume":"4","author":"Yan Vincent KC","year":"2021","unstructured":"Vincent KC Yan, Xiaodong Li, Xuxiao Ye, Min Ou, Ruibang Luo, Qingpeng Zhang, Bo Tang, et al. Drug repurposing for the treatment of covid-19: A knowledge graph approach. Advanced Therapeutics, 4(7):2100055, 2021.","journal-title":"Advanced Therapeutics"},{"issue":"100267","key":"e_1_2_1_61_1","first-page":"08","article-title":"Motif discovery in networks: A survey","volume":"37","author":"Yu Shuo","year":"2020","unstructured":"Shuo Yu, Yufan Feng, Da Zhang, Hayat Dino Bedru, Bo Xu, and Feng Xia. Motif discovery in networks: A survey. Computer Science Review, 37:100267, 08 2020.","journal-title":"Computer Science Review"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3632093.3632118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:28:18Z","timestamp":1705750098000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3632093.3632118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.14778\/3632093.3632118"],"URL":"https:\/\/doi.org\/10.14778\/3632093.3632118","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"2024-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}