A Unifying Relational Perspective on Expressive Lottery Tickets

Lorenz Kummer; Samir Moustafa; Anatol Ehrlich; Franka Bause; Marco Nennstiel; Przemysław Andrzej Wałȩga; Nils Morten Kriege

cs.LGAug 19, 2026

A Unifying Relational Perspective on Expressive Lottery Tickets

Authors: Lorenz Kummer, Samir Moustafa, Anatol Ehrlich, Franka Bause, Marco Nennstiel, Przemysław Andrzej Wałȩga, Nils Morten Kriege

Organizations: Faculty of Computer Science, University of Vienna, Vienna, Austria · Doctoral School Computer Science, University of Vienna, Vienna, Austria · CeMM Research Center for Molecular Medicine of the Austrian Academy of Sciences, Vienna, Austria · CISPA Helmholtz Center for Information Security, Saarbrücken, Germany · School of Electronic Engineering and Computer Science, Queen Mary University of London, UK · Research Network Data Science, University of Vienna, Vienna, Austria

Abstract

Graph neural networks (GNNs) are widely used, but how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants is poorly understood. The Strong Expressive Lottery Ticket Hypothesis (SELTH) posits the existence of sparse GNNs that preserve Weisfeiler-Leman (WL) expressivity on static graphs. We generalize this existence result to a probabilistic statement for multi-relational and temporal domains via the relational WL (RWL). We prove that sufficiently parameterized RGNNs contain sparse subnetworks that maintain 1-RWL expressivity and derive a lower bound on the probability that a random pruning yields such a subnetwork. We show that common TGNNs and cross-graph message passing schemes admit RGNN reformulations such that they inherit these guarantees and, moreover, that the expressivity of a sparse RGNN is connected to its optimization behavior under common update regimes. Experiments instantiate the bound, compare it to empirical probabilities on synthetic data, and study how pre-training expressivity relates to optimization and prediction quality metrics on temporal and molecular benchmarks.

Figures & tables

Figure 1: (a) Landscape of $\gamma_{\mathrm{RGNN}}$ over $N_{\max}$ (log-scale, x) as task complexity proxy and width $m_{\min}$ (y) at fixed sparsity $\rho=0.70$ . Black iso-curves show efficiency $=\gamma_{\mathrm{RGNN}}/(\text{MADDs}\cdot 10^{-6})$ . (b) $\gamma_{\mathrm{RGNN}}$ versus $s_{\min}$ (x) and $m_{\min}$ (y) at $\rho=0.70$ ; contours at $\gamma_{\mathrm{RGNN}}=0.99$ and $10^{-9}$ illustrate that increasing $s_{\min}$ expands the high- $\gamma_{\mathrm{RGNN}}$ region, reducing the width needed to hit the target. (c) MADDs cost landscape over $(\rho,m_{\min})$ with $\gamma_{\mathrm{RGNN}}=0.99$ and $10^{-9}$ frontiers overlaid, showing that achieving $\gamma_{\mathrm{RGNN}}\approx 1$ typically requires either lower pruning (smaller $\rho$ ) or larger width. (d) $\gamma_{\mathrm{RGNN}}=0.99$ frontiers in the $(\rho,m_{\min})$ plane for multiple $N_{\max}$ (color) and branch counts $B=|\mathcal{B}|$ (line style): larger $N_{\max}$ or $B$ shifts the frontier toward denser or wider regimes. Unless varied per panel: $L=5$ , $B=4$ (varied only in d), $M=2$ , $s_{\min}=2$ , and $N_{max}=1000$ .

Figure 2: (a)

\gamma_{\mathrm{empirical}}

(green) vs. mean

\overline{\gamma}_{\mathrm{RGNN}}

(red) for randomly sparsely initialized untrained simple RGNNs on

\mathcal{D}_{syn}

. Orange segments visualize

\Delta_{\gamma}=\gamma_{\mathrm{empirical}}-\overline{\gamma}_{\mathrm{RGNN}}

. (b) Spearman correlation between the fraction of separable graphs before training and (i) mean gradient flow, (ii) final training loss, and (iii) final training accuracy. For

\rho

, we average results across trials and compute Spearman’s

\rho_{sm}

and its

p

-value; points plot

(\rho_{sm},\,-\log_{10}p)

, with the dashed lines indicating

p=0.05

and

\rho_{sm}=0

Figure 3: Spearman correlation between the fraction of separable graphs before training and post-training metrics under fixed sparsity (simple RGNN,

\mathcal{D}_{\mathrm{syn}}

). For each

\rho

, we compute Spearman’s

\rho_{sm}

(and

p

-value) across masks between pre-training separability and (i) mean gradient flow, (ii) final training loss, and (iii) final training accuracy. Points plot

(\rho_{sm},-\log_{10}p)

, dashed lines indicate

\rho_{sm}=0

and

p=0.05

Figure 4: Tightness of

\gamma_{\mathrm{RGNN}}

as model and dataset characteristics vary. Each panel reports the absolute area between

\gamma_{\mathrm{empirical}}

and mean

\overline{\gamma}_{\mathrm{RGNN}}

over a sparsity sweep, compare Figure 2 (a), so smaller area indicates a tighter bound. Panels vary (a) width

m

, (b) number of graphs

|\mathcal{D}_{\mathrm{syn}}|

, (c) number of nodes per graph

n

, (d) number of message-passing layers

L

, and (e) number of relations

|\mathcal{R}|

. For each

\rho

\gamma_{\mathrm{empirical}}

is estimated from 10 pruning-mask trials, while

\gamma_{\mathrm{RGNN}}

is instantiated using model-specific statistics and averaged over 10 sparse-mask samples. Unless varied per panel:

m=16

|\mathcal{D}_{\mathrm{syn}}|=30

6

nodes per graph,

L=3

, and

|\mathcal{R}|=3

Figure 5: (a) For each model–dataset variant, we compute Spearman’s

\rho_{sm}

(and

p

-value) across runs between (i) separability (Sep.) and normalized test performance (Perf.), (ii) Sep. and compression (Compr.), and (iii) Perf. and Compr.; points plot

(\rho_{sm},\,-\log_{10}p)

(log-

y

), with colors encoding the variable pair and markers the model–dataset group; dashed lines indicate

\rho_{sm}=0

and

p=0.05

. (b)

P(\mathrm{WT}\mid\mathrm{Sep.})

for pruned runs, shown per model–dataset variant over separability bins (midpoints on

x

Explore similar work

Unifying approach to uniform expressivity of graph neural networks
Feb 20, 2026Huan Luo, Jonni VirtemaGraph Neural Networks GNN Expressivity
School of Computer Science, University of Sheffield, UK · School of Computing Science, University of Glasgow, UK
Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture
Oct 12, 2026Daumantas Kojelis, Carsten LutzGraph Neural Networks GNN Expressivity
Institute of Computer Science, Leipzig University, Leipzig, Germany · Institute of Computer Science, Leipzig University and ScaDS.AI Dresden/Leipzig, Leipzig, Germany
On Halting vs Converging in Recurrent Graph Neural Networks
Apr 28, 2026Jeroen Bollen, Stijn VansummerenGraph Neural Networks GNN Expressivity
Hasselt University

Feb 20, 2026J/K move · Enter open · S save

Unifying approach to uniform expressivity of graph neural networks

Huan Luo, Jonni Virtema

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

Graph Neural Networks GNN Expressivity

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Unifying approach to uniform expressivity of graph neural networks

Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture

On Halting vs Converging in Recurrent Graph Neural Networks