基于邻域采样的异质网络链接预测算法*

刘 臣 谢宁静 周立欣

（上海理工大学管理学院 上海 200093）

1 引言

图作为一种常用的抽象数据结构，包含着丰富的内容信息和复杂的结构信息。现实世界中许多场景都可以用图来表示，如知识图谱［1］、开放学术网络［2］、交通网络［3］等。图卷积网络（Graph Convolution Network，GCN）在学习图表示方面表现优异，已经受到各个领域的广泛关注［4］。然而，随着大数据时代的到来，数据量爆炸式增长，导致图的规模日益扩大。传统图卷积模型在大规模图上很难直接有效训练。因此，如何高效处理大规模图成为一个急需解决的问题。

面对规模日益增长的图数据，采样成为提高模型训练速度，节约计算资源的常用方法。采样方法根据特定规则选择图中的部分节点作为输入样本，从而适当调整输入数据的大小和构成。采样模块通过灵活地构建输入模型中的数据，可以很好地缓解传统图卷积训练的邻域爆炸问题。其中，邻域爆炸是指图卷积计算过程中邻居节点数随着卷积层深度的增加而呈指数增长。同时，采样模块避免图卷积过程一直存储并处理图中每个节点的邻居，保证了信息传播的顺利进行，降低GCN训练的计算和存储成本。

现有采样方法主要用于同质图处理，按照采样对象选择的角度不同，可简单分为基于节点采样、基于分层采样以及基于子图采样三类。Graph-SAGE［5］是一种典型的基于节点采样方法，该方法通过对训练图中每个节点的邻居进行固定数量的采样，学习了一个利用邻域采样和聚合生成节点嵌入的归纳过程，达到了减少计算成本的目的。但该方法估计方式存在着偏差，并且收敛性无法保证。随后，有学者通过添加某些独特采样机制提出了新的节点采样方法。Ying等［6］通过模拟随机行走过程遍历节点，计算访问计数，为每个节点选取最具影响力的邻居。Dai等［7］提出通过添加交替采样策略对单跳邻居进行采样以更新嵌入和函数。VR-GCN［8］则通过方差减少技术将采样邻居的大小限制为任意小的数字，并利用历史激活来近似嵌入，避免了递归计算。这些方法已经取得了不错的效果，但除了SSE［7］方法外，其他方法仍然面临着邻居爆炸问题。

为了减轻节点采样方法中邻居节点数随着层数增长呈指数扩展带来的昂贵计算，有学者提出分层采样方法。分层采样的思想是在一个抽样步骤中对一定数量的节点进行抽样，避免邻居爆炸并降低采样过程的时间开销。基于分层采样的代表性工作之一是FastGCN［9］，其采用蒙特卡洛方法，根据预先设定的概率分布，在每一层独立采样一定数量的节点，避免了对多跳邻居的递归采样。然而该采样方法可能导致采样节点产生的邻接矩阵是稀疏的，无法实现高精度。因此Huang等［10］在FastGCN的基础上做出改进，AS-GCN通过自上而下对每层固定数量的节点进行抽样，保证了较高的准确性。上述采样方法避免了邻域爆炸，提高了模型的训练速度，但当训练图的规模很大时，这些方法在加速训练时并不能优化内存成本。

面对训练过程中的内存成本问题，有学者提出基于子图的采样方法。基于子图的采样方法在形式上是对GCN训练中的每个小批进行一个或多个子图抽样，而不是在完整的图上进行节点采样或边采样。Cluster-GCN［11］使用图聚类算法将原始图划分为多个簇，再随机抽样固定数量的聚类构造子图。但在实际操作簇的大小很难控制。Graph-SAINT［12］通过使用随机游走策略对根节点集中一个节点的邻居进行采样，并利用所选的邻居和根节点集生成子图。J.Bai等提出的Ripple Walk Training［13］考虑图结构数据的随机性和连通性，通过纹波行走采样器采样高质量子图，用于后续模型训练。

目前，上述三类采样方法已经在同质网络中取得了相多的应用。但相较于同质网络，异质网络［14］结构更加复杂。异质网络是一种包括多种节点类型以及多种关系类型的特殊网络。关于异质网络的研究有很多数据挖掘任务，其中链接预测能够有效挖掘网络中的丢失信息，在实际生活中具有重要的使用价值，如好友推荐［15］、电影推荐［16］、知识图谱完善［17］、新陈代谢网络重建［18］等。Schlichtkrull等［19］提出的关系图卷积网络（RGCN）是学习异质网络表示的强大模型，能够有效解决链接预测任务。但当面临真实世界中的大规模网络结构时，关系图卷积模型的使用成本、计算复杂度太高，因此迫切需要引入采样方法以保证大规模图的可扩展性。

