论文笔记：发布具有差分隐私保证的图神经网络

基于 DP 的深度学习框架中比较经典的是 PATE，但是将图数据分割成许多互不相干的训练集可能会破坏结构信息并影响模型表现。基于此作者提出了一个新的针对图数据的 DP 训练框架以安全的发布“学生”GNN，完全避免分割私人训练数据。“学生”GNN 使用公共数据进行训练，部分地使用专门为每个查询节点训练的“教师”GNN 模型进行标注。 

如果大家对大图数据上高效可扩展的 GNN 和基于图的隐私计算感兴趣，欢迎关注译者的 Github，之后会不断更新相关的论文和代码的学习笔记。

https://github.com/XunKaiLi/Awesome-GNN-Research

01
Motivation

[1] 提出了差分隐私随机梯度下降（DP-SGD）算法，以实现深度学习模型的差分隐私保证。具体来说，在训练的每一步中，DP-SGD 在随机梯度下降优化过程中向经过 裁剪的梯度添加适当的噪声。训练中产生的隐私预算 使用 moment’s accountant 计算，该技术可以追踪训练过程中由于将噪声加入到输入数据中的随机子集且多次调用的隐私损失。 

除了 DP-SGD 缓慢的训练过程外，注入的噪声与训练周期数成正比，降低了性能。更重要的是，DP-SGD 的隐私保证对于图数据和 GNN 模型来说并不简单成立的 [2]。虽然 DP-SGD 是为独立同分布的数据设计的，但图数据中的节点是相关的。GNNs 使用消息传递机制在连接的节点之间交换信息。DP-SGD 的隐私保证需要一组独立同分布的数据 生成 lots 和 batches，对GNN和图数据不成立 [2]。

为了解决 DP-SGD 对训练过程的依赖性，如迭代次数 epochs，PATE训练框架被提出，PATE利用在不相交的私有数据子集上训练的大型“教师”模型集合，将知识转移给“学生”模型，然后在保证隐私的情况下发布。然而，将图数据分割成许多不相干的训练集会破坏结构信息，并对准确性产生不利影响。

由于现有的 DP 框架不能直接适用于 GNN，本文提出了一个隐私保护框架，即 PRIVGNN，用于发布具有差分隐私保证的 GNN 模型。与 PATE 的假设类似，存在两个图数据：一个存在 label 的需要考虑隐私问题的隐私图数据和一个没有 label 的公共图。PRIVGNN 利用了知识提炼的范式。基于差分隐私的框架，在隐私图上训练的“教师”模型的知识被转移到只在公共图上训练的“学生”模型中。PRIVGNN 通过将“教师”和“学生”模型的训练与两种噪声机制相结合，实现了隐私保证：使用泊松抽样的随机子抽样和噪声标签机制来获得公共节点的伪标签。发布“学生”GNN 模型，该模型使用少量的公共节点进行训练，公共节点的标签通过使用一个查询公共节点标签的查询向量经过“教师”模型获得的。

1. 与分布式设置中假设图结构或一组节点为非私有的情况相反，本文假设整个图及其节点、特征和标签是私有的，并且只有一个所有者。例如，这种情况可能出现在拥有社交网络的公司，该公司希望在不损害任何用户和社交网络隐私的情况下发布一个 GNN 模型。虽然在分布式设置中，攻击者可能是持有部分数据的任何所有者一方，但在本文中，假设对手是对训练好的模型拥有 Whitebox 访问权的用户；

2. 其次，避免了用 DP-SGD 训练差分隐私模型所需独立同分布数据的要求；

3. 最后，作者的设置与传统图统计学的不同隐私分析方法或图数据的差分隐私发布方法不同。

02
Theoreetical Components

2.1 Differential Privacy

拉普拉斯机制（Laplace Mechanism）是一个 -DP 算法的例子，它允许 中的数值的任意查询释放一个噪声答案/输出。该机制被定义为：

拉普拉斯分布 以 0为中心，其比例参数 ，概率密度函数如下：

许多 DP 算法结合了多种随机化机制，基于组成定理可以得到如下定理：

-DP的一个常见的简化版本是 -DP：

2.2 Rènyi Differential Privacy

Rènyi Differential Privacy（RDP）是基于 Rènyi divergence 概念的 DP 泛化。非常适用于表达异质机制的组成保证，特别是那些适用于数据子样本的机制：

当 时，RDP 会收敛到纯 -DP。为了方便，考虑 RDP 的函数形式。因此，我们把表示为机制的满足 -RDP 时阶数为 上。函数提供了一个与相关的隐私保证的明确特征。具体来说，对于常见的机制，可以是高斯机制或拉普拉斯机制，在本文中的 RDP 公式采用拉普拉斯机制，表示如下：

