基于元路径的关系选择图神经网络

吴世康

（1.北京交通大学计算机信息与技术学院，北京100044；2.交通数据分析与挖掘北京市重点实验室，北京100044）

0 引言

现实世界中的许多数据都可以表示成异质图［1］的形式，如学术网络、推荐系统，等等。由于异质图中节点类型与边类型不唯一，其相较同质图具有更丰富的语义信息和异质结构信息，近年来受到学者们的关注。异质图嵌入借鉴了同质图嵌入［2］的思想，将图上节点表示为低维稠密的向量的同时保留图中的异质结构信息和语义信息，以更好地服务于如节点分类［3］、节点聚类［4］等下游任务中。

主流的异质图嵌入模型多依赖元路径［1］，一种定义在异质图上的高阶关系，来捕获图中的异质结构信息和语义信息。早期的异质图嵌入模型通过元路径来指导图上的随机游走过程［5－6］，并与Deepwalk［7］结合生成节点嵌入。然而这些模型只能利用一种元路径下的结构信息，为了更有效地挖掘图中信息，Shang等人［8］通过人为的将多个元路径下生成的节点嵌入融合，Zhang等人［9］提出将多种元路径组合为元图来指导随机游走序列的生成。随后，Wang等人［10］为了使模型能同时考虑节点属性和结构信息，将图神经网络［11］与异质图相结合，利用图注意力网络［12］在各元路径子图上生成节点表示后再融合。Yun等人［13］通过图卷积［14］对模型生成的多个元路径子图聚合节点嵌入。

这些模型虽能对多元路径下的信息加以利用，但它们假设各元路径之间相互独立，并分别为每种元路径生成节点嵌入再融合。这种聚合信息的方式只关注了各元路径内部的局部结构，忽略了元路径之间的全局相关性。假设A、B、C三个作者节点，以及“共同作者”、“同会议下作者”两种元路径关系，A与B互为共同作者，B与C互为同会议下作者，显然A与C之间存在一定的相关性，其研究方向大概率类似。但是仅通过“共同作者”或“同会议下作者”均不能使A与C产生联系。若将三个节点构成多关系图，使不同高阶关系同时建模在一张图中，就能使A与C构成全局上的相关。

基于这样的思路，本文提出可以将异质图转化为基于元路径的多关系图，使节点间多种高阶关系能同时建模。针对生成的多关系图，一种直接的做法是利用关系图卷积［15］来聚合图中各关系下的邻居信息以生成节点嵌入。但是这样的方式忽略了不同关系对于后续任务的重要性。因此本文提出的一种基于元路径的关系选择图神经网络（Metapath-based Relational Selection Graph Neural Network，MRSGNN）。该网络由多个关系选择图卷积层构成，每个关系选择图卷积层在关系图卷积操作的基础上，通过引入关系选择模块，从各关系内部和多关系间对邻居信息进一步筛选，充分考虑元路径间的全局相关性的同时对不同元路径的重要性加以区分。在三个真实异质图数据集上的节点分类任务上，MRSGNN分别取得了94%、92%、61%的预测准确度，均优于现有基准模型。同时在节点聚类任务上，也取得了不错的实验结果。

1 问题定义

定义一（异质图）ɡ表示为异质图或异质信息网络（下文简称“图”），ɡ＝｛V，E，A｝，其中V和E分别表示节点集和边集，A∈R｜V｜×｜V｜为图ɡ对应的邻接矩阵，｜V｜为图中节点数目。图中任意节点v∈V或边e∈E分别能通过映射函数ϕ：V→T与ψ：E→R获得节点与边对应的类型，其中T和R分别为节点类型集与边类型集，且满足｜T｜＋｜R｜＞2。

定义二（异质图嵌入［16］）旨在通过学习一个映射函数F：V→Rd，使图中的节点v能表示为隐空间Rd中的向量并保留节点间邻居关系与节点自身信息，其中d≪｜V｜。

定义三（元路径）m∈M是定义在异质图ɡ上的由多种节点类型T1，T2，…，TL构成的一种高阶关系，M为给定的元路径集合。通常元路径m可以表示为m：T1T2T3…TL＋1。每种元路径分别代表图上的一种高阶关系，如图1（a）这样的学术网络中，元路径APA代表共同作者关系。

图1 异质图与元路径子图

