Is Complex Query Answering Really Complex?¶

会议: ICML 2025
arXiv: 2410.12537
代码: 未提及
领域: 图学习 / 知识图谱推理
关键词: 复杂查询回答, 知识图谱, 多跳推理, 基准评估, 数据泄露

一句话总结¶

本文揭示了知识图谱复杂查询回答（CQA）现有基准中高达 98% 的"复杂"查询实际上可被简化为简单的单链接预测问题，由此导致研究进展被严重高估；作者提出了平衡采样的新基准（FB15k237+H、NELL995+H、ICEWS18+H），并引入混合求解器 CQD-Hybrid 验证了这一发现，在新基准上所有 SOTA 方法的 MRR 大幅下降（最多超过 30 个点）。

研究背景与动机¶

领域现状：复杂查询回答（CQA）是知识图谱（KG）上的一项核心推理任务，要求模型根据逻辑查询（包含合取、析取、存在量化等操作）在不完整的知识图谱上检索答案。近年来，大量神经方法（如 BetaE、ConE、GNN-QE、CQD、QTO 等）被提出，在 FB15k237 和 NELL995 等标准基准上取得了令人印象深刻的性能提升。

现有痛点：然而，这些基准的构建方式隐含了一个关键问题——训练集中已经包含了测试查询推理树中大量的边（链接）。这意味着一个标注为"2i1p"类型的复杂查询，实际上可能只需要预测其中一条缺失链接，其余链接都已在训练数据中出现过。

核心矛盾：现有基准将所有同一查询类型的查询-答案（QA）对视为等难度，但实际上存在一个从"仅需预测1条链接"（partial-inference，最简单）到"所有链接都缺失"（full-inference，最难）的难度谱系。由于基准中绝大多数 QA 对属于最简单的 partial-inference 类型，MRR 指标被严重膨胀，研究者对 CQA 领域真实进展的感知被扭曲。

本文目标 - 量化现有基准中"简单"QA 对的比例 - 揭示 SOTA 方法在真正困难的 full-inference 查询上的实际表现 - 构建更公平、更具挑战性的新基准

切入角度：作者从"推理树"（reasoning tree）的视角出发，分析每个 QA 对的推理树中有多少链接来自训练集，从而将查询的"形式复杂度"与"实际难度"解耦。

核心 idea：通过分析推理树中训练链接的泄露程度，揭示 CQA 基准的虚假复杂性，并构建难度均衡的新基准来真实度量模型的多跳推理能力。

方法详解¶

整体框架¶

本文并非提出新的 CQA 模型，而是一项系统性的基准分析与重构工作。整体流程包含三个阶段： 1. 诊断阶段：定义推理树和 QA 对的难度分类体系（trivial / partial-inference / full-inference），量化现有基准中各类 QA 对的分布 2. 验证阶段：提出 CQD-Hybrid 混合求解器，验证"记忆训练链接"即可解释 SOTA 性能的假设；对多个 SOTA 方法做分层性能评估 3. 重构阶段：构建三个新基准（FB15k237+H、NELL995+H、ICEWS18+H），确保各难度级别的 QA 对均匀采样，并新增 4p 和 4i 两种更复杂的查询类型

关键设计¶