本文提出了基于邻域采样的异质网络链接预测小批量训练算法，我们将邻域采样和批处理结合起来，可用于大规模异质网络。算法的主要思想是通过小批量训练的方式，对全图进行采样得到邻域子图。通过每次只构建一个批量的子图进行更新参数，从而减少训练过程的计算开销。简单来说，就是在训练过程中，随机打乱训练图数据，确定固定大小的小批量数据。然后以每个批量数据为中心，对训练图进行采样，得到每个批量对应的邻域子图。最后将子图输入关系图卷积模型中，进行图卷积操作，得到对应的低维节点表征。并且由于DistMult［20］是一个简单有效的因式分解，其在链接预测任务中有着良好表现。因此，在得到节点嵌入后，本文将DistMult模型作为评分函数处理后续异质网络链接预测任务。

本文主要工作如下：

1）本文提出了一种针对大规模异质网络的邻域采样方法。该采样方法能够更好地保留异质网络的结构信息，并且在保持子图的连通性和随机性上具有明显优势。因此，该算法不仅提高了RGCN在大图上的训练速度，还能减少训练过程的计算内存。

2）本文通过小批量训练的方式实现了邻域采样方法。对全图进行采样得到批量邻域子图。RGCN模型在子图内执行小批量随机梯度下降，梯度计算不依赖于子图之外的节点。

3）本文选择多个基线方法，在规模不同的数据集进行链接预测任务的实验，实验结果证明了本文提出的采样方法的有效性。实验表明，大规模图中链接预测准确率提高了30.67%。

2 相关研究

本文提出基于邻域采样的异质网络链接预测小批量训练算法，该算法利用邻域采样获得子图，并利用关系图卷积模型对子图进行编码，捕获异质网络的结构和语义信息。本文将相关研究分为了两类：图卷积网络的训练技术和关系图卷积模型。

1）图卷积网络的训练技术

为了提高图卷积的计算效率以及减少内存成本，一个简单的解决措施是通过子图采样构建浅领域。通过将全局视角转化到局部视角，即整个消息传递的步骤不是在全图上进行的，而是在局部子图上执行的，这样我们能够解决表达和计算的问题。Cluster-GCN［11］是一种基于子图采样的典型方法，该方法通过对全图聚类构造子图，但实际上聚类的大小是很难控制的，而且在大规模图上聚类的空间和时间的开销是不可忽略。于是Zeng等［12］以在大规模上训练GCN模型为动机提出GraphSAINT，该方法在训练过程中构建小批量的随机漫步采样器，模型性能优于先前工作。此外，Zhang等［21］提出的SEAL链接预测框架通过提取k阶封闭子图进行链接预测，并获得了不错的效果，证实了使用局部子图来代替全局网络的可行性。Zeng等［22］分析了深度图神经网络面临着邻居爆炸和过度平滑的缺点，并据此提出打破传统的分层采样思想，使用多种子图采样器，将在全图上进行的图卷积操作转向局部子图。实验证明，这种基于子图的采样方法提高了推理精度和计算效果。因此，我们考虑通过采样，使用局部子图代替全局网络进行训练。

为了提高模型链接预测能力与训练速率，基于以上研究，本文提出一种针对大规模网络的邻域采样方法。该方法结合k阶采样器［22］对异质图进行采样，在保留网络的结构信息的基础上，获取局部子图，后续卷积操作都在小批量子图上进行。

2）关系图卷积模型

目前有多个研究利用图卷积神经网络（GCN）［4］处理图数据，作为GCN模型的扩展，关系图卷积模型（RGCN）［19］在处理多关系图上的优秀表现也受到了各个研究领域的广泛关注。该模型通过计算边缘的方向和分别处理不同关系的消息传递将图卷积扩展到多关系图上。实验结果表明，RGCN作为一个学习多关系图潜在特征的消息传递框架，可以有效应用于多关系数据的建模。然而，尽管RGCN在处理异质网络数据上性能较好，但它仍然面临挑战。对于图卷积操作来说，节点的邻域结构信息影响着该节点的特征表示，在消息传递过程中起着至关重要的作用。在RGCN训练过程中，模型会在整个网络中随机采样边，并在采样的边缘上执行消息传递，生成节点嵌入。在此过程，大规模异质网络的结构信息很容易丢失，而且并不能保证目标节点的邻域结构信息被充分保留，因此，RGCN模型在大规模异质图上并不能得到有效扩展。

