InductWave：知识图谱上的归纳式多跳逻辑查询回答

# InductWave：知识图谱上的归纳式多跳逻辑查询回答
来源：https://arxiv.org/html/2607.07422
Mayank Kharbanda, Michael Cochez, Rajiv Ratn Shah, Raghava Mutharaju

M. Kharbanda ([email protected]) 隶属于印度IIIT-Delhi，并客座于荷兰阿姆斯特丹自由大学。M. Cochez ([email protected]) 隶属于芬兰Ellis Institute Finland和奥布学术大学，此前受雇于荷兰阿姆斯特丹自由大学。R. Shah ([email protected]) 隶属于印度IIIT-Delhi，R. Mutharaju ([email protected]) 隶属于印度IIT Palakkad。

###### 摘要

知识图谱上的逻辑多跳查询回答可以视为在隐式完备性假设下的查询问题。当前研究主要聚焦于存在一阶逻辑（EFO）查询，这些EFO查询包含合取（∧）、析取（∨）和否定（¬）算子。大多数现有方法采用*直推式*推理，即无法对训练期间未见过的实体进行推理。在现实世界中，资源稀缺，我们无法用大规模KG的所有节点来训练模型。为此，我们提出InductWave——一种基于小波的*归纳式*嵌入方法，用于大规模KG上的逻辑查询回答。在此设置下，训练图的节点数少于测试图。我们的模型在使用一半消息传递层数的情况下，性能与基线模型持平；在大多数情况下，使用75%的层数即可超越所有基线。更少的资源需求使我们能够评估InductWave在巨型图（如Wiki-KG）上的表现。我们通过在FB15k-(237)数据集上不同训练-测试图比例下的大量实验，与最先进模型进行对比测试。模型代码和数据集可在https://github.com/kracr/inductwave/ 获取。

###### 索引术语：知识图谱、逻辑查询回答、多跳查询回答、归纳式查询回答、图小波。

## I 引言

