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

Abstract

In this work, we propose that reasoning in knowledge graph (KG) networks can be guided by surprise minimization. Entities that are close in graph distance will have lower surprise than those farther apart. This connects the Free Energy Principle (FEP) [1] from neuroscience to KG systems, where the KG serves as the agent's generative model. We formalize surprise using the shortest-path distance in directed graphs and provide a framework for KG-based agents. Graph distance appears in graph neural networks as message passing depth and in model-based reinforcement learning as world model trajectories. This work-in-progress study explores whether distance-based surprise can extend recent work showing that syntax minimizes surprise and free energy via tree structures [2].

Keywords

• eol>Knowledge Graphs
• Graph Neural Networks
• Active Inference
• Semantic Grounding
• Agents

1. Introduction

The Free Energy Principle (FEP) suggests that biological systems minimize surprise by maintaining accurate world models [ 1, 3, 4 ]. Recently, Murphy et al. [ 2 ] demonstrated that syntactic operations minimize surprise through shallow tree structures. They quantified surprise via tree depth (geometric complexity) and Kolmogorov complexity (algorithmic complexity), approximated through Lempel-Ziv compression [ 5, 6 ].

In FEP, agents minimize variational free energy = − log (, ) − [()] , where represents observations, hidden states, the generative model, and the agent’s beliefs [ 1 ]. The first term, − log (, ) , quantifies surprise: entities with high probability under the generative model (high (, )) yield low surprise (low − log (, ) ). For syntactic trees, Murphy et al. [ 2 ] used tree depth to proxy this probability; we extend this principle to general graphs using shortest-path distance.

In active inference, minimizing free energy drives both perception (updating beliefs ()) and action (selecting policies that reduce uncertainty) [ 3 ]. We apply this principle to KG reasoning: entities at shorter graph distances have a higher probability under the agent’s graph-based generative model. The central question we address is: given a KG serving as an agent’s generative model, which entity groundings are plausible for a query in context? We propose one principled approach: plausibility inversely correlates with graph distance.

Knowledge graphs (KGs) are increasingly integrated with modern AI agents, with the ability to improve reasoning, memory, and planning [ 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ]. Unlike syntactic tree structures, KGs are directed graphs that can contain cycles and multiple paths between nodes (entities). In this preliminary work, we propose that surprise in KG reasoning corresponds to graph distance, where the KG serves as the agent’s generative model. Entities that require shorter paths from context are unsurprising, whereas distant or disconnected entities are more surprising. This is unlike surprisedriven exploration in RL [ 17, 18 ], where agents maximize surprise to explore, FEP agents minimize surprise by maintaining accurate generative models. Our work connects the FEP to practical KG systems through shortest-path distance, providing theoretical foundations for graph neural networks [ 19, 20, 21 ] and model-based reinforcement learning [ 22, 23 ].

2. From Syntax to Semantics

Murphy et al. [ 2 ] quantified syntactic surprise via tree depth. We extend this to arbitrary directed graphs with cycles. Given a KG = (ℰ , ℛ, ) with entities ℰ , relations ℛ, and triples ⊆ ℰ × ℛ × ℰ geometric surprise is: ⎧ ⎨ m∈in (, ) if path exists ⎩ otherwise where (, ) is the shortest directed path length from context ∈ to entity (computed via BFS, Appendix B), and is a hyperparameter penalizing disconnection. In our worked example, we set = 5 ; in general, should exceed the graph’s diameter (longest shortest-path distance) to ensure disconnected entities always have higher surprise than any connected entity. Combined with algorithmic complexity [ 2 ]:

( | ) = geo( | ) + ( →) where ( →) is Kolmogorov complexity of the relation path, approximated via Lempel-Ziv compression, and weights the components. For trees, this recovers Murphy’s tree depth; for general graphs, it handles cycles naturally.

Connection to FEP: Under FEP, agents minimize = − log (, ) − [()] [ 1 ]. Interpreting the KG as the agent’s generative model, we posit − log ( | ) ∝ (, ): shorter distances indicate higher probability. Thus geo implements the surprise term, while () approximates [()]. Figure 1 illustrates this with a political KG example (detailed calculations in Appendix A).

A. Murphy et al.: Syntax (Trees)

