A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances

The all-pairs shortest distances (APSD) with differential privacy (DP) problem takes as input an undirected, weighted graph G = (V,E, w) and outputs a private estimate of the shortest distances in G between all pairs of vertices. In this paper, we present a simple O(n1/3/ε)-accurate algorithm to solve APSD with ε-DP, which reduces to O(n1/4/ε) in the (ε, δ)-DP setting, where $n = |V|$. Our algorithm greatly improves upon the error of prior algorithms, namely O(n2/3/ε) and O(√n/ε) in the two respective settings, and is the first to be optimal up to a polylogarithmic factor, based on a lower bound of Ω(n1/4). In the case where a multiplicative approximation is allowed, we give two different constructions of algorithms with reduced additive error. Our first construction allows a multiplicative approximation of O(kloglogn) and has additive error O(k· n1/k/ε) in the ε-DP case and O(√k· n1/(2k)/ε) in the (ε, δ)-DP case. Our second construction allows multiplicative approximation $2k-1$ and has the same asymptotic additive error as the first construction. Both constructions significantly improve upon the currently best-known additive error of, O(k· n1/2 + 1/(4k+2)/ε) and O(k· n1/3 + 2/(9k+3)/ε), respectively. Our algorithms are straightforward and work by decomposing a graph into a set of spanning trees, and applying a key observation that we can privately release APSD in trees with O(polylog(n)) error.