{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:27Z","timestamp":1779131187874,"version":"3.51.4"},"reference-count":85,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    <jats:italic toggle=\"yes\">Densest subgraph discovery (DSD)<\/jats:italic>\n                    is a fundamental research topic in network science and graph databases. As a typical variant of DSD, the anchored densest subgraph (ADS) problem aims to detect a densest subgraph that is anchored around user-defined seed vertices. The ADS problem has been shown to be very useful in some personalized applications, such as community search and recommendation. While the ADS problem is very useful, existing algorithms suffer from weak theoretical guarantees and perform poorly in practice. To address these issues, we first propose a novel approximation algorithm with improved time complexity, achieving the same accuracy as existing methods while requiring significantly fewer iterations. To further enhance practical performance, we introduce a graph reduction technique that localizes the ADS search to a much smaller subgraph, while still providing non-trivial theoretical guarantees. Building on this approximation, we also develop an efficient exact algorithm. We have performed an extensive empirical evaluation of our approaches on 12 real large datasets. The results show that our proposed algorithms are up to four orders of magnitude faster than the state-of-the-art.\n                  <\/jats:p>","DOI":"10.1145\/3802044","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance"],"prefix":"10.1145","volume":"4","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-0005-1371-666X","authenticated-orcid":false,"given":"Youran","family":"Sun","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"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824780"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598582"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_1_6_1","first-page":"379","article-title":"Finding subgraphs with maximum total density and limited overlap","author":"Balalau Oana Denisa","year":"2015","unstructured":"Oana Denisa Balalau, Francesco Bonchi, TH Hubert Chan, Francesco Gullo, and Mauro Sozio. 2015. Finding subgraphs with maximum total density and limited overlap. In WSDM. 379-388.","journal-title":"WSDM."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_8_1","volume-title":"arXiv preprint cs\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003)."},{"key":"e_1_2_1_9_1","series-title":"SIAM journal on imaging sciences","volume-title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems","author":"Beck Amir","year":"2009","unstructured":"Amir Beck and Marc Teboulle. 2009. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences, Vol. 2, 1 (2009), 183-202."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512158"},{"key":"e_1_2_1_11_1","first-page":"173","article-title":"Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. 2015. Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In STOC. 173-182.","journal-title":"STOC."},{"key":"e_1_2_1_12_1","volume-title":"Flowless: Extracting densest subgraphs without flow computations. In WWW.","author":"Boob Digvijay","year":"2020","unstructured":"Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting densest subgraphs without flow computations. In WWW."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401198"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_15_1","volume-title":"Densest Subgraph: Supermodularity, Iterative Peeling, and Flow","author":"Chekuri Chandra","year":"2022","unstructured":"Chandra Chekuri, Kent Quanrud, and Manuel R Torres. 2022. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. In SODA. SIAM, 1531-1555."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2009.14"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636226"},{"key":"e_1_2_1_18_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. National security agency technical report","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report, Vol. 16, 3.1 (2008)."},{"key":"e_1_2_1_19_1","first-page":"345","article-title":"Scaling Up Maximal k-plex Enumeration","author":"Dai Qiangqiang","year":"2022","unstructured":"Qiangqiang Dai, Rong-Hua Li, Hongchao Qin, Meihao Liao, and Guoren Wang. 2022a. Scaling Up Maximal k-plex Enumeration. In CIKM. 345-354.","journal-title":"CIKM."},{"key":"e_1_2_1_20_1","first-page":"1200","article-title":"Anchored Densest Subgraph","author":"Dai Yizhou","year":"2022","unstructured":"Yizhou Dai, Miao Qiao, and Lijun Chang. 2022b. Anchored Densest Subgraph. In SIGMOD. 1200-1213.","journal-title":"SIGMOD."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651589"},{"key":"e_1_2_1_22_1","first-page":"589","article-title":"Listing k-cliques in sparse real-world graphs","author":"Danisch Maximilien","year":"2018","unstructured":"Maximilien Danisch, Oana Balalau, and Mauro Sozio. 2018. Listing k-cliques in sparse real-world graphs. In WWW. 589-598.","journal-title":"WWW."},{"key":"e_1_2_1_23_1","first-page":"233","article-title":"Large scale density-friendly graph decomposition via convex programming","author":"Danisch Maximilien","year":"2017","unstructured":"Maximilien Danisch, T-H Hubert Chan, and Mauro Sozio. 2017. Large scale density-friendly graph decomposition via convex programming. In WWW. 233-242.","journal-title":"WWW."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554895"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_28_1","unstructured":"Uriel Feige Michael Seltser et al. 1997. On the densest k-subgraph problem. Citeseer."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.2.186"},{"key":"e_1_2_1_30_1","first-page":"1807","article-title":"Core decomposition and densest subgraph in multilayer networks","author":"Galimberti Edoardo","year":"2017","unstructured":"Edoardo Galimberti, Francesco Bonchi, and Francesco Gullo. 2017. Core decomposition and densest subgraph in multilayer networks. In CIKM. 1807-1816.","journal-title":"CIKM."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_2_1_32_1","volume-title":"Finding a maximum density subgraph","author":"Goldberg Andrew V","unstructured":"Andrew V Goldberg. 1984. Finding a maximum density subgraph. University of California Berkeley."},{"key":"e_1_2_1_33_1","unstructured":"Elfarouk Harb Kent Quanrud and Chandra Chekuri. 2022. Faster and Scalable Algorithms for Densest Subgraph and Decomposition. In NIPS."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588923"},{"key":"e_1_2_1_35_1","volume-title":"Alex Beutel, Neil Shah, Kijung Shin, and Christos Faloutsos.","author":"Hooi Bryan","year":"2016","unstructured":"Bryan Hooi, Hyun Ah Song, Alex Beutel, Neil Shah, Kijung Shin, and Christos Faloutsos. 2016. Fraudar: Bounding graph fraud in the face of camouflage. In SIGKDD. 895-904."},{"key":"e_1_2_1_36_1","first-page":"1241","article-title":"Querying minimal steiner maximum-connected subgraphs in large graphs","author":"Hu Jiafeng","year":"2016","unstructured":"Jiafeng Hu, Xiaowei Wu, Reynold Cheng, Siqiang Luo, and Yixiang Fang. 2016. Querying minimal steiner maximum-connected subgraphs in large graphs. In CIKM. 1241-1250.","journal-title":"CIKM."},{"key":"e_1_2_1_37_1","first-page":"427","article-title":"Revisiting Frank-Wolfe: Projection-free sparse convex optimization","author":"Jaggi Martin","year":"2013","unstructured":"Martin Jaggi. 2013. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In ICML. PMLR, 427-435.","journal-title":"ICML. PMLR"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23525-7_39"},{"key":"e_1_2_1_39_1","unstructured":"Ravindran Kannan and V Vinay. 1999. Analyzing the structure of large graphs. Forschungsinst. f\u00fcr Diskrete Mathematik."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_41_1","unstructured":"Konect. 2006. Konect. http:\/\/konect.cc\/networks\/."},{"key":"e_1_2_1_42_1","first-page":"2","article-title":"On a Quest for Combating Filter Bubbles and Misinformation","author":"Lakshmanan Laks VS","year":"2022","unstructured":"Laks VS Lakshmanan. 2022. On a Quest for Combating Filter Bubbles and Misinformation. In SIGMOD. 2-2.","journal-title":"SIGMOD."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3653298"},{"key":"e_1_2_1_44_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_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_2_1_46_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. 2023a. A Survey of Densest Subgraph Discovery on Large Graphs. arXiv preprint arXiv:2306.07927 (2023)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00029"},{"key":"e_1_2_1_48_1","first-page":"2719","article-title":"Finding locally densest subgraphs: a convex programming approach","volume":"15","author":"Ma Chenhao","year":"2022","unstructured":"Chenhao Ma, Reynold Cheng, Laks VS Lakshmanan, and Xiaolin Han. 2022a. Finding locally densest subgraphs: a convex programming approach. PVLDB, Vol. 15, 11 (2022), 2719-2732.","journal-title":"PVLDB"},{"key":"e_1_2_1_49_1","first-page":"845","article-title":"A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery","author":"Ma Chenhao","year":"2022","unstructured":"Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks VS Lakshmanan, and Xiaolin Han. 2022b. A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery. In SIGMOD. 845-859.","journal-title":"SIGMOD."},{"key":"e_1_2_1_50_1","first-page":"1051","article-title":"Efficient algorithms for densest subgraph discovery on large directed graphs","author":"Ma Chenhao","year":"2020","unstructured":"Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks VS Lakshmanan, Wenjie Zhang, and Xuemin Lin. 2020. Efficient algorithms for densest subgraph discovery on large directed graphs. In SIGMOD. 1051-1066.","journal-title":"SIGMOD."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3483940"},{"key":"e_1_2_1_52_1","first-page":"815","article-title":"Scalable large near-clique detection in large-scale networks via sampling","author":"Mitzenmacher Michael","year":"2015","unstructured":"Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, and Shen Chen Xu. 2015. Scalable large near-clique detection in large-scale networks via sampling. In SIGKDD. 815-824.","journal-title":"SIGKDD."},{"key":"e_1_2_1_53_1","first-page":"543","article-title":"A method for solving the convex programming problem with convergence rate O$(1\/k^2)$","volume":"269","author":"Nesterov Yu E","year":"1983","unstructured":"Yu E Nesterov. 1983. A method for solving the convex programming problem with convergence rate O$(1\/k^2)$. In Dokl. Akad. Nauk SSSR, Vol. 269. 543-547.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_2_1_54_1","volume-title":"Multiplicative weights update, area convexity and random coordinate descent for densest subgraph problems. arXiv preprint arXiv:2405.18809","author":"Nguyen Ta Duy","year":"2024","unstructured":"Ta Duy Nguyen and Alina Ene. 2024. Multiplicative weights update, area convexity and random coordinate descent for densest subgraph problems. arXiv preprint arXiv:2405.18809 (2024)."},{"key":"e_1_2_1_55_1","unstructured":"Laboratory of Web Algorithmics. 2013. Laboratory of Web Algorithmics Datasets. http:\/\/law.di.unimi.it\/datasets.php."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.94"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_2_1_58_1","unstructured":"Stanford Network Analysis Project. 2009. SNAP. http:\/\/snap.stanford.edu\/data\/."},{"key":"e_1_2_1_59_1","first-page":"965","article-title":"Locally densest subgraph discovery","author":"Qin Lu","year":"2015","unstructured":"Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. 2015. Locally densest subgraph discovery. In KDD. 965-974.","journal-title":"KDD."},{"key":"e_1_2_1_60_1","unstructured":"Network Repository. 2014. Network Repository. https:\/\/networkrepository.com\/network-data.php."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/ietfec\/e91-a.11.3304"},{"key":"e_1_2_1_62_1","first-page":"181","article-title":"Near-optimal fully dynamic densest subgraph","author":"Sawlani Saurabh","year":"2020","unstructured":"Saurabh Sawlani and Junxing Wang. 2020. Near-optimal fully dynamic densest subgraph. In STOC. 181-193.","journal-title":"STOC."},{"key":"e_1_2_1_63_1","volume-title":"Network structure and minimum degree. Social networks","author":"Seidman Stephen B","year":"1983","unstructured":"Stephen B Seidman. 1983. Network structure and minimum degree. Social networks, Vol. 5, 3 (1983), 269-287."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_65_1","first-page":"2959","article-title":"Efficient Cross-layer Community Search in Large Multilayer Graphs","author":"Sun Longxu","year":"2024","unstructured":"Longxu Sun, Xin Huang, Zheng Wu, and Jianliang Xu. 2024. Efficient Cross-layer Community Search in Large Multilayer Graphs. In ICDE. IEEE, 2959-2971.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_68_1","first-page":"104","article-title":"Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees","author":"Tsourakakis Charalampos","year":"2013","unstructured":"Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. 2013. Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In SIGKDD. 104-112.","journal-title":"SIGKDD."},{"key":"e_1_2_1_69_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_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975673.43"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752948"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589314"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319886"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3637528.3671727"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0451-4"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.14778\/3712221.3712230"},{"key":"e_1_2_1_77_1","first-page":"1049","article-title":"Extracting analyzing and visualizing triangle k-core motifs within networks","author":"Zhang Yang","year":"2012","unstructured":"Yang Zhang and Srinivasan Parthasarathy. 2012. Extracting analyzing and visualizing triangle k-core motifs within networks. In ICDE. IEEE, 1049-1060.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681975"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/3748191.3748210"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677129"},{"key":"e_1_2_1_81_1","volume-title":"In-depth Analysis of Densest Subgraph Discovery in a Unified Framework. arXiv preprint arXiv:2406.04738","author":"Zhou Yingli","year":"2024","unstructured":"Yingli Zhou, Qingshuo Guo, Yi Yang, Yixiang Fang, Chenhao Ma, and Laks Lakshmanan. 2024c. In-depth Analysis of Densest Subgraph Discovery in a Unified Framework. arXiv preprint arXiv:2406.04738 (2024)."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i14.17477"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3769785"},{"key":"e_1_2_1_84_1","unstructured":"Yingli Zhou Youran Sun and Yixiang Fang. 2025c. Efficient Anchored Densest Subgraph Discovery: Improved Time Complexities and Practical Performance (technical report). https:\/\/github.com\/JayLZhou\/TechnicalReport\/blob\/main\/ADS_Technical_report.pdf."},{"key":"e_1_2_1_85_1","unstructured":"Zhaonian Zou. 2013. Polynomial-time algorithm for finding densest subgraphs in uncertain graphs. In MLG."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:23:55Z","timestamp":1779128635000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":85,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802044"],"URL":"https:\/\/doi.org\/10.1145\/3802044","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}