保持Motif结构的网络表示学习*

许 磊，黄 玲，王昌栋

中山大学 数据科学与计算机学院，广州 510000

1 引言

随着“大数据”时代的到来，网络（又叫作图）变得无处不在，人们日常生活中所产生的各种各样的数据，都能形成网络。网络不仅是一种数据表示形式，同时也是信息的载体，能够很好地存储两两物体之间的连接关系。如何能够更加有效地对网络进行分析，挖掘出有价值的信息，是如今很多学者密切关注且亟待解决的问题。网络分析的任务大致可以分为4种：节点分类任务、链路预测任务、社区发现任务以及可视化任务。过去的几十年，为了解决上述所提及到的任务，许多学者提出了各种不同的算法。比如，基于模块度优化[1]和谱方法[2]的社区发现算法，基于随机游走来传递标签[3]的节点分类算法，以及基于节点相似度[4]和最大似然模型[5]的链路预测算法等。然而，这些算法大多是在原有的向量空间，即网络邻接矩阵上来推导求解，从而完成相关任务。这样做法虽然直接、方便且解释性强，但需要很昂贵的计算资源。除此之外，邻接矩阵非常稀疏，对于一个大规模网络来说，邻接矩阵中绝大部分都是0，这也使得一些快速有效的算法无法很好地应用。

近年来，网络表示学习（又称为网络嵌入）成为了一个热门领域，引起了很多研究学者的兴趣。网络表示学习可以广义地理解成网络的特征学习，旨在保留网络拓扑结构信息、顶点内容以及其他辅助信息的同时，能够学习出网络的潜在、低维度的嵌入向量空间Rd。之前的网络分析算法，它们认为获取网络结构信息是一个预处理的步骤，因此更多的是依赖于人工提取；而网络表示学习则是将这样一个问题当作是网络分析任务的一部分，使用一种“数据驱动”的模式，学习出能够包含网络结构信息的嵌入空间[6]。图1是网络表示学习的一个流程图，从图中可以直观地看出，网络表示学习起到的是桥梁的作用[7]。

Fig.1 Flowchart of network representation learning图1 网络表示学习的流程图

网络Motif，又称网络的高阶结构，最早是由Milo等人[8]提出的，它指的是由多个节点组成的一个小型子网络结构。在真实应用中，网络Motif在复杂网络分析中起到了至关重要的作用。比如，一个三角型Motif的存在可能说明社交网络中这三个节点的关系如“铁三角”般密切；一个多跳环形结构的存在可能说明金融网络中存在着洗钱的行为；星形网络结构可能对应的是银行客户信息网络中一个合成的造假个人账号[9]。因此，如果能够捕捉出节点的高阶连接模式，那么就能够更加准确地刻画出网络结构，从而更好地完成网络分析任务。

这几年，很多网络表示学习算法被提出并被很好地应用在实际应用中，然而它们大多数只考虑了节点的邻域属性或邻近性，忽略了节点的Motif结构，这样可能会导致一个问题：没有考虑到节点的高阶连接模式。

Fig.2 Problem in previous algorithm图2 之前的算法存在的问题

图2 表示的是节点A和节点B的网络拓扑结构，可以看到，节点A和节点B都有三个邻居，因此如果只考虑节点的邻近性，网络表示学习算法会认为节点A与节点B具有相同的结构，从而使得学习出来的节点嵌入向量会很接近。然而，对于A节点，它没有Motif结构的存在；对于B节点，它存在一个三角Motif结构。因此，A节点与B节点从Motif角度考虑的话是不相同的。然而，目前为止提出的网络表示学习算法都没有考虑到节点的高阶连接模式，因此对于拥有网络Motif结构的节点来说，学习出来的节点嵌入向量可能会不够准确。

