防御链接预测攻击的隐私保护方法

韩学波，王利娥，黄丝曼，刘 鹏，李先贤

(广西师范大学 广西多源信息挖掘与安全重点实验室，广西 桂林 541004)

0 引 言

针对采用深度学习方法预测链接带来的隐私问题，目前只有极少的研究借鉴深度学习的对抗攻击方法，将生成对抗样本的方法用于欺骗深度学习的链接预测方法，进而对敏感链接预测错误，从而保护敏感链接的隐私。但是目前提出的方法的计算复杂度较高，只适用于小型社交网络。随着大数据的发展，目前社交网络的规模变得越来越大，针对这一不足，本文提出一种基于积分梯度的局部扰动算法，该算法通过划分敏感链接的闭合子图来缩小扰动范围，只计算扰动范围内的链接的积分梯度，降低了计算复杂度，适用于大规模的社交网络。该算法将深度学习模型对扰动图中敏感链接的错误预测作为结束扰动的判断依据，不需要提前设置扰动链接的数量，从而减少了扰动链接数量，提高了隐私保护发布图的效用性。该算法能够防御基于相似性和深度学习的链接预测算法，具有普适性。

1 相关工作

链接预测攻击采用现有的链接预测方法[1]发现数据发布者隐藏的敏感链接信息。防御链接预测攻击的隐私保护方法一般针对需要保护的敏感链接信息，采用删除、扰动等方法阻止敏感链接被预测出来[2]。目前，主要的链接预测算法都是基于网络结构设计的，因此数据发布者可以在原始网络中添加干扰，降低链接预测攻击导致的敏感链接泄露的风险。但是，发布社交网络数据的主要目的是进行有价值的研究分析，因此需要限制链接的扰动程度，确保发布网络数据的效用性。

在链接预测算法的研究中，基于相似性的算法是最主流的链接预测方法，它假定两个节点越相似，它们越有可能产生联系。根据相似性计算需要的邻居最大跳数进行分类，分为一阶、二阶和高阶启发式算法。一阶启发式算法只涉及两个目标节点的单跳邻居，例如，共同邻居CN(common neighbor)算法[3]假设两个节点的共同邻居越多，那么它们越容易产生链接。优先连接PA(preferential attachment)算法[4]认为节点更有可能和度数较高的节点产生链接。二阶启发式算法根据目标节点的两跳邻居计算相似度，例如，AA(adamic-adar)算法[5]根据共同邻居节点的度为每个节点赋予一个权重值，该权重等于该节点度的对数的倒数。于是AA算法计算出的相似值就等于两个节点的所有共同邻居的权重值的和。资源分配RA(resource allocation)算法[6]的形式与AA算法差不多，不同的是RA的权重形式变成了节点的度的倒数。高阶启发式算法根据目标节点的三跳及以上邻居计算相似性，如局部路径指标LP(local path)[7]在二跳邻居的基础上考虑三跳邻居。Katz算法[8]是基于全局网络的算法，根据整个网络计算相似度，全面考虑节点在网络中的路径信息，对网络中两节点之间所有路径做加权求和，它的缺点是计算复杂度太高。目前已经有一些工作提出了防御基于相似性的链接预测算法的隐私保护方法。文献[2]针对基于相似性的链接预测算法RA，提出一种启发式和进化扰动算法，降低了RA算法预测敏感链接的性能。文献[9]针对链接预测能够暴露两人的敏感关系的情况，提出一种社交用户逃避链接预测算法的隐私保护方法。文献[10]通过删除链接来攻击基于相似性的链接预测。

近年来，随着深度学习不断的发展，逐渐促进了链接预测性能的提高。文献[11]提出了一种网络嵌入方法DeepWalk，通过截断随机游走学习出网络节点的向量表示。文献[12]提出一种node2vec方法，改进了DeepWalk方法的随机游走生成过程。文献[13]将自编码器迁移到了图领域，提出了一种用于链接预测任务的图自动编码器GAE(graph auto-encoders)模型，这一模型用已知的图数据经过编码(图卷积)学到节点向量表示的分布，在分布中采样得到节点的向量表示，然后进行解码(链接预测)重新构建图。文献[14]提出一种基于图神经网络的链接预测DGCNN模型，通过对闭合子图的分类来预测敏感链接是否存在，提高了基于相似性的预测链接的准确度和通用性。

