跳转至

Extending Complex Logical Queries on Uncertain Knowledge Graphs

会议: ACL 2025
arXiv: 2403.01508
领域: Knowledge Graph / Logical Reasoning
关键词: 不确定知识图谱, 软查询, 复杂逻辑推理, 知识图谱嵌入, 置信度校准

一句话总结

提出在不确定知识图谱（Uncertain KG）上进行软查询（Soft Query）的新问题设定 SQUK，结合必要性（necessity）和重要性（importance）扩展一阶逻辑查询语义，并设计带校准的神经符号推理方法 SRC，避免前向推理中的级联错误。

研究背景与动机

知识图谱（KG）上的复杂查询回答（Complex Query Answering, CQA）是重要的 AI 推理任务，涉及存在量化、合取、析取和否定等一阶逻辑操作。然而，现有工作存在两个核心局限：

  1. 忽略知识的不确定性：现实世界中知识天然带有不确定性（如 O*NET 职业技能图谱、STRING 蛋白质交互网络中的置信度值），但现有 CQA 方法基于布尔逻辑，与不确定 KG 不兼容
  2. 一阶逻辑表达力不足：在不确定场景下，纯粹的一阶逻辑难以描述实际决策中的细粒度偏好（如"领导力对 PI 岗位很重要"vs"对初级开发者不重要"）

概率数据库虽然扩展了置信度，但假设所有未观测事实具有统一的不确定性，且仅限于一阶逻辑。

方法详解

整体框架

SQUK（Soft Queries on Uncertain KG）设定包含三个创新层面： 1. 将不完整 KG 扩展为不完整+不确定 KG（每条三元组附带置信度 \(p \in [0,1]\)） 2. 将一阶逻辑扩展为带软约束的查询语言（必要性 α + 重要性 β） 3. 提出 SRC 方法（Soft Reasoning with Calibrated Confidence）进行推理

该框架的核心思想是将软约束满足问题（Soft CSP）的理论引入知识图谱推理，通过半环代数统一定义合取、析取和存在量化的语义。实验在 CN15k、PPI5k 和 NL27k 三个不确定 KG 基准上进行，覆盖了从 1p 到 up 的 9 种标准查询结构。

关键设计

1. 软查询的语法与语义

软原子公式定义为 \((h, r, t, \alpha, \beta)\)，其中： - \(\alpha\)（必要性）：源自 possibilistic CSP，定义阈值操作 \([p]_\alpha\)，当 \(p < \alpha\) 时将置信度置零，实现硬过滤 - \(\beta\)（重要性）：源自 weighted CSP，作为权重调整不同条件的相对重要性 - 软合取/析取操作通过半环 \((+, \max, -\infty)\) 实例化

示例：搜索初级开发者候选人 vs PI 候选人： - 初级开发者：不需要领导力（β=1, 低权重），但重视开发能力（β=3） - PI：重视领导力（α=0.7 阈值, β=3 高权重）+ 需要 ML 技能（α=0.9）

2. SRC 推理方法

  • 前向推理：使用不确定知识图谱嵌入（UKGE）预测缺失事实的置信度，然后按软查询语义递归计算效用向量
  • 误差分析：证明了 SRC 避免了前向推理中的灾难性级联错误，计算复杂度与 SOTA 符号方法相同
  • 反向校准（Backward Calibration）：通过去偏（debiasing）和学习来校准 UKGE 预测的置信度，进一步提升性能

3. 效用向量

给定置信度函数 \(P\) 和软查询 \(\Phi\)，每个实体 \(s_i\) 的效用值 \(\mathbf{u}_i = U(\Phi(s_i/y), P)\) 构成效用向量，用于排序候选答案。

实验关键数据

主实验

在 UKGE 设定下的基准测试中： - SRC 在多个软查询类型上显著优于 Query Embedding + Number Embeddings（QE+NE）方法 - 校准后的 SRC（SRC-cal）进一步提升性能，验证了反向校准的有效性 - 在不同查询结构（1p/2p/3p/2i/3i/ip/pi/2u/up）上表现一致

关键发现

  • 与 LLM 在自然语言设定下的公平对比表明，SRC 在精确推理方面有明显优势
  • QE+NE 方法在涉及否定操作的查询上表现尤其差，而 SRC 通过符号推理避免了此问题
  • 反向校准对前向推理的改进是普遍性的，不依赖于特定查询结构
  • 在多跳查询（3p）上 SRC 的优势更加显著，说明符号推理在复杂查询上的级联误差控制能力更强
  • UKGE 的预测质量与最终软查询回答质量高度相关，进一步证明了基座嵌入模型的重要性

亮点与洞察

  1. 问题定义的原创性：将不确定性和软约束编程引入 CQA，necessity 和 importance 的设计直觉清晰且形式化优雅
  2. 理论保证：证明了级联错误的避免和计算复杂度保持不变，这在神经符号方法中很有价值
  3. 实际应用性：以职位搜索为例的动机非常直观，完美展示了软查询相比硬查询的优势
  4. 半环框架的灵活性：通过选择不同的半环实例化，可以适配不同的应用场景

局限性

  • 依赖 UKGE 的预测质量，如果 UKGE 本身性能差，SRC 的上限也会受限
  • 软查询的 α/β 参数需要人工指定，缺乏自动确定或自适应学习的机制
  • 实验规模有限，未在超大规模不确定 KG（如完整的 ConceptNet 或 STRING）上验证可扩展性
  • 半环的选择（\((+, \max)\)）是固定的，其他半环选择（如概率半环）的效果对比不够充分
  • 仅支持存在一阶逻辑中的标准查询结构，未扩展到更复杂的查询模式
  • 校准方法的去偏参数可能对不同数据集需要单独调优
  • 未与最新的 LLM-based KG 推理方法（如基于 in-context learning 的方案）进行系统对比

相关工作

  • 复杂查询回答：BetaE、QTO 等在确定性 KG 上的 CQA 方法
  • 概率数据库：经典的 tuple-independent 概率数据库方法
  • 不确定 KG 嵌入：UKGE 等预测缺失三元组置信度的方法
  • 软约束满足问题：possibilistic CSP、weighted CSP 等约束编程理论

评分

  • 新颖性: ⭐⭐⭐⭐⭐ (全新的问题设定，理论和实践价值兼具)
  • 技术深度: ⭐⭐⭐⭐⭐ (严格的形式化定义 + 误差分析 + 校准方法)
  • 实验充分度: ⭐⭐⭐⭐ (多基线对比，但数据规模偏小)
  • 实用性: ⭐⭐⭐⭐ (搜索/推荐场景下的不确定推理有广泛需求)