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

🕒 Published (v1): 2025-12-01 16:59 UTC · Source: Arxiv · Venue: NEURIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This work-in-progress proposes that knowledge graph (KG) reasoning can be formalized as surprise minimization under the Free Energy Principle (FEP), where graph distance (shortest-path BFS) serves as a proxy for surprise. Entities closer to context nodes in a KG are treated as more plausible groundings because they have lower free energy. The framework extends Murphy et al.'s syntactic tree-depth surprise measure to arbitrary directed graphs with cycles.

Problem¶

Existing LLM-KG integration lacks a principled, theory-grounded mechanism for ranking candidate entity groundings given a query context. Prior work on surprise minimization in language (Murphy et al.) was limited to syntactic tree structures and does not generalize to cyclic directed graphs like KGs.

Method¶

The framework defines geometric surprise for an entity e given context C as:

S_geo(e | C) = min_{c∈C} d_G(c, e) (shortest directed BFS path), or α (a penalty exceeding graph diameter) when no path exists.

Free energy combines geometric surprise with Kolmogorov complexity of the relation path (approximated via Lempel-Ziv compression of the relation sequence):

F(e | C) = S_geo(e | C) + λ·K(π_{C→e})

The KG serves as the agent's generative model; lower F implies higher plausibility. For trees, this recovers Murphy et al.'s tree-depth formulation. Three theoretical justifications are given: generalization from trees, least-action principle alignment with active inference, and correspondence to GNN message-passing depth (k-hop neighborhoods).

Key Contributions¶

Formalizes KG reasoning as FEP surprise minimization, extending Murphy et al.'s syntax result to semantic graphs
Defines geometric surprise via shortest directed-path BFS, handling cycles naturally via visited-set termination
Combines geometric and algorithmic (Lempel-Ziv) complexity into a unified free-energy score for entity grounding
Connects GNN message-passing depth and model-based RL world-model trajectories to the FEP framework
Provides a worked example (Canadian PM KG) demonstrating cycle handling, multi-answer coexistence, and disconnected-entity penalization

Results¶

No empirical benchmarks are reported. The paper is explicitly work-in-progress. The only quantitative demonstration is a manually computed worked example on a 5-entity toy KG: - Trudeau, Harper: S_geo = 1, F ≈ 1.3 (correctly ranked as plausible PMs) - Biden: S_geo = α = 5, F ≈ 5.5 (correctly rejected as disconnected)

Limitations¶

No empirical validation; framework is tested only on a hand-constructed 5-entity toy graph
Kolmogorov complexity is uncomputable; Lempel-Ziv approximation on short relation sequences may be unreliable
α (disconnection penalty) and λ (complexity weight) are hyperparameters with no tuning guidance beyond heuristics
Framework covers only entity grounding ranking; does not address relation prediction or multi-hop inference strategies
Directionality assumption (only outgoing edges) may miss valid reverse-traversal reasoning paths
No comparison to existing KG reasoning baselines (e.g., TransE, R-GCN, KGQA systems)

Relevance to Agentic AI / LLM Agents¶

This paper directly targets a core challenge in KG-augmented LLM agents: principled entity grounding when the agent queries a structured knowledge base. By framing the KG as an agent's generative world model and grounding selection as free-energy minimization, it offers a neuroscience-motivated alternative to heuristic retrieval. The connection to active inference is directly relevant to agentic planning loops—pragmatic (exploitation) vs. epistemic (exploration) value naturally maps onto goal-directed vs. curiosity-driven agent behavior. If empirically validated, the BFS-based surprise score could serve as a lightweight, interpretable ranking signal for RAG-over-KG agents.