arXiv CS open access

A Unifying Relational Perspective on Expressive Lottery Tickets

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

A Unifying Relational Perspective on Expressive Lottery Tickets

Lorenz Kummer 1 2 Samir Moustafa 1 2 3 Anatol Ehrlich 1 2 Franka Bause 4 Marco Nennstiel 1 Przemysław Andrzej Wał˛ega 5 Nils Morten Kriege 1 6

arXiv:2608.18819v1 [cs.LG] 19 Aug 2026

Abstract

or social networks are represented as graphs with featureenriched nodes and edges. They extend deep learning to domains including finance, social networks, medical data, and chem-/bioinformatics (Lu & Uddin, 2021; Cheung & Moura, 2020; Sun et al., 2021; Gao et al., 2022; Wu et al., 2018; Xiong et al., 2021). A central research direction concerns expressivity, i.e., the ability to distinguish nonisomorphic graphs, typically benchmarked against the WL test, with 1-WL serving as a standard baseline. Foundational advances such as Deep Sets (Zaheer et al., 2017) and Graph Isomorphism Network (GIN) (Xu et al., 2019) established 1-WL as the reference point for evaluating GNN expressivity, spurring efforts to surpass its limitations (Morris et al., 2023). Nonetheless, 1-WL remains sufficient for distinguishing most graphs in widely used benchmarks (Morris et al., 2021; Zopf, 2022), underscoring its practical relevance. These advances, however, do not address the multirelational setting and focus exclusively on static graphs.

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 crossgraph 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.

For multi-relational graphs, Barceló et al. (2022) and Huang et al. (2023b) introduce the relational WL (1-RWL) and relate it to the expressivity of RGNNs, as proposed by, e.g., Schlichtkrull et al. (2018); Vashishth et al. (2020), and present k-relational GNNs that provably surpass 1-RWL. For temporal graphs, Wał˛ega & Rawson (2025) analyze temporal message passing (MP) by distinguishing global and local TGNNs, provide RWL characterizations for both, and show that their expressivities are incomparable in general but that local models are more powerful on color-persistent temporal graphs. In contrast, Heeg et al. (2025) study temporal isomorphism via time-respecting paths and propose an RWL test on augmented event graphs, grounding expressivity in the temporal causal topology rather than in the global/local MP distinction.

1. Introduction GNNs are powerful models for learning on graph-structured data, where complex objects such as molecules, proteins, 1

Faculty of Computer Science, University of Vienna, Vienna, Austria 2 Doctoral School Computer Science, University of Vienna, Vienna, Austria 3 CeMM Research Center for Molecular Medicine of the Austrian Academy of Sciences, Vienna, Austria 4 CISPA Helmholtz Center for Information Security, Saarbrücken, Germany 5 School of Electronic Engineering and Computer Science, Queen Mary University of London, UK 6 Research Network Data Science, University of Vienna, Vienna, Austria. Correspondence to: Lorenz Kummer <lorenz.kummer@univie.ac.at>.

The Lottery Ticket Hypothesis (LTH), introduced by Frankle & Carbin (2019), posits that large, randomly initialized neural networks contain smaller subnetworks, termed winning tickets, that can be trained in isolation to match the full model’s prediction quality. LTH has also been extended to GNNs via pruning of both graph structures and GNN parameters, resulting in Graph Lottery Tickets (GLTs) that retain prediction quality while lowering computational demands (Chen et al., 2021; Tsitsulin & Perozzi, 2023). Recently, Kummer et al. (2025b) formalized the link between

A Unifying Relational Perspective on Expressive Lottery Tickets

the LTH and GNN expressivity for static, uni-relational graphs: at a minimum, a winning ticket must allow the model to learn to distinguish any non-isomorphic graphs (or nodes) associated with different targets in the downstream task. Under certain circumstances, a sparsely initialized GNN cannot recover from a loss of expressivity. Kummer et al. (2025b) conclude that preserving expressivity under sparsity is crucial for successfully identifying winning lottery tickets and show that sparse subnetworks exist which preserve 1-WL expressivity, thereby introducing the SELTH. Their analysis is purely existential, restricted to static unirelational graphs and the corresponding 1-WL variant, and does not extend to temporal or multi-relational settings, which can be parameter heavy (Ehrlich et al., 2026).

Relating LTH to TGNN expressivity is challenging, as the very notion of isomorphism on temporal graphs is still being clarified. Wał˛ega & Rawson (2025) lay out two seminal notions of temporal isomorphism: pointwise isomorphism (Beddar-Wiesing et al., 2024), which compares snapshots independently, and timewise isomorphism, which additionally preserves inter-snapshot time gaps. They formalize global (Longa et al., 2023; Xu et al., 2020; Luo & Li, 2022) and local (Qu et al., 2020; Rossi et al., 2020) MP TGNNs via knowledge graphs and prove tight 1-RWL characterizations. Moreover, they note that event-based temporal graphs can be transformed into the snapshot representation (Gao & Ribeiro, 2022; Longa et al., 2023), concluding that analyzing snapshots subsumes event-based inputs. Hence, our work focuses on this snapshot representation to maximize its generality. Complementing these snapshot-oriented notions, Heeg et al. (2025) introduce consistent event-graph isomorphism and prove it is equivalent to static isomorphism on an augmented event graph. Other notions of temporal graph isomorphism are provided by Gao & Ribeiro (2022); Souza et al. (2022). Furthermore Souza et al. (2022) show that TGNNs with injective aggregation/updates are as expressive as a variant of 1-WL that refines colors using timestamped interactions, whereby walk-aggregating and MP TGNNs are incomparable.

To address this gap, we leverage Wał˛ega & Rawson (2025)’s characterization of local and global MP schemes as instances of 1-RWL on suitable abstractions. Together with the RGNN framework, this enables us to extend the SELTH beyond static graphs, proving that sparsely initialized subnetworks can preserve 1-RWL expressivity in both temporal and multi-relational settings, thereby establishing SELTH as a general principle for expressive and efficient RGNNs and TGNNs. We further apply the framework to cross-graph and hierarchical MP (Fey et al., 2020; Ehrlich et al., 2026).

Similarly, the expressivity of cross-graph and hierarchical MP architectures has, to the best of our knowledge, not yet been formally characterized or discussed under sparsity. While Ehrlich et al. (2026) formally show that their proposed architecture (XIMP) subsumes Fey et al. (2020) (HIMP), which, in turn, can distinguish some exemplary molecular graphs indistinguishable to 1-WL-bounded GNNs, neither provides formal guarantees.

Related work. Building on Frankle & Carbin (2019)’s LTH, Frankle et al. (2019) prune early in training rather than strictly at initialization, and obtain sparse subnetworks without loss of prediction quality or stability. Malach et al. (2020); da Cunha et al. (2022) extend to the Strong Lottery Ticket Hypothesis (SLTH), proving that over-parameterized networks contain subnetworks that achieve high prediction quality without training. Zhang et al. (2021a) explain LTH’s generalization benefits: pruning enlarges a convex region of the loss landscape, enabling faster convergence with fewer samples. Zhang et al. (2021b) further validate that pruned subnetworks can match dense networks without repeated prune-retrain cycles.

Contributions. We generalize SELTH to (i) multirelational RGNNs, (ii) local and global TGNNs and (iii) crossgraph and hierarchical MP architectures. We formally show that sparse subnetworks in these architectural classes exist which preserve expressivity under the 1-RWL framework. That is, we prove Relational SELTH (RSELTH), which subsumes the original SELTH, and derive an explicit lower bound on the probability that a random pruning mask yields a maximally expressive subnetwork. We further show that every local or global TGNN can be rewritten as an RGNN, to which RSELTH applies, and that RSELTH similarly applies to certain cross-graph and hierarchical MP patterns, for which our 1-RWL characterization also marks the first formal characterization of their expressivity. For TGNNs, we connect RSELTH with different notions of temporal isomorphism. Finally, we analyze the optimization of sparse RGNNs with the minimal expressivity required to realize all task-relevant distinctions, and show that all surviving parameters remain trainable under small-step first-order methods.

In GNNs, LTH approaches typically co-prune graph structure and model parameters. Chen et al. (2021); Wang et al. (2023) and Sui et al. (2023) co-prune adjacency matrices and weights to recover GLTs that retain prediction quality and Zhang et al. (2024) automate adaptive pruning to find GLTs without manual tuning. Hui et al. (2023) and Yuxin et al. (2024) consider co-pruning from an adversarial robustness perspective. Tsitsulin & Perozzi (2023) posit that any graph contains a sparse substructure preserving downstream prediction quality. Yan et al. (2024) leverage SLTH to improve memory efficiency. Kummer et al. (2025b) formally and empirically linked LTH and GNN expressivity via SELTH. In line with Zhang et al. (2021b), Kummer et al. (2025b) show that expressive sparse initializations can speed convergence and improve generalization. 2

A Unifying Relational Perspective on Expressive Lottery Tickets

2. Preliminaries

where Υ3 is any fixed injective encoding of its arguments (k) (k) into a new color in C. Let Crwl (G) = {{ cG (v) | v ∈ V (G) }} denote the multiset of node colors at iteration k. (k) (k+1) The refinement stabilizes once |Crwl (G)|= |Crwl (G)|. For two input graphs G, H, if there exists k ≥ 0 such that (k) (k) Crwl (G) ̸= Crwl (H), then G ̸≃RWL(k) H. Finally, 1-RWL reduces to classical 1-WL if |R|= 1 and G is undirected. Therefore, it can be seen as the relational counterpart to 1-WL, serving as an expressivity baseline for RGNNs.

An undirected graph G is a pair (V, E) of a finite set of nodes V and edges E ⊆ {{u, v} | u, v ∈ V }. The node and edge sets of G are denoted by V (G) and E(G), respectively. The neighborhood of a node v ∈ V (G) is N (v) = {u ∈ V (G) | {u, v} ∈ E(G)}. For a node labeled graph G, we write G = (V, E, λ), where λ : V (G) → X maps to a label set X . For an edge labeled graph G, we write G = (V, E, τ ), where τ : E → R maps to a label set R. If G is a directed graph, we write Ė ⊆ V ×V and τ̇ : Ė → R. We define the outgoing and incoming neighborhoods of v ∈ V as N − (v) = { u ∈ V | (v, u) ∈ Ė }, N + (v) = { u ∈ V | (u, v) ∈ Ė } and N ± (v) = N − (v) ∪ N + (v). If G is directed and R is a set of relations (edge types), we refer to G as directed multi-relational graph and write Ėr = {(u, v) ∈ Ė | τ̇ (u, v) = r} for r ∈ R and Nr− (v) = { u ∈ V | (v, u) ∈ Ėr }, Nr+ (v) = { u ∈ V | (u, v) ∈ Ėr } and Nr± (v) = Nr− (v) ∪ Nr+ (v). If G is undirected multi-relational with τ : E(G) → R, we write Er (G) = {{u, v} ∈ E(G) | τ ({u, v}) = r} and Nr (v) = {u ∈ V (G) | {u, v} ∈ Er (G)}. If a bijection φ: V (G) → V (H) with {u, v} ∈ E(G) ⇐⇒ {φ(u), φ(v)} ∈ E(H) for all u, v ∈ V (G) exists, we call the two undirected unlabeled graphs G and H isomorphic and write G ≃ H. For node labeled graphs H, G, the bijection must satisfy λH (φ(v)) = λG (v) for all v ∈ G. For undirected edge labeled graphs H, G, the bijection must satisfy τH ({φ(u), φ(v)}) = τG ({u, v}) for all {u, v} ∈ E(G) and, for directed edge labeled graphs, τ̇H (φ(u), φ(v)) = τ̇G (u, v) for all (u, v) ∈ Ė(G). For directed multi-relational graphs H, G, the bijection must satisfy (u, v) ∈ Ėr (G) ⇐⇒ (φ(u), φ(v)) ∈ Ėr (H), where Ėr (G) = {(u, v) ∈ Ė(G) | τ̇G (u, v) = r} for all r ∈ R. For undirected multi-relational graphs H, G, the bijection must satisfy {u, v} ∈ Er (G) ⇐⇒ {φ(u), φ(v)} ∈ Er (H), where Ėr (G) = {{u, v} ∈ Ė(G) | τG (u, v) = r} for all r ∈ R.

Relational GNNs. Let G = (V, Ė, λ, τ̇ ) be a directed, node-labeled, multi-relational graph with relation set R. We initialize node embeddings from labels via an encoder (0) Λ : X → Rd , i.e., hv = Λ(λ(v)). A relational GNN (RGNN) layer produces h(l+1) from h(l) at layer l ≤ L by first aggregating messages per relation and direction, and then combining the resulting summaries in a permutationinvariant fashion (Barceló et al., 2022). Representative of common RGNN architectures such as (Schlichtkrull et al., 2018; Vashishth et al., 2020; Huang et al., 2023b), we define an RGNN layer that mirrors directed 1-RWL refinement G = (V, Ė, λ, τ̇ ) as (l)

(k+1)

(k)

(l)

(1)

(l) (l) + mr,+ (v) = Ωa ({{Φr,+(h(l) u ), u ∈ Nr (v)}})

(2)

for each r ∈ R and (l) h(l+1) = Γ Ωc ({{h(l) v v }} ⊎

]

(l) {{mr,▷ (v), r ∈ R}}) .

▷∈{+,−}

(3) (l)

Here, each Φr± : Rd → Rd and Γ(l) : Rd → Rd are learnable functions and ⊎ is the additive multiset union: if A, B are multisets with multiplicity functions µA , µB , P then µA⊎B (x) = µA (x) + µB (x). Using as multiset (l) aggregator Ωa and combinator Ωc and injective Φr and (l) Γ (e.g., MLPs with suitable activations and width (Amir et al., 2023; Puthawala et al., 2022; Zaheer et al., 2017)) yields the same distinguishing power as 1-RWL: P Remark 2.1. Using aggregation as a permutationinvariant multiset encoder over the elements of a multiset D alone is injective if the elements of D are linearly inde(l) pendent (Kummer et al., 2025a). Hence Φr,± and Λ must be chosen accordingly.

Relational Weisfeiler-Leman. Let G = (V, Ė, λ, τ̇ ) be a directed, node-labeled, multi-relational graph with relation set R. The (directed) 1-RWL test maintains a node color(k) ing cG : V (G) → C over iterations k ≥ 0, initialized as (0) (k) cG = λ. Given cG , the next coloring is obtained by aggregating, for each relation r ∈ R, the multisets of colors in the relation-specific outgoing and incoming neighborhoods Nr− (v) and Nr+ (v), and then applying an injective hashing scheme to obtain new, unused colors. Concretely, similar to (Huang et al., 2023b), we write the update rule as

− mr,− (v) = Ωa ({{Φr,−(h(l) u ), u ∈ Nr (v)}}),

Note that normalizations (e.g., degree-based scalings) can be inserted into the sums without changing the 1-RWL upper bound (Barceló et al., 2022). We denote the L-layer RGNN architecture stacking layers of the form (1)-(3) as Ψ(L) and (L) write ΨΘ for a concrete parameterization Θ.

