融合社区连接信息的网络嵌入方法

宋振寰,胡 军

(1.重庆邮电大学 计算智能重庆市重点实验室 重庆 400065;2.重庆邮电大学 计算机科学与技术学院 重庆 400065)

0 引 言

网络在现实生活中无处不在,常见的如生物蛋白质系统、社交系统、交通系统等都可以抽象为网络的形式。通过分析这些网络结构,可从中提取有价值的信息,比如用户间的好友关系,蛋白质网络中单独蛋白的相互作用关系等[1]。传统的网络表示方法常基于网络的拓扑结构,通过图的邻接矩阵或相似矩阵进行表示,但是这些表示方法在面对大规模网络时存在高维稀疏的问题,且可能包含噪声和冗余信息[2]。针对这一问题,近年来学者们提出了网络嵌入方法,其通过将原始网络映射到向量空间得到节点嵌入表示,从而有利于结合机器学习模型高效处理网络分析的下游任务,如节点分类[3-4],推荐[5-6],链接预测[7-9]等。现有的网络嵌入方法主要分为基于随机游走的方法[10-12]、基于深度神经网络的方法[13]和基于矩阵分解的方法[14-15]。这些方法大多仅考虑了节点的局部结构信息,忽略了网络中的社区信息。

为解决网络嵌入中社区信息缺失的问题,S.Cavallari等[16]基于高斯混合分布提出了融合社区信息(community embedding,ComE)的算法。M.M.Keikha等[17]对随机游走进行扩展,提出了融合社区信息的随机游走(community aware random walk for embedding,CARE)算法,主要依据阈值选择社区节点进行游走。B.Rozemberczki等[18]提出了一种在学习节点嵌入的同时进行节点聚类(graph embedding with self clustering,GEMSEC)算法,主要通过在学习节点嵌入过程中考虑节点聚类损失融合社区信息。Zhou等[19]提出一种考虑社区节点游走的同时结合注意力机制增强语义信息的(community aware and relational attention,CARA)算法。然而这些融合社区信息的方法仅对社区内的节点信息进行了加强,没有考虑网络中的社区间信息。

在现实生活中,社区信息和社区间的关系都至关重要,因为不仅同一社区的节点有大概率产生联系,不同社区的成员也可能产生联系,如图1所示。在实验室社交网络中,每个节点代表一个学生或老师,每条边表示相连的2个节点间存在联系,不同颜色代表不同的实验室社区。其中,学生x和y在社交网络中虽然没有连边,但由于它们属于同一实验室社区,它们之间大概率会存在连边关系[20]。而A,B两实验室社区因为存在多个共有的老师作为团队指导,则x节点有更大的概率和z节点存在链接。因此,融合社区信息的过程中有必要考虑社区间的关系,在保留节点间的连接信息和社区信息的同时,保留社区间的连接信息。

图1 社区之间关系Fig.1 Relationship between communities

基于上述分析,本文提出一种融合社区连接信息的网络嵌入方法(network embedding based on community connection information,ECCI)。该方法首先结合社区发现算法获得网络的社区结构,然后基于不同社区的亲密度,捕捉网络中社区间关系,接着采用有偏游走的方式保留网络局部信息,并采用社区游走的方式保留网络社区内信息和社区间信息,最后通过负采样优化的Skip-Gram模型得到与之对应的网络表示结果。在3个公开数据集上的实验结果表明,该方法相比基准方法在链接预测实验的效果有一定程度的提升。

1 相关工作

网络嵌入旨在提取网络中节点、边的低维信息表示。一个网络可以表示为一个图G=(V,E),其中,V表示图中的节点集合,E是边的集合,网络嵌入的目标是通过一个映射函数为每个节点v学习低维稠密的实数向量f：V→Rd,d是嵌入向量的维数,并在低维空间中保存网络的拓扑结构信息,如点和边的邻近关系,以及社区信息等。

