Speaker: Prof. Jingcheng Liu, Nanjing University

Time: 15:00 p.m., December 21, 2023, GMT+8

Venue: Room 204, Courtyard No.5, Jingyuan

Abstract: 

We propose an efficient ϵ-differentially private algorithm, that given a simple weighted n-vertex, m-edge graph G with a maximum unweighted degree Δ, outputs a synthetic graph which approximates the spectrum within O(min{Δ(G),sqrt(n)) 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 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 Δ(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 optimal additive error for weighted graphs. This removes the gap in the upper and lower bound in Eliáš, Kapralov, Kulkarni, and Lee (SODA 2020). Based on joint work with Jalaj Upadhyay and Zongrui Zou.

Source: Center on Frontiers of Computing Studies, PKU