(k)

(v) = Υ3 cG (v), ( {{ cG (u) | u ∈ Nr− (v) }} )r∈R , (k) ( {{ cG (u) | u ∈ Nr+ (v) }} )r∈R , 3

A Unifying Relational Perspective on Expressive Lottery Tickets

time lags R = {0, 1, . . . , n − 1}, whereby the r ∈ R is obtained from the real valued time stamps via the orderpreserving bijection ι : {t1 , . . . , tn } → {1, . . . , n} with ι(ti ) = i, i.e., r = ι(tj ) − ι(ti ) = j − i. Then, for Kglob , the relational edge sets for each r ∈ R can be constructed over the directional edge sets Ė glob = {(j − i, (v, ti ), (u, tj )) | i ≤ j, {u, v} ∈ Ei } ⊆ R × V time × V time as Ėrglob = {e ∈ Ė glob | τ̇ ⋆ (e) = r} with τ̇ ⋆ ((j − i, (v, ti ), (u, tj ))) = r = j − i (with ⋆ indicating the adaptation to the triplet domain). For Kloc , they are constructed via Ė loc = {(j − i, (v, tj ), (u, tj )) | i ≤ j, {u, v} ∈ Ei } ⊆ R × V time × V time and Ėrloc = {e ∈ Ė loc | τ̇ ⋆ (e) = r}.

Temporal graphs. A temporal graph in the snapshot model is a finite sequence T G = ((G1 , t1 ), . . . , (Gn , tn )) of undirected node labeled graphs with strictly increasing (real-valued) timestamps t1 < · · · < tn , where each snapshot Gi = (V, Ei , λi ) shares the same node set V (node labels may vary with i) (Wał˛ega & Rawson, 2025). For T G, timestamped nodes are defined as V time = {(v, ti ) | v ∈ V, i ∈ {1, . . . , n}} = t-nodes(T G) with timeaware labels λtime (v, ti ) := λi (v). For a timestamped node (v, t), we follow Souza et al. (2022) and define its temporal neighborhood as N (v, tj ) = { (u, ti ) | {u, v} ∈ Ei , for some (Gi , ti ) ∈ T G with ti ≤ tj }. We overload N (·) by context: when the second argument is a time tj , N (v, tj ) denotes the multiset/set of timestamped neighbors up to (and including) time tj , whereas N (v) denotes the static neighborhood in a single snapshot. According to Wał˛ega & Rawson (2025), two temporal graphs T Ga = ((Ga1 , ta1 ), . . . , (Gan , tan )) and T Gb = ((Gb1 , tb1 ), . . . , (Gbm , tbm )) are timewise isomorphic if n = m, tai+1 − tai = tbi+1 − tbi for all i ∈ {1, . . . , n − 1}, and there exists a bijection ϕ that is a graph isomorphism between Gai and Gbi for every i ∈ {1, . . . , n}. If this is the case, we write T Ga ≃time T Gb . The timestamped nodes (v, tai ) and (u, tbi ) are timewise isomorphic if ϕ(v) = u.

For these Kloc and Kglob , the following trivially follows from Wał˛ega & Rawson (2025): Corollary 2.2. Let T G be a temporal graph and let x = (v, ti ), x′ = (u, tj ) ∈ V time . For any k ∈ N, for any local or global TGNN, and 1-RWL instantiated with the perrelation, per-direction neighborhoods Nr+ (·), Nr− (·) of the corresponding K⋆ (T G), with ⋆ ∈ {glob, loc}, there exist parameters for that TGNN such that (k)

(k)

cK⋆ (T G) (x) = cK⋆ (T G) (x′ ) ⇐⇒ h(k) x = hx′ .

Temporal GNNs. Let δ((u, ti ), (v, tj )) := tj − ti denote the real valued time gaps between timestamped nodes and write δij as shorthand. Then, following (Wał˛ega & Rawson, 2025), for a T G as above, a general TGNN is defined as

The proofs of the above and all subsequent theoretical claims are provided in Appendix D.

3. Relational Expressivity and Lottery Tickets

(l) (l) mtj (v) = Ωa ({{Φ(l)(Ξ(h⋆ , ζ(δij ))), (u, ti ) ∈ N (v, tj )}})

We now extend SELTH to RGNNs. We assume that all binary pruning masks M with sparsity ratio ρ ∈ (0, 1) are constructed such that each entry is an independent Bernoulli random variable, and we write M ∼i.i.d. B(1 − ρ). Furthermore, we assume a parameter initialization Θ0 for Ψ(L) where each entry is independently drawn from a continuous, bounded uniform distribution on an interval [c, d] ∈ R with c < d, and we write Θ0 ∼ Ucd . A sparse initialization of b 0 = M ⊙ Θ0 . Ψ(L) is then given by the Hadamard product Θ (l) We also assume, for all MLPs (e.g., Γ ), a class of realanalytic, injective, continuously differentiable zero-fixing activations σ with a nowhere-zero derivative. The assumptions on σ are merely technical and simplify the analysis. Extending our results to other activations is straightforward but requires case distinctions. We assume that initial node labels are encoded by an injective map Λ. Appendix H details all assumptions and limitations.

(4) whereby ⋆ = (u, ti ) yields global and ⋆ = (u, tj ) yields local MP, ζ denotes some mapping of the scalar δij to a (l) scalar or a vector and Ξ denotes a function combining h(u,ti ) (l)

or h(u,tj ) with ζ(δij ), whereby Wał˛ega & Rawson (2025) chose concatenation ∥ for Ξ and ζ(δij ) = δij . This followed by a combinator (l+1) (l) (l) h(v,tj ) = Γ(l) Ωc ({{hv,tj }} ⊎ {{mtj (v)}}) . (5) P By Rossi et al. (2020); Xu et al. (2019), summation or concatenation ∥ are common choices for Ωa , Ωc . Similar to RGNNs, we denote the L-layer TGNN stacking layers (L) of the form (4)-(5) as Ψ or ΨΘ . Where ambiguous, we (L) specify whether ΨΘ denotes an RGNN or a TGNN.

Theorem 3.1 (Relational SELTH). Let D be any finite collection of finite graphs, where each element of D is a directed node-labeled multi-relational graph G = (V, Ė, λ, τ̇ ). Let Ψ(L) be a corresponding sufficiently overparametrized depth-L RGNN. Then, for all Ga , Gb ∈ D,

Expressivity of TGNNs. To bridge the MP schemes of TGNNs with the 1-RWL characterization of expressivity, Wał˛ega & Rawson (2025) construct from T G two directed, multi-relational knowledge graphs Kglob and Kloc over the timestamped nodes V time and a finite relation set of

b (L) (Ga ) ̸= Ψ b (L) (Gb ) Ga ̸≃RWL(L) Gb ⇐⇒ Ψ b b Θ Θ 0

A Unifying Relational Perspective on Expressive Lottery Tickets

or global TGNN. Then, with ⋆ ∈ {glob, loc} being Ψ(L) ’s (L) MP paradigm, there exist Θ for Ψ⋆ such that

with a probability at least γRGNN > 0. Intuitively, γRGNN is the probability that all branch and combine MLPs remain injective on the finite input sets they witness on D. The proof of Theorem 3.1 (Appendix D) yields an explicit lower bound in terms of: the maximum (l) number Nmax of distinct inputs witnessed by any Φr± or Γ(l) , the minimum ℓ0 -separation smin between such inputs, the minimum hidden width mmin across these MLPs, the number of branches |B| per layer (tied to the relations and directions), the MLP depth M , message-passing depth L, and the pruning probability ρ. Appendix D derives γRGNN by bounding per-block non-injectivity on D, union-bounding within each layer, and composing over L layers under independent masks. A compact (slightly looser) bound is e L(M |B|+1) Nmax semin m e min γ eRGNN ≥ [1 − ρ ]+ , 2

K⋆ (T Ga ) ̸≃RWL(L) K⋆ (T Gb ) ⇐⇒ (L)

(L)

ΨΘ,⋆ (T Ga ) ̸= ΨΘ,⋆ (T Gb ).

(6) (7)

To show that Theorem 3.1 also applies to TGNNs, we show that Lemma 3.2 also holds under pruning. To achieve this, we consider several different routes. Any global or local TGNN can be rewritten as an RGNN operating on an auge ⋆ (T G) (either encoding the real valued time gaps mented K δij as edge features or using a refined relation alphabet) to which Theorem 3.1 applies. We discuss the case of a e ⋆ (T G) encoding δij as edge features here and the alternaK tive route along its shortcomings in Appendix A. To this purpose, we construct an RGNN operating on e ⋆ (T G) that is algebraically identical to an augmented K the corresponding TGNN operating on T G: Fix ⋆ ∈ {glob, loc} and a TGNN layer as in Eqs. (4)-(5) with aggregation/combination Ωa , Ωc , message map Φ(l) , combiner Γ(l) , gap encoder ζ, edge-time gaps δ(y, x) and a corresponding K⋆ (T G). We can realize the same update e ⋆ (T G) by attaching to each directed with an RGNN on K edge e = (y → x) the edge feature ξe := ζ(δ(y, x)), (l) and using a shared message map Φr,± ≡ Φ(l) , writing e (l) (h, ξ) := Φ(l)(Ξ(h, ξ)), for an appropriate Ξ (e.g., Φ ∥). With the same Ωa , Ωc , Γ(l) as in the TGNN, the RGNN update at x becomes

emax := with [x]+ := max{x, 0}, where N max{Nmax , Nmax,comb }, semin := min{smin , smin,comb }, and m e min := min{mmin , mmin,comb } aggregate worstcase input-count, separation, and width across branch and combine MLPs; the full expression is given in Appendix D. For any target γtarget ∈ (0, 1), it suffices to choose m e min large enough so that the (clamped) bound se m e L(M |B|+1) ([ 1 − Nmax ρ min e min ]+ ) exceeds γtarget . 2 e Nmax s emin m e min Provided 1 − 2 ρ > 0, a sufficient width to certify γ eRGNN ≥ γtarget is ! 1/(L(M |B|+1)) 1 − (γtarget ) 1 m e min ≥ ln . emax N semin ln ρ

