面向链接预测的本地差分隐私图数据建模方法

韩启龙 吴晓明

摘  要：针对工业企业图数据链接预测过程中，节点间的敏感数据面临隐私泄露的问题，以本地差分隐私理论为基础，从链接预测任务表现的角度分析了现有的图数据建模方法在隐私保护上的缺点和不足。提出在个性化采样技术的随机响应机制，减少用户端噪声添加，同时结合两轮数据收集的子图划分策略，保留原始图数据中子图聚集特征，最终实现了一种个性化采样随机响应本地差分隐私（Personalized Sampling Randomized Response Local Differential Privacy，PSRR-LDP）图数据建模算法，理论证明PSRR-LDP算法满足ε-边本地差分隐私。仿真实验结果表明，PSRR-LDP算法在保证隐私的同时具有更优的链接预测效果。

关键词：隐私保护技术；链接预测；本地差分隐私；个性化采样；图数据收集

DOI：10.15938/j.jhust.2023.05.007

中图分类号： TP391

文献标志码： A

文章编号： 1007-2683（2023）05-0051-10

Local Differential Privacy Graph Data Modeling Method for Link Prediction

HAN Qilong1，  WU Xiaoming2

（1.College of Computer Science and Technology， Harbin Engineering University， Harbin 150001， China;

2.Law School， Harbin University of Commerce， Harbin 150028， China）

Abstract：To solve the problem of node sensitive link privacy being exposed in the process of link prediction on industrial business graph data， according to the theory of local differential privacy， the shortcomings of the existing graph privacy protection technology are analyzed from the perspective of link prediction task performance. Based on the existing randomized response mechanism， it introduces the personalized sampling technology to reduce the noise addition on the user side. At the same time， combined with the subgraph partitioning strategy of two rounds of data collection， the subgraph cluster feature of the original graph is retained. Finally， a personalized sampling randomized response local differential privacy （PSRR-LDP） graph data perturbing algorithm was implemented， and the PSRR-LDP algorithm is theoretically proved to satisfy the ε-edge Local differential privacy. The simulation experiments show that the PSRR-LDP algorithm has better link prediction performance while ensuring privacy.

Keywords：privacy-preserving techniques; link prediction; local differential privacy; personalized sampling; graph data collection

收稿日期： 2022-05-17

基金項目： 国家重点研发计划（2020YFB1710200）；国家自然科学基金（61872105）；黑龙江省哲学社会科学研究规划项目（19FXE275）.

作者简介： 吴晓明（1976—），女，副教授，硕士生导师.

通信作者：

韩启龙（1974—），男，教授，博士研究生导师，E-mail：hanqilong@hrbeu.edu.cn.

0  引  言

随着互联网、大数据、人工智能等信息技术的快速发展，社交网络、工业互联网等应用已经广泛深入到人们的生产生活中。图数据作为数据管理与分析的重要手段，因其网络结构特征及科学运算的模式，图数据挖掘已经成为当今学术界与工业界研究的热点问题之一。链接预测（link prediction，LP）是图数据挖掘的重要部分，可在现有图数据基础上预测未来节点间的链接关系［1］，在社交网络、推荐系统、工业互联网等网络服务中有着广泛的应用 ［2-6］。早期的探索式LP算法基于目标节点对的局部特征判断目标链接是否会在将来出现［7］。最近，文［8］提出目标节点对的局部封闭子图包含足够的用于链接预测的特征同时提出可以使用图神经网络的方式提取这样的特征。

近年来隐私泄漏事件的频繁发生，如Facebook隐私信息泄漏事件、澳大利亚电信公司Optus数据泄漏事件等，用户如何在使用网络服务的同时保证敏感信息不被泄漏已经获得了广泛关注［9-16］。传统的隐私保护技术，如k-邻算法［10］，k-度匿名［11］，差分隐私［12-14］等，多是基于中心化场景下开展研究。这种方法要求具有可信第三方服务提供商，一旦服务提供商不可信或发生隐私泄漏，则无法保障用户的隐私信息，所以研究者们基于本地差分隐私（local differential privacy，LDP）提出了LDPGen［15］、RABV（randomized adjacency bit vector） ［16］和GraphLDP［17］等去中心化技术解决中心化隐私保护中存在的不足。本地差分隐私技术通过在用户端进行数据扰动保护敏感信息，然后将扰动后的数据发送给数据收集者，即使数据收集者不可靠，仍可有效保护用户的敏感数据。LDP已经被成功用于各种数据分析任务中保护隐私，比如频率估计［18-20］，频繁项集挖掘［21］以及地理位置隐私保护［22］。

