使用子图推理实现知识图谱关系预测

于慧琳，陈 炜，王 琪，高建伟，万怀宇

北京交通大学 计算机与信息技术学院，北京100044

知识图谱作为一种结构化的语义表示，可以对现实世界中的实体、概念、属性以及它们之间的关系进行建模。通常知识图谱中的知识并不是完整的，存在实体或者关系缺失等问题，如图1（a）中，实体Charlotte Bronte 与Writer 之间缺失Profession关系。面对知识图谱中的信息缺失问题，需要通过现有的知识推导出潜在的实体或关系，完善知识图谱中的知识，为许多下游任务提供知识支持，例如问答系统、推荐系统、信息检索等。

知识图谱关系推理旨在从现有数据中识别和推断出新的关系。知识图谱关系推理可以分为单步推理和多步推理。单步推理主要是基于表示学习的方法如TransE、TransR等，通过距离打分函数来度量向量化后的实体与关系进而预测实体间的关系。由于实体向量和关系向量缺乏明确含义，基于表示学习的方法存在可解释性较差的问题。为了解决这一问题，研究者们提出了基于路径的多步推理方法，如推理链、PathRNN等，此类方法主要通过神经网络挖掘实体之间的路径关系进行关系推理。近年来，一些研究者将强化学习融入到路径推理中，如Deep-Path、MINERVA等，通过提升关系路径构建的准确性来提高推理效果。虽然基于路径的方法具有更好的可解释性，但它们往往只考虑所选取的单条路径对关系的影响，忽视了多条路径上的实体信息和节点之间的相关性。同时，基于强化学习的路径推理方法在遇到选取路径错误的情况时，还会出现误差累积的问题，产生不理想的推理结果。如图1（a）所示，若只选取路径Charlotte Bronte→HasFather→Patrick Bronte→Profession→Writer，就会推理出关系Charlotte Bronte→Profession→Writer，这意味着使用父亲的职业来直接推测儿子的职业，显然是不合理的。由于单条路径所包含的语义信息不足，常常无法有效地推理出实体间的关系。

针对上述问题，本文考虑多条路径包含的丰富信息，提出了基于子图的关系预测方法SubGLP（subgraph link prediction）。如图1（b）所示，将多条路径构建成子图，使用子图推理预测实体之间的关系，不仅可以解决表示学习的可解释性问题，还能缓解路径推理的误差累积问题，进而完成稳定高效的关系推理。具体而言，本文方法首先基于实体对构建节点子图，获取实体间结构化的实体和关系信息；然后使用高阶图神经网络（-GNNs）更新子图表示，以此来获取子图的高阶特征；最后通过聚合操作将子图表示作为实体之间的关系特征，完成实体间关系的推理。本文的主要贡献总结如下：

图1 知识图谱推理方法转变Fig.1 Transformation of reasoning method of knowledge graph

（1）提出了基于子图推理的知识图谱关系预测方法SubGLP，该方法结合表示学习与路径推理的优势，使用具有丰富信息的子图结构获取实体对的邻域结构信息，实现实体之间的关系预测。

（2）分别从实体层面和关系层面出发，构建节点子图和关系子图，并使用图神经网络来融合节点子图和关系子图的高阶特征信息，从而获得更丰富的实体关系特征。

（3）在两个广泛使用的基准数据集FB15K-237和NELL-995 上分别对SubGLP 模型进行了评估，实验结果表明，SubGLP 模型明显优于现有的单步推理和多步推理的方法，同时验证了模型在大规模知识图谱推理任务上的有效性。

1 相关工作

传统的知识图谱关系推理的方法主要是基于人工制定的规则进行的，如一阶归纳学习方法（first order inductive learner，FOIL），从一个关系表示派生出一组特征的一阶推理方法（kernel first order inductive learner，kFOIL）等。随着深度学习的发展，许多神经网络模型在解决关系推理问题上也取得了很好的效果，它们大致可以被分为单步推理和多步推理。其中，单步推理主要利用表示学习方法中的距离打分函数来预测实体间的关系，多步推理则利用实体间路径作为特征来预测实体间的关系。

