0. 摘要

知识图谱（KG）推理旨在从现有事实中推断出新事实。基于关系路径的方法显示出强大的、可解释的和可转移的推理能力。然而，路径在捕获图中的局部证据方面受到了限制。

本文引入了一种新的关系结构，即关系有向图（r-digraph），它由重叠的关系路径组成，以捕获 KG 的局部证据。

由于 rdigraphs 比路径更复杂，因此如何有效地构建并有效地从中学习是具有挑战性的。直接编码 r-digraphs 不能很好地扩展，并且在 r-digraphs 中很难捕获与查询相关的信息。我们提出了一种图神经网络的变体，即 RED-GNN，以应对上述挑战。

具体来说，RED-GNN 利用动态规划对多个具有共享边的 r-digraph 进行递归编码，并利用查询依赖的注意力机制来选择强相关的边。

我们证明了 RED-GNN 不仅高效，而且在归纳和转导推理任务中都可以比现有方法实现显着的性能提升。此外，RED-GNN 中学习到的注意力权重可以为 KG 推理提供可解释的证据。

1. 引言

知识图谱（KG）包含现实世界中的对象、人、概念等之间的交互，在人工智能和人类知识之间带来了很多联系。交互被表示为具有三元形式（主体实体、关系、对象实体）的事实，以指示实体之间的关系。现实世界的 KG 很大且高度不完整，因此推断新事实具有挑战性。 KG 推理模拟了这样一个过程，以从现有事实中推断出新的事实。它在语义搜索、推荐和问答等方面有广泛的应用。在本文中，我们重点学习关系结构从而实现查询（实体、关系, ?)。

在过去的十年中，基于三元组的模型在学习 KG 中的语义信息方面引起了很多关注。这些模型直接使用实体和关系嵌入对三元组进行推理，例如 TransE、ConvE、ComplEx 、RotatE、QuatE、AutoSF 等。由于三元组是独立学习的，它们不能明确地捕获局部证据，即查询三元组周围的局部结构。而这些局部结构可以用作 KG 推理的证据。

路径学习有助于更好地捕获图中的局部证据，因为它们可以保留节点之间的顺序连接。关系路径通过尝试捕获语义和本地证据进行推理。DeepPath、MINERVA 和 M-walk 使用强化学习 (RL) 来采样与查询具有强相关性的关系路径。由于 KG 的稀疏特性，RL 方法很难在大规模 KG 上训练。PathCon 对实体之间的所有关系路径进行采样，并使用注意力机制对不同路径进行加权，但对于实体查询任务而言代价高昂。基于规则的方法，如 RuleN、Neural LP 、DRUM 和 RNNLogic，将关系路径概括为逻辑规则，它们学习通过关系的逻辑组合来推断关系，并且可以提供可解释的见解。此外，逻辑规则可以处理推理中存在看不见的实体的归纳推理，这在现实世界的应用中很常见。

在捕获本地证据方面，子图自然比路径更能提供信息。它们的有效性已经在例如基于图的推荐和节点表示学习中得到了经验验证。随着图神经网络 (GNN) 在图结构数据建模中的成功，引入了 GNN 来捕获 KG 中的子图结构。 R-GCN、CompGCN 和 KE-GCN 提出通过聚合每一层中的所有邻居来更新实体的表示。但是，它们无法区分和解释不同邻居的结构作用。DPMPN 通过修剪给定查询的不相关实体而不是学习特定的局部结构来学习减小子图的大小以在大规模 KG 上进行推理。p-GAT 联合学习图注意网络和马尔可夫逻辑网络，以弥合嵌入和规则之间的差距。但是，必须预先定义一组规则，并且应该使用昂贵的 EM 算法进行优化。最近，GraIL 提出从局部封闭子图预测关系，并体现了子图的归纳能力。然而，由于封闭子图的限制，它同时存在有效性和效率问题。