e (l) (h(l) , ξ(y→x) ) | y ∈ N ± (x)}}), mr,± (x) = Ωa({{Φ y r ] h(l+1) = Γ(l) Ωc ({{h(l) {{mr,± (x))}}) , x x }} ⊎

This threshold is obtained by inverting a conservative lower bound and may be pessimistic. We therefore call Ψ(L) sufficiently overparameterized if its smallest hidden width m e min satisfies the above inequality, which certifies γtarget .

r,±

which by construction is algebraically identical to Eqs. (4)(5) for the chosen (global/local) neighborhoods: Lemma 3.3. Fix ⋆ ∈ {glob, loc} and a TGNN layer with maps (Ωa , Ωc , Φ(l) , Γ(l) , ζ, Ξ). Instantiate an RGNN on e ⋆ (T G) with Φ e (l) (h, ξ) := Φ(l)(Ξ(h, ξ)), using the same K (l) (Ωa , Ωc , Γ(l) ) and strict weight tying Φr,± ≡ Φ(l) across (r, ±). Then for every T G, all x ∈ V time and all l ≥ 0

Theorem 3.1 is not a restatement of Kummer et al. (2025b)’s SELTH, which is an existence result for 1-WL bounded GNNs. Theorem 3.1 gives a probabilistic guarantee: under a random sparse initialization, directed 1-RWL distinguishability on directed multi-relational graphs is preserved with probability at least γRGNN > 0. This requires |B| relationdirection branches plus a combine MLP and makes γRGNN depend on worst-case input statistics across all branch and combine blocks. With |R|= 1 and no directions, Theorem 3.1 reduces to Kummer et al. (2025b)’s SELTH.

e (l) e h(l) x (TGNN on T G) = hx (RGNN on K⋆ (T G)) . Together with Corollary 2.2, Lemma 3.3 implies that the e ⋆ (T G) has exactly the same nodeRGNN operating on K level expressivity as 1-RWL operating K⋆ (T G), which transfers to the graph level by the same argument as in Lemma 3.2. As D is finite and each T G ∈ D is finite, only finitely many time gaps δ appear as edge feae ⋆ (T G). Hence Theorem 3.1 applies verbatim tures on K to this RGNN via the same finite-domain injectivity argu(l) ment. Moreover, as we tie parameters (Φr,± ≡ Φ(l) ) and

Temporal expressivity and lottery tickets. To bring RSELTH to TGNNs, we first derive the following graphlevel statement from the node-level formulation of Corollary 2.2 to match the setup of Theorem 3.1: Lemma 3.2. Let T Ga , T Gb be arbitrary elements of a finite collection D of temporal graphs and Ψ(L) a depth-L local 5

A Unifying Relational Perspective on Expressive Lottery Tickets

choose Ωa , Ωc , Γ(l) to match the TGNN exactly, parameter matrices correspond one-to-one and pruning masks transfer verbatim from the RGNN back to the TGNN. Consequently, RSELTH, up to minor modifications, also holds for sufficiently overparameterized global and local TGNNs. We state the corresponding TGNN reformulation of Theorem 3.1 in Appendix B, and, for completeness, prove it directly using Eqs. (4)-(5). Moreover, Appendix C extends the result to the node level, matching the node-level focus of Wał˛ega & Rawson (2025).

iff there exists v ∈ V with Si [v, u] = Sk [v, w] = 1. While I2 MP and DIMP both employ a single-layer postaggregation transformation (a linear map followed by a pointwise nonlinearity), XIMP and HIMP can employ arbitrary standard GNNs for local MP on G and Ti . Moreover, XIMP uses mean aggregation and HIMP uses concatenation or sum. Hence, to standardize the analysis, we adopt sum aggregation to leverage its multiset discriminative power (Xu et al., 2019) and assume a single-layer post-aggregation transformation for I2 MP, DIMP and MP. Un We define the compound node set Ve := V ⊎ i=1 Vi and construct a directed multi-relational compound graph G⊕ = e τ̇ ⊕ ) by taking the disjoint union of all intra(Ve , Ė ⊕ , λ, graph edges and adding typed cross-graph edges: (i) intra edges Ė on V and Ėi on Vi retain their original relation labels; (ii) for each i and each (v, u) with Si [v, u] = 1, add v → u with relation type αi and u → v with type ᾱi ; (iii) for i ̸= k, add u ∈ Vi → w ∈ Vk with type βik whenever there exists v ∈ V such that Si [v, u] = Sk [v, w] = 1 and the corresponding reverse edge with type β̄ki . Up to notation, our definition is the same as Ehrlich et al. (2026), except that edge types are made explicit. As XIMP applies non-linear transformation post-aggregation, we initialize embeddings (0) e by e hx = Λ(λ(x)) for x ∈ Ve with an injective Λ as in the relational case (Section 3) but with the additional constraint that Λ(X ) ⊂ Rd is linearly independent (Remark 2.1). A single cross-graph layer on G⊕ is then a relational update as in Eqs. (1)-(3), over R⊕ , the union of all intra-graph relation types and the cross-graph types αi , ᾱi , βik , β̄ki . By tying parameters per relation type (i.e., assigning linear (l) (l) Φr to all cross-graph types and one parameter tied Φr to each set ofPintra-graph per G and Ti ) and using P relations Ωa = σ ◦ , Ωc = with Γ(l) = id, this single layer is, except DIMP’s normalization, by construction algebraically identical to XIMP’s combination of MP with I2 MP and DIMP. As DIMP’s normalization would not change the 1RWL bound on G⊕ (Section 2), we omit it in the analysis.

We now relate Theorem 3.1 applied to TGNNs to (Wał˛ega & Rawson, 2025)’s notion of temporal isomorphism, which is taken to the graph level by the following Lemma. Lemma 3.4. Let T Ga = ((Ga1 , ta1 ), . . . , (Gan , tan )) and T Gb = ((Gb1 , tb1 ), . . . , (Gbn , tbn )) be temporal graphs. Fix L ∈ N and ⋆ ∈ {glob, loc}. Then for sufficient L: T Ga ≃time T Gb =⇒ K⋆ (T Ga ) ≃RWL(L) K⋆ (T Gb ). Therefore, combining Lemma 3.4 with Theorem 3.1 via Lemma 3.3, if a sparse parameterization of a (local or global) TGNN distinguishes two temporal graphs, then those graphs are not timewise isomorphic. This links RSELTH to other notions of isomorphism of temporal graphs. By Wał˛ega & Rawson (2025), (Beddar-Wiesing et al., 2024)’s pointwise isomorphism is less strict than timewise isomorphism. Heeg et al. (2025)’s notion is also more relaxed than timewise isomorphism: they prove it lies between time-aggregated and time-concatenated isomorphism, with the latter being equivalent to the notions proposed by Gao & Ribeiro (2022); Souza et al. (2022). For unlabeled snapshot graphs, Wał˛ega & Rawson (2025)’s timewise isomorphism coincides with time-concatenated isomorphism, hence any timewise-isomorphic pair is consistent event-graph isomorphic (equivalently, their augmented event graphs are isomorphic). The converse does not hold in general; equivalence with timewise isomorphism holds only under constraints (Heeg et al., 2025).

Corollary 3.5. Let D be a finite collection of inputs (G, {Ti , Si }ni=1 ) and G⊕ be constructed as above for each element of D. Then there exists a parameterization of an RGNN on G⊕ such that, for all pairs in D and all L ∈ N,

Cross-graph MP (XIMP/HIMP). Let G = (V, Ė, λ, τ̇ ) be a directed, node-labeled, (multi-)relational graph (e.g., a molecular graph) and let {Ti = (Vi , Ėi , λi , τ̇i )}ni=1 be abstractions of G (e.g., junction tree (Jin et al., 2018), extended reduced graph (Stiefl et al., 2006)). Analogous to Ehrlich et al. (2026) (XIMP) and Fey et al. (2020) (HIMP), we encode atom-abstraction incidence by an assignment matrix Si ∈ {0, 1}|V |×|Vi | , where Si [v, u] = 1 iff v ∈ V contributes to u ∈ Vi . XIMP takes G and {Ti , Si } as input and (L) computes ΨΘ (G, {Ti , Si }) to embed G. It performs MP on G and each Ti and two-way inter-graph MP both indirectly (I2 MP, G ↔ Ti ) via Si and directly (DIMP, Ti ↔ Tk ) via the on-the-fly computed abstraction-abstraction incidence matrix Sik ∈ 0, 1|Vi |×|Vk | , where Sik [u, w] = 1

⊕ G⊕ a ̸≃RWL(L) Gb ⇐⇒ (L)

(L)

ΨΘ (Ga , {Tia , Sia }) ̸= ΨΘ (Gb , {Tib , Sib }).

(8)

As the reduction to a relational layer on the compound graph G⊕ yields a one-to-one correspondence with XIMP’s parameters by construction, the pruning masks align. It suffices to directly apply Theorem 3.1 to the corresponding RGNN operating on {G⊕ }: sparse subnetworks that preserve 1-RWL distinguishing power on G⊕ transfer to XIMP (and hence HIMP, as setting n=1 with T1 the junction tree recovers HIMP’s inter-MP), yielding SELTH for cross-graph MP. 6

A Unifying Relational Perspective on Expressive Lottery Tickets

105

1.5

2.0

=0 = 1 .99 0 9

.99

2.5

smin

3.0

3.5

0.2

0.4

0.6

Sparsity

0.8

0.2

RGNN

Nmax = 102 Nmax = 103 Nmax = 104 Nmax = 105 Nmax = 106 Nmax = 107

Line: B

B=2 B=8 B = 32

0.4

0.6

Sparsity

0.8

0 1e8 2

MADDS (est.)

Nmax

(d)

Color: Nmax

104

(c)

Width mmin

1.2 10

1.7 10

2.4 10

6.4 10

=0 0 9

103

(b)

3.3 10

8.8 10

4.6 10

(a)

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.

putational cost under varying Nmax , smin , mmin , |B|, M, L and ρ in Figure 1. We treat γRGNN as a worst-case probability that a random mask preserves the L-round 1-RWL expressivity on a finite dataset, not as a predictor of downstream prediction quality. We focus on the RGNN of Section 2 and estimate the multiply-adds operations (MADDs) of an MLP similar to Kummer et al. (2023); see Appendix F.

Optimization of expressive lottery tickets. The optimization of sparse RGNNs is subtle, so we defer technical details to Appendix E and summarize the main results here. We call a sparse initialization with mask M optimizable on a finite dataset D if, when the output loss gradient is nonzero at least for one element of D, every surviving parameter is gradient-connected to the loss and receives a nonzero update at least once over D. We show for RGNNs that irreducible task-expressive masks (minimal masks whose surviving parameters suffice to distinguish exactly those non-isomorphic graphs in D that carry different labels) are optimizable in this sense. In contrast, arbitrarily sparsified RGNNs at the same sparsity need not be optimizable: they may both fail to realize label-relevant distinctions and allocate disconnected parameters receiving zero gradients. Finally, we prove that optimizability under irreducible task-expressive masks persists under standard small-step first-order updates for sufficiently small step sizes.

Figure 2(a) illustrates the tightness of γRGNN . We first generate a synthetic dataset Dsyn of 30 multi-relational graphs. Then, P we randomly initialize and prune a simple RGNN using for Ωa , Ωc and readout. Next, we compute graph embeddings over Dsyn . A pruning mask at sparsity ρ is counted as successful iff the resulting embeddings are pairwise distinct across all graphs. Sampling 100 masks for each ρ on a uniform grid of 50 values in [0.01, 0.99] yields an empirical success rate γempirical , which we plot against the mean γ RGNN obtained by instantiating γRGNN on the configuration-specific input statistics of each sample (details Appendix G). Moreover, Figure 2(b) shows how a simple pre-training separability proxy is associated with optimization under pruning. For each ρ, we sample 20 masks, apply each mask to a freshly initialized RGNN with a linear classifier, and evaluate the fraction of separable graphs before training, i.e., the number of distinct embeddings divided by |Dsyn |. We then train the model for 10 epochs on a graphID classification task over Dsyn , masking both weights and gradients. We record (i) the final training loss, (ii) the final training accuracy, and (iii) the global gradient-flow (Evci et al., 2022) given by the global ℓ2 -norm of the gradients, averaged over epochs. We average metrics across trials and report Spearman correlations between pre-training separability and post-training metrics. While Figure 2(b) illustrates a general trend that separability is associated with optimization under pruning over a large interval of pruning rates, it does not fully disentangle expressivity from model size. As subnetworks with lower sparsity naturally retain more parameters, it remains unclear whether the observed improvement in gradient flow, loss, or accuracy comes from preserv-

4. Numerical Illustrations and Empirics Our evaluation has three parts: (i) we instantiate Theorem 3.1’s bound γRGNN to visualize width–sparsity– compute trade-offs as its governing quantities vary (Figure 1); (ii) on a synthetic multi-relational dataset, we instantiate γRGNN using architecture/dataset-specific input statistics, compare it to an empirical mask success rate γempirical , and relate pre-training graph separability (i.e., whether observed graphs receive distinct embeddings) as empirical expressivity proxy to gradient flow and training loss/accuracy under fixed masks as a proxies for optimizability (Figures 2, 3 and 4); (iii) on real temporal and molecular benchmarks, we examine how pre-training separability of pruned models correlates with compression across pruning rates and predicts test performance (Figure 5).

Setup. We instantiate Theorem 3.1’s γRGNN to visualize how expressivity and sparsity interact with width and com7

A Unifying Relational Perspective on Expressive Lottery Tickets

log10 (p)

Flow Loss

0.5 0.0

RGNN

0.25

Acc.

empirical

0.00

(b)

log10 (p)

(a)

1.0

0.50

Sparsity

0.75

1.00

0.4

0.2

0.0

0.2

Spearman's sm .

0.4

= 0.9125 = 0.925

Flow Loss

1.0

0.5

0.0

0.5

Spearman's sm .

= 0.9375 = 0.95 Acc.

1.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 , − log10 p), dashed lines indicate ρsm = 0 and p = 0.05.

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 , − log10 p), with the dashed lines indicating p = 0.05 and ρsm = 0.

pre-training separability. Separability values are grouped into 25 bins, and for each bin we report P (WT | Sep.), the probability of a model being a winning ticket (WT) 1 .

ing task-relevant expressivity or simply from having larger subnetworks. Figure 3 hence shows a fixed-sparsity control experiment: using the same RGNN configuration and Dsyn , for four sparsity levels ρ ∈ {0.9125, 0.925, 0.9375, 0.95}, we sampled 100 random masks with identical parameter counts and compared optimization behavior across different pre-training separability levels, using 30 training epochs.

Results and practical implications. The numerical behavior of γRGNN suggests practical design rules for sparse RGNN initializations. Figure 1(d) shows that as Nmax and B increase, the width–sparsity trade-off shifts, so larger and more complex benchmarks typically tolerate less aggressive pruning (or require wider layers) to maintain a fixed γRGNN . Moreover, Figure 1(b) shows that increases in smin (which could be achieved via input encodings (Kummer et al., 2025a) or by avoiding pruning schemes (Deng et al., 2020) inherently zeroing activations) can increase the sparsity attainable at a given width for the same target γRGNN . This also suggests a link to over-smoothing (Chuang et al., 2025; Rusch et al., 2023), which can similarly reduce input separability. The γRGNN contours in Figure 1(c) highlight a width–pruning trade-off: along a fixed target level (e.g., γRGNN ≈ 0.99), width can be traded for sparsity up to moderate ρ while keeping the approximate MADDs budget roughly constant. At high sparsity, however, the width required to maintain the target makes cost grow exponentially. Consistently, Figure 1(a) shows diminishing cost-efficiency from further widening at fixed benchmark complexity and sparsity as γRGNN → 1. Figures 1(a)–(c) show that the band between γRGNN = 10−9 and γRGNN = 0.99 is narrow, suggesting that most configurations are either severely underparameterized or inefficiently overparameterized. Only a small region supports a cost-effective, highly expressive subnetwork, where careful tuning of width and sparsity relative to dataset and architectural properties affects γRGNN .

To complement Figure 2(a), in Figure 4, we perform a per-factor study of bound tightness using the same synthetic multi-relational graph generator and the same simple, randomly initialized, untrained RGNN as above. Unless varied, we fix the common hidden width and remaining dataset/model parameters to (m, |Dsyn |, n, L, |R|) = (16, 30, 6, 3, 3), and sweep m, n, |Dsyn |∈ {4, 8, 16, 32, 64}, and L, |R|∈ {2, 4, 6, 8, 10} one at a time. For each configuration, we evaluate 50 uniformly spaced sparsity levels ρ ∈ [0.01, 0.99]. At each ρ, we estimate γempirical and γRGNN from 10 independently sampled pruning masks and associated statistics, respectively. R We summarize tightness by the integrated absolute gap |γempirical (ρ) − γ RGNN (ρ)| dρ ≈ P (see Figure 2(a)), so smaller values indicate ∆ (ρ) γ ρ closer agreement between γRGNN and γempirical . Figure 5(a) relates compression ratio, test performance and separability ratio of the untrained, pruned model, measured (i) at the node level after the final message-passing step for local and global TGNNs on the node-classification benchmark tgbn-trade (Huang et al., 2023a), and (ii) at the graph level for XIMP on one polaris ADMET (HLM) and potency (pIC50 MERS-CoV Mpro) regression benchmark (ASAP Discovery x OpenADMET, 2025a;b) each. Motivated by Figure 2(a), we sweep pruning ratios ρ over 200 uniformly spaced values in [0.0, 0.995], with 5 samples per ρ. We train XIMP for 50 epochs and the TGNNs for 10 epochs, using width 16 for all learnable transformations. Figure 5(b) shows the same setup but from a probabilistic perspective. We estimate, for each model-dataset pair, the probability that a pruned model achieves test performance within a small margin of its dense counterpart, conditioned on its

Figure 2(a) compares mean γ RGNN to γempirical . The bound is tight when expressivity holds with high probability (roughly ρ ≲ 0.65 here), becomes more conservative in the transition region where expressivity fails (approx. 1 Code for reproducing results and figures is available at GitHub: https://github.com/lorenz0890/relational_selth

| emp.

RGNN | d

A Unifying Relational Perspective on Expressive Lottery Tickets

(a)

(b)

(c)

(d)

(e)

0.50 0.25 4 8 16

64 4 8 16

| syn |

64 4 8 16

64 2

10 2

| |

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.

(a)

(b)

1.0

TGNNloc /trade TGNNglob /trade

log10 (p)

P(WT|Sep. )

103

0.5

101 1

Spearman's sm .

0.0

XIMP/admet XIMP/potency 0

Separability

Figure 2(b) shows that higher pre-training separability is associated with stronger gradient flow, lower final training loss, and higher final training accuracy. Figure 3 strengthens this conclusion. Even at fixed sparsity, higher pre-training separability remains significantly associated with stronger gradient flow and lower final loss across all tested sparsity levels, and with higher accuracy at the higher sparsity levels. Thus, the optimization trend in Figure 2(b) is not merely a byproduct of larger subnetworks, but persists in a within-sparsity comparison as well. This matches Section 3’s optimization discussion: masks that preserve more label-relevant distinctions at initialization retain more gradient-connected paths, so loss signals reach more surviving weights. Moreover, this aligns with the hypothesis that more expressive sparse RGNN initializations are easier to optimize, which is consistent with Kummer et al. (2025b)’s empirical findings and theoretical Gradient Diversity (Yin et al., 2018) analysis for classic GNNs. Figure 5 further supports this on real-world benchmarks and practical architectures: pre-training separability correlates with and predicts test-set performance and is anticorrelated with pruning compression. In practice, this highlights the importance of expressivity-aware sparsification for finding winning lottery tickets.

Sep., Perf. Sep., Comp. Perf., Comp. P(WT|Sep. )

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 , − log10 p) (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).

