# Almost Tight Bounds for Differentially Private Densest Subgraph

arXiv: https://arxiv.org/abs/2308.10316 · HTML: https://mlsanity.com/paper/2308.10316/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2023.

## Built on by (most cited first, 2 of 2)

- [Privacy-Computation trade-offs in Private Repetition and Metaselection](https://mlsanity.com/paper/2410.19012/) (2024)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)

## Abstract (arXiv)

We study the Densest Subgraph (DSG) problem under the additional constraint of differential privacy. DSG is a fundamental theoretical question which plays a central role in graph analytics, and so privacy is a natural requirement. All known private algorithms for Densest Subgraph lose constant multiplicative factors, despite the existence of non-private exact algorithms. We show that, perhaps surprisingly, this loss is not necessary: in both the classic differential privacy model and the LEDP model (local edge differential privacy, introduced recently by Dhulipala et al. [FOCS 2022]), we give (ε, δ)-differentially private algorithms with no multiplicative loss whatsoever. In other words, the loss is purely additive. Moreover, our additive losses match or improve the best-known previous additive loss (in any version of differential privacy) when 1/δ is polynomial in n, and are almost tight: in the centralized setting, our additive loss is O(log n /ε) while there is a known lower bound of Omega(√log n / ε). We also give a number of extensions. First, we show how to extend our techniques to both the node-weighted and the directed versions of the problem. Second, we give a separate algorithm with pure differential privacy (as opposed to approximate DP) but with worse approximation bounds. And third, we give a new algorithm for privately computing the optimal density which implies a separation between the structural problem of privately computing the densest subgraph and the numeric problem of privately computing the density of the densest subgraph.