  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 $(\epsilon,
\delta)$-differentially private algorithms with no multiplicative loss
whatsoever. In other words, the loss is \emph{purely additive}. Moreover, our
additive losses match or improve the best-known previous additive loss (in any
version of differential privacy) when $1/\delta$ is polynomial in $n$, and are
almost tight: in the centralized setting, our additive loss is $O(\log n
/\epsilon)$ while there is a known lower bound of $\Omega(\sqrt{\log n /
\epsilon})$.
  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.
