All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
share
We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea16]. In this paper, we improve significantly on Sealfon's results, both for arbitrary weighted graphs and for bounded-weight graphs on n nodes. Specifically, we provide an approximate-DP algorithm that outputs all-pairs shortest path distances up to maximum additive error Õ(√(n)), and a pure-DP algorithm that outputs all pairs shortest path distances up to maximum additive error Õ(n^2/3) (where we ignore dependencies on ε, δ). This improves over the previous best result of Õ(n) additive error for both approximate-DP and pure-DP [Sea16], and partially resolves an open question posed by Sealfon [Sea16, Sea20]. We also show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly n^√(2)-1+o(1) in the approximate-DP setting and roughly n^(√(17)-3)/2 + o(1) in the pure-DP setting. Previously, it was only known how to obtain Õ(n^1/2) additive error in the approximate-DP setting and Õ(n^2/3) additive error in the pure-DP setting for bounded-weight graphs [Sea16].
READ FULL TEXT