论文标题
稀疏图的平滑匿名性
Smooth Anonymity for Sparse Graphs
论文作者
论文摘要
当使用提供明确定义的隐私保证的用户数据时，至关重要。在这项工作中，我们旨在与第三方私下操纵和共享整个稀疏数据集。实际上，差异隐私已成为隐私的黄金标准，但是，在共享稀疏数据集时，例如作为我们的主要结果之一，稀疏的网络证明了\ emph {any}具有私人机制，该机制保持了与初始数据集的合理相似性，注定要具有非常薄弱的隐私保证。在这种情况下，我们需要研究其他隐私概念，例如$ k $ - 匿名性。在这项工作中，我们考虑了$ k $ - 匿名的变体，我们称之为平滑$ k $ - 匿名性，并设计简单的大型算法，可有效地提供光滑的$ k $ - 匿名性。我们进一步进行经验评估，以支持我们的理论保证，并表明我们的算法改善了匿名数据下游机器学习任务的性能。
When working with user data providing well-defined privacy guarantees is paramount. In this work, we aim to manipulate and share an entire sparse dataset with a third party privately. In fact, differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets, e.g. sparse networks, as one of our main results, we prove that \emph{any} differentially private mechanism that maintains a reasonable similarity with the initial dataset is doomed to have a very weak privacy guarantee. In such situations, we need to look into other privacy notions such as $k$-anonymity. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity. We further perform an empirical evaluation to back our theoretical guarantees and show that our algorithm improves the performance in downstream machine learning tasks on anonymized data.