近年来兴起的网络嵌入研究起源于自然语言处理领域的表示学习,受词向量嵌入方法的启发,DeepWalk[10]方法提出,其基于随机游走的策略,每个节点随机从邻居集合中选择一个节点加入节点序列,对该序列使用Skip-Gram模型进行学习,得到嵌入结果。Node2vec[11]在随机游走的过程中加入了超参数p,q改变游走概率,可选择深度优先遍历或广度优先遍历,从而保存网络的同质性和同构性。大规模信息网络嵌入方法(large-scale information network embedding,LINE)[12]则是利用丰富的二阶邻域来弥补一阶邻居的稀疏性。并且,随着深度学习的发展,深层神经网络模型也逐步应用于网络嵌入技术中,主要用于提取网络中的非线性信息。基于深层神经网络模型的嵌入方法(structural deep network embedding,SDNE)[13]基于深层神经网络模型,使用深度自动编码器来保持节点的一阶邻居相似度和二阶邻居相似度,然后联合优化这两个近似值,再通过非线性的函数获得节点的表示。此外,基于矩阵分解的网络嵌入方法(graph representations,GraRep)[14],其通过对节点不同k步距离内的网络拓扑信息进行奇异值分解,并将每一步的结果相连得到节点嵌入结果。ProNE[15]首先通过将任务定义为稀疏矩阵分解有效地初始化网络嵌入,然后通过在频谱调制空间中传播来增强嵌入。但是这些方法都没有考虑网络中的社区信息。

