Graph Distance as Surprise: Free Energy Minimization in Knowledge Graph Reasoning¶

会议: NeurIPS 2025 (NORA Workshop)
arXiv: 2512.01878
代码: 无
领域: 图像生成
关键词: Knowledge Graph, Free Energy Principle, graph distance, surprise minimization, entity grounding

一句话总结¶

将神经科学的 Free Energy Principle (FEP) 与知识图谱推理连接，提出用图的最短路径距离作为 surprise 的度量，将 Murphy et al. 的树结构 surprise 理论推广到一般有向图，为 KG-based agent 的 entity grounding 提供了一个有原则的理论框架。

研究背景与动机¶

FEP 从神经科学走向 AI 系统。Free Energy Principle (FEP) 认为生物系统通过维护精确的世界模型来最小化 surprise。Murphy et al. 此前证明了句法操作通过浅层树结构最小化 surprise，并用树深度量化 surprise。但该框架局限于树结构，无法处理知识图谱中常见的有向图、环路和多路径等复杂拓扑。

KG 推理亟需理论基础。知识图谱在现代 AI agent 中被广泛用于增强推理、记忆和规划，但一个核心问题缺乏理论指导：当 agent 需要基于 KG 进行 entity grounding 时，如何有原则地判断"在给定上下文中，哪些实体是合理的"？现有的 embedding-based 方法（如 TransE、RotatE）虽然实用但缺乏认知科学层面的理论支撑。

图距离作为 surprise 的自然选择。本文提出一个直觉且有理论根基的答案：在 KG 中，距离上下文越近的实体越不令人惊讶（less surprising），距离越远的越令人惊讶。将 KG 视为 agent 的生成模型（generative model），最短路径距离直接对应 FEP 中的 surprise 项，从而将抽象的认知原理转化为可计算的图算法。

方法详解¶

整体框架¶

给定知识图谱 \(\mathcal{G} = (\mathcal{E}, \mathcal{R}, \mathcal{T})\) 和查询上下文 \(C\)，框架通过 BFS 计算上下文到所有候选实体的最短路径距离，结合关系路径的 Kolmogorov complexity 估计，得到每个实体的 free energy 值，低 free energy 意味着高合理性。

关键设计¶

Geometric Surprise（几何惊讶度）:
- 功能：量化实体相对于上下文的"惊讶程度"
- 核心思路：\(S_{\text{geo}}(e|C) = \min_{c \in C} d_{\mathcal{G}}(c, e)\)，若存在路径则为最短有向路径长度（BFS 计算），否则为惩罚常数 \(\alpha\)（应大于图的直径）
- 设计动机：对树结构退化为 Murphy 的树深度，是其自然推广；BFS 通过 visited set 处理环路，保证终止性，复杂度 \(O(|\mathcal{E}| + |\mathcal{T}|)\)
Free Energy 组合公式:
- 功能：将几何距离与路径复杂度结合，给出完整的 surprise 度量
- 核心思路：\(F(e|C) = S_{\text{geo}}(e|C) + \lambda K(\pi_{C \to e})\)，其中 \(K(\pi)\) 是关系路径的 Kolmogorov complexity（通过 Lempel-Ziv 压缩近似）
- 设计动机：仅靠距离不够——频繁出现的关系模式（如 hasLeader）比罕见模式（如跨国推理）更"不令人惊讶"；algorithmic complexity 项捕捉路径的规则性/不规则性
与 FEP 的形式化映射:
- 功能：为图距离 surprise 提供认知科学理论基础
- 核心思路：在 FEP 中 \(F = -\log P(o,s) - H[Q(s)]\)，将 KG 解释为 agent 的生成模型后，\(-\log P(e|C) \propto d_{\mathcal{G}}(C,e)\)（距离越短→概率越高→surprise 越低），\(S_{\text{geo}}\) 实现 surprise 项，\(K(\pi)\) 近似熵项
- 设计动机：FEP 的 least-action 原则与最短路径的最小化目标一致，GNN 的 \(k\) 次 message passing 聚合 \(k\)-hop 邻域也与此呼应

损失函数 / 训练策略¶

本文为理论框架论文，不涉及模型训练。推理流程：构建 KG → 确定上下文 \(C\) → BFS 计算距离 → LZ77 压缩估计路径 Kolmogorov complexity → 组合 free energy \(F = S_{\text{geo}} + \lambda K(\pi)\) → 按 free energy 升序排列候选实体。

实验关键数据¶

主实验¶

本文为理论框架 + worked example，无标准 benchmark 实验。使用加拿大政治 KG 作为示例：

Entity	图距离 \(S_{\text{geo}}\)	\(K(\pi)\) (路径复杂度)	Free Energy \(F\)	说明
Trudeau	1	Low	~1.3	正确答案，1 hop 直接连接
Harper	1	Low	~1.3	正确答案，与 Trudeau 同等 surprise
PrimeMinister (节点)	2	Low	~2.3	抽象角色节点，非直接答案
Biden	5 (=α)	High	~5.5	无路径连接，正确被排斥

消融实验¶

配置	关键指标	说明
仅 \(S_{\text{geo}}\) (无 \(K(\pi)\))	可区分连接/断开实体	但无法区分不同路径模式
\(S_{\text{geo}} + K(\pi)\)	完整 free energy	同时考虑距离和路径规则性
环路处理	BFS 正确处理 Trudeau↔Harper 环	visited set 确保终止

关键发现¶

框架正确将 Trudeau 和 Harper（两任加拿大 PM）识别为低 surprise 实体，Biden（美国总统，与上下文断开）被赋予最高 surprise
环路不影响框架——BFS 通过 visited set 自然处理
多个有效答案可以共存（同等 surprise）

亮点与洞察¶

跨学科视角有新意：将认知科学的 FEP 与 KG 推理做了明确的形式化映射，为 GNN message passing 深度提供了 FEP 视角的理论解释
数学形式简洁：从 surprise 定义到 free energy 组合公式逻辑自洽，对树结构可退化为已有结论
三个理论支撑（proper generalization、least-action、computational grounding）相互呼应

局限与展望¶

仅为 work-in-progress：缺乏在 FB15k-237、YAGO 等标准 KG 数据集上的定量评估
Worked example 过于简单（5 个实体），无法验证在大规模 KG（百万节点）上的可扩展性
"图距离越近越合理"本身是相当直觉的观点，FEP 包装增加了理论装饰但实质贡献有限
Kolmogorov complexity 的 LZ 压缩近似对短关系序列（1-2 hop）质量存疑
所有关系等权处理，实际 KG 中不同关系的语义重要性差异很大
未与 embedding-based 方法（TransE、RotatE）或 path-based 推理做实验对比
\(\alpha\) 和 \(\lambda\) 超参数缺乏系统的选择策略

评分¶

新颖性: ⭐⭐⭐ 跨学科连接有趣但 FEP→图距离的映射相当直觉，理论深度有限
实验充分度: ⭐⭐ Workshop paper，仅有 toy example，无 benchmark 实验
写作质量: ⭐⭐⭐ 逻辑清晰但内容偏薄，形式化严谨
价值: ⭐⭐⭐ 提供了有趣的理论视角但距离实用还有较大距离