🤖 AI

Structural Preservation and the Logical Expressiveness of Graph Neural Networks

This paper establishes a semantic characterization of the logical expressiveness of broad classes of Graph Neural Networks by demonstrating that preservation under embeddings, injective homomorphisms, and homomorphisms corresponds respectively to existential graded modal logic, its existential-positive fragment, and existential-positive modal logic, while proving that each class admits a GNN architecture with equivalent expressiveness.

Original authors: Przemysław Andrzej Wałęga, Bernardo Cuenca Grau

Published 2026-06-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Przemysław Andrzej Wałęga, Bernardo Cuenca Grau

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

Imagine you have a team of detectives (Graph Neural Networks, or GNNs) trying to solve mysteries on a map of connected cities (graphs). Each detective stands on a city and gathers clues from their immediate neighbors to decide if that city is "guilty" or "innocent."

For a long time, scientists have tried to understand exactly how smart these detectives are and what kinds of clues they can actually use. This paper acts like a translator, converting the detective's "math language" into "logic language" to see exactly what they can and cannot do.

Here is the core idea, broken down into simple concepts:

1. The Detective's "Local" Vision

The paper starts with a simple rule: These detectives are local. If a detective has been working for 5 days (5 layers of the network), they only know about the cities within a 5-mile radius. They don't know about the whole world, just their neighborhood.

Because they only look at their neighborhood, their view of the world is like a tree that grows out from their starting point. If the real map has loops (like a roundabout), the detective's "mental map" unfolds those loops into a straight tree so they can process it.

2. The Three Rules of "Robustness"

The authors ask: "What happens if we change the map slightly? Does the detective still give the same verdict?" They test three specific ways of changing the map:

The "Copy-Paste" Rule (Embeddings): Imagine you take a small neighborhood and paste it perfectly into a bigger city. If the detective says "Guilty" in the small neighborhood, they should still say "Guilty" in the bigger city.
- The Logic: This corresponds to Existential Graded Modal Logic. It's like saying, "I can find at least 3 neighbors who are guilty." It allows for specific counts and checking for the absence of things (e.g., "No one here is wearing a red hat").
The "Stretching" Rule (Injective Homomorphisms): Imagine you take the neighborhood and stretch it out. You might add new, empty streets or change a "Red Hat" to a "Red Hat + Blue Scarf," but you never merge two people into one. The structure stays distinct.
- The Logic: This corresponds to Existential-Positive Graded Modal Logic. This is stricter. The detective can only say "I see at least 3 guilty neighbors." They cannot say "I see no guilty neighbors" (because adding more people might accidentally create a guilty neighbor). They can only look for things that are there, not things that aren't.
The "Merging" Rule (Homomorphisms): This is the most extreme change. Imagine you squish the map. You might merge two different neighbors into a single person, or turn a "Red Hat" into a "Blue Hat."
- The Logic: This corresponds to Existential-Positive Modal Logic. This is the simplest logic. The detective can only say, "I see at least one guilty neighbor." They lose the ability to count (because merging people changes the count) and they lose the ability to check for specific numbers. They just know "something is there."

3. The "Tree" Trick (The Technical Magic)

How did the authors prove this? They realized that because the detectives only look at a limited distance, their "mental maps" are always trees of a certain height.

They used a mathematical tool called a Well-Quasi-Order. Think of this like a "Lego set" rule. If you have an infinite number of Lego trees, but they are all limited to a certain height, you can prove that you don't need an infinite number of rules to describe them. You only need a finite list of the "smallest" or "simplest" trees. If a detective can spot one of these simple trees, they can spot any bigger tree that contains it.

This allowed the authors to say: "Because the detective's view is a finite tree, we can write a finite logical sentence that perfectly describes exactly what that detective can see."

4. The Architectural Match

The paper doesn't just say "Logic works." It also says, "We can build the detective to match the logic."

If you want a detective who follows the "Copy-Paste" rule, you build a network that can do math with negative numbers (to check for absences) and count exactly.
If you want a detective who follows the "Stretching" rule, you build a network that only adds things up (monotonic) and never subtracts.
If you want a detective who follows the "Merging" rule, you build a network that only looks at the maximum value (ignoring how many neighbors there are) and never subtracts.

The Big Takeaway

There is a trade-off.

The more flexible you make the detective (allowing them to handle complex changes like merging or stretching), the simpler their logic becomes. They lose the ability to count or check for negatives.
The more rigid you make the detective (only allowing perfect copies), the smarter they can be, but they are less robust to changes in the map.

In short, the paper draws a perfect line in the sand: If you want your AI to be robust against a specific type of change, you are mathematically limited to a specific type of logical reasoning. You can't have a detective that is both super-flexible (handles merging) and super-detailed (counts exactly and checks for negatives) at the same time.

Technical Summary: Structural Preservation and the Logical Expressiveness of Graph Neural Networks

1. Problem Statement

While connections between Graph Neural Networks (GNNs) and logical formalisms have been established, prior work largely relies on fixing specific architectural choices (e.g., aggregation, combination, and activation functions) to define restricted classes of GNNs. These architecture-driven characterizations link specific GNN variants to extensions of first-order logic (e.g., with counting terms or Presburger quantifiers) or rule-based formalisms like Datalog.

This paper addresses the need for a semantic framework that characterizes the logical expressiveness of GNN classes based on structural preservation properties rather than specific syntactic constraints. Specifically, the authors investigate GNN classifiers that are preserved under three distinct structural relations:

