面向子图匹配的社会网络隐私保护方法*

2019-09-14张晓琳袁昊晨李卓麟张换香

计算机与生活 2019年9期

张晓琳，袁昊晨，李卓麟，张换香，刘娇

内蒙古科技大学信息工程学院，内蒙古包头 014000

1 引言

随着社会网络的快速发展，社会网络含有更加丰富的信息，例如Facebook、Twitter、微博等。社会网络中含有用户的隐私信息，在云平台内进行子图匹配[1-4]时保护隐私信息是非常重要的。K-自同构算法[5]是传统的社会网络隐私保护算法，这种方法在处理大规模社会网络图时，处理效率会大幅度下降[6]而且不能保证较高的数据可用性。传统的K-自同构算法在原始图中添加噪声边，使原始图中的每个节点都有至少有k-1 个对称节点。如图1 是社会网络原始图，在原始图的基础上添加3 条噪声边，同时根据表1对原始图的标签进行标签分组泛化[7]后使原始图转换成2-自同构图，如图2。

可以看出K-自同构算法能很好地抵御结构攻击。但这种方法因为添加了噪声边，导致了子图匹配结果的不准确以及在云平台中进行子图匹配大量的空间时间消耗。

为此提出一种解决方案，将原始社会网络图匿名成K-自同构匿名图并将K-自同构匿名图的一部分和K-自同构函数上传至云平台中；在云平台中进行子图匹配操作得到不完全子图匹配结果；将得到的结果以及K-自同构函数下载至客户端内进行恢复和过滤。本文主要研究内容如下：

（1）提出分布式K-自同构社会网络隐私保护算法DK-A（distributedK-automorphism）保护社会网络结构隐私，为了减少子图匹配时间空间成本，上传K-自同构图的一部分和K-自同构函数至云平台。

（2）提出分布并行的子图匹配方法，在云平台中对搜索分解子图QSGs（query subgraphs）进行子图匹配，将得到的结果以及K-自同构函数下载回客户端中进行子图匹配。

（3）通过实验证明以上方法保证了社会网络在上传至云平台中进行子图匹配时没有泄露隐私，并且大幅度减少了空间和计算成本。

2 相关工作

Fig.1 Original graph of social network图1 社会网络原始图

Fig.2 2-automorphism anonymous graph of original graph图2 原始图的2-自同构匿名图

许多学者对保护社会网络的结构隐私信息做出了研究，这些研究可以作为保护上传图隐私信息的基本方法。文献[8]假设攻击者只使用一种结构攻击方法，然而攻击者有可能使用多种结构攻击方法获得隐私信息。文献[9-13]提出的基于删除边的结构隐私保护算法，边的删除可能会导致上传图丢失重要信息。使用分布式K-自同构社会网络隐私保护算法作为匿名社会网络的基本方法原因如下：因为算法没有删除边，所以不会丢失重要信息；利用K-自同构图的对称性可以在客户端中恢复子图匹配结果；分布式K-自同构社会网络隐私保护算法适用于大规模社会网络环境。

文献[14]提出LP（linear programming）模型可以匿名权重社会网络图并且保留图中节点间的最短路径，但是攻击者具有任意拓扑背景信息时可以对匿名图进行重识别，而且不能保护客户端内子图匹配结果的准确。文献[7，15]提出了保护子图匹配结果正确性的社会网络隐私保护方法，这些思想通过使用图的索引进行子图匹配，保证结果的正确性但是不适用于大规模社会网络环境。

本文提出DK-A 算法保护发布至云平台中社会网络的图的隐私，提出适用于大规模社会网路的分布式子图匹配方法，保证在云平台中进行高效的子图匹配同时确保隐私不会泄露，并通过对匹配结果的恢复和过滤得到正确的子图匹配结果。

3 背景知识及问题定义