其中 ，其中是拉普拉斯分布的尺度参数。可以用以下定理将 RDP 转换为标准的 -DP，对于任何 的情况：

一般来说，对于一个组成的机制 ，通过 Lemma 5 可以推出：

在本文中使用（5）来获得 保证。与 -DP相比，RDP 的另一个显著优势是它的组合非常自然。

Lemma 6 意味着由两个机制 和 组成的隐私损失是：

2.3 Privacy Amplification by Subsampling

在隐私方面常用的方法是子抽样（subsampling），其中 DP 机制被应用于从数据中随机选择的样本。subsampling 提供了更强的隐私保证，因为两个相邻的数据集之间不同的一个数据点在较小的样本中出现的概率降低。也就是说，将一个 -DP 机制应用于随机的数据子集时，整个过程满足 -DP。通过子抽样放大隐私的直观概念是，DP机制的隐私保证可以通过应用于给定数据集中的一个小的随机子抽样记录而放大。这在文献中也被称为子采样定理 [3]。在对 的一些限制下，将子抽样法和 RDP [4, 5] 的紧密高级组合表示为：

该机制等同于 "无替换抽样 "方案，即。当 ，而 时，二项分布会收敛为泊松分布。在此为 Poisson Sample 提供了严格的隐私放大约束：

03
Approach

本文假设除了私有图（有节点特征和标签）外，还存在一个与私有图不重叠的公共图（有节点特征），公共图的节点是没有标签的。

隐私图被表示为 ，节点特征矩阵和标签矩阵分别被表示为 。被公开的图神经网络模型为 ，查询节点的集合为 ，节点的阶邻居被表示为 ，因此 ，递归定义如下：

and
PRIVGNN 模型主要被分为三个模块：私有数据的选择（private data selection），噪声伪标签的检索（retrieval of noisy pseudo-labels），以及“学生”模型的训练（student model training）。

1. 从公开的图数据中采样节点集合
2. 使用泊松分布从私有图节点中进行采样得到随机私有图节点子集 
3. 对每个查询向量重复执行4、5、6、7步
4. 利用 KNN 算法求得采样到的私有图节点子集中与当前节点 最相近的个节点
5. 从私有子图中根据 KNN 算法求得节点子集构建私有图的诱导子图
6. 在诱导子图上利用私有标签初始化并训练“教师”GNN 模型
7. 利用“教师”模型输出的预测结果利用拉普拉斯噪声 构建伪标签
8. 在公开图数据上利用从公开图数据上采样的节点集合和注入噪声的伪标签训练发布的“学生”GNN 模型。
9. 得到训练好可发布的“学生”GNN 模型。

本文重点在于提出一个满足差分隐私的 GNN 训练框架，对于 GNN 实际算法的选择没有过多的限制，可适用于现有的所有 GNN 方法，例如 GCN、GAT、GraphSAGE（inductive），都可以用来训练“教师”GNN 模型。

但是对于“学生模型”采用的是归纳式的训练方法，私有模型  只回答来自公共图的选定数量的查询。这是因为每次模型  被查询时，它都会利用在私有数据上训练的模型，这将导致隐私成本的增加。因此，所有选定的已回答的查询与未标记的数据一起被用作伪标签，以在一个过渡性设置中训练“学生”模型 。然后发布公共学生模型 ，该模型使用噪声伪标签训练。基于伪标签的可信推诿的差分隐私的后处理特性。公共模型在发布时满足差分隐私。

04
Experiments

实验参数设置细节可见 Experimental setup
RQ 1. PRIVGNN 的性能和隐私保证与其他私有化和非私有化 baselines 的比较实验：

RQ 2. 不同的 KNN 对 PRIVGNN 方法的性能的影响：

RQ 3. 不同方法的最终隐私预算与查询节点数量的增加的关系：

RQ 4. 不同的采样率对 PRIVGNN 隐私效用权衡的影响：

05
引用

[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 308–318.

[2] Timour Igamberdiev and Ivan Habernal. 2021. Privacy-Preserving Graph Convolutional Networks for Text Classification. arXiv preprint arXiv:2102.09604 (2021).

[3] Borja Balle, Gilles Barthe, and Marco Gaboardi. 2018. Privacy amplification by subsampling: Tight analyses via couplings and divergences. arXiv preprint arXiv:1807.01647 (2018).

[4] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. 2019. Subsampled Rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1226–1235.

[5] Yuqing Zhu and Yu-Xiang Wang. 2019. Poission subsampled rényi differential privacy. In International Conference on Machine Learning. PMLR, 7634–7642.

END

译者简介：李洵楷，本科就读于山东大学，目前在北京理工大学计算机学院攻读博士学位。研究兴趣包括联邦学习、图神经网络等。知乎：天下客

▼

往期回顾#

▼

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群