为在网络嵌入中融合社区信息,ComE定义了节点嵌入、社区检测、社区嵌入的方法流程。但是其假设嵌入空间中社区是拟合高斯分布的,并通过高斯混合模型进行建模。CARE使用Louvain[21]算法检测出社区网络结构,利用社区信息指导随机游走,在生成节点序列时,根据阈值α从社区中随机选择一个节点加入序列,进而融合社区信息到最后的嵌入结果中。GEMSEC通过在学习节点嵌入的过程中添加节点到聚类中心的聚类损失以融合网络中的社区信息。CARA在获取节点周围的局部结构时还捕捉了节点的社区信息,并且通过注意力机制对节点之间的语义信息进行了加强。M-NMF[22]通过模块化非负矩阵分解来保存网络的微观和宏观结构,从而在最终的节点嵌入结果保留社区信息。融合k步社区的网络嵌入方法(network embedding guided by partial community,PCGNE[23]定义了k步社区的概念,通过部分社区结构对随机游走进行指导,以保存更高质量的社区信息。

从上述方法来看,现有的嵌入方法多仅采用不同的方式在嵌入结果中融合社区信息,但只强调了社区内节点的关系,忽略了社区间的信息。为此,研究一种融合网络社区间信息的网络嵌入方法具有十分重要的意义。

2 融合社区连接信息的网络嵌入

融合社区连接信息的网络嵌入方法ECCI主要思想：首先对输入的网络使用Louvain算法进行社区发现,得到输入网络的所有社区;然后根据发现的社区得到社区间的亲密度(community relevance jaccard,CR-JC)[24],并结合CR-JC对网络中的每一个节点V生成融合局部结构、社区信息和社区间信息的节点序列捕捉网络的局部信息和全局信息;最后使用Skip-Gram模型最大化节点在定义的窗口中出现的条件概率,从节点序列中学习出节点的嵌入结果,方法的主要思想如图2所示。

图2 融合社区连接信息网络嵌入Fig.2 Network embedding based on community connection information

2.1 社区生成

由于Louvain算法可快速有效地发现网络中的社区结构,因此本文使用该算法来生成社区信息。该算法首先将每一个节点单独划分为一个社区,然后尝试把每个节点分配到邻居节点所在的社区并计算模块度的变化,最后选择模块度最大的社区进行加入。模块度计算公式为[25]

(1)

(1)式中：m表示图中边的权重之和;ki表示所有与节点i相连的边的权重之和;ci表示节点i所属的社区;δ是一个增量函数,当社区相等时返回1。

模块度优化完成后,该算法另一阶段是聚集已发现的社区,建立一个新的社区网络。然后不断重复上述过程,直至模块度不再增加。

2.2 有偏游走序列生成

本文采用Node2vec获取节点邻居结构,具体步骤如算法1所示,该方法对初始节点v,通过有偏游走的方式生成长度为l的游走序列,以更好地保留网络中的结构信息。具体地,通过控制p,q两个超参数可以实现深度优先遍历和广度优先遍历,其中p用于控制是否重复游走,即是否返回已经走过的节点。q用于控制游走的方向,是倾向深度优先遍历还是广度优先遍历。

算法1Node2vec有偏游走

输入：网络G(V,E);参数p,q;节点游走的路径长度l;节点的游走路径数量u;

输出：有偏游走序列Sn。

1：有偏游走序列Sn←∅,网络节点V←G.nodes()

2：通过p,q值计算每个节点的别名采样概率α

3：for iter=1 toudo

4：for eachv∈Vdo

5：Initialize walk_list to [v]

6：for walk_iter=1 toldo

7：curr_v=walk_list[-1]//从最新加入的节点出发

8：next_v=AliasSample(curr_v,α)//通过别名采样获取下一节点

9：append next_vto walk_list//加入节点到游走序列中,作为下一个初始节点

10：end for

11：Sn=Sn∪walk_list//所有游走序列

12：end for

13：end for

14：Return Sn

2.3 社区游走序列生成

本文使用CR-JC相似度作为2个社区之间亲密度的关系度量,其物理意义是不同社区以及其邻居节点中产生交集的部分越多,则2个社区之间的联系越紧密,定义为

CR(ci,cj)CR-JC=

(2)

(2)式中：Γ(ci)表示社区ci的邻居节点集合;V(ci)表示社区ci中的节点集合。

社区亲密度计算示意图如图3所示。给定一个无向无权图G(V,E),其中,Γ(c1)={7,8,11,12,13,14},V(c1)={1,2,3,4,5,6},Γ(c2)={2,3,4,5,13,14},V(c2)={7,8,9,10,11,12},由公式(2)可得社区1和社区2之间的CR-JC亲密度为5/7。同理可得,社区1和社区3之间CR-JC亲密度为3/7,社区2和社区3之间亲密度为3/7。

图3 社区亲密度计算示意图Fig.3 Community Intimacy Calculation

社区游走序列生成步骤如算法2第4-10行所示,首先以v为初始节点,根据发现的社区信息确定当前节点的所属社区。接着,将社区抽象为节点,计算CR-JC亲密度作为网络中社区节点之间的跳跃概率,结合别名采样法确定下一跳社区,并从下一跳社区中随机选择节点加入游走序列,直至游走序列长度达到l。特别地,ci=cj的时候CR-JC值为1,因此初始节点选择同一社区的节点进行游走的概率更高,其次才是其他相似度高的社区中的节点。可以看出,社区游走序列中既保存了网络中节点的社区内信息,也基于社区相似度捕捉了网络中社区间的关系,弥补了有偏游走序列中全局信息的缺失,可更好地对网络结构进行表示。

算法2社区游走

输入：网络G(V,E);社区信息com;社区游走路径数量c;社区游走的路径长度l;

输出：社区游走序列Sc。

1：社区游走序列Sc←∅,网络中节点V←G.nodes()

2：通过CR-JC计算每个社区的别名采样概率α

3：for iter=1 tocdo

4：for eachv∈Vdo

5：Initialize walk_list to [v]//将节点V作为初始节点

6：for walk_iter=1 toldo

7：curr_v=walk_list[-1]

8：curr_com=com(curr_v)//当前节点所属社区

9：next_com=AliasSample(curr_com,α)//别名采样法获取下一跳社区

10：next_v=RandomChoice(next_com)

11：append next_vto walk_list

12：end for

13：Sc=Sc∪walk_list

14：end for

15：end for

16：Return Sc

2.4 SkipGram模型

SkipGram模型如图4所示,对每个节点得到有偏游走和社区游走的序列l={v1,v2,…vn}后,ECCI使用Skip-Gram模型来学习网络的节点嵌入。具体地,从得到的序列中任选一个节点vi,根据窗口大小w获得vi的上下文节点,将节点的独热编码输入神经网络模型,通过正向运算和反向传播更新权重矩阵,最大化序列vi-w,…,vi,…,vi+w中节点共现的概率为

图4 SkipGram模型Fig.4 SkipGram model

(3)

为降低(3)式的计算复杂度,这里采用负采样进行优化,表达式为

(4)

(4)式中：K为负采样个数;X(v)为负采样概率分布。

3 实验分析

对于本文提出的网络嵌入方法,将得到的表示向量运用于链接预测任务以验证其有效性,并通过参数敏感性实验进行参数分析。

3.1 数据集

实验选用了3个真实数据集来进行测试,数据集的具体信息如表1所示。

表1 数据集Tab.1 Dataset

Cora[26]：每个节点代表1篇机器学习论文,一共可分为7个类别。网络中存在2 708个节点以及5 429个链接。

Facebook[27]：每个节点代表1个用户,每1条边则代表2个用户之间的友情。该网络一共存在4 039个节点和88 234条边。

表2 链接预测结果Tab.2 Link prediction results

Wiki[28]：每个节点代表维基百科中的文章,每条边的连接表示2篇文章之间的引用,该网络一共存在2 405个节点以及17 981条边,共17个种类。

3.2 对比方法和评价指标

实验对比的方法包括以下5种网络嵌入方法。

1)DeepWalk：利用随机游走生成节点序列获得局部信息,并通过Skip-Gram模型学习节点的表示。

