Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

We study the problem of releasing the weights of all-pair shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most 1 in the ℓ1-distance. We give an ε-DP algorithm with additive error tildeO(n2/3 / ε) and an (ε, δ)-DP algorithm with additive error tildeO(√n / ε) where n denotes the number of vertices. This positively answers a question of Sealfon (PODS'16), who asked whether a o(n)-error algorithm exists. We also show that an additive error of Omega(n1/6) is necessary for any sufficiently small ε, δ > 0. Finally, we consider a relaxed setting where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, %2k - 1, the additive error can be reduced to tildeOleft(n1/2 + O(1/k) / εright) in the ε-DP case and tildeO(n1/3 + O(1/k) / ε) in the (ε, δ)-DP case, respectively.