受基于路径的方法的可解释和可转移能力以及子图的结构保持特性的启发，本文在 KG 中引入了一种新的关系结构，称为 r-digraph，以综合路径推理和图推理模型方法的优势。 r-digraphs 通过保留重叠的关系路径和关系结构来将关系路径推广到子图。与具有简单结构的关系路径不同，如何有效地构建和学习 r-digraph 具有挑战性，因为构建过程很昂贵。受使用动态规划在重叠子问题中节省计算成本的启发，本文提出了 RED-GNN，这是 GNN 的一种变体，用于递归编码具有共享边的多个关系有向图（r-digraphs）并通过查询选择强相关边依赖的注意力权重。从经验上看，RED-GNN 在归纳和转导基准测试中都比最先进的推理方法有显着的进步。此外，模型的优势包括训练和推理过程高效，模型参数数量少，学习结构可解释。

2. 相关工作

文章介绍了利用知识图谱中的结构进行推理的基于路径的方法和基于 GNN 的方法。

2.1 基于路径的方法

关系路径是一组按顺序连接的三元组。基于路径的方法学习通过一组关系路径作为局部证据来预测三元组（𝑒𝑞，𝑟𝑞，𝑒𝑎）。 DeepPath 通过强化学习 (RL) 学习生成从𝑒𝑞 到𝑒𝑎 的关系路径。为了提高效率，MINERVA 和 M-walk 学习通过 RL 从𝑒𝑞 开始生成多条路径。分数由不同𝑒𝑎上的到达频率表示。由于 KG 的复杂结构，奖励非常稀疏，难以训练 RL 模型。 PathCon 对连接两个实体的所有路径进行采样以预测它们之间的关系，然而，这对于推理任务（𝑒𝑞，𝑟𝑞，𝑒𝑎）来说是昂贵的。

基于规则的方法不是直接使用路径，而是将逻辑规则学习为关系路径的一般形式。逻辑规则由一组关系组成，以推断特定关系。这可以提供更好的解释，并且可以被转移到看不见的实体。这些规则是通过像 RuleN 这样的挖掘方法、像 RNNLogic 这样的 EM 算法或像 Neural LP 和 DRUM 这样的端到端训练来学习的，以在 𝑒𝑞 和 𝑒𝑎 之间生成高度相关的关系路径。这些规则可以提供逻辑解释并转移到看不见的实体。然而，规则只捕获顺序证据，因此无法学习更复杂的模式，例如子图结构。

2.2 基于GNN的方法

子图可以保存比关系路径更丰富的信息，因为子图中允许的度数更多。 GNN 在对图形结构化数据进行建模方面显示出强大的能力。这激发了最近的工作，例如 R-GCN、CompGCN 和 KE-GCN，在 KG 上扩展 GNN 以在消息传递框架下聚合实体和关系的表示为

它在维度为 𝑑 的实体 𝑒𝑜 的单跳相邻边 (𝑒𝑠,𝑟,𝑒𝑜) ∈ F 上聚合消息 𝜙(·,·)。 𝑾 ℓ ∈ R𝑑×𝑑 是权重矩阵，𝛿 是激活函数，𝒉ℓ𝑟 是第ℓ层的关系表示。在 𝐿 层的聚合之后，表示 𝒉𝐿𝑒 捕获实体的局部结构 𝑒 ∈V 与解码器评分函数共同工作以测量三元组。由于消息传递函数聚合了所有邻居的信息并且与查询无关，因此 R-GCN 和 CompGCN 无法捕获特定查询的显式本地证据并且不可解释。

DPMPN 没有使用所有邻域，而是设计了一个 GNN 来聚合实体的嵌入，并设计另一个 GNN 来动态扩展和修剪查询实体 𝑒𝑞 的推理子图。对采样实体应用查询相关注意力以进行修剪。这种方法通过剪枝子图上的注意力流显示可解释的推理过程，但仍然需要嵌入来指导剪枝，因此不能推广到看不见的实体。此外，它无法捕获支持给定查询三元组的显式本地证据。

p-GAT 和 pLogicNet 通过变分 EM 算法联合学习基于嵌入的模型和马尔可夫逻辑网络 (MLN)。嵌入模型生成证据供 MLN 更新，MLN 将训练数据用于嵌入模型进行训练。 MLN 带来了嵌入模型和逻辑规则之间的差距，但它需要一组预定义的初始化规则，并且变分 EM 算法的训练成本很高。