当前的图数据LDP隐私保护工作主要分为图数据合成与图中统计量无偏估计两大分析任务。LDPGen算法采用满足LDP的方法收集节点度信息来合成图，在保留图拓扑特征的同时保护隐私，但为了平衡整体性统计特征和边粒度统计特征，算法损失了图中一些重要的局部特征。GraphLDP使用安全多方计算赋予节点假名从而将节点间连接假名化同时结合LDP算法收集节点的度，数据收集者根据假名化的节点间连接和节点的度重构一个保护隐私的图结构。以上的工作都是关于图数据合成，而另一类重要的任务是图中统计量的无偏估计。LF-GDPR（local framework for graph with differentially private release）［15］算法在满足LDP条件下对图中的统计量进行无偏估计以达到隐私保护效果。文［23］提出了满足LDP条件下图中的三角计数和k-星计数方法。节点是否存在边的概率主要依赖于图的局部特征与图拓扑结构［8］，因此，图局部特征的损失会极大地影响LP算法对节点间是否存在边的判断，同样，在收集图数据时不考虑图的拓扑结构也将对是否存在边的结果产生重要影响。

综上，现有的图LDP算法存在破坏图拓扑结构、局部特征损失等问题。本文提出一种个性化采样随机响应的本地差分隐私保护链接预测算法，利用个性化采样随机响应机制，对用户的每一条数据使用不同的采样概率，减少用户端噪声添加，结合两轮数据收集方式与图划分机制，保留原始图中边分布的特征，理论证明了算法满足LDP隐私，通过对比实验分析，验证了本文算法在图数据链接预测任务中有更高的准确性。

1  图本地差分隐私链接预测

1.1  本地差分隐私

为了解决第三方服务器可能的隐私泄露，在LDP中，用户对敏感数据使用满足LDP机制的本地扰动，然后发送给服务器。在图LDP中包括边差分隐私、节点差分隐私，其中边差分隐私对图中任意一条边的添加或删除进行保护，节点差分隐私对任一节点的增删及其相关边进行保护。

设图中节点的集合V={v1，…，vn}，其中n为节点数量。节点vi与其他节点间的關系表示为一个n维位向量vi={b1，…，bn}，其中bj=1，j∈{1，…，n}，当且仅当节点vi与vj有边，否则，bj=0。节点位向量形成用户邻接矩阵M={v1，…，vn}。

定义1  节点本地差分隐私［15］。随机算法A满足ε-节点本地差分隐私（ε-node LDP），如果对任意两个相邻的节点位向量v与v′，有Pr（A（v）=s）Pr（A（v′）=s）≤eε，其中，s∈range（A），称A满足ε-node LDP。

定义2  边本地差分隐私［15］。随机算法A满足ε-边本地差分隐私（ε-edge LDP），如果对任意两个相邻的节点位向量v与v′，这两个相邻位向量中只有一位不同，有Pr（A（v）=s）Pr（A（v′）=s）≤eε，其中，s∈range（A），称A满足ε-edgeLDP。

定理1  序列组合原理［15］。若有n个独立的随机算法Ai（1≤i≤n），都分别满足εi-node（edge） LDP，则算法Ai的组合仍然满足（∑εi）-node（edge）LDP。

除了序列组合原理，LDP也内在的拥有后处理特性［24］。节点LDP相邻数据库定义在位向量的任意个比特位上，边LDP的相邻数据库定义在节点位向量的某一位上。通常情况下，由于节点LDP也实现了边LDP，节点LDP相比边LDP具有更强的保护程度。在具体的实际应用场景中，选择合适的隐私保护强度更有意义。如在社区发现与三角计数应用中，采用边LDP在保证图中边的不可区分性的同时，又具有较好的数据可用性。因此，在图数据挖掘中，多采用边LDP机制进行对敏感数据的保护［15］。

1.2  满足LDP的图链接预测

设有简单无向图G=（V，E），其中V为节点集合，E为边集合，图中不包括重边和自环。M为图G的邻接矩阵，如果（i，j）∈E，则Mi，j=1，否则Mi，j=0。U表示节点间所有|V|·（|V|－1）2个可能的链结，其中|V|为集合V中的节点数量，则U-E表示所有当前不存在的边。假设一些边会在将来出现，链接预测的任务即是发现这些可能出现的边。非隐私保护的链接预测算法能给出目标链接在将来可能出现的概率。

如果有一个非隐私保护的链接预测算法B，为了满足边LDP，使用一个满足边LDP的扰动算法A在用户本地扰动数据，然后在收集端聚集所有用户扰动后的数据获得隐私保护的图G～=（V，E～），之后使用非隐私的链接预测算法B去计算目标链接的存在概率。根据LDP的后处理性质［23］，此时算法B的输出满足LDP，因此能保护个人隐私。