早期的基于表示学习的方法是Bordes 等人于2013 年提出的知识表示学习模型TransE，该模型将知识图谱中的实体与关系映射到低维向量空间中，得到实体与关系的向量表示，并使用头尾实体的向量差来表示关系。由于TransE 模型在处理一对多、多对一、多对多复杂关系时具有一定的局限性，一些研究者后来相继提出TransH、TransR和TransD等模型来解决这一问题。基于表示学习的方法虽然具备较强的可扩展性，但实体向量和关系向量都缺乏明确的含义，存在可解释性弱的缺点。多步推理主要是通过挖掘知识图谱中路径的语义信息来进行实体间的关系预测。例如Neelakantan 等利用随机游走的方法来生成路径，并通过递归神经网络（recurrent neural network，RNN）来实现多跳关系推理。但是，这些方法并不能很好地识别实体之间的关键路径信息。

为了提高基于路径推理中路径查找的准确性，研究者们开始尝试将强化学习应用到路径推理中。Xiong 等人提出了一种新的DeepPath 框架，采用强化学习方法进行路径查找，以此来解决多跳推理问题。随后，Das 等人提出了一种优化的强化学习方法MINERVA，使用长短期记忆网络（long short-term memory，LSTM）来学习历史状态的表示。近年来，MARLPaR（multi-agent and reinforcement learning based method for path reasoning）、M-Walk、RLH（reasoning like human）等方法纷纷将不同的强化学习策略应用到路径推理中，取得了效果上的提升。虽然基于路径的推理在一定程度上解决了表示推理存在的问题，但基于路径的方法尤其是结合强化学习的路径推理过分依赖于单一路径，无法综合利用多条路径的丰富信息，对关系特征的捕获并不全面。

为了解决上述基于路径推理中存在的路径选取单一和误差累积等问题，本文将基于路径的推理转化为基于子图的推理，综合考虑多条路径上的节点以及节点之间的关系等更丰富的语义信息，从而更有效地进行实体间的关系推理。

2 基于子图推理的知识图谱关系预测

本章首先对知识图谱关系预测问题进行形式化定义，并介绍相关概念的符号表示，最后详细介绍SubGLP 的整体框架与细节描述。

2.1 基本定义

将知识图谱定义为有向图G=(,)，其中和分别表示图中的节点和边的集合。知识图谱G 由许多三元组(,,)构成，其中、分别表示头、尾实体，表示实体间的关系。知识图谱关系预测的目标就是在给定头实体、实体的条件下，预测出实体间的关系，即解决实体间的关系推理(,?,)问题。

2.2 模型框架

本文提出的模型框架如图2 所示，该框架主要包含以下三部分：

图2 SubGLP 模型框架图Fig.2 Framework of SubGLP

（1）子图抽取模块：基于实体对(,)，使用双向宽度优先搜索（breath first search，BFS）策略，分别构建实体对的节点子图S和边子图S，并使用TransR预训练整个知识图谱得到实体和关系的嵌入表示l、l，然后将子图结构S、S与实体表示l、关系表示l组合得到具有节点向量表示的两个子图()和()。

（2）子图表示模块：将具有向量表示的节点子图() 和边子图() 分别输入高阶图神经网络-GNNs 进行训练，并进行多段池化，得到节点子图和边子图的向量表示L和L，从而捕获子图中的实体和关系结构等多层次信息。

（3）融合预测模块：融合所得到的子图特征，进行非线性激活后计算关系存在的概率(|,)，实现实体间的关系推理。

2.3 子图抽取

首先根据给定的实体对，在知识图谱中查找实体之间连通路径。由于实体之间路径众多，为了提高搜索效率，分别从头、尾实体出发进行双向广度优先搜索，以此来完成实体对路径的查找。为了获取更加丰富和完整的路径信息，本文将反向关系也添加到了知识图谱中，即针对每个三元组(,,)，增加了反向三元组(,,)，并允许在路径中对节点进行多次访问。

假设在实体对(,)间找到了条路径，将第条路径表示为p，即路径p从头实体出发，经过路径→→…到达尾实体：

在路径构建完成后，分别将节点路径和关系路径组合成节点子图S与边子图S：

