We consider the problem of releasing all pairs shortest path distances (APSD) in a weighted undirected graph with differential privacy (DP) guarantee. We consider the weight-level privacy introduced by Sealfon [PODS'16], where the graph topology is public but the edge weight is considered sensitive and protected from inference via the released all pairs shortest distances. The privacy guarantee ensures that the probability of differentiating two sets of edge weights on the same graph differing by an $\ell_1$ norm of $1$ is bounded. The goal is to minimize the additive error introduced to the released APSD while meeting the privacy guarantee. The best bounds known (Chen et al. [SODA'23]; Fan et al. [Arxiv'22]) is an $\tilde{O}(n^{2/3})$ additive error for $\varepsilon$-DP and an $\tilde{O}(n^{1/2})$ additive error for $(\varepsilon, \delta)$-DP. In this paper, we present new algorithms with improved additive error bounds: $\tilde{O}(n^{1/3})$ for $\varepsilon$-DP and $\tilde{O}(n^{1/4})$ for $(\varepsilon, \delta)$-DP, narrowing the gap with the current lower bound of $\tilde{\Omega}(n^{1/6})$ for $(\varepsilon, \delta)$-DP. The algorithms use new ideas to carefully inject noises to a selective subset of shortest path distances so as to control both `sensitivity' (the maximum number of times an edge is involved) and the number of these perturbed values needed to produce each of the APSD output. In addition, we also obtain, for $(\varepsilon, \delta)$-DP shortest distances on lines, trees and cycles, a lower bound of $\Omega(\log{n})$ for the additive error through a formulation by the matrix mechanism.
翻译:我们考虑释放所有配对最短路径距离( APSD) 的问题。 我们考虑的是, 在一个有不同隐私( DP) 保障的加权非方向图中, 释放所有配对最短路径距离( APSD) 。 我们考虑Selfon [PODS' 16] 引入的重量级隐私, 图表表层是公开的, 但边缘重量被视为敏感, 并且不会通过释放的所有配对最短距离释放所有配对的所有配对。 隐私保障可以确保在同一图表上区分两组不同的$( ell_ 1美元) 标准为$( $) 的加值。 目标是在满足隐私保障的同时, 尽量减少对已释放的 APSDSD的添加错误 。 已知的最佳范围( CHen et al. [Sat' 23] ; Fan. [Arxivar] 是一个$( 美元) 递增的递增错误, 美元1美元( 美元) 和美元( 美元) 的递解数( 美元) 在本文中, 我们用新的递增的 IM1- IM1 IM1 IM 的递增的递增的 IMFDLI1 的递解 值 。