ρ ∈ [0.65, 0.95]), and tightens again as success vanishes for ρ → 1. The observed variations of γ RGNN in Figure 2(a) reflect the dependency of γRGNN on statistics obtained from concrete model and mask instantiations. This matches the standard deviation (0.18) of the empirical fraction of distinguishable graphs over ρ ∈ [0.65, 0.95]. Figure 4 studies bound tightness through the integrating the gap ∆γ . The clearest effect is width: as m increases, the gap decreases, indicating that once the model is sufficiently overparameterized, the lower bound tracks the empirical success curve more closely. Increasing |Dsyn | has the opposite effect and makes the guarantee more conservative, which is consistent with the need to control more witnessed inputs and distinctions on the finite Dsyn . The trends with n and |R| require more caution. In our setup, varying n and |R| does not only change a single quantity in the bound; it also changes the synthetic graphs generated (see Appendix G), and, therefore, the witnessed statistics used to instantiate γRGNN . Hence, a smaller gap in panels (c) and (e) should not be read as saying that larger graphs or more relations intrinsically improve the lower bound itself. Rather, these changes move the sparsity regimes in which both γemp. and γ RGNN curves are closer (compare Figure 2(a)). Thus, Figure 4 complements rather than contradicts Figure 1: Figure 1 analyzes how the bound varies as a function of its governing quantities, whereas Figure 4 measures how well the instantiated bound matches empirical behavior for a specific construction.

5. Conclusion We introduce RSELTH, proving that sufficiently wide RGNNs contain sparse subnetworks that match 1-RWL expressivity on any finite dataset and deriving an explicit lower bound γRGNN on the probability that a random pruning mask yields such a subnetwork. We show the theory extends to TGNNs and XIMP/HIMP-type architectures. Our results indicate that (i) γRGNN is tight in the high- and low-success regimes and becomes most conservative near the critical sparsity threshold where expressivity breaks down, (ii) only a narrow band of width–sparsity configurations yields costefficient, highly expressive sparse initializations, (iii) the attainable expressivity at fixed width and sparsity depends strongly on dataset complexity and (iv) more expressive sparse initializations can be easier to optimize. Together, our results position RSELTH as a unifying perspective on sparse, expressive RGNNs and TGNNs and beyond. 9

A Unifying Relational Perspective on Expressive Lottery Tickets

Acknowledgements

Cheung, M. and Moura, J. M. Graph neural networks for covid-19 drug discovery. In IEEE International Conference on Big Data, pp. 5646–5648, 2020.

This work was supported in part by the Vienna Science and Technology Fund (WWTF) and the City of Vienna through grants [10.47379/VRG19009] and [10.47379/ICT22059].

Chuang, Y.-N., Lai, K.-H., Tang, R., Du, M., Chang, C.-Y., Zou, N., and Hu, X. Fair-rgnn: Mitigating relational bias on knowledge graphs. ACM Trans. Knowl. Discov. Data, 19(2), February 2025. ISSN 1556-4681. doi: 10.1145/3681792. URL https: //doi.org/10.1145/3681792.

Impact Statement This work advances the theoretical understanding of how parameter sparsity interacts with expressivity in relational and temporal graph neural networks. By clarifying when random pruning can preserve discriminative power, the results may support the design of more compute- and memory-efficient graph models, which can reduce deployment costs and energy use in applications where graph learning is already standard.

da Cunha, A., Natale, E., and Viennot, L. Proving the strong lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations (ICLR), 2022. Deng, L., Li, G., Han, S., Shi, L., and Xie, Y. Model compression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 108(4):485–532, 2020.

The methods studied here are general and could be applied to sensitive relational or temporal data (e.g., social, financial, or behavioral graphs). Improved efficiency can lower the barrier to deploying such models at scale, which may amplify risks around privacy, profiling, or biased decision-making if used without appropriate safeguards.

Ehrlich, A., Kummer, L., Voracek, V., Bause, F., and Kriege, N. M. XIMP: Cross graph inter-message passing for molecular property prediction. CoRR, abs/2601.19037, 2026.

Our contributions do not introduce new data collection or new capabilities targeted at a specific domain, and they do not address fairness, privacy, or security directly. Practitioners should treat the theory as one component in a broader responsible pipeline, including dataset governance, privacy-preserving training where appropriate, and domain-specific evaluations for bias and misuse.

Evci, U., Ioannou, Y., Keskin, C., and Dauphin, Y. Gradient flow in sparse neural networks and how lottery tickets win. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6577–6586, 2022. Fey, M., Yuen, J.-G., and Weichert, F. Hierarchical inter-message passing for learning on molecular graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workshop, 2020.

References

Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations (ICLR), 2019.

Amir, T., Gortler, S., Avni, I., Ravina, R., and Dym, N. Neural injective functions for multisets, measures and graphs via a finite witness theorem. In Advances in Neural Information Processing Systems (NeurIPS), pp. 42516–42551, 2023. ASAP Discovery x OpenADMET. Antiviral ADMET 2025. Data set, 2025a. URL https://polarishub. io/competitions/asap-discovery/ antiviral-admet-2025. License: CC0-1.0. ASAP Discovery x OpenADMET. Antiviral potency 2025. Data set, 2025b. URL https://polarishub. io/competitions/asap-discovery/ antiviral-potency-2025. License: CC-BY-4.0. Barceló, P., Galkin, M., Morris, C., and Orth, M. R. Weisfeiler and Leman go relational. In Rieck, B. and Pascanu, R. (eds.), Proceedings of the First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, pp. 46:1–46:26. PMLR, 09–12 Dec 2022. URL https://proceedings.mlr.press/ v198/barcelo22a.html.

Frankle, J., Dziugaite, G. K., Roy, D. M., and Carbin, M. Stabilizing the lottery ticket hypothesis. CoRR, abs/1903.01611, 2019. Gao, J. and Ribeiro, B. On the equivalence between temporal and static equivariant graph representations. In International Conference on Machine Learning (ICML), pp. 7052–7076. PMLR, 2022. Gao, J., Lyu, T., Xiong, F., Wang, J., Ke, W., and Li, Z. Predicting the survival of cancer patients with multimodal graph neural network. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(2):699–709, 2022. Heeg, F., Sauer, J., Mutzel, P., and Scholtes, I. Weisfeiler and Leman follow the arrow of time: Expressive power of message passing in temporal event graphs. arXiv preprint arXiv:2505.24438, 2025. Huang, S., Poursafaei, F., Danovitch, J., Fey, M., Hu, W., Rossi, E., Leskovec, J., Bronstein, M., Rabusseau, G., and Rabbany, R. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems (NeurIPS), 36:2056–2073, 2023a.

Beddar-Wiesing, S., D’Inverno, G. A., Graziani, C., Lachi, V., Moallemy-Oureh, A., Scarselli, F., and Thomas, J. M. Weisfeiler-Lehman goes dynamic: An analysis of the expressive power of graph neural networks for attributed and dynamic graphs. Neural Networks, 173:106213, 2024.

Huang, X., Orth, M. R., Ceylan, İ. İ., and Barceló, P. A theory of link prediction via relational weisfeiler-Leman on knowledge graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2023b. URL https://openreview. net/forum?id=7hLlZNrkt5.

Chen, T., Sui, Y., Chen, X., Zhang, A., and Wang, Z. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning (ICML), pp. 1695–1706, 2021.

A Unifying Relational Perspective on Expressive Lottery Tickets Hui, B., Yan, D., Ma, X., and Ku, W.-S. Rethinking graph lottery tickets: Graph sparsity matters. In International Conference on Learning Representations (ICLR), 2023.

Rusch, T. K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993, 2023.

Jin, W., Barzilay, R., and Jaakkola, T. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning (ICML), volume 80 of PMLR, 2018. URL https://proceedings.mlr.press/v80/ jin18a.html.

Schlichtkrull, M., Kipf, T. N., Bloem, P., Van Den Berg, R., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593–607. Springer, 2018. Souza, A., Mesquita, D., Kaski, S., and Garg, V. Provably expressive temporal graph networks. Advances in Neural Information Processing Systems (NeurIPS), 35:32257–32269, 2022.

Kummer, L., Sidak, K., Reichmann, T., and Gansterer, W. N. Adaptive precision training (AdaPT): A dynamic quantized training approach for DNNs. In SIAM International Conference on Data Mining (SDM), pp. 559–567, 2023.

Stiefl, N., Watson, I., Baumann, K., and Zaliani, A. ErG: 2d pharmacophore descriptions for scaffold hopping. Journal of Chemical Information and Modeling, 46:208–20, 2006. doi: 10.1021/ci050457y.

Kummer, L., Gansterer, W. N., and Kriege, N. M. On the relationship between robustness and expressivity of graph neural networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2025a.

Sui, Y., Wang, X., Chen, T., Wang, M., He, X., and Chua, T.S. Inductive lottery ticket learning for graph neural networks. Journal of Computer Science and Technology, 2023.

Kummer, L., Moustafa, S., Ehrlich, A., Bause, F., Suess, N., Gansterer, W. N., and Kriege, N. M. Weisfeiler and Leman go gambling: Why expressive lottery tickets win. In International Conference on Machine Learning (ICML), 2025b. URL https://openreview.net/forum?id= 7EtP9u7JNw.

Sun, Z., Yin, H., Chen, H., Chen, T., Cui, L., and Yang, F. Disease prediction via graph neural networks. IEEE Journal of Biomedical and Health Informatics, 25(3):818–826, 2021. Tsitsulin, A. and Perozzi, B. The graph lottery ticket hypothesis: Finding sparse, informative graph structure. CoRR, abs/2312.04762, 2023.

Longa, A., Lachi, V., Santin, G., Bianchini, M., Lepri, B., Lio, P., Scarselli, F., Passerini, A., et al. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Trans. Mach. Learn. Res., 2023:1–24, 2023.

Vashishth, S., Sanyal, S., Nitin, V., and Talukdar, P. P. Compositionbased multi-relational graph convolutional networks. In International Conference on Learning Representations (ICLR), 2020.

Lu, H. and Uddin, S. A weighted patient network-based framework for predicting chronic diseases using graph neural networks. Scientific reports, 11(1):22607, 2021.

Wał˛ega, P. A. and Rawson, M. Expressive power of temporal message passing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 21000–21008, 2025.

Luo, Y. and Li, P. Neighborhood-aware scalable temporal network representation learning. In Learning on Graphs Conference, pp. 1–1. PMLR, 2022.

Wang, K., Liang, Y., Wang, P., Wang, X., Gu, P., Fang, J., and Wang, Y. Searching lottery tickets in graph neural networks: A dual perspective. In International Conference on Learning Representations (ICLR), 2023.

Malach, E., Yehudai, G., Shalev-Schwartz, S., and Shamir, O. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning (ICML), pp. 6682–6691, 2020.

Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):513–530, 2018.

Morris, C., Fey, M., and Kriege, N. The power of the WeisfeilerLeman algorithm for machine learning with graphs. In International Joint Conference on Artificial Intelligence (IJCAI), pp. 4543–4550, 2021.

Xiong, J., Xiong, Z., Chen, K., Jiang, H., and Zheng, M. Graph neural networks for automated de novo drug design. Drug Discovery Today, 26(6):1382–1393, 2021.

Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. Weisfeiler and Leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333):1–59, 2023.

Xu, D., Ruan, C., Korpeoglu, E., Kumar, S., and Achan, K. Inductive representation learning on temporal graphs. In International Conference on Learning Representations, 2020. URL https: //openreview.net/forum?id=rJeW1yHYwH.

Puthawala, M., Kothari, K., Lassas, M., Dokmanić, I., and De Hoop, M. Globally injective ReLU networks. Journal of Machine Learning Research, 23(1):4544–4598, 2022.

Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.

Qu, L., Zhu, H., Duan, Q., and Shi, Y. Continuous-time link prediction via temporal dependent graph neural network. In Proceedings of the Web Conference 2020, pp. 3026–3032, 2020.

Yan, J., Ito, H., García-Arias, Á. L., Okoshi, Y., Otsuka, H., Kawamura, K., Van Chu, T., and Motomura, M. Multicoated and folded graph neural networks with strong lottery tickets. In Learning on Graphs Conference (LoG), pp. 11–1, 2024.

Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., and Bronstein, M. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637, 2020.

A Unifying Relational Perspective on Expressive Lottery Tickets Yin, D., Pananjady, A., Lam, M., Papailiopoulos, D., Ramchandran, K., and Bartlett, P. Gradient diversity: a key ingredient for scalable distributed learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1998–2007, 2018. Yuxin, W., Xiannian, H., Jiaqing, X., Zhangyue, Y., Yunhua, Z., Xipeng, Q., and Xuanjing, H. Graph structure learning via lottery hypothesis at scale. In Asian Conference on Machine Learning, pp. 1401–1416, 2024. Zaheer, M., Kottur, S., Ravanbakhsh, S., Póczos, B., Salakhutdinov, R., and Smola, A. J. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3391–3401, 2017. Zhang, G., Wang, K., Huang, W., Yue, Y., Wang, Y., Zimmermann, R., Zhou, A., Cheng, D., Zeng, J., and Liang, Y. Graph lottery ticket automated. In International Conference on Learning Representations (ICLR), 2024. Zhang, S., Wang, M., Liu, S., Chen, P.-Y., and Xiong, J. Why lottery ticket wins? a theoretical perspective of sample complexity on sparse neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2707–2720, 2021a. Zhang, Z., Jin, J., Zhang, Z., Zhou, Y., Zhao, X., Ren, J., Liu, J., Wu, L., Jin, R., and Dou, D. Validating the lottery ticket hypothesis with inertial manifold theory. In Advances in Neural Information Processing Systems (NeurIPS), pp. 30196–30210, 2021b. Zopf, M. 1-WL expressiveness is (almost) all you need. In International Joint Conference on Neural Networks (IJCNN), pp. 1–8, 2022.

A Unifying Relational Perspective on Expressive Lottery Tickets