处理后的S与S包含各自的图结构信息。同时，为了将知识图谱中的实体、关系转化为可训练的向量表示，本文使用TransR对整个知识图谱进行预训练，分别得到实体和关系的向量表示l、l。

2.4 子图表示

图神经网络（graph neural networks，GNN）是一种专门处理图结构信息的神经网络模型，它主要是通过聚合图中节点的邻居节点特征，并结合节点自身特征信息来完成节点更新。用()表示知识图谱中节点的邻居节点集合，以节点子图为例，使用()代表具有预训练表示的节点子图(S,l)。使用GNN更新节点信息的计算公式如下：

通过定义→R以及与有且仅有-1 个公共节点的邻居子图()，以便于-GNNs 在建模时可以获取更多的高阶信息。使用-GNNs 更新子图节点表示方法如下：

更新节点特征后，使用Top-池化进行下采样，来缩小图规模，获取关键特征，再将全局平均池化（global average pooling，GAP）结果与全局最大池化（global max pooling，GMP）结果拼接，求和作为子图特征：

其中，H为下采样后的子图，L为拼接后的节点子图S的表示向量。

使用同样的方法，得到边子图的表示向量L。

2.5 融合预测

将节点子图表示L与边子图表示L输入到双层感知机中，通过非线性变换得到压缩节点子图表示g与边子图表示g，同样以节点子图为例：

为了能够准确表示实体信息与实体之间的关系情况，将节点子图表示g与边子图表示g拼接得到完整子图表示，然后送入Softmax 分类器中计算实体对(,)中关系存在的概率(|,)：

接着，采用交叉熵损失函数优化模型：

其中，表示模型的所有参数，为实体对的标签。(|,,)表示实体对(,)预测关系为的概率。

SubGLP 算法的整体流程如算法1 所示，由于各个模块在上文进行了详细解释，这里进行简要概括。

SubGLP 模型算法

3 实验与结果分析

为了验证SubGLP 模型的有效性，本文在两个基准数据集上分别进行了实验，并与基于表示的方法和基于路径的方法进行了对比分析。

3.1 实验数据集

本文在FB15K-237 数据集与NELL-995 数据集上分别进行测试以验证SubGLP 模型的有效性。其中FB15K-237 是Freebase 的子集，包含237 种关系、14 000 种实体和310 000 组三元组，从中抽取10 种关系进行测试，关系类型包括出生地、国籍、首都、导演、编剧等。NELL-995 是卡内基梅隆大学发布的数据集，包含200 种关系、75 000 种实体和154 000 组三元组，同样从中抽取10 种关系进行测试，关系类型包含出生地、归属地区、雇佣关系等，如表1 所示。

表1 实验数据集Table 1 Experimental datasets

3.2 参数设置与评估指标

对于每个关系推理任务，设置双向BFS 查找路径数=5，预训练后的实体和关系向量的维度=100，划分=128，-GNNs 维度128。在池化部分设置Top-池化比率为0.8，非线性变换维度=256，=128，=64，=2，dropout 比例为0.5，模型学习率=0.000 5。实验采用平均精度均值（mean average precision，MAP）作为评价指标，训练集、测试集划分比例为7∶3。

3.3 基准模型

本文将模型与六种关系推理方法进行比较，其中前两种模型（TransE 和TransR）使用单步推理，即基于表示学习的方法，后四种模型（DeepPath、MINERVA、M-Walk 和RLH）使用多步推理，即基于路径的方法。

TransE：一种经典表示学习模型，它将知识图谱中的实体与关系映射到同一个低维向量空间中，使用头尾实体的向量差来预测关系。

TransR：TransR 与TransE 将实体和关系嵌入在相同空间的方法不同，TransR 分别在实体空间和关系空间构建实体和关系嵌入。

DeepPath：一种用于学习多跳关系路径的强化学习框架，使用强化学习自动探索路径，并设计考虑准确性、多样性和效率的奖励函数，来解决知识图谱中的多跳推理问题。

MINERVA：一种将查询条件引入到强化学习路径搜索中的方法，将推理问题形式化为一个马尔可夫决策过程，使用LSTM 表示观察序列和历史决策序列，解决知识图谱的问答问题。