基于以上研究，本文将使用关系图卷积模型对采样得到的子图进行编码以获取各节点的特征表示。该部分能够充分考虑异质图中的关系类型，有利于链接预测任务的完成。

3 基于邻域采样的异质网络链接预测算法

3.1 问题描述

其中，Vt表示通过在训练图上进行批量处理确定的种子节点集合。子图G[v]表示以节点v为初始节点对训练图G进行采样得到的子图。G'm表示批量m对应的子图。此基础上我们探究了异质网络链接预测任务。异质网络链接预测研究的是异质网络中的两个节点之间是否存在链接［21］，即判断节点vi和节点vj之间的边(vi,vj)是否存在，以及存在边的关系类型r。

3.2 基于k阶采样器的邻域采样

本节将介绍基于k阶采样器［22］的邻域采样方法，该方法对全图进行采样得到批量邻域子图，将图的规模控制在可计算的范围内。我们将采样方法分成三个步骤：确定种子节点、k阶采样、子图节点重排序。邻域子图的构建过程如图1所示。

图1 邻域子图的构建

3.2.1 确定种子节点

输入异质图G，将图G中的N个三元组随机打乱来构建M个批次，每个批次内固定b条数据。通过计算批次内数据源节点和终节点的并集确定种子节点。由于种子节点集合的结果依赖于分批的随机性，这在一定程度上考虑到数据的多样性，使得不同类型的节点能够被收集，进而减少了网络信息的损失。

3.2.2k阶采样

利用k阶采样器对每个批次中的种子节点进行采样，将相同批次中所有种子节点的k阶邻域子图连接得到采样结果图。其中，k阶采样器的实现方式是从种子节点出发寻找与其自身的最短路径为k跳的节点集合，并从该集合中随机选取b个节点作为采样的结果。在该过程中，采样器能够捕捉到原始输入图一些有意义的全局结构特征。同时，SEAL框架［21］证明了局部网络能够表示全局网络。因此，我们采样得到的子图包含自身和输入原始图的结构信息。使得节点嵌入中蕴含的信息更为丰富。此外，与随机采样的方式不同，本文所使用的采样方法在保证随机性的同时，还考虑了邻域子图的连接性。使得采样结果子图更好地保留了异质网络中的领域结构信息。

3.2.3 子图节点重排序

将每个批次中采样得到的子图分别重新编号得到最终的采样结果图。重新编号能够清除原始输入图中的链接关系，避免模型学习到无关信息。通过这样的方式能够提升计算效率，消除采样结果子图中的冗余信息，提升模型的泛化性能。上述采样方法的总体流程的伪代码如算法1所示。

算法1基于k阶采样器的邻域采样算法

输出：每个批量构建的子图｛G'}={G1'…GM'}，每个批量对应的训练样本

3.3 链接预测任务

本节介绍链接预测总框架。先通过采样模块对异质图进行采样，获得各批量对应的子图，再使用关系图卷积模型编码器对邻域子图进行特征提取，并采用解码器处理下游链接预测任务的过程。具体来说，先利用关系图卷积模型的学习能力和泛化能力对各邻域子图进行编码，学习子图中各节点和关系的低维嵌入，再利用DistMult解码器对这些嵌入进行学习。链接预测整体结构如图2所示。

图2 链接预测框架

3.3.1 邻域子图的特征提取

本文采用Schlichtkrull等［19］提出的关系图卷积（RGCN）的方法在多关系邻域子图上执行消息传递来获得各节点和关系的低维嵌入。该方法是获得异质图表征的一个有效方法，其在基于GCN的聚合邻居的操作之上，对关系维度也进行了一次聚合，从而使得节点的聚合操作成为邻居、关系维度上的双重聚合。其核心公式表达如下：

其中，ci,r是通过预先学习或者选择的特定的标准化常数，一般可选为表示与节点vi具有r关系的邻居集合。为可学习参数，是节点自身对应的权重参数。

如图2所示，RGCN模型的输入是邻域子图。经过两层关系卷积神经计算之后，编码器会生成邻域子图各节点的特征向量，并将其输入解码器中。

3.3.2 预测评分

链接预测通常是指预测一个实体与另一个给定实体之间有特定关系的任务，包括实体排名［23～24］和关系预测［25］。具体来说，实体排名是给定(r,vj)预测实体vi或给定（vi，r）预测实体vj。前者表示为（?,r,vj），后者表示为（vi,r,?）。关系预测是预测两个给定实体之间的关系，表示为（vi,?,vj）。这里我们仅考虑采用异质网络关系预测任务。DistMult评分函数可用于计算关系存在可能性分数值。

