基于改进随机游走的网络表示学习算法

王文涛 黄烨 吴淋涛 柯璇 唐菀

摘 要：现有的基于Word2vec的网络表示学习（NRL）算法使用随机游走（RW）来生成节点序列，针对随机游走倾向于选择具有较大度的节点，生成的节点序列不能很好地反映网络结构信息，从而影响表示学习性能的问题，提出了基于改进随机游走的网络表示学习算法。首先，使用RLP-MHRW算法生成节点序列，它在生成节点序列时不会偏向大度节点，得到的节点序列能更好地反映网络结构信息;然后，将节点序列投入到Skip-gram模型得到节点表示向量;最后，利用链路预测任务来测度表示学习性能。在4个真实网络数据集上进行了实验。在论文合作网络arXiv ASTRO-PH上与LINE和node2vec算法相比，链路预测的AUC值分别提升了8.9%和3.5%，其他数据集上也均有提升。实验结果表明，RLP-MHRW能有效提高基于Word2vec的网络表示学习算法的性能。

关键词：网络表示学习;随机游走;链路预测;无偏采样;机器学习

中图分类号： TP391; TP18

文献标志码：A

文章编号：1001-9081（2019）03-0651-05

Abstract： Existing Word2vec-based Network Representation Learning （NRL） algorithms use a Random Walk （RW） to generate node sequence. The RW tends to select nodes with larger degrees， so that the node sequence can not reflect the network structure information well， decreasing the performance of the algorithm. To solve the problem， a new network representation learning algorithm based on improved random walk was proposed. Firstly， RLP-MHRW （Remove self-Loop Probability for Metropolis-Hastings Random Walk） was used to generate node sequence. This algorithm would not favor nodes with larger degrees while forming a node sequence， so that the obtained sequence can efficiently reflect the network structure information. Then， the node sequence was put into Skip-gram model to obtain the node representation vector. Finally， the performance of the network representation learning algorithm was measured by a link prediction task. Contrast experiment has been performed in four real network datasets. Compared with LINE （Large-scale Information Network Embedding） and node2vec on arXiv ASTRO-PH， the AUC （Area Under Curve） value of link prediction has increased by 8.9% and 3.5% respectively， and so do the other datasets. Experimental results show that RLP-MHRW can effectively improve the performance of the network representation learning algorithm based on Word2vec.

Key words： Network Representation Learning （NRL）; Random Walk （RW）; link prediction; unbiased sampling; Machine Learning （ML）

0 引言

有在现实世界中，网络可以很好地描述一些关系系统，比如社会、生物和信息系统。系统中的每个实体都映射到网络中的一个节点，实体之间的关系被映射到网络中的边。网络结构有助于更直观地了解现实世界中的事物关系，例如，利用网络结构表示的微博数据，能很清楚地表示微博用户的关注和被关注信息;在蛋白质相互作用网络里连边展示了蛋白质间能否相互反应。但是，想要进一步了解网络的深层信息就需要用到网络分析和数据挖掘的技术。网络分析任务通常涉及节点和边的信息预测，在一个典型的链路预测任务中，通常试图根据观察到的链接和节点的属性来预测两个节点之间是否有连接[1]。链路预测被广泛地应用于各个领域[2]，越来越多的国内外学者开始研究复杂网络中的链接预测问题[3]。

随着机器学习算法的盛行，越来越多的机器学习算法被设计出来，其性能也远超传统算法。但是，网络结构数据不能直接作为机器学习算法的输入，一个直观的想法就是将网络结构特征提取出来并嵌入到向量中，将这个特征向量作为机器学习算法的输入实现网络分析任务。这个向量必须要尽可能地包含原始网络结构的信息，且维度不能太大，网络表示学习（Network Representation Learning， NRL）就正好滿足了这一需求。网络表示学习算法将网络信息转换为低维实值向量[4]，在学习到低维向量之后，就可以使用现有的机器学习方法来简单高效地执行网络分析任务，这不仅避免了传统方法的复杂计算，还提高了算法性能[5]。

Mikolov等在文献[6]中提出的Word2vec神经网络语言模型在词表示上取得良好效果，Perozzi等受此文启发在文献[7]提出DeepWalk算法，第一次将深度学习中的技术引入到网络表示学习领域，文中作者利用随机游走（Random Walk， RW）从网络中生产节点序列类比于“句子”，将节点类比于“词”投入到Word2vec模型中得到节点表示向量，在网络分析任务上取得较大的性能提升。随后又出现了基于简单神经网络的LINE（Large-scale Information Network Embedding）[8]和改进DeepWalk的node2vec[2]等算法。LINE算法没有延用DeepWalk的思想，而是对所有的第一级相似度和第二级相似度节点对进行概率建模，最小化概率分布和经验分布的距离来得到表示结果，有着较好的表示效果;node2vec算法在生成节点序列时没有像DeepWalk那样均匀地随机选取下一节点，而是引入p、q两个超参数来均衡采样过程的采样深度和宽度，提升了算法的扩展性，同时还提高了节点表示的性能。