最近，GraIL 提出在查询实体 𝑒𝑞 和答案实体 𝑒𝑎 之间提取封闭子图 G(𝑒𝑞,𝑒𝑎)。为了学习封闭子图，将具有查询依赖注意力的关系 GNN 应用于 G (𝑒𝑞,𝑒𝑎) 中的边缘，以控制边缘对不同查询的重要性，但学习到的注意力权重不可解释。在 𝐿 层聚合之后，图级表示聚合子图中的所有实体 𝑒 ∈ V，并用于对三元组（𝑒𝑞，𝑟𝑞，𝑒𝑎）进行评分。由于需要显式提取子图并针对不同的三元组进行评分，因此计算成本非常高。

3. 关系 Digraph

关系路径在 KG 上显示出强大的可转移和可解释推理能力。但是，由于路径中的节点仅按顺序连接，因此它们在捕获 KG 中更复杂的依赖关系方面受到限制。基于 GNN 的方法可以学习不同的子图结构。但是现有的方法都不能有效地学习既可解释又可归纳的子图结构。因此，我们有动力定义一种新的结构，探索重要的本地证据。

分层 st 图：分层 st 图是一个有向图，只有一个源节点 (s) 和一个汇节点 (t)。所有边都是有向的，连接连续层之间的节点并从 𝑙 层指向 𝑙+1层。

在这里采用一般方法来增加具有反向和同一关系的三元组。那么，所有在 𝑒𝑞 和 𝑒𝑎 之间长度小于或等于 𝐿 的关系路径都可以表示为长度为𝐿的关系路径𝑒𝑞→𝑟1·→𝑟2···→𝑟𝐿𝑒𝑎。

通过这种方式，它们可以形成分层 st 图中的路径，同时具有单个源实体 𝑒𝑞 和汇实体 𝑒𝑎。这种结构保留了𝑒𝑞 和 𝑒𝑎 之间的所有关系路径，长度为 𝐿，并能够维护子图结构。基于这一观察，我们在定义中定义了 r-digraph（关系有向图）。

r-digraph G𝑒𝑞,𝑒𝑎 |𝐿 是一个分层的 st-图，具有源实体 𝑒𝑞 和汇实体 𝑒𝑎。同一层中的实体彼此不同。 r-digraph 向图中从 𝑒𝑞 到 𝑒𝑎 的任何路径都是关系路径𝑒𝑞→𝑟1·→𝑟2···→𝑟𝐿𝑒𝑎，长度为 𝐿，其中 𝑟ℓ 将 ℓ−1 层中的实体连接到 ℓ 实体层。我们定义 G𝑒𝑞,𝑒𝑎 |𝐿 =∅，如果不存在连接 𝑒𝑞 和 𝑒𝑎 且长度为𝐿的关系路径。

• 图：关系有向图 r-digraph 的一个例子。