定义1（特征无向图）[7]将社会网络表示成节点带标签的简单无向G=(V(G),E(G),T,Γ,L)。（1）V(G)是图G的节点的集合；（2）E(G)⊆V(G)×V(G)是一个无向边的集合；（3）T是节点的类型，每个节点只有一种类型；（4）Γ是节点的特征集合，一个节点有一个或多个节点特征，并且节点的类型不同，节点的特征也不同；（5）L是节点的标签集合，每个节点特征有一个或多个节点标签。T(V)、Γ(V)、L(V)是节点的类型、特征和标签。例如在图1中节点c1的类型是C（company），节点s1的类型是S（school），节点p1的类型是P（person）。对于任意两个不同的节点V1、V2，如果T(V1)=T(V2)，那么Γ(V1)=Γ(V2)。对于一个节点特征A∈Γ(V)，表示节点V的特征A的标签。一个节点特征或许有多个标签，例如图1 中公司类型的特征有互联网、软件、网络媒体等标签。

定义2（K-自同构图）[5]如果图Gk={V(Gk),E(Gk)},并且V(Gk)可以被分割至k个块内，每块图中有个节点。任意节点v有k-1 个对应节点在其他块中，那么这个图是K-自同构图。

定义3（K-自同构函数）[5]v是K-自同构图Gk中的一个节点，v和它的k-1 个对称节点组成了序列AVI（alignment vertex instance），所有的序列组成了表AVT（alignment vertex table），AVT表中每一行表示一组AVI，如图3。基于自同构图Gk的AVT表建立K-自同构函数Fi(i=0,1,…,k-1)。

F0(v)=v

Fi(v)=Fi-1(v).next,for 1≤i≤k-1

Fig.3 AVT table图3 AVT表

例如在图3的AVT表中，F0(p1)=p1；F1(p1)=p5。

定义4（子图匹配）[4]给出一个图G=(V(G),E(G),T,Γ,L)，一个搜索图Q=(V(Q),E(Q),T,Γ,L)，如果存在至少一个映射V(Q)→V(G)使得：

（1）∀qi∈V(Q),g(qi)∈V(G)⇒L(qi)⊆L(g(qi))

（2）∀qi,qj∈V(Q),edge qiqj∈E(Q)⇒

edge g(qi)g(qj)∈E(G)

那么Q是G的同构子图。如果Q是G的同构子图，子图匹配是找出在图G中所有与Q同构的子图，这些子图的集合就是搜索图Q关于数据图G的子图匹配结果。搜索图Q关于数据图G的子图匹配结果记为R(Go)。

云计算提供的服务主要有两种：基础设施即服务（infrastructure-as-a-service，IaaS）和软件即服务（software-as-a-service，SaaS）。数据的拥有者可以将数据上传至云平台中进行分析。使用合适的算法可以降低数据的存储、分析成本，提高数据分析效率。例如在云平台中对数据进行子图匹配操作的速度要远远大于在单机环境下对数据进行子图匹配，当处理大规模的图数据时，这种差异会更加明显。

云平台会完全按照使用者提供的要求运行，但是数据存储以及运行是在第三方提供的云平台中，因此对于数据提供者来说存在隐私泄露危险。使用云平台处理数据是需要成本消耗并且在云平台中处理数据会产生严重的隐私泄露问题。比如节点再识别攻击。如果一个攻击者知道云平台中上传图中节点t的结构信息，比如节点的度、一邻居图。根据已经掌握的节点结构信息对云环境中的图进行子图匹配，如果在上传图中只有很少的节点匹配节点t，那么就可以以较高的概率在上传图中识别节点t，这样就会造成关于节点t的敏感信息泄露。

面向子图匹配的社会网络隐私的目标是在云平台中进行关于社会网络的子图匹配时保护社会网络的隐私，并在客户端得到正确子图匹配结果。

4 云平台中社会网络隐私保护方法

为了保护云平台中社会网络图的结构隐私，使用DK-A 算法对上传至云平台中的社会网络图进行匿名；根据K-自同构图的对称性提出新的上传方案降低云平台中子图匹配的成本。

4.1 分布式K-自同构社会网络隐私保护算法DK-A

分布式的K-自同构算法DK-A 算法的基本思想是：利用Trinity框架[16]相邻节点之间可以发送接收消息的特点，将社会网络图中的节点分布存储于计算节点中，通过节点之间的标记信息确定需要添加噪声边的节点。

