用于链接预测的本地差分隐私图收集方法
摘要
随着信息技术的发展，图数据广泛存在于人们的生活中，例如社交网络和万维网等。
在图数据使用过程中如何保护用户隐私也成为学术界和工业界的研究热点之一。传统的
隐私保护技术需要一个可信的第三方收集者。然而，第三方收集者可能会因为各种原因
泄露用户数据。本地差分隐私通过让用户在本地对数据进行扰动，然后发送扰动后的版
本给收集者，从而规避了上述问题。目前，本地差分隐私下的图处理方法主要面向图生
成和图统计量估计等后续任务，很少有针对链接预测任务的方法研究。因此，使用现有
1
方法收集的图数据应用在链接预测任务时会面临以下一个或多个问题：（）收集的图
2
未充分保留原始图的细粒度结构特征；（）收集的图能保留原始图的细粒度结构特征
34
但边密度膨胀；（）收集的图丢失原始图上的社团结构；（）收集的图大量丢失节点
属性信息。因此，本文针对上述问题进行了以下研究：
首先，针对以隐私保护的方式收集图时出现的前三个问题，本文提出了本地差分隐
私图收集方法。该方法利用随机响应机制保留细粒度的结构特征，同时采用个性化采样
技术有效解决了在用户端直接使用随机响应机制导致的边密度膨胀问题。然后，该方法
采用社区发现技术以及用户和收集者之间两轮数据交互的方式，有效地保留了原始图中
的社团结构。
其次，针对以隐私保护的方式收集属性图时出现的最后一个问题，本文提出了本地
差分隐私属性图收集方法。该方法的思想是通过图结构和节点属性之间的关系来缓解节
点属性信息丢失的问题。因此，该方法包括以下组成部分：其一，使用拉普拉斯机制扰
动节点的度，并结合基于子图划分的个性化采样随机响应图生成算法完成对图结构的收
集。其二，基于Louvain社区发现算法实现在扰动后的图上对真实图的社区结构估计。
其三，采用多比特机制对节点属性进行扰动和校正。同时，提出基于社区一致性和同质
性的属性后处理方法以缓解节点属性信息的丢失。
最后，本文在真实数据集上进行了对不同图处理方法收集的图数据在链接预测任务
中的表现对比实验。实验使用曲线下面积AUC作为衡量收集到的图数据在链接预测任
务中性能表现的指标，并使用运行时间评估图处理方法的运行效率。实验结果证明本文
提出的方法在给定隐私预算下具有更好的性能表现和运行效率。
关键词：本地差分隐私；链接预测；个性化采样；子图划分
用于链接预测的本地差分隐私图收集方法
Abstract
Withthedevelopmentofinformationtechnology,graphdatawidelyexistsinpeople’s
lives,suchassocialnetworksandWorldWideWeb.Howtoprotectuserprivacyduringthe
useofgraphdatahasalsobecomeoneoftheresearchhotspotsinacademiaandindustry.
Traditionalprivacyprotectiontechniquesrequireatrustedthird-partycollector.However,the
third-partycollectormayleaktheuser’sdataforvariousreasons.Thelocaldifferential
privacymakesusersperturbtheirdatabythemselvesandthensendtheperturbedversionto
thecollectortoavoidt