在论文中，Eℓ𝑒𝑞,𝑒𝑎|𝐿 是边，Vℓ𝑒𝑞,𝑒𝑎|𝐿={𝑒𝑜|(𝑒𝑠,𝑟,𝑒𝑜)∈Eℓ𝑒𝑞,𝑒𝑎|𝓐th 是 𝐿 层的实体。G𝑒𝑞,𝑒𝑎 |𝐿 =E1 𝑒𝑞,𝑒𝑎 |𝐿 ⊗···⊗E𝐿𝑒𝑞,𝑒𝑎 |𝐿 ，⊗表示逐层连接，同时并运算定义为 G𝑒𝑞1，𝑒𝑎1|𝐿∪g𝑒𝑞2，χ2|𝐿=（e1𝑒𝑞1，𝑒𝑎1|𝐿∪e1𝑒𝑞2，𝑒𝑎2|𝐿）⊗··⊗（e𝐿𝑒𝑞1，𝑒𝑎1|𝐿∪e𝐿𝑒𝑞2，𝑒𝑎2|𝐿 ）。

给定一个实体𝑒，将 ^Eℓ𝑒、ˇEℓ𝑒 和 Vℓ𝑒 分别表示为出边、入边和实体的集合，在从 𝑒 出发的第 ℓ 步中可见。

4. 方法

在这里，我们展示了如何定制 GNN 以高效和有效地从 r-digraphs 中学习。提取子图结构然后学习子图表示是文献中子图编码的常见做法，例如 GraphSage 和 GraIL。给定一个查询三元组（𝑒𝑞，𝑟𝑞，𝑒𝑎），子图编码通常包含三个过程：（i）提取 𝑒𝑞 和 𝑒𝑎 的邻域；（ii）取交点构造子图；（iii）运行消息传递并使用图表示作为子图编码。

在处理 r-digraph G𝑒𝑞,𝑒𝑎 |𝐿 时，可以在算法中自定义相同的方法。首先，获得 𝑒𝑞 和 𝑒𝑎 的邻域。其次，从 𝑒𝑞 和 𝑒𝑎 获取邻域的交集，以逐层诱导 r-digraph G𝑒𝑞,𝑒𝑎 |𝐿。第三，如果 r-digraph 为空，表示设置为 0。否则，逐层进行消息传递，实现递归编码。由于 𝑒𝑎 是单汇实体，最后一层表示 𝒉𝐿𝑒𝑎(𝑒𝑞,𝑟𝑞) 被用作子图表示来编码 r 向图 G𝑒𝑞,𝑒𝑎|𝐿。我们将这个简单的解决方案命名为 RED-Simp。

但是，算法复杂度很高。首先，我们需要进行两次定向采样，并取交点来提取 r-digraph。其次，给定一个查询 (𝑒𝑞,𝑟𝑞,?)，我们需要对 |V| 所有不同实体的不同三元组 𝑒𝑎 ∈V 执行此算法。它需要 𝑂(|V|·(min( 𝐷𝐿, |F|𝐿)+𝑑 ̄𝐸𝐿)) 时间来预测给定的查询（𝑒𝑞,𝑟𝑞,?），其中 𝐷 是实体的平均值，𝐸 是关系的平均值。PathCon 和 GraIL 中也存在这些限制。为了提高效率，本文建议递归地编码多个 r-digraph。

• 图：逐层消息传递的递归编码过程。

• 算法一

4.1 递归 r-digraph 编码

这部分主要介绍如何通过初始节点和共享边，实现目标节点和图的递归编码，同时实现和 RED-SIMP 相同的图结构。

在算法 1 中，当使用不同的 𝑒𝑎 ∈V 但相同的查询 (𝑒𝑞,𝑟𝑞,?) 评估 (𝑒𝑞,𝑟𝑞,𝑒𝑎) 时，相邻边 ^Eℓ𝑒𝑞,ℓ =1...𝐿 的 𝑒𝑞 是共享的。观察到：从 𝑒𝑞 通过 ℓ-steps 可见的边集 ^Eℓ𝑒𝑞 等于∪𝑒𝑎∈VEℓ𝑒𝑞,𝑒𝑎|𝐿，即 ^Eℓ𝑒𝑞 （是 r-digraph 中第 ℓ 层边）是所有实体 𝑒𝑞 和 𝑒𝑎 之间的并集 。这表明第 ℓ 层不同的答案实体 𝑒𝑎 共享同一组边 Eℓ𝑒𝑞,𝑒𝑎 |𝐿。在重叠子问题中节省计算成本的常用方法是动态规划。这已被用于在大规模图上聚合节点表示或在 KG 上传播问题表示。受动态规划所获得的效率的启发，我们递归地构造 𝑒𝑞 和任何实体 𝑒𝑜 之间的有向图为

一旦第 ℓ−1 层中所有实体 𝑒𝑠 ∈Vℓ−1𝑒𝑞 的 G𝑒𝑞,𝑒𝑠 |ℓ−1 表示准备就绪，我们就可以通过第ℓ层的共享边 (𝑒𝑠,𝑟,𝑒𝑜)∈^Eℓ𝑒𝑞 实现图编码 G𝑒𝑞,𝑒𝑜 |ℓ。通过上述方法，可以采用动态规划的方式进行递归编码，并在 ^Eℓ𝑒𝑞 中逐层计算共享边。

最初，只有 𝑒𝑞 在 V0𝑒𝑞 中可见。在第 ℓ 层，收集边 Eℓ𝑒𝑞 和实体 Vℓ𝑒𝑞。然后通过限制 Eℓ𝑒𝑞 边的消息传递，获得 𝑒𝑜 ∈Vℓ𝑒𝑞 的表示。最后，获取答案实体表示 𝒉𝐿𝑒𝑎(𝑒𝑞,𝑟𝑞)，为所有实体𝑒𝑎 ∈ V 进行图编码 G𝑒𝑞,𝑒𝑎 |𝐿 ，并返回。使用Eℓ𝑒𝑞 中的共享边和更少的循环，递归编码可以更有效，并且获得的 RED-SIMP 的图结构是一样的。

• 算法二。

4.2 r-digraph 的可解释推理

由于 G𝑒𝑞，𝑒𝑎|𝐿 的构造与查询关系 𝑟𝑞 无关，如何编码 𝑟𝑞 是另一个需要解决的问题。给定不同的三元组共享相同的 r-digraph，例如（Sam，starred，Spider-2）和（Sam，directed，Spider-2），我们用于推理的本地证据是不同的。为了从 r-digraph 中捕获与查询相关的知识并发现可解释的局部证据，我们使用注意力机制并将 𝑟𝑞 编码到注意权重中，以控制 G𝑒𝑞、𝑒𝑎 |𝐿 中不同边缘的重要性。消息传递函数指定为

其中边缘（𝑒𝑠，𝑟，𝑒𝑜）的注意力权重 𝛼ℓ𝑒𝑠，𝑟，𝑒𝑜|𝑟𝑞 是

⊕ 是连接运算符。使用 Sigmoid 函数 𝜎 而不是 softmax attention 来确保可以在同一邻域中选择多个边缘。

在 𝐿 层聚合之后，表示向量 𝒉𝐿𝑒𝑎（𝑒𝑞，𝑟𝑞）可以编码用于评分的基本信息（𝑒𝑞，𝑟𝑞，𝑒𝑎）。因此，我们设计了一个简单的评分函数

将多类对数损失与每个训练三元组（𝑒𝑞，𝑟𝑞，𝑒𝑎）相关联，第一部分是训练查询集 Ttra 中正三元组（𝑒𝑞，𝑟𝑞，𝑒𝑎）的得分，第二部分包含具有相同查询的所有三元组的得分（𝑒𝑞，𝑟𝑞，? ）

模型参数 𝚯={{𝑾 ℓ}, {𝒘ℓ𝛼}, {𝑾 ℓ𝛼}, {𝒉ℓ𝑟 }, 𝒘 } 随机初始化并通过使用随机梯度下降最小化来优化。提供定理来表明，如果一组关系路径与查询三元组强相关，则它们可以通过 RED-GNN 中的注意力权重来识别，因此是可解释的。

定理 1. 给定一个三元组 (𝑒𝑞,𝑟𝑞,𝑒𝑎)，令 P 是一组关系路径 𝑒𝑞 →𝑟1 𝑖 ·→𝑟2 𝑖 ···→𝑟𝐿𝑖 𝑒𝑎，由 𝑒𝑞 和 𝑎 之间的一组规则生成：

其中𝑋，𝑌，𝑍1，. . .,𝑍𝐿−1 是由唯一实体限定的变量。将GP表示为由P构造的 r-digraph。对于 RED-GNN，存在一个参数设置 𝚯 和一个阈值 𝜃 ∈ (0,1)，GP 可以等于 r-digraph，其边缘具有注意权重 𝛼ℓ𝑒𝑠，𝑟，𝑒𝑜 |𝑟𝑞 >𝜃。

4.3 推理复杂度

在这一部分中，我们比较了不同基于 GNN 的方法的推理复杂度。在对查询（𝑒𝑞，𝑟𝑞，？）进行推理时，我们需要使用不同的答案实体𝑒 ∈ V 评估 |V|三元组。我们假设平均度数为 𝐷，r-digraph 每一层的平均边数为 𝐸，则有

相比之下，就推理复杂度而言，有 RED-GNN ≈CompGCN <DPMPN < RED-Simp <GraIL。第 5.3 节提供了实证评估。

5. 实验

5.1 归纳推理

归纳推理是一个热门的研究课题，因为在现实世界的应用中出现了新的实体，例如新用户、新项目和新概念。能够对看不见的实体进行推理需要模型捕获语义和本地证据，而忽略实体的身份。

设置：我们遵循一般归纳设置，其中测试中有新实体，并且关系与训练中的相同。具体来说，训练和测试包含两个 KGs Ktra ={Vtra,R, Ftra } 和 Ktst ={Vtst,R, Ftst }，具有相同的关系集但实体集不相交。提供了增加反向关系的 Ttra/Tval/Ttst。 Ftra 分别用于预测 Ttra 和 Tval 以进行训练和验证。在测试中，Ftst 用于预测 Ttst。使用过滤后的排名指标，即平均倒数排名 (MRR)、Hit@1 和 Hit@10。

基线：由于训练和测试包含不相交的实体集，所有需要实体嵌入的方法都不能在这里应用。我们主要比较四种方法：1）RuleN，离散规则归纳法； 2）Neural-LP，第一个可微分的规则学习方法； 3) DRUM，Neural-LP 的改进工作； 4）GraIL，它设计了用于归纳推理的封闭子图。 MINERVA、PathCon 和 RNNLogic 可以在此设置上工作，但缺少用于归纳设置的自定义源代码，因此无法比较。

