{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T15:27:04Z","timestamp":1772206024074,"version":"3.50.1"},"reference-count":67,"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":[[2024,11]]},"abstract":"<jats:p>\n            Frequent subgraph mining is an important and well-studied problem with numerous applications such as the prediction of protein functionalities and graph indexing. Many studies use the minimum-image-based support (MNI) to measure the frequency of subgraphs in single graph mining. Given a graph\n            <jats:italic>G<\/jats:italic>\n            and an integer\n            <jats:italic>k<\/jats:italic>\n            , top-\n            <jats:italic>k<\/jats:italic>\n            frequent subgraph mining is to find top-\n            <jats:italic>k<\/jats:italic>\n            frequent subgraphs in the graph\n            <jats:italic>G<\/jats:italic>\n            based on MNI. However, there are two main challenges in top-\n            <jats:italic>k<\/jats:italic>\n            frequent subgraph mining. (1) Computing MNI is time-consuming. (2) The number of subgraphs for which MNI should be computed is large. In this paper, we propose a novel algorithm Minting to address these challenges. We propose a method to significantly reduce the number of subgraphs for which MNI computation is required by using a tight upper bound of the MNI value. We also improve the computation of MNI itself by utilizing both a lower bound and an upper bound of the MNI value. Experiments shows that our algorithm outperforms the state-of-the-art algorithms by up to three orders of magnitude in terms of the elapsed time. Our algorithm is also a feasible solution for this challenging problem, even for large\n            <jats:italic>k.<\/jats:italic>\n          <\/jats:p>","DOI":"10.14778\/3712221.3712225","type":"journal-article","created":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:03:04Z","timestamp":1744048984000},"page":"557-570","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Top-\n            <i>k<\/i>\n            Frequent Subgraph Mining using Tight Upper and Lower Bounds"],"prefix":"10.14778","volume":"18","author":[{"given":"Seonho","family":"Lee","sequence":"first","affiliation":[{"name":"Seoul National University"}]},{"given":"Yeunjun","family":"Lee","sequence":"additional","affiliation":[{"name":"Seoul National University"}]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[{"name":"Seoul National University"}]}],"member":"320","published-online":{"date-parts":[[2025,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"2024. FastPat-KG. Retrieved 2024-12-17 from https:\/\/github.com\/DBGroup-SUSTech\/FastPat-KG","DOI":"10.1007\/s35724-024-1622-2"},{"key":"e_1_2_1_2_1","unstructured":"2024. GraMi. Retrieved 2024-12-17 from https:\/\/github.com\/ehab-abdelhamid\/GraMi"},{"key":"e_1_2_1_3_1","unstructured":"2024. Peregrine. Retrieved 2024-12-17 from https:\/\/github.com\/pdclab\/peregrine"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 716--727","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 Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 716--727."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2743075"},{"key":"e_1_2_1_6_1","volume-title":"Industrial Conference on Data Mining. 146--160","author":"Alobaidi Isam A","year":"2019","unstructured":"Isam A Alobaidi, Jennifer L Leopold, and Ali A Allami. 2019. The Use of Frequent Subgraph Mining to Develop a Recommender System for Playing Real-Time Strategy Games. In Industrial Conference on Data Mining. 146--160."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 1--26","author":"Arai Junya","year":"2023","unstructured":"Junya Arai, Yasuhiro Fujiwara, and Makoto Onizuka. 2023. GuP: Fast Subgraph Matching by Guard-based Pruning. In Proceedings of ACM SIGMOD International Conference on Management of Data. 1--26."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 1199--1214","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 ACM SIGMOD International Conference on Management of Data. 1199--1214."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining. 858--863","author":"Bringmann Bj\u00f6rn","year":"2008","unstructured":"Bj\u00f6rn Bringmann and Siegfried Nijssen. 2008. What is frequent in a single graph?. In Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining. 858--863."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447818.3460359"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2830336"},{"key":"e_1_2_1_13_1","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--36.","journal-title":"IEEE Transactions on Information Technology in Biomedicine"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598591"},{"key":"e_1_2_1_15_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.127"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_1_18_1","volume-title":"Seventh IEEE International Conference on Data Mining Workshops. IEEE, 399--404","author":"Fiedler Mathias","year":"2007","unstructured":"Mathias Fiedler and Christian Borgelt. 2007. Subgraph support in a single large graph. In Seventh IEEE International Conference on Data Mining Workshops. IEEE, 399--404."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of Big Data Analytics. 209--226","author":"Fournier-Viger Philippe","year":"2019","unstructured":"Philippe Fournier-Viger, Chao Cheng, Jerry Chun-Wei Lin, Unil Yun, and R Uday Kiran. 2019. Tkg: Efficient mining of top-k frequent subgraphs. In Proceedings of Big Data Analytics. 209--226."},{"key":"e_1_2_1_20_1","volume-title":"Computers and intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael R","unstructured":"Michael R Garey and David S Johnson. 1979. Computers and intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of IEEE International Conference on Data Mining. 179--186","author":"Guralnik Valerie","year":"2001","unstructured":"Valerie Guralnik and George Karypis. 2001. A scalable algorithm for clustering sequential data. In Proceedings of IEEE International Conference on Data Mining. 179--186."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 1429--1446","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 ACM SIGMOD International Conference on Management of Data. 1429--1446."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 337--348","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 ACM SIGMOD International Conference on Management of Data. 337--348."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of IEEE International Conference on Data Mining. 549--552","author":"Huan Jun","year":"2003","unstructured":"Jun Huan, Wei Wang, and Jan Prins. 2003. Efficient mining of frequent subgraphs in the presence of isomorphism. In Proceedings of IEEE International Conference on Data Mining. 549--552."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of 13th USENIX Symposium on Operating Systems Design and Implementation. 745--761","author":"Iyer Anand Padmanabha","year":"2018","unstructured":"Anand Padmanabha Iyer, Zaoxing Liu, Xin Jin, Shivaram Venkataraman, Vladimir Braverman, and Ion Stoica. 2018. ASAP: Fast, approximate graph pattern mining at scale. In Proceedings of 13th USENIX Symposium on Operating Systems Design and Implementation. 745--761."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0376-y"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888912000331"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 925--937","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 ACM SIGMOD International Conference on Management of Data. 925--937."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.12.010"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of SIAM International Conference on Data Mining. 757--765","author":"Li Ruirui","year":"2015","unstructured":"Ruirui Li and Wei Wang. 2015. REAFUM: Representative approximate frequent subgraph mining. In Proceedings of SIAM International Conference on Data Mining. 757--765."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 391--402","author":"Meng Jinghan","year":"2017","unstructured":"Jinghan Meng and Yi-cheng Tu. 2017. Flexible and feasible support measures for mining frequent patterns in large labeled graphs. In Proceedings of ACM SIGMOD International Conference on Management of Data. 391--402."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13040-018-0181-9"},{"key":"e_1_2_1_38_1","volume-title":"Gianmarco De Francisci Morales, and Matteo Riondato","author":"Uddin Nasir Muhammad Anis","year":"2021","unstructured":"Muhammad Anis Uddin Nasir, Cigdem Aslay, Gianmarco De Francisci Morales, and Matteo Riondato. 2021. Tiptap: approximate mining of frequent k-subgraph patterns in evolving graphs. ACM Transactions on Knowledge Discovery from Data 15, 3 (2021), 1--35."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of IEEE International Conference on Data Mining. 370--379","author":"Natarajan Dheepikaa","year":"2016","unstructured":"Dheepikaa Natarajan and Sayan Ranu. 2016. A scalable and generic framework to mine top-k representative subgraph patterns. In Proceedings of IEEE International Conference on Data Mining. 370--379."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2020.103539"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 1099--1114","author":"Park Yeonsu","year":"2020","unstructured":"Yeonsu Park, Seongyun Ko, Sourav S Bhowmick, Kyoungmin Kim, Kijae Hong, and Wook-Shin Han. 2020. G-CARE: A framework for performance benchmarking of cardinality estimation techniques for subgraph matching. In Proceedings of ACM SIGMOD International Conference on Management of Data. 1099--1114."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397245"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3587254"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of IEEE International Conference on Data Engineering. 844--855","author":"Ranu Sayan","year":"2009","unstructured":"Sayan Ranu and Ambuj K Singh. 2009. Graphsig: A scalable approach to mining significant subgraphs in large graph databases. In Proceedings of IEEE International Conference on Data Engineering. 844--855."},{"key":"e_1_2_1_45_1","volume-title":"Discovery of functional motifs from the interface region of oligomeric proteins using frequent subgraph mining","author":"Saha Tanay Kumar","year":"2017","unstructured":"Tanay Kumar Saha, Ataur Katebi, Wajdi Dhifli, and Mohammad Al Hasan. 2017. Discovery of functional motifs from the interface region of oligomeric proteins using frequent subgraph mining. IEEE\/ACM transactions on Computational Biology and Bioinformatics 16, 5 (2017), 1537--1549."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 927--942","author":"Song Yinglong","year":"2018","unstructured":"Yinglong Song, Huey Eng Chua, Sourav S Bhowmick, Byron Choi, and Shuigeng Zhou. 2018. BOOMER: Blending visual formulation and processing of p-homomorphic queries on large networks. In Proceedings of ACM SIGMOD International Conference on Management of Data. 927--942."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 1083--1098","author":"Sun Shixuan","year":"2020","unstructured":"Shixuan Sun and Qiong Luo. 2020. In-memory subgraph matching: An in-depth study. In Proceedings of ACM SIGMOD International Conference on Management of Data. 1083--1098."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0466-x"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839491"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_53_1","first-page":"1","article-title":"A graph mining approach for ranking and discovering the interesting frequent subgraph patterns","volume":"14","author":"Rehman Saif Ur","year":"2021","unstructured":"Saif Ur Rehman, Kexing Liu, Tariq Ali, Asif Nawaz, and Simon James Fong. 2021. A graph mining approach for ranking and discovering the interesting frequent subgraph patterns. International Journal of Computational Intelligence Systems 14 (2021), 1--17.","journal-title":"International Journal of Computational Intelligence Systems"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation. 763--782","author":"Wang Kai","year":"2018","unstructured":"Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018. RStream: Marrying relational algebra with streaming for efficient graph mining on a single machine. In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation. 763--782."},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of International Conference on Database Systems for Advanced Applications. 891--907","author":"Wang Tongtong","year":"2018","unstructured":"Tongtong Wang, Hao Huang, Wei Lu, Zhe Peng, and Xiaoyong Du. 2018. Efficient and scalable mining of frequent subgraphs using distributed graph processing systems. In Proceedings of International Conference on Database Systems for Advanced Applications. 891--907."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2022.117262"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of IEEE International Conference on Data Engineering. 1938--1941","author":"Yan Da","year":"2020","unstructured":"Da Yan, Wenwen Qu, Guimu Guo, and Xiaoling Wang. 2020. Prefixfpm: A parallel framework for general-purpose frequent pattern mining. In Proceedings of IEEE International Conference on Data Engineering. 1938--1941."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 433--444","author":"Yan Xifeng","year":"2008","unstructured":"Xifeng Yan, Hong Cheng, Jiawei Han, and Philip S Yu. 2008. Mining significant graph patterns by leap search. In Proceedings of ACM SIGMOD International Conference on Management of Data. 433--444."},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of IEEE International Conference on Data Mining. 721--724","author":"Yan Xifeng","year":"2002","unstructured":"Xifeng Yan and Jiawei Han. 2002. gspan: Graph-based substructure pattern mining. In Proceedings of IEEE International Conference on Data Mining. 721--724."},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 286--295","author":"Yan Xifeng","year":"2003","unstructured":"Xifeng Yan and Jiawei Han. 2003. Closegraph: mining closed frequent graph patterns. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 286--295."},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 335--346","author":"Yan Xifeng","year":"2004","unstructured":"Xifeng Yan, Philip S Yu, and Jiawei Han. 2004. Graph indexing: a frequent structure-based approach. In Proceedings of ACM SIGMOD International Conference on Management of Data. 335--346."},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 1167--1182","author":"Yang Zhengwei","year":"2016","unstructured":"Zhengwei Yang, Ada Wai-Chee Fu, and Ruifeng Liu. 2016. Diversified top-k subgraph querying in a large graph. In Proceedings of ACM SIGMOD International Conference on Management of Data. 1167--1182."},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","first-page":"1979","DOI":"10.14778\/3476249.3476256","article-title":"Towards plug-and-play visual graph query interfaces: data-driven selection of canned patterns for large networks","volume":"14","author":"Yuan Zifeng","year":"2021","unstructured":"Zifeng Yuan, Huey Eng Chua, Sourav S Bhowmick, Zekun Ye, Wook-Shin Han, and Byron Choi. 2021. Towards plug-and-play visual graph query interfaces: data-driven selection of canned patterns for large networks. Proceedings of the VLDB Endowment 14, 11 (2021), 1979--1991.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of IEEE International Conference on Data Engineering. 936--947","author":"Zeng Jian","year":"2021","unstructured":"Jian Zeng, Xiao Yan, Mingji Han, Bo Tang, et al. 2021. Fast core-based top-k frequent pattern discovery in knowledge graphs. In Proceedings of IEEE International Conference on Data Engineering. 936--947."},{"key":"e_1_2_1_65_1","first-page":"608","article-title":"Extracting Top-k Frequent and Diversified Patterns in Knowledge Graphs","volume":"36","author":"Zeng Jian","year":"2024","unstructured":"Jian Zeng, Xiao Yan, Yan Li, Mingji Han, Bo Tang, et al. 2024. Extracting Top-k Frequent and Diversified Patterns in Knowledge Graphs. IEEE Transactions on Knowledge and Data Engineering 36, 2 (2024), 608--626.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of ACM SIGMOD International Conference on Management of Data. 1317--1332","author":"Zhang Gensheng","year":"2018","unstructured":"Gensheng Zhang, Damian Jimenez, and Chengkai Li. 2018. Maverick: Discovering exceptional facts from knowledge graphs. In Proceedings of ACM SIGMOD International Conference on Management of Data. 1317--1332."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2023.3257887"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3712221.3712225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:23:26Z","timestamp":1744050206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3712221.3712225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["10.14778\/3712221.3712225"],"URL":"https:\/\/doi.org\/10.14778\/3712221.3712225","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,11]]},"assertion":[{"value":"2025-04-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}