定义四（元路径邻居集和元路径子图［10］）异质图ɡ中的任意节点v可以通过元路径m获取其在该元路径下的邻居集Nm（v）。如图1（a）中所示，将图中所有目标节点和节点在元路径下的邻居构成连边，最终能获得如图1（c）所示的元路径子图ɡm。

2 基于元路径的关系选择图神经网络

本文提出了一种基于元路径的关系选择图神经网络（MRSGNN）来同时捕获元路径自身的局部信息与多元路径间的全局相关性。如图2所示，模型首先将原始异质图转化为基于元路径的多关系图ɡM，随后将多关系图gM与节点特征X＝｛xv，∀v∈V｝共同输入到关系选择图卷积层中，从而直接聚合多关系下的邻居信息。受到Wang等人［17］的启发，第k层关系选择图卷积层中包含nk个相互独立的关系选择图卷积模块以增加模型的拟合能力。MRSGNN通过叠加多层关系选择图卷积层以扩大节点所感知的邻域范围，并利用知识跳跃层自适应的从所有中间层的输出结果中的选择最佳的隐层输出作为最终的节点嵌入。以下将对MRSGNN中的各个组件进行详细介绍。

图2 MRSGNN模型框架

2.1 基于元路径的多关系图转化

给定元路径集合M，模型首先将异质图ɡ＝｛V，E，A｝转化为基于元路径的多关系图ɡM＝｛V，｛ɡm，Am，∀m∈M｝｝（以下简称图ɡM），其中Em和Am分别表示元路径子图ɡm对应的边集合和邻接矩阵，且：

后续关系选择图卷积层将直接在图ɡM上聚合邻居信息从而考虑不同关系间的相关性。

2.2 关系选择图卷积模块

多关系图ɡM（以下简称图ɡM）中的节点v∈V的邻居集可以表示为｛Nm（v），∀m∈M｝，其中Nm（v）表示节点v在高阶关系（元路径）m下的邻居集。图3展示了关系选择图卷积模块生成节点表示的过程。模块首先通过特征转化层将输入的节点表示Hk－1投射到每个关系选择图卷积模块i的特征子空间：

图3 关系选择图卷积模块框架

其中Wk，i∈Ra×d为可学习的参数矩阵，Hk－1∈R｜V｜×d表示上一层输出的节点嵌入，初始值H0＝X，d为模型隐层维度

2.2.1 关系图卷积操作

2.2.2 关系内选择操作

其中〈，〉表示向量内积，tanh（x）＝（ex－e－x）／（ex＋e－x）。

2.2.3 关系间选择操作

其中qk，i∈Rd为注意力向量，da为注意力向量的维度，relu（x）＝max（x，0）。

2.3 关系选择图卷积层

如图4所示，每个关系选择图卷积层将该层对应的nk个关系选择图卷积模块中生成的节点表示˜hk，i按行拼接作为本层的输出Hk∈R｜V｜×d：

图4 关系选择图卷积层框架

其中Hk∈R｜V｜×d为该层第i个关系选择图卷积模块的输出，［·，·］表示向量按行拼接。令用Fk来表示第k个关系选择图卷积层，则每个关系选择图卷积层可以表示为：

2.4 知识跳跃层

为了避免模型性能随图神经网络层数增加而下降，Xu等人［19］提出了知识跳跃层网络，该网络能从所有隐层中自适应找出最佳隐层作为输出。基于这样的思想，知识跳跃层将所有关系选择图卷积层的输出｛Hk，1≤k≤K｝进行聚合，并通过元素级最大池化自适应的选择最佳的隐层输出以作为节点最终表示Z∈R｜V｜×d：

其中K为关系选择图卷积层的最大层数，Fmax表示元素级最大池化。

2.5 预测层

通过知识跳跃层后的节点v的嵌入可以用Zv来表示，在预测层中模型直接使用单层神经网络根据节点表示Zv预测节点的标签类别：

其中W0∈Rd0×d为预测层参数矩阵，d0为节点类别数，S为Softmax激活函数，其计算公式如下：

2.6 模型训练

训练过程中，通过计算节点v的真实标签的独热向量yv与模型预测的节点类别概率分布之间的交叉损失函数，然后利用结合反向传播（Back Propagation）和梯度下降（Gradient Descent）算法来优化模型参数。交叉熵公式如下所示：

其中C为节点类别数，VL表示带有标签的节点集合。最后利用训练好的模型再次输入图结构以及节点特征，并将生成的测试集对应的节点嵌入作为后续节点分类、节点聚类任务的输入。

3 实验结果与分析