Tie Policy：在评估中，Tie Policy 很重要。具体来说，当存在具有相同等级的三元组时，选择平局中的最大等级和最小等级将导致相当不同的结果。考虑到对于 G𝑒𝑞,𝑒𝑎 |𝐿 =∅ 的三元组，我们给出相同的分数 0，因此会担心平局策略。因此，我们按照建议 [31] 使用平局中三元组的平均排名。

数据集：我们使用基准数据集，在 WN18RR、FB15k237 和 NELL-995 上创建。每个数据集包括四个版本，具有不同的三元组。

结果：性能如表 1 所示。首先，GraIL 是所有方法中最差的，因为封闭的子图不能很好地学习可以推广到看不见的实体的关系结构。其次，基于规则的方法中没有绝对的赢家，因为不同的规则对这些数据集的适应不同。相比之下，RED-GNN 在所有基准测试中都优于基线。注意力权重可以帮助自适应地学习不同数据集的相关关系路径，同时保留结构模式。在某些情况下，RED-GNN 的 Hit@10 比基于规则的方法略差，因为它可能会过度拟合到排名靠前的样本。

• 表1：归纳推理。最佳性能由粗体数字表示。

5.2 转导推理

转导推理（其实就是观察特定训练样本，预测特定测试样本的方法），也称为 KG 补全，是另一种通用设置。它评估模型在不完整 KG 上学习模式的能力。

