论文标题
打破差分私有图形距离释放中的线性误差屏障
Breaking the Linear Error Barrier in Differentially Private Graph Distance Release
论文作者
论文摘要
在重量差异隐私（DP）下释放所有成对最短路径（APSP）距离是一项挑战的任务。在先前的尝试（Sealfon 2016}}的尝试中，通过向每个边缘的重量或每个输出距离添加拉普拉斯噪声，以实现DP，以一定的预算来实现DP，并且在所有已发布的成对距离的可能性很大的情况下，最大的绝对错误大约是$ o（n）$ $ o（n）$，其中$ n $是节点的数量。将$ n $中的Sublritear简化为一个有趣的公开问题。 我们通过提出一种私下释放构造的合成图的算法来打破上一个结果的距离近似误差的线性屏障。在构造图上计算所有成对距离仅引入$ \ tilde o（n^{1/2}）$错误回答固定隐私参数的所有成对最短路径距离时。我们的方法基于新的图直径（链路长度）通过为路径构造“快捷方式”的增强。通过在原始图中添加一组快捷方式边缘，我们显示任何节点对具有最短的路径，链路长度$ \ tilde o（n^{1/2}）$。然后，通过向边缘权重添加一些正均值的噪声，我们表明新图是私人的，可以发表以使用$ \ tilde o（n^{1/2}）$（使用标准APSP计算）回答所有成对的最短路径距离（N^{1/2}）$。 此外，我们考虑具有小反馈顶点集号码的图。图形的反馈顶点集（FVS）是一组顶点，其删除将图形留在没有周期的情况下，而反馈顶点集合的图形$ k $是最小的反馈顶点集的大小。我们建议使用错误率$ \ tilde o（k）$的DP算法。
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)$.
