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

Abstract

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 ${\ell }_1$-distance. We give an $\epsilon$-DP algorithm with additive error $\tilde{O}(n^{2/3}/\epsilon )$ and an $(\epsilon ,\delta )$-DP algorithm with additive error $\tilde{O}(\sqrt{n}/\epsilon )$ 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 (n^{1/6})$ is necessary for any sufficiently small $\epsilon ,\delta >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 $\tilde{O}\left(n^{1/2+O(1/k)}/\epsilon \right)$ in the $\epsilon$-DP case and $\tilde{O}(n^{1/3+O(1/k)}/\epsilon )$ in the $(\epsilon ,\delta )$-DP case, respectively.