2)Node2vec：1种在随机游走过程中通过2个超参数p,q考虑深度优先搜索和广度优先搜索的网络嵌入表示方法。

3)ComE：采用混合高斯分布作为社区表示的模型,并假设节点表示是由这样的社区分布生成的。

4)CARE：1种基于已知社区进行随机游走的网络嵌入方法,能在嵌入结果中考虑网络中的社区信息。

5)LouvainNE[29]：1种基于层次聚类的网络嵌入方法,能在嵌入结果中考虑不同层级的社区信息。

其中,ComE、CARE和LouvainNE是融合了社区信息的方法,DeepWalk和Node2vec是没有融合社区信息的方法。

实验使用的评价指标有AUC(Area Under Curve,ROC曲线下面积)和F1-Score值,其中F1-Score计算方式为

(5)

(6)

(7)

(5)—(7)式中：TP、FN、FP分别为预测结果中真阳性、假阴性和假阳性样本;precision为真阳样本和预测为阳的样本占比;recall为真阳样本和真实为阳的样本占比。

3.3 实验设置

所有方法在游走的过程中进行统一的参数设置。具体地,设置滑动窗口大小为5,嵌入维度为128,游走路径数量为10,游走长度为80。对比方法的参数均按照相应论文中描述进行设置。特别地,本文提出的方法负采样个数为5,ComE的聚类数根据网络中的真实类别数进行设置,无类别信息的Facebook数据集则使用社区发现算法发现的社区个数作为聚类数。LouvainNE方法a值设置为0.01。

网络嵌入方法仅仅为每个节点生成嵌入向量,因此本文参照Node2vec使用多种操作运算符计算边的嵌入g(u,v),具体定义如下

Hadamard：

[f(u)*f(v)]i=fi(u)*fi(v)

(8)

Average：

(9)

Weighted-L1：

‖f(u)·f(v)‖1i=|f(u)i-f(v)i|

(10)

Weighted-L2：

‖f(u)·f(v)‖2i=|f(u)i-f(v)i|2

(11)

3.4 链接预测分析

3.4.1 全局链接预测

