[Paper] Bayesian Networks, Markov Networks, Moralisation, Triangulation: a Categorical Perspective

Source: arXiv - 2512.09908v1

Overview

The paper “Bayesian Networks, Markov Networks, Moralisation, Triangulation: a Categorical Perspective” re‑imagines two classic transformations in probabilistic graphical models—moralisation (turning a directed Bayesian network into an undirected Markov network) and triangulation (the reverse direction)—through the lens of category theory. By treating networks themselves as functors, the authors expose a clean separation between syntactic rewrites (purely structural) and semantic operations (involving the underlying probability distributions). This abstraction not only clarifies long‑standing algorithmic steps such as variable elimination but also opens a path toward more modular, compositional software for probabilistic reasoning.

Key Contributions

• Functorial representation of graphical models: Bayesian and Markov networks are modeled as functors from a “syntax” category (graph structure) to a “semantics” category (probability spaces).
• Categorical formulation of moralisation and triangulation: Both transformations become functor pre‑composition, with moralisation staying entirely syntactic and triangulation requiring semantic information.
• Decomposition of variable elimination: The classic elimination algorithm is split into two independent functors—one handling the syntactic triangulation step, the other handling the semantic factor‑combination step.
• Clear distinction between syntactic vs. semantic modifications: The framework makes explicit which parts of a transformation affect only the graph and which affect the underlying probability distribution.
• Foundational groundwork for compositional probabilistic programming: By casting model transformations as categorical morphisms, the work suggests a modular way to build and manipulate probabilistic programs.

Methodology

1. Define a syntax category whose objects are graph‑like structures (nodes, directed edges for Bayesian nets, undirected edges for Markov nets) and whose morphisms capture graph rewrites.
2. Define a semantics category whose objects are probability spaces and whose morphisms are measurable maps (e.g., marginalisation, conditioning).
3. Model a concrete network as a functor F : Syntax → Semantics that assigns to each syntactic component the corresponding probabilistic factor.
4. Moralisation is expressed as pre‑composing a Bayesian‑net functor with a moralisation functor on the syntax side; no probability calculations are needed.
5. Triangulation is expressed as pre‑composing a Markov‑net functor with a triangulation functor that depends on the semantics (e.g., the order of variable elimination).
6. Variable elimination is recast as a composition of two functors:
   • a syntactic triangulation functor that adds fill‑in edges to make the graph chordal, and
   • a semantic elimination functor that multiplies and marginalises the associated factors.

All constructions are proved to be functorial, guaranteeing that chaining transformations respects composition and identity.

Results & Findings

• Moralisation is purely syntactic: Converting a Bayesian network to a Markov network never touches the underlying probability tables; it is a graph‑only rewrite.
• Triangulation mixes syntax and semantics: While the graph structure (adding fill‑in edges) can be described syntactically, the choice of which edges to add depends on the elimination order, which is driven by the distribution’s factor sizes—a semantic concern.
• Variable elimination splits cleanly: By separating the two functors, the paper demonstrates that the expensive part of inference (computing new factors) can be isolated from the cheaper graph‑structural part (making the graph chordal).
• Functoriality guarantees composability: Any pipeline that chains moralisation, triangulation, and elimination behaves predictably, enabling modular reasoning about complex inference pipelines.

Practical Implications

• Modular inference libraries: Developers can implement the syntactic part (graph transformations) once and reuse it across different probabilistic back‑ends, swapping in custom semantics (e.g., discrete, continuous, or hybrid distributions) without touching the graph code.
• Optimised compilation for probabilistic programming languages (PPLs): Compilers can treat moralisation as a compile‑time rewrite, while triangulation can be deferred to a runtime optimisation pass that has access to factor size statistics, leading to better memory and speed trade‑offs.
• Explainable AI tooling: Because the categorical view separates “what the model looks like” from “what the numbers mean,” debugging tools can visualise purely syntactic changes (e.g., added fill‑in edges) independently from numerical issues (e.g., overflow during factor multiplication).
• Education and documentation: The functorial perspective offers a high‑level, language‑agnostic way to teach graphical model transformations, making it easier for new engineers to grasp why certain steps (like moralisation) are cheap and others (like triangulation) are costly.
• Potential for automated reasoning about model equivalence: Since transformations are morphisms, automated theorem provers could verify that two different pipelines produce the same underlying distribution, aiding model versioning and reproducibility.

Limitations & Future Work

• Abstractness vs. implementation: The categorical formalism, while elegant, may be non‑trivial to translate into performant code without additional engineering layers.
• Scalability of semantic triangulation: The semantic component still relies on heuristics (e.g., min‑fill, min‑weight) that can be expensive for very large models; the paper does not provide new heuristics.
• Restricted to exact inference: The framework focuses on exact variable elimination; extending it to approximate methods (e.g., loopy belief propagation, variational inference) remains an open challenge.
• Empirical validation: The authors present theoretical proofs but limited experimental benchmarks; future work could quantify runtime gains when separating syntactic and semantic steps in real‑world PPLs.

Overall, the paper offers a fresh, mathematically rigorous way to think about classic graphical‑model transformations, paving the way for more compositional and maintainable probabilistic software.

Authors

• Antonio Lorenzin
• Fabio Zanasi

Paper Information

• arXiv ID: 2512.09908v1
• Categories: cs.AI, cs.LO, math.CT
• Published: December 10, 2025
• PDF: Download PDF