A. TGNN → RGNN via refined relational alphabet e ⋆ (T G) using an augmented relation alphabet is a little more intricate. For a fixed temporal The construction of a K graph T G = ((G1 , t1 ), . . . , (Gn , tn )) in D with strictly increasing timestamps, let the finite set of realized gaps as ∆(T G) := { tj − ti | 1 ≤ i ≤ j ≤ n, and there is a corresponding edge in K⋆ (T G) }. Furthermore, let σ : ∆(T G) → {1, . . . , B} be any injective enumeration of these gaps (with B := |∆(T G)|). We define the refined relation alphabet e := { (r, b) | r ∈ {0, . . . , n−1}, b ∈ {1, . . . , B}, and ∃ i ≤ j : j−i = r, σ(tj −ti ) = b }. We then form a as R e ⋆ (T G) = (V time , Ė ⋆ , λtime , τ̃ ⋆ ) by keeping the same node set and directed edge refined temporal knowledge graph K e Then, set as in K⋆ (T G), but labeling each edge ((v, ti ) → (u, tj )) by τ̃ ⋆((v, ti ), (u, tj )) := (j−i, σ(tj −ti )) ∈ R. − ⋆ e ⋆ (T G) as N we write the per-relation, per-direction neighborhoods on K = { y | τ̃ (x, y) = (r, b) } and (r,b) (x) + ⋆ N(r,b) (x) = { y | τ̃ (y, x) = (r, b) }. Lemma A.1. Let ⋆ ∈ {glob, loc} and a TGNN layer as in Eqs. (4)-(5) with maps Ωa , Ωc , Φ(l) , Ξ, ζ. Consider the RGNN e ⋆ (T G) with relation alphabet R. e There exist per-relation message instantiated on the refined temporal knowledge graph K (l) maps Φ(r,b),± : Rd → Rd and a combiner Γ(l) (same as in Eq. (5)) such that, for all x ∈ V time , (l) (l) − m(r,b),− (x) = Ωa {{Φ(r,b),− (h(l) y ) | y ∈ N(r,b) (x)}} , (l) (l) + m(r,b),+ (x) = Ωa {{Φ(r,b),+ (h(l) ) | y ∈ N (x)} } , y (r,b) (l) h(l+1) = Γ(l) Ωc ({{h(l) x x }} ⊎ M (x)) . U (l) (l) with M(l) (x) := s∈R e {{ms,− (x), ms,+ (x)}} and these updates exactly match those of the original TGNN on T G (global or local, respectively). Proof. Let x = (v, tj ) ∈ V time and ⋆ ∈ {glob, loc}. Let N⋆ (x) denote the multiset of neighbors used by the TGNN aggregation at x in Eq. (4): for ⋆ = glob, N⋆ (x) = {(u, ti ) | {u, v} ∈ Ei , i ≤ j}; for ⋆ = loc, N⋆ (x) = {(u, tj ) | ∃ i ≤ j : {u, v} ∈ Ei }. Each y ∈ N⋆ (x) is associated with a unique index lag r = j − i and a realized time gap ∆ = tj − ti . By construction of the e we assign a bucket b = σ(∆) to ∆. Hence every neighbor y determines a unique triple augmented relation alphabet R, e ⋆ (T G) enters or leaves x. (r, b, ▷), whereby ▷ ∈ {+, −} indicates whether the corresponding directed edge in K This induces a disjoint partition of N⋆ (x) into the per-relation/per-direction neighborhoods ] + − N⋆ (x) = N(r,b) (x) ⊎ N(r,b) (x) , e (r,b)∈R ±

e ⋆ (T G), N ± (x) = { y ∈ V time | (r, b) is the edge type and y → x }. where, by definition of K (r,b) For each bucket b fix the (unique) gap value realized on that bucket at x and denote it by ∆b . Define the per-relation message maps (l) Φ(r,b),± (h) := Φ(l)( Ξ(h, ζ(∆b )) ). ± Because every y ∈ N(r,b) (x) has the same index lag r and the same realized gap ∆b , we obtain