2  PSRR-LDP图生成算法

2.1  个性化采样随机响应算法

随机化邻居列表算法是一个直接使用随机响应机制（rondimized response mechanism， RR）满足LDP的图隐私化算法［15］。给定一个节点的位向量vi={b1，…，bn}，以及隐私预算ε，根据式（1）获得扰动后的位向量i={1，…，n}。

j=bjw.p.eε1+eε

1－bjw.p.11+eε（1）

如果原始图中边密度为η，则收集的图中真实边比例为ηpηp+（1－η）（1－p），其中p=eε1+eε。假设节点vi的邻居节点数为mi（1≤mi≤n-1），收集到的图中真实边比例在期望上应为

∑ni=1mip∑ni=1mip+∑ni=1（n－mi－1）（1－p）

即攻击者在收集到的边中推测出真实边的概率，由于在社交网络等实际应用场景中，图通常具有稀疏性，攻击者推测成功的概率较低。但直接采用RR方法对图进行重构将导致生成图中边密度的快速膨胀，重构图中将会包含过多的假边，从而降低图的可用性。如，在Facebook数据集中，原始边密度为，η=0.0108，若隐私预算ε=1，采用RR算法状态保留概率p=e11+e1≈0.7310，扰动后的边密度为≈0.2739，是原始边密度的25.36倍。此外，在无向图上采用经典的RR机制虽然可实现ε-edge LDP，但因为用户会对同一条边进行两次独立扰动，对收集者只能实现2ε-edge LDP，同时，每个用户独立随机化发送所有位向量给第三方收集者，也将导致较高的计算与通信开销。

针对这些不足，本文提出个性化采样随机响应方法解决边密度膨胀问题，并根据矩阵对称性降低了计算与通信开销。

假设用户i表示为图节点vi，同时与其他用户间的连接关系表示为位向量vi={b1，…，bn}。假设r∈（0，1）为扰动后图中真实边的比例期望，ε为随机响应的隐私预算，m为邻居节点数量。为保证对数据收集者也满足ε-edge LDP，根据邻接矩阵的对称性，算法只需处理上三角矩阵。邻接矩阵每行对应一个节点的位向量，仅处理位向量中位置在［（i+1），（i+1+t mod n）］区间的元素，对前1≤i≤n2个节点，其中t=n2，否则t=n－12。将位向量vi中采样的子集表示为Φi，则位向量中每个位bj的采样概率πj如式（2）所示：

πj=1如果bj=1

min（meε（1－r）r（t－m），1）如果bj=0（2）

获得子集Φi后，根据式（1）对子集中的位进行扰动，然后将扰动后比特值对应为1的索引发送给收集者。数据收集者根据索引值将邻接矩阵对应位置填充为1，然后复制对称位置的值，并对缺失位置用0进行填充，最终获得完整的邻接矩阵。

算法1：个性化采样随机响应算法

输入：原始用户位向量集合{v1，…，vn}

隐私预算ε

扰动后真实边比例期望r

输出：

扰动后的邻接矩阵M～

//用户端

1）用户i计算传输范围大小t，如果i≤n2则t=n2， 否则t=n－12;

2）每個用户i在位向量vi上统计在传输范围［（i+1），（i+1+t mod n）］内的邻居节点数量m;

3）遍历用户位向量vi中在传输范围内的每个比特bj， 使用式（2）计算每个比特的采样概率πj;

4）对需要处理的比特bj根据对应的采样概率πj进行伯努利采样，将采样获得的比特值bj和对应的索引j记录进集合Φi中;

5）遍历集合Φi中的每个比特值bj进行如公式（1）的随机响应得到扰动后的比特值j

6）用户将对应扰动后比特值为1的索引发送给数据收集者;

//收集端

7）初始化一个n×n的全零矩阵M～;

8）每个用户i的位向量vi对应矩阵中M～的一行，收集端根据每个用户发送的索引集合将矩阵M～中对应位置的元素赋值为1;

9）以矩阵M～的主对角线为对称轴复制对称位置的元素;

10）返回处理后的矩阵M～。

在算法中邻接矩阵的每一个对称位置的元素只被扰动一次，因此对收集者也满足ε-edge LDP。邻接矩阵中所有被处理的位构成了一个上三角矩阵，其中真实边的比例期望为r，将上三角矩阵元素复制到下三角矩阵中，则在图中全部的真实边比例期望仍为r。

2.2  基于子图划分的图生成算法

