{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:54Z","timestamp":1787320794839,"version":"build-2736575974"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:p>\n                    A\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -plex is a dense subgraph structure where every vertex can be disconnected with at most\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    vertices. Finding a maximum\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -plex (M\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    P) in a big graph is a key primitive in many real applications such as community detection and biological network analysis. A lot of M\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    P algorithms have been actively proposed in recent years in top AI and DB conferences, featuring a broad range of sophisticated pruning techniques. In this paper, we study the various pruning techniques from nine recent M\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    P algorithms including kPlexT, Maple, Seesaw, DiseMKP, kPlexS, KpLeX, Maplex, BnB and BS by unifying them in a common framework called V-M\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    P. We summarize their proposed techniques into three categories, those for (1) branching, (2) upper bounding, and (3) reduction during subgraph exploration. We find that different pruning techniques can have drastically different performance impacts, but there exists a configuration of the techniques dependent on\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    that leads to the best performance in vast majority of the time. Interestingly, extensive experiments with our unified framework reveal that some techniques are not effective as claimed in the original works, and we also discover an unmentioned technique that is actually the major performance booster when\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    &gt; 5. We also study problem variants such as finding all the M\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    Ps and finding the densest M\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    P (i.e., with the most edges) to cover community diversity, and effective algorithm parallelization. Our source code is released at https:\/\/github.com\/akhlaqueak\/MKP-Study.\n                  <\/jats:p>","DOI":"10.14778\/3746405.3746418","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T17:06:20Z","timestamp":1756919180000},"page":"2928-2940","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximum\n                    <i>k<\/i>\n                    -Plex Finding: Choices of Pruning Techniques Matter!"],"prefix":"10.14778","volume":"18","author":[{"given":"Akhlaque","family":"Ahmad","sequence":"first","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Da","family":"Yan","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiao","family":"Chen","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lyuheng","family":"Yuan","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saugat","family":"Adhikari","sequence":"additional","affiliation":[{"name":"Indiana University Bloomington"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"brock200-2. https:\/\/networkrepository.com\/brock200-2.php."},{"key":"e_1_2_1_2_1","unstructured":"dbpedia-link. http:\/\/konect.cc\/networks\/dbpedia-link\/."},{"key":"e_1_2_1_3_1","unstructured":"delicious-ui. http:\/\/konect.cc\/networks\/delicious-ui\/."},{"key":"e_1_2_1_4_1","unstructured":"hamming6-2. https:\/\/networkrepository.com\/hamming6-2.php."},{"key":"e_1_2_1_5_1","unstructured":"ia-wiki-talk. https:\/\/networkrepository.com\/ia-wiki-Talk.php."},{"key":"e_1_2_1_6_1","unstructured":"johnson8-4-4. https:\/\/networkrepository.com\/johnson8-4-4.php."},{"key":"e_1_2_1_7_1","unstructured":"keller4. https:\/\/networkrepository.com\/keller4.php."},{"key":"e_1_2_1_8_1","unstructured":"p-hat500-1. https:\/\/networkrepository.com\/p-hat500-1.php."},{"key":"e_1_2_1_9_1","unstructured":"sc-ldoor. https:\/\/networkrepository.com\/sc-ldoor.php."},{"key":"e_1_2_1_10_1","unstructured":"sc-msdoor. https:\/\/networkrepository.com\/sc-msdoor.php."},{"key":"e_1_2_1_11_1","unstructured":"soc-buzznet. https:\/\/networkrepository.com\/soc-buzznet.php."},{"key":"e_1_2_1_12_1","unstructured":"soc-digg. https:\/\/networkrepository.com\/soc-digg.php."},{"key":"e_1_2_1_13_1","unstructured":"soc-gowalla. https:\/\/networkrepository.com\/soc-gowalla.php."},{"key":"e_1_2_1_14_1","unstructured":"soc-lastfm. https:\/\/networkrepository.com\/soc-lastfm.php."},{"key":"e_1_2_1_15_1","unstructured":"soc-livemocha. https:\/\/networkrepository.com\/soc-LiveMocha.php."},{"key":"e_1_2_1_16_1","unstructured":"soc-orkut. https:\/\/networkrepository.com\/soc-orkut.php."},{"key":"e_1_2_1_17_1","unstructured":"soc-pokec. https:\/\/networkrepository.com\/soc-pokec.php."},{"key":"e_1_2_1_18_1","unstructured":"soc-sinaweibo. https:\/\/networkrepository.com\/soc-sinaweibo.php."},{"key":"e_1_2_1_19_1","unstructured":"soc-youtube. https:\/\/networkrepository.com\/soc-youtube.php."},{"key":"e_1_2_1_20_1","unstructured":"soc-youtube-snap. https:\/\/networkrepository.com\/soc-youtube-snap.php."},{"key":"e_1_2_1_21_1","unstructured":"socfb-a-anon. https:\/\/networkrepository.com\/socfb-A-anon.php."},{"key":"e_1_2_1_22_1","unstructured":"socfb-b-anon. https:\/\/networkrepository.com\/socfb-B-anon.php."},{"key":"e_1_2_1_23_1","unstructured":"socfb-duke14. https:\/\/networkrepository.com\/socfb-Duke14.php."},{"key":"e_1_2_1_24_1","unstructured":"web-clueweb09. https:\/\/networkrepository.com\/web-ClueWeb09.php."},{"key":"e_1_2_1_25_1","unstructured":"wikipedia-link-en. http:\/\/konect.cc\/networks\/wikipedia_link_en\/."},{"key":"e_1_2_1_26_1","unstructured":"wikipedia-link-en13. https:\/\/networkrepository.com\/web-wikipedia-link-en13-all.php."},{"key":"e_1_2_1_27_1","volume-title":"https:\/\/github.com\/akhlaqueak\/MKP-Study\/blob\/main\/Technical_Report.pdf","author":"Report Full Technical","year":"2024","unstructured":"Full Technical Report. https:\/\/github.com\/akhlaqueak\/MKP-Study\/blob\/main\/Technical_Report.pdf, 2024."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-4-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_30_1","volume-title":"An o(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049","author":"Batagelj V.","year":"2003","unstructured":"V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049, 2003."},{"key":"e_1_2_1_31_1","first-page":"444","volume-title":"SIGMOD","author":"Berlowitz D.","unstructured":"D. Berlowitz, S. Cohen, and B. Kimelfeld. Efficient enumeration of maximal k-plexes. In SIGMOD, pages 431\u2013444. ACM, 2015."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_33_1","volume-title":"Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic acids research, 31(9):2443\u20132450","author":"Bu D.","year":"2003","unstructured":"D. Bu, Y. Zhao, L. Cai, H. Xue, X. Zhu, H. Lu, J. Zhang, S. Sun, L. Ling, N. Zhang, et al. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic acids research, 31(9):2443\u20132450, 2003."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565817"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639318"},{"key":"e_1_2_1_36_1","first-page":"65","volume-title":"EDBT","author":"Cheng Q.","unstructured":"Q. Cheng, D. Yan, T. Wu, L. Yuan, J. Cheng, Z. Huang, and Y. Zhou. Efficient enumeration of large maximal k-plexes. In EDBT, pages 53\u201365. OpenProceedings.org, 2025."},{"key":"e_1_2_1_37_1","first-page":"124","volume-title":"KDD","author":"Conte A.","unstructured":"A. Conte, D. Firmani, C. Mordente, M. Patrignani, and R. Torlone. Fast enumeration of large k-plexes. In KDD, pages 115\u2013124. ACM, 2017."},{"key":"e_1_2_1_38_1","first-page":"1281","volume-title":"KDD","author":"Conte A.","unstructured":"A. Conte, T. D. Matteis, D. D. Sensi, R. Grossi, A. Marino, and L. Versari. D2K: scalable community detection in massive networks via small-diameter k-plexes. In KDD, pages 1272\u20131281. ACM, 2018."},{"key":"e_1_2_1_39_1","first-page":"354","volume-title":"CIKM","author":"Dai Q.","unstructured":"Q. Dai, R. Li, H. Qin, M. Liao, and G. Wang. Scaling up maximal k-plex enumeration. In CIKM, pages 345\u2013354. ACM, 2022."},{"key":"e_1_2_1_40_1","first-page":"1455","volume-title":"IJCAI","author":"Gao J.","unstructured":"J. Gao, J. Chen, M. Yin, R. Chen, and Y. Wang. An exact algorithm for maximum k-plexes in massive graphs. In IJCAI, pages 1449\u20131455. ijcai.org, 2018."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436916"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0307750100"},{"key":"e_1_2_1_43_1","volume-title":"Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics, 21(suppl_1):i213\u2013i221","author":"Hu H.","year":"2005","unstructured":"H. Hu, X. Yan, Y. Huang, J. Han, and X. J. Zhou. Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics, 21(suppl_1):i213\u2013i221, 2005."},{"key":"e_1_2_1_44_1","first-page":"5621","volume-title":"IJCAI","author":"Jiang H.","unstructured":"H. Jiang, F. Xu, Z. Zheng, B. Wang, and W. Zhou. A refined upper bound and inprocessing for the maximum k-plex problem. In IJCAI, pages 5613\u20135621. ijcai.org, 2023."},{"key":"e_1_2_1_45_1","first-page":"1696","volume-title":"IJCAI","author":"Jiang H.","unstructured":"H. Jiang, D. Zhu, Z. Xie, S. Yao, and Z. Fu. A new upper bound based on vertex partitioning for the maximum k-plex problem. In IJCAI, pages 1689\u20131696. ijcai.org, 2021."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00712-2"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2014.08.025"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_52_1","first-page":"382","volume-title":"European Conference on Principles of Data Mining and Knowledge Discovery","author":"Ucar D.","unstructured":"D. Ucar, S. Asur, U. Catalyurek, and S. Parthasarathy. Improving functional modularity in protein-protein interactions graphs using hub-induced subgraphs. In European Conference on Principles of Data Mining and Knowledge Discovery, pages 371\u2013382. Springer, 2006."},{"key":"e_1_2_1_53_1","first-page":"5656","volume-title":"IJCAI","author":"Wang Z.","unstructured":"Z. Wang, Y. Zhou, C. Luo, and M. Xiao. A fast maximum k-plex algorithm parameterized by the degeneracy gap. In IJCAI, pages 5648\u20135656. ijcai.org, 2023."},{"key":"e_1_2_1_54_1","first-page":"1527","volume-title":"WWW","author":"Wang Z.","unstructured":"Z. Wang, Y. Zhou, M. Xiao, and B. Khoussainov. Listing maximal k-plexes in large real-world graphs. In WWW, pages 1517\u20131527. ACM, 2022."},{"key":"e_1_2_1_55_1","first-page":"925","volume-title":"AAAI","author":"Xiao M.","unstructured":"M. Xiao, W. Lin, Y. Dai, and Y. Zeng. A fast algorithm to compute maximum k-plexes in social network analysis. In AAAI, pages 919\u2013925. AAAI Press, 2017."},{"key":"e_1_2_1_56_1","first-page":"1380","volume-title":"ICDE","author":"Yan D.","unstructured":"D. Yan, G. Guo, M. M. R. Chowdhury, M. T. \u00d6zsu, W. Ku, and J. C. S. Lui. G-thinker: A distributed framework for mining subgraphs in a big graph. In ICDE, pages 1369\u20131380. IEEE, 2020."},{"key":"e_1_2_1_57_1","first-page":"412","volume-title":"T-thinker: a task-centric distributed framework for compute-intensive divide-and-conquer algorithms","author":"Yan D.","unstructured":"D. Yan, G. Guo, M. M. R. Chowdhury, M. T. \u00d6zsu, J. C. S. Lui, and W. Tan. T-thinker: a task-centric distributed framework for compute-intensive divide-and-conquer algorithms. In J. K. Hollingsworth and I. Keidar, editors, PPoPP, pages 411\u2013412. ACM, 2019."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00688-z"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00687-0"},{"key":"e_1_2_1_60_1","first-page":"3163","volume-title":"ICDE","author":"Yuan L.","unstructured":"L. Yuan, D. Yan, J. Han, A. Ahmad, Y. Zhou, and Z. Jiang. Faster depth-first subgraph matching on gpus. In ICDE, pages 3151\u20133163. IEEE, 2024."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588928"},{"key":"e_1_2_1_62_1","volume-title":"Two new upper bounds for the maximum k-plex problem. CoRR, abs\/2301.07300","author":"Zheng J.","year":"2023","unstructured":"J. Zheng, M. Jin, Y. Jin, and K. He. Two new upper bounds for the maximum k-plex problem. CoRR, abs\/2301.07300, 2023."},{"key":"e_1_2_1_63_1","first-page":"12460","volume-title":"AAAI","author":"Zhou Y.","unstructured":"Y. Zhou, S. Hu, M. Xiao, and Z. Fu. Improving maximum k-plex solver via second-order reduction and graph color bounding. In AAAI, pages 12453\u201312460. AAAI Press, 2021."},{"key":"e_1_2_1_64_1","first-page":"2449","volume-title":"AAAI","author":"Zhou Y.","unstructured":"Y. Zhou, J. Xu, Z. Guo, M. Xiao, and Y. Jin. Enumerating maximal k-plexes with worst-case time guarantee. In AAAI, pages 2442\u20132449. AAAI Press, 2020."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3746405.3746418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T19:53:39Z","timestamp":1757015619000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3746405.3746418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5]]},"references-count":64,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.14778\/3746405.3746418"],"URL":"https:\/\/doi.org\/10.14778\/3746405.3746418","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,5]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}