用户画像与个人隐私-2(user profiling and privacy-2)在线视频

前面我们介绍了LifeSpec项目，

这个项目是关于用户理解和用户画像的。

下面我要讲这次课的最后一部分，

这个部分是关于用户连接和图隐私的。

我们想说，用户连接

与隐私保护有很强的相关性。

所以，在这张幻灯片中你们可以看到，左边有两个网络。

对于用户连接，我们的目标是映射

这两个网络和连接这些网络中的用户节点。

然后，我们就能产生一个更大的网络。

这样，用户就能够被连接在一起，我们就可以知道

跨网络的用户信息。但是，

如果从隐私的角度来看这个问题，

把第一个图看成一个匿名化处理后的图，

称其为目标图；把第二张图看成

辅助图或者攻击者可获得的信息。

所以，如果能够匹配这两幅图，

就意味着我们能够把匿名化处理之后的图中的一个节点

与辅助图中的一个节点匹配在一起。这意味着，这个节点就被去匿名化了。

这是隐私攻击者的一个典型任务。

下面来看看隐私保护的一些基本概念。

这里我们感兴趣的是身份泄露攻击。

身份泄露意味着暴露节点在真实世界中的身份。

有两种类型的攻击，一种称为主动攻击，

另一种称为被动攻击。对于主动攻击，攻击者会

创建很多小账号并建立

一些具有很高的可区分度的模式来连接这些帐号。

在数据发布之后，攻击者会搜索那些

模式。他们可以在匿名化处理之后的图中有效地连接目标账号。

然而，对于被动攻击，

攻击者不能在数据发布之前做这件事情，

因此他们需要收集其他外部数据。

例如，他们有感兴趣的节点以及这些节点之间的部分边的信息。

基于这些信息，攻击者就可以匹配

辅助信息和原始图并识别目标结点。

看看右边的图，

上面的图称为目标图，即发布的经过匿名化处理之后的图。

攻击者可能会有一个称为

辅助图的子图。他们知道

子图中所有节点的真实身份。他们想要把子图与

目标图进行匹配以识别感兴趣的节点。

这里，我们会处理简单图和丰富图。

简单图是指节点和边都没有属性的图。

丰富图是指

节点或者边有属性的图。例如，

节点可能会有一些人口属性信息，

边可能会有交互信息。

传统上，图的匿名化是通过修改

图的结构和描述信息来实现的。

例如，看看右边的目标图和辅助图。

为了让攻击者无法匹配这两张图，

我们可以修改目标图，如增加一些边。

这样会增加攻击的难度，

因为改变了目标图的结构。

但是，同时，这也会

损失数据的效用，因为增加了

不正确的数据。一个例子是K自同构

算法，它能够保证抵御各种

类型的结构性攻击。但是，它需要增加超过70%的

新边到数据库和理论会议中的共同作者图中。

实践中仍然会使用很多轻量级的匿名化算法。

这里的轻量级匿名化算法是指

算法没有对图做很多修改。

一个极端的例子是简单匿名化，这种方法

只对节点的id进行哈希处理，而不改变其他任何东西。

例如，Kaggle是一个数据挖掘

和分析竞赛的平台，

很多学生和研究人员都对它很感兴趣。

在这个平台中，脸谱和其他公司发布的社交网络数据

仍然只做了简单匿名化处理。

这里，我想介绍一些基本术语。

首先是简单图。

简单图是指不含任何描述信息的无向图。这里，

图中的节点对应于用户，

边对应于用户之间的社会关系。

丰富图是有向图和

无向图的组合，其中用户和

社会关系都有相关联的属性。

在这项工作中，我们想要设计图的

去匿名化算法，这个算法能够

处理简单图和丰富图。我们假设，

对手总是能收集目标节点附近的子图。

所收集的子图称为辅助图，

其中节点的真实身份是已知的。

如果能够设计这样的去匿名化算法，

那么就可以使用这个算法来连接

这两幅图并进行用户连接，而用户连接将有助于用户理解。

首先，我们从简单图开始。

这里的关键是定义图节点的相似度。

这里的基本假设是辅助图与目标图相似。

所以，这里我们想要定义

用来测量目标图中的一个节点与辅助图中的另一个节点的相似度的方法。

定义了相似度之后，我们就可以得到一个矩阵。

矩阵中包含目标图和辅助图中的所有节点对的

相似度。最后，我们可以使用一个算法来

根据这些相似度输出最佳匹配。

这里的相似性是以

递归的方式定义的。基本上，两个节点的相似度是和它们的邻接节点的相似度相关的。

所以，看看右边这个例子。

我们有目标图和

辅助图。如果想比较节点3和节点C。

我们注意到，节点3有节点1和节点2这两个邻接节点，

节点C有节点B、节点D和节点E

这三个邻接节点。首先，因为邻接节点的数量不同，所以

节点3和节点C的相似度会受到影响。