在实际应用中多数图是低秩的，即图中有明显的多个子图聚类的特点。同时社区结构有助于链接预测［25］。对子图中某个特定的节点，与其他子图所链接的边数量通常是不同的，因此在算法中考虑到子图间链接特点设置不同的采样概率，可以在图重构中保留原始图的子图聚类特征，从而增强后续链接预测算法的正确性。

提出了基于子图划分的个性化随机响应图生成算法。给定总的隐私预算ε和隐私分配系数α，将隐私预算分为两个部分ε1和ε2，其中ε1=αε，ε2=（1-α）ε。在第一轮数据收集中，因为数据收集者没有关于原始图的信息，仅发送ε1给每个用户，用户根据算法1处理本地数据然后发送给数据收集者，收集者根据收到的数据形成邻接矩阵M～1，然后收集者使用子图发现算法，本文使用Louvain子图发现算法［26］，获得初步的子图划分C={c1，c2，…，ck}，其中k为子图的数量，且每个节点只属于一个子图。在第二轮的交互中，收集者发送子图划分C和隐私预算ε2给每一个用户，用户i根据收到的信息将位向量中的位划分到相应的子图，然后计算每个节点在相应子图的邻居节点数量Δi={δi1，…，δik}以及子图的大小Si={si1，…，sik}。假设位bj属于子图cj，则位bj被采样的概率可根据式（3）计算。

πij=1如果 bj=1

min（δicjeε2（1－r）r（sicj－δicj），1）如果 bj=0（3）

对于同一个子图的位设置相同的采样概率，之后采样获得对应的子集Φi，之后使用式（1）进行扰动，并将扰动后的结果发送给数据收集者，收集者形成邻接矩阵M～2。

算法2：基于子图划分的图生成算法

输入：原始用户位向量集合{v1，…，vn}

隐私预算ε

扰动后真实边比例期望r

输出：扰动后的图邻接矩阵M～2

//第一轮数据收集

1）计算ε1=αε，ε2=（1-α））ε

2）使用隐私预算为ε1的算法1获得M～1然后收集者使用社区发现算法在邻接矩阵M～1上获得子图划分C={c1，c2，…，ck}

//第二轮数据收集

//用户端

3）用户i计算传输范围大小t，如果i≤n2则t=n2， 否则t=n－12;

4）遍历用户位向量vi在传输范围［（i+1），（i+1+t mod n）］内的每个比特bj，然后将比特值bj和对应的索引j记录到集合T中;

5）遍历子图划分C中的每个子图c，计算每个子图在传输范围内的节点数量sic=|c∩T|然后记录到集合Si={si1，…，sik}以及计算c∩T中比特值为1的元素数量保存到Δi={δi1，…，δik};

6）遍历集合T根据等式（3）计算每个比特bj∈T被采样的概率，然后根据概率进行伯努利采样如果被采样中则记录下被采样元素的比特值bj和对应的索引j到集合Φi中;

7）使用隐私预算为ε2的随机响应算法扰动集合Φi中的每个比特值，然后将扰动后比特值为1的元素对应的索引发送给数据收集者；

//数据收集端

8）和算法1类似，首先初始化一个n×n的全零矩阵M～2，然后根据每个用户发送的索引集合填充矩阵M～2对应位置的元素为1，之后沿主对角线复制邻接矩阵M～2对称位置的元素，最后返回M～2。

2.3  算法隐私分析

设有节点位向量v={b1，…，bn}与隐私預算ε。v′={b′1，…，b′n}与v={b1，…，bn}是邻居数据库，它们只相差一条边τ，不失一般性，假设b′n≠bn使用符号PRR表示先采用个性化采样获得一个子集，然后在采样后的子集上使用随机响应机制这个过程。符号Ψ表示采样过程，RR表示随机响应过程。根据边LDP定义和文［15］有如下定理。

定理1［15］  给定任意两个邻居节点位向量v与v′，它们只差一条边，在v上使用隐私预算ε的随机响应机制，则如下两个不等式成立：

Pr［RR（v）=o］Pr［RR（v′）=o］≤eε， Pr［RR（v′）=o］PR［RR（v）=o］≤eε（4）

其中o∈range（RR）表示随机响应机制任何可能的输出结果。

文［15］中证明了当在v上使用隐私预算为ε的随机响应机制扰动后的结果满足ε-edge LDP。

定理2  给定任意的用户位向量v，其每一个位都具有特定的采样概率0≤π≤1，依据概率π在v中进行一次采样获得的子集Φ，在Φ上以隐私预算ε进行随机响应的结果满足ε-edge LDP。

