Optimal Bounds on Private Graph Approximation via Markov chain
- Prof. Jingcheng Liu, Nanjing University
- Time: 2023-12-21 15:00
- Host: Dr. Tianren Liu
- 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 uses Markov chain to simulate 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.
Biography
Jingcheng Liu is an Associate Professor in the Theory Group of the Department of Computer Science and Technology at Nanjing University. He is broadly interested in theoretical computer science, which includes randomized algorithms, computational phase transition, and differential privacy.
Before that, he completed undergrad at SJTU (ACM Honors class) and PhD at UC Berkeley, and he was a Wally Baer and Jeri Weiss postdoctoral scholar at Caltech.