Unifying approach to uniform expressivity of graph neural networks

Huan Luo; Jonni Virtema

cs.LGFeb 20, 2026

Unifying approach to uniform expressivity of graph neural networks

Authors: Huan Luo, Jonni Virtema

Organizations: School of Computer Science, University of Sheffield, UK · School of Computing Science, University of Glasgow, UK

Abstract

The expressive power of Graph Neural Networks (GNNs) is often analysed via correspondence to the Weisfeiler-Leman (WL) algorithm and fragments of first-order logic. Standard GNNs are limited to performing aggregation over immediate neighbourhoods or over global read-outs. To increase their expressivity, recent attempts have been made to incorporate substructural information (e.g. cycle counts and subgraph properties). In this paper, we formalize this architectural trend by introducing Template GNNs (T-GNNs), a generalized framework where node features are updated by aggregating over valid template embeddings from a specified set of graph templates. We propose a corresponding logic, Graded template modal logic (GML(T)), and generalized notions of template-based bisimulation and WL algorithm. We establish an equivalence between the expressive power of T-GNNs and GML(T), and provide a unifying approach for analysing GNN expressivity: we show how standard AC-GNNs and its recent variants can be interpreted as instantiations of T-GNNs.

Figures & tables

Panel of Figure 1 — Figure 1: Templates $T_{1}$ and $T_{2}$ used to capture AC-GNNs and AC+-GNNs. The solid arrow represents an element of $E^{+}$ , while the dashed arrow represents an element of $E^{-}$ .

Panel of Figure 2 — Figure 2: Top: $2$ -hop subgraph WL extracts subgraphs rooted at node $v$ . Bottom: $\mathcal{T}$ -WL arrives at the same colouring by matching node $v$ against $\mathcal{T}=\{T_{\vartriangle},T_{p}\}$ .

Explore similar work

Structural Preservation and the Logical Expressiveness of Graph Neural Networks
Jun 16, 2026Przemysław Andrzej Wałęga, Bernardo Cuenca GrauGNN Expressivity
Queen Mary University of London · University of Oxford
Towards Understanding the Expressive Power of GNNs with Global Readout
Apr 23, 2026Maurice Funk, Daumantas KojelisGraph Neural Networks GNN Expressivity
Leipzig University, Germany
The Logical Expressiveness of Topological Neural Networks
Apr 21, 2026Amirreza Akbari, Amauri H. Souza, Vikas GargGraph Neural Networks GNN Expressivity
Aalto University · Federal Institute of Cear´a, 2δ AI · YaiYai Ltd

Jun 16, 2026J/K move · Enter open · S save

Structural Preservation and the Logical Expressiveness of Graph Neural Networks

Przemysław Andrzej Wałęga, Bernardo Cuenca Grau

Queen Mary University of London · University of Oxford

GNN Expressivity

Open paper AskPDF arXiv

Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activation functions. These choices define restricted classes of GNNs for which tight correspondences with logical formalisms can be obtained, by showing that logical formulae can be translated into equivalent GNNs and, conversely, that GNNs can be translated into equivalent formulae. In this paper we take a semantic perspective by establishing the logical expressiveness of classes of GNN classifiers that are preserved under structural properties: embeddings (extensions), injective homomorphisms, and homomorphisms. We show that, for each such property, there exists a fragment of graded modal logic characterising the class of GNNs. In particular, preservation under embeddings, injective homomorphisms, and homomorphisms corresponds to existential graded modal logic, its existential-positive fragment, and existential-positive modal logic, respectively. These results characterise the expressiveness of broad classes of GNNs independently of specific architectural choices, but we also show that each of these classes admits a GNN architecture of the same expressiveness. Technically, our approach uses a new well-quasi-order result for trees of bounded height, yielding finite representations of unravelling-invariant classes.

Abstract

Explore similar work

Structural Preservation and the Logical Expressiveness of Graph Neural Networks

Towards Understanding the Expressive Power of GNNs with Global Readout

The Logical Expressiveness of Topological Neural Networks