知识图谱（KG）[17 (https://arxiv.org/html/2607.07422#bib.bib1)]是一种用于表示事实的有向图，它由一组以源实体、关系和目标实体形式表示的三元组组成。KG通过利用结构和逻辑特征，从数据中提取非平凡信息。这些图涵盖医疗、金融、电子商务和搜索等多个领域。在KG上执行推荐系统、链接预测和知识检索等任务以提取新信息[20 (https://arxiv.org/html/2607.07422#bib.bib17)]。KG上的多跳逻辑查询回答涉及回答一阶逻辑（FOL）查询，包括从起始节点遍历KG超过一跳。当前研究主要关注由合取（∧）、析取（∨）和否定（¬）算子组成的存在一阶逻辑（EFO）查询。训练模型主要有两种方法：第一种是*直推式*方法，其中训练图和测试图中的节点和关系完全相同，仅测试图中的三元组（边）数量增加；另一种是*归纳式*方法，模型在节点和/或关系的子集上训练，并能在测试时处理新节点和/或关系。

最先进的现有方法。传统的查询语言（如SPARQL）在处理不完整或噪声数据上的查询时变得不足。为此，引入了神经逻辑查询回答方法。这些模型将查询和KG嵌入到潜在空间中，并在噪声和缺失链接的情况下预测答案。近年来，多跳逻辑查询回答的神经方法取得了显著进展。然而，这些方法大多是*直推式*的，需要在整个KG的所有部分上进行训练，并且在推理时遇到新节点/关系时常常失败。随着现实世界中知识和数据集的扩展，我们需要在包含数百万个节点的巨型KG上处理查询。但由于资源限制，通常不可能用这些巨大KG的所有节点进行训练。解决这一问题的一种方法是在节点较少的子图上训练模型，然后外推至更大的图处理查询。已提出*归纳式*方法，如GNN-QE[38 (https://arxiv.org/html/2607.07422#bib.bib23)]和NodePiece-QE，它们超越了*直推式*模型[9 (https://arxiv.org/html/2607.07422#bib.bib22),10 (https://arxiv.org/html/2607.07422#bib.bib20)]。在*归纳式*设置下，GNN-QE通常在小或中型图上表现优于NodePieceQE。然而，GNN-QE采用内存密集型的链接预测方法NBF-Net[39 (https://arxiv.org/html/2607.07422#bib.bib19)]，使得在大图上训练变得困难。相比之下，NodePiece-QE不存在此类内存限制，从而能高效处理更大规模的图。

我们提出InductWave，一种基于图小波的逻辑查询回答方法。它利用节点的结构信息来增强链接预测。因此，该模型能够在更少的消息传递层数下实现与GNN-QE类似的能力。最终，这使我们能够使用消息传递方法在拥有数百万个节点的巨型图（Wiki-KG）上进行查询。

贡献I：一种新的链接预测方法WAVBFNet。
我们提出了一种新的消息传递算法WAVBFNet，该方法将图小波嵌入[8 (https://arxiv.org/html/2607.07422#bib.bib30)]与神经Bellman-Ford网络（NBF-Net）[39 (https://arxiv.org/html/2607.07422#bib.bib19)]相结合用于链接预测。前者为后者的消息传递方法提供节点的结构上下文。WAVBFNet用于查询回答过程中的关系投影操作。

见图注
图1：*归纳式*查询回答的玩具示例。测试图（Gtest）包含比训练图（Gtrain）更多的节点（用蓝色表示）。虚线圆圈表示查询Q1的解：“说出一位法国菲尔兹奖得主毕业的大学”，其FOL形式为Q = v. ∃ u: win(FieldMedal, u) ∧ citizen(France, u) ∧ graduate(u, v)。

贡献II：消息传递的高效执行。
我们扩展了GE-SpMM[19 (https://arxiv.org/html/2607.07422#bib.bib36)]方法，使其兼容图小波嵌入。这使得WAVBFNet能够在GPU硬件上高效计算，将内存复杂度从O(2b|E|d)降低到O(b|V|d + |E|d)。其中b是批量大小，|E|和|V|分别是三元组和节点数量，d是嵌入维度。

贡献III：广泛评估。
我们在来自FB15k-(237)[30 (https://arxiv.org/html/2607.07422#bib.bib35)]数据集的不同比例训练和推理节点集上评估我们的模型。我们还在包含数百万个节点的Wiki-KG[18 (https://arxiv.org/html/2607.07422#bib.bib34)]数据集上测试模型。结果通过InductWave的消融研究以及空间和运行时分析得到支持。

## II 相关工作

多跳查询回答。在多跳推理中，一种方法是在KG中遍历路径以进行链接预测[33 (https://arxiv.org/html/2607.07422#bib.bib2),23 (https://arxiv.org/html/2607.07422#bib.bib4),5 (https://arxiv.org/html/2607.07422#bib.bib5),14 (https://arxiv.org/html/2607.07422#bib.bib6),13 (https://arxiv.org/html/2607.07422#bib.bib7),32 (https://arxiv.org/html/2607.07422#bib.bib8)]。这些技术改进了对罕见或复杂关系的预测。多跳推理的另一个应用是回答复杂的逻辑查询，涉及处理FOL算子以获得答案。我们的工作与后一种方法一致。

图查询嵌入（GQE）[15 (https://arxiv.org/html/2607.07422#bib.bib9)]和Query2Box[26 (https://arxiv.org/html/2607.07422#bib.bib10)]是首批引入解决包含析取（∨）和合取（∧）算子查询的方法。使用贝塔分布进行嵌入的BetaE[27 (https://arxiv.org/html/2607.07422#bib.bib11)]将否定算子（¬）融入查询。还有几何嵌入方法，如ConE[37 (https://arxiv.org/html/2607.07422#bib.bib33)]和Query2Geom[28 (https://arxiv.org/html/2607.07422#bib.bib37)]，将查询嵌入为潜在空间中的几何形状。FuzzyQE[6 (https://arxiv.org/html/2607.07422#bib.bib12)]在查询遍历之间提供模糊答案集。GNN-QE[38 (https://arxiv.org/html/2607.07422#bib.bib23)]使用NBF-Net[39 (https://arxiv.org/html/2607.07422#bib.bib19)]进行关系投影，并使用模糊算子处理其他FOL操作。CQD[2 (https://arxiv.org/html/2607.07422#bib.bib26)]采用束搜索的贪心方法处理FOL操作，并使用ComplEx[31 (https://arxiv.org/html/2607.07422#bib.bib32)]进行关系投影。RConE[21 (https://arxiv.org/html/2607.07422#bib.bib13)]和STARQE[1 (https://arxiv.org/html/2607.07422#bib.bib14)]分别处理多模态和超关系图中的查询回答。关于KG推理和逻辑查询回答的详细研究分别在[22 (https://arxiv.org/html/2607.07422#bib.bib18)]和[25 (https://arxiv.org/html/2607.07422#bib.bib16)]中。

归纳式逻辑查询回答。到目前为止讨论的大多数逻辑查询回答方法都是*直推式*的，需要为KG中的每个实体训练查询。为了泛化训练过程，提出了*归纳式*方法。最初为*直推式*推理设计的GNN-QE[38 (https://arxiv.org/html/2607.07422#bib.bib23)]也可用于*归纳式*查询回答[9 (https://arxiv.org/html/2607.07422#bib.bib22)]，因为每次关系投影时，节点和关系嵌入都根据查询进行初始化。模型在KG的子图上训练。NodePiece-QE[9 (https://arxiv.org/html/2607.07422#bib.bib22),10 (https://arxiv.org/html/2607.07422#bib.bib20)]是另一种归纳式方法。它通过每个节点的入边（出边）关系来表示节点，并利用节点与少数预定义锚点节点的距离来捕获高层结构信息。该模型使用CQD[2 (https://arxiv.org/html/2607.07422#bib.bib26)]进行FOL操作。ULTRA[11 (https://arxiv.org/html/2607.07422#bib.bib28),12 (https://arxiv.org/html/2607.07422#bib.bib21)]学习跨多个KG的泛化嵌入。它在少数几个KG的关系结构上训练，然后通过比较这些结构在全新的KG上进行测试。该模型在测试时有效处理新的关系集。

图中波。GraphWave[8 (https://arxiv.org/html/2607.07422#bib.bib30)]在无向图上为节点嵌入生成扩散小波，通过基于热核的信息流捕获节点邻域的结构信息。GWNN[34 (https://arxiv.org/html/2607.07422#bib.bib29)]提出了一种图小波神经网络，用于无向图上的节点分类。该模型学习一个对角滤波器，以调整邻居小波变换的信息。之前的模型主要关注低通滤波器，而ASWT[24 (https://arxiv.org/html/2607.07422#bib.bib38)]同时使用带通和低通滤波器进行图小波变换，结合GCN和图小波进行节点分类。

InductWave是一种基于消息传递的*归纳式*逻辑查询回答方法，类似于GNN-QE，但所需内存更少，因此适用于大型图。该方法在其框架中使用图小波。它在KG的样本上训练，并在整个KG上评估；因此我们使用GNN-QE和NodePiece-QE作为基线。我们排除了ULTRA的比较，因为该方法的目标根本不同：它通过在一组KG上训练，从而在多个KG上泛化查询回答。

## III 预备知识

KG上的归纳推理。一个知识图谱G(V, E, R)是一个有向图，包含节点集V、关系集R和三元组集E。
E = {(es, r, eo) | es, eo ∈ V, r ∈ R} (1)
给定 |V| = N 和 |R| = M，如果训练KG (Gtrain) 包含α1个节点和β1个关系，且 |α1| < N 或 |β1| < M，则查询回答称为*归纳式*。此外，推理图|α2|由Gtrain的节点和测试时额外节点组成。归纳式设置意味着模型在训练期间不会看到推理图中的所有节点和/或关系。类似地，可以定义基于归纳式关系的设置。在本文中，我们侧重于归纳式节点设置（|α1| < N 且 β1 = M）。

逻辑查询。一阶逻辑（FOL）查询由锚点集和变量集组成。锚点实体集表示查询的边界条件，通过变量将查询逻辑公式化为存在一阶逻辑（EFO）。EFO(-)查询是FOL的一个子集，其中量词部分利用存在量词。P.公式。以下示例查询是EFO(-)形式：
v: ∃ u: win(FieldMedal, u) ∧ citizen(France, u) ∧ graduate(u, v) (2)
变量u是存在量化的，而v是自由变量。查询的目标是找到从KG中推导出的所有v值。

包含查询。包含查询是FOL的一个子集，仅由合取（∧）和存在量词（∃）组成。在图1中，查询Q1是包含查询的一个示例。

负查询。负查询使用合取（∧）、存在量词（∃）和否定（¬）。例如：
v: ∃ u: graduate(v, u) ∧ ¬topInst(u) (3) 表示所有毕业于非顶尖机构的实体v。

投影操作。在消息传递查询回答中，投影操作将当前查询嵌入通过关系r扩展为邻居节点，形式为：proj(h, r) = hop(h, r) (4)
其中h是当前节点嵌入（对于关系r来说作为源节点），proj是投影后的输出嵌入（目标节点）。在消息传递范式中，我们执行关系投影，通过图的拓扑传播节点嵌入。在后续部分中，我们将符号proj称为公式5的扩展。

## IV 方法

### IV-A 关系投影：WAVBFNet

我们提出WAVBFNet，它在NBF-Net[39]的消息传递中添加了一个初始化步骤。令h(v)是节点v的d维嵌入向量，与查询无关。在投影操作的每一步，我们将此嵌入与当前查询嵌入进行拼接和线性变换，作为消息传递的起始嵌入：
h(0)Q(v) = Winit · [h(v) || q] (5)
其中h(0)Q(v)是消息传递步骤0时节点v的初始嵌入，函数[·]表示拼接，q是查询的向量表示（关系嵌入），Winit是可学习的权重矩阵。

**图小波嵌入** 我们采用复数域（磁）拉普拉斯算子来捕捉边方向信息。我们利用谱序理论[35]，并考虑邻接矩阵的有向对称部分和反对称部分。首先定义一个对称邻接矩阵As(v, u) = max(A(v, u), A(u, v))，如果节点v和u之间存在任何有向边则值为1，否则为0。对于关系r，我们定义有向邻接矩阵Ar，如果节点v和u之间存在关系r的有向边则Ar(v, u) = 1，否则为0。节点v关于关系r的度定义为Dsr(v) = sum_u Asr(v, u)。

接着，我们引入磁拉普拉斯算子[36]的概念。它通过一个表示边方向的角度项来捕捉方向性。对于每个关系r，我们定义：
Θ_r^{(g)}(u, v) = 2π g (A^r(u, v) - A^r(v, u)) (6)
其中g是超参数，取值范围[0, 0.25]。如果存在有向边A^r(u, v) ∈ E，但不存在反向边A^r(v, u) ∉ E，则Θ_r^{(g)}(u, v)为正，而Θ_r^{(g)}(v, u)为负。反之，如果边是双向的或不存在，则Θ_r^{(g)}(u, v) = 0。我们利用厄米矩阵定义原始关系邻接矩阵A^r：
H^{r(g)} = A_s^r ⊙ exp(i_r Θ_r^{(g)}) (7)
这里，i_r是关系r的虚数维度，⊙表示逐元素乘法。A_s^r捕获边存在性，而exp(i_r Θ_r^{(g)})表示方向性。受[36]启发，我们提出关系r的未归一化拉普拉斯算子：
L_un^{r(g)} = D_s^r - H^{r(g)} = D_s^r - A_s^r ⊙ exp(i_r Θ_r^{(g)}) (8)
我们定义KG拉普拉斯算子为这些关系拉普拉斯算子的集合：L_un^{(g)} = { L_un^{r(g)} | r ∈ R }。L_un^{r(g)}是半正定的证明可在补充材料中找到。在公式8中，第r个拉普拉斯算子包含特定关系r的信息。然而，两个不同的关系拉普拉斯算子L_un^{r(g)}和L_un^{s(g)} (r, s ∈ R, r ≠ s)之间没有信息交换。这可能导致KG内关系间的上下文丢失。为解决这一信息损失，我们使用节点在整个KG（GX）中的度数（而非仅基于关系r的度数）来归一化关系拉普拉斯算子。关系r的归一化磁拉普拉斯算子定义为：
L_n^{r(g)} = D_z^{-1/2} L_un^{r(g)} D_z^{-1/2} (9)
其中D_z是节点在整个KG中的度数。