论文标题
通过图的异质差异隐私
Heterogeneous Differential Privacy via Graphs
论文作者
论文摘要
我们概括了一个以前的框架，该框架是通过图形设计实用性 - 最佳差异化机制（DP）机制，在该图中，数据集是图表中的顶点，而边缘表示数据集邻域。边界集包含数据集，其中个人的响应与邻居相比会更改二进制值的查询。以前的工作仅限于同质情况，在所有数据集中，隐私参数$ \ varepsilon $都是相同的，边界数据集的机制相同。在我们的工作中，该机制可以在边界上采用不同的分布，而隐私参数$ \ varepsilon $是相邻数据集的函数，该函数恢复了对个性化DP的早期定义作为特殊情况。问题是如何以计算高效且实用性的最佳方式将机制扩展到边界集定义的机制。使用最强诱导的DP条件的概念，我们在多项式时间（图中的大小）中有效地解决了此问题。
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).