推理树与难度分类体系（Reasoning Tree & Hardness Taxonomy）
- 功能：为每个 QA 对 \((q, t)\) 定义推理树——从锚定实体到目标实体的有向无环图，结构匹配查询图
- 核心思路：检查推理树中每条边是否属于 \(G_{\text{train}}\)。若所有边都在训练集中，则为 trivial（被过滤）；若部分边在训练集中，则为 partial-inference（可简化为更简单的查询类型）；若所有边都在测试集中，则为 full-inference（真正需要多跳推理）。当存在多条推理路径时，选择缺失链接最少、跳数最少的那条
- 设计动机：现有评估将同一查询类型的所有 QA 对视为等难度，但实际上一个 2i1p 查询可能只需要预测 1 条链接（等价于 1p 链接预测），这完全不需要多跳推理能力。该分类体系让我们能精确量化基准中的"虚假难度"
CQD-Hybrid 混合求解器
- 功能：在 CQD 基础上，对训练集中已知的链接赋予最高分数，而非依赖神经链接预测器的输出
- 核心思路：CQD 将复杂查询分解为多个 1p 子查询，每个 1p 查询由神经链接预测器打分，通过模糊逻辑算子（fuzzy logic operators）组合分数。CQD-Hybrid 的唯一改动是：若某条边 \((s, p, o) \in G_{\text{train}}\)，则直接赋予该边最高分数，而非使用预测器输出。这样，贪心搜索过程会优先沿着已知链接推理
- 设计动机：验证假设——如果仅仅利用训练链接的记忆就能大幅提升性能，说明现有基准的"好成绩"主要来自记忆能力而非推理能力。CQD-Hybrid 比 QTO 和 FIT 等混合方法更简单（无需分数校准和前向/后向更新），但已足以达到甚至超越 SOTA
新基准构建策略
- 功能：构建 FB15k237+H、NELL995+H、ICEWS18+H 三个新基准
- 核心思路：对每种查询类型，均匀采样各个难度级别的 QA 对。例如对 3p 查询，采样 30,000 个 QA 对，其中 10,000 个可简化为 1p，10,000 个可简化为 2p，10,000 个为 full-inference。同时过滤 union 查询中推理树包含"不存在链接"（既不在训练集也不在测试集中）的 QA 对。新增 4p（四跳路径）和 4i（四路交叉）两种更难的查询类型
- 设计动机：消除现有基准中对简单 QA 对的极端偏向（1p 可达 98%），让 MRR 指标真实反映模型在各难度级别上的推理能力
ICEWS18 时序分割策略
- 功能：基于时态知识图谱 ICEWS18 构建更真实的训练/测试分割
- 核心思路：传统基准的训练/测试分割是随机的（假设三元组独立），不符合实际。ICEWS18+H 按时间戳排序三元组，前 80% 为训练集，中间 10% 为验证集，最后 10% 为测试集，相同事实只保留最早的时间戳
- 设计动机：模拟"用过去的知识预测未来"的真实场景，即使是简单的 1p 查询也变得更具挑战性

Union 查询的假难度发现¶

作者发现 FB15k237 和 NELL995 中 2u 和 2u1p 类型查询的推理树中存在"不存在链接"——既不在 \(G_{\text{train}}\) 也不在 \(G_{\text{test}}\) 中的边。这些边违反了 inference-based QA 对的定义。过滤掉这些异常 QA 对后，2u 查询的 MRR 从远低于 1p 恢复到了与 1p 相当的水平，证实了理论上 2u 和 1p 应有相同难度的预期。

实验关键数据¶

主实验：现有基准中 QA 对的难度分布¶

查询类型	可简化为 1p (FB15k237)	Full-inference (FB15k237)	可简化为 1p (NELL995)	Full-inference (NELL995)
2p	98.1%	1.9%	97.6%	2.4%
3p	97.2%	0.1%	95.6%	0.1%
2i	96.0%	4.0%	94.0%	6.0%
3i	91.6%	0.2%	87.4%	0.5%
1p2i	86.8%	0.2%	49.5%	0.9%
2i1p	96.7%	0.1%	96.2%	0.2%
2u1p	98.3%	0.1%	98.5%	0.1%

新基准上 SOTA 方法的 MRR 对比¶

方法	1p	2p	3p	2i	3i	2i1p	4p	4i
FB15k237+H
GNN-QE	42.8	5.2	4.0	6.0	8.8	9.9	4.3	20.0
CQD	46.7	4.4	2.4	11.3	12.8	11.5	1.1	23.8
CQD-Hybrid	46.7	4.8	3.1	6.0	8.6	12.9	2.4	17.4
QTO	46.7	4.9	3.7	8.7	10.1	13.5	3.9	20.2
CLMPT	45.3	5.3	4.7	10.2	12.2	14.9	4.5	24.0
NELL995+H
CQD	60.4	9.6	4.2	18.5	19.6	22.6	2.0	24.8
QTO	60.3	9.8	8.0	14.6	15.8	21.1	7.0	20.9
CLMPT	58.1	10.1	7.8	22.7	25.0	24.4	7.2	29.1

