Almost Tight Bounds for Differentially Private Densest Subgraph
Michael Dinitz, Satyen Kale, Silvio Lattanzi, Sergei Vassilvitskii · Society for Industrial and Applied Mathematics eBooks · 2025
We study the Densest Subgraph (DSG) problem under the additional constraint of differential privacy. DSG is a fundamental theoretical question that 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 previous state of the art 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 .