Zongrui Zou, Nanjing University

Abstract

We propose an efficient ε-differentially private (DP) algorithm, that given a simple weighted n-vertex, m-edge graph G with a maximum unweighted degree Δ(G), outputs a synthetic graph which approximates the spectrum with $tilde{O}(Delta(G))$ bound on the purely additive error. To the best of our knowledge, this is the first ε-DP algorithm with a non-trivial additive error for approximating the spectrum of the graph. One of our subroutines 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 log-concave distribution defined over a convex set. As a direct application of our result, we give the first non-trivial bound on approximating all-pairs effective resistances by a synthetic graph, which also implies approximating hitting/commute time and cover time of random walks on the graph. 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 (ε,δ)-DP and an optimal additive error. 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 in the upper and lower bound with respect to the average edge weight in Eliáš, Kapralov, Kulkarni, and Lee (SODA 2020).
This is a joint work with Jingcheng Liu and Jalaj Upadhyay.