3.1 数据集介绍

为了评估MRSGNN模型的有效性，本文在三个真实的异质图数据集进行节点分类与节点聚类实验，其中包括两个引文网络数据集DBLP1https：／／dblp.uni－trier.de／、ACM2http：／／dl.acm.org／和一个电影数据集IMDB3https：／／www.imdb.com／。表1中展示了实验使用的异质数据集的基本统计信息，各数据集的划分遵循文献［10］的设置。DBLP数据集包含论文（P）、作者（A）、会议（C）三种类型节点，本文将作者节点设为目标节点，作者的研究领域作为标签，其关键字的词带表示作为节点特征。ACM数据集包含论文（P）、作者（A）、主题（S）三种类型节点，本文将论文节点为目标节点，论文的研究类型为标签，其关键字的词带表示为节点特征。IMDB包含电影（M）、演员（A）和导演（D）三种类型的节点，本文将电影节点为目标节点，电影的类型作为标签，其情节的词带表示作为节点特征。

表1 数据集统计信息

3.2 对比方法及参数设置

本文将MRSGNN模型与其他基准模型的实验结果进行比较，各模型介绍如下：

Deepwalk［7］是定义在同质图上的嵌入模型，该模型通过随机游走生成节点序列从而学习节点嵌入。

Metapath2vec［5］是定义在异质图上的嵌入模型，该模型通过元路径随机游走生成节点序列从而学习节点嵌入。

HERec［6］是定义在异质图上的嵌入模型，模型通过元路径获得基于元路径的高阶关系图，随后在所获得的图上直接使用Deepwalk模型获得节点嵌入。

GCN［14］是定义在同质图上的图神经网络，通过在谱域上定义了图上的卷积操作，来捕获图中结构信息与节点信息，从而生成节点嵌入。

GAT［12］是定义在同质图上的图神经网络，该模型通过注意力机制对邻居间信息带权聚合的方式来生成节点嵌入。

HAN［10］是定义在异质图上的图神经网络，它通过将多个元路径子图视为互相独立，分别使用GAT来捕获子图内信息，最后利用语义级别注意力机制对多个元路径下获得的节点表示进行融合，是最新的基准模型。

GTN［13］是定义在异质图上的图神经网络，它通过学习不同元路径组合考虑所有潜在基于元路径的高阶关系图，并在所得的图上使用GCN聚合节点信息，是最新的基准模型。

在实验中，对于Deepwalk模型，本文直接将原始异质图作为输入，并忽略节点和边的异质性。对于基于单元路径的异质图嵌入模型（Metapath2vec、HERec）以及同质图图神经网络（GCN、GAT），本文分别对每个候选元路径对应的元路径序列或元路径子图作为模型输入进行测试，最终选出最好的结果进行展示。对于半监督学习模型（如GCN、GAT、HAN、GTN以及本文提出的模型MRSGNN），本文将各个数据集的目标节点按表1中所设大小随机划分为训练集、验证集和测试集。对于基于随机游走的算法，游走序列的窗口大小为5，长度为100，每个节点作为初始节点游走40次，负采样的个数设置为5。GAT、HAN的多头注意力统一设置为8，HAN和MRSGNN中所使用的注意力向量维度为128。本文用“｛n0，…，nK｝”的形式来表示MRSGNN中所使用关系选择图卷积层的层数和每层所包含的关系选择图卷积模块的数目，例如DBLP和ACM数据集中该超参值为｛8，1｝，IMDB为｛2，1｝。为了保证公平性，所有模型生成的节点嵌入的维度均设置为64。模型学习器为Adam，学习率设为0.005，L2正则项的权重为0.001。所有的模型统一训练200轮，并设置早停（early stopping）的容忍系数为40。

节点分类任务的评价指标为micro-F1，其常用来衡量多分类任务下模型精准度，并兼顾了模型的精准率和召回率。节点聚类任务的评价指标为标准化互信息（Normalized Mutual Information，NMI）和调整兰德里系数（Adjusted Rand Index，ARI）。

3.3 节点分类任务

本文在三个数据集上进行了节点分类实验来对比模型的效果，具体实验步骤参照了文献［10］的做法，并使用K－近邻（K-Nearest Neighbor，KNN）作为节点分类实验的分类器。由于基于半监督学习的模型（GCN、GAT、HAN、GTN和MRSGNN）在训练阶段已使用训练集和验证集对模型参数进行更新，因此我们仅使用测试集中的节点作为KNN模型的输入以保持公平性，并测试不同训练率下的节点分类结果。