设置：在此设置中，给出了 KG K ={V,R,F} 和查询三元组 T𝑣𝑎𝑙/Ttst，并增加了反向关系。对于基于三元组的方法，F 中的三元组用于训练，T𝑣𝑎𝑙/Ttst 用于推理。对于其他，F 中的 3/4 三元组用于提取路径/子图以预测训练中剩余的 1/4 三元组，然后使用完整集 F 来预测推理中的 T𝑣𝑎𝑙/Ttst。使用相同的过滤排名指标和相同的平局策略，即 MRR、Hit@1 和 Hit@10。

基线：将 RED-GNN 与基于三元组的方法 ConvE、RotatE和 QuatE 进行比较；基于路径的方法 MINERVA、Neural LP、DRUM 和 RNNLogic；基于 MLN 的方法 pLogicNet 和基于 GNN 的方法 CompGCN 和 DPMPN。 RuleN 在这里没有进行比较，因为它已被证明在此设置中比 DRUM 和 RNNLogic 更差。 p-GAT 没有进行比较，因为它们的结果是在有问题的框架上评估的。 GraIL 没有进行比较，因为在大规模知识图谱上计算困难。

• 表3：转导推理数据集信息。

结果。如表 2 所示，基于三元组的方法在 Family 和 UMLS 上优于基于路径的方法，并且在 WN18RR、FB15k-237 上与 DRUM 和 RNNLogic 相当。实体嵌入可以隐式地保留实体周围的局部信息，而基于路径的方法可能会丢失结构模式。 CompGCN 的表现与基于三元组的方法相似，因为它主要依赖于聚合嵌入和解码器评分函数。由于使用了完整的邻接矩阵，神经 LP、DRUM 和 CompGCN 在具有 74 个实体的 NELL-995 上耗尽了内存。对于 DPMPN，剪枝子图中的实体比 CompGCN 中的实体信息量更大，因此具有更好的性能。对于 RED-GNN，它优于 MRR 指标指示的所有基线。这些证明了 r-digraph 不仅可以很好地转移到看不见的实体，还可以在不使用实体嵌入的情况下捕获不完整 KG 中的重要模式。

