# Distances Release with Differential Privacy in Tree and Grid Graph

arXiv: https://arxiv.org/abs/2204.12488 · HTML: https://mlsanity.com/paper/2204.12488/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2022.

## Built on by (most cited first, 7 of 7)

- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [Almost linear time differentially private release of synthetic graphs](https://mlsanity.com/paper/2406.02156/) (2024)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)

## Abstract (arXiv)

Data about individuals may contain private and sensitive information. The differential privacy (DP) was proposed to address the problem of protecting the privacy of each individual while keeping useful information about a population. Sealfon (2016) introduced a private graph model in which the graph topology is assumed to be public while the weight information is assumed to be private. That model can express hidden congestion patterns in a known transportation system. In this paper, we revisit the problem of privately releasing approximate distances between all pairs of vertices in (Sealfon 2016). Our goal is to minimize the additive error, namely the difference between the released distance and actual distance under private setting. We propose improved solutions to that problem for several cases. For the problem of privately releasing all-pairs distances, we show that for tree with depth h, we can release all-pairs distances with additive error O(log1.5 h · log1.5 V) for fixed privacy parameter where V the number of vertices in the tree, which improves the previous error bound O(log2.5 V), since the size of h can be as small as O(log V). Our result implies that a log V factor is saved, and the additive error in tree can be smaller than the error on array/path. Additionally, for the grid graph with arbitrary edge weights, we also propose a method to release all-pairs distances with additive error tilde O(V3/4)  for fixed privacy parameters. On the application side, many cities like Manhattan are composed of horizontal streets and vertical avenues, which can be modeled as a grid graph.