A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910903547461632 |
|---|---|
| author | Dinitz, Michael Fan, Chenglin Liu, Jingcheng Upadhyay, Jalaj Zou, Zongrui |
| author_facet | Dinitz, Michael Fan, Chenglin Liu, Jingcheng Upadhyay, Jalaj Zou, Zongrui |
| contents | We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as \textit{recursively separable}. In particular, for any $n$-vertex $K_h$-minor-free graph, our algorithm achieve an additive error of $\widetilde{O}(h(nW)^{1/3} ) $, where $ W $ represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of $\widetilde{O}(n^{1/4}\sqrt{W})$.
Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are \textit{recursively separable}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03354 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances Dinitz, Michael Fan, Chenglin Liu, Jingcheng Upadhyay, Jalaj Zou, Zongrui Data Structures and Algorithms We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as \textit{recursively separable}. In particular, for any $n$-vertex $K_h$-minor-free graph, our algorithm achieve an additive error of $\widetilde{O}(h(nW)^{1/3} ) $, where $ W $ represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of $\widetilde{O}(n^{1/4}\sqrt{W})$. Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are \textit{recursively separable}. |
| title | A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.03354 |