Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance
Summary: Introduces an improved-iteration approximation for anchored densest subgraphs, plus a reduction that localizes search while retaining guarantees. An exact algorithm built atop these ideas is up to four orders of magnitude faster than prior methods on 12 real graphs. (summarized by gpt-5.6-luna on Jul 26 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Yingli Zhou (Chinese University of Hong Kong)
- 2. Youran Sun (Chinese University of Hong Kong)
- 3. Yixiang Fang (Chinese University of Hong Kong)
BibTeX Citation
@inproceedings{zhou_sigmod26,
title = {{Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance}},
author = {Zhou, Yingli and Sun, Youran and Fang, Yixiang},
series = {{SIGMOD} '26},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3802044},
url = {https://dl.acm.org/doi/10.1145/3802044},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 24 of 24 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,519 | A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery | 2024 | SIGMOD |
| 2 | 10,767 | Integral Densest Subgraph Search on Directed Graphs | 2025 | SIGMOD |
| 3 | 9,553 | Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs | 2025 | VLDB |
| 4 | 11,608 | Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques | 2022 | VLDB |
| 5 | 10,930 | Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory | 2025 | VLDB |
| 6 | 10,807 | In-depth Analysis of Densest Subgraph Discovery in a Unified Framework | 2025 | VLDB |
| 7 | 3,737 | Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs | 2020 | SIGMOD |
| 8 | 10,363 | Efficient and Scalable Directed Densest Subgraph Discovery | 2026 | SIGMOD |
| 9 | 2,024 | Efficient Algorithms for Densest Subgraph Discovery | 2019 | VLDB |
| 10 | 4,554 | Anchored Densest Subgraph | 2022 | SIGMOD |