{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:36Z","timestamp":1775912916661,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"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":[[2024,5,29]]},"abstract":"<jats:p>Densest subgraph discovery (DSD) is a fundamental topic in graph mining. It has been extensively studied in the literature and has found many real applications in a wide range of fields, such as biology, finance, and social networks. As a typical problem of DSD, the k-clique densest subgraph (CDS) problem aims to detect a subgraph from a graph, such that the ratio of the number of k-cliques over the number of its vertices is maximized. This problem has received plenty of attention in the literature, and is widely used in identifying larger ''near-cliques''. Existing CDS solutions, either k-core or convex programming based solutions, often need to enumerate almost all the k-cliques, which is very inefficient because real-world graphs usually have a vast number of k-cliques. To improve the efficiency, in this paper, we propose a novel framework based on the Frank-Wolfe algorithm, which only needs k-clique counting, rather than k-clique enumeration, where the former one is often much faster than the latter one. Based on the framework, we develop an efficient approximation algorithm, by employing the state-of-the-art k-clique counting algorithm and proposing some optimization techniques. We have performed extensive experimental evaluation on 14 real-world large graphs and the results demonstrate the high efficiency of our algorithms. Particularly, our algorithm is up to seven orders of magnitude faster than the state-of-the-art algorithm with the same accuracy guarantee.<\/jats:p>","DOI":"10.1145\/3654922","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":8,"title":["A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5630-6822","authenticated-orcid":false,"given":"Yingli","family":"Zhou","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4477-6052","authenticated-orcid":false,"given":"Qingshuo","family":"Guo","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-8512","authenticated-orcid":false,"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412036"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Venkat Anantharam and Justin Salez. 2016. The densest subgraph problem in sparse random graphs. (2016).","DOI":"10.1214\/14-AAP1091"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_2_1_6_1","volume-title":"Densest subgraph in streaming and mapreduce. arXiv preprint arXiv:1201.6567","author":"Bahmani Bahman","year":"2012","unstructured":"Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012. Densest subgraph in streaming and mapreduce. arXiv preprint arXiv:1201.6567 (2012)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746592"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380140"},{"key":"e_1_2_1_10_1","unstructured":"Richard L. Burden and J. Douglas Faires. 2010. Numerical Analysis (9 ed.). Brooks\/Cole Cengage Learning."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539100"},{"key":"e_1_2_1_14_1","series-title":"SIAM Journal on computing 14, 1","volume-title":"Arboricity and subgraph listing algorithms","author":"Chiba Norishige","year":"1985","unstructured":"Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing 14, 1 (1985), 210--223."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_16_1","volume-title":"An algorithm for finding functional modules and protein complexes in protein-protein interaction networks. Journal of Biomedicine and Biotechnology 2008","author":"Cui Guangyu","year":"2008","unstructured":"Guangyu Cui, Yu Chen, De-Shuang Huang, and Kyungsook Han. 2008. An algorithm for finding functional modules and protein complexes in protein-protein interaction networks. Journal of Biomedicine and Biotechnology 2008 (2008)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517890"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557142"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554895"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_24_1","unstructured":"Uriel Feige Michael Seltser et al. 1997. On the densest k-subgraph problem. Citeseer."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536342"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789987"},{"key":"e_1_2_1_29_1","unstructured":"Andrew V Goldberg. 1984. Finding a maximum density subgraph. (1984)."},{"key":"e_1_2_1_30_1","first-page":"26966","article-title":"Faster and scalable algorithms for densest subgraph and decomposition","volume":"35","author":"Harb Elfarouk","year":"2022","unstructured":"Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. 2022. Faster and scalable algorithms for densest subgraph and decomposition. Advances in Neural Information Processing Systems 35 (2022), 26966--26979.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588923"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti1049"},{"key":"e_1_2_1_33_1","volume-title":"International conference on machine learning. PMLR, 427--435","author":"Jaggi Martin","year":"2013","unstructured":"Martin Jaggi. 2013. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In International conference on machine learning. PMLR, 427--435."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380264"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_37_1","volume-title":"International colloquium on automata, languages, and programming","author":"Khuller Samir","unstructured":"Samir Khuller and Barna Saha. 2009. On finding dense subgraphs. In International colloquium on automata, languages, and programming. Springer, 597--608."},{"key":"e_1_2_1_38_1","volume-title":"A survey on the densest subgraph problem and its variants. arXiv preprint arXiv:2303.14467","author":"Lanciano Tommaso","year":"2023","unstructured":"Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. 2023. A survey on the densest subgraph problem and its variants. arXiv preprint arXiv:2303.14467 (2023)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_41_1","volume-title":"The H-index of a network node and its relation to degree and coreness. Nature communications 7, 1","author":"L\u00fc Linyuan","year":"2016","unstructured":"Linyuan L\u00fc, Tao Zhou, Qian-Ming Zhang, and H Eugene Stanley. 2016. The H-index of a network node and its relation to degree and coreness. Nature communications 7, 1 (2016), 10168."},{"key":"e_1_2_1_42_1","volume-title":"A Survey of Densest Subgraph Discovery on Large Graphs. arXiv preprint arXiv:2306.07927","author":"Luo Wensheng","year":"2023","unstructured":"Wensheng Luo, Chenhao Ma, Yixiang Fang, and Laks VS Lakshman. 2023. A Survey of Densest Subgraph Discovery on Large Graphs. arXiv preprint arXiv:2306.07927 (2023)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00029"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599306"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_1_50_1","unstructured":"The Technique Report. 2023. A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery (technical report). https:\/\/drive.google.com\/file\/d\/1--9bDgjiQuIDKnUOWy16JU-iaX-reQNTc\/view?usp=sharing."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192424.3192431"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_57_1","volume-title":"Koobface: The evolution of the social botnet. In 2010 eCrime Researchers Summit","author":"Tanner Brian K","year":"2010","unstructured":"Brian K Tanner, Gary Warner, Henry Stern, and Scott Olechowski. 2010. Koobface: The evolution of the social botnet. In 2010 eCrime Researchers Summit. IEEE, 1--10."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_59_1","volume-title":"The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1","author":"Tomita Etsuji","year":"2006","unstructured":"Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science 363, 1 (2006), 28--42."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_62_1","volume-title":"Mathematical and algorithmic analysis of network and biological data. arXiv preprint arXiv:1407.0375","author":"Tsourakakis Charalampos E","year":"2014","unstructured":"Charalampos E Tsourakakis. 2014. Mathematical and algorithmic analysis of network and biological data. arXiv preprint arXiv:1407.0375 (2014)."},{"key":"e_1_2_1_63_1","volume-title":"A novel approach to finding near-cliques: The triangle-densest subgraph problem. arXiv preprint arXiv:1405.1477","author":"Tsourakakis Charalampos E","year":"2014","unstructured":"Charalampos E Tsourakakis. 2014. A novel approach to finding near-cliques: The triangle-densest subgraph problem. arXiv preprint arXiv:1405.1477 (2014)."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467398"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589314"},{"key":"e_1_2_1_66_1","volume-title":"Data Science for Fake News: Surveys and Perspectives","author":"Yu Kaiqiang","unstructured":"Kaiqiang Yu and Cheng Long. 2021. Graph Mining Meets Fake News Detection. In Data Science for Fake News: Surveys and Perspectives. Springer, 169--189."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.35"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654922","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:41:54Z","timestamp":1755787314000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654922"],"URL":"https:\/\/doi.org\/10.1145\/3654922","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}