然后，因为已经

在前面的步骤中计算了所有节点对的相似度，所以我们可以利用这些相似度

来简化这一步中的计算。因此，

在这个例子中，我们有了

节点1和节点B、节点1和节点D、节点2和节点B等的相似度。

所以，基于这些相似度，可以找到

二分图之间的最大加权匹配。这里的二分图

一边是节点1和节点2，另一边是节点B、节点D和节点E。

如果找到了最大加权匹配，

我们就可以估计节点3和节点C之间的相似度。

所以，这样我们可以递归地

更新这两个图的相似度。

我们的相似度计算方法

还有一些好的属性。假设目标图

与辅助图是子同构的。

目标图中节点的自相似是指

这个节点与它在辅助图中对应节点之间的相似性。

例如，如果知道节点3和节点C是

同一个人，那么自相似是指

节点3和节点C之间的相似度。所以，首先可以证明，

一个节点总是和它自身最相似。这意味着看看

节点3，如果节点C是节点3

在辅助图中对应的节点，

那么节点3和辅助图中所有其他节点的相似度

将小于等于节点3和节点C之间的相似度。

所以，这是相似度的一个非常好的属性。

我们还可以证明，

自相似度总是来源于

目标图的邻接矩阵的主特征向量。

由于真实社交图的特征向量都是有偏的，

因此主特征值很高的社交图

通常都是与众不同的，这意味着

它们很容易被识别。

对于丰富图，我们仅扩展了之前的

定义，考虑了属性和方向。

因为边和节点都有属性，

所以我们可以比较这些属性并

把它们加入到相似性计算中去。

我们不会谈很多细节，因为这非常简单。

这幅图展示了我们的去匿名化算法的步骤。

这里的去匿名化算法是指，如果有一幅

目标图和一幅辅助图，那么怎么样来匹配这两幅图。

还有，怎样找到目标图中的节点的真实身份。

所以，开始时我们让所有相似度

等于1，即它们都是一样的。然后

根据我们的相似度函数迭代地更新这些值。

我们介绍了计算节点3和节点C

之间的相似度的例子。

我们反复更新这些值，最后

会收敛到最终的相似度矩阵。

基于这个相似度矩阵，我们可以找到由这些矩阵

生成的二分图的最大匹配。

然后，输出排名最靠前的m个映射作为匹配的结果。

我们使用两个数据集来评估我们的算法。一个数据集是

微软学术搜索的共同作者图，

其中包含8,000多个节点和18,000多条边。

这个图中没有属性，所以它是简单图。

第二个数据集是

2012年KDDCup发布的腾讯微博的交互数据。

这个数据集中包含230万个节点

和5,500万条边。这是一个丰富图，

节点有性别、年龄和标签等属性，

边有评论数、转发数和@数。

我们采用准确率和召回率作为选出

最先输出的m个映射的评价准则。这里我们对比了

我们的去匿名化算法和几个轻量级去匿名化算法的

准确率和召回率。这些轻量级去匿名化算法包括

之前介绍过的简单去匿名化算法。

简单去匿名化算法只是简单的交换节点的位置而不改变图的结构。

k度匿名化确保图中的每个节点

至少有其他k-1个

节点和它具有相同的度。

K度匿名化只向图中增加最少数量的边。

对于稀疏化，这个方法随机

去掉一部分边。对于扰动，

这个方法先随机去掉一部分边，再随机增加一部分边。

对于交换，这个方法会交换

两条随机选择的边之间的连接。最后，我们想要评价

这个算法在保谱随机化方面的表现。

这个方法尝试使扰动和转换随机化，

同时尽量保留图谱。

这是为了获得更好的效用。

首先，我们报告了我们的算法在子图攻击方面的性能。

对于子图攻击，这里我们假设

辅助图是原始图的子图，

其规模可能是原始图，即目标图的25%或50%。

在这个图中我们可以看到，

我们的算法在识别方面获得了相当高的准确度。

即使当子图较小，如规模只有原始图的25%时，我们的算法在识别方面仍然可以获得相当高的准确度。

这里，X轴展示的是不同的匿名化方法，

Y轴展示的是最好的2,000个输入匹配

的准确度。

我们还在重叠图上比较我们的算法。

这意味着，辅助图和原始图

有一定程度的重叠。也就是说，辅助图不是原始图的一个

子图，其中还包含一些新的节点。

这里的性能与

之前的子图攻击的结果类似。同样的，这里的

X轴表示不同的匿名化方法，

Y轴表示最好的2,000个输入匹配。

我们研究了

攻击的准确性和主特征向量之间的关系。我们发现,

在主特征向量中的值大的节点更容易被识别。在这个图中，

X表示不同的

匿名化方法，Y轴表示识别的准确性。

这里，我们

根据特征值把节点分到不同的桶中。这里

有八个桶，我们使用不同的颜色来表示不同的桶中的节点。

我们发现，特征值高的

