# Heterogeneous Differential Privacy via Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2022.

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

- [Heterogeneous Graph Neural Network for Privacy-Preserving Recommendation](https://mlsanity.com/paper/2210.00538/) (2022)
- [Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free](https://mlsanity.com/paper/2305.09668/) (2023)
- [Mean Estimation Under Heterogeneous Privacy Demands](https://mlsanity.com/paper/2310.13137/) (2023)

## Abstract (arXiv)

We generalize a previous framework for designing utility-optimal differentially private (DP) mechanisms via graphs, where datasets are vertices in the graph and edges represent dataset neighborhood. The boundary set contains datasets where an individual's response changes the binary-valued query compared to its neighbors. Previous work was limited to the homogeneous case where the privacy parameter varepsilon across all datasets was the same and the mechanism at boundary datasets was identical. In our work, the mechanism can take different distributions at the boundary and the privacy parameter varepsilon is a function of neighboring datasets, which recovers an earlier definition of personalized DP as special case. The problem is how to extend the mechanism, which is only defined at the boundary set, to other datasets in the graph in a computationally efficient and utility optimal manner. Using the concept of strongest induced DP condition we solve this problem efficiently in polynomial time (in the size of the graph).