2024/07/09 by Campbell, Jesse, Zhu, Chunjiang
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2407.06913
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 \widetildeO(n1/3/ε)-accurate algorithm to solve APSD with ε-DP, which reduces to \widetildeO(n1/4/ε) in the (ε, δ)-DP setting, where n = |V|. Our algorithm greatly improves upon the error of prior algorithms, namely \widetildeO(n2/3/ε) and \widetildeO(√(n)/ε) in the two respective settings, and is the first to be optimal up to a polylogarithmic factor, based on a lower bound of \widetildeΩ(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 \widetildeO(k⋅ n1/k/ε) in the ε-DP case and \widetildeO(√(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, \widetildeO(k⋅ n1/2 + 1/(4k+2)/ε) and \widetildeO(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.