桶中的节点的识别准确度要高得多。

这表明，如果你在

社交网络中非常有影响力，那么你就

很容易被识别，因此具有更高的隐私风险。

我们还对比了我们的算法和一个已有的方法。

这个方法是Narayanan提出的。

我们在共同作者图上进行了这个比较。

我们使用的辅助图

与原始图有25%的重叠。我们的方法和

Narayana的方法的区别之一在于我们不需要任何种子

映射。这意味着我们的算法可以在没有任何信息的情况下开始，

而他们的方法需要一组高质量的

种子映射才能开始。在实验中，我们发现，

Narayana的方法要获得好的性能，至少需要

有60%～80%的种子映射是正确的。而且，即使所有的种子映射都是正确的，

Narayana的方法的召回率仍然低于我们的方法。

这幅图中展示了准确性和召回率的曲线。

绿色的线表示我们的方法，红色的线表示他们的方法。

对于绿色的线，如果想要获得高的召回率，

那么就需要输出更多的映射，但是这样会使准确率变低。

对于红色的曲线，我们只改变

种子映射的质量。

当种子映射的质量更高时，

他们的方法的准确率和召回率都会更高。

从这幅图中你们可以看到，

为了让他们的方法比我们的方法更好，

对于各种匿名化方法，

他们需要使映射的准确率达到60%、

70%甚至是80%。

此外，它们的方法的召回率总是低于我们的方法。

我们还评估了我们的方法应用于丰富图时的性能。

在这个试验中，我们使用了腾讯微博的图。

我们使用原始数据集的子图作为附属图，子图总是

包含1,000个节点，但是具有

不同的重叠比例。与目标图相比，这一比例

可能在25%～100%之间。目标图

包含所有剩余节点的匿名化子图。

腾讯微博的图中有230万个节点。

这里我们还使用了一个特定的概率来扰动属性。

这意味着我们可能随机地把性别从男性变为女性。

在图中，X轴表示不同的

匿名化方法，Y轴

表示最好的250个映射的准确度。

比较我们的方法和简单匿名化方法，我们发现，改变图的

结构不会对匿名化带来很大的困难。

因为不同的匿名化策略在准确率方面的差别不大。

但是另一方面，

对属性的扰动会显著地降低准确率。

由于节点和边的属性提供了重要的

信息，因此可以预期这些信息

会使攻击更加容易。

在效率方面，微软学术搜索的共同作者图

是一个包含8,000个节点的简单图，我们通常需要

8分钟～20分钟来完成去匿名化。

对于2012年KDDCup的腾讯微博用户交互图，

由于它非常大，包含

230万个节点和5,500万条边，所以我们设计了

一个方法来提高效率。

这里，X轴表示最佳候选对的数量。

这意味着我们在迭代中只维护特定数量的

最佳候选对。此外，为了节省空间和时间，

我们还移除了所有其他候选对。

左边这幅图的Y轴表示准确率，右边这幅图的Y轴表示

运行时间。从运行时间中，我们可以看到，

如果保持一定数量的候选对，准确率

会先提高然后保持平稳。

所以从这里来看，我们可以说不需要保留所有

最佳候选对，而只需要保留

一部分最佳候选对，

这样可以在保持高的准确率的同时获得好的运行时间。

好了，总结一下这次课的最后一部分。

在这一部分中，我们设计了一个

基于节点相似度的社交图去匿名化算法。

这个算法同时考虑了图的结构和属性。

我们说明了这个算法能够有效地完成大规模社交图的去匿名化。

我们发现，额外的描述信息使攻击

更加容易，即使信息不准确时也是如此。

我们发现，在特征向量中心度方面有影响力的节点

具有高的隐私风险。

我这次

基于大规模人类行为数据的用户理解课程就讲完了。在这次课中，

我介绍了用户理解这个重要的大数据应用。

我讲了什么是用户行为数据以及这些数据是怎么积累的。

我还讲了为什么我们需要研究这些数据

以及为什么这些研究是重要的。

我介绍了最近我们在用户移动规律的理解、

用户画像和隐私保护方面的研究项目。

对于未来的挑战，

隐私无疑是我们需要面对的最重要的挑战。

因为所有这些数据都来源于用户，

它们都代表了用户的一些行为模式，

所以用户会关心我们如何使用这些数据以及我们能够从这些数据中挖掘出什么。

第二个挑战是我们如何

从不同的公司和组织获得数据。

这对于这个领域中的研究非常重要。

我们还鼓励多学科的研究，

因为我们的很多研究主题都与

社会学和心理学的研究相关，所以我们需要

鼓励不同学科的研究人员和我们一起工作。

最后，由于数据

是多种多样的，这些数据可能是用户轨迹、

照片、标签和社交网络。

我们有各种各样的数据。如何管理

这些大规模的不同来源的数据对我们来说是另一个挑战。

谢谢大家！希望你们喜欢这次课。