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

We study the problem of releasing the weights of all-pairs 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 algorithm with additive error Õ(n2/3/ε) in the ε-DP case and an algorithm with additive error in the (ε,δ)-DP case, where n denotes the number of vertices. This positively answers a question of Sealfon [Sea16, Sea20], who asked whether a o(n)- error algorithm exists. We also show that an additive error of Ω(n1/6) is necessary for any sufficiently small ε,δ > 0. Furthermore, we show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly in the ε-DP case and roughly in the (ε, δ)-DP case. Previously, it was only known how to obtain Õ(n2/3/ε1/3) additive error in the ε-DP case and additive error in the (ε,δ)-DP case for bounded-weight graphs [Sea16]. Finally, we consider a relaxation where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, the additive error can be reduced to Õ(n1/2+O(1/k)/ε) in the ε-DP case and Õ(n1/3+O(1/k)/ε) in the (ε,δ)-DP case.