Releasing all pairwise shortest path (APSP) distances between vertices on general graphs under weight Differential Privacy (DP) is known as a challenging task. In the previous attempt of (Sealfon 2016}, by adding Laplace noise to each edge weight or to each output distance, to achieve DP with some fixed budget, with high probability the maximal absolute error among all published pairwise distances is roughly $O(n)$ where $n$ is the number of nodes. It was shown that this error could be reduced for some special graphs, which, however, is hard for general graphs. Therefore, whether the approximation error can be reduced to sublinear in $n$ is posted as an interesting open problem. We break the linear barrier on the distance approximation error of previous result, by proposing an algorithm that releases a constructed synthetic graph privately. Computing all pairwise distances on the constructed graph only introduces $\tilde O(n^{1/2})$ error in answering all pairwise shortest path distances for fixed privacy parameter. Our method is based on a novel graph diameter (link length) augmentation via constructing "shortcuts" for the paths. By adding a set of shortcut edges to the original graph, we show that any node pair has a shortest path with link length $\tilde O(n^{1/2})$. Then by adding noises with some positive mean to the edge weights, we show that the new graph is differentially private and can be published to answer all pairwise shortest path distances with $\tilde O(n^{1/2})$ approximation error using standard APSP computation. Additionally, we consider the graph with small feedback vertex set number. A feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles, and the feedback vertex set number of a graph, $k$, is the size of a smallest feedback vertex set. We propose a DP algorithm with error rate $\tilde O(k)$.
翻译:(APSP) 在重力下, 差异隐私 (DP) 被称为一项具有挑战性的任务。 在先前的尝试中 (Searlfon 2016}), 将 Laplace 噪音加到每个边缘重量或每个输出距离中, 以某种固定预算实现 DP, 所有出版的对称距离的最大绝对差错大约是 $O (n) 美元, 其中节点数为美元。 显示, 对于某些特殊图表来说, 此差错可以减少, 但对于一般图形来说, 差值是很难的。 因此, 在先前的尝试中( Searfon 2016 2016 } ), 将Laplace 噪音加到每个边端重量或每个输出距离, 以某种固定的合成图形, 计算所有双偏差的离差, 用于固定隐私参数的所有对等离差值。 我们的方法是以新的图形直径( 链接长度), 通过构建“ shortcutterral rickral ral ral”, 以显示一个正数 。