攻击者采用基于深度学习的链接预测算法，可以更精确预测出社交网络用户的敏感关系，之前针对相似性链接预测的防御方法并不能起到很好的防御效果，基于深度学习的链接预测方法给隐私保护方法的研究带来了新的挑战。由于深度学习的脆弱性，人们针对深度学习的对抗攻击展开了一系列研究，本文借鉴深度学习的对抗攻击方法，将生成对抗样本方法用于防御基于深度学习的链接预测，使深度学习的链接预测方法对敏感链接预测错误，从而保护敏感链接的隐私。其中，文献[15]对图深度学习的鲁棒性及对抗攻击进行了开创性研究，针对图神经网络模型分别提出了基于强化学习、遗传算法和梯度的对抗攻击方法。文献[16]将生成对抗样本的方法用于保护用户的链接隐私，假设数据发布者对图自动编码器GAE模型有充分的了解，针对图自动编码器GAE模型提出迭代梯度攻击(IGA)进行隐私保护，降低了GAE模型对特定敏感链接的预测性能，同时也可以作为一种衡量链接预测算法的鲁棒性的方法。然而这种迭代梯度攻击方法有两个不足：①这种方法需要通过计算图中所有链接梯度来确定扰动链接，同时又需要迭代计算梯度，从而导致这种方法的计算复杂度比较高，不适用于大规模网络；②这种方法需要提前设置算法的迭代次数和每次迭代中链接扰动的数量，缺乏扰动过程中对扰动效果的判断依据。

本文针对目前防御链接预测攻击的隐私保护方法的不足，提出一种基于积分梯度的局部扰动方法，这种方法不需要提前设定链接扰动数量，适用于大规模网络，不但能够保护用户的链接隐私，而且可以保证发布图的效用性。本文的主要贡献如下：

(1)本文划分敏感链接的闭合子图作为扰动范围，只计算扰动范围内链接的积分梯度，降低了计算复杂度，适用于大规模网络的链接隐私保护；

(2)本文将链接预测模型对扰动图中敏感链接的错误预测作为结束扰动的判断依据，不需要提前设置扰动链接的数量，减少了链接扰动数量，提高了隐私保护发布图的效用性；

(3)本文通过敏感链接的保护成功率评估敏感链接的实际保护效果，利用平均链接修改数量评估发布图的效用性。通过针对主流链接预测算法的防御实验，验证本文提出的隐私保护方法的普适性。

2 问题定义和预备知识

2.1 问题定义

定义1 链接预测：给定原始图G=(V,E)，V表示所有节点的集合，E表示所有链接的集合。E分为两组，Eo是可以观察到的链接，Eu是需要预测的未知链接，其中Eo∩Eu=∅，Eo∪Eu=E。 链接预测是基于V和Eo的信息来预测Eu。

(1)

其中，Eβ+∪Eβ-=Eβ，Eβ+∩Eβ-=∅，Eβ-⊂Eo，Eβ+⊂(Ω-E), Ω={(i,j),(i,j)∈V,i≠j}。

(2)

其中， I(·)∈{0,1} 是一个指示函数(indicator function)，m是链接修改的最大数目，Eβ=Eβ+∪Eβ-。

2.2 图自动编码器GAE模型

GAE模型是一种主流的基于深度学习的链接预测方法，通过两层图卷积网络从距离中心节点最多2跳的节点信息中学习节点表示，极大提升了链接预测的性能。本文以GAE模型为例，将GAE模型作为敏感链接预测的攻击工具，根据GAE模型提出一种敏感链接的隐私保护方法。下面介绍一下GAE模型。

(1)计算GCN层提取的每个节点的嵌入向量矩阵Z

(3)

(2)计算所有链接的概率

As=s(ZZT)

(4)

其中，s是sigmoid函数，As是分数矩阵, 当分数矩阵中的分数元素大于阈值0.5时，预测对应的链接存在，反之不存在。

(3)为了训练模型，构造监督训练的交叉熵损失函数L

(5)

ω是加权交叉熵的权重，用于防止对负样本的过度拟合，因为在现实世界的网络中，不存在的链接通常比存在的链接多得多。

