Beyond Square-root Error: New Algorithms for Differentially Private All Pairs Shortest Distances

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.