F = GraphDepth + ?K

B. Our Work: Semantics (KGs) (1) (2)

A Tree Depth

B

C

Canada (context) hasLeader hasLeader D

E

F

G

Trudeau holdsPosition

depth = 2 Harper holdsPosition No Path

Biden depth = ?

Prime Minister Prime Minister successor depth = 2

3. Theoretical Justification

Three principles justify the shortest-path distance: (1) Proper generalization: For trees, it recovers Murphy’s tree depth. (2) Least-action: Shortest paths minimize cumulative cost, aligning with active inference where agents minimize expected free energy [ 3 ]. (3) Computational grounding: In GNNs, message-passing iterations aggregate -hop neighborhoods [ 19, 21 ]; minimizing iterations minimizes distance and surprise. Cycles pose no issue: FEP accommodates circular causality [ 24 ], and BFS handles cycles via visited sets (Appendix B).

4. Implications and Future Work

This work-in-progress connects FEP from neuroscience to KG reasoning in AI systems. The presented framework ofers practical implications: (1) Entity grounding: LLM-KG systems could rank candidate entity groundings by computing geo via BFS from discourse context entities, preferring groundings with lower free energy [ 10, 9 ]; (2) KG embeddings: embedding methods could preserve distance-based surprise structure [ 25 ]; (3) GNN architecture: depth could be selected to balance computational cost against the surprise horizon needed for a task.

Future work includes empirical validation on benchmark KG datasets (FB15k-237 [ 26 ], YAGO [ 27 ]), comparison with human semantic similarity judgments, integration with existing KG reasoning systems [ 10, 28, 9 ], and extension to temporal KGs.

This work represents an early-stage exploration of applying FEP to knowledge graph reasoning. While we proposed the shortest-path distance as a principled formalization of surprise, other formulations may be more elegant or practical.

We aim to present this contribution as an initial research direction rather than a definitive solution. We also encourage the community to develop complementary or improved approaches to connecting FEP principles with graph-based reasoning.

Acknowledgments

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), Alberta Innovates, Alberta Advanced Education, and Athabasca University, Canada. We would also like to thank the reviewers for their suggestions on how to improve this work.

Declaration on Generative AI

During the preparation of this work, the author(s) used Grammarly and Claude (Anthropic) for Grammar and spelling checks.

A. Worked Example: Free Energy Calculations

A.1. Scenario and Knowledge Graph

Consider query “Who is the Prime Minister?” with context = {Canada}. The knowledge graph contains:

Entities: ℰ = {Canada, Trudeau, Harper, PrimeMinister, Biden}

Relations: (Canada, hasLeader, Trudeau), (Canada, hasLeader, Harper), (Trudeau, holdsPosition, PrimeMinister), (Harper, holdsPosition, PrimeMinister),(Trudeau, successor, Harper), (Harper, predecessor, Trudeau)

The successor/predecessor relations form a cycle: Trudeau ↔ Harper. Importantly, Biden has no directed path from Canada (separate subgraph).

A.2. Computing Geometric Surprise

Using BFS from Canada, we compute shortest directed paths: • (Canada, Trudeau) = 1 (direct via hasLeader) • (Canada, Harper) = 1 (direct via hasLeader) • (Canada, PrimeMinister) = 2 (via hasLeader then holdsPosition) • (Canada, Biden) = ∞ (no path)

Therefore: geo(Trudeau) = geo(Harper) = 1, geo(PrimeMinister) = 2, and geo(Biden) = = 5.

The cycle between Trudeau and Harper does not afect distances: BFS selects the shortest path (direct edge) and handles cycles via visited set (Appendix B).

A.3. Computing Algorithmic Complexity

For each grounding, we estimate Kolmogorov complexity via relation path patterns:

Trudeau & Harper: Paths = [hasLeader] use frequent relations, yielding high compression (low ()).

PrimeMinister node: Path = [hasLeader, holdsPosition] uses standard role-modeling patterns, also yielding low ().

Biden: No path from Canada. The grounding requires irregular cross-country reasoning not represented in the graph (high ()).

A.4. Free Energy Results

Combining components with = 1: Entity

Trudeau Harper Biden

geo

