💻 computer science

Causal Graph Dynamics and Kan Extensions

This paper demonstrates that Causal Graph Dynamics, which describe synchronous and deterministic transformations of port graphs, can be rigorously captured within the Global Transformations formalism by expressing them as Kan extensions, thereby revealing the universality of Monotonic Causal Graph Dynamics among general ones.

Original authors: Luidnel Maignan, Antoine Spicher

Published 2026-03-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Luidnel Maignan, Antoine Spicher

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Two Ways to Build a Universe

Imagine you are a god-like architect trying to build a universe where things change over time. You have two different toolkits to describe how this universe evolves:

The "Local Rule" Toolkit (Causal Graph Dynamics - CGD): This is like a game of Minecraft or a cellular automaton (like Conway's Game of Life). You have a giant grid of blocks (or nodes). Every single block looks at its immediate neighbors, follows a simple rule, and decides what to become in the next second. The whole world changes all at once (synchronously).
- The Catch: In this toolkit, the blocks have specific names (IDs). If you swap the names of two blocks, the rules might break or behave differently. It's very rigid about who is where.
The "Universal Blueprint" Toolkit (Global Transformations - GT): This is a more abstract, mathematical approach. It asks: "Can we describe any changing structure using a single, universal mathematical formula?" It uses a branch of math called Category Theory (specifically something called Kan Extensions) to say, "If I know what happens to a small piece, I can mathematically guarantee what happens to the whole."
- The Goal: To prove that the rigid "Local Rule" toolkit is actually just a special, simple version of the fancy "Universal Blueprint" toolkit.

The Problem: The "Missing Neighbor" Trap

The authors tried to fit the "Local Rule" toolkit (CGD) into the "Universal Blueprint" (GT). They thought it would be a perfect match. But they hit a snag.

The Analogy: The Party Guest
Imagine you are at a party (the graph).

Scenario A: You are standing alone in a corner. You decide to start dancing because you feel lonely.
Scenario B: You are standing next to a wall. You decide to start dancing because you feel lonely.

In the "Local Rule" world, these are two different situations. In Scenario A, you have no neighbor. In Scenario B, you have a wall as a neighbor. The rule might say: "If you have no neighbor, dance. If you have a wall, sit still."

The Conflict:
The "Universal Blueprint" (GT) works on a principle of Monotonicity (adding information shouldn't change the past).

If you know "You are alone," the blueprint says "Dance."
If you know "You are alone AND next to a wall," the blueprint sees this as more information. It expects the result to be a "superset" of the first result.
But in our party example, adding the wall changed the result from "Dance" to "Sit still." The result got smaller (or different), not bigger.

This is the Non-Monotonic problem. The "Local Rule" toolkit allows for rules that react to missing things (like "no neighbor"), which breaks the mathematical rules of the "Universal Blueprint."

The Solution: The "Magic Translator"

The authors realized they couldn't just force the two toolkits to match. Instead, they had to build a translator.

The Analogy: The "Fill-in-the-Blanks" Game
To make the "Local Rule" toolkit play nice with the "Universal Blueprint," they invented a new way of looking at the graph.

The Problem: In the original game, an empty space is just... empty. It's invisible.
The Fix: They decided that empty space must be visible.
- If a block is missing a neighbor, we don't leave it blank. We put a special "Ghost Neighbor" (a loopback edge) there.
- If a block has no label, we don't leave it blank. We put a special "Ghost Label" (like a star *) there.

Why this works:
Now, "Scenario A" (alone) and "Scenario B" (next to a wall) are no longer comparable in a confusing way.

In the new system, "Alone" means "You have a Ghost Neighbor."
"Next to a Wall" means "You have a Real Neighbor."
You can't say one is "more than" the other anymore because they have different types of neighbors. The confusion disappears!

By filling in all the "missing" parts with special "Ghost" markers, they turned the chaotic, non-monotonic rules into Monotonic rules. Now, the "Universal Blueprint" can finally understand the "Local Rule" toolkit.

The "Universal" Discovery

Here is the most surprising part of the paper:

The authors proved that every possible "Local Rule" system (even the messy, non-monotonic ones) can be translated into this new "Ghost-filled" system.

The Metaphor: Imagine you have a chaotic, unpredictable dance troupe. You think they are impossible to choreograph using a strict mathematical formula. But then you realize: if you just give every dancer a specific costume that represents their lack of a partner, you can write a strict formula that predicts their every move.
The Result: The "Monotonic" systems (the ones that fit the Universal Blueprint) are Universal. They are powerful enough to simulate any other system, provided you use the right translation (the encoding with Ghost Neighbors).

The Final Polish: Hiding the Names

Finally, the paper tackles one last issue: Names.
In the original "Local Rule" toolkit, blocks have names (IDs). In the "Universal Blueprint," names shouldn't matter; only the shape of the structure matters.

The authors used advanced math (Category Theory) to say: "Let's treat two graphs as the same if they just have different names but the same shape." They turned the list of graphs into a Category where "renaming" is just a type of movement. This allowed them to prove that the "Universal Blueprint" works perfectly even when we ignore the specific names of the blocks.

Summary in One Sentence

The authors proved that even the most chaotic, name-dependent, "missing-neighbor" reacting systems can be mathematically tamed and understood as a special case of a universal, name-independent mathematical formula, provided we first "fill in the blanks" with special ghost markers to make the rules consistent.

The Takeaway:

Old View: "Local rules" and "Global formulas" are different languages.
New View: "Local rules" are just "Global formulas" wearing a disguise. If you remove the disguise (by filling in the missing info), they are the same thing.

1. Problem Statement

The paper addresses the theoretical relationship between two frameworks for modeling dynamical systems on evolving spatial structures:

Causal Graph Dynamics (CGDs): Introduced in 2012, CGDs describe synchronous, local, and deterministic transformations of labeled port graphs where the graph structure itself evolves. They generalize Cellular Automata (CAs) to arbitrary graph topologies.
Global Transformations (GTs): Proposed in 2015, GTs use Category Theory (specifically Kan extensions) to define synchronous local transformations for any spatial structure.

The Core Question: Can CGDs be formally characterized as a specific instance of Global Transformations?

Initial Hypothesis: Since CGDs operate on port graphs (a specific type of spatial structure), they should naturally fit the GT framework. The authors initially expected a direct mapping where the CGD evolution function is simply the pointwise left Kan extension of its local rule.
The Obstacle: The authors discovered that this direct mapping only holds for a specific subclass of CGDs: Monotonic CGDs. General CGDs (which include non-monotonic behaviors like particle bouncing or label removal) do not fit the standard Kan extension definition based on the subgraph order. The paper aims to resolve this discrepancy and explain the precise sense in which CGDs are GTs.

2. Methodology

The authors employ a rigorous combination of Order Theory and Category Theory to analyze the structural properties of CGDs.

A. Order-Theoretic Analysis (Sections 1–2)

Subgraph Order: The authors define a partial order ( $\subseteq$ ) on graphs based on set inclusion of vertices, edges, and labels.
Kan Extension Formulation: They attempt to express the global CGD function $F$ $F$ as the pointwise left Kan extension of a local rule $f$ $f$ along a "pointer-dropping" functor $i$ $i$ .
- Formula: $F(G) = \sup \{ f(D) \mid i(D) \subseteq G \}$ .
The Monotonicity Issue: They prove that for this equation to hold, the local rule $f$ must be monotonic (if $D_1 \subseteq D_2$ , then $f(D_1) \subseteq f(D_2)$ ). However, many standard CGD examples (e.g., a particle bouncing off a wall) are non-monotonic. In these cases, a subgraph (e.g., a vertex with no right neighbor) might trigger a different behavior than a supergraph (a vertex with a right neighbor), violating the monotonicity required for a direct Kan extension.

B. Universality via Encoding (Section 3)

To bridge the gap between non-monotonic CGDs and the monotonic requirement of GTs, the authors propose an encoding strategy:

Idea: Transform any general CGD into a Monotonic CGD by encoding "missing" information explicitly.
Mechanism:
- Port Doubling: For every original port, add a "loopback" port to represent a missing edge.
- Label Extension: Add a special symbol (e.g., $\star$ ) to represent missing vertex labels.
- Total Graphs: The encoding $\omega(G)$ converts any partial graph into a "total" graph where every port and label is explicitly defined (either by its original value or the special "missing" symbol).
Result: In this encoded space, the distinction between "no neighbor" and "neighbor exists" becomes a structural difference in the graph itself, rather than an absence of information. This allows the construction of a monotonic local rule $f'$ that simulates the original non-monotonic rule $f$ .
Universality: They prove that Monotonic CGDs are universal among all CGDs. Any general CGD can be simulated by a monotonic one via this encoding.

C. Categorical Integration of Renaming-Invariance (Section 4)

CGDs possess renaming-invariance: the dynamics should not depend on the absolute names of vertices, only on the graph structure.

From Posets to Categories: The authors move from the poset of graphs (ordered by inclusion) to a Category of Graphs ( $\mathcal{G}_{\Sigma, \Delta, \pi}$ $G_{Σ, Δ, π}$ ).
- Objects: Graphs.
- Morphisms: Subgraph isomorphisms (renamings followed by inclusions).
Disk Category: They define a category of disks where morphisms account for renamings and center alignment.
Functorial Extension: They lift the CGD function $F$ and local rule $f$ to functors $\tilde{F}$ and $\tilde{f}$ .
Main Categorical Result: Under the assumption of unique conjugates (a condition regarding the symmetry of the dynamics), the functor $\tilde{F}$ is proven to be the pointwise left Kan extension of $\tilde{f}$ along the pointer-dropping functor $\tilde{i}$ .

3. Key Contributions

Characterization of Monotonicity: The paper identifies that the direct correspondence between CGDs and Kan extensions is restricted to Monotonic CGDs. It provides a formal proof that non-monotonic CGDs cannot be directly expressed as Kan extensions under the standard subgraph order.
Universality of Monotonic CGDs: The authors prove that the class of Monotonic CGDs is universal. They construct a specific encoding ( $\omega$ ) that transforms any general CGD into a monotonic one, preserving the dynamics ( $F' \circ \omega = \omega \circ F$ ). This implies that, in terms of computational power, restricting to monotonic dynamics is sufficient.
Categorical Formulation of Renaming-Invariance: The paper successfully integrates the renaming-invariance property of CGDs into the categorical framework. By treating graphs as objects in a category where isomorphisms (renamings) are morphisms, they show that CGDs are categorical Kan extensions.
Resolution of the "Missing Information" Problem: The paper clarifies how GTs handle "absence of information." In the categorical view, the "missing" edge or label is treated as a specific structural feature (via the encoding), ensuring the monotonicity required for the supremum (colimit) operation to work correctly.

4. Results

Theorem 1 (Monotonicity): A CGD is a pointwise left Kan extension (under the subgraph order) if and only if it is monotonic.
Theorem 2 (Universality): For every CGD $F$ , there exists a monotonic CGD $F'$ and an encoding $\omega$ such that $F'$ simulates $F$ .
Theorem 3 (Categorical Equivalence): Under the unique conjugate assumption, the functorial extension of a monotonic CGD is the pointwise left Kan extension of the local rule functor along the pointer-dropping functor in the category of graphs with renamings.

5. Significance

Unification of Frameworks: The paper successfully unifies the "local-to-global" approach of Causal Graph Dynamics with the abstract, category-theoretic approach of Global Transformations. It validates the claim that GTs can capture the behavior of CGDs, provided one accounts for monotonicity and renaming-invariance correctly.
Theoretical Insight: It reveals that the "non-monotonicity" often seen in graph dynamics is an artifact of how "missing information" is handled. By making missing information explicit (via the encoding), the dynamics become monotonic, aligning with the requirements of Kan extensions.
Foundation for Future Work: The categorical formulation provides a robust foundation for analyzing graph rewriting systems, site graphs, and other dynamical systems. It suggests that future models of computation on evolving spaces should consider "total" representations (explicitly marking missing parts) to leverage the power of category theory (colimits/Kan extensions) for global behavior derivation.
Practical Implications: The universality result implies that researchers can focus on designing monotonic rules (which are easier to analyze and compose) without losing expressive power, as any complex non-monotonic behavior can be simulated within this monotonic framework.

In summary, the paper demonstrates that while CGDs are not directly Kan extensions in their raw form, they are universally equivalent to monotonic CGDs, which are Kan extensions. This establishes a deep theoretical link between local graph rewriting and global categorical transformations.