{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:31:13Z","timestamp":1761294673058,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T00:00:00Z","timestamp":1702944000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2024,2,29]]},"abstract":"<jats:p>Maximal frequent subgraph mining (MFSM) is the task of mining only maximal frequent subgraphs, i.e., subgraphs that are not a part of other frequent subgraphs. Although many intelligent systems require MFSM, MFSM is challenging compared to frequent subgraph mining (FSM), as maximal frequent subgraphs lie in the middle of graph lattice, and FSM algorithms must explore an exponential space and an NP-hard subroutine of frequency counting. Different from prior research, which primarily focused on optimal solutions, we introduce pmMine, a progressive graph neural framework designed for MFSM in a single large graph to attain an approximate solution. The framework combines isomorphic graph embedding, non-parametric partitioning, and an efficiently top-down pattern searching strategy. The critical insight that makes pmMine work is to define the concepts of rooted subgraph and isomorphic graph embedding, in which the costly isomorphism subroutine can be efficiently performed using similarity estimation in embedding space. In addition, pmMine returns the patterns identified during the mining process in a progressive manner. We validate the efficiency and effectiveness of our technique through extensive experiments on a variety of datasets spanning various domains.<\/jats:p>","DOI":"10.1145\/3630635","type":"journal-article","created":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T22:25:06Z","timestamp":1698445506000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Isomorphic Graph Embedding for Progressive Maximal Frequent Subgraph Mining"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6050-0774","authenticated-orcid":false,"given":"Thanh Toan","family":"Nguyen","sequence":"first","affiliation":[{"name":"Faculty of Information Technology, HUTECH University, Ho Chi Minh City, Viet Nam"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2586-7757","authenticated-orcid":false,"given":"Thanh Tam","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Griffith University, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4865-7127","authenticated-orcid":false,"given":"Thanh Hung","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Hanoi University of Science and Technology, Viet Nam"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1395-261X","authenticated-orcid":false,"given":"Hongzhi","family":"Yin","sequence":"additional","affiliation":[{"name":"The University of Queensland, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9709-1663","authenticated-orcid":false,"given":"Thanh Thi","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Monash University, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3099-2712","authenticated-orcid":false,"given":"Jun","family":"Jo","sequence":"additional","affiliation":[{"name":"Griffith University, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9687-1315","authenticated-orcid":false,"given":"Quoc Viet Hung","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Griffith University, Australia"}]}],"member":"320","published-online":{"date-parts":[[2023,12,19]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"716","volume-title":"SC","author":"Abdelhamid Ehab","year":"2016","unstructured":"Ehab Abdelhamid, Ibrahim Abdelaziz, Panos Kalnis, Zuhair Khayyat, and Fuad Jamour. 2016. ScaleMine: Scalable parallel frequent subgraph mining in a single large graph. In SC. 716\u2013727."},{"key":"e_1_3_2_3_2","article-title":"Extremely large minibatch SGD: Training ResNet-50 on ImageNet in 15 minutes","author":"Akiba Takuya","year":"2017","unstructured":"Takuya Akiba, Shuji Suzuki, and Keisuke Fukuda. 2017. Extremely large minibatch SGD: Training ResNet-50 on ImageNet in 15 minutes. arXiv preprint arXiv:1711.04325 (2017).","journal-title":"arXiv preprint arXiv:1711.04325"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961194"},{"issue":"9","key":"e_1_3_2_5_2","article-title":"A comprehensive survey of graph embedding: Problems, techniques, and applications","volume":"30","author":"Cai Hongyun","year":"2018","unstructured":"Hongyun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. 2018. A comprehensive survey of graph embedding: Problems, techniques, and applications. TKDE 30, 9 (2018).","journal-title":"TKDE"},{"issue":"1","key":"e_1_3_2_6_2","first-page":"1","article-title":"D-map+ interactive visual analysis and exploration of ego-centric and event-centric information diffusion patterns in social media","volume":"10","author":"Chen Siming","year":"2018","unstructured":"Siming Chen, Shuai Chen, Zhenhuang Wang, Jie Liang, Yadong Wu, and Xiaoru Yuan. 2018. D-map+ interactive visual analysis and exploration of ego-centric and event-centric information diffusion patterns in social media. ACM Transactions on Intelligent Systems and Technology (TIST) 10, 1 (2018), 1\u201326.","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BFb0059424","volume-title":"Recent Trends in Graph Theory","author":"Chinn Phyllis Zweig","year":"1971","unstructured":"Phyllis Zweig Chinn. 1971. The frequency partition of a graph. In Recent Trends in Graph Theory. 69\u201370."},{"issue":"1","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/TITB.2009.2028234","article-title":"Predicting protein function by frequent functional association pattern mining in protein interaction networks","volume":"14","author":"Cho Young-Rae","year":"2009","unstructured":"Young-Rae Cho and Aidong Zhang. 2009. Predicting protein function by frequent functional association pattern mining in protein interaction networks. IEEE Transactions on Information Technology in Biomedicine 14, 1 (2009), 30\u201336.","journal-title":"IEEE Transactions on Information Technology in Biomedicine"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447270"},{"issue":"7","key":"e_1_3_2_10_2","article-title":"GraMi: Frequent subgraph and pattern mining in a single large graph","volume":"7","author":"Elseidy Mohammed","year":"2014","unstructured":"Mohammed Elseidy, Ehab Abdelhamid, Spiros Skiadopoulos, and Panos Kalnis. 2014. GraMi: Frequent subgraph and pattern mining in a single large graph. PVLDB 7, 7 (2014).","journal-title":"PVLDB"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2700836"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2016.09.008"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2018.03.022"},{"key":"e_1_3_2_14_2","first-page":"475","volume-title":"SIGMOD","author":"Gurukar Saket","year":"2015","unstructured":"Saket Gurukar, Sayan Ranu, and Balaraman Ravindran. 2015. COMMIT: A scalable approach to mining communication motifs from dynamic networks. In SIGMOD. 475\u2013489."},{"issue":"5","key":"e_1_3_2_15_2","first-page":"5325","article-title":"Top-k socio-spatial co-engaged location selection for social users","volume":"35","author":"Haldar Nur Al Hasan","year":"2022","unstructured":"Nur Al Hasan Haldar, Jianxin Li, Mohammed Eunus Ali, Taotao Cai, Yunliang Chen, Timos Sellis, and Mark Reynolds. 2022. Top-k socio-spatial co-engaged location selection for social users. IEEE Transactions on Knowledge and Data Engineering 35, 5 (2022), 5325\u20135340.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_2_16_2","first-page":"1024","volume-title":"NIPS","author":"Hamilton Will","year":"2017","unstructured":"Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS. 1024\u20131034."},{"key":"e_1_3_2_17_2","first-page":"1231","volume-title":"KDD","author":"Henderson Keith","year":"2012","unstructured":"Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. 2012. RolX: Structural role extraction & mining in large graphs. In KDD. 1231\u20131239."},{"key":"e_1_3_2_18_2","first-page":"581","volume-title":"KDD","author":"Huan Jun","year":"2004","unstructured":"Jun Huan, Wei Wang, Jan Prins, and Jiong Yang. 2004. SPIN: Mining maximal frequent subgraphs from graph databases. In KDD. 581\u2013586."},{"key":"e_1_3_2_19_2","volume-title":"Random Graphs","author":"Janson Svante","year":"2011","unstructured":"Svante Janson, Tomasz Luczak, and Andrzej Rucinski. 2011. Random Graphs. Vol. 45. John Wiley & Sons."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3466685"},{"key":"e_1_3_2_21_2","first-page":"1","article-title":"Persistent graph stream summarization for real-time graph analytics","author":"Jia Yan","year":"2023","unstructured":"Yan Jia, Zhaoquan Gu, Zhihao Jiang, Cuiyun Gao, and Jianye Yang. 2023. Persistent graph stream summarization for real-time graph analytics. World Wide Web (2023), 1\u201321.","journal-title":"World Wide Web"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1049\/cit2.12186"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(02)00268-4"},{"key":"e_1_3_2_24_2","article-title":"Semi-supervised classification with graph convolutional networks","author":"Kipf Thomas N.","year":"2016","unstructured":"Thomas N. Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).","journal-title":"arXiv preprint arXiv:1609.02907"},{"issue":"12","key":"e_1_3_2_25_2","article-title":"Network similarity decomposition (NSD): A fast and scalable approach to network alignment","volume":"24","author":"Kollias Giorgos","year":"2011","unstructured":"Giorgos Kollias, Shahin Mohammadi, and Ananth Grama. 2011. Network similarity decomposition (NSD): A fast and scalable approach to network alignment. TKDE 24, 12 (2011).","journal-title":"TKDE"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2016.03.008"},{"key":"e_1_3_2_27_2","volume-title":"ICDM","author":"Kuramochi Michihiro","year":"2001","unstructured":"Michihiro Kuramochi and George Karypis. 2001. Frequent subgraph discovery. In ICDM."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0168344"},{"key":"e_1_3_2_30_2","volume-title":"KDD","author":"Leskovec Jure","year":"2005","unstructured":"Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In KDD."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_3_2_32_2","article-title":"Frequent pattern mining in big social graphs","author":"Li Lei","year":"2021","unstructured":"Lei Li, Ping Ding, Huanhuan Chen, and Xindong Wu. 2021. Frequent pattern mining in big social graphs. TETCI (2021).","journal-title":"TETCI"},{"key":"e_1_3_2_33_2","first-page":"661","volume-title":"KDD","author":"Li Mu","year":"2014","unstructured":"Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J. Smola. 2014. Efficient mini-batch training for stochastic optimization. In KDD. 661\u2013670."},{"issue":"1","key":"e_1_3_2_34_2","first-page":"1","article-title":"Refined-graph regularization-based nonnegative matrix factorization","volume":"9","author":"Li Xuelong","year":"2017","unstructured":"Xuelong Li, Guosheng Cui, and Yongsheng Dong. 2017. Refined-graph regularization-based nonnegative matrix factorization. ACM Transactions on Intelligent Systems and Technology (TIST) 9, 1 (2017), 1\u201321.","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2023.01.131"},{"issue":"2","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3488902","article-title":"Make more connections: Urban traffic flow forecasting with spatiotemporal adaptive gated graph convolution network","volume":"13","author":"Lu Bin","year":"2022","unstructured":"Bin Lu, Xiaoying Gan, Haiming Jin, Luoyi Fu, Xinbing Wang, and Haisong Zhang. 2022. Make more connections: Urban traffic flow forecasting with spatiotemporal adaptive gated graph convolution network. ACM Transactions on Intelligent Systems and Technology (TIST) 13, 2 (2022), 1\u201325.","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(77)90007-8"},{"key":"e_1_3_2_38_2","first-page":"4602","volume-title":"AAAI","author":"Morris Christopher","year":"2019","unstructured":"Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, Vol. 33. 4602\u20134609."},{"key":"e_1_3_2_39_2","article-title":"Fast and scalable algorithms for mining subgraphs in a single large graph","volume":"90","author":"Nguyen Lam B. Q.","year":"2020","unstructured":"Lam B. Q. Nguyen, Bay Vo, Ngoc-Thao Le, Vaclav Snasel, and Ivan Zelinka. 2020. Fast and scalable algorithms for mining subgraphs in a single large graph. EAAI 90 (2020).","journal-title":"EAAI"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2023.119287"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3317572"},{"key":"e_1_3_2_42_2","first-page":"701","volume-title":"KDD","author":"Perozzi Bryan","year":"2014","unstructured":"Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: Online learning of social representations. In KDD. 701\u2013710."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1186\/s13040-021-00250-1"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3068335"},{"key":"e_1_3_2_45_2","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. JMLR 12, Sep. (2011).","journal-title":"JMLR"},{"key":"e_1_3_2_46_2","volume-title":"ICDM","author":"Speakman Skyler","year":"2013","unstructured":"Skyler Speakman, Yating Zhang, and Daniel B. Neill. 2013. Dynamic pattern detection with temporal consistency and connectivity constraints. In ICDM."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839491"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92013-9_29"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData50022.2020.9377872"},{"issue":"6","key":"e_1_3_2_50_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3209686","article-title":"Learning urban community structures: A collective embedding perspective with periodic spatial-temporal mobility graphs","volume":"9","author":"Wang Pengyang","year":"2018","unstructured":"Pengyang Wang, Yanjie Fu, Jiawei Zhang, Xiaolin Li, and Dan Lin. 2018. Learning urban community structures: A collective embedding perspective with periodic spatial-temporal mobility graphs. ACM Transactions on Intelligent Systems and Technology (TIST) 9, 6 (2018), 1\u201328.","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3469087"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3446344"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3474842"},{"key":"e_1_3_2_54_2","volume-title":"ICLR","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks?. In ICLR."},{"key":"e_1_3_2_55_2","first-page":"721","volume-title":"ICDM","author":"Yan Xifeng","year":"2002","unstructured":"Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-based substructure pattern mining. In ICDM. 721\u2013724."},{"key":"e_1_3_2_56_2","first-page":"974","volume-title":"KDD","author":"Ying Rex","year":"2018","unstructured":"Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph convolutional neural networks for web-scale recommender systems. In KDD. 974\u2013983."},{"key":"e_1_3_2_57_2","article-title":"Frequent subgraph mining by walking in order embedding space","author":"Ying R.","year":"2020","unstructured":"R. Ying, A. Wang, J. You, and J. Leskovec. 2020. Frequent subgraph mining by walking in order embedding space. ICML (2020).","journal-title":"ICML"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511810114"},{"issue":"1","key":"e_1_3_2_59_2","first-page":"1","article-title":"Simultaneous past and current social interaction-aware trajectory prediction for multiple intelligent agents in dynamic scenes","volume":"13","author":"Zhu Yanliang","year":"2021","unstructured":"Yanliang Zhu, Dongchun Ren, Yi Xu, Deheng Qian, Mingyu Fan, Xin Li, and Huaxia Xia. 2021. Simultaneous past and current social interaction-aware trajectory prediction for multiple intelligent agents in dynamic scenes. ACM Transactions on Intelligent Systems and Technology (TIST) 13, 1 (2021), 1\u201316.","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3630635","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3630635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:32Z","timestamp":1750178192000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3630635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,19]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1145\/3630635"],"URL":"https:\/\/doi.org\/10.1145\/3630635","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2023,12,19]]},"assertion":[{"value":"2022-08-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}