基于综合游走策略的边嵌入链路预测算法

艾春玲，何 敏，吕 亮，杨青青

(云南大学 信息学院，云南 昆明 650500)

网络可以很好地描述社会、生物和信息系统[1]，例如：社交关系网络、交通物流网络、生物网络和蛋白质相互作用网络等[2-5].其中不同的个体或不同的事物被表示成图中的节点，个体间的关系、事物间的联系被表示成图中节点间的连边，这就是常见的节点图(Graph，G)[6].若将关系或联系表示成图中的节点，则获得的图相对复杂，被称为连边图(Line Graph，LG)[7].

图嵌入（Graph Embedding，GE）能方便、高效地提取图的特征信息，并将学习到的特征嵌入到低维的向量空间，对图数据的研究具有重要意义.矩阵分解(Matrix Factorization，MF)通过对不同的连接矩阵进行分解达到降维的目的，实现节点向量的嵌入，推动了图嵌入技术的发展.如谱聚类(Spectral Clustering)[8]通过对拉普拉斯矩阵的分解得到节点的嵌入向量；GraRep[9]模型采用奇异值分解（Singular Value Decomposition，SVD）K-步转移矩阵，得到节点的向量表示等.但基于矩阵分解的方法受邻接矩阵边的约束，在保持图的二阶和高阶相似性方面存在不足[10].受Word2Vec词嵌入模型的启发，DeepWalk[11]首次将深度学习应用于图嵌入领域，在一定程度上提升了节点向量潜在表示的效果.但Word2Vec中的Skip-gram模型[12]没有充分考虑被采样的下一个节点对采样过程的影响，游走生成的节点序列质量不佳，导致得到的节点向量表示性不强.

现有图嵌入方法及其下游任务，如链路预测(Link Prediction，LP)默认采用节点图，SVD的方法对邻接矩阵进行处理，生成节点嵌入，图神经网络（Graph Neural Network，GNN）[13]利用节点间的消息传递捕捉某种依赖关系，使生成的嵌入可以保留任意深度的领域信息[14].相对于节点图，连边图包含的信息更丰富.近年来，部分学者开始关注用连边图表示网络及节点间的关系，如线图神经网络模型[15]、ONNEE模型[16]通过使用边到节点的方向来学习更好的节点表示.

针对基于Skip-gram模型的图嵌入方法没有充分考虑被采样的下一个节点对采样过程的影响、不能直接获得边向量这两个问题，本文对网络图的表示和构成进行了研究，设计了一种以连边图为研究对象的图嵌入算法Line2Vec，并在此基础上提出边嵌入链路预测框架Line2Vec-L.首先，采用无偏和有偏的思想，设计了一种可以处理连边图的图嵌入算法Line2Vec，该算法在采用随机游走生成节点序列时，考虑了当前节点和邻居节点对游走概率的影响，充分调动了被采样的下一个节点在采样过程中的主动性，提高了节点序列的生成质量；然后结合关联矩阵，将获得的边向量用于链路预测.实验结果表明，本文提出的方法提升了链路预测的性能.

1 边嵌入链路预测框架

1.1 边嵌入链路预测框架（Line2Vec-L）描述Line2Vec-L主要分为两个部分.首先，通过有偏+无偏的图嵌入算法Line2Vec生成边向量；然后，结合关联矩阵得到不存在边或未知边的向量表示，将获得的边向量用于链路预测，预测框架如图1所示.在Line2Vec-L框架中，首先将节点图转换为连边图，得到表示节点与连边关系的关联矩阵，采用无偏+有偏的灵活随机游走采样策略设计了一种改进的可以处理连边图的图嵌入算法Line2Vec，通过连边图和Line2Vec算法可获得存在边的向量表示，结合关联矩阵进而得到其它未知边的向量表示，最后将获得的边向量用于链路预测.

连边图由节点图转换而来，连边图的节点是节点图的边，若节点图中两条边有一个公共节点，则连边图中，这两个节点之间有边.

图1 边嵌入链路预测框架（Line2Vec-L）Fig.1 Link prediction algorithm using edge embedding（Line2Vec-L）

图2 节点图、连边图与边向量之间的关系Fig.2 The relationship among node graph, link graph and edge embedding

关联矩阵表征连边图中节点与节点间的关系，用B∈RN×Y表示，其中元素Bij定义为：

式中：vi为 节点图的节点，ej为连边图的节点.可见，关联矩阵实际上代表了节点与边的关系.

1.2 图嵌入算法Line2Vec与边向量的生成生成边向量有两种方法，一是将节点图嵌入为节点向量，然后利用边函数得到边嵌入向量；二是本文采用的直接将节点图转换为连边图，然后将连边图输入本文提出的改进算法Line2Vec中得到边嵌入向量.节点图、连边图与边嵌入向量3者之间具体的转换关系如图2所示.

为了通过图嵌入直接获得更具表示性的边嵌入向量，本文在无偏采样算法MHRW(Metropolis-Hasting Random Walk)的基础上，设计了一种无偏+有偏的随机游走采样策略，即将当前节点的自环率按邻居节点的度值加权分配给邻居节点[17]，得到新的采样邻居节点的转移概率mij为：

