论文周报——Sharing Graphs using Differentially Private Graph Models

た入场券 2022-05-19 14:28 112阅读 0赞

针对这篇论文中的基于差分隐私的算法进行概括解析：

**|输入**

输入为结点对格式，用一个整数代表一个结点。

例如下图，假如将A-F表示成1-6，则表示成节点对格式为：

1 2

2 3

3 4

4 5

4 6

![70][]

**|输出**

输出和输入的格式相同，结果为经差分隐私处理后的结点对。

**|算法解析**

*  **需求分析：**

建立一个系统，通过将原始图G提取成图结构的统计表示，添加受控水平的“噪声”，然后使用结果统计信息生成一个新的图G’。

所以，可分成两部分工作：

1.  首先，需要一种方法来准确地捕获一个图的结构作为一组结构统计数据，以及一个生成器将它转换回一个图。
2.  其次，我们需要一种方法来确定适当的噪音，以保证一个理想的隐私水平。

*  **算法实现：**

**1.读取图数据**

数据结构：

HashMap<Integer,HashSet<Integer>

生成各结点的邻接表。

**2.生成dK-2 series**

![70 1][]

如上图所示，红色数字标识各结点的度（degree），dK-2 series定义为度的不同组合与各组合的出现次数的映射。

例如：<1,2> = 1 (A-B)，表示的是degree=1和degree=2的结点相连的边只有AB一条。

考虑合适的数据结构来存储dK-2 series，可采用Hashmap，其中key为其中一个结点的degree（两个结点中较小的degree），value为一个HashSet，为第二个结点的degree和degree组合数的映射。

HashMap<Integer,HashMap<Integer,Integer>>

例如上图所示图结构提取出的dK-2 series数据为：

![70 2][]

然后按照顺序放到优先队列中，排序规则是degree对中较大的放后面，例如：

（2，（4,3））< （1，（5,3））<（2，（5,2））

**3.添加噪音**

所需添加的拉普拉斯噪声量是用户指定的隐私参数epsilon和DK函数的灵敏度S的函数。定义了dK-2 series后，导出它的灵敏度SdK−2。灵敏度被计算为所有G的邻域图中dk-2 series的最大变化数。接着描述了dk扰动算法(dK-PA)在原dK-2 series中的注入噪声，并证明了该算法的有效性，即保证了访问所需的ε-差分隐私。

证明得dK-2灵敏度上限为4·dmax + 1，故代码中添加噪声体现为：

![70 3][]

然后对其随机产生的负度数进行统计，归零，然后在正degree部分上减去一些，以保持基本分布不变。

**4.分组**

作者首先将数据作为整体一起处理，结果显示为若要满足较高的隐私保护要求，最终生成的图与原始的图G差距较大，使得其可用性较低。

于是，**改进措施**是将排序好的dK-2 series分成一定的tuples，在每个tuples中计算各自的maxdegree，添加噪声，然后再将各个分组合并成整个图。这样就使得大多数元组的maxDegree变小，添加的噪声较小，使得数据更好地保持原样。

LaplaceDistribution(0,(4\*maxDegree + 1)/epselon);

**5.生成新图并输出**

（生成器的具体实现过程没看懂，结果就是根据差分隐私保护后的degree生成了新的图，嗯。）然后把HashMap的键值对输出到自定义的文件中，和输入的图G格式相同。

![70 4][]

得到的几组数据：

![70 5][]

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

ps: 整个算法的过程大致如上。如有描述不当的地方请指正(\#^.^\#)

[70]: /images/20220519/efbeb8a78130419b92ea2236d9d29065.png
[70 1]: /images/20220519/2ebef273e9524376819c9bff54d7b656.png
[70 2]: /images/20220519/fa3cb00119544d0183074f38fe14368e.png
[70 3]: /images/20220519/8d987b3825394398b07e46e3227a6f96.png
[70 4]: /images/20220519/f684c415f2a947bcbe2336316ed59744.png
[70 5]: /images/20220519/e63ecbc35e8641678b92a709e0802759.png