(l) ± ± (l) (l) Ωa {{Φ(r,b),± (h(l) ) | y ∈ N (x) } } = Ω , ζ(∆ ))) | y ∈ N (x)} } { {Φ (Ξ(h a b y y (r,b) (r,b) (l)

for parameterizations of Φ(r,b),± suitable to the choice of Ξ, ζ (e.g., ∥, ∆b , respectively, consistent with Wał˛ega & Rawson (2025). ± Given ζ(∆b ) = ζ(tj − ti ) for all y ∈ N(r,b) (x), the right-hand side is exactly the contribution that the original TGNN ± aggregation, Eq. (4), would collect from the subset N(r,b) (x) of neighbors.

A Unifying Relational Perspective on Expressive Lottery Tickets + − Since {N(r,b) (x), N(r,b) (x)}(r,b) forms a disjoint partition of the TGNN’s neighborhood N⋆ (x), aggregating within each block by Ωa and then feeding the family of block summaries to the combiner reproduces the TGNN’s total message: the multiset {{Φ(l)(Ξ(h(l) y , ζ(tj − ti ))) | y ∈ N⋆ (x)}} (l)

(l)

± is the disjoint multiset union of the blockwise multisets {{Φ(r,b),± (hy ) | y ∈ N(r,b) (x)}}. Therefore, with the same Ωc and

Γ(l) as in (5), the update ] (l) (l) h(l+1) = Γ(l) Ωc ( {{h(l) {{m(r,b),− (x), m(r,b),+ (x)}} ) x x }} ⊎ (r,b) (l)

(l)

coincides with applying Γ(l) to the combine of hx and the TGNN’s one-shot aggregate mtj (v) from (4). Hence the relational layer above reproduces exactly the original TGNN layer on T G (for both glob and loc). While correct and allowing for the unifying perspective through RSELTH similar as Lemma 3.3, as Theorem 3.1 applies verbatim to the above RGNN, this reduction has a drawback: the resulting sparsity (pruning) masks for the RGNN do not, in general, trivially transfer back to the original TGNN, as handling the δij present in Eqs. (4)-(5) in the RGNN framework given by Eqs. (1)-(3) requires a refinement of the relation alphabet along with an associated extended parameterization.

B. Temporal SELTH (TSELTH) While Temporal SELTH as stated below in Theorem B.1 directly follows from the RGNN reformulation discussed in the main paper, we provide a reformulation and standalone proof for completeness. Theorem B.1 (Temporal SELTH). Let D be a finite collection of finite temporal graphs. Let Ψ(L) be a corresponding sufficiently overparameterized depth-L TGNN of the pattern described either in Eqs. (4)-(5).Then, for M ∼i.i.d. B(1 − ρ), b 0 = M ⊙ Θ0 of Ψ(L) , the following holds for all T Ga , T Gb ∈ D, Θ0 ∼ Ucd and corresponding sparse initialization Θ K⋆ (T Ga ) ̸≃RWL(L) K⋆ (T Gb ) ⇐⇒

(9)

b (L) (T Ga ) ̸= Ψ b (L) (T Gb ) Ψ b ,⋆ b ,⋆ Θ Θ

(10)

with a probability at least γTGNN > 0. Proof. For any local or global TGNN, Lemma A.1 implies that, at layer l, the set of inputs that the message MLP Φ(l) actually receives across D is given by o [ [ [ n ▷ S (l) := Ξ(h(l) y , ζ(∆(y, x))) y ∈ N(r,b) (x) , T G∈D x∈V time (T G) (r,b,▷) ▷ where (r, b, ▷) ranges over the per-lag, per-bucket, per-direction neighborhoods N(r,b) (·) on K̃⋆ (T G) (see Lemma A.1), and ∆(y, x) is the time gap used by the TGNN.

On a finite D over finite temporal graphs, Nl := |S (l) | is likewise finite. Let the minimum ℓ0 -separation across distinct inputs be sl := min′ ∥z − z ′ ∥0 (≥ 1). z̸=z z,z ′ ∈S (l)

Consider the MLP with width ml and a Bernoulli pruning mask whose entries are 0 independently with probability ρ ∈ (0, 1) (sparsity ratio). By Lemma A.1 in Kummer et al. (2025b), the masked map is injective on Sl with probability at least Nl γl ≥ 1 − ρ sl ml . 2 and the layer is injective with probability γllayer ≥ 1 −

Nl Nl,comb ρ sl ml − ρ sl,comb ml,comb , 2 2 14

A Unifying Relational Perspective on Expressive Lottery Tickets

where (·)comb refers to the combine MLP. As in Theorem 3.1, we define for the combine MLP the input multiset Ml (which here is similarly the finite multiset of possible branch summaries), width ml,comb , Nl,comb = |Ml | and sl,comb := min′ ∥z − z ′ ∥0 (≥ 1). z̸=z z,z ′ ∈Ml

If we use independent masks across all MLP blocks, and take a conservative worst-case bound with Nmax := max Nl ,

smin := min sl ,

mmin := min ml , l

Nmax,comb := max Nl,comb ,

smin, := min sl,comb , mmin,comb := min ml,comb , l l Nmax smin mmin then each branch is injective with probability at least 1 − ρ and each combination with probability at least 2 s min,comb mmin,comb 1 − Nmax,comb ρ . For M = 1 MLP sublayers per MP layer and L MP layers, without relational branch 2 MLPs as in Theorem 3.1, the crude product lower bound for TGNNs simplifies to ! L Nmax Nmax,comb smin mmin smin,comb mmin,comb γTGNN ≥ [ 1 − ρ ]+ [1 − ρ ]+ 2 2 l

with [x]+ := max{x, 0} and furthermore to e L Nmax e min γ eTGNN ≥ [1 − ρ semin m ]+ , 2

with emax := max{Nmax , Nmax,comb }, N

semin := min{smin , smin,comb },

m e min := min{mmin , mmin,comb }.

By the same argument as in Theorem 3.1, we argue this estimate is conservative; so for fixed Nmax , smin and their combine or e· counterparts, one can pick m such that γTGNN > 0.

C. TSELTH Node Level Transfer The transfer is possible because 1-RWL (and its temporal variants via K⋆ (T G)) operates fundamentally through iterative node color refinement: nodes with distinct k-hop relational or temporal neighborhoods receive distinct colors (Corollary 2.2), encoding their structural roles. In sparse subnetworks under SELTH, the preservation of injective aggregation and combi(L) nation functions ensures that node embeddings hx remain distinct for such nodes, providing the discriminative features needed for node-level predictions. Lemma C.1. Fix ⋆ ∈ {glob, loc} and depth L. Consider a TGNN of the form Eqs. (4)-(5) with (i) an injective label encoder, (ii) injective Φ(l) and Γ(l) on the finite input sets they actually witness on a finite dataset D, and (iii) Ωa , Ωc chosen as P injective multiset encoders on those finite domains (e.g., with a linearly independent codebook (see Remark 2.1)). Then for every T G ∈ D and every k ≤ L there exists an injective ηk such that for all timestamped nodes x (k)

h(k) = ηk (cK⋆ (T G) (x)). x (k)

(k)

In particular, if cK⋆ (T G) (x) ̸= cK⋆ (T G) (x′ ), then hx ̸= hx′ under the same parameters. Proof. We proceed by induction on k. (0)

Base case (k = 0). By definition of directed 1-RWL on K⋆ (T G), the initial color is cK⋆ (T G) (x) = λtime (x). The TGNN (0)

(0)

initializes hx = Λ(λtime (x)) with an injective label encoder Λ. Hence setting η0 := Λ gives hx = η0(cK⋆ (T G) (x)), and η0 is injective. (k)

(k)

Inductive step. Assume for some k ≥ 0 there exists an injective ηk such that hy = ηk(cK⋆ (T G) (y)) for all timestamped nodes y. Fix x = (v, tj ) ∈ V time . In the global/local TGNN, aggregation ranges over the temporal neighborhood N (v, tj ) 15

A Unifying Relational Perspective on Expressive Lottery Tickets

as in Eq. (4). By construction of K⋆ (T G), each (u, ti ) ∈ N (v, tj ) with i ≤ j appears as an incoming edge (u, ti ) → (v, tj ) labeled by the unique index lag r = j − i. Writing Nr+ (x) := { (u, ti ) | (u, ti ) → (v, tj ) in K⋆ (T G), j−i = r }, we obtain a disjoint partition of the temporal neighborhood by lag: N (v, tj ) =

j−1 ]

Nr+ (x),

r=0

and, moreover, δ((u, ti ), x) = tj − ti is constant on each slice Nr+ (x) (namely tj − ti with j − i = r). Consequently, we may equivalently index the aggregation by the per-lag, per-direction neighborhoods Nr▷ (x) of K⋆ (T G), which matches the directed 1-RWL bookkeeping; the same reasoning applies to the outgoing branch ▷ = − if present. For each relation r and direction ▷ ∈ {+, −} on K⋆ (T G), define (k)

(k)

Ar,▷ (x) := {{ cK⋆ (T G) (y) | y ∈ Nr▷ (x) }} (k)

and

(k)

▷ Hr,▷ (x) := {{ h(k) y | y ∈ Nr (x) }}.

(k)

By the induction hypothesis, elementwise hy = ηk(cK⋆ (T G) (y)) on the finite dataset D, so (as multisets) (k)

(k)

Hr,▷ (x) = ηk[Ar,▷ (x)], where ηk [·] acts elementwise. Apply the layer’s elementwise message map and relation/direction aggregator: (k)

(k)

▷ (k) mr,▷ (x) = Ωa( {{ Φ(k) (h(k) y ) | y ∈ Nr (x) }}) = Ωa( {{ Φ (ηk (a)) | a ∈ Ar,▷ (x) }}) . | {z } (k) (k) := Fr,▷ (Ar,▷ (x))

By assumption, Φ(k) is injective on the finite set ηk (Im c(k) ) actually witnessed on D, and Ωa is an injective multiset encoder on the corresponding finite domain (e.g., sum over a linearly independent codebook; cf. Remark 2.1). Therefore (k) (k) Fr,▷ is injective on the finite family of multisets Ar,▷ (x) realized on D. Next, combine the self-embedding and all per-(r, ▷) messages: ] ] (k) (k) (k) (k) (k) (k) (k) h(k+1) = Γ Ω ({{ h }} ⊎ {{ m (x) }}) = Γ Ω ({{ η (c (x)) }} ⊎ {{ F (A (x)) }}) . r,▷ r,▷ r,▷ c c k x x r,▷

r,▷

By assumption, Ωc is injective on the finite domain of inputs realized on D, and Γ(k) is injective there as well. Moreover, (k) since each Fr,▷ is injective and we retain the (r, ▷) tags, the map from the refinement input (k) (k) c(k) (x), (Ar,− (x))r , (Ar,+ (x))r (k)

to all per-relation/per-direction messages mr,▷ (x) (for r ∈ R and ▷ ∈ {+, −}) is injective. Applying the injective Ωc to this indexed tuple and then the injective Γ(k) preserves injectivity, so the right-hand side is an injective function of the above refinement input, which is precisely the directed 1-RWL refinement input at x on K⋆ (T G). As the 1-RWL color update (k+1) (k) (k) cK⋆ (T G) (x) = Υ3 c(k) (x), (Ar,− (x))r , (Ar,+ (x))r uses an injective Υ3 on this finite domain, we can define ηk+1 on the set of (k+1)-colors actually realized on D by ] (k+1) (k) (k) ηk+1(cK⋆ (T G) (x)) := Γ(k) Ωc ({{ ηk (c(k) (x)) }} ⊎ {{ Fr,▷ (Ar,▷ (x)) }}) . r,▷

This is well-defined (equal colors correspond to equal refinement inputs) and injective (distinct colors correspond to distinct (k+1) (k+1) refinement inputs and the outer map is injective), and we have hx = ηk+1(cK⋆ (T G) (x)). (k)

(k)

By induction, for every k ≤ L there exists an injective ηk with hx = ηk(cK⋆ (T G) (x)) for all timestamped nodes x. In (k)

(k)

particular, for any x, x′ , if cK⋆ (T G) (x) ̸= cK⋆ (T G) (x′ ), then hx ̸= hx′ under the same parameters. 16

A Unifying Relational Perspective on Expressive Lottery Tickets

By Theorem B.1, on any finite D there exists a sparse mask M that preserves the layerwise injectivity conditions above. Therefore, Lemma C.1 continues to hold under the same sparse support M .

D. Proofs (Main Paper) Complete proofs for all theoretical claims made in the main paper are given below. The proofs for theoretical claims made in the appendix are given directly below the respective claim. D.1. Proof of Corollary 2.2 Corollary 2.2 is effectively a concise summary of Theorems 2 to 6 proven by Wał˛ega & Rawson (2025). Proof. Let a temporal graph T G and timestamped nodes x = (v, ti ), x′ = (u, tj ) ∈ V time , and let ⋆ ∈ {glob, loc} match the TGNN MP type. (⇒) By Theorem 2 (global) and Theorem 5 (local) of Wał˛ega & Rawson (2025), directed 1-RWL on K⋆ (T G) upper-bounds (k) (k) any MP-TGNN of the corresponding type. In our notation this reads: if cK⋆ (T G) (x) = cK⋆ (T G) (x′ ), then there exists a (k)

(k)

TGNN layer of the form (4) with combiner (5) for which we have hx = hx′ , which implies the existence of corresponding parameters. (⇐) By Theorem 3 (global) and Theorem 6 (local) of Wał˛ega & Rawson (2025), there exists a TGNN of the corresponding architectural form such that, layerwise, be mapped 1-to-1 to the 1-RWL colors on K⋆ (T G). Instantiating P embeddings can our layer class (4), (5) with Ωa = and choosing Φ(l) , Γ(l) as in the referred constructions, hence implies the existence of parameters for which (k)

h(k) x = hx′

⇐⇒

(k)

cK⋆ (T G) (x) = cK⋆ (T G) (x′ ).

This proves the bi-implication for some parametrization of any TGNN of the examined class. D.2. Proof of Lemma 3.2 Proof. Let ⋆ ∈ {glob, loc} and T Ga , T Gb ∈ D and assume K⋆ (T Ga ) ̸≃RWL(L) K⋆ (T Gb ). Then their L-step 1-RWL color multisets on K⋆ differ: (L)

(L)

{{ cK⋆ (T Ga ) (x) | x ∈ V time (T Ga ) }} ̸= {{ cK⋆ (T Gb ) (x) | x ∈ V time (T Gb ) }}. (L)

By Corollary 2.2, there exists a parametrization of the (local/global) TGNN such that, layerwise, hx for some injective ψL . Consequently, the two multisets of node embeddings differ.

(L)

= ψL(cK⋆ (T G) (x))

LetPthe TGNN’s graph readout χ be permutation-invariant and injective on finite multisets; for instance, χ({{hx }}) = α( x hx ), where α is injective (e.g., a suitable MLP (Amir et al., 2023; Puthawala et al., 2022)) and the codebook (see Remark 2.1) {ψL (·)} is chosen linearly independent, which makes the sum an injective multiset encoder (Zaheer et al., 2017). Then (L)

(L)

time time ΨΘ,⋆ (T Ga ) = χ({{h(L) (T Ga )}}) ̸= χ({{h(L) (T Gb )}}) = ΨΘ,⋆ (T Gb ), x |x∈V x |x∈V

for suitable Θ as claimed. (L)

(L)

Conversely, assume ΨΘ,⋆ (T Ga ) ̸= ΨΘ,⋆ (T Gb ). By injectivity of χ, the underlying multisets of node embeddings must differ: time time {{h(L) (T Ga )}} ̸= {{h(L) (T Gb )}}. x |x∈V x |x∈V (L)

(L)

As hx = ψL (cK⋆ (T G) (x)) with injective ψL , the two color multisets at depth L must differ, hence K⋆ (T Ga ) ̸≃RWL(L) K⋆ (T Gb ). This establishes the claimed bi-implication for the chosen parameterization Θ. 17

A Unifying Relational Perspective on Expressive Lottery Tickets

D.3. Proof of Theorem 3.1 Proof. In R-GNN Ψ(L) , if each layer injectively aggregates separately per relation and per direction (Eq. (1)) and then applies an injective combine to the resulting tuple together with the node’s own embedding (Eq. (3)), the layer realizes exactly the 1RWL refinement step at the next iteration. This is the relational analogue of the criterion used in the static case (Kummer et al., 2025b), Lemma 2.1, which is based on the correspondence between 1-WL and GNN aggregation/combine injectivity (Xu et al., 2019). Stacking L such RGNN layers matches 1-RWL to depth L. Hence, we need to first show injectivity can be preserved under pruning. Let a finite dataset D (cardinality |D|) and a depth-L RGNN Ψ(L) . At any layer l and for any branch b (one per relation r ∈ R in the undirected case, or per relation/direction in the directed case), let Xl,b ⊂ Rnl,b denote the finite set of inputs that actually occur at branch b when propagating D up to layer l. We write Nl,b = |Xl,b | and let sl,b := min′ ∥x − x′ ∥0 (≥ 1), x̸=x x,x′ ∈Xl,b

(l)

be the minimum ℓ0 -separation across distinct inputs in Xl,b . Consider the branch MLP Φb with width ml,b and a Bernoulli pruning mask whose entries are 0 independently with probability ρ ∈ (0, 1) (sparsity ratio). By Lemma A.1 in Kummer et al. (2025b), which has the same distributional assumptions on parameters and pruning masks, the masked branch map is injective on Xl,b with probability at least Nl,b γl,b ≥ 1 − ρ sl,b ml,b . 2 Apply the same argument to every branch of layer l and to the combine MLP Γ(l) (whose input multiset Ml is the finite multiset of possible branch summaries) with width ml,comb , Nl,comb = |Ml | and sl,comb := min′ ∥x − x′ ∥0 (≥ 1). x̸=x x,x′ ∈Ml

Then, by a union bound one obtains a layer-level lower bound X Nl,b Nl,comb γllayer ≥ 1 − ρ sl,b ml,b − ρ sl,comb ml,comb , 2 2 b∈Bt

where Bl is the set of branches at layer l and (·)comb refers to the combine MLP. If we use independent masks across all MLP blocks, and take a conservative worst-case bound with Nmax := max Nl,b , l,b

Nmax,comb := max Nl,comb , l

smin := min sl,b , l,b

smin, := min sl,comb , l

mmin := min ml,b l,b

mmin,comb := min ml,comb , l

Nmax 2

s m then each branch is injective with probability at least 1 − ρ min min and each combination with probability at least Nmax,comb smin,comb mmin,comb 1− ρ . Counting M MLP sublayers per MP layer and L MP layers, with |Bl |= |R| (undirected) 2 or |Bl |= 2|R| (directed), a crude product lower bound is γRGNN ≥

! |B| M L Nmax N max,comb [1 − ρ smin mmin ]+ [1 − ρsmin,comb mmin,comb ]+ , 2 2

with [x]+ := max{x, 0}, where |B|= |R| or 2|R|, which further simplifies to e L (M |B|+1) Nmax e min γ eRGNN ≥ [1 − ρ semin m ]+ , 2 with emax := max{Nmax , Nmax,comb }, N

semin := min{smin , smin,comb }, 18

m e min := min{mmin , mmin,comb }.

A Unifying Relational Perspective on Expressive Lottery Tickets

This is conservative, as (i) earlier non-injectivity would shrink the finite input sets faced by later blocks, increasing their success probability and (ii) any increase of width m drives ρsm down exponentially, so for fixed Nmax , smin and their combine or e· counterparts, one can pick the width m of the pruned branch and combine MLPs such that γRGNN > 0 or γ eRGNN > 0. Consequentially, the random pruning of Ψ(L) can preserve 1-RWL expressivity under mild assumptions2 .

D.4. Proof of Lemma 3.4 Proof. We begin by first showing the following auxiliary Corollary:

Corollary D.1. Let f : V (Gai ) → V (Gbi ) be the timewise isomorphism’s snapshot-wise bijection and define f ′ : (v, tai ) 7→ (l) (l) (f (v), tbi ). Then for all l ∈ {0, . . . , L} and all x = (v, tai ) we have cK⋆ (T Ga ) (x) = cK⋆ (T Gb ) (f ′ (x)).

Proof. By Wał˛ega & Rawson (2025)’s Theorem 10, timewise-isomorphic timestamped nodes produce identical embeddings in any TGNN at every layer. Instantiate the specific local/global TGNN that (by the standard WL-characterisation used in (l) our Corollary 2.2) computes embeddings h(l) = ψl(cK⋆ (·) ) with ψl injective at each layer l. Applying Wał˛ega & Rawson (l)

(l)

(2025)’s Theorem 10 to this TGNN yields hx = hf ′ (x) , hence injectivity of ψl gives cK⋆ (T Ga ) (x) = cK⋆ (T Gb ) (f ′ (x)) for all l.

The map f ′ is a bijection between V time (T Ga ) and V time (T Gb ), so Corollary D.1 implies equality of the entire L-step color multisets, as stated. In particular, if one employs a permutation-invariant, multiset-injective graph readout χ for the final TGNN layer (e.g., a sum followed by an injective MLP), then applying χ to equal multisets yields equal graph-level (L) (L) outputs ΨΘ,⋆ (T Ga ) = ΨΘ,⋆ (T Gb ) for suitable Θ. D.5. Proof of Corollary 3.5 Proof. For each (G, {Ti , Si }) ∈ D, we build G⊕ as in Section 3. Then, by construction, stacking L relational layers on G⊕ (with the appropriate parameter choices) simulates L XIMP layers. As in the relational setup, we pick parameters so that at every layer l there exists an injective map ψl with e h(l) = ψl(c(l) ), where c(l) is the l-round 1-RWL color on G⊕ ; this is feasible on finite inputs using sum aggregation with a linearly independent codebook (see Remark 2.1) and injective (l) (l) Φr,+ , Φr,− , Γ(l) . ⊕ If G⊕ a ̸≃RWL(L) Gb , then their L-round color multisets differ. Injectivity of ψL implies the final-layer node-embedding multisets differ. With any permutation-invariant readout χ that is injective on finite multisets (e.g., sum followed by an injective MLP), the graph-level outputs differ:

(L)

ΨΘ (Ga , {Tia , Sia }) ̸= ΨΘ (Gb , {Tib , Sib }). (L)

(L)

Conversely, if ΨΘ (Ga , {Tia , Sia }) ̸= ΨΘ (Gb , {Tib , Sib }) under an injective χ, then the final-layer node-embedding ⊕ multisets must differ; by injectivity of ψL , the L-round 1-RWL color multisets differ, hence G⊕ a ̸≃RWL(L) Gb . Therefore, for suitable parameters, 1-RWL on G⊕ exactly characterizes the L-round distinguishing power of XIMP/HIMP on the finite collection D. 2

The non-colinearity result of Kummer et al. (2025b), Proposition 3.4, extends branch-wise to the relational block: with sufficiently wide layers and independently pruned weights, distinct inputs that are separated by the masked map almost surely produce non-colinear embeddings in each branch and after the combine, hence also at the graph readout.

A Unifying Relational Perspective on Expressive Lottery Tickets

D.6. Proof of Lemma 3.3 Proof. Fix ⋆ ∈ {glob, loc} and a temporal node x = (v, tj ) ∈ V time . Recall the TGNN aggregation and update from Eqs. (4)-(5): (l) (l) (global) mtj (v) = Ωa {{Φ(l)(Ξ(h(u,ti ) , ζ(δij ))) (u, ti ) ∈ N (v, tj )}} , (l) (l) (local) mtj (v) = Ωa {{Φ(l)(Ξ(h(u,tj ) , ζ(δij ))) (u, ti ) ∈ N (v, tj )}} , (l+1) (l) (l) h(v,tj ) = Γ(l) Ωc ({{h(v,tj ) }} ⊎ {{mtj (v)}}) , where δij = tj − ti and N (v, tj ) is the temporal neighborhood N (v, tj ) = {(u, ti ) | {u, v} ∈ Ei , i ≤ j}. On the knowledge-graph side, let K⋆ (T G) be the (directed, typed) temporal knowledge graph constructed for ⋆ as in the preliminaries, and define its edge-feature augmentation ξ(y→x) := ζ(δ(y, x)), where for y = (u, ti ) and x = (v, tj ) we e ⋆ (T G) with have δ(y, x) = tj − ti . As in the statement, instantiate the RGNN on K e (l) (h, ξ) = Φ(l) (Ξ(h, ξ)), Φ (l)

strict tying Φr,± ≡ Φ(l) across (r, ±), and the same (Ωa , Ωc , Γ(l) ). We now prove by induction on l that for all x = (v, tj ), (l)

(l)

h(v,tj ) (TGNN) = e h(v,tj ) (RGNN). (0)

Base case (l = 0). Both models use the same initialization h(v,tj ) = Λ(λtime (v, tj )), so the claim holds. (l) (l) Induction step. Assume h(·) = e h(·) for all timestamped nodes. Fix x = (v, tj ) and consider the multiset of incoming neighbors to x in K⋆ (T G), grouped by index lag r = j − i:

[

Nr+ (x)

with

Nr+ (x) = {(u, ti ) | (u, ti ) → (v, tj ) in K⋆ (T G), j−i = r}.

By construction of K⋆ (T G), for every (u, ti ) ∈ N (v, tj ) there is a unique index lag r = j−i ∈ {0, . . . , n−1} and a corresponding incoming edge of type r into x = (v, tj ): for ⋆ = glob the edge is (u, ti ) → (v, tj ), and for ⋆ = loc the edge is (u, tj ) → (v, tj ) but it is labeled by the witness snapshot i via r = j−i. Hence each temporal neighbor (u, ti ) belongs to exactly one lag class r, and the per-lag incoming neighborhoods form a disjoint (multi)set partition of the TGNN temporal neighborhood: ] N (v, tj ) = Nr+ (x) . r

Moreover, if (u, ti ) ∈ Nr+ (x) is the (unique) witness for lag r = j−i, then the realized time gap used by the TGNN is fixed on that block: δ((u, ti ), x) = tj − ti = δij . Define the RGNN’s per-lag incoming messages as (l) e (l) (e mr,+ (x) = Ωa {{Φ h(l) y , ξ(y→x) )

y ∈ Nr+ (x)}} .

(l) (l) Using ξ(y→x) = ζ(δ(y, x)) = ζ(δij ) and the induction hypothesis e hy = hy , we obtain, elementwise inside each Nr+ (x), (l) (l) e (l) (e Φ h(l) y , ξ(y→x) ) = Φ (Ξ(hy , ζ(δij ))).

Now distinguish the two TGNN cases: 20

A Unifying Relational Perspective on Expressive Lottery Tickets

• Global (Eq. (4)). Here y = (u, ti ) is precisely the embedding source used by the TGNN, so (l) (l) mr,+ (x) = Ωa {{Φ(l) (Ξ(h(u,ti ) , ζ(δij ))) (u, ti ) ∈ Nr+ (x)}} . • Local (Eq. (4)). By construction of Kloc (T G), Nr+ (x) contains the current-time counterparts (u, tj ); hence (l) (l) mr,+ (x) = Ωa {{Φ(l) (Ξ(h(u,tj ) , ζ(δij ))) (u, ti ) ∈ Nr+ (x)}} . U Summing over lags and using the disjoint union N (v, tj ) = r Nr+ (x) yields ] (l) Ωa {{Φ(l) (Ξ(·, ζ(δij ))) (u, ti ) ∈ N (v, tj )}} = Ωa {{mr,+ (x)}} , | {z } r {z } | (l) TGNN mt (v)

RGNN combined incoming

(l)

i.e., the TGNN aggregate mtj (v) equals the RGNN’s combined incoming per-lag message at x. (l)

Finally, both models apply the same (Ωc , Γ(l) ) to {{h(v,tj ) }} and the above aggregate, hence ] (l+1) (l+1) (l) (l) (l) (l) h(v,tj ) . h(v,tj ) = Γ(l) Ωc ({{h(v,tj ) }} ⊎ {{mtj (v)}}) = Γ(l) Ωc ({{h(v,tj ) }} ⊎ {{mr,+ (x)}}) = e r

This proves the induction step and concludes the proof.

E. Optimization of Expressive Lottery Tickets We now discuss the impact of the expressivity of sparse RGNN initializations with fixed pruning masks on a fixed and finite dataset on their optimization behavior assuming standard small-step weight updates. Throughout, we use the directed multi-relational RGNN layer from Eqs. (1)–(3) with: (i) single-layer linear maps (i.e., without bias) plus nonlinearity for all (l) message and combine functions Φr,± and Γ(l) , (ii) a real-analytic activation σ that is continuously differentiable, injective, ′ satisfies σ(0) = 0, and σ (x) ̸= 0 for all x, (iii) sum aggregation/combination as in Section 2, (iv) a fixed finite dataset D of finite input graphs with labels y. We focus on graph classification for clarity; node-level tasks are analogous. (l)

Let Θ denote the collection of all trainable RGNN parameters, including all weights of the message maps Φr,± and the combine maps Γ(l) . Let Θk denote the collection at optimization step k. We index individual parameters by Θk,i . A mask M is a binary tensor of the same shape as Θ, and a sparse initialization is given by e 0, Θ0 = M ⊙ Θ e 0 , with surviving parameter indices supp(M ) = {i | Mi = 1}. Let L ∈ N denote the network for some base initialization Θ b with supp(Θ) b ⊆ supp(M ) such depth. A mask M is expressive for D up to depth L if there exists a parameter setting Θ that for all Ga , Gb ∈ D, (L) (L) Ga ̸≃RWL(L) Gb =⇒ ΨΘ b (Ga ) ̸= ΨΘ b (Gb ), i.e., the masked RGNN matches the L-round 1-RWL distinguishing power on D. An expressive mask M is irreducible if for every i ∈ supp(M ), the mask M (−i) obtained by setting Mi = 0 is not expressive for D up to depth L. Irreducibility captures the intuition of a “minimal expressive ticket”: every surviving parameter is needed (on D) to maintain the desired expressivity. Let y(G) denote the label of graph G ∈ D. Relational 1-WL induces an equivalence relation ≡RWL(L) on graphs via L refinement steps. Within our RGNN class, ≡RWL(L) is the fundamental upper bound on what can be distinguished. We are interested only in those WL-distinctions that are label-relevant on D. A pair (Ga , Gb ) ∈ D2 with Ga ̸= Gb is task-relevant (for depth L) if Ga ̸≡RWL(L) Gb and y(Ga ) ̸= y(Gb ). That is, the architecture can distinguish Ga , Gb at depth L, and the labels require it. 21

A Unifying Relational Perspective on Expressive Lottery Tickets

Let M be a binary mask over the parameters of an L-layer RGNN. We call M task-expressive for (D, y) up to depth L if b with supp(Θ) b ⊆ supp(M ) such that for all task-relevant pairs (Ga , Gb ), there exists a parameter setting Θ (L)

(L)

ΨΘ b (Ga ) ̸= ΨΘ b (Gb ). In other words: the masked network realizes all label-relevant distinctions that are representable by L-round 1-RWL. A task-expressive mask M is irreducible if for every i ∈ supp(M ), the mask M (−i) obtained by setting Mi = 0 is not task-expressive for (D, y) up to depth L. Irreducibility in this context means: every remaining parameter is needed to realize some required label-relevant distinction on D (given the architectural 1-RWL limit). We next formalize when a surviving parameter structurally participates in the supervised computation. Let L(Θ) be the empirical loss on (D, y) under parameters Θ: L(Θ) =

1 X (L) ℓ(ΨΘ (G), y(G)), |D| G∈D

with some per-graph loss function ℓ(·, ·) (e.g., cross-entropy). Let M be a mask and consider an RGNN with parameters supported on M and loss L on (D, y). A parameter index i ∈ supp(M ) is gradient-connected (w.r.t. (D, y)) if there exists some G ∈ D and some output coordinate j such that: (i) the forward computation from G to that output depends on Θk,i via a path of operations through the weights of some (l) Φr,± and/or Γ(l) , (ii) along this path, all local derivatives (including σ ′ ) are nonzero on the realized inputs. (L)

(L)

Equivalently, ∂ℓ(ΨΘk (G), y(G))/∂ΨΘk,i (G)j ̸= 0 for some G ∈ D and j. A non-connected parameter is structurally dead for this task on D: changing it never affects any prediction on D. Using the RGNN equations and the chain rule, we now spell out the explicit gradients for the linear +σ blocks Γ(l) and (l) Φr,± in the directed multi-relational case (Eqs. (1)–(3)), with sum aggregation/combination3 . We parameterize (l)

(l)

Γ(l) (x) = σ(WΓ x),

Φr,± (h) = σ(Wr,± h),

(11) (l)

(l)

where σ is injective, continuously differentiable, satisfies σ(0) = 0 and σ ′ (x) ̸= 0 for all x, and Wr,± , WΓ ∈ Rd×d . Instantiating Ωa as the sum, for each v ∈ V and r ∈ R, the per-relation messages are X X (l) (l) (l) (l) mr,− (v) = Φr,−(h(l) mr,+ (v) = Φr,+(h(l) u ), u ). u∈Nr− (v)

(12)

u∈Nr+ (v)

Instantiating Ωc as the sum, the input to Γ(l) is (l) a(l) v = hv +

(l)

mr,− (v) +

(l)

mr,+ (v),

(13)

h(l+1) = σ(zv(l+1) ). v

(14)

r∈R

and

X r∈R

(l)

zv(l+1) = WΓ a(l) v ,

Let L be the training loss on the fixed finite dataset D. All sums below range over all graphs in D and their nodes. We define the local backpropagation factor at layer l+1: δv(l+1) :=

∂L (l+1) ∂zv

∂L (l+1) ∂hv

⊙ σ ′(zv(l+1) ).

(15)

3 As sanity-check, we applied our derived formulas and numerically compared the obtained gradients with those obtained via PyTorch’s autograd: https://github.com/SamirMoustafa/gcn-rgcn-gradient-verification

A Unifying Relational Perspective on Expressive Lottery Tickets

Gradients for Γ(l) .

By the chain rule ∂L (l) ∂WΓ

⊤

δv(l+1) (a(l) v ) .

(16)

(l)

The gradient w.r.t. av is ∂L

(l) ⊤

= (WΓ ) δv(l+1) =: gv(l) .

(l) ∂av (l)

(l)

(17)

(l)

Since av is a sum of hv and all mr,± (v) (see (13)), each summand receives the same contribution: ∂L (l) ∂mr,+ (v) (l)

∂L

= gv(l) ,

(l)

∂mr,− (v)

= gv(l) ,

(18)

(l)

and gv also contributes to ∂L/∂hv via the self-term. (l)

Gradients for Φr,+ .

For each r and u, define (l)

(l)

zr,+ (u) = Wr,+ h(l) u , (l)

Since mr,+ (v) =

(l)

(19)

gv(l) .

(20)

⊙ σ ′(zr,+ (u)),

(21)

ϕr,+ (u) = Φr,+(h(l) u ) = σ(zr,+ (u)).

(l) u∈Nr+ (v) ϕr,+ (u), we obtain

∂L (l) ∂ϕr,+ (u)

∂L

(l) ∂mr,+ (v) v: u∈Nr+ (v)

X v: u∈Nr+ (v)

We define ∂L

(l)

δr,+ (u) :=

(l) ∂zr,+ (u)

∂L

(l)

(l) ∂ϕr,+ (u)

which is nonzero whenever the upstream terms are nonzero, since σ ′ (x) ̸= 0. Then ∂L (l) ∂Wr,+

(l)

Gradients for Φr,− .

X (l) ⊤ δr,+ (u) (h(l) u ) .

The derivation is analogous for the incoming-direction block. For each r and u, (l)

(l)

zr,− (u) = Wr,− h(l) u , (l)

and since mr,− (v) =

(22)

(l)

ϕr,− (u) = σ(zr,− (u)),

(23)

(l) u∈Nr− (v) ϕr,− (u),

∂L (l) ∂ϕr,− (u)

(l) ∂mr,− (v) v: u∈Nr− (v)

∂L

(l)

δr,− (u) :=

∂L

(l) ∂zr,− (u)

∂L (l) ∂ϕr,− (u)

gv(l) ,

(24)

⊙ σ ′(zr,− (u)),

(25)

v: u∈Nr− (v) (l)

and thus ∂L

= (l)

∂Wr,−

X (l) ⊤ δr,− (u) (h(l) u ) .

(26)

u (l)

These explicit expressions specialize the backpropagation rules to the RGNN blocks Γ(l) and Φr,± with sum aggregation, and are exactly the gradients used in our optimizability analysis. 23

A Unifying Relational Perspective on Expressive Lottery Tickets

Lemma E.1. Let M be a mask and let i ∈ supp(M ) be gradient-connected for the RGNN described in Eqs. (11)–(26). Then, for almost all initializations Θ0 supported on M , and for any nonzero loss gradient at the network outputs on some G ∈ D, we have ∂L (Θ0 ) ̸= 0. ∂Θ0,i (l)

(l)

Proof. By construction of the RGNN layer, every trainable parameter in Θ belongs to one of the matrices WΓ or Wr,± . We show that for a gradient-connected parameter, the corresponding partial derivative is a nontrivial smooth function of Θ, hence nonzero almost everywhere. (l)

Case 1: Θi is an entry of WΓ . (l)

From (16), each entry of ∂L/∂WΓ is of the form h ∂L i (l) ∂WΓ pq (l+1)

δv(l+1) [p] a(l) v [q],

(l)

where δv is defined in (15) and av in (13). Gradient-connectedness of Θi means there exists at least one node v and (l) output coordinate such that: (i) av [q] depends (through the RGNN computation) on earlier features along a path using Θi , (l+1) and (ii) the upstream factor δv [p] receives nonzero signal from the loss whenever the output loss gradient is nonzero. All involved mappings are compositions of linear transformations and σ with σ ′ (x) ̸= 0, hence are smooth and locally invertible along the path. (l)

Consequently, the function Θ 7→ [∂L/∂WΓ ]pq is not identically zero on the parameter space restricted by M : at some (l+1)

(l)

admissible parameter setting, the corresponding summand δv [p]av [q] is nonzero. A nontrivial real-analytic (indeed (l) smooth) function has a zero set of Lebesgue measure zero. Thus for almost all Θ0 supported on M , [∂L/∂WΓ ]pq (Θ0 ) ̸= 0. (l)

Case 2: Θi is an entry of Wr,+ . From (22), h ∂L i (l)

∂Wr,+ pq

X (l) δr,+ (u)[p] h(l) u [q], u

(l) (l) (l) with δr,+ (u) given by (21). Each δr,+ (u) is obtained from upstream gradients gv (see (17), (20)) multiplied elementwise (l) by σ ′ (zr,+ (u)), which is never zero. If Θ0,i is gradient-connected, there exists at least one path from Θ0,i to some output (l) (l) (l) (l) (l) coordinate through hu 7→ zr,+ (u) 7→ ϕr,+ (u) 7→ mr,+ (v) 7→ av 7→ h(l+1) 7→ . . . that is used in the computation on

some G ∈ D. Along this path, all local derivatives are nonzero by assumption, and the loss provides a nonzero upstream (l) (l) signal. Therefore the corresponding summand δr,+ (u)[p] hu [q] is a non-constant smooth function of Θ and is not identically zero. As in Case 1, its zero set has measure zero, hence for almost all Θ0 , h ∂L i (l)

∂Wr,+ pq

(Θ0 ) ̸= 0.

(l)

Case 3: Θi is an entry of Wr,− . (l)

(l)

This is identical to Case 2, using Eqs. (23)–(26): for a gradient-connected entry, at least one term δr,− (u)[p] hu [q] is a nontrivial smooth function of Θ, hence nonzero for almost all Θ0 . In all cases, if i is gradient-connected, the map Θ 7→ ∂L/∂Θi is not identically zero on the parameter space compatible with M . Thus its zero set is a measure-zero subset, and for almost all initializations Θ0 supported on M we obtain ∂L/∂Θ0,i (Θ0 ) ̸= 0 whenever the loss gradient at the outputs is nonzero. A sparse initialization Θ0 with mask M is optimizable on (D, y) if: 24

A Unifying Relational Perspective on Expressive Lottery Tickets

(i) every i ∈ supp(M ) is gradient-connected w.r.t. (D, y), ∂L (ii) for almost all Θ0 supported on M , all surviving parameters receive nonzero gradient at initialization, i.e., ∂Θ (Θ0 ) ̸= 0 0,i whenever the loss gradient at the outputs is nonzero,

(iii) thus small gradient steps from Θ0 can affect all task-relevant directions permitted by M (no structurally dead subblocks). Proposition E.2. Let M be an irreducible task-expressive mask for (D, y) up to depth L in the RGNN architecture of Eqs. (11)–(26). Then every i ∈ supp(M ) is gradient-connected w.r.t. (D, y). Consequently, for almost all initializations Θ0 supported on M , Θ0 is optimizable on (D, y). Proof. Suppose, for contradiction, that there exists i ∈ supp(M ) that is not gradient-connected. By definition, “not gradient-connected” is equivalent to (L) ∂ΨΘ (G) ≡ 0 for all G ∈ D, ∂Θ0,i i.e., the RGNN outputs on D are independent of Θ0,i . Because the loss L is computed from these outputs, the chain rule together with the explicit gradients (16), (22), (26) implies ∂L (Θ) ≡ 0 ∂Θ0,i

for all parameter settings Θ supported on M .

Equivalently, varying Θ0,i while keeping all other coordinates fixed never changes any prediction on D. Now consider the reduced mask M (−i) obtained from M by setting its i-th entry to zero. For any Θ supported on M , define Θ′ supported on M (−i) by ( Θ0,j , j ̸= i, ′ Θ0,j = 0, j = i. Since the outputs on D are independent of Θi , we have (L)

(L)

ΨΘ (G) = ΨΘ′ (G)

for all G ∈ D.

Thus M (−i) can realize exactly the same functions on (D, y) as M . b supported on M that realizes all required label-relevant distinctions By Because M is task-expressive, there exists some Θ b b ′ supported on M (−i) that induces the same predictions on D, the above argument, zeroing out Θ0,i yields a parameter Θ (−i) and hence M is also task-expressive. This contradicts irreducibility , which requires that removing any i ∈ supp(M ) destroys task-expressivity. Therefore, every i ∈ supp(M ) must be gradient-connected. Finally, by Lemma E.1, for each gradient-connected i ∈ supp(M ) the partial derivative ∂L/∂Θ0,i is nonzero for almost all initializations Θ0 supported on M whenever there is a nonzero loss gradient at the outputs on some G ∈ D. Since this holds for all surviving parameters, Θ0 is optimizable on (D, y). Proposition E.3. Fix depth L and a sparsity level s. There exist masks M ′ with |supp(M ′ )|= s such that: (a) M ′ is not task-expressive for (D, y) up to depth L, i.e., it fails to separate some task-relevant pair (Ga , Gb ), ∂L (b) some i ∈ supp(M ′ ) is not gradient-connected w.r.t. (D, y), so ∂Θ (Θ) = 0 for all Θ and all training steps. k,i

Thus M ′ is strictly dominated by an irreducible task-expressive mask: it is worse both in terms of expressivity for the task and in terms of optimizability. Proof. Start from an irreducible task-expressive mask M and: 25

A Unifying Relational Perspective on Expressive Lottery Tickets (l)

(i) remove some nonzeros on paths (through parameters of Φr,± or Γ(l) ) needed to separate a task-relevant pair (Ga , Gb ), and (ii) reassign the same number of nonzeros to parameters that only affect intermediate features which are structurally disconnected from the loss. Concretely, pick a feature channel (or neuron) whose entire set of outgoing weights to subsequent layers and to the readout is pruned by M ′ , so that no computational path from this channel can reach a labeled output on D. Place the new nonzeros on the incoming weights into this channel. By construction, these ∂L (Θ) = 0 parameters lie in supp(M ′ ) but any change to them can never influence the network outputs on D, hence ∂Θ k,i for all Θ. The resulting mask M ′ has the same sparsity but cannot realize all label-relevant distinctions anymore, so it is not taskexpressive. By construction, the newly added parameters never lie on a path to the loss and hence are not gradient-connected, with identically zero gradients. E.1. Persistence Under Training We now extend Proposition E.2 from initialization (k=0) to the whole optimization trajectory under small-step gradient-based updates with a fixed mask M . We write a generic first-order update as Θk+1 = Θk + Uk(Θk , ∇L(Θk )),

(27)

where Uk is continuous in its arguments and satisfies ∥Uk (Θk , ∇L(Θk ))∥≤ κk ∥∇L(Θk )∥ for some stepsize κk > 0 (e.g., gradient descent, SGD, momentum, Adam with bounded step). The mask M remains fixed throughout. We begin by showing that, under our construction, parameter gradients that are non-zero at a point Θk remain non-zero in a local neighbourhood of Θk in parameter space: Lemma E.4. Fix (D, y) and the RGNN block structure in Eqs. (11)–(26). Suppose that at iteration k the output loss ∂L (Θk ) ̸= 0. Then there exists a radius ωk > 0 such that for every gradient is nonzero and for all i ∈ supp(M ) we have ∂Θ k,i Θ with ∥Θ − Θk ∥< ωk , ∂L (Θ) ̸= 0 for all i ∈ supp(M ). ∂Θi Proof. For each surviving parameter index i ∈ supp(M ) define the scalar function gi (Θ) :=

∂L (Θ). ∂Θi

By construction of the RGNN layer, all forward computations (14), (19), (23) are obtained from the parameters Θ by finitely many compositions of • linear maps (matrix–vector products, sums), and • the activation σ, which is real-analytic and hence C 1 , together with finite sums over nodes and relations. The explicit gradient expressions (16), (17), (22), (26) are built from these quantities using again only sums, products, and σ ′ . All of these operations are continuous, and finite compositions and sums of continuous functions are continuous. Therefore, for each i, the map gi : Θ 7→ ∂L/∂Θi (Θ) is continuous on the parameter space (restricted by the mask M ). ∂L Next, fix some i ∈ supp(M ). By assumption, gi (Θk ) = ∂Θ (Θk ) ̸= 0. Define i

εi :=

1 |gi (Θk )| > 0. 2

Using the standard definition of the continuity of a function, by continuity of gi at Θk , there exists a radius ωk,i > 0 such that ∥Θ − Θk ∥< ωk,i =⇒ |gi (Θ) − gi (Θk )| < εi . 26

A Unifying Relational Perspective on Expressive Lottery Tickets

For any such Θ we have |gi (Θ)| ≥ |gi (Θk )| − |gi (Θ) − gi (Θk )| > |gi (Θk )| − εi = εi > 0. Hence gi (Θ) ̸= 0 for all Θ in the ball B(Θk , ωk,i ). The mask support supp(M ) is finite, so we have only finitely many radii {ωk,i }i∈supp(M ) . Define ωk :=

min i∈supp(M )

ωk,i > 0.

If ∥Θ − Θk ∥< ωk , then ∥Θ − Θk ∥< ωk,i for every i ∈ supp(M ), and by the previous step each gi (Θ) is nonzero. Equivalently, ∂L (Θ) = gi (Θ) ̸= 0 for all i ∈ supp(M ), ∂Θi whenever ∥Θ − Θk ∥< ωk . This is exactly the desired statement. Proposition E.5. Let M be an irreducible task-expressive mask for (D, y) up to depth L for the RGNN of Eqs. (11)–(26). Assume training follows (27) with a fixed mask M . Then, for almost all initializations Θ0 supported on M , the following holds: (a) (Base case) At k=0, Θ0 is optimizable on (D, y) (Proposition E.2). (b) (Inductive step) Suppose at some k ≥ 0 the output loss gradient is nonzero on the current batch and Θk is optimizable. Let ωk > 0 be as in Lemma E.4. If the update satisfies ∥Θk+1 − Θk ∥< ωk , then Θk+1 is also optimizable. Consequently, for any finite horizon K ∈ N there exists a stepsize schedule {η0 , . . . , ηK−1 } such that Θk is optimizable for all k ≤ K, provided the output loss gradient is nonzero at those iterations. Proof. (a) is exactly Proposition E.2. For (b), assume Θk is optimizable. Then, by the definition of optimizability and the fixed-mask architecture, every i ∈ supp(M ) remains gradient-connected at all iterations: gradient-connectedness depends only on the existence of (l) structural paths through Φr,± and Γ(l) together with σ ′ (x) ̸= 0, not on the specific numerical values of Θk . By the definition ∂L of optimizability and Lemma E.1, ∂Θ (Θk ) ̸= 0 for all surviving i, given a nonzero output loss gradient. Lemma E.4 k,i yields a radius ωk > 0 within which these partial derivatives remain nonzero for all i ∈ supp(M ). If the update obeys ∥Θk+1 − Θk ∥< ωk , then ∂Θ∂L (Θk+1 ) ̸= 0 for all surviving i whenever the output loss gradient is k+1,i nonzero at iteration k+1. Thus items (i) and (ii) of the definition of optimizability hold at k+1, so Θk+1 is optimizable. By induction, repeating this argument up to any finite K proves the consequence.

F. Computational cost model For an MLP of depth M (number of hidden layers), width m (hidden dimension), and unstructured sparsity level ρ ∈ [0, 1] applied to nin distinct inputs (e.g., nodes or branch inputs), we roughly approximate the per-forward MADDS as MADDMLP (nin , m, M, ρ) = nin · M · (1 − ρ) m2 ≈ Nmax · M · (1 − ρ) m2min . Here m2 counts the weights in a dense m × m layer, (1 − ρ)m2 is the number of surviving weights after pruning, and the factor nin accounts for applying the MLP to all inputs.

G. Toy dataset and RGNN architecture This appendix details the exact RGNN architecture and the synthetic multi-relational dataset generator used for Figure 2. Synthetic multi-relational dataset. Each graph is a directed multi-relational graph G = (V, {Er }r∈R ), with |V |= N nodes and |R|= R relations. We construct Er by first sampling an undirected Erdős–Rényi edge set Ẽr ⊆ {{u, v} | u < v, u, v ∈ V } where each unordered pair is included independently with probability pr . To avoid degenerate empty relations, if Ẽr = ∅ we add one random undirected edge {u, v} with u ̸= v. We then convert each undirected edge to two directed edges, i.e., Er := {(u, v), (v, u) | {u, v} ∈ Ẽr }. To encourage structural diversity among generated 27

A Unifying Relational Perspective on Expressive Lottery Tickets

graphs, we reject duplicates under a cheap signature heuristic: for each relation r, we compute the (out-)degree sequence (degr (v))v∈V , degr (v) := |{u ∈ V | (v, u) ∈ Er }|, sort it, and concatenate it with the undirected edge count |Ẽr |. A candidate graph is accepted only if its signature has not been seen before. Unless stated otherwise, we generate Gset = 30 graphs with N = 6 nodes and R = 3 relations using probabilities (pr )R r=1 = (0.12, 0.20, 0.28) and a fixed random seed. Node features.

We use simple structural node features derived from degrees: ⊤

xv := [ 1, degr1 (v), degr2 (v), . . . , degrR (v) ] ∈ R1+R .

(28)

Thus the input dimension is din = 1 + R. RGNN architecture. We instantiate a minimal directed multi-relational RGNN with L layers, hidden width D, and activation σ = tanh. All linear maps are bias-free. First, we project node features to hidden states: h(0) = σ(Win xv ) , v

Win ∈ Rd×din .

For each layer ℓ ∈ {0, . . . , L − 1} and relation r ∈ R, we compute a (directed) sum aggregation X d a(ℓ) h(ℓ) v,r = u ∈R ,

(29)

(30)

(u,v)∈Er

apply a relation-specific linear map, and pass through tanh: (ℓ) (ℓ) m(ℓ) = σ W a v,r r v,r ,

Wr(ℓ) ∈ Rd×d .

(31)

We then combine the current state with all relation messages via summation (rather than concatenation) and apply a shared combine transform: X s(ℓ) = h(ℓ) m(ℓ) h(ℓ+1) = σ Wc(ℓ) s(ℓ) , (32) v v + v,r , v v r∈R (ℓ) with Wc ∈ Rd×d . Finally, we produce a graph-level embedding by sum readout:

e(G) =

h(L) ∈ Rd . v

(33)

v∈V

In our experiments we use d = 16 or 8 and L = 3 unless stated otherwise, and we evaluate embeddings without training (random initialization as in standard nn.Linear defaults).

H. Assumptions and Limitations Assumptions. Our results are stated and proved under the following assumptions, which are either inherent to the setting (finite datasets) or technically convenient for establishing dataset-conditional injectivity guarantees under random pruning. All expressivity and probability guarantees are dataset-conditional: we fix a finite dataset D of finite (relational or temporal) graphs. This makes the sets of MLP inputs actually witnessed on D finite and allows us to bound non-injectivity events via combinatorial arguments. The expressivity target is L-round 1-RWL (and its temporal lift via the corresponding knowledge-graph construction). Concretely, the theorems guarantee that, with probability at least γ > 0 over a random mask, a pruned network preserves the ability to separate all pairs in D that are separated by L rounds of the corresponding 1-RWL refinement. We analyze random pruning at initialization via a Bernoulli mask M ∼ Bρ (entries independently set to zero with probability ρ). We additionally assume a bounded base initialization (e.g., Θ0 ∼ Ucd ) and define the sparse initialization by b 0 = M ⊙ Θ0 . Θ Initial node labels are encoded by an injective map Λ, ensuring label collisions are not introduced at input. The RWL-to-RGNN correspondence relies on injectivity of the multiset encoders and update maps on the finite domain witnessed on D. The probability lower bounds are expressed in terms of (i) the maximum number Nmax of distinct witnessed 28

A Unifying Relational Perspective on Expressive Lottery Tickets

MLP inputs, (ii) the minimum ℓ0 -separation smin between distinct witnessed inputs, and (iii) the minimum hidden width mmin across the relevant MLP blocks. (l)

For all MLPs (e.g., Γ(l) and, in the optimization discussion, also Φr,± ), we assume a real-analytic, injective, continuously differentiable, zero-fixing activation σ with a nowhere-zero derivative (i.e., σ(0) = 0 and σ ′ (x) ̸= 0 for all x). These assumptions are technical and simplify the analysis. They hold for smooth monotone activations such as tanh and shifted sigmoids (e.g., x 7→ sigmoid(x) − sigmoid(0), which enforces σ(0) = 0) but exclude non-smooth activations such as ReLU. Extending the theory to non-smooth activations is conceptually possible, but would require different lemmata and additional case distinctions, which we consider future work beyond the scope of the current paper. In Appendix E we focus on the RGNN block structure induced by Eqs. (1)–(3) with single-layer linear maps (no bias) plus nonlinearity for all message and combine functions, sum aggregation/combination, a fixed finite dataset (D, y), and small-step first-order updates with a fixed mask. Limitations and scope. The above assumptions enable clean, explicit probability bounds and a unifying reduction viewpoint, but they also delimit what we claim. Theorems certify preservation of RWL-separations on a fixed finite dataset; they do not constitute a population-level or distributional generalization guarantee. The guarantee is with respect to L-round 1-RWL (and the temporal analogue). It does not address distinctions beyond this baseline (e.g., higher-order WL tests) and does not, by itself, guarantee the best possible expected test-set performance for a given task. The probability lower bounds are derived for independent Bernoulli pruning at initialization (and independence across MLP blocks when composing across layers). Structured pruning (e.g., magnitude-based, channel-wise) is outside the formal guarantee unless separately analyzed. The lower bound γRGNN is derived via per-block non-injectivity bounds and union-bounding; as a result it can be conservative, particularly near the critical sparsity/width regime where expressivity transitions from holding to failing. Empirically, it tightens again in the high- and low-success regimes. The certificate depends on Nmax and smin (witnessed input counts and separations). These quantities capture dataset/architecture interaction, but they can be large or difficult to control a priori; consequently, the bound may be pessimistic even when expressive subnetworks exist. Appendix E establishes non-degeneracy/gradient-connectivity properties and local persistence of nonzero gradients under small-step updates for fixed masks; it is not a global convergence result.

A Unifying Relational Perspective on Expressive Lottery Tickets

Analyze & explore related research in Conceptio

Related documents