式中：mij表示从节点vi到 其邻居节点集合Γ(i)（包括自身节点）中选取节点vj进行采样的转移概率，ki、kj分 别为节点vi、vj的 度值，rii表示继续采样当前节点时的转移概念，由式(3)中当vi=vj时计算所得.在式(2)的转移概率中，前一部分为无偏采样，保证了游走采样的完整性，后一部分为有偏采样，可消除自环率的不利影响.

Line2Vec主要由两个部分组成：一是无偏+有偏的采样节点生成器，二是基于深度学习的嵌入过程.首先，从图G中随机采样一个节点作为节点序列Wwalk的根节点；然后，找出节点序列中最后一个节点的邻居节点集合，利用式(2)计算出最后一个节点与所有邻居间的转移概率mij；最后，根据转移概率来选取某下一个要采样的邻居节点，以此采样直至节点序列达到最大长度l，同一个根节点采样ζ次.嵌入过程主要利用深度学习框架SkipGram，该过程将生成器中生成的Nζ个长度为l的“句子”，送入SkipGram进行训练，最终得到节点的向量表示.

1.3 基于边嵌入的链路预测算法

输入图数据G(VN，EY)，嵌入维度η，窗口大小ϖ，游走长度l，每个节点的游走次数ζ.

输出节点向量表示的矩阵Φ.

1 初始化：Wwalks∈∅ //walks表示存储的节点序列，∅为游走生成的节点序列，初始为空集.

2foreachvertexvi∈Vdo

3fori=1toζdo

4 使用公式(3)计算每个节点与它的邻居节点间的转移概率mij，其中，vi，vj∈Γ(i).

5Wwalk=Line2VecWalk表示根据概率选取的下一个邻居节点.

6 将Wwalk添 加到Wwalks.

7Wwalks=Shuffle(Wwalks) //将Wwalks打乱.

8 Φ=SkipGram(Wwalks，η，ϖ) //将Wwalks送入到 S kipGram中 得到节点的向量表示Φ.

9 将节点图转换为连边图，获得关联矩阵.

10 将存在边关联矩阵的逆与不存在或未知边关联矩阵相乘，得到不存在或未知边与存在边的关系，结合向量 Φ 得到未知边向量Q.

11 将 Φ和Q按测试集比例为20%进行划分，并使用线性回归中的逻辑回归作为判别分类器进行预测，输出预测结果.

1.4 算法的评价指标本文选择AUC[18]指标评价算法的准确性.AUC是一种比较概率，设随机比较n次 ，其中，有n′次评分高，每高一次加1分，有n′′次评分相等，每等一次加0.5分，则AUC值的定义为：

AUC 值 在 0～1之间，值越大的链路预测方法准确性越高.

节点分类是图嵌入中最常见的下游任务，常用于评价图表示性能优劣的指标，节点分类的评价指标主要有微平均分F1Micro和宏平均分F1Macro[19]，定义如下：

式中：b表 示节点的类别数，TP(True Positive)表示真阳性，TPi为在第i类中预测的正类数，FP(False Positive)表示假阳性，FPi为在第i类中预测的假正类数，FN( False Negative)表示假阴性，FNi为在第i类中预测的假负类数.

2 实验结果与分析

为了验证预测框架的有效性，分别完成了两组实验：首先是图嵌入算法的节点分类实验，比较了Line2Vec与其他嵌入算法在5个数据集下的节点分类效果；其次是边嵌入链路预测实验，将Line2Vec-L方法在6个数据集上与4种边函数构造方法获得的结果进行的链路预测效果对比.

2.1 实 验 数 据实验选取了6个不同规模且具代表性的真实数据集，均为无权无向图.实验数据集包括Jazz、NetScience、Power、Alpha（来源于https://github.com/benedekrozemberczki） 与E-mail[20]、PolBlogs[21].详细信息如表1所示.Jazz、NetScience、E-mail为相对小规模网络，Power、Alpha、PolBlogs为相对大规模网络.表中，N表示网络的节点数，Y表示网络的边数，〈K〉 表 示网络的平均度，〈C〉表示网络的平均聚集系数，D表示网络的相对直径.

表1 实验数据的网络结构特征Tab.1 Network structure features of datasets

2.2 实验基准方法与参数设置将Line2Vec与图嵌入领域具有代表的几类经典方法进行比较，其中谱聚类（Spectral Clustering）、Diff2Vec[22]、BoostNE[23]方法是基于矩阵分解的图嵌入方法，DeepWalk、Node2Vec[24]、Role2Vec[25]是基于Word2Vec模型的图嵌入方法.为了保证实验的公平性，所有方法的嵌入维度 η =128；DeepWalk、Node2Vec、Role2Vec、Diff2Vec、Line2Vec的游走次数 ζ=10，游走长度l=80 ，窗口大小 ϖ=10，此外，BoostNE 的嵌入层数为8，每一层的嵌入维度 ηi=16，组合维度 η =128.

