Extending Complex Logical Queries on Uncertain Knowledge Graphs¶

会议	arXiv	代码	领域	关键词
ACL 2025	2403.01508	-	图学习 / 知识图谱推理	不确定知识图谱, 复杂逻辑查询, 软查询, 神经符号方法, 置信度校准

一句话总结¶

本文提出"软查询"形式化框架，将复杂逻辑查询扩展到不确定知识图谱（带置信度值），并设计 SRC 方法结合前向推理和后向校准来高效回答软查询，理论证明误差不会灾难性级联。

研究背景与动机¶

研究问题： 如何在不完整且带有置信度值的不确定知识图谱（Uncertain KG）上进行复杂逻辑推理？

现有问题： - 现有复杂查询回答（CQA）方法基于布尔逻辑，无法处理知识的不确定性（如"某人掌握 Python 的置信度为 0.8"） - 概率数据库假设所有未观测事实具有均匀不确定性，无法利用机器学习的泛化能力 - 一阶逻辑不足以描述实际推理中的偏好和必要性（如招聘时领导力对 PI 比对初级开发者更重要）

核心动机： 真实世界知识本质上是不确定的（如 O*NET、STRING、ConceptNet），需要一种新的查询语言和推理方法来同时处理知识不确定性和不完整性。

方法详解¶

整体框架¶

提出 Soft Queries on Uncertain KG (SQUK) 设置，包含三个层次： 1. 软查询语言： 在存在一阶逻辑基础上引入 α 必要性和 β 重要性参数 2. SRC 前向推理： 基于 UKGE 置信度函数的符号推理算法 3. 后向校准： 通过 Debiasing 和 Learning 两种策略减少推理误差

关键设计¶

软查询定义： 每个软原子公式 \((h, r, t, α, β)\) 中，\(α\) 为必要性阈值（过滤不达标的候选），\(β\) 为重要性权重（调整不同条件的相对重要性）。语义基于半环 \((+, \max, -\infty)\)，合取为求和、析取为取最大值。

SRC 前向推理算法： - 为每个变量节点维护状态向量 \(C_z \in \mathbb{R}^{|E|}\) - 通过两种等价变换逐步剪枝查询图边：RemoveConstNode（\(O(|E|)\)）和 RemoveLeafNode（\(O(|E|^2)\)） - 最终自由变量的状态向量即为效用向量

误差分析（核心理论贡献）： - Theorem 1：单个软原子查询的推理误差受 UKGE 误差界函数控制 - Theorem 2：合取查询的累积误差至多为线性增长，不会出现灾难性级联误差

损失函数¶

校准 Learning 策略通过可学习仿射变换 \(\hat{P}_c(s,r,o) = \hat{P}(s,r,o)(1+\rho_\theta) + \lambda_\theta\) 校准置信度值，优化 MSE 损失：

\[\mathcal{L} = \sum_{u(s)>0} (U(\phi(s), \hat{P}_c) - U(\phi(s), \mathcal{P}))^2\]

实验¶

主实验结果¶

不确定KG	方法	τ AVG	ρ AVG	MAP AVG	NDCG
CN15k	LogicE+NE	4.8	5.8	7.0	11.2
CN15k	ConE+NE	8.1	10.0	7.7	13.2
CN15k	SRC	5.9	8.9	9.2	15.5
CN15k	SRC(D)	10.5	-	-	-
CN15k	SRC(D+L)	最优	最优	最优	最优

SRC(D+L) 在三个数据集（CN15k、PPI5k、O*NET20k）上的 12 种查询类型中全面超越查询嵌入和神经符号基线。

消融实验¶

消融项	效果
α=0（无必要性过滤）	误差积分范围扩大到 [0,1]，性能下降
Debiasing 策略	通过偏移 α 阈值补偿 UKGE 的零偏向，显著提升性能
Learning 策略	仅在 α=0 时训练校准变换，简化训练但泛化性更好
与 LLM 对比	在自然语言描述的软查询上，SRC 优于商用 LLMs

关键发现¶

SRC 的推理复杂度与现有最优符号方法相同（\(O(n_e|E|^2 + n_r|E|)\)），利用稀疏性可进一步加速约 97%
后向校准策略是性能提升的关键，仅前向推理不足以应对 UKGE 的预测偏差
软查询能建模传统 FOL 查询无法表达的偏好和必要性区分，在招聘、推荐等场景有明确应用价值
即使是先进的 LLM 也难以在结构化知识推理上匹敌专用神经符号方法

亮点¶

形式化定义了"软查询"语言，优雅地将不确定性和偏好融入逻辑查询
严谨的误差界分析（Theorem 1&2）提供了算法可靠性的理论保证
构建了完整的 SQUK 基准数据集，覆盖三个领域（常识、生物、就业）和多种查询结构

局限性¶

UKGE 的预测误差（CN15k 上 MAE 约 0.2）仍然是推理精度的瓶颈
仅在三个中等规模的不确定 KG 上实验，对超大规模图的可扩展性未验证
软需求的 α、β 参数需要人工设定或基于统计分位数启发式选择
当前训练时仅使用基础查询类型（1P、2P 等），对复杂查询结构的泛化需更多验证

评分¶

维度	分数
新颖性	⭐⭐⭐⭐⭐
实用性	⭐⭐⭐⭐
技术深度	⭐⭐⭐⭐⭐
实验充分性	⭐⭐⭐⭐