Interpretation: Real groundings (Trudeau, Harper) exhibit low free energy: (1) short distance (1 hop), (2) regular relation patterns. The impossible grounding (Biden) exhibits high free energy: (1) disconnection (no path), (2) irregular pattern. The framework correctly identifies both Trudeau and Harper as plausible (both were Canadian PMs) while rejecting Biden (US president).

We focus on entity groundings (Trudeau, Harper, Biden) rather than the position node itself, as queries about leadership typically seek individuals rather than abstract roles. The PrimeMinister node, at distance 2, would have intermediate surprise (geo = 2, ≈ 2.3 ), but is not a direct answer to “Who is the Prime Minister?” This demonstrates how our framework naturally distinguishes between entities at diferent levels of abstraction in reified KG schemas.

This demonstrates three key properties: (1) cycles handled naturally, (2) multiple valid answers coexist with equal surprise, (3) disconnected entities correctly penalized.

B.1. Breadth-First Search Algorithm

Given directed graph = (ℰ , ℛ, ) and context ⊆ ℰ , we compute geo( | ) via BFS:

Algorithm 1 Compute Geometric Surprise

Require: Knowledge graph , context , target entity Ensure: Geometric surprise geo( | ) 1: Initialize: () ← 0 for all ∈ ; () ← ∞ for ∈/ 2: ← (queue), ← (visited set) 3: while ̸= ∅ do 4: ← dequeue from 5: for each outgoing edge (, , ) ∈ do 6: if ∈/ then 7: () ← () + 1 8: ← ∪ {}, enqueue to 9: end if 10: end for 11: end while 12: return () if () < ∞, else

Properties: (1) Correctness: BFS finds shortest paths in (|ℰ | + | |) time. (2) Cycle handling: Visited set prevents re-visiting nodes, ensuring termination. (3) Directionality: Only outgoing edges followed, respecting direction.

B.2. Kolmogorov Complexity Approximation

We approximate ( →) via Lempel-Ziv compression: (1) Extract relation sequence = [ 1, . . . , ] from shortest path. (2) Encode as string (e.g., “pm|successor”). (3) Compress with LZ77. (4) Compute ratio () = compressed/original.

Interpretation: Regular patterns (frequent relations, short sequences) achieve high compression (low ). Irregular patterns (rare relations, long sequences) achieve low compression (high ). This approximates Kolmogorov complexity, which is uncomputable [ 5 ]. Murphy et al. [ 2 ] use the same approximation for syntactic patterns.

B.3. Connection to Active Inference

In active inference, agents minimize expected free energy () [ 3, 4 ]: () = [(|)‖ ()] + E(|) [[ (|)]] ⏟ Pragm⏞atic ⏟ (3) balancing pragmatic value (exploitation) and epistemic value (exploration).

Pragmatic value: Entities at shorter distances are more likely: (observe | ) increases as geo decreases, making low-distance entities preferred for goal-directed actions.

Epistemic value: Entities at longer distances provide higher information gain: observing distant entities reduces uncertainty about unexplored graph regions, making high-distance entities preferred for exploration.

Our geo implements pragmatic value: low surprise entities preferred for exploitation. Extensions could weight distance inversely for epistemic value, valuing high-surprise entities for exploration.

References

[1] K. Friston , The free-energy principle: a unified brain theory? , Nature Reviews Neuroscience 11 ( 2010 ) 127 - 138 . URL: https://www.nature.com/articles/nrn2787. doi: 10 .1038/nrn2787.

[2] E. Murphy , E. Holmes , K. Friston , Natural language syntax complies with the free-energy principle , Synthese 203 ( 2024 ) 154 . URL: https://link.springer. com/10.1007/s11229-024-04566-3 . doi: 10 .1007/ s11229-024-04566-3.

[3] K. Friston , T. FitzGerald, F. Rigoli , P. Schwartenbeck , G. Pezzulo, Active Inference: A Process Theory , Neural Computation 29 ( 2017 ) 1 - 49 . URL: https://direct.mit.edu/neco/article/29/1/1-49/ 8207. doi: 10 .1162/NECO_a_ 00912 .

[4] T. Parr , G. Pezzulo, K. J. Friston , Active Inference: The Free Energy Principle in Mind, Brain, and Behavior , The MIT Press, 2022 . URL: https://direct.mit.edu/books/book/5299/ Active-InferenceThe-Free-Energy- Principle-in-Mind. 0001 .