为了解决上述问题，本文旨在提出一种考虑Motif结构的网络表示学习算法，那么需要考虑两个难题：（1）如何根据指定的Motif结构，捕捉到各个节点的高阶连接模式；（2）如何将各个节点的Motif结构信息应用到网络表示学习上。针对上述提出的难题，本文提出了MPNE（Motif-preserving network embedding）模型，研究工作主要有：

（1）提出了一种网络高阶结构表示学习算法框架——MPNE，使得在进行网络表示学习时能够考虑节点的高阶结构信息。

（2）MPNE算法首先根据邻接矩阵A构建出基于Motif的权重矩阵W，接着通过APPR（approximate personalized PageRank）算法，计算出每个节点到每个节点之间的概率，从而将各个节点的高阶结构信息包含在内。

（3）提出了基于Motif的随机游走MotifWalk，使得随机游走时更倾向于与当前节点有着紧密Motif结构关系的节点。

（4）在三个真实世界的数据集上进行了实验，选取节点分类作为网络分析的任务，实验结果证实了提出的MPNE算法的有效性，特别是在稠密以及Motif结构丰富的网络中，Micro-F1以及Macro-F1都比对比算法提高了不少。

2 相关工作

网络表示学习的目的是为了把原本稀疏的邻接矩阵映射到一个低维的向量空间，使得节点能够用低维稠密的向量表示的同时，也能保持原来的网络结构信息、节点内容等。本文简要地介绍目前网络表示学习算法的不同分支的一些经典算法。

早期的网络表示学习，绝大多数都把目光放在矩阵分解的方法上。矩阵分解的算法主要是将网络节点的联系通过一个矩阵表达，之后对这个矩阵进行分解从而得到节点的向量表达。最早的一篇基于矩阵分解的网络表示学习算法是LLE（locally linear embedding）算法[10]。它认为在向量空间中，每一个节点应该是它所有邻居节点的线性组合，而线性组合的权重是由网络的节点邻接矩阵来决定的。随后，LE（Laplacian eigenmaps）算法[11]则认为如果两个节点之间的权重值越高则这两个节点在向量空间中越接近，而且是用拉普拉斯矩阵来决定这个权重值。之后，GF（graph factorization）算法[12]在分解节点邻接矩阵的过程中加入了一个正则化项来控制节点表示向量的秩，同时运用随机梯度下降的方法进行优化，使得算法在大规模图中也能高效运行。

基于随机游走方法的网络表示学习是近年来这个领域比较火的方法。随机游走类的算法在网络分析领域一直被广泛使用，原因是因为随机游走能够很好地反映出网络结构的特性，且相比于矩阵分解的方法，基于随机游走的方法在性能上要提高很多。DeepWalk算法[12]是第一个把随机游走应用到网络表示学习中的，它主要通过模拟随机游走的过程，获取到了每个节点在整个网络中游走的一条路径。之后，这条路径可以看作是一段语句，而路径中每一个节点则是语句中的一个单词，然后应用到自然语言处理领域中的Word2Vec模型上，从而得到每一个节点的嵌入向量。它的核心思想是，如果两个节点很相近，则在游走的路径上会更可能地同时出现。随后node2vec算法[14]改进了DeepWalk算法的随机游走过程，它认为游走时不仅仅要考虑一阶相似性，还要考虑二阶相似性，因为如果两个节点的共同邻居越多，说明这两个节点越相似。

随着深度学习的高速发展，基于深度学习的表示学习算法如SDNE（structural deep network embedding）[15]和DNGR（deep neural network for graph representation）[16]也随之被提出。相比其他的方法，基于深度学习能够很好地在降维的同时学习到数据的非线性特征。

除此之外，有其他一些算法还会考虑到网络节点的属性信息[17]。然而目前为止，网络表示学习大多只考虑了网络节点与节点之间的相似性，没有去考虑网络中Motif结构的存在。Motif结构在网络中起到了很大的作用，往往组成Motif的节点关系更为密切，因此如果能捕捉到每个节点的高阶连接模式，那么对于整个网络结构的刻画会更为准确，基于这样的考虑，本文提出了MPNE算法。目前为止，这是第一篇考虑了网络高阶结构的网络表示学习方法。