关键发现¶

性能膨胀惊人：在旧基准 FB15k237 上，QTO 在 3i 查询上可达 MRR 54.6，但在新基准 FB15k237+H 上仅为 10.1，下降超过 44 个点
记忆即 SOTA：CQD-Hybrid 仅在 CQD 基础上加入训练链接记忆，就能在旧基准 14 项指标中 9 项超越或持平更复杂的非混合 SOTA 方法（Table 3）
没有统一的 SOTA：在新基准上，没有任何单一方法在多数查询类型上占据 SOTA 地位，说明现有方法可能过拟合了旧基准的简单 QA 对分布
2u 查询的假难度：过滤不存在链接后，2u 查询的 MRR 从 ~15 恢复到 ~33-41（FB15k237），接近 1p 水平，证实 2u 的"难度"只是数据构建的人工制品
时序分割更具挑战性：ICEWS18+H 即使在 1p 查询上也远难于 FB15k237+H 和 NELL995+H（如 CQD 的 1p MRR 仅 16.6 vs 46.7 和 60.4），说明数据分割方式对基准难度影响巨大

亮点与洞察¶

推理树难度分类体系是一个简洁而深刻的分析框架。它将"查询类型≠查询难度"这一直觉形式化为可量化的概念（trivial / partial-inference / full-inference），为未来所有 CQA 基准的构建提供了理论基础。这一思路可以迁移到任何存在"训练信息泄露"的图推理任务中
CQD-Hybrid 的极简设计揭示了一个尴尬的现实：只需在已有方法上加一行"如果边在训练集中则给最高分"，就能接近甚至超越精心设计的 SOTA 方法。这种"最小干预实验"是验证假设的优秀方法论范例
Union 查询"不存在链接"的发现是一个纯粹的数据质量问题，但长期以来被忽视，导致社区对 2u/2u1p 类型查询的难度产生了系统性误判。这提醒我们在构建基准时必须验证数据的语义一致性
均衡采样 + 时序分割的新基准设计思路可推广到其他需要多步推理的任务评估中（如多跳问答、程序合成等）

局限与展望¶

仅考虑单目标变量查询：本文分析仅覆盖绑定单个目标变量的查询，但许多真实世界查询需要多变量绑定（答案元组），未来需扩展到多变量场景
分析范围限于封闭世界假设：新基准仍然假设测试链接是唯一的"缺失"链接，未考虑开放世界中可能存在的未知实体和关系
未涵盖归纳设置：作者承认未分析归纳场景（inductive setting），即测试时出现训练中未见过的实体和关系，这是 CQA 的一个重要研究方向
CQD-Hybrid 的简单性既是优势也是局限：它仅验证了"记忆假设"，但未提出能在新基准上真正提升 full-inference 性能的新方法
新基准的难度可能过于均匀：实际应用中各难度级别的查询分布不太可能完全均匀，是否应根据真实 KG 的统计特性来确定采样比例值得探讨

评分¶

新颖性: ⭐⭐⭐⭐ 核心发现（基准虚假复杂性）具有重要价值，但分析方法较为直观，技术新颖性一般
实验充分度: ⭐⭐⭐⭐⭐ 分析极其系统，覆盖两个旧基准+一个新时序基准，6 种 SOTA 方法，包含含否定/不含否定的多种查询类型
写作质量: ⭐⭐⭐⭐⭐ 论文逻辑清晰，Figure 1 的示例非常直观，从诊断到验证到新基准构建层层推进
价值: ⭐⭐⭐⭐⭐ 对 CQA 社区的基准评估范式有根本性影响，新基准将成为后续工作的标准测试平台