M-Walk：在DeepPath 的基础上使用蒙特卡洛树（Monte-Carlo tree search，MCTS）策略帮助代理在图中搜索路径，从而尝试在稀疏奖励的环境下提升路径搜索的准确性。

RLH：一个基于分层强化学习的知识图谱推理模型，用于解决知识图谱多跳推理过程的多语义问题。

3.4 对比实验结果与分析

表2 和表3 展示了不同算法的实验结果，从中可以看出，基于强化学习的路径推理方法（DeepPath、MINERVA、M-Walk 和RLH）整体效果要优于基于表示学习的方法（TransE 和TransR）。这表明路径中可以包含更加丰富的语义信息，通过挖掘实体之间的路径信息能有效地提高关系推理的准确性。而本文提出的SubGLP 模型优于基于路径的推理方法，在两个数据集上比效果次好的RLH 模型的MAP 平均值分别高出0.060 与0.017，且比TransE 的MAP 平均值分别高出0.199 与0.190，这也验证了实体间的子图比实体间的单一路径具备更丰富的语义特征，有助于获取实体之间的关系特征，提升关系推理效果。

表2 FB15K-237 数据集上的关系推理（MAP）实验结果Table 2 Link prediction results(MAP)on FB15K-237 datasets

表3 NELL-995 数据集上的关系推理（MAP）实验结果Table 3 Link prediction results(MAP)on NELL-995 datasets

在分析路径与子图的区别时，也注意到由于基于路径的方法使用的信息量较少，当某些关系可以使用单条路经来明确指向时，如NELL-995 数据集上的athletePlaysInLeague 关系使用关系路径athletePlays-ForTeam →teamPlaysInLeague 会产生很好的推理结果，使得基于路径的方法的实验结果也相对较好。

为了分析SubGLP 模型在两个数据集上的效果差异，分别统计了两个数据集上子图的平均节点数与边数，统计结果如图3 所示。可见FB15K-237 数据集中的子图规模更小，NELL-995 数据集的子图则包含了更多节点和边，这解释了模型在NELL-995 数据集上效果更好、更稳定的原因，也说明了内容越丰富的子图对于关系推理具有更加积极的作用。

图3 两种数据集抽取的子图信息比较Fig.3 Subgraph statistics comparison of two datasets

3.5 消融实验

为了进一步验证模型的有效性，通过消融实验来证明各个模块的作用，探究实体与关系对关系预测的不同影响。在实验中，删除了完整模型中的子图拼接模块，分别使用节点子图和边子图来表示预测实体之间的关系。其中，仅使用节点子图的方法称为SubGLP-nod，仅使用边子图的方法称为SubGLPedg，实验结果如表4 所示。从表中可以看出，不论是节点子图还是边子图，都能带来实验效果的提升，其中节点子图在两个数据集上分别比RLH 的MAP 值平均高出0.041 与0.015，边子图在两个数据集上分别比RLH 的MAP 平均值高出0.032 与0.003，这也验证了基于子图的关系推理的优势。

表4 消融实验结果Table 4 Ablation experiment results

此外，从消融实验中还可以看出节点子图的效果比边子图的效果好，且在数据集FB15K-237 上的filmWrittenBy 关系和NELL-995 上的athletePlaysSport与athletePlaysForTeam 关系上，单独的节点子图具有比融合两个子图更好的效果，这说明实体信息对关系推理具有更重要的作用。同样地，从消融实验中还可以看出本文提出的SubGLP 方法与单独使用节点子图或边子图相比，MAP 值均有提升，这也说明模型使用融合两种子图信息的方法可以捕获实体间的更多邻域信息，这对于解决关系推理问题是更有效的。

4 总结

本文将图神经网络与知识图谱推理相结合，提出了基于子图推理的知识图谱关系预测方法SubGLP。为了获取实体间更丰富的信息，采取了先分别构建节点子图和边子图，然后使用图神经网络获取子图高阶语义特征，最后融合两个子图的语义特征来预测实体之间关系的方法。在两个基准数据集上的实验结果验证了本文方法优于现有的基于单步推理与多步推理的关系预测方法。