DK-A算法由三部分构成：

（1）使用MLP（multi-level label propagation）算法[17]通过多级别标签传递的方法对原始图进行分割，根据分割后的K块图得到AVT表；

（2）块内噪声边的添加；

（3）块间噪声边的添加。

块内噪声边的添加主要基于AVT表的同列内相邻节点之间发送标记信息。当节点接受到标记信息后对自己进行标记，并与同行节点进行比较，如果同行有未被标记节点，在此节点与发送行同列节点间添加边。

算法1块内添加噪声边

输入：AVT；Go。

输出:Gk′。

块间噪声边的添加主要基于AVT表的不同列相邻节点之间发送标记信息。

当节点接收到标记信息后对自己进行标记，并与同行节点进行比较，如果同行有未被标记节点，根据K-自同构函数添加块间边。

算法2块间添加噪声边

输入：AVT；Gk′。

输出:Gk。

DK-A 算法在最坏情况下时间复杂度为O(mn),m是AVT表的行数，n是AVT表的列数，可以发现算法需要的执行时间与AVT表的规格相关。

例如首先对图1进行分割，得到如图3（a）的AVT表；在计算节点中的节点按照AVT表传递标记信息，如图3（b），当算法循环至p3节点所在行时，s4被标记，但是s2未被标记，因此添加边p3s2；当块内边完成添加后，节点继续按照AVT表传递信息并添加边，如图3（c），循环至p2所在行时，发现p3行只有p7被标记。通过K-自同构函数F1(p2)=p6，F1(p7)=p3，添加边p6p3，当块间边添加完成后得到2-自同构匿名图如图2。

4.2 K-自同构图的上传方案

直接将K-自同构图上传到云平台中会导致巨大的存储成本。因此只上传图中的一部分和K-自同构图的K-自同构函数Fi(i=0,1,…,k-1)至云平台中进行子图匹配。因为K-自同构图具有对称性，所以在客户端中仍然可以得到准确的子图匹配结果。这样可以减少存储空间，增加匹配速度，大幅降低成本。

定义5（上传图）对于K-自同构图Gk=(V(Gk)，E(Gk),T,Γ,L)，它的上传图为Gu=(V(Gu)，E(Gu),T,Γ,L)。（1）V(Gu)是自同构图Gk的第一块图中节点V(B1)和第一块图的一邻居节点V(N1)的集合；（2）E(Gu)是无向边E(Gk)的子集，并且它连接了V(B1)内的节点以及V(B1)和V(N1)的节点，如图4是图2的上传图，M1～M4表示计算节点序号。

5 分布式子图匹配方法

分布式的子图匹配算法由搜索图的分解、云平台中子图匹配、子图匹配结果处理三部分构成。

5.1 搜索图的分解

定义6（搜索分解图）设Q是搜索图，设S={QSG1,QSG2,…,QSGn}，S是搜索分解图QSG（query subgraph）的集合。Q的任意边包含在并且仅包含在一个QSGi中。称集合S是搜索图Q的一个QSG 覆盖。

如图5（a）是一个搜索图，表示搜索两个有关系的人，他们的共同点是在北京上学，他们分别从事于互联网和软件行业的工作。P、S、C 分别表示的是节点的类型。

Fig.4 Upload graph Gu图4 上传图Gu

Fig.5 Query graph图5 搜索图

QSG是一个层数为2的树结构。记QSG={r,L}，r表示的是根节点的标签，L是r的孩子节点的标签的集合，如图5（b）。

最少QSG覆盖问题的目标是找出搜索图Q的最少QSG 覆盖。很明显当|S|越小时，子图匹配结果所需要的连接次数越少，子图匹配速度越快。

定理1最少QSG覆盖问题等价于最少节点覆盖问题。

证明反证法：设S是Q最少QSG 覆盖，设V是所有QSGi(1≤i≤n)的根节点的集合。任意一边至少与集合V中的一节点相连，因此V是Q的节点覆盖。假设这里存在其他的覆盖V，使|V′|<|V|，建立一个由集合V中节点做根节点的集合S，且v∈V′，使搜索图内与节点v相关的边与节点v共同组成一个QSG。随机删除QSGs中的边直到任意边只属于一个QSG，这样集合S′中的QSG 都至少含有一条边。很明显|S′|≤|V′|<|V|=|S|，这说明S不是最少QSG覆盖。□

