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
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 γRGNN over Nmax (log-scale, x) as task complexity proxy and width mmin (y) at fixed sparsity ρ=0.70 . Black iso-curves show efficiency =γRGNN/(MADDs⋅10−6) . (b) γRGNN versus smin (x) and mmin (y) at ρ=0.70 ; contours at γRGNN=0.99 and 10−9 illustrate that increasing smin expands the high- γRGNN region, reducing the width needed to hit the target. (c) MADDs cost landscape over (ρ,mmin) with γRGNN=0.99 and 10−9 frontiers overlaid, showing that achieving γRGNN≈1 typically requires either lower pruning (smaller ρ ) or larger width. (d) γRGNN=0.99 frontiers in the (ρ,mmin) plane for multiple Nmax (color) and branch counts B=∣B∣ (line style): larger Nmax or B shifts the frontier toward denser or wider regimes. Unless varied per panel: L=5 , B=4 (varied only in d), M=2 , smin=2 , and Nmax=1000 .
Figure 2: (a) γempirical (green) vs. mean γRGNN (red) for randomly sparsely initialized untrained simple RGNNs on Dsyn . Orange segments visualize Δγ=γempirical−γ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 ρ , we average results across trials and compute Spearman’s ρsm and its p -value; points plot (ρsm,−log10p) , with the dashed lines indicating p=0.05 and ρsm=0 .
Figure 3: Spearman correlation between the fraction of separable graphs before training and post-training metrics under fixed sparsity (simple RGNN, Dsyn ). For each ρ , we compute Spearman’s ρ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 (ρsm,−log10p) , dashed lines indicate ρsm=0 and p=0.05 .
Figure 4: Tightness of γRGNN as model and dataset characteristics vary. Each panel reports the absolute area between γempirical and mean γ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 ∣Dsyn∣ , (c) number of nodes per graph n , (d) number of message-passing layers L , and (e) number of relations ∣R∣ . For each ρ , γempirical is estimated from 10 pruning-mask trials, while γRGNN is instantiated using model-specific statistics and averaged over 10 sparse-mask samples. Unless varied per panel: m=16 , ∣Dsyn∣=30 , 6 nodes per graph, L=3 , and ∣R∣=3 .
Figure 5: (a) For each model–dataset variant, we compute Spearman’s ρ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 (ρsm,−log10p) (log- y ), with colors encoding the variable pair and markers the model–dataset group; dashed lines indicate ρsm=0 and p=0.05 . (b) P(WT∣Sep.) for pruned runs, shown per model–dataset variant over separability bins (midpoints on x ).
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.
Huan Luo, Jonni Virtema
School of Computer Science, University of Sheffield, UK · School of Computing Science, University of Glasgow, UK
A landmark result states that the expressive power of graph neural networks (GNNs) is bounded from above by the 1-dimensional Weisfeiler-Leman (1-WL) test. We ask whether a constant-depth GNN can match the expressive power of 1-WL while using only rational weights. We prove that this is the case when Schanuel's conjecture, a famous open problem from transcendental number theory, is taken to be true. Our GNN construction works even with integer weights, and more generally with a broad range of rational weights. As the activation function, it may use logistic sigmoid, hyperbolic tangent, or related functions. It is uniform across all graph sizes. We also prove a partial converse: if a GNN with exponentiation, hyperbolic sine or hyperbolic cosine as activation matches the expressive power of the 1-WL test in a slightly more expressive setting where graphs may contain certain auxiliary vertices, then this implies Schanuel's conjecture restricted to the numbers that arise in computations of the GNN. We also conduct experiments showing that the constructed GNNs indeed match the 1-WL test.
Daumantas Kojelis, Carsten Lutz
Institute of Computer Science, Leipzig University, Leipzig, Germany · Institute of Computer Science, Leipzig University and ScaDS.AI Dresden/Leipzig, Leipzig, Germany
Recurrent Graph Neural Networks (RGNNs) extend standard GNNs by iterating message-passing until some stopping condition is met. Various RGNN models have been proposed in the literature. In this paper, we study three such models: converging RGNNs, where all vertex representations must stabilise; output-converging RGNNs, where only the output classifications must stabilise; and halting RGNNs, where a per-vertex halting classifier determines when to stop. We establish expressiveness relationships between these models: over undirected graphs, converging RGNNs are equally expressive as graded-bisimulation-invariant halting RGNNs, while output-converging RGNNs are at least as expressive. Combined with prior results on halting RGNNs, this shows that, relative to the classifiers expressible in monadic second-order logic (MSO), converging RGNNs express exactly the graded modal μ-calculus (μGML), and output-converging RGNNs express at least μGML. These results hold even when restricting to ReLU networks with sum aggregation. The main technical challenge is simulating halting RGNNs by converging ones: without a global halting classifier, vertices may locally decide to halt at different times, causing desynchronisation. We develop a "traffic-light" protocol that enables vertices to coordinate despite this asynchrony. Our results answer an open question from Bollen et al. (2025) and show that the RGNN model of Pflueger et al. (2024) retains full μGML expressiveness even when convergence is guaranteed.