表2展示的是在相同数据切分规则下的所有模型10次实验结果的平均值。从表2中可以看出，基于图神经网络的模型效果普遍优于传统图嵌入模型，而利用多种元路径的异质图神经网络模型（HAN和GTN）效果普遍优于其他仅使用单一元路径的基准模型，这反映出通过多种元路径能更有效地捕捉图中异质结构信息。GTN在ACM和IMDB数据集上节点分类效果均好于HAN，其潜在原因是该模型将生成的不同元路径子图直接相加的方式能一定程度上考虑不同元路径间的全局相关度。本文所提出的模型MRSGNN在所有数据集上一致取得了最好的实验结果，即便对比最新的基线模型HAN和GTN仍有不少的提升，这说明了MRSGNN通过考虑多种元路径间的全局相关性并对不同关系下邻居信息进行筛选能更有效地捕捉图中的异质结构信息与语义信息。

表2 各数据集上的节点分类任务结果

3.4 节点聚类任务

本文同样参照文献［10］的做法在三个数据集上进行了节点聚类实验，并仅使用测试集中的节点嵌入作为K－均值（K-means）算法的输入，K-means算法的预设集簇数设置为每个数据集对应的节点标签类别数。

由于K-means算法的聚类结果会受到聚类中心初始位置的影响，因此为了增加实验结果的可靠性，我们取10次聚类实验的平均值作为最终结果并展示在表3中。从表3中观察可见，基于元路径的异质图神经网络HAN、GTN效果要优于传统图嵌入模型与同质图神经网络模型，这也进一步证明了结合元路径和图神经网络能更有效捕捉图中的异质结构。MRSGNN在DBLP和ACM数据集上均取得了最好的结果，也侧面反映出模型考虑多种元路径间全局相关性是有必要的。特别指出，IMDB数据集上所有模型的聚类结果表现均不佳，其潜在原因可能是因为该数据集中标签不一定准确：通常一部电影对应多种类别，而实验中仅使用其中一个类别作为节点标签。

表3 各数据集上的节点聚类任务结果

3.5 消融实验

为了验证模型中提出的关系内选择操作和关系间选择操作的有效性，本节分别对模型做了如下变种，2个模型变体分别为：①Intra：将每个关系选择图卷积模块中去掉关系内选择操作；②Inter：将每个关系选择图卷积模块中去掉关系间选择操作，直接将不同关系下的邻居信息相加。我们在DBLP数据集上进行了如3.3与3.4小节的节点分类与节点聚类实验，并使用相同的指标进行评估两种模型变体的效果。消融实验的结果如表4所示。

表4 DBLP数据集上消融实验结果

通过对比可以发现，去掉关系内选择或关系间选择都会使模型性能下降。特别指出，若将关系间选择中注意力模块去掉，直接相加不同关系下的邻居信息，模型的性能明显下降。通过后续观察发现DBLP数据集中对后续任务帮助最大的元路径是APCPA，因此若直接相加两种元路径下的邻居信息则会削弱APCPA元路径在后续任务中的主导地位。这也进一步表明了不同元路径对后续任务的重要性不同，通过关系间选择操作能更有效地考虑不同元路径的重要性，从而更好地融合多关系下的邻居信息。

3.6 超参实验

本小节将对MRSGNN中部分超参进行了敏感性实验，并将实验结果（Micro-F1和NMI）展示在表5中。

表5 DBLP数据集上超参实验结果

首先对模型层数和各层模块数进行测试，结果表明增加模型层数和模块数均使模型效果有一定的提升，其原因在于前者能扩大感知的邻域范围，后者则增加了模型的拟合能力。随后对最终生成嵌入的维度进行测试，随着维度的增加，模型效果先提升后略有下降，其原因是MRSGNN需要合适的维度来建模图中语义信息与结构信息，而过大的维度反而引入额外的冗余。

4 结语

本文针对异质图场景提出了一种基于元路径的关系选择图神经网络（MRSGNN）模型来学习节点嵌入。通过将原始异质图转化为基于元路径的多关系图，模型能在引入多元路径下局部结构信息的同时考虑不同元路径间的全局相关性，并利用所提出关系选择图卷积层在聚合多关系下的邻居信息的同时对其进一步筛选。模型在3个真实数据集的进行实验，实验表明MRSGNN相较其他基线模型一致取得最好的预测效果。