证明：根据边本地差分隐私的定义，为了证明PRR机制满足ε-edge LDP，需要证明Pr［PRR（v）=s］≤eεPr［PRR（v′）=s］。其中s∈range（PRR）表示PRR机制任何可能的输出。而Pr［PRR（v）=s］可以重写为如下形式：

Pr［PRR（v）=s］=Pr［Ψ（v）=Φ］Pr［RR（Φ）=s］

其中：Φ表示从v中采样出的比特子集；Φ′表示从v′中采样出的比特子集。v与v′的采样结果可以分为包括或不包括边τ这两种情况v－τ={b1，…，bn－1}，表示从v或者v′中去除边τ之后的数据集。Φ-τ和Φ′-τ分别表示从v－τ和v′－τ中的采样结果。因为v和v′只有边τ不同，所以v－τ=v′－τ因此存在采样结果Φ-τ=Φ′-τ。使用πτ表示边τ在采样过程中被采样中的概率，则有如下等式成立：

Pr［PRR（v）=s］=

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ）=s］+

∑Φ－τv－τ（1－πτ）Pr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］（5）

类似的有：

Pr［PRR（v′）=s］=

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ′）=s］+

∑Φ－τv－τ（1－πτ）Pr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］

当假设边τ被采样中时，则相邻数据库v和v′上的采样结果Φ和Φ′仍然是相邻数据集，则由定理1可得如下不等式：

Pr［RR（Φ）=s］≤eεPr［RR（Φ′）=s］

当ε>0时，eε>1，因此将上述不等式带入等式（5）得到如下式子：

Pr［PRR（v）=s］≤

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］eεPr［RR（Φ′）=s］+

∑Φ－τv－τ（1－πτ）Pr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］≤

∑Φ－τv－τπτPr［Ψ（v－τ）=Φ－τ］eεPr［RR（Φ′）=s］+

∑Φ－τv－τ（1－πτ）eεPr［Ψ（v－τ）=Φ－τ］Pr［RR（Φ－τ）=s］=

eεPr［Ψ（v′）=Φ′］Pr［RR（Φ′）=s］=

eεPr［PRR（v′）=s］

根据对称性原则，有：

Pr［PRR（v′）=s］≤eεPr［PRR（v）=s］

成立。因此，个性化采样随机响应机制满足ε-edge LDP。证毕。

定理3  基于子图划分的个性化采样随机响应机制的图生成算法满足ε-edge LDP。

证明：根据算法2的流程，总隐私预算ε被划分为两个部分ε1和ε2，分别用于第一轮和第二轮的个性化采样随机响应，根据边LDP的序列组合原理结合定理2可得算法2满足ε-edge LDP。证毕。

2.4  算法复杂度分析

在用户端，算法1多次遍历了用户位向量中的每个元素，因此算法1在用户端的时间复杂度是O（n），其中n是参与的用户数量。算法2在用户和收集者第一次交互时使用了算法1，之后用户和收集者又进行了第二轮交互，在第二轮交互中用户端对用户位向量进行了多次遍历，综上算法2在用户端的时间复杂度是O（n）+O（n）=O（n）。算法1在收集端需要收集者遍历每个用户提交的索引集合因此算法1在收集端的时间复杂度是O（n2）。算法2在收集端需要在第一轮交互中调用算法1以及在第一轮交互中收集端使用Louvain社区发现算法进行子图划分而运行一次Louvain算法的时间复杂度是O（nlog（n））［27］，在第二轮交互中数据收集端同样需要O（n2）的时间复杂度，因此综上算法2在数据收集端需要O（nlog（n）+n2）的时间复杂度。在通信复杂性方面，我们将一个用户和收集者之间的通信宽度作为通信复杂度。算法1中收集者首先发送参数到用户此时通信复杂度是O（1）。然后用户只需要发送一次部分位向量的索引集合，所以它的通信复杂度是O（n）。因此算法1的通信复杂度是O（n）。算法2第一次交互中使用算法1，第二次交互中数据收集端需要给用户发送子图划分此时通信复杂度是O（n），之后用户端需要发送位向量的索引集合则复杂度是O（n），综上算法2的通信复杂度是O（n）。文献中的方法RABV与LDPGen算法在用户端的时间复杂度都较小为O（n），在收集端RABV的时间复杂度为O（n2），文［14］中表明LDPGen的时间复杂度是O（n2+n（k0+k1）），其中k0是LDPGen算法中初始赋予的节点聚类个数，k1是LDPGen算法计算出的调整后的节点聚类个数。此外RABV和LDPGen算法在用户和收集者之间的通信复杂度为O（n）。

