  In this paper, we give an almost linear time and space algorithms to sample
from an exponential mechanism with an $\ell_1$-score function defined over an
exponentially large non-convex set. As a direct result, on input an $n$ vertex
$m$ edges graph $G$, we present the \textit{first} $\widetilde{O}(m)$ time and
$O(m)$ space algorithms for differentially privately outputting an $n$ vertex
$O(m)$ edges synthetic graph that approximates all the cuts and the spectrum of
$G$. These are the \emph{first} private algorithms for releasing synthetic
graphs that nearly match this task's time and space complexity in the
non-private setting while achieving the same (or better) utility as the
previous works in the more practical sparse regime. Additionally, our
algorithms can be extended to private graph analysis under continual
observation.
