Optimal Bounds on Private Graph Approximation

We propose an efficient ε-differentially private algorithm, that given a simple em weighted n-vertex, m-edge graph G with a maximum unweighted degree Delta(G) ≤ n-1, outputs a synthetic graph which approximates the spectrum with widetildeO(minDelta(G), √n) bound on the purely additive error. To the best of our knowledge, this is the first ε-differentially private algorithm with a non-trivial additive error for approximating the spectrum of the graph. One of the subroutines of our algorithm also precisely simulates the exponential mechanism over a non-convex set, which could be of independent interest given the recent interest in sampling from a em log-concave distribution defined over a convex set. Spectral approximation also allows us to approximate all possible (S,T)-cuts, but it incurs an error that depends on the maximum degree, Delta(G). We further show that using our sampler, we can also output a synthetic graph that approximates the sizes of all (S,T)-cuts on n vertices weighted graph G with m edges while preserving (ε,δ)-differential privacy and an additive error of widetildeO(√mn/ε). We also give a matching lower bound (with respect to all the parameters) on the private cut approximation for weighted graphs. This removes the gap of √W_mathsfavg in the upper and lower bound in Eli'avs, Kapralov, Kulkarni, and Lee (SODA 2020), where W_mathsfavg is the average edge weight.