• 表2：转导推理结果。最佳性能由粗体数字表示。 “-”表示无法获得结果，带有“*”的方法的结果是从原始论文中复制的。

5.3 复杂度分析

我们在这部分比较了不同方法在运行时间和参数大小方面的复杂性。我们在图 2(a) 中显示了每种方法在 Ttst 上的训练时间和推理时间，在图 2(b) 中显示了学习曲线，在图 2(c) 中显示了模型参数。

归纳推理：在 WN18RR (V1)、FB15k-237 (V1) 和 NELL-995 (V1) 上比较 RuleN、Neural LP、DRUM、GraIL 和 RED-GNN。RuleN 中的训练和推理都非常有效。NeuralLP 和 DRUM 的成本相似，但通过使用完整的邻接矩阵比 RED-GNN 更昂贵。对于 GraIL，训练和推理都非常昂贵，因为它们需要双向采样来提取子图，然后计算每个三元组。至于模型参数，RED-GNN 和 GraIL 的参数数量相似，少于 Neural-LP 和 DRUM。总体而言，RED-GNN 比可微分方法 Neural LP、DRUM 和 GraIL 更有效。

转导推理：在 Family、WN18RR 和 NELL-995 上比较了 RotatE、MINERVA、CompGCN、DPMPN 和 RED-GNN。由于三元组的训练框架简单，RotatE 是最快的方法。 MINERVA 比基于 GNN 的方法更有效，因为采样的路径可以按顺序有效地建模。层数较少的 CompGCN 与 RED-GNN 的成本相似，因为它的计算是在整个图上进行的。对于 DPMPN，剪枝成本很高，并且它有两个 GNN 一起工作，因此它比 RED-GNN 更昂贵。 GraIL 比 RED-GNN 贵数百倍，因此在这种情况下在较大的 KG 上难以处理。由于 RED-GNN 不学习实体嵌入，因此与其他四种方法相比，它的参数要少得多。

• 图2：运行时间、学习曲线和模型参数。

5.4 案例研究——学习 r-digraphs

通过 RED-GNN 在 Family 和 UMLS 数据集上使用 𝐿=3 可视化一些示例学习的 r-digraphs。给定三元组 (𝑒𝑞,𝑟𝑞,𝑒𝑎)，我们删除 G𝑒𝑞,𝑒𝑎 |𝐿 中注意力权重小于 0.5 的边缘，并提取剩余部分。图 3(a) 显示了 DRUM 失败的一个三元组。如图所示，将 id-1482 推断为 id-1480 的儿子需要从本地结构中知道 id-1480 是叔叔 id-1432 的唯一兄弟。图 3(b) 显示了具有相同 𝑒𝑞 和 𝑒𝑎 共享相同有向图 G𝑒𝑞,𝑒𝑎 |𝐿 的示例。如图所示，RED-GNN 可以为不同的查询关系学习不同的结构，这符合定理 1。图 3 中的示例表明 RED-GNN 是可解释的。

• 图3：学习结构的可视化。虚线表示反向关系。查询三元组由红色矩形表示。由于空间限制，UMLS 数据集中的实体显示为黑色圆圈。

5.5 消融研究

注意力：研究了移除 𝑟𝑞 对注意力的影响（表示为 Attn-w.o.-𝑟𝑞）。具体而言，我们从注意力αℓ𝑒𝑠，𝑟，𝑒𝑜|在（4）中除去 𝒉ℓ𝑟𝑞，并将评分功能改为𝒘𝒘（𝒉𝐿𝑒𝑎（𝑒𝑞，𝑟𝑞）⊕𝒉𝑟𝑞），用 𝒘r2𝑑。由于注意力 𝛼ℓ𝑒𝑠,𝑟,𝑒𝑜 |𝑟𝑞 旨在找出 G𝑒𝑞,𝑒𝑎 |𝐿 中的重要边，因此如果不控制查询关系𝑟𝑞，学习到的结构信息量就会减少，因此性能较差。