3 保持高阶结构的网络表示学习算法

给定一个无权重网络G=(V,E)，以及它的邻接矩阵A，其中：如果节点i与节点j有连接关系存在，即存在一条边，则A(i,j)=1；n=|V|表示网络中节点的个数，m=|E|表示网络中边的数量。假设已知网络Motif结构T，本文提出的算法想要解决的问题就是将每一个节点v∈V映射到一个低维的向量空间Rd中，即学习出一个映射方法fG:V→Rd，其中d≪n，使得在向量空间Rd中，原本网络中每个节点的Motif结构T会很好地被保留下来。

3.1 基于Motif的APPR

这节介绍如何在经典的APPR算法上考虑节点的Motif结构。思路是首先构建基于Motif的网络矩阵，随后将APPR算法应用到这个权重矩阵上，从而得到每个顶点的PageRank值。

3.1.1 构建Motif权重矩阵

要构建基于Motif的矩阵，核心思想是将输入的邻接矩阵转换成一个无向带权重的矩阵，而这个权重是由两两节点共同参与形成的Motif数量决定[18]。假定基于Motif所构建的矩阵为W，则W(i,j)的值为节点i与节点j所共同参与构成的Motif的数量。如图3所示，可以看到，节点1与节点3共同参与构成的三角Motif的数量为2，分别是（123）和（134），因此对应位置上W(1,3)的权值为2；而节点1与节点2形成的三角Motif数量只有一个，因此对应位置上的权值为1。不同的Motif具有不同的特性，在实验时，要根据具体的任务选用适合的Motif网络结构；如果网络中同时存在不同类型的Motif结构，只需针对特定任务所选取的Motif结构进行研究即可。

Fig.3 Motif weighted matrix图3 Motif权重矩阵

这样一来，就可以得到一个基于Motif的无向带权网络Gw=(Vw,Ew,W)，其中Vw指的是拥有Motif的节点。

3.1.2 预估个性化PageRank向量

个性化PageRank向量（PPR）代表的是一个稳定的随机游走的分布概率。在随机游走的每一步，有一个转移概率α∈(0,1)，它代表着当前随机游走到的节点，有(1-α)的概率会回到随机游走的起始点u，有α的概率会继续随机游走到下一个节点。之所以称之为“个性化”，就是保证了随机游走时只能跳转到一些特定的点，从而反映出偏好。在这里，选择特定的点为随机游走的起点，这样一来，越接近起始点u的节点，在从u节点开始的随机游走的分布概率值（即PPR向量pu）中的值越大。稳定的分布概率可以通过式（1）来表达：

其中，I是单位矩阵，P代表着在整个网络随机游走的概率转移矩阵。随机游走是一个马尔科夫链的一个过程，即下一步只与当前结果有关，与更早之前的结果无关。因此，随机游走到下一个点的概率取决于当前节点与当前节点的邻近程度，因此P=WD-1，其中W是网络的Motif权重矩阵，D=diag(We)代表的是度数矩阵，度数矩阵是个对角矩阵，对角元素为每一个节点的度数，e表示的是所有元素为1的矩阵。eu是节点u的指示向量，如式（2）所示：

如果要想求得这样一个稳定分布概率，一般是通过幂迭代的方法得到。然而，这样做会带来高昂的计算代价，因此本文采用文献[19-20]当中的快速估算PageRank值算法。算法通过一个误差容忍值ε来求得预估向量pu，使得预估值p͂u满足式（3）所示条件：

其中，D指的是度数矩阵。

基于Motif的APPR（MAPPR）伪代码如算法1所示。

算法1 Motif-Approximate-PPR

输入：网络Gw=(Vw,Ew,W)，起始节点u，转移概率α，误差容忍值ε。

