Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance
Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-27
DOI: 10.1145/3802044 ↗At a glance
Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Yingli Zhou and 2 co-authors. 85 references.
Abstract (original language)
Densest subgraph discovery (DSD) 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.
Cite
APA
Zhou, Y., Sun, Y., & Fang, Y. (2026). Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802044
Vancouver
Zhou Y, Sun Y, Fang Y. Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802044
BibTeX
@article{Zhou2026,
author = {Zhou, Yingli and Sun, Youran and Fang, Yixiang},
title = {Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--27},
doi = {10.1145/3802044}
}
EUVIMED