最少节点覆盖问题是经典的NP-hard 问题。根据定理1，最少QSG 覆盖问题也是NP-hard 问题。2-approximate算法是一个处理最少节点覆盖问题的经典算法。这个算法在每步随机选择一条边(u,v)，将u、v加入结果集中，并在原图删除所有与u、v相连的边，重复以上步骤直到图中的边都被删除。对这个经典算法进行改进，使这个算法适用于最少QSG覆盖问题。

算法主要修改了边的选择方法，通过节点的选择度选择边进行QSG 覆盖。设函数表示节点的选择度，deg(v)表示节点v的度，freq(v)表示节点v的标签在数据图中出现的次数。

算法3搜索图分解

输入：Q。

输出:QSGs。

如图5 所示。首先选择q2q3边，因为f(q2)=3,f(q3)=3,f(q2)+f(q3)值最高；然后产生QSG1={q2,(q1,q3,q4)}和QSG2={q3,(q1,q5)}。

定理2算法3 得到的QSG 的个数最多是最少QSG覆盖问题最优解的两倍。

证明设H*是最优QSG覆盖集合。设E是算法选择的边的集合。因为在集合E中的边没有公共点并且在一个QSG 中的所有边一点存在一个公共点，因此每个QSG最多包含一条集合E中的边。这表示|E|≤|H|。对于每条边e∈E，最多会产生两个QSG，因此|H|≤2|E|≤2|H*|。 □

5.2 云平台中子图匹配算法

子图匹配需要对QSGs 的标签进行泛化防止泄露隐私。在计算节点中对QSGs依次进行算法3的子图匹配操作。

算法4子图匹配

输入：QSGs，QSG={r,L};Gu'。

输出：R。

1.Sr←Index.getID(r)/*找到标签为r的节点ID*/

2.R=∅；

3.for eachninSrdo

4.c=Cloud.Load(n)/*载入节点ID为n

5.for eachliinLdo

7.R=R∪{{n}×Sl1×Sl2×…×Slk}；

8.ReturnR；

例如图6 是图5 中QSGs 在上传图图4 中的匹配结果。

所有计算节点内关于QSGs 的子图匹配结果进行连接得到最后的子图匹配结果。例如将图6 中所有结果连接后得到子图匹配结果Rin，如图7。

5.3 子图匹配结果处理

Fig.6 Subgraph matching result of QSG图6 搜索分解子图匹配结果

Fig.7 Subgraph matching result Rin图7 子图匹配结果Rin

得到关于上传图Gu的子图匹配结果不是完整K-自同构图的子图匹配结果。将已经得到的结果和云平台中存储的K-自同构函数下载到客户端。使用K-自同构函数将下载到的结果恢复成关于K-自同构图的子图匹配的结果。例如使用图7的结果Rin并根据图3的AVT表得到F1(c1)=c3,F1(p2)=p6,F1(p3)=p7,F1(c2)=c4,F1(s1)=s3，得到如图8 的映射结果Rout。R(Gk)=Rin∪Rout是关于K-自同构图的子图匹配结果。因此图7和图8是关于匿名图的子图匹配结果。

Fig.8 Mapping result Rout图8 映射结果Rout

定理3设关于原始图Go，K-自同构图Gk的子图匹配结果R(Go)、R(Gk),R(Go)⊆R(Gk)。

关于K-自同构图的子图匹配结果R(Gk)与在关于原始图Go的子图匹配结果R(Go)不同。由于对原始图边的添加使子图匹配结果有可能增多。对于数据的拥有者来说，这造成了信息的可用性下降。因此客户端在得到子图匹配结果后，还应进行子图匹配结果过滤，删除含有在原始图中不存在的节点或边的子图匹配结果；删除节点标签与搜索图中对应节点标签不同的子图匹配结果。

算法5匹配结果过滤

输出：R(Gk),Go。

输出:R(Go)。