Optimal Bounds on Private Graph Approximation

We propose an efficient ɛ-differentially private algorithm, that given a simple weighted n-vertex, m -edge graph G with a maximum unweighted degree Δ( G ) ≤ n - 1, outputs a synthetic graph which approximates the spectrum with Õ (min{Δ( 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 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. Given the significance of effective resistance in understanding the statistical properties of a graph, we believe our result would have further implications. Spectral approximation also allows us to approximate all possible (S, T )-cuts, but it incurs an error that depends on the maximum degree, Δ( 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 -vertex weighted graph G with m -edge while preserving (ɛ, δ-differential privacy and an additive error of Õ ( √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 avg in the upper and lower bound in Elias, Kapralov, Kulkarni, and Lee (SODA 2020), where W avg is the average edge weight.

Authors

• Jingcheng Liu 0001
• Jalaj Upadhyay
• Zongrui Zou

Keywords

No keywords are indexed for this paper.