# All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights

Preprint · Justin Y. Chen, Shyam Narayanan, Yinzhan Xu

- Archive id: arxiv:2204.02335
- Published: 2022-04-05
- arXiv: https://arxiv.org/abs/2204.02335
- Source URL: https://arxiv.org/abs/2204.02335
- PDF: https://arxiv.org/pdf/2204.02335
- Provenance: arxiv

## Abstract

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 $\\tilde{O}(\\sqrt{n})$, and a pure-DP algorithm that outputs all pairs shortest path distances up to maximum additive error $\\tilde{O}(n^{2/3})$ (where we ignore dependencies on $\\varepsilon, δ$). This improves over the previous best result of $\\tilde{O}(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^{\\sqrt{2}-1+o(1)}$ in the approximate-DP setting and roughly $n^{(\\sqrt{17}-3)/2 + o(1)}$ in the pure-DP setting. Previously, it was only known how to obtain $\\tilde{O}(n^{1/2})$ additive error in the approximate-DP setting and $\\tilde{O}(n^{2/3})$ additive error in the pure-DP setting for bounded-weight graphs \[Sea16\].

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.