Unifying Approach to Uniform Expressivity of Graph Neural Networks

Paper: 2602.18409 Authors: Huan Luo, Jonni Virtema Categories: cs.LG, cs.AI, cs.LO

Abstract

This paper addresses a fundamental question in graph neural network theory: how to systematically understand and compare the expressive power of different GNN architectures. The authors introduce Template GNNs (T-GNNs), a generalized framework that formalizes the recent architectural trend of incorporating substructural information into GNNs. In T-GNNs, node features are updated by aggregating over valid template embeddings from a specified set of graph templates. The paper establishes a formal correspondence between T-GNNs and a newly proposed logic called Graded Template Modal Logic (GML(T)), along with generalized notions of template-based bisimulation and Weisfeiler-Leman algorithm. This unifying framework demonstrates that standard AC-GNNs and their recent variants can be interpreted as specific instantiations of T-GNNs, providing a principled approach to analyzing GNN expressivity.

Key Contributions

• Introduction of Template GNNs (T-GNNs), a generalized architectural framework that captures GNNs performing aggregation over arbitrary graph templates
• Proposal of Graded Template Modal Logic (GML(T)) as the logical counterpart to T-GNNs
• Establishment of formal equivalence between the expressive power of T-GNNs and GML(T)
• Generalization of template-based bisimulation and Weisfeiler-Leman algorithm to the template setting
• Demonstration that standard AC-GNNs and recent variants (subgraph GNNs, cycle-counting GNNs) are instantiations of the T-GNN framework

Theoretical Framework

The T-GNN framework operates on a simple yet powerful principle: instead of aggregating only over immediate neighbors or global structures, nodes aggregate information over all valid embeddings of predefined graph templates. Given a set of templates $\mathcal{T}$, a T-GNN updates node features by:

$h_v^{(k+1)} = \text{COMBINE}\left(h_v^{(k)}, \text{AGGREGATE}\left(\{h_{\phi}^{(k)} : \phi \in \text{Emb}(G, \mathcal{T}, v)\}\right)\right)$

where $\text{Emb}(G, \mathcal{T}, v)$ denotes all valid template embeddings that include node $v$. This formulation naturally generalizes standard message-passing GNNs (where templates are single edges) and recent substructure-aware architectures.

The corresponding logic GML(T) extends modal logic with graded modalities indexed by templates. A formula $\langle T \rangle_{\geq k} \phi$ expresses that there exist at least $k$ embeddings of template $T$ satisfying property $\phi$. This grading mechanism captures the counting capabilities inherent in GNN aggregation functions.

Expressivity Analysis and Equivalence Results

The paper’s central theoretical result establishes a tight correspondence between T-GNNs and GML(T). Specifically, two graphs are indistinguishable by T-GNNs if and only if they satisfy the same GML(T) formulas. This equivalence is proven through:

1. Template-based bisimulation: A generalization of standard bisimulation that respects template embeddings, providing a game-theoretic characterization of GML(T) equivalence
2. Template Weisfeiler-Leman algorithm: An extension of the classical WL test that refines node colors based on template embedding patterns
3. Three-way equivalence: Demonstrating that T-GNN indistinguishability, GML(T) equivalence, and template-WL equivalence all coincide

This result provides a powerful tool for analyzing GNN expressivity: to understand what a particular GNN architecture can distinguish, one can equivalently study the corresponding logic or algorithmic test. The framework also reveals fundamental limitations—T-GNNs with finite template sets cannot distinguish graphs that differ only in properties requiring unbounded template sizes.

Unifying Existing Architectures

A key insight of the paper is showing how diverse GNN architectures fit within the T-GNN framework:

• Standard MPNNs: Instantiated with single-edge templates
• Subgraph GNNs: Use templates corresponding to specific subgraph patterns (triangles, cliques, etc.)
• Cycle-counting GNNs: Employ cycle templates of various lengths
• Higher-order GNNs: Captured by templates representing k-tuples of nodes

This unification reveals that many seemingly different architectural innovations are actually exploring different regions of the same design space—the choice of template set $\mathcal{T}$. The framework thus provides a systematic way to compare architectures and understand their relative expressivity based on their template sets.

Takeaways

1. Template GNNs provide a unifying mathematical framework for understanding modern GNN architectures that incorporate substructural information
2. The equivalence between T-GNNs, GML(T), and template-WL algorithms offers multiple perspectives for analyzing expressivity
3. Many recent GNN variants can be understood as instantiations of T-GNNs with different template choices
4. The framework reveals fundamental trade-offs: richer template sets increase expressivity but also computational complexity
5. This theoretical foundation enables principled design of new GNN architectures by selecting appropriate template sets for specific tasks