预测两个给定节点之间的关系（vi,?,vj）时，对于给定的三元组，模型通过使用以下函数对所有可能的三元组打分来训练：

其中⊙为哈达玛积，evi，evi表示关系r和节点vi的嵌入。表示可能的关系类型嵌入。本文利用交叉熵损失进行优化，使模型的正三元组评分高于负三元组，通过最小化交叉熵损失来得到知识图谱中实体与关系的嵌入，损失函数公式如下：

其中T是该批次内正负三元组的全部集合，l是激活函数，y是一个指示符，当y=1时表示正三元组，y=0时表示负三元组。f(vi,r,vj)包括来自RGCN编码器的实体嵌入和来自DistMult解码器的关系嵌入。

3.4 空间算法复杂度分析

与以往的图卷积操作不同，基于领域采样的异质网络链接预测算法考虑构建一种内存友好的方式。该算法只需要存储邻域子图的节点特征向量矩阵与关系向量矩阵。其空间开销如下：

对于传统的关系图卷积来说，在计算过程中通常依赖于全局网络，其内存开销为

其中|G|v表示整个网络的节点数量，|G|r表示整个网络的关系类型数量，K为RGCN设置层数。

由3.2节算法介绍可知，邻域子图是从大规模网络中采样得到，其规模远小于原网络，领域子图中节点远小于原网络中的节点数，即因此，显然本文提出算法空间开销远小于以往训练方法，即S1＜S2。这使得模型能够在大规模图上高效地进行训练。

4 实验

4.1 实验数据集及评价指标

为了证明提出的邻域采样算法框架的通用性及有效性，本文实验针对三种规模不同的异质网络进行链接预测对比，主要包括知识图谱Freebase中的子集FB15k-237［19］，FB-Toy［26］以及词汇数据库WordNet中的子集WN18［19］。上述数据集的各项指标统计如表1所示。

表1 数据集描述

鉴于WN18数据集中存在一个影响实验结果的缺陷：存在反向三元组对（vi,r,vj）和（vj,r-1,vi），其中（vi,r,vj）存在于训练集，（vj,r-1,vi）存在于测试集。这在很大程度上影响了RGCN模型在异质网络中链接预测任务的准确性。因此我们选择FB15k-237与FB-Toy作为我们的主要评估数据集。

本文主要采用了准确率（Accuracy）评估指标，判断关系类型的预测与标签是否一致，公式如下：

其中，TP代表预测正确的正例样本数，TN表示预测正确的负例样本数，R为总样本数。准确率越高，说明模型链接预测越准确。

4.2 对比模型

为了验证邻域采样算法的有效性，我们将结合邻域采样进行训练的RGCN模型与原始RGCN模型以及其他添加本文提出的邻域采样机制的GCN［4］、GAT［27］、GraphSAGE［5］模型进行比较。

1）RGCN：该模型将图卷积应用到异质网络中，能够处理图中不同的边关系类型对节点嵌入的影响，适用于解决异质网络链接预测以及实体分类问题。

2）RGCN+：添加了本文提出的邻域采样机制的RGCN模型。原始RGCN模型通过随机边采样构建训练图，考虑对高度多关系数据的建模。

3）GCN+：该模型将GCN与本文提出的邻域采样机制相融合。原始GCN是在训练中对整个图进行操作的半监督方法，在学习图表示方面表现优异。

4）GAT+：添加了本文提出的邻域采样机制的GAT模型。原始GAT在传播过程引入自注意力（self-attention）机制，每个节点的隐藏状态通过为其邻居节点分配权重来计算。

5）GraphSAGE+：添加本文提出的邻域采样机制的GraphSAGE模型。GraphSAGE是一个利用节点特征信息为未知节点生成有效嵌入的通用归纳框架。

4.3 实验参数设置

经过多次实验，针对不同数据集，本文模型的超参数设置不同，具体如下。

默认设置RGCN模型层数为两层。设置FB15k-237数据集在RGCN模型隐藏层的大小为256，学习率为0.0001，迭代次数为5；设置WN18数据集在RGCN模型隐藏层的大小为200，学习率为0.0005，迭代次数为25；对于FB-Toy数据集，其模型隐藏层的大小设为200，学习率设为0.0001，迭代次数为30。为了防止过拟合，上述三个数据集都使用了dropout［28］技术，统一设置为0.2，并且都选择ADAM［29］作为优化器。经过多次实验比较，本文邻域采样机制中采样参数k,B选择为k=1,B=7时，模型效果最好。