2.3 积分梯度

对于给定的模型F∶Rnn→[0,1]， 其中x∈Rn是输入，x′是基线输入(例如，图像数据的黑色图像)。计算从基线输入x′到输入x的直线路径的所有梯度，通过累积这些梯度得到积分梯度。输入x的第i个特征的积分梯度(IG)的计算公式如下

(6)

积分梯度可以通过求和来有效地逼近，利用足够小的间隔对从基线输入x′到输入x的直线路径上的点的梯度求和，积分梯度的近似计算公式如下

(7)

3 隐私保护方法

本文提出一种基于积分梯度的局部扰动方法，欺骗深度学习对敏感链接做出错误预测，从而防止敏感链接的隐私泄露。该方法的主要思想是：首先划分敏感链接的二阶闭合子图作为扰动范围，只扰动二阶闭合子图中的链接，就会改变敏感链接的邻居节点，导致GAE模型提取错误的邻居节点信息，然后计算扰动范围内每个链接的积分梯度，衡量这些链接修改对敏感链接损失函数的影响，最后按照积分梯度从大到小的顺序扰动链接，当链接预测模型对扰动图的敏感链接预测错误时结束扰动。

下面只介绍单个敏感链接的保护算法，由于本文采用局部扰动的方式，当需要同时保护多个敏感链接时可以对该算法采用并行计算，减少算法的运行时间。

3.1 确定扰动范围

本文将原图G中敏感链接 (i′,j′) 的节点对i′和j′的直接和间接邻居节点以及它们之间的链接构成的闭合子图Gh作为扰动范围，扰动范围中的链接可以任意修改。GAE模型使用两层GCN提取距离中心节点最多2跳的邻居节点信息，然而GAE模型判断邻居节点的依据是节点间是否存在链接，所以扰动敏感链接的闭合子图，就会改变敏感链接的邻居节点，导致GAE模型错误的提取邻居节点信息，从而提高敏感链接预测错误的概率。文献[14]验证了目标链接的闭合子图包含了相似性算法预测目标链接所需的大部分结构信息，而闭合子图以外的结构信息对于目标链接预测的帮助很小。所以本文只将敏感链接闭合子图的所有链接作为扰动范围，使得扰动更有针对性，减少了计算复杂度。

3.2 构造敏感链接的交叉熵损失函数

(8)

其中，Ai′j′为敏感链接 (i′,j′) 在原图中的真实值，Ai′j′∈{0,1}， 其中0代表敏感链接不存在，1代表敏感链接存在；Yi′j′(A) 为GAE模型敏感链接存在的概率值。

3.3 确定扰动链接的顺序

因为之前的研究中图神经网络的梯度计算次数只有一次，梯度的计算结果不准确，所以文献[18]在图数据中引入积分梯度，提高了梯度计算的准确性，表明积分梯度可以准确反映扰动链接对图神经网络模型输出和损失函数的影响。本文受到这一研究的启发，将积分梯度用于衡量扰动链接 (i,j) 对敏感链接损失函数的影响，扰动链接的积分梯度值越大，说明这个链接对敏感链接的损失函数的影响越大。因为积分梯度可以一次计算出链接对敏感链接损失函数的影响，所以本文根据积分梯度对扰动范围中除敏感链接外的所有存在链接和不存在链接进行从大到小排序，从而确定扰动链接的顺序。

根据链接是否存在，分为两种计算积分梯度的方法，具体如下：

(9)

(10)

3.4 扰 动

积分梯度只是反映了每个链接对敏感链接损失函数造成的影响，但是这种影响会导致两种情况，一种情况是使敏感链接的损失函数变大，另一种是使敏感链接的损失函数变小，本文要想增大GAE模型预测敏感链接的错误概率，就应该选择敏感链接损失函数值最大化的扰动链接。积分梯度分为正梯度和负梯度，正梯度意味着目标损失最大化的方向是在邻接矩阵的相应位置增加值，负梯度则是在邻接矩阵的相应位置减小值。由于网络数据是离散的，我们只允许添加或删除链接。因为积分梯度有正负，所以本文按照积分梯度的绝对值从大到小排序，对原图进行迭代扰动，算法的伪代码展示了每一次迭代扰动的具体过程。