综上，之前的算法与PSRR-LDP图生成算法时间复杂度同阶，后续的实验结果同样表明本文算法的时间复杂度与之前的算法相似，但是链接预测准确性有明显的提升。

3  对比实验与结果分析

为了验证PSRR-LDP算法的有效性，在以下4个领域内常用的公开数据集上进行实验验证。

USAir［28］：美国航空线路的网络，数据集中包括332个节点与2126条边。

NS［29］：网络科学领域研究者的协作网络数据集，包括1589个节点与2742条边。

PB［30］：美国政治博客的网络数据集，包括1222个节点与16714条边。

Facebook［31］：美国Facebook社交网络的快照数据集，包括4039个节点与88234条边。

对比算法选取了无隐私保护机制的算法A，以及目前参考文献中性能最优的隐私保护机制：RABV与LDPGen，为了证明子图划分的作用，还与个性化采样随机响应算法（personalized sampling randomized response algorithm， PRR）进行了性能比较。为评价算法所生成的图数据在链接预测任务上的效果，选择了CN［32］、Katz［32］、Node2vec［33］和SEAL［8］4个经典的链接预测算法进行验证。与参考文献中相同，设置Katz方法的影响系数为0.001，Node2vec方法的嵌入向量维度为80，其余的超参数设置与相应参考文献中的默认值设置一致，对每个实验进行10次图收集，最终以平均结果作为衡量依据。一般而言，很难判断哪些边会在将来出现，实验时为了测试链接预测算法的效果，随机将当前的边集E划分为训练集ET与验证集EP两部分。原始图中10%的边被随机选择作为正的验证集。遵照链接预测数据处理中的常见操作，将相同数量的不存在的边作为负的验证集。将他们合在一起构成了总验证集EP。剩余的边构成了训练集ET。通过训练集ET，构建图GT=（V，ET）用于算法训练，对图GT采用ε-edgeLDP机制进行重构，得到满足边LDP的图G～T=（V，E～T），以此图为基础训练图链接预测算法。實验使用Python语言在具有英特尔至强奔腾8260 CPU和500GB内存的服务器上面编写实验代码。

3.1  评价指标

本文采用AUC（area under the curve， AUC）指标［32］评价算法的链接预测效果。在验证集上运行链接预测算法得出每条边的分数，然后按如下方式计算出AUC值。从验证集Ep中取出缺失边与不存在边进行比较。假设有z个独立的比较结果，在结果中缺失边的分数大于不存在边的分数为x次，分数相等的次数为y，AUC值可以由以下公式得出：

AUC=x+0.5yz

若所有结果都来自一个独立且相同的分布，则AUC的值会接近0.5，AUC值越大，算法相比于随机选择的效果越好。

3.2  结果分析

在设置相同的隐私预算ε=0.1，相同的真实边占比的期望r=0.5，隐私预算分配系数设置为α=0.1时，实验结果如表1所示。为了衡量在链接预测任务中的效果，分别选取了CN，Katz，Node2vec和SEAL链接预测算法进行对比实验，表1中A为未进行隐私保护的图数据与不同的链接预测算法分别在4个数据集上的AUC指标值，实验结果表明文章所提出PSRR-LDP算法的性能在所有的数据集和所有的链接预测算法中效果都是最优的。因为在用户端有效地减少了噪声边的添加，同时保留了细粒度的图结构特征，算法PSRR-LDP性能显著优于RABV和LDPGen算法，在所有数据集上，性能至少提高了30%以上。

为了考查隐私预算ε发生变化时，所提出算法的效果，选取了Katz和SEAL链接预测算法分别在不同数据集上进行了实验验证，USAir数据集结果如图1所示，NS数据集结果如图2所示，PB 数据集结果如图3所示，Facebook数据集结果如图4 所示。与文献中隐私预算设置相同，实验中ε从0.1至7区间进行变化，PSRR-LDP算法几乎在所有隐私预算下都优于对比方法。随着隐私预算的增加，PSRR-LDP、PRR和RABV算法的AUC性能值显著提升，在ε=6时会接近无隐私机制的AUC值并保持稳定。在NS数据集上，当隐私预算较小时PSRR-LDP与PRR算法有相似的表现，当隐私预算较大时，PSRR-LDP算法会明显优于PRR算法，这是因为在NS数据集上具有明显的社区结构，利用社区划分算法可以获得模块度很高的社区划分结果，但在社区数量较多，多数社区中的节点数量较少，因此不满足PSRR-LDP算法的低秩需要。当隐私预算较小时第一轮数据收集后的社区划分结果会引起大量小型社区的合并，从而导致无法有效获取真实的社区结构，因此在效果上与PRR算法相似，当隐私预算较大时，算法第一轮数据收集可以获得更好的接近真实社区结构的社区划分结果，与PRR相比更好地保留了图结构，所以具有更优的效果。