输出：个性化PageRank向量的预估值。

3.2 MPNE算法框架

在解决了第一个难点后，开始解决第二个难点：如何将包含了节点高阶连接模式信息的个性化PageRank预估值应用到网络表示学习上。本文采用的是基于DeepWalk算法的想法，通过特定的随机游走得到路径，将路径运用到自然语言处理领域上的Word2Vec模型上。

3.2.1 DeepWalk模型

Word2Vec算法是Mikolov等人提出用来学习语料库中单词的分布式表达[21]。随后，DeepWalk算法受此启发，将语料库中的单词这样一个概念换成网络中的节点，从而将经典的Word2Vec算法应用到网络表示学习领域上。DeepWalk通过随机游走得到一条路径，这个路径可以被看作是句子，而单词的上下文可以看作这条路径中选定节点的邻居。假如给定一个网络G=(V,E)，则整个模型的目标函数如式（4）所示：

其中，N(v)是节点v在路径上的上下文邻居，p(c|v;θ)表示的是基于给定节点v和当前的参数θ下出现节点c的条件概率。之后，DeepWalk采用了二叉霍夫曼树和随机梯度下降优化了目标函数的求导。最后通过反向传播算法，不断优化更新从而得到最终的节点向量表示。

3.2.2 MotifWalk

然而，DeepWalk算法中的随机游走只考虑了一阶相似性，即在随机游走的过程，下一步只会跳到当前节点的邻居节点，因此DeepWalk算法只适用于不带权重的无向图。而需要的随机游走过程是基于求解得到的个性化PageRank预估值进行的，因此在这里，本文提出了基于Motif的随机游走MotifWalk，伪代码如算法2所示。

算法2 MotifWalk

输入：网络Gw=(Vw,Ew,W)，起始节点u，路径长度L，转移概率α，误差容忍值ε。

输出：基于Motif的随机游走路径walk。

算法2中的第4行概括了MotifWalk是如何进行随机游走的，即下一步节点的选择是通过带权重的非均匀采样实现，而权重则是当前节点的个性化PageRank预估值。这样一来，路径会更可能地添加PageRank值高的节点，也就是与当前节点有很强Motif结构联系的节点。

3.2.3 MPNE算法伪代码

最后，整个算法伪代码如算法3所示。

算法3Motif-preserving network embedding

输入：网络Gw=(Vw,Ew,W)，向量空间维度d，转移概率α，误差容忍值ε，每个节点的随机游走次数γ，上下文窗口大小w，随机游走的路径长度L。

输出：节点的向量表示矩阵Φ∈R|Vw|×d。

基于之前的预备知识，首先从原网络中得到Motif权重网络Gw，之后对这个网络中每一个节点进行MotifWalk，这样就能得到以网络中每一个节点为起始节点的游走路径。这个过程重复γ次，最终能够得到路径集合Ψ。将路径集合放到Word2Vec模型中，设置好上下文的窗口大小w，就能得到所需的网络节点向量表示矩阵Φ。

4 实验结果与分析

本章首先介绍实验的设置，包括实验所采用的数据集、评估标准以及对比算法。之后，对MPNE算法的实验结果以及参数敏感性进行分析。本文实验采用的Motif结构为三角Motif。

4.1 实验设置

4.1.1 数据集

本文实验所采用的数据集有3个，它们分别是：

（1）Cora[22]数据集是基于链接的数据集，是一个引用网络。整个数据集是由7个不同领域的2 708篇科学出版物，以及5 429条链接组成。如果两篇科学出版物存在着引用/被引用关系，则这两篇科学出版物存在链接关系。节点的类标表示这篇科学出版物属于哪个领域。经过统计，该数据集拥有三角Motif结构的节点有1 470个。

（2）Citeseer[22]数据集和Cora数据集相似，同样是基于链接的数据集，是一个引用网络。整个数据集是由6个不同领域的3 312篇科学出版物，以及4 732条链接组成。经过统计，该数据集拥有三角Motif结构的节点有1 189个。