本文算法的伪代码如下。

算法1：LDIG算法

输入：原图G，计算积分梯度的步骤数m，迭代次数K，扰动链接数量n

(1)确定敏感链接 (i′,j′) 的闭合子图；

(3)输入原图训练GAE模型；

(4)计算闭合子图中所有链接的积分梯度；

(5)IfAij=1；

(6)Ab=0，计算IG(i,j)

(7)Else

(8)Ab=1，计算IG(i,j)

(9)根据积分梯度的绝对值对扰动范围中除敏感链接外的所有链接从大到小排序；

(10)确定最大积分梯度IG_max和对应的链接 (i,j)；

(11)初始化扰动数量n=0；

(12)通过迭代扰动来逐渐实现模型的错误预测，当模型对敏感链接预测错误时，结束扰动；

(14) ifAij=0 and IGmax(i,j)>0

(15)Aij=1， IGmax(i,j)=0

(16) else ifAij=1 and IGmax(i,j)<0

(17)Aij=0， IGmax(i,j)=0

(18) Else

(19) continue

由于本文提出的隐私保护方法只考虑对网络结构进行扰动，所以这种方法能够有效防御只考虑网络结构进行预测的链接预测方法，针对综合考虑节点属性和网络结构的方法也有一定的保护效果，不适用于只考虑节点属性的方法。因为只考虑节点属性的链接预测方法是很少的，大部分的链接预测方法都要考虑网络结构，所以本文提出的隐私保护方法具有一定的普适性。

4 实 验

我们的实验环境为：操作系统为ubuntu18.04 LTS；CPU核数为8核，CPU频率为2.50 GHz，型号为Intel(R) Xeon(R) Silver 4215；GPU的显存为16 160 M，型号为Tesla V100-FHHL。

4.1 数据集

为了更全面测试本文提出的算法性能，本文选择了不同规模和不同类型的网络数据集，见表1，这些数据集都是无向图。

表1 数据集信息统计

Facebook是一个大型社交网络数据集，其中节点代表用户，链接是他们的友谊关系。Cora和Citeseer是引文网络数据集，每个节点表示一篇科学论文，节点之间的链接表示两篇论文存在引用关系。Pumbed是一个大型生物医学方面的引文网络数据集。

4.2 实验方法

本文随机选择整个网络链接集中10%的链接作为需要保护的敏感链接测试集，验证防御方法对敏感链接的保护效果，其它的链接作为训练集。

我们比较了3种防御链接预测攻击的隐私保护方法。

(1)分布估计算法

分布估计算法EDA(estimation of distribution algorithm)是文献[2]针对RA算法提出的一种进化扰动算法，根据个体染色体的适应值对染色体进行抽样估计,然后根据统计学方法估计删除链接和添加链接的概率分布，最后根据各自的分布产生n个染色体。本文在实验中将敏感链接的链接度k设置为算法的迭代次数。

(2)迭代梯度攻击算法

迭代梯度攻击算法IGA(iterative gradient attack)是文献[16]针对GAE模型提出的一种基于梯度的对抗攻击方法，通过迭代计算梯度产生扰动。IGA算法分为无限攻击和单节点攻击，其中的无限攻击可用于数据发布，本文与IGA算法的无限攻击作对比。无限攻击没有任何修改链接的限制，唯一的限制是修改链接的总数。本文在实验中将保护敏感链接的链接修改数量设置为敏感链接度k， 其中链接度k是构成链接的两个节点的度的总和，将k设置为算法的迭代次数，每次迭代修改的链接数量n设置为1。

(3)LDIG算法

由于本文提出的LDIG算法不提前设定修改链接的数量，为了与之前的两个算法进行合理对比，当LDIG算法的链接修改数量小于敏感链接度k时才确定为成功保护，其中计算积分梯度的步数m设置为10。

4.3 评价指标

(1)保护成功率

保护成功率是模型错误预测敏感链接的数量与所有敏感链接的比例。本文通过保护成功率评估隐私保护方法的实际效果。保护成功率越大，说明隐私保护方法对敏感链接的保护效果越好。

(2)平均链接修改数量