在全局链接预测任务中,首先将网络中的一些边随机删除,然后通过各种方法预测这些缺失的边。具体实验采用了生成带标签的数据集方式,在不影响网络连通性的情况下从网络存在的边中随机移除10%、20%、30%、40%、50%的边作为正样本,从节点间无连接的节点对当中采集负样本,最后利用剩余的网络进行网络嵌入得到嵌入结果。AUC和F1-Score指标用于评估该任务的准确性,取5次实验的平均值作为最终结果,更高的AUC值和F1-Score值意味着更好的模型性能。

3个数据集上Hadamard运算符实验结果AUC(百分制)如表2所示。

从实验结果可以看出,本文提出的方法ECCI在大多数情况下比只考虑局部结构信息的方法在AUC有较大提升,且对于只考虑社区信息的方法也有一定的提升。具体地,在Facebook和Wiki数据集中优于所有方法,并且在Cora数据集上比仅考虑局部结构信息的方法(DeepWalk、Node2vec)的效果提升了4%～7%,与融合社区信息的方法(ComE、CARE、LouvainNE)相比效果有一定优势,但在边删除过多时,社区划分不准确对实验结果有一定影响。对于F1-Score,ECCI在绝大部分情况下都优于其他对比方法,具有良好的模型性能。

另外,实验将各个方法通过不同运算符得到的边嵌入运用在Facebook数据集的链接预测实验中,以验证方法得到的节点嵌入是否具有适用性。实验结果如图5所示。从图5可以看出,ECCI在Hadamard、Weighted-l1和Weighted-l2运算符下获得的边嵌入向量在链接预测实验中效果较好,其中,Hadamard运算符的效果优于其他所有方法,说明ECCI获得的节点嵌入在大多数运算符下都具有适用性。

图5 Facebook数据集各运算方法结果Fig.5 Results of various algorithms in the Facebook dataset

综上所述,本文提出的方法相对Node2vec和DeepWalk,在嵌入结果中保留了社区信息和社区间信息,同时与融合了社区信息的方法ComE、CARE以及LouvainNE相比,在嵌入结果中保留了网络中的社区间信息,从而预测性能有一定的优势。

3.4.2 社区间的链接预测

实验在社区间链接预测中选择网络10%的边进行删除,原因在于删除过多的边会使网络结构发生巨大变化,导致社区发现效果不佳。具体地,随机遍历网络中的边,通过判断边的社区属性以及删除后网络的连通性进行筛选,使得删除的边中社区内的边(边的两端节点属于同一社区)分别占总删除边数的10%～90%,从而判断嵌入方法是否对网络社区间的关系进行保留。

在3个数据集上进行实验,实验结果AUC和F1-Score(百分制)如表3—5所示。

表3 Cora数据集上社区间链接预测结果Tab.3 Intercommunity link prediction results on Cora datasets

表5 Wiki数据集上社区间链接预测结果Tab.5 Intercommunity link prediction results on Wiki datasets

从实验结果可以看出,本文提出的方法在社区间边多的情况下AUC和F1-Score相比其他对比方法有一定的提升。产生以上实验效果的原因主要是DeepWalk和Node2vec随机生成游走序列,没有融合社区信息。虽然Node2vec考虑了深度优先搜索和广度优先搜索,但是p,q参数并不能提取网络中的社区信息。ComE和CARE虽然都考虑了社区信息,但它们更关注于社区内部的信息提取,而忽略了社区之间的信息保留。LouvainNE方法虽然考虑了不同层次的社区信息,但是一些社区可能联系不大但也被归属到同一层级进行强化,从而导致错误判别节点间是否存在链接。本文提出的方法在游走序列中加入了融合社区信息和社区间信息的社区游走,且由超参数c控制迭代次数,社区间亲密关系控制社区游走概率。

只考虑社区信息的方法ComE在部分结果中依然表现出良好性能的原因在于,它在形成嵌入信息的过程中形成了一个闭环,不断地优化节点嵌入信息和社区嵌入信息,对它们进行一个平衡,因此弥补了只考虑社区信息的不足,但是本文提出的方法从社区间关系的角度对只考虑社区信息的方法进行优化,提升了链接预测实验的AUC分数。同时,通过各方法在不同数据集上的F1-Score对比,可以发现ECCI在大多数情况下都优于其他对比方法,在社区内的边少且社区间的边多的情况下,ECCI相比其他方法有着更好的性能,并且,随着社区内的边不断增加,ECCI的效果与基准方法相比也有一定优势。这说明ECCI在保留网络中的社区信息时考虑比其余方法更加充分,同时保留了社区内信息和社区间信息。