（3）TerroristAttack数据集是国外PIT（profile in terror）项目中的一个联系网络数据集。整个数据集由1 293个节点以及3 172条边组成，每一个节点表示一场恐怖袭击，如果两场恐怖袭击的参与者是属于同一恐怖组织的，则这两个节点存在连接关系。每个节点有一个类标，表示这场恐怖袭击通过什么手段实施犯罪，共有6类，分别是：纵火、轰炸、绑架、放射性物质、枪械武器和其他。经过统计，该数据集拥有三角Motif结构的节点有354个。

4.1.2 对比算法

为了验证本文算法的表现，本文和以下算法进行了对比：

SpectralClustering[23]：谱聚类算法首先通过网络G的邻接矩阵求得网络的归一化拉普拉斯矩阵L͂。之后，选取矩阵L͂的前d个最小特征值所对应的特征向量作为节点的表示向量，从而将网络嵌入到向量空间Rd中。

LINE（large-scale information network embedding）[24]：LINE算法不仅考虑了一阶相似性，同时也考虑了二阶相似性，从而使得最终学习到的向量空间中能够既保留网络局部结构信息，也能保留网络全局结构信息。

DeepWalk：DeepWalk算法是通过随机游走生成路径，之后沿用Word2Vec算法的Skip-Gram模型从而将网络嵌入到向量空间Rd中。

4.1.3 评估准则

本次实验选择完成的网络分析任务为节点分类，由于节点的类标种类有多个，因此是多分类任务。由于是多分类任务，因此采用的评测指标为Micro-F1和Macro-F1，如式（5）、式（6）所示。其中TPi指的是类标i被预测正确的数量，FPi指的是实际上不属于类标i但被预测为类标i的数量，FNi指的是实际上属于类标i但没被正确预测的数量，M指的是类标个数。

这里需要一提的是，在实验中计算Macro-F1时，有一些数据集可能存在某个类标使得Fi为NaN，从而使得Macro-F1显示为NaN的结果。因此，在求解Macro-F1中的Precisioni、Recalli以及Fi时，会在分母上加1，避免出现NaN的情况。

4.1.4 实验参数设置

实验时，对比算法所选用的参数都为对比算法论文中提供的缺省参数，其中SpectralClustering以及DeepWalk算法的d设置为64，LINE算法的d设置为500。为了使得实验结果更有说服性，这里MPNE算法的实验参数设为与DeepWalk算法相同。

4.2 实验结果分析

网络表示学习算法的重点是更好地将网络节点通过嵌入向量表示，因此为了体现这一点，所采用的机器学习算法也应该越简单越好。本文最终选用KNN算法来完成多分类任务，训练集是从数据集中随机选取，它的个数占数据集个数的比例从10%依次增加至90%。KNN采用的是欧式距离，经实验发现，K值的选择在8～15之间比较合适。实验过程重复20次，最后计算Micro-F1以及Macro-F1的平均值作为最终结果。由于本文提出的算法是针对节点的Motif结构，因此最后进行实验的节点是数据集中具有Motif结构的节点。最终实验结果如表1～表3所示。这说明，今后如果遇到网络已知的真实类标比较少的情况下，本文提出的算法能够更好地完成网络分析任务。表2显示的是在Citeseer数据集上运行的结果，然而这个数据集上表现得最好的是DeepWalk算法。经过分析，Cora数据集共有2 708个节点，5 429条边，其中具有三角Motif结构的节点有1 470个；而Citeseer数据集共有3 312个节点，却只有4 732条边，此外，具有三角Motif结构的节点只有1 189个。也就是说，相比于Citeseer数据集，Cora数据集更加得稠密，含有的Motif结构信息更加丰富，因此本文算法MPNE能够表现得更好；而Citeseer数据集比较稀疏，含有的高阶连接模式信息较少，因此DeepWalk算法能够表现得更好。这说明，本文提出的MPNE算法更适用于稠密网络，有助于更好地分析网络中的Motif结构信息。最后，表3显示的是在TerroristAttack数据集上运行的结果。Terrorist Attack数据集共有1 293个节点以及3 172条边，然而实际上大多数节点都是单独一个节点存在，经过统计，最终只有645个节点参与了边的构建，且只有354个节点具有三角Motif结构，因此整个网络比较稠密，Motif结构信息比较丰富。从结果来看，当训练集比例大于20%时，MPNE算法表现得最好。