平均链接修改数量是导致模型错误预测敏感链接的平均扰动链接的数量。本文利用平均链接修改数量评估发布图的效用性，平均链接修改数量越小，隐私保护发布图的效用性越好。

4.4 隐私保护方法的普适性

尽管本文提出的算法可以抵御链接预测GAE的攻击，但是攻击者也可以使用其它链接预测方法，因此，了解LDIG算法的普遍适用性是十分重要的。本文通过其它链接预测算法的防御实验，验证LDIG算法的普遍适用性。由于链接预测算法的种类众多，同时基于网络结构相似性和基于深度学习的方法是目前比较流行的方法，所以本文采用这两类中比较有代表性的算法。表2为选出的具有代表性的链接预测算法的预测性能比较。

4.5 实验结果

表3给出了LDIG、EDA和IGA算法的保护成功率和平均链接扰动数量。从表中可以看出，LDIG算法的整体性能不错。

本文首先介绍一下LDIG算法与IGA的实验对比结果，在保护成功率方面，LDIG算法在4个数据集的平均值分别比IGA高0.07%、0.12%、0.04%和1.04%，其中LDIG算法防御GAE、PA、CN和RA算法的成功率比IGA算法高，防御LP、LRW、node2vec算法的成功率与IGA算法不相上下，但是防御Katz算法的成功率不如IGA。在平均扰动链接数量方面，LDIG算法在4个数据集的平均值分别比IGA少6.07、1.04、1.09和1.84。这表明LDIG算法在保证敏感链接保护效果的同时，减少了网络的扰动链接数量，提高了发布数据的效用性。这是因为LDIG算法只考虑局部网络信息，所以更有针对性的防御链接预测攻击，同时减少了链接扰动数量，而IGA算法考虑全局结构信息，更利于防御基于全局网络的Katz算法，但是扰动链接的数量比较多。

表2 各种链接预测算法的预测性能比较

表3 不同隐私保护算法的防御效果

本文然后介绍一下LDIG算法与EDA的实验对比结果，在保护成功率方面，LDIG算法在4个数据集的平均值分别比EDA高6.88%、7.82%、5.74%和9.56%，其中LDIG算法防御8种链接预测的保护成功率都高于EDA。在平均扰动链接数量方面，LDIG算法在4个数据集的平均值分别比EDA多0.39、0.55、0.48和0.98。这表明LDIG算法比EDA算法的敏感链接保护效果提高了不少，同时在可接受的范围内增加了链接扰动数量，所以LDIG算法从整体上优于EDA算法。这是由于EDA算法考虑一跳邻居的信息，LDIG算法在一跳邻居的基础上考虑二跳邻居的信息，所以LDIG算法防御高阶邻居的链接预测的成功率比EDA高，同时增加了链接扰动数量，由于LDIG算法能够自动判断扰动效果来结束扰动，所以这个算法能够在可接受的范围内增加链接扰动数量。

4.6 算法复杂度

如表4所示，本文比较了3个算法保护单个敏感链接的平均运行时间，LDIG算法在4个数据集中的平均时间分别比IGA少1175.58 s、510.35 s、502.01 s和5708.62 s，远远小于IGA。LDIG算法在4个数据集中的平均时间分别比EDA算法多2.91 s、1.2 s、1.2 s和14.58 s，LDIG算法比EDA算法增加的时间很少，增加的时间在可接受范围内。这表明LDIG算法的时间复杂度比较低。这是由于LDIG算法划分敏感链接的二阶闭合子图作为扰动范围，只计算扰动范围中的链接的积分梯度，与IGA算法相比，大大降低了计算复杂度。

表4 算法平均运行时间/s

5 结束语

本文针对采用深度学习预测链接导致敏感关系隐私泄露的问题，提出了一种基于积分梯度的局部扰动算法，欺骗深度学习对敏感链接预测错误，防止敏感链接的隐私泄露。该算法适用于大规模的社交网络数据，同时减少了扰动链接的数量，提高了发布数据的效用性。防御主流链接预测算法的实验结果表明，这种算法可以防御主流的链接预测攻击，具有普适性。本文没有考虑基于节点属性的链接预测方法，而节点属性也是社交网络中重要的一部分，因此接下来研究如何防御基于节点属性的链接预测攻击。