A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery
Summary: Convex-programming recasts directed densest subgraph into LPs, enabling exact and parameterized approximation via LP duality. Empirical results on eight large datasets show up to five orders of magnitude speedups over state-of-the-art. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Chenhao Ma (University of Hong Kong)
- 2. Yixiang Fang (Chinese University of Hong Kong)
- 3. Reynold Cheng (University of Hong Kong)
- 4. Laks V.S. Lakshmanan (University of British Columbia)
- 5. Xiaolin Han (University of Hong Kong)
BibTeX Citation
@inproceedings{ma_sigmod22,
title = {{A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery}},
author = {Ma, Chenhao and Fang, Yixiang and Cheng, Reynold and Lakshmanan, Laks V.S. and Han, Xiaolin},
series = {{SIGMOD} '22},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3514221.3517837},
url = {https://dl.acm.org/doi/10.1145/3514221.3517837},
year = {2022}
}
Incoming Citations (Sorted by Pagerank)
Showing 20 of 20 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 138 | Discovering Large Dense Subgraphs in Massive Graphs | 2005 | VLDB | 0.00029823423 |
| 564 | Densest Subgraph in Streaming and MapReduce | 2012 | VLDB | 0.00016485347 |
| 1,018 | Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification | 2012 | VLDB | 0.0001263063 |
| 1,307 | KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs | 2020 | VLDB | 0.00011232263 |
| 2,024 | Efficient Algorithms for Densest Subgraph Discovery | 2019 | VLDB | 9.2907829e-05 |
| 3,737 | Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs | 2020 | SIGMOD | 7.1609645e-05 |
| 7,354 | DeepTEA: Effective and Efficient Online Time-dependent Trajectory Outlier Detection | 2022 | VLDB | 5.6348348e-05 |
| 11,690 | On Analyzing Graphs with Motif-Paths | 2021 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,608 | Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques | 2022 | VLDB |
| 2 | 10,807 | In-depth Analysis of Densest Subgraph Discovery in a Unified Framework | 2025 | VLDB |
| 3 | 10,767 | Integral Densest Subgraph Search on Directed Graphs | 2025 | SIGMOD |
| 4 | 9,696 | An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery | 2024 | SIGMOD |
| 5 | 9,519 | A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery | 2024 | SIGMOD |
| 6 | 10,226 | Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance | 2026 | SIGMOD |
| 7 | 2,024 | Efficient Algorithms for Densest Subgraph Discovery | 2019 | VLDB |
| 8 | 3,148 | Finding Locally Densest Subgraphs: A Convex Programming Approach | 2022 | VLDB |
| 9 | 3,737 | Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs | 2020 | SIGMOD |
| 10 | 10,363 | Efficient and Scalable Directed Densest Subgraph Discovery | 2026 | SIGMOD |