为什么ε-微分隐私保护1/ε边的子集？

Question

在书差分隐私的算法基础由辛西娅德劳，亚伦罗斯在第24页，数据库形式的图表是讨论。

另一方面，我们可以在与边缘对应的粒度级别上考虑微分隐私，并要求我们的算法只对图中单个或少量边的添加或删除不敏感。当然，这是一个较弱的担保，但可能仍足以满足某些目的。非正式地说，如果我们承诺将\epsilon**-微分隐私在单个边的级别上，那么任何数据分析人员都不应该能够得出关于图中任何1/\epsilon边子集的存在性的结论。在某些情况下，大量的社会接触可能不被视为敏感信息:例如，一个人可能不认为有必要隐瞒他的大部分联系人是在他的城市或工作场所与个人接触的事实，因为他的居住地和工作地点都是公共信息。另一方面，可能有少量的社会接触是高度敏感的存在(例如一个潜在的新雇主，或一个亲密的朋友)。在这种情况下，边缘隐私应该足以保护敏感信息，同时仍然允许对数据进行比顶点隐私更全面的分析。边缘隐私将保护这样一个人的敏感信息，只要他的朋友少于1/\epsilon**。

在这次讨论中，他们是如何推导出\large\frac{1}{\epsilon}数的？\epsilon的数量是否仍然代表着隐私的损失？谢谢你提前帮忙！

Answer 1

我认为这是对团体隐私的参考。见Dwork书中的定理2.2 .

如果您有用于更改1边缘的(\varepsilon,0)-differential隐私，那么您就有(1,0)-differential隐私用于更改1/\varepsilon边缘。