这些基于Word2vec的网络表示学习算法，使用随机游走（RW）或其改进算法来得到节点序列，然而，RW算法在采样时会偏向大度节点，会导致采样样本不能正确反映完整的网络拓扑信息[9];所以，使用RW算法生成节点序列的网络表示学习算法，其性能也会受到节点采样的影响。

针对这一问题，分别使用MHRW（Metropolis-Hastings Random Walk）[10]和改进后的MHRW代替RW生成节点序列，旨在使采样得到的节点序列能更好地保留原网络的结构特征。为了测度网络表示学习算法的性能，本文使用常见的网络分析任务——链路预测来衡量网络表示学习算法的性能。最终实验结果显示，相比基准对比算法，本文所提算法有更好的链路预测效果，即本文所提网络表示学习算法有更好的表示性能。

1 相关问题

本章主要介绍与本文工作相关的定义、模型和问题。

1.1 Word2vec模型

Mikolov在文献[6]中提出Word2vec神经网络语言模型，该模型能通过给定文本快速地学习词向量表示。Word2vec中包含CBOW（Continuous Bag-Of-Words model）和Skip-gram（continuous skip-gram model）两种语言模型。前者利用词的上下文来预测中间词;后者则利用当前词来预测其上下文。在使用Word2vec时可以通过设置相应的参数来选择所要使用的模型。这两个模型都是包含输入层、投影层和输出层的三层神经网络，如图1所示。

1.2 网络表示学习

网络表示学习（NRL）定义：给定网络G（V，E），对任意节点v∈V，学习低维向量表示rv∈Rd，rv是一个稠密的低维实数向量，并且满足d远小于|V|。

传统机器学习结果的好坏极度依赖人工特征设计，这一过程繁琐且精度不高。信息化时代导致数据量激增，在庞杂的数据中寻找有价值的特征无疑是一项耗时耗力的工作，最终还很难找到令人满意的特征。表示学习的出现就解决了这一问题，它的目标是从原始数据中自动地学习到有意义的特征表示。

网络表示学习算法负责从网络数据中学习得到网络中每个节点的向量表示，之后这些节点表示就可以作为节点的特征应用于后续的网络应用任务，如节点分类、链接预测和可视化等[4]。

1.3 基于Word2vec的网络表示学习

Word2vec神经网络语言模型最初是用来学习词表示向量的，Perozzi等在DeepWalk中第一次把Word2vec应用到网络表示学习中来，他们把在网络中利用RW采样得到的节点序列类比“句子”，把节点类比“词”，投入到Word2vec模型中得到了节点的表示向量，并获得了很好的表示效果。算法的整体框架如图2所示。

图2中，k表示节点序列的长度，d表示表示向量的维度。从图2可以看出，采样算法得到的节点序列是影响后续产生的节点表示特征向量的关键步骤之一，所以采样算法的性能也将直接影响到整个模型的性能。

1.4 RW及其有偏性

RW算法的思想是从当前节点出发以等概率选取其邻居节点作为下一个采样节点。经典的随机游走采样的转移概率表达式如式（1）：

对于RW算法，G（V，E）中任意节点v被采样到的概率是πv=kv2E[11]，其中|E|是目标采样图的边数，很容易看出RW采样时会偏向于大度节点。

2 本文方法

这一章里，首先介绍了MHRW算法的思想并在推导过程中说明了MHRW采样的无偏性，随后就MHRW算法的缺点进行了讨论和改进。

2.1 MHRW

文献[10]中提出的MHRW算法是一种无偏采样算法，对于MHRW算法，G（V，E）中任意节点v被采样到的概率是πv=1/|V|，即任意节点被采样到的概率是相等的。MHRW算法是借鉴了MH（Metropolis-Hasting）[10]算法的思想而形成的。

MHRW算法就是在RW采样的基础上引入MH算法，从RW的概率密度函数中采样，构建一个平稳分布状态为均匀分布的马尔可夫链。结合式（2）就得到了MHRW算法的转移概率表达式如式（3）：

从式（4）可以看出，MHRW算法的节点转移概率是由当前节点u的度和其邻居节点v的度共同决定的，当v=u时，表示节点停留在当前节点。从MHRW算法的公式推导过程容易看出，MHRW采样算法是等概率采样任意节点，即MHRW是無偏的。

2.2 RLP-MHRW

