一. 简介
差分隐私（DP）是密码学的一种手段，它旨在提供一种当从统计数据库查询时，最大化数据查询的准确性，同时最大限度减少识别其记录的机会。差分隐私最早被用来保护tabular数据，如查询数据库返回数据的统计信息，这时对统计信息加差分隐私就可以让用户很难推断出包含隐私的单个数据。非欧几里得数据（如图数据）由于其组织的复杂性，更容易收到攻击，给DP的应用带来了很大的挑战。本文梳理了一些经典的将DP用于图数据隐私保护的研究工作（主要包括结构和特征的扰乱算法，其他略）。
二. 预备知识
DP和LDP定义
DP的形式化定义为：
如果上式对任意D，D'及S都成立，则称随机化算法M满足(ε,δ)-差分隐私。其中D和D'是相邻的数据集，相邻数据集取决于我们对隐私数据的定义，比如我们保护的数据是数据库中的每个记录，那么相邻数据集就彼此有一个记录不同。S为原始数据经过随机化算法之后的得到的结果。直观上来讲，差分隐私使得攻击者无法判断S来自于哪一个相邻数据集，又因为相邻数据集只有一条隐私数据的差异，从而保护了数据隐私。DP可以分为中心化差分隐私（CDP）和本地化差分隐私（LDP)，其区别在于本地化差分隐私是每个用户在本地进行差分隐私，不需要可信的中心服务器。
敏感度 (sensitivity)
敏感度衡量相邻数据集的最大差异。比如L2敏感度定义如下：
其中f是一个查询，通常为对原始数据的统计或处理（需要发布的），如在GNN中，可以是对GNN的前向传播，损失计算或者梯度计算。利用敏感度可以使我们设计的随机化算法M满足差分隐私的定义，如对数值型数据添加拉普拉斯噪声时，拉普拉斯分布的参数λ=△/ε则满足ε-差分隐私。
DP应用于图数据
根据图数据的隐私保护对象，DP在图上的应用可分为多类，下面是一些经典的类别 [1]: (1) edge-level DP: 相邻数据集有一条边不同（去掉或加上一条边） (2) node-level DP：相邻数据集有一个节点不同（去掉或加上一个节点） (3) graph-level DP：相邻数据集有一个图不同（去掉或加上一个图）。由DP的定义，node-level更难实现，因为它需要在去掉（加上）一个节点及其邻边后的图的分布还相似，而edge-level只需去掉（加上）一条边后满足。由此可见node-level DP比edge-level DP有更强的隐私保证（它包括了edge-level DP），同时在具有相同隐私预算时，数据的可用性更低。
三. 相关工作
现有工作大多基于edge-level ldp的定义，也有少数工作针对node或graph-level LDP。根据保护的对象，本文将现有工作分为 1.只保护图结构，和 2. 保护特征（包括label和图结构）两部分。
结构隐私保护
LDPGEN (CCS 2017) [2]: 每个client的数据为一个节点和它的一阶邻居，server端的任务为生成完整的图结构。一个直观想法是本地客户端利用RR上传邻接矩阵(RNL)，但RR可以使稀疏图变稠密，引入过多噪声；第二个想法是客户端上传经过扰乱的节点的度(DGG)，但这样只关注全局的度，生成的图缺少了很多结构信息。为了平衡噪声和信息丢失两部分，LDPGEN 首先将所有节点划分成多个组，这样每个节点在每个组里都有一个度信息，形成一个度向量，把度向量上传到server进行图结构生成。那么RR和DGG就是LDPGEN的两个极端情况：RR是每个节点为一个组，DGG是所有节点为一个组。如何找到最合理的划分是一个挑战，因为收集数据后才能找到一个划分，而想要收集数据又需要知道一个划分，所以LDPGEN采用了一个迭代的设计。理想的情况是，每个组里的节点结构相似。LDPGEN首先初始化k0个组，将初始化信息发送给各个client。在接下来的多个迭代步骤中，client根据当前分组计算度向量发送给server，server根据度向量得到新的分组。在迭代的初期分配大的隐私预算，后面逐渐减小。迭代结束后，server利用BTER模型生成图的结构。LPGEN对度的扰乱算法采用了拉普拉斯噪音，也证明了此算法满足ε-edge LDP。LDPGEN示意图：
Solitude (TIFS 2022) [3]: edge-level LDP，是对LPGNN场景的改进，structure 和 node feature是隐私信息，label是公开的。structure扰动采用了RR机制，feature扰动采用了LPGNN中的multi-bit机制。在server端采用了一个正则项来处理RR带来的denser graph 问题：
这里A^c是要学习的calibrated graph，A(hat)是server收集到的经过RR后的邻接矩阵。最终server端GNN的训练损失函数为：
并进行迭代训练参数θ和A^c。
DPRR (arXiv 2022) [4]: edge-level LDP。对RR进行了改进，使得经过扰乱的节点的度是无偏的，具体而言，在RR的之后为1的位置以概率q来保持，概率1-q翻转：
当q设置为：
并且节点的度远小于节点数时（稀疏图），DPRR得到的度是无偏的。这里di*是加了拉普拉斯噪音的度。
LF-GDPR (TKDE 2022) [5]。这篇工作主要是得到图上一些常用的统计量，如clustering coefficient，modularity等。server端为做这些统计，需要client端以隐私保护的形式上传节点的邻接矩阵和度。对于邻接矩阵，采用RNL算法进行扰动，但对于无向图server端会收到一条边的两次扰动，所以根据组合原理，实际上隐私预算为原来ε1的2倍，同时由于每个node都需要上传它的整个邻接矩阵，所以通信和计算代价也增加。LF-GDPR提出了一种Randomized Adjacency Bit Vector （RABV）算法，即每个node只扰动它的一部分邻接node上传，并且所有node扰动的部分是不重合的，如下图所示，这样就达到了ε1-LDP：
对于client上传的degree，由于同样的道理，敏感度实际上为2，LF-GDPR利用参数为2/ε2的拉普拉斯噪声达到ε2-LDP。这样实际上server可以得到两个度，一个是client上传的degree，另一个是利用client上传的邻接矩阵计算得到的degree。server利用这些信息进行aggregation和calibration，并且估计相应的统计量。
特征隐私保护
AsgLDP (TIFS 2020) [6]：edge-level LDP。此篇是对LDPGEN的改进，AsgLDP不仅保护图结构，还保护了节点特征。对于节点特征的保护，类似于LDPGEN中的randomized neighbor list（RNL），AsgLDP提出了randomized attribute lists（RAL），将binary 向量表示的node feature的每一位进行RR得到扰乱后的表示；对于图结构的保护，AsgLDP主要针对节点度的保护，但由于在分布式场景下整个网络的最大度（节点数）是不知道的，传统LDP算法（需要知道value domain）在这种场景下不适应。AsgLDP提出了random jump （RJ）算法来扰乱节点的度：
即给出了一个degree扰动结果的范围，即在degree周围半径r的范围内的整数集合。有p的概率保持原degree，1-p的概率来在离散集合中随机选择。r的选取平衡了隐私保护和效用损失。此算法满足ε-LDP并且对于度是无偏的。server收集各个节点特征和度之后，做每个attribute和degree的无偏频率估计。有了这两个属性后，AsgLDP进行图的生成，使得和原始图有相似的degree分布和attribute联合分布。AsgLDP的模型图如下：
LPGNN (CCS 2021) [7]: node feature和node label是保存在各个客户端，是隐私信息，但是拓扑结构是中心服务器已知的。对于node feature，LPGNN采用multi-bit机制来进行特征的扰动：(1)离散化（2）用RR进行扰动（3）服务器修正以保证无偏性。这也是很多对特征扰动的经典流程。相比于传统的1-bit机制，LPGNN主要做的改进是采样一部分特征纬度进行扰动,并且feature的domain范围是[a,b]而不是[-1,1]的限制。有个节点的特征，server就可以做GNN聚合，LPGNN通过理论推导证明在mean聚合方式下聚合误差和节点的度有关，度越大，误差越小。为了减少误差，LPGNN通过多次聚合来聚合远端邻居（KProp），达到增加节点度的效果。对于节点的label，首先采用RR进行扰动，然后上传到server和feature一样进行多次聚合（KProp）消除噪音，其他细节详细查看论文。模型架构如下图所示：
其中绿色实线代表训练路径，红色虚线代表validation路径。
GAP (USENIX Security 2023) [8]: node-level DP。场景设定为集中式的DP，即server知道所有的图数据，对查询结果进行扰动再发布，使得扰动算法满足edge-level 和node-level DP。直观上讲，GAP对GNN一次聚合后的结果进行扰动，就能让攻击者不能推断出其中一条边是否存在，就能满足edge-level DP。GAP的架构图如下所示：
它分成三个模块，encoder，aggregation和classification。整个模型不是end2end的方式，encoder是一个预训练模型，它仅仅利用节点特征和label训练一个mlp。encoder训练后固定mlp参数，按照图的结构进行邻居聚合（SUM），注意这里邻居聚合是没有参数的，每层聚合的结果用高斯噪声扰乱，并且将每层聚合的结果保存起来（cache）。最后将各层聚合结果经过mlp训练一个分类器。这里不采用end2end的方式是因为减少aggregation过程中隐私预算的分配，如果采用end2end方式，那么聚合结果每次迭代都会变化，那么总的perturbation次数为T*K，T为迭代论数，K为聚合层数；而先训练一个encoder，那么总的perturbation次数为K次，即只需运行一次聚合模块。在inference阶段，transductive 模式下聚合模块只需运行一次，inductive模式下需要多运行一次聚合模块，但由于数据已经不同，所以根据差分隐私并行原理，总的隐私预算不变。GAP也被证明了满足edge-level RDP，并且在bounded-degree的前提下，而且encoder和classifier的参数更新用DP-SGD保护的话，GAP也满足node-level RDP。
四. 总结
从图上的LDP定义上来说，现有方法主要满足edge-level LDP，针对node-level或graph-level LDP 的工作如DP-SGD (TPAMI 2023) [9]还非常少；从保护对象角度来看，现有方法对图结构的保护大多基于LDPGEN中的RNL（RR），对图特征的保护大多基于LPGNN的multi-bit机制（即先离散化再RR），缺少对一些具有实际意义的复杂属性特征保护机制；从图信息聚合方式看，现有方法只是针对简单的SUM或MEAN聚合方式，对于一些更加复杂的聚合方式如GNN中的ATTENTION机制的研究还没有；从下游任务（或图模型）角度来说，现有方法可以分为传统的图上信息统计任务（如degree，modularity）和基于GNN的节点分类、图分类任务等，其中基于GNN的隐私保护研究还处于初步阶段。
五. 参考文献
[1] Mueller T T, Usynin D, Paetzold J C, et al. SoK: Differential privacy on graph-structured data[J]. arXiv preprint arXiv:2203.09205, 2022.
[2] Qin Z, Yu T, Yang Y, et al. Generating synthetic decentralized social graphs with local differential privacy[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 425-438.
[3] Lin W, Li B, Wang C. Towards private learning on decentralized graphs with local differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2022, 17: 2936-2946.
[4] Hidano S, Murakami T. Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy[J]. arXiv preprint arXiv:2202.10209, 2022.
[5] Ye Q, Hu H, Au M H, et al. LF-GDPR: A framework for estimating graph metrics with local differential privacy[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(10): 4905-4920.
[6] Wei C, Ji S, Liu C, et al. AsgLDP: collecting and generating decentralized attributed graphs with local differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2020, 15: 3239-3254.
[7] Sajadmanesh S, Gatica-Perez D. Locally private graph neural networks[C]//Proceedings of the 2021 ACM SIGSAC conference on computer and communications security. 2021: 2130-2145.
[8] Sajadmanesh S, Shamsabadi A S, Bellet A, et al. Gap: Differentially private graph neural networks with aggregation perturbation[C]//USENIX Security 2023-32nd USENIX Security Symposium. 2023.
[9] Mueller T T, Paetzold J C, Prabhakar C, et al. Differentially Private Graph Neural Networks for Whole-Graph Classification[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
转自：“arXiv每日学术速递”微信公众号
如有侵权，请联系本站删除！
