Locally Differentially Private Analysis of Graph Statistics
Locally Differentially Private Analysis of Graph Statistics
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Jacob Imola;Takao Murakami;Kamalika Chaudhuri
中科院分区：
文献类型：
--
作者：
Jacob Imola;Takao Murakami;Kamalika Chaudhuri
图的差分私有分析被广泛用于从敏感图中发布统计信息，同时仍然保护用户隐私。然而，大多数现有的算法都处于集中式隐私模型中，其中可信的数据管理员拥有整个图。由于该模型提出了许多隐私和安全问题-例如，策展人的可信度和数据泄露的可能性，因此需要考虑在更分散的本地模型中的算法，其中没有服务器保存整个图。在这项工作中，我们考虑了一个本地模型，并提出算法计算子图-一个基本的任务，分析图中的连接模式-与LDP（本地差分隐私）。对于三角形计数，我们提出的算法，使用一轮和两轮的相互作用，并表明，额外的一轮可以显着提高效用。对于$k$-星星计数，我们提出了一种算法，实现了一个非交互式局部模型的最优估计误差。我们提供了新的下界估计误差一般图统计，包括三角形计数和$k$-星星计数。最后，我们在两个真实的数据集上进行了大量的实验，并表明在局部差分隐私模型中确实可以准确地估计子图计数。
Differentially private analysis of graphs is widely used for releasing statistics from sensitive graphs while still preserving user privacy. Most existing algorithms however are in a centralized privacy model, where a trusted data curator holds the entire graph. As this model raises a number of privacy and security issues -- such as, the trustworthiness of the curator and the possibility of data breaches, it is desirable to consider algorithms in a more decentralized local model where no server holds the entire graph. In this work, we consider a local model, and present algorithms for counting subgraphs -- a fundamental task for analyzing the connection patterns in a graph -- with LDP (Local Differential Privacy). For triangle counts, we present algorithms that use one and two rounds of interaction, and show that an additional round can significantly improve the utility. For $k$-star counts, we present an algorithm that achieves an order optimal estimation error in the non-interactive local model. We provide new lower-bounds on the estimation error for general graph statistics including triangle counts and $k$-star counts. Finally, we perform extensive experiments on two real datasets, and show that it is indeed possible to accurately estimate subgraph counts in the local differential privacy model.