MHRW在节点采样时会有一定概率停留在当前节点，为了更好地理解这个停留概率这里用自环率Ci来表示节点的停留概率即Ci=Pi，i∈[0，1），MHRW导致自环率如图3所示。

图3中节点上的数字表示节点的度，边上的数字（没有画出全部的边）表示利用式（4）计算出来的节点间的转移概率，为了表示自环率图3在节点自身上加了一条自环边。可以看出节点x和节点z的自环率高达0.74，节点e的自环率更是高达0.983，这意味着当游走到这些节点时将会长时间地停留在这些节点，导致采样算法收敛慢。

在网络表示学习中，节点序列的采样希望能尽可能地发现节点的邻域结构信息，类似与图3的高自环率会导致采样算法有限的采样步长内丢失较多的邻域节点;并且，转移概率的严格对称也并不合理，例如，图3中节点e的度为1，只有一个邻居节点f，那么从节点e只能转移到节点f，转移概率应该为1，而不是与f到e对等的0.017。

所以，本文进一步将MHRW算法产生的自环率去掉，得到RLP-MHRW（Remove self-Loop Probability for MHRW），并且将转移概率变为有向，同时在去自环率的过程中保持MHRW算法原有的节点转移概率分布比例，并且保证转移概率矩阵行和为1。具体做法是先用MHRW算法计算出各节点转移概率，然后将节点u的自环率Cu（非0）按照其转移到邻居节点的概率Pu，v的比例划分，并将划分得到的概率对应追加给Pu，v，数学化定义如式（5）：

2.3 算法实施

针对RW算法在图采样上偏向于大度节点的缺点，使用本文提到的MHRW算法和RLP-MHRW算法来进行网络采样生成节点序列，然后，分别利用Skip-gram模型训练得到节点表示向量，算法定义如下。

算法2里的Sample（）函数会依据给定的概率来选择返回的节点，利用式（4）计算P表示该算法为MHRW，利用式（5）则为RLP-MHRW。在给定网络G=（V，E）和相关的参数后，算法1将会计算出G中所有节点的表示向量。

3 仿真与性能分析

3.1 實验数据及数据处理

本文实验数据为4个不同大小、不同领域、具有代表性的真实网络数据集，均为无向无权网络，细节分别如下：

Facebook[12] 一个美国的社交网络，数据中节点表示用户，边表示用户间的朋友关系，网络中有4039个节点，88234条边;

arXiv ASTRO-PH[12]（arXiv Astro Physics collaboration network） 一个从arXiv电子出版论文中生成的论文合作网络，其中节点表示科学家，边表示科学家合作过论文，网络中有18722个节点，198110条边;

USAir（http：//vlado.fmf.uni-lj.si/pub/networks/data/） 一个航空路线网络，其中节点表示机场，边表示机场间的航线，网络中有332个节点，2126条边;

Metabolic（http：//www.linkprediction.org/index.php/link/resource/data/） 一个生物代谢网络，其中节点表示线虫代谢物，表示代谢物之间能直接参与酶催化反应，网络中有453个节点，2025条边。

为了评估算法，本文将数据集随机地划分为训练集和测试集，50%的边被抽取作为训练集，50%的边作为测试集。在随机划分过程中要保证训练集网络的连通性，数据集的标签依据原网络中边的有无来定，原网络中存在的边标签为1，其他为0。

3.2 基准方法

为了展示算法性能，本文选用以下算法作为对比：

DeepWalk 该方法是第一个将深度学习使用到网络表示学习中的算法，它使用均匀随机游走来生成节点序列，利用Skip-gram模型来学习节点向量表示;

LINE 该方法将学习d维的特征表示分为两部分：第一部分，在直接邻居节点上模拟BFS（Breadth-First Search）来学习d/2维的特征;第二部分，严格的从距离源节点2-hop的节点中采样学习剩下的d/2为特征;

node2vec node2vec是一个半监督的NRL模型，它由p、q两个超参数来分别控制随机游走的深度和广度，这两个超参数需要额外的训练。当p=q=1时，node2vec等价于DeepWalk。

3.3 算法评价

本文网络表示学习算法得到的是节点表示向量，要利用链路预测任务来测度算法的性能就需要得到边的特征表示向量，这里直接引用文献[2]中的映射操作，如表1所示。

链路预测的结果度量使用AUC（Area Under the receiver operating characteristic Curve）值作为算法评价指标，AUC是常用的二值分类评价标准，从整体上评价算法精度。利用预测算法计算出所有节点间边存在的分值，AUC值可以看作是在测试集中随机选取一条存在边的分值大于随机一条不存在的边分值的概率。一般AUC值会大于0.5，值越高算法精度越高，最大不超过1。公式化的定义如下：

3.4 实验环境及参数设置

实验硬件环境为：Intel Core i7-4790 （3.6GHz*8） CPU，32GB内存;

软件环境为：Ubuntun16.04系统，使用python 2.7版本，主要python第三方包及版本有：用于科学计算的numpy 1.12.1版，处理网络数据的networkx 1.11版和包含Word2vec的gensim 2.2.0版;

实验参数：采样迭代次数r=10，节点序列长度l=80，Skip-gram模型窗口设为10，节点向量维度为d=128。

3.5 实验及结果分析

为了更方便地将本文方法与相关基线进行比较，本文将链接预测作为所有方法的下游任务。对于所有的模型，使用逻辑回归来预测。为了减弱随机性，将本文所提算法在3.1节提到的数据集上独立重复实验20次，以20次实验的AUC平均值作为最终结果。表2为各算法在预测结果上AUC值的对比，表3为MHRW和RLP-MHRW生成节点序列的执行时间的对比。