Random Projections, Graph Sparsification, and Differential Privacy
Random Projections, Graph Sparsification, and Differential Privacy
复制标题
随机投影、图稀疏化和差分隐私
DOI：
10.1007/978-3-642-42033-7_15
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Jalaj Upadhyay
中科院分区：
文献类型：
--
作者：
Jalaj Upadhyay
本文在数据集稀疏的情况下，开展了保持差分隐私保护的研究。我们研究了构造有效的消毒器的问题，该消毒器既能保持DP，又能保证回答图上的割查询的高效性。研究稀疏图的主要动机来自于社交网站是稀疏图的经验证据。我们还鼓励和倡导，如果一个人希望有一个保护隐私的消毒剂的实际部署，除了效用保证外，还有必要包括消毒剂的效率。
我们证明了Blocki等人的技术[3]BBDS可以用来保持DP以回答稀疏图上的割查询，并且具有渐近有效的消毒器Thaniá？BBDS。我们以此为基础，为任意图构造了一个高效的消毒器。特别是，我们使用了一个保留光谱特性的预条件步骤，因此，任何切割的大小都保持不变，然后再应用我们的基本消毒剂。我们首先证明了我们的消毒器对高电导图保持DP。然后，我们仔细地将我们的基本技术与改进的消毒器组合在一起，以证明任意图的结果。在某种意义上，我们的方法是对随机清理的补充，用于回答割查询[17]：我们使用图稀疏，而随机清理使用图密集。
我们的消毒器几乎实现了两全其美，具有相同的隐私保证，即它几乎与最有效的消毒器一样有效，它的效用保证几乎与最好的消毒算法的效用保证一样强大。
我们在用BBDS回答一些未解决的问题方面也取得了一些进展。我们做了一个组合观察，证明了经过消毒的图也可以回答S，T-割查询，并且与我们的S，{S}$-割的消毒算法具有相同的渐近效率、效用和DP保证。此外，我们实现了比Gupta、Roth和Ullman更好的效用保证[17]。通过证明Ailon和Chazelle[2]的快速Johnson-Lindenstrauss变换也保持DP，给出了进一步的优化。
This paper initiates the study of preserving differential privacy DP when the data-set is sparse. We study the problem of constructing efficient sanitizer that preserves DP and guarantees high utility for answering cut-queries on graphs. The main motivation for studying sparse graphs arises from the empirical evidences that social networking sites are sparse graphs. We also motivate and advocate the necessity to include the efficiency of sanitizers, in addition to the utility guarantee, if one wishes to have a practical deployment of privacy preserving sanitizers.
We show that the technique of Blocki et al.[3] BBDS can be adapted to preserve DP for answering cut-queries on sparse graphs, with an asymptotically efficient sanitizer thani¾?BBDS. We use this as the base technique to construct an efficient sanitizer for arbitrary graphs. In particular, we use a preconditioning step that preserves the spectral properties and therefore, size of any cut is preserved, and then apply our basic sanitizer. We first prove that our sanitizer preserves DP for graphs with high conductance. We then carefully compose our basic technique with the modified sanitizer to prove the result for arbitrary graphs. In certain sense, our approach is complementary to the Randomized sanitization for answering cut queries [17]: we use graph sparsification, while Randomized sanitization uses graph densification.
Our sanitizers almost achieves the best of both the worlds with the same privacy guarantee, i.e., it is almost as efficient as the most efficient sanitizer and it has utility guarantee almost as strong as the utility guarantee of the best sanitization algorithm.
We also make some progress in answering few open problems by BBDS. We make a combinatorial observation that allows us to argue that the sanitized graph can also answer S,T-cut queries with same asymptotic efficiency, utility, and DP guarantee as our sanitization algorithm for S, $\bar{S}$ -cuts. Moreover, we achieve a better utility guarantee than Gupta, Roth, and Ullman [17]. We give further optimization by showing that fast Johnson-Lindenstrauss transform of Ailon and Chazelle [2] also preserves DP.