Private Graph All-Pairwise-Shortest-Path Distance Release with Improved Error Rate

Releasing all pairwise shortest path (APSP) distances among vertices on general graphs under weight Differential Privacy (DP) is known as a challenging task that has gained increasing interest recently. Previous work achieved DP with the maximal absolute error among all published pairwise distances bounded by ˜ O ( n ) where n is the number of nodes. Whether the approximation error can be reduced to sublinear in n is still an interesting open problem. In this paper, we break the linear barrier on the distance approximation error in APSP release, by proposing an algorithm that releases a constructed synthetic graph privately. Computing all pairwise distances on the constructed graph only introduces ˜ O ( n 1 / 2 ) error in answering all pairwise shortest path distances for fixed privacy parameter. Our method is based on a novel graph diameter (link length) augmentation via constructing “shortcuts” for the paths and the use of Laplace noise with non-zero mean. Numerical examples are also provided. Additionally, we also propose a DP algorithm with error rate ˜ O ( k ) , which improves the error of general graphs, when the graph has small feedback vertex set number k = o ( n 1 / 2 ) .