[5] M. Li , P. Vitányi , An Introduction to Kolmogorov Complexity and Its Applications , Texts in Computer Science, Springer New York, New York, NY, 2008 . URL: http://link.springer.com/10.1007/ 978-0- 387 -49820-1. doi: 10 .1007/978-0- 387 -49820-1.

[6] J. Ziv , A. Lempel , A universal algorithm for sequential data compression , IEEE Transactions on Information Theory 23 ( 1977 ) 337 - 343 . URL: https://ieeexplore.ieee.org/document/1055714/. doi: 10 .1109/TIT. 1977 . 1055714 .

[7] L. Chen , P. Tong , Z. Jin , Y. Sun , J. Ye , H. Xiong , Plan-on-graph: self-correcting adaptive planning of large language model on knowledge graphs , in: Proceedings of the 38th International Conference on Neural Information Processing Systems , NIPS '24, Curran Associates Inc., Red Hook , NY , USA, 2025 . Event-place: Vancouver, BC, Canada.

[8] Y. Cui , Z. Sun , W. Hu , A prompt-based knowledge graph foundation model for universal in-context reasoning , in: Proceedings of the 38th International Conference on Neural Information Processing Systems , NIPS '24, Curran Associates Inc., Red Hook , NY , USA, 2025 . Event-place: Vancouver, BC, Canada.

[9] X. He , Y. Tian , Y. Sun , N. V. Chawla , T. Laurent , Y. LeCun , X. Bresson , B. Hooi , G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering , in: The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024 . URL: https://openreview.net/forum?id= MPJ3oXtTZl .

[10] G. Jhajj , X. Zhang , J. R. Gustafson , F. Lin , M. P.-C. Lin , Educational Knowledge Graph Creation and Augmentation via LLMs , in: A. Sifaleras , F. Lin (Eds.), Generative Intelligence and Intelligent Tutoring Systems , Springer Nature Switzerland, Cham, 2024 , pp. 292 - 304 . doi: 10 .1007/978-3- 031 -63031-6_ 25 .

[11] G. Jhajj , J. R. D. Gustafson , R. Morland , C. E. Gutierrez , M. P.-C. Lin , M. A. A. Dewan , F. Lin , Neuromorphic Knowledge Representation: SNN-Based Relational Inference and Explainability in Knowledge Graphs , in: S. Graf, A . Markos (Eds.), Generative Systems and Intelligent Tutoring Systems , volume 15724 , Springer Nature Switzerland, Cham, 2026 , pp. 159 - 165 . URL: https://link. springer.com/10.1007/978-3- 031 -98284-2_ 13 . doi: 10 .1007/978-3- 031 -98284-2_ 13 .

[12] G. Jhajj , Y. Nomura , Jack and the beansTALK: Towards question answering in plant biology , in: Eighth Widening NLP Workshop (WiNLP 2024) Phase II , 2024 . URL: https://openreview.net/forum? id=0DlJEPHHKe.

[13] R. D. Morland , F. Lin , An adaptable client-server architecture for generating educational content using large language models , Bulletin of the Technical Committee on Learning Technology (ISSN: 2306-0212) 25 ( 2025 ) 42 - 49 .

[14] J. R. D. Gustafson , G. Jhajj , X. Zhang , F. O. Lin , Enhancing project-based learning with a genai tool based on retrieval: Augmented generation and knowledge graphs, in: AI Applications and Strategies in Teacher Education , IGI Global , 2025 , pp. 161 - 194 .