最后，比较不同的邻接矩阵合成方法在收集端的运行时间，结果如表2所示。从结果可以看出运行时间从短到长分别是PRR，RABV，PSRR-LDP以及LDPGen。

3  结  语

针对图数据中节点链接预测导致用户敏感信息隐私泄露问题，提出了个性化采样随机响应机制捕获用户间的信息，并应用于图数据的链接预测分析，同时在去中心化场景下实现了本地差分隐私保护，保护用户隐私的同时提高了数据的可用性。在USAir、NS、PB、Facebook 4个不同真实数据集上的实验结果表明本文算法的有效性和优越性。在后续的工作中，将在确保生成图与原始图之间具有更相似的社区划分，以及减少通讯开销等方面进行深入研究，同时扩展个性化采样技术可解决其它特殊的图类型与其他本地差分隐私场景，如属性图，均值估计和多维数据收集等。

参 考 文 献：

［1］  LIBEN-NOWELL D， KLEINBERG J. The Link Prediction Problem for Social Networks［J］. Journal of theAmerican Society for Information Science and Technology， 2007， 58（7）：1019.

［2］  DE A， CHAKRABARTI S. Differentially Private Link Prediction with Protected Connections［C］// National Conference on Artificial Intelligence. Proceedings of the AAAI Conference on Artificial Intelligence. California： AAAI， 2021：63.

［3］  伍杰华， 程智锋. 联合社区和影响节点的通用可扩展的链接预测［J］. 计算机工程与设计， 2022（2）：43.

WU Jiehua， CHENG Zhifeng. Integrating Community and Influential Node for General and Scalable Link Prediction［J］. Computer Engineering and Design， 2022（2）：43.

［4］  李贞，吴勇，耿海军.基于重引力搜索链接预测和评分传播的大数据推荐系统［J］.计算机应用与软件，2020，37（2）：39.

LI Zhen， WU Yong， GENG Haijun. Big Data Recommender System Based on Gravitational Search for Link Prediction and Ratings Propagation［J］. Computer Applications and Software，20，37（2）：39.

［5］  唐晨，趙杰煜，叶绪伦，等.基于对抗图卷积网络的链接预测模型［J］.模式识别与人工智能，2021，34（2）：95.

TANG Chen， ZHAO Jieyu， YE Xulun， et al. Link Prediction Model Based on Adversarial Graph Convolutional Network ［J］. Pattern Recognition and Artificial Intelligence， 201，34（2）：95.

［6］  赵晓娟，贾焰，李爱平，等.基于层级注意力机制的链接预测模型研究［J］.通信学报，2021，42（3）：36.

ZHAO Xiaojuan， JIA Yan， LI Aiping， et al. Research on Link Prediction Model Based on Hierarchical Attention Mechanism ［J］. Journal of Communications，2021，42（3）：36.

［7］  ZHOU Tao， LU Linyuan， ZHANG Yicheng. Predicting Missing Links via Local Information［J］. The European Physical Journal， 2009， 71， 623.

［8］  ZHANG Muhan， CHEN Yixin. Link Prediction Based on Graph Neural Networks.［C］//Advances in Neural Information Processing Systems， 2018：31.

［9］  李志鹏，孙名松，宋增林. 移动智能终端的位置隐私保护技术［J］.哈尔滨理工大学学报，2018，23（2）：58.

LI Zhipeng，SUN Mingsong，SONG Zenglin. The Location Privacy Protection Technology of Mobile Intelligent Terminal［J］.Journal of Harbin University of Science and Technology，2018，23（2）：58.

［10］ZHOU Bin， PEI Jian. Preserving Privacy in Social Networks Against Neighborhood Attacks［C］// International Conference on Data Engineering. 2008 IEEE 24th International Conference on Data Engineering， IEEE Press， 2008：506.

［11］LIU Kun， TERZI E. Towards Identity Anonymization on Graphs［C］// Acm Sigmod International Conference on Management of Data. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM， 2008：93.

［12］XU Shengzhi， SU Sen， XIONG Li， et.al. Differentially Private Frequent Subgraph Mining［C］//International Conference on Data Engineering. 2016 IEEE 32nd International Conference on Data Engineering （ICDE）.IEEE Press， 2016：229.

［13］XIAO Qian， CHEN Rui， TAN K. Differentially Private Network Data Release via Structural Inference［C］// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2014：911.