效率：RED-Simp 由于效率问题，不能使用需要计算许多负三元组的分数的损失函数。因此，我们在 GraIL 中使用带有一个负样本的边际排名损失。如表 4 所示，RED-Simp 的性能弱于 RED-GNN，因为多类对数损失优于负采样损失函数。 RED-Simp 在表 1 中仍然优于 GraIL，因为 rdigraph 是更好的推理结构。运行时间RED-Simp 在图 2(a) 和 2(b) 中。算法 1 比算法 2 贵得多，但比 GraIL 便宜，因为 GraIL 需要 Dijkstra 算法来标记实体。

模型的深度：在图 4 中，我们在左侧 𝑦 轴显示了使用不同层或步骤 𝐿 测试 MRR 的影响。测试三元组 (𝑒𝑞,𝑟𝑞,𝑒𝑎) 的覆盖率 (%)，其中 𝑒𝑎 在 𝐿 步骤中从𝑒𝑞 可见，即𝑒𝑎 ∈V𝐿𝑒𝑞，显示在右侧 𝑦 轴中。直观地说，当 𝐿 增加时，会覆盖更多的三元组，𝑒𝑞 和𝑒𝑎 之间的路径或子图会包含更丰富的信息，但会更难学习。如图所示，当 𝐿 ≥ 4 时，DRUM、Neural LP 和 MINERVA 的性能下降。当 𝐿 >3 时，CompGCN 内存不足，并且在 𝐿=3 时也难以捕获复杂结构。当 𝐿 太小，例如 𝐿 ≤ 2 时，RED-GNN 的性能很差，主要是由于在如此小的 r-digraph 中编码的信息有限。 RED-GNN 在 𝐿 ≥ 3 时实现了最佳性能，其中 r-digraph 可以包含更丰富的信息，并且可以通过 (3) 有效地学习用于推理的重要信息。由于计算成本随着 𝐿 显着增加，我们调整 𝐿 ∈ {3,4,5} 以平衡实践中的效率和有效性。

距离表现：请注意，给定具有 𝐿 层的 r-digraph，算法 2 无法传播通过 𝐿 跃点无法到达的两个节点之间的信息。这可能会引起对 RED-GNN 预测能力的担忧，尤其是对于在𝐿 步骤。我们在这里证明这不是问题。具体来说，给定一个三元组（𝑒𝑞，𝑟𝑞，𝑒𝑎），我们计算从𝑒𝑞到𝑒𝑎的最短距离。然后，MRR 性能被分组在不同的距离。我们在表 5 中比较了 CompGCN (𝐿 =2)、DPPMN (𝐿=5) 和 RED-GNN (𝐿=5)。所有模型在距离较远的三元组上的性能都较差，并且不能很好地对距离较远的三元组进行建模。 RED-GNN 在距离 5 内具有最佳的距离性能。

• 表4：消融研究结果

• 表5：WN18RR 与 MRR 的每距离评估最短路径的长度

• 图4：不同 𝐿 的 MRR 性能和 𝐿 步内的三元组覆盖率

6. 结论

本文介绍了一种新的关系结构，即 r-digraph，作为 KG 推理的关系路径的广义结构。

对于推理任务（𝑒𝑞，𝑟𝑞，？），在每个 r-digraph 上单独计算是昂贵的。因此，受动态规划解决重叠子问题的启发，我们提出 RED-GNN 作为 GNN 的变体，以有效地构建和有效地学习 r-digraph。

文章展示了 RED-GNN 在 KG 中通过归纳和转导 KG 推理基准实现了最先进的性能。与其他基于 GNN 的基线相比，RED-GNN 的训练和推理非常有效。此外，RED-GNN 可以学习用于推理的可解释结构。

最后，一项并发工作 NBFNet 提出将查询实体之间的所有路径递归编码为多个答案实体，这类似于 RED-GNN。然而，NBFNet 使用全邻接矩阵进行传播，非常昂贵，需要 128GB GPU 内存。在未来的工作中，可以利用 [47] 中的剪枝技术或 [8] 中的分布式编程将 RED-GNN 应用到超大规模的 KG 上。