[15] G. Jhajj , F. Lin , Augmenting japanese language acquisition via LLMs and ASR , in: IEEE Smart World Congress 2025 (IEEE SWC'25) , Calgary, Canada, 2025 , p. 3 . 84 .

[16] M. R. Kabir , F. Lin , An llm-powered adaptive practicing system ., in: LLM@ AIED , 2023 , pp. 43 - 52 .

[17] D. Pathak , P. Agrawal , A. A. Efros , T. Darrell, Curiosity-driven exploration by self-supervised prediction , in: Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML'17 , JMLR.org, 2017 , p. 2778 - 2787 .

[18] T. Rakotoaritina , G. Jhajj, C. Reinke , K. Doya , Information-theoretic formulation and combination of intrinsic rewards: Novelty, surprise and empowerment , in: Seventh International Workshop on Intrinsically Motivated Open-ended Learning , 2025 . URL: https://openreview.net/forum?id= WN7ofwXNvv .

[19] T. N. Kipf , M. Welling , Semi-Supervised Classification with Graph Convolutional Networks , in: International Conference on Learning Representations, 2017 . URL: https://openreview.net/forum? id= SJU4ayYgl .

[20] M. Schlichtkrull , T. N. Kipf , P. Bloem , R. Van Den Berg, I. Titov, M. Welling , Modeling Relational Data with Graph Convolutional Networks , in: A. Gangemi , R. Navigli , M.-E. Vidal, P. Hitzler , R. Troncy , L. Hollink , A. Tordai , M. Alam (Eds.), The Semantic Web , volume 10843 , Springer International Publishing, Cham, 2018 , pp. 593 - 607 . URL: https://link.springer.com/10. 1007/978-3- 319 -93417-4_ 38 . doi: 10 .1007/978-3- 319 -93417-4_ 38 .

[21] P. W. Battaglia , J. B. Hamrick , V. Bapst , A. Sanchez-Gonzalez , V. Zambaldi , M. Malinowski , A. Tacchetti , D. Raposo , A. Santoro , R. Faulkner , C. Gulcehre , F. Song , A. Ballard , J. Gilmer , G. Dahl , A. Vaswani , K. Allen , C. Nash , V. Langston , C. Dyer , N. Heess , D. Wierstra , P. Kohli , M. Botvinick , O. Vinyals , Y. Li , R. Pascanu , Relational inductive biases, deep learning , and graph networks , 2018 . URL: http://arxiv.org/abs/ 1806 .01261. doi: 10 .48550/arXiv. 1806 . 01261 , arXiv: 1806 .01261.

[22] R. S. Sutton , A. G. Barto , Reinforcement Learning: An Introduction, A Bradford Book , Cambridge, MA, USA, 2018 .

[23] B. Millidge , A. Tschantz , A. K. Seth , C. L. Buckley , On the Relationship Between Active Inference and Control as Inference , in: T. Verbelen, P. Lanillos , C. L. Buckley , C. De Boom (Eds.), Active Inference , volume 1326 , Springer International Publishing, Cham, 2020 , pp. 3 - 11 . URL: https: //link.springer.com/10.1007/978-3- 030 -64919- 7 _1. doi: 10 .1007/978-3- 030 -64919- 7 _ 1 .

[24] K. Friston , M. Levin , B. Sengupta , G. Pezzulo, Knowing one's place: a free-energy approach to pattern regulation , Journal of The Royal Society Interface 12 ( 2015 ) 20141383 . URL: https: //royalsocietypublishing.org/doi/10.1098/rsif. 2014 . 1383 . doi: 10 .1098/rsif. 2014 . 1383 .

[25] A. Bordes , N. Usunier , A. Garcia-Durán , J. Weston , O. Yakhnenko , Translating embeddings for modeling multi-relational data , in: Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS'13 , Curran Associates Inc., Red Hook , NY , USA, 2013 , pp. 2787 - 2795 . Event-place: Lake Tahoe, Nevada.

[26] M. Schlichtkrull , T. N. Kipf , P. Bloem , R. v. d. Berg, I. Titov, M. Welling , Modeling relational data with graph convolutional networks , in: European semantic web conference , Springer, 2018 , pp. 593 - 607 .

[27] F. M. Suchanek , G. Kasneci, G. Weikum, Yago: a core of semantic knowledge , in: Proceedings of the 16th International Conference on World Wide Web, WWW '07 , Association for Computing Machinery, New York, NY, USA, 2007 , p. 697 - 706 . URL: https://doi.org/10.1145/1242572.1242667. doi: 10 .1145/1242572.1242667.

[28] Y. Deng , C. Ye , Z. Huang , M. D. Ma , Y. Kou , W. Wang, GraphVis: Boosting LLMs with Visual Knowledge Graph Integration , in: The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024 . URL: https://openreview.net/forum?id=haVPmN8UGi.