［14］ZHANG Sen， NI Weiwei， FU Nan. Differentially Private Graph Publishing with Degree Distribution Preservation［J］. Computers & Security， 2021， 106（6）：102285.

［15］QIN Zhan， YU Ting， YANG Yin， et al. Generating Synthetic Decentralized Social Graphs with Local Differential Privacy［C］// Acm Sigsac Conference on Computer & Communications Security. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM， 2017：425.

［16］YE Qingqing， HU Haibo， MAN H A， 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.

［17］張佳程，彭佳，王雷. 大数据环境下的本地差分隐私图信息收集方法 ［J］. 信息网络安全，2020，20（6）：44.

ZHANG Jiacheng， PENG Jia， WANG Lei. A Graph Information Collection Method Based on Local Differential Privacy in Big Data Environment［J］. Netinfo Security， 2020， 20（6）： 44.

［18］贺星宇，朱友文，张跃.基于OLH的效用优化本地差分隐私机制［J］.密码学报，2022，9（5）：820.

HE Xingyu， ZHU Youwen， ZHANG Yue. Utility-Optimized Local Differential Privacy Mechanism Based on OLH［J］. Journal of Cryptologic Research，2022，9（5）：820.

［19］曹依然，朱友文，贺星宇，等.效用优化的本地差分隐私集合数据频率估计机制［J］.计算机研究与发展，2022，59（10）：2261.

CAO Yiran， ZHU Youwen， HE Xingyu， et al. Utility-Optimized Local Differential Privacy Set-Value Data Frequency Estimation Mechanism［J］. Journal of Computer Research and Development，202，59（10）：2261.

［20］WANG Tianhao， JEREMIAH B， LI Ninghui. Locally Differentially Private Protocols for Frequency Estimation［C］//USENIX Security Symposium. 26th USENIX Security Symposium （USENIX Security 17）， USENIX， 2017：729.

［21］欧阳佳，印鉴，肖政宏，等.面向频繁项集挖掘的本地差分隐私事务数据收集方法［J］.软件学报，2021，32（11）：3541.

OUYANG Jia， YIN Jian， XIAO Zhenghong， et al. Transaction Data Collection for Itemset Mining Under Local Differential Privacy ［J］. Journal of Software，2021，32（11）：3541.

［22］冯立刚，朱友文.保护位置隐私的效用优化本地差分隐私机制［J］.计算机与现代化，2022，325（9）：99.

FENG Ligang， ZHU Youwen. Utility-Optimized Local Differential Privacy Mechanism for Protecting Location Privacy［J］. JISUANJI YU XIANDAIHUA，2022，325（9）：99.

［23］IMOLA J， MURAKAMI T， CHAUDHURI K. Locally Differentially Private Analysis of Graph Statistics［C］// USENIX Security Symposium， USENIX， 2021：983.

［24］DWORK C， ROTH A. The Algorithmic Foundations of Differential Privacy［M］. Foundations and Trends in Theoretical Computer Science，2014： 211.

［25］SHAO Junming， ZHANG Zhong， YU Zhongjing， et al. Community Detection and Link Prediction via Cluster-driven Low-rank Matrix Completion［C］//IJCAI. Proceedings of The 28th International Joint Conference on Artificial Intelligence. IJCAI， 2019：3382.

［26］BLONDEL V， GUILLAUME J， LAMBIOTTE R， et.al. Fast Unfolding of Communities in Large Networks［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 200（10）：10008.

［27］LESKOVEC J. Community Structure in Networks［EB/OL］.［2023-02-15］.http：//snap.stanford.edu/class/cs224w-2019/slides/04-communities.pdf

［28］VLADIMIR B， ANDREJ M. Pajek datasets［EB/OL］.［2023-2-15］. http：//vlado.fmf.uni-lj.si/pub/networks/data/.

［29］NEWMAN M. Finding Community Structure in Networks Using the Eigenvectors of Matrices［J］. Physical Review， 2006， 74（3）：036104.

［30］ACKLAND R. Mapping The us Political Blogosphere： Are Conservative Bloggers More Prominent［C］//BlogTalk Downunder. Blog Talk Downunder 2005 Conference， 2005.

［31］LESKOVEC J， MCAULEY J. Learning to Discover Social Circles in Ego Networks［J］. Advances in Neural Information Processing Systems， 2012， 25.

［32］LU Linyuan， ZHOU Tao. Link Prediction in Complex Networks： A Survey［J］. Physica A： Statistical Mechanics and Its Applications， 2011， 390（6）：1150.

［33］GROVER A， LESKOVEC J. Node2vec： Scalable Feature Learning for Networks［C］//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2016：855.

（編辑：温泽宇）