本文所使用的对比模型的超参数设置如下：对比模型默认层数为两层。原始RGCN模型在不同数据集上超参数设置不同，FB-Toy数据集及WN18数据集的嵌入维度设为200，迭代次数为10000；FB15k-237数据集隐藏层的大小为500，迭代次数为10000；其余参数遵循原始论文设置。GCN+、GAT+、Graph SAGE+模型的超参数设置与本文模型在不同数据集上参数设置相同。

4.4 实验结果与分析

4.4.1 链接预测任务评估指标对比

本文在不同数据集上的实验结果如表2和图3所示，其中表2中加粗的表示最好的结果。根据实验结果，我们总结出如下重要发现。

图3 链接预测准确率对比结果

表2 模型在各数据集的评估指标对比

随着数据集规模的增大，添加了本文提出的邻域采样算法的模型性能基本上都在不断地提升。与小规模数据集FB-Toy对比，RGCN+模型在大规模数据集FB15k-237数据集上性能提升了14.68%。而在GCN+模型上对应的数据为16.73%。此外，由于WN18数据集本身存在缺陷，导致了在RGCN+、GAT+和SAGE+模型上的表现并未与数据规模同步递增。但是，在主要评估数据集FB-Toy以及FB15k-237上，数据规模越大，GAT+和SAGE+表现也越好。与小数据集FB-Toy相比，GAT+、SAGE+模型在大数据集FB15k-237上的链接预测准确率分别提升了7.63%、9.93%。综上所述，本文提出的采样方法有效且在大规模数据集上优势明显。

综合考虑异质图的关系类型有益于提升链接预测的准确性。在不同数据集上，RGCN+模型与基线模型相比，效果基本上都是最优的。在FB-Toy，Wn18，FB15k-237数据集上，RGCN+模型性能与其他基准模型相比平均提升了12.84%，15.69%，23.19%。其中，由于FB-Toy数据集过小，导致RGCN+与RGCN效果差异不大。这也说明了采样方法在大规模数据集中才更加凸显优势。此外，在添加了采样方法的GCN+，GAT+，SAGE+，RGCN+中，由于RGCN+额外考虑了异质图中的关系类型，而其他模型忽略了这一因素，使得它们的表现不如RGCN+。

4.4.2 模型效率分析

我们通过在实验中记录模型训练所需要的时间，证明了本文提出的采样方法能够减少模型训练时间。具体数据如表3所示。结果表明在不同数据集上，添加本文提出的邻域采样算法能够提高模型的训练速度。在三个数据集上，RGCN+模型比RGCN模型运行时间平均减少了32281s。在RGCN上使用邻域采样算法不仅需要较少的内存空间，而且可以加快训练过程的收敛速度。这是因为每个训练阶段涉及的空间和计算复杂度都较小。在每次批处理中，基于邻域采样的异质网络链接预测算法模型在GUP加载的每个子图内执行小批量随机梯度下降。并在算法的后续运行过程中，前向传播和后向传播都在小而完整的邻域子图上进行，而不是对原始图进行处理。综上所述，本文提出的采样方法能够提升模型的运行效率。

表3 训练时间对比（单位：s）

4.4.3 采样参数敏感性分析

为了验证采样过程中邻居数量对模型的影响，本文在三种数据集上对采样参数B进行了敏感性分析。实验结果如图4所示，随着采样邻居数量的递增，在小规模数据集FB-Toy以及规模较大但存在缺陷的WN18数据集上，链接预测准确率整体呈上升趋势，但幅度较小。而在大规模数据集FB15k-237，采样邻居数量越多，模型的性能也更佳，邻居数量到达一定的值后，模型的性能趋于平稳。因此，综合考虑训练时间和模型性能，本文将参数b设为7进行对比实验。

5 结语

本文提出了一种基于邻域子图采样的训练框架，该框架通过小批量训练的方式实现了一种针对大规模异质图的领域采样方法。该方法采样得到的子图很好地保留了异质图的结构信息，而且子图内依然保持着良好的连通性。这样就使得模型能够在大规模图上高效地进行训练。此外，通过在子图内进行小批量的随机梯度下降的方式解决了梯度爆炸的问题。本文通过将采样方法应用于链接预测问题来验证其有效性。在多个真实网络上的实验表明，添加该采样算法的关系图卷积模型与基线相比能够显著提升链接预测的准确率。同时，模型的训练速度也得到了显著的提升。未来的研究方向是将该采样方法与不同的模型结合应用到更多的实际问题中。