Differentially Private Release of Synthetic Graphs
Lists
Only you see this
Abstract
We propose a (ϵ, δ)-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G’ approximating all cuts of the input graph up to an additive error of . This is the first construction of differentially private cut approximator that allows additive error o(m) for all m > n logC n. The best known previous results gave additive O(n3/2) error and hence only retained information about the cut structure on very dense graphs. Thus, we are making a notable progress on a promiment problem in differential privacy. We also present lower bounds showing that our utility/privacy trade-off is essentially the best possible if one seeks to get purely additive cut approximations.
BibTeX
@inproceedings{elias2020differentially,
author = {Marek Eliás and Michael Kapralov and Janardhan Kulkarni and Yin Tat Lee},
title = {{Differentially Private Release of Synthetic Graphs}},
booktitle = {SODA},
year = {2020},
doi = {10.1137/1.9781611975994.34},
}Loading related content...