论文标题
差异私人全对最短路径距离：改进的算法和下限
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
论文作者
论文摘要
我们研究了带有差异隐私（DP）的加权无向图中释放全皮最短路径的权重的问题。在这种情况下，基础图是固定的，如果其边缘权重有所不同，则两个图是邻居的，在$ \ ell_1 $ distance中最多有1美元。我们给出$ε$ -DP算法，并带有附加错误$ \ tilde {o}（n^{2/3} /ε）$和$（ε，δ）$ - dp算法，带有附加错误$ \ tilde {o \ tilde {o}（o \ tilde {o}（\ sqrt {\ sqrt {n} /这积极回答了Sealfon（PODS'16）的问题，他询问$ o（n）$ - 错误算法是否存在。我们还表明，对于任何足够小的$ε，δ> 0 $，必不可少的$ω（n^{1/6}）$的添加误差是必需的。 最后，我们考虑允许乘法近似的放松设置。我们表明，使用乘法近似因子$ k $，％$ 2K-1 $，可以将添加期错误降低到$ \ tilde {o} \ left（n^{1/2 + o（1/k）}/am imp）$ y $ -dp case and $ \ tilde and $ \ tilde {1/y $}（1/3^y^y^^y^ + of） $（ε，δ）$ -DP情况。
We study the problem of releasing the weights of all-pair shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most $1$ in the $\ell_1$-distance. We give an $ε$-DP algorithm with additive error $\tilde{O}(n^{2/3} / ε)$ and an $(ε, δ)$-DP algorithm with additive error $\tilde{O}(\sqrt{n} / ε)$ where $n$ denotes the number of vertices. This positively answers a question of Sealfon (PODS'16), who asked whether a $o(n)$-error algorithm exists. We also show that an additive error of $Ω(n^{1/6})$ is necessary for any sufficiently small $ε, δ> 0$. Finally, we consider a relaxed setting where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor $k$, %$2k - 1$, the additive error can be reduced to $\tilde{O}\left(n^{1/2 + O(1/k)} / ε\right)$ in the $ε$-DP case and $\tilde{O}(n^{1/3 + O(1/k)} / ε)$ in the $(ε, δ)$-DP case, respectively.
