论文标题
全对最短路径距离具有差异隐私：改进的有限和无界权重的算法
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
论文作者
论文摘要
我们重新审查了私下释放全对的问题的问题，最短的无向图的最短添加剂误差的最短路径距离，这是Sealfon [Sea16]首先研究的。在本文中，无论是在$ n $ nodes上的任意加权图还是有限的重量图，我们都可以在Sealfon的结果上得到显着改善。具体而言，我们提供了一个大约DP算法，该算法将最短的路径距离输出到最大添加误差$ \ tilde {o}（\ sqrt {n}）$，以及一个纯dp算法，将所有对距离输出的最大差异$ \ tilde $ \ tilde $ \ tilde $ \ tille {n^n^n^2/3^2/3/ $ \ varepsilon，δ$）。这比以前的$ \ tilde {o}（n）$添加误差的最佳结果都改善了近似dp和pure-dp [sea16]，并部分解决了Sealfon [Sea16，Sea16，Sea20]提出的一个空旷问题。 We also show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly $n^{\sqrt{2}-1+o(1)}$ in the approximate-DP setting and roughly $n^{(\sqrt{17}-3)/2 + o(1)}$ in the pure-DP setting.以前，仅知道如何在近似dp设置中获得$ \ tilde {o}（n^{1/2}）$添加性错误，而$ \ tilde {o}（n^{2/3}）$ addiDe {n^{2/3}）$添加性错误在pure-ddp设置中用于有界weight-weight Graphs [sea16]。
We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea16]. In this paper, we improve significantly on Sealfon's results, both for arbitrary weighted graphs and for bounded-weight graphs on $n$ nodes. Specifically, we provide an approximate-DP algorithm that outputs all-pairs shortest path distances up to maximum additive error $\tilde{O}(\sqrt{n})$, and a pure-DP algorithm that outputs all pairs shortest path distances up to maximum additive error $\tilde{O}(n^{2/3})$ (where we ignore dependencies on $\varepsilon, δ$). This improves over the previous best result of $\tilde{O}(n)$ additive error for both approximate-DP and pure-DP [Sea16], and partially resolves an open question posed by Sealfon [Sea16, Sea20]. We also show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly $n^{\sqrt{2}-1+o(1)}$ in the approximate-DP setting and roughly $n^{(\sqrt{17}-3)/2 + o(1)}$ in the pure-DP setting. Previously, it was only known how to obtain $\tilde{O}(n^{1/2})$ additive error in the approximate-DP setting and $\tilde{O}(n^{2/3})$ additive error in the pure-DP setting for bounded-weight graphs [Sea16].