Embeddings (extensions).
Injective homomorphisms.
Homomorphisms.

The core challenge is to determine which fragments of logic correspond to these preservation properties and to provide finite representations for the classes of graphs they define, despite the infinite nature of graph structures.

2. Methodology

The authors adopt a semantic perspective inspired by finite model theory, adapting preservation theorems (such as van Benthem–Rosen and Rossman's theorems) to the setting of GNNs. The methodology proceeds through three main stages:

A. Locality and Unravelling

Leveraging the inherent locality of GNNs (where an $L$ -layer GNN's output depends only on the $L$ -hop neighborhood), the authors utilize the concept of $L$ -unravelling. This transforms a pointed graph $(G, v)$ into a rooted tree of height at most $L$ . A key property established is that GNN classifiers are invariant under this transformation: $N(G, v) = N(\text{Unr}_L(G, v))$ . This allows the analysis of GNNs to be reduced to the analysis of tree structures.

B. Well-Quasi-Ordering (WQO) Results

To handle the infinite set of possible graphs, the paper introduces a new combinatorial result regarding well-quasi-orders (WQO).

Theorem 4: The embedding relation on any class of rooted trees with heights uniformly bounded by a fixed constant is a well-quasi-order.
Corollary 5: This result extends to injective homomorphisms and homomorphisms on bounded-height trees.
Significance: Since WQOs admit only finitely many minimal elements, any class of trees invariant under unravelling and preserved under these structural relations can be represented by a finite set of minimal trees. This finiteness is crucial for establishing logical definability.

C. Preservation Theorems

Combining unravelling invariance with the WQO results, the authors prove preservation theorems linking structural properties to logical definability in fragments of Graded Modal Logic (GML):

Classes preserved under embeddings correspond to Existential Graded Modal Logic ( $\exists$ GML).
Classes preserved under injective homomorphisms correspond to Existential-Positive Graded Modal Logic ( $\exists^+$ GML).
Classes preserved under homomorphisms correspond to Existential-Positive Modal Logic ( $\exists^+$ ML).

D. Syntactic Characterization

The paper complements these semantic results by identifying specific GNN architectures that realize these expressiveness classes. The authors define:

Monotonic GNNs (MGNNs): GNNs with non-decreasing aggregation and combination functions.
MAX-MGNNs: MGNNs using MAX as the aggregation function.
Augmented MGNNs: MGNNs preceded by a pointwise feature transformation layer.

3. Key Contributions and Results

Logical Characterizations

The paper establishes tight correspondences between preservation properties and logical fragments (Theorem 7, Corollary 8):

Embeddings $\iff$ $\exists$ GML: GNNs preserved under embeddings have the same expressiveness as $\exists$ GML.
Injective Homomorphisms $\iff$ $\exists^+$ GML: GNNs preserved under injective homomorphisms correspond to $\exists^+$ GML.
Homomorphisms $\iff$ $\exists^+$ ML: GNNs preserved under homomorphisms correspond to $\exists^+$ ML.

Architectural Realizations

The authors demonstrate that these semantic classes can be captured by specific architectural constraints (Theorem 16):

Augmented MGNNs are equivalent in expressiveness to $\exists$ GML.
MGNNs are equivalent to $\exists^+$ GML.
MAX-MGNNs are equivalent to $\exists^+$ ML.
Augmented MAX-MGNNs are equivalent to $\exists$ ML.

Positive-Weight GNNs

A significant finding concerns positive-weight GNNs (where parameter matrices have non-negative entries). The paper shows that any GNN preserved under injective homomorphisms (including all monotonic GNNs) can be transformed into an equivalent positive-weight GNN. This implies that the syntactic restriction to non-negative weights is not restrictive regarding expressiveness within this class.

Expressiveness Trade-offs

The results reveal a fundamental trade-off:

Stronger preservation properties (e.g., homomorphisms) lead to simpler logical characterizations (e.g., $\exists^+$ ML) but reduced expressive power.
Weaker preservation properties (e.g., embeddings) allow for richer logical fragments (e.g., $\exists$ GML) capable of expressing non-monotone properties (like "node $v$ does not have label $A$ ") but are less robust to structural transformations.
Specifically, MAX-MGNNs cannot express threshold-based conditions (e.g., "at least $k$ neighbors") because MAX aggregation is insensitive to multiplicities, whereas MGNNs can express such conditions but cannot handle non-injective homomorphisms that merge nodes.

4. Significance and Scope

The paper claims to provide a semantic framework for analyzing GNN expressiveness that is independent of specific architectural choices, yet capable of identifying architectures that achieve these bounds. By establishing exact correspondences between structural preservation, logical fragments, and GNN architectures, the work offers principled tools for:

Analyzing the expressiveness of GNNs.
Enabling symbolic methods for verification and explanation.
Understanding the limitations of monotonic and positive-weight GNNs.

The authors note limitations: the framework focuses on node classification (not graph-level prediction), assumes local neighborhood behavior (ignoring global reasoning mechanisms), restricts to threshold-based classifiers, and assumes discrete node labels. Furthermore, the correspondence captures the locality-bounded behavior of GNNs and does not account for properties beyond the bounded unravelling regime.

The technical contribution of the new WQO result for bounded-height trees is highlighted as being of independent interest to the study of well-quasi-orders, distinct from its application to GNNs.