Abstract
Releasing all-pairs shortest path (APSP) distances while preserving differential privacy (DP) is a fundamental challenge in private graph analysis. Previous state-of-the-art approaches were largely limited to additive errors linear in the number of nodes $n$. This paper introduces novel algorithmic frameworks—landmark-based hitting sets and recursive peeling—that achieve the first sublinear additive error rates for APSP. For graphs with unbounded weights, we achieve errors of $\tilde{O}(\sqrt{n})$ under approximate-DP and $\tilde{O}(n^{2/3})$ under pure-DP. For bounded weights, these bounds are further improved to approximately $n^{0.4143}$ and $n^{0.5616}$, respectively.
Introduction
In applications such as real-time navigation, graph data often contains sensitive information regarding individual movements or infrastructure usage. Differential Privacy (DP) provides a robust mathematical framework to protect this data by ensuring that the output of an algorithm is insensitive to changes in a single individual's data (e.g., the weight of a single road segment).
The specific challenge addressed here is the All-Pairs Shortest Path (APSP) problem: releasing the distances between every pair of nodes in a graph. Prior work, such as that by Sealfon [Sea16], was constrained to an additive error of $O(n)$ for a graph with $n$ nodes. In large-scale networks, an error proportional to the number of nodes renders the data practically unusable. This research investigates whether it is possible to release these distances with significantly smaller, sublinear error.
Methodology
The authors propose two primary algorithmic frameworks tailored to the nature of the edge weights: "unbounded" and "bounded" (capped at a maximum value $A$).
Unbounded Weights: Landmarks and Noisy Edges
For general graphs with unbounded weights, the algorithm employs a "hitting set" strategy. The core idea is to balance the noise added to individual edges against the noise added to global "landmarks."
- Landmark Selection: A random set of "landmark" nodes $S \subset V$ of size $L$ is selected.
- Noisy Release: The algorithm releases the distances between all pairs of landmarks with added noise $Lap(T)$. Simultaneously, it releases the weights of every individual edge $e \in E$ with added noise $Lap(2/\epsilon)$.
- Distance Estimation: To estimate the distance between arbitrary nodes $u$ and $v$, the algorithm considers two candidates: a "short" path (composed of noisy edges) and a "long" path that transits through the nearest landmarks.
Bounded Weights: Recursive Peeling
When edge weights are bounded, a more sophisticated "recursive peeling" procedure is utilized. The algorithm iteratively "peels" off small neighborhoods (balls) of the graph and solves the problem recursively on these sub-structures. A martingale-based analysis is used to demonstrate that most shortest paths do not cross an excessive number of these "peeled" boundaries, thereby preventing the accumulation of noise and maintaining low total error.
Key Results
The proposed algorithms provide significant improvements over previous benchmarks, particularly in achieving sublinear error across all standard DP settings.
| Setting | Privacy Model | New Additive Error | Previous Best |
|---|---|---|---|
| Unbounded Weights | Approximate-DP | $\tilde{O}(\sqrt{n})$ | $\tilde{O}(n)$ |
| Unbounded Weights | Pure-DP | $\tilde{O}(n^{2/3})$ | $\tilde{O}(n)$ |
| Bounded Weights | Approximate-DP | $\approx n^{0.4143}$ | $\tilde{O}(\sqrt{n})$ |
| Bounded Weights | Pure-DP | $\approx n^{0.5616}$ | $\tilde{O}(n^{2/3})$ |
Note: $\tilde{O}$ notation suppresses logarithmic factors.
Discussion and Future Work
While these results represent a major breakthrough, several open questions remain. There is still a gap between these new upper bounds and known lower bounds (which suggest an error of at least $n^{1/6}$ may be necessary). Additionally, the recursive peeling algorithm is currently restricted to undirected graphs; extending these tighter bounds to directed graphs is a primary area for future research. Finally, while the algorithms are polynomial-time, the practical computational overhead of recursive structures on massive real-world networks warrants further optimization.
Summary updated