2.3 图 嵌 入 算 法 的 实 验 及 结 果采 用Word2Vec模型在多个真实网络图上进行节点分类的效果评估算法对图的表示性能.实验选取5种不同领域不同规模的真实数据集(http://networkrepository.com)，包括Twitch、Facebook、Wikipedia、Github、Blogcatalog，如表2所示，其中，N表示网络的节点数，Y表示网络的边数，C表示网络的连通数，〈L〉表示网络的标签数.实验在每个数据集上独立重复10次，取平均值.训练数据的划分比例为10%，30%，50%，70%，90%，使用线性回归中的逻辑回归作为判别分类器.基准方法和参数设置见2.2节，结果如表3～7所示.其中，Spectral Clustering、DeepWalk、Node2Vec、Role2Vec、Diff2Vec、BoostNE、Line-2Vec分别简写为SC、DW、N2V、R2V、D2V、BNE、L2V.

表2 数据集的结构特征Tab.2 Structure features of datasets

表3～7中，最佳F1Micro和F1Macro值用粗体显示.可以看出，随着数据集训练比例的增加，所有方法的性能都随之提升.在同一训练比例下，Line2Vec在所有数据集上都比DeepWalk算法性能更佳；与Node2Vec算法相比，绝大多数情况下Line2Vec的评价指标更高，尤其当训练比例仅为10%时，Line2Vec在所有数据集上都获得了比Node2Vec 更好的性能.与带有属性化随机游走的Role2Vec 算法相比，Line2Vec在所有数据集上的评价指数更高，这意味着综合考虑当前节点和邻居节点共同决定的游走方式比属性化随机游走方式的表现力更强，与 Diff2Vec 算法相比，Line2Vec也有相同的优势，在绝大部分情况下，Line2Vec相较于其它6种基准方法，其F1Micro和F1Macro值都更高，说明采用Line2Vec方法表示的节点向量更有效.

表3 Twitch数据集上的节点分类性能比较Tab.3 The comparison of node classification performance on Twitch datasets

表4 Facebook数据集上的节点分类性能比较Tab.4 The comparison of node classification performance on Facebook datasets

表5 Wikipedia数据集上的节点分类性能比较Tab.5 The comparison of node classification performance on Wikipedia datasets

表6 Github数据集上的节点分类性能比较Tab.6 The comparison of node classification performance on Github datasets

表7 Blogcatalog数据集上的节点分类性能比较Tab.7 The comparison of node classification performance on Blogcatalog datasets

与将节点图作为输入的图嵌入算法不同，Line2Vec算法能处理连边图，由此，可先将节点图转换为连边图，在转换过程中同时也得到了相应的关联矩阵，因此增加了空间复杂度.传统谱聚类算法基于数据样本计算矩阵并进行规范化，其时间复杂度为O(N3)，具有代表性的DeepWalk的时间复杂度为Ο(N2)，Line2Vec的时间复杂度也为Ο(N2)，但由于要存储边向量，增加了一倍的空间复杂度.

2.4 链路预测算法的结果与分析表8比较了不同算法在缺失部分边缘时的链路预测性能.其中，Average、Hadamard、Weighted-L1、Weighted-L2为Node2Vec提出的4种边函数[24]，可对生成的节点向量进行数学运算构造出边向量.Line2Vec-L则采用基于Line2Vec的边嵌入算法进行链路预测.Line2Vec既能处理节点图，也能处理连边图，若将连边图作为输入，则不再需要边函数来构造边向量.

在表8中，最佳AUC值用粗体显示，对于通过边函数间接构造得到边向量的图嵌入算法，表现最好的用下划线显示.从表8中可以看出，Line2Vec在5种数据集上AUC值最高；在3个大规模的数据集上，Line2Vec-L获得了最佳的预测性能;此外，采用节点向量作为输入获得边向量的图嵌入算法Line2Vec，在4个数据集上也获得了最佳性能，这说明基于无偏+有偏的综合游走策略的图嵌入算法Line2Vec获得的节点表示效果更好; 同时，在大规模数据集上，采用连边图作为输入与采用节点向量作为输入的方法相比，更有助于性能的提升.

3 结束语

本文针对网络图的表示和构成进行了研究，设计了一种以连边图为研究对象的边嵌入算法Line2Vec，并在此基础上提出了基于Line2Vec的边嵌入链路预测框架Line2Vec-L.首先，基于有偏和无偏思想，设计了一种可以处理连边图的图嵌入算法Line2Vec，该算法在采用随机游走采样策略生成节点序列时，充分调动了被采样的下一个节点在采样过程中的主动性；然后，结合关联矩阵，将生成的边向量用于链路预测.实验结果表明，采用Line2Vec方法得到的节点向量表示性更强，提升了链路预测的性能.下一步，可以综合考虑节点图和连边图，研究双层图或多层图嵌入算法的链路预测.

表8 网络数据集中 4 种边函数与不同基准方法结合的链路预测 AUC 值比较Tab.8 The AUC value of network datasets under four edge-functions to different benchmark methods