Table 1 Multi-classification results on Cora表1 在Cora数据集上的多分类结果

Table 2 Multi-classification results on Citeseer表2 在Citeseer数据集上的多分类结果

Table 3 Multi-classification results on TerroristAttack表3 在TerroristAttack数据集上的多分类结果

4.3 参数敏感性分析

本节进行参数敏感性实验，从而检测出所用参数对算法结果的影响。这里选用Cora数据集做测试，选取Micro-F1作为测试指标来观察，以及训练集的比例设为90%。当以某一参数作为变量进行实验时，其他参数选用缺省值。本文验证了嵌入空间向量维度参数d，如何选择上下文邻居节点到Word2Vec模型的参数（随机游走次数、游走的路径长度以及上下文窗口大小）和计算个性化PageRank向量预估值的参数（转移概率和误差容忍值），最后结果如图4所示。

可以看到，有些参数的选择对结果影响不大，如向量维度、随机游走次数以及上下文窗口大小。从结果中得出，向量维度d的建议取值是32，随机游走次数γ的建议取值是10以及上下文窗口大小w的建议取值是8，因为此时算法效果比较好，且如果取了更大的值会带来更高的一个计算代价，但却不能使算法表现提高，得不偿失。有些参数的选择对结果会稍微影响，比如当路径长度大于50和转移概率大于0.9时，算法的表现会下降；而有些参数的选择则会对结果造成比较大的影响，比如当误差容忍值ε的取值太大时，会使算法表现得比较糟糕，因此结合计算性能和算法表现考虑，误差容忍值ε的建议取值为0.01×|V|/2|E|。

Fig.4 Parameter sensitivity analysis图4 参数敏感性分析

5 结束语

本文提出了保持Motif结构的网络表示学习算法——MPNE算法，从而在学习网络节点的向量表示时，更加侧重地考虑节点的高阶连接模式。算法首先根据需要的网络Motif结构得到基于Motif的网络权重矩阵；接着根据算法MAPPR来快速求得基于Motif的个性化PageRank预估值；最后，根据这个预估值进行MotifWalk，得到每一个节点的随机游走路径，从而能够运用Word2Vec模型来得到网络的向量表示。为了验证提出的算法性能，本文将算法应用到三个真实数据集上，以及与三个经典的网络表示算法进行比较。从实验结果上来看，在稠密以及Motif结构丰富的网络中，本文的算法表现得更好，能够更好地捕捉到网络结构信息。除此之外，本文还做了与算法相关参数敏感性分析的实验。

网络表示学习领域是最近蓬勃发展的一个领域，很多学者提出了许多创新、有启发性的算法来更好地揭示网络的本质，挖掘了很多隐藏的信息。然而，随着数据的形式越来越多元化，网络也会变得越来越复杂，而现有的网络表示学习算法还有很多空白区域没有涉及，比如本文提出的网络高阶结构。而在本文的基础上，在下一步的研究中，可以更加关注动态网络的表示学习，比如以网络高阶结构为载体来揭示动态网络结构变化的趋势，从而来预测网络的发展变化。除此之外，如今异构信息网络越来越热门，因为它是由不同类型的节点以及不同类型的边构成的，所以异构信息网络的表示学习也是会被不断关注、探究的方向。