3.5 参数敏感性分析

为了评估ECCI中不同的参数值是如何影响不同数据集上的结果,实验在删除10%边的情况下的链接预测任务上进行,实验结果如图6所示。

图6 参数敏感性实验结果示意图Fig.6 Schematic diagram of parameter sensitivity experimental results

从实验结果可以发现,在Cora数据集中,随着c值的改变,实验结果的精度有先上升再下降的趋势,在c=2时获得最好的结果,Facebook数据集中,最好的结果在c=1时得到,且随着c值的增加链接预测的效果呈下降趋势,而wiki数据集的表现与Cora数据集类似,在c=2的情况下效果最佳。产生上述实验结果的原因可能在于,Facebook数据集中每个社区平均5 300条边,此时对社区中的节点进行游走有很大概率无法走出社区,即节点游走在刻画网络结构的过程中已保留了部分社区信息。而c作为社区游走的迭代次数,每次迭代都可强化网络社区信息及社区间关系,但迭代次数过多可能会导致同一社区的节点嵌入趋于一致,从而将原本没有边连接的节点预测为有边相连,所以在Facebook数据集一次迭代效果最佳。对于Cora和Wiki数据集,它们社区中平均连边分别为151条和498条。节点游走出社区对网络结构进行刻画的概率更大,从而导致社区信息保留较少,故可增大c值强化社区信息。总的来说,在大规模稠密网络(网络中边集远大于点集,社区中边集远大于游走序列长度)中,c值设置偏小,稀疏网络(网络中边集与点集相差不大,社区中边集不多)中c值可适当增大。

然后实验分析了网络表示结果的嵌入维度和游走路径数量对链接预测结果的影响。在Cora和Wiki数据集中,随着dimensions的改变,实验结果有先上升后下降的趋势,在dimensions=64时获得最好的结果。Facebook数据集则是在dimensions=128时获得最好的结果。产生上述实验结果的原因可能是不同的数据集适合的嵌入维度各不相同但是过低或者过高的维度会导致模型欠拟合或过拟合。此外,通过实验分析可以发现,对于稠密数据集Facebook,实验效果随着numwalks的增加而增加,在达到一定规模后产生轻微波动,原因可能在于该数据集规模较大,因此需要多次游走才能更好地学习网络的结构,而对于Cora和Wiki数据集,由于网络规模较小,不需要多次numwalks就可以完成网络结构的学习,实验效果随着numwalks的改变产生轻微波动,但过多的游走次数会产生一定噪声使实验效果降低。

最后,从滑动窗口的实验结果可以看出,网络中的一阶邻居和二阶邻居的重要性通常大于高阶邻居的重要性,但是在Cora这类有明显节点标签信息的网络中高阶信息对嵌入结果有一定提升。

4 结束语

为融合社区信息和社区间信息更好地对网络进行嵌入表示,本文提出了一种融合社区连接信息的网络嵌入方法。该方法通过Louvain算法得到网络中的社区划分,然后通过不同社区之间的亲密关系,对节点生成融合局部结构、社区信息和社区间信息的特定节点序列作为上下文信息,以捕捉网络中的局部拓扑信息和全局信息,该方法丰富了嵌入结果的社区信息和社区间信息。在3个真实数据集的实验结果验证了模型的有效性和优越性,在全局链接预测以及社区间的链接预测任务中AUC和F1-Score相比基准方法都有一定提升。

本文中所提出的算法主要基于网络的拓扑结构,无法处理网络中的其他辅助信息,因此得到的网络嵌入不适用于网络中的边或点含有多种属性的复杂网络,未来将考虑融合各种辅助信息的网络嵌入方法。