A Unifying Relational Perspective on Expressive Lottery Tickets

AI summary

Overview

Research area: Graph machine learning theory — specifically the intersection of graph neural network (GNN) expressivity (Weisfeiler-Leman style analysis) and the Lottery Ticket Hypothesis (sparse subnetworks that preserve performance). The paper sits at the boundary of relational graph learning, temporal graph learning, and pruning theory.

Technical level: Advanced. The paper is heavily formal, building on Weisfeiler-Leman refinement, relational GNNs, temporal GNN message-passing schemes, and probabilistic pruning bounds. The introduction and methodology sections are readable with a background in GNNs; the theorems and bounds require familiarity with graph isomorphism and expressivity literature.

One-sentence scope: The paper generalizes the Strong Expressive Lottery Ticket Hypothesis from static, uni-relational graphs to multi-relational, temporal, and cross-graph/hierarchical message-passing architectures, proving that sparse subnetworks preserving relational Weisfeiler-Leman expressivity exist with a quantified probability.

What This Paper Is About

Graph neural networks are widely pruned into sparse "winning tickets," but the prior theory explaining why sparsity does not destroy a GNN's ability to tell non-isomorphic graphs apart only covered static, single-relation graphs. This paper asks whether the same guarantee holds for the relational and temporal GNN variants that are increasingly used and are often parameter-heavy. The authors answer yes, by proving a probabilistic version of the Strong Expressive Lottery Ticket Hypothesis in a relational framework, and by showing that temporal and cross-graph message-passing models can be rewritten as relational GNNs that inherit the guarantee.

Key Contributions

1. Relational SELTH (RSELTH). The authors generalize the Strong Expressive Lottery Ticket Hypothesis (SELTH) of Kummer et al. (2025b) to directed, node-labeled multi-relational graphs, proving that sufficiently over-parameterized relational GNNs contain sparse subnetworks that preserve 1-RWL expressivity. The original SELTH is recovered as the special case with |R| = 1 and no directions.

2. An explicit probabilistic lower bound. Rather than a purely existential statement, the paper derives a lower bound γ_RGNN on the probability that a random pruning mask yields a maximally expressive subnetwork, together with a compact bound and a sufficient-width formula for hitting a target probability γ_target.

3. A reduction from temporal and cross-graph models to RGNNs. The authors show that every local or global temporal GNN can be rewritten as an RGNN operating on an augmented knowledge graph K̃⋆(TG), with parameter matrices corresponding one-to-one so that pruning masks transfer verbatim; the same treatment is applied to cross-graph and hierarchical message passing (XIMP/HIMP).

4. Connection to temporal isomorphism and optimization behavior. RSELTH is linked to timewise isomorphism and related notions of temporal graph isomorphism, and the paper shows that the surviving parameters of a sparse RGNN remain trainable under small-step first-order methods, connecting expressivity to optimization under common update regimes.

The paper also states that its 1-RWL characterization marks the first formal characterization of expressivity for the cross-graph and hierarchical message-passing patterns studied.

Main Findings

• Probabilistic, not merely existential, guarantee. Theorem 3.1 (Relational SELTH) states that for a finite collection of finite directed node-labeled multi-relational graphs and a sufficiently over-parameterized depth-L RGNN, G_a ≄_RWL^(L) G_b holds if and only if the sparse-initialized RGNN outputs differ, with probability at least γ_RGNN > 0. The authors emphasize this is not a restatement of Kummer et al. (2025b), which was an existence result.

• What γ_RGNN depends on. The proof yields a lower bound in terms of the maximum number N_max of distinct inputs witnessed by any branch map Φ_r±^(l) or combine map Γ^(l), the minimum ℓ0-separation s_min between such inputs, the minimum hidden width m_min, the number of branches |B| per layer, the MLP depth M, the message-passing depth L, and the pruning probability ρ. Intuitively, γ_RGNN is the probability that all branch and combine MLPs remain injective on the finite input sets they witness on D.

• The compact bound. A slightly looser compact form given in the paper is γ̃_RGNN ≥ ([1 − binom(Ñ_max, 2) ρ^(s̃_min m̃_min)]+)^(L(M|B|+1)), with [x]+ := max{x, 0}, where Ñ_max, s̃_min, and m̃_min aggregate the worst-case input count, separation, and width across branch and combine MLPs.

• Sufficient width for a target probability. If 1 − binom(Ñ_max, 2) ρ^(s̃_min m̃_min) > 0, a sufficient width to certify γ̃_RGNN ≥ γ_target is m̃_min ≥ (1 / (s̃_min ln ρ)) ln( (1 − (γ_target)^(1/(L(M|B|+1)))) / binom(Ñ_max, 2) ). The authors note this threshold comes from inverting a conservative bound and "may be pessimistic." They call Ψ^(L) sufficiently over-parameterized when its smallest hidden width satisfies the inequality.

• Temporal GNNs inherit the guarantee. Lemma 3.2 shows equality of distinguishability between 1-RWL on K⋆(TG) and the temporal GNN's outputs, for ⋆ in {glob, loc}. Lemma 3.3 shows that a TGNN layer with maps (Ω_a, Ω_c, Φ^(l), Γ^(l), ζ, Ξ) has an algebraically identical RGNN realization on K̃⋆(TG) under strict weight tying Φ_r,±^(l) ≡ Φ^(l). Because the dataset is finite, only finitely many time gaps δ appear as edge features, so Theorem 3.1 applies verbatim and pruning masks transfer back to the TGNN.

• Link to temporal isomorphism. Lemma 3.4 states that for sufficient L, timewise isomorphism TG_a ≃_time TG_b implies K⋆(TG_a) ≃_RWL^(L) K⋆(TG_b). Combined with Theorem 3.1 via Lemma 3.3, this means that if a sparse local or global TGNN distinguishes two temporal graphs, they are not timewise isomorphic. The paper also positions this against pointwise isomorphism (Beddar-Wiesing et al., 2024) and the consistent event-graph isomorphism of Heeg et al. (2025), noting that timewise isomorphism coincides with time-concatenated isomorphism for unlabeled snapshot graphs.

• Optimization under sparsity. The paper analyzes optimization of sparse RGNNs with the minimal expressivity required to realize all task-relevant distinctions and reports that all surviving parameters remain trainable under small-step first-order methods.

• Empirical component. 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. The provided content does not name the specific benchmarks or report dataset sizes or headline empirical numbers.

Methodology in Plain English

The authors start from a known characterization: Wałęga & Rawson (2025) showed that the message passing used in local and global temporal GNNs can be described as an instance of the relational Weisfeiler-Leman test (1-RWL) running on a suitable knowledge graph built over timestamped nodes (K_loc and K_glob). The authors exploit this by treating those knowledge graphs as ordinary multi-relational graphs.

From there the argument proceeds in three layers. First, they fix a formal definition of relational GNNs (RGNNs) whose aggregation, per-relation and per-direction message maps, and combining step mirror directed 1-RWL refinement exactly; they assume an injective label encoder and MLPs with real-analytic, injective, continuously differentiable, zero-fixing activations with nowhere-zero derivatives, noting these are technical assumptions that simplify the analysis. Second, they define a sparse initialization as a Hadamard product M ⊙ Θ_0, where M is a binary mask whose entries are independent Bernoulli variables with probability (1 − ρ) and Θ_0 is drawn entrywise from a continuous bounded uniform distribution. Third, they bound the probability that every branch and combine MLP in this sparse network stays injective on the finite set of inputs it actually sees on the given finite dataset — union-bounding within each layer and composing across L layers under independent masks.

To transfer this to temporal GNNs, the authors show that any local or global TGNN layer can be rewritten as an RGNN layer on an augmented knowledge graph K̃⋆(TG), where the time gap is attached to each directed edge as an edge feature and the same aggregators, combiners, and parameter matrices are used. Since pruning masks correspond one-to-one across this rewriting, any sparse-subnetwork guarantee proved for the RGNN carries over. The same rewriting strategy is applied to cross-graph and hierarchical message passing, where an assignment matrix S_i encodes atom-abstraction incidence and the model performs message passing within G and within each abstraction T_i, plus indirect inter-graph passing through S_i and direct passing between abstractions.

Why This Matters

Impact on research. The paper upgrades the Strong Expressive Lottery Ticket Hypothesis from a statement about static, single-relation graphs to a probabilistic statement covering multi-relational, temporal, and cross-graph/hierarchical architectures. That creates a common theoretical language — 1-RWL on an appropriately constructed relational graph — in which expressivity under sparsity can be asked and answered across model families. It also supplies what the authors describe as the first formal 1-RWL characterization of expressivity for cross-graph and hierarchical message-passing patterns. Practically, it gives researchers a computable width threshold m̃_min for certifying a target probability of retaining expressivity, which turns an abstract existence claim into a design rule.

Real-world applications (domains the paper cites as motivation for graph learning):

• Chem- and bioinformatics, e.g., molecules and proteins represented as feature-enriched graphs.
• Medical data analysis.
• Social network analysis.
• Financial applications.

Industry relevance. Pruning is a standard technique for deploying GNNs under memory and latency budgets, and the temporal and relational variants the paper targets are often parameter-heavy. A bound that links the pruning rate ρ, network width, and the probability of preserving task-relevant distinguishing power gives practitioners a principled way to reason about how aggressively a relational or temporal GNN can be sparsified before its ability to separate structurally different inputs degrades. The optimization result — that surviving parameters stay trainable under small-step first-order methods — is directly relevant to whether sparsely initialized models can actually be trained in practice.

Future Directions

• Tightening the bound. The authors explicitly call their sufficient-width threshold conservative and "pessimistic," noting it comes from inverting a conservative lower bound. Closing the gap between the theoretical bound and observed empirical pruning probabilities is an open question their synthetic experiments begin to probe.

• Broadening the activation and architecture assumptions. The injectivity, real-analyticity, zero-fixing, and nowhere-zero-derivative assumptions on activations, and the continuous bounded uniform initialization, are described as merely technical. The paper states that extending the results to other activations is straightforward but requires case distinctions, leaving the general case open.

• Resolving temporal isomorphism notions. The paper notes that the very notion of isomorphism on temporal graphs is still being clarified and that several competing definitions (pointwise, timewise, consistent event-graph, time-concatenated) relate in ways that hold only under constraints. Determining when RSELTH-style guarantees transfer across these notions remains open.

• Formal guarantees for cross-graph architectures. The paper observes that neither XIMP nor HIMP previously provided formal expressivity guarantees, and that its own 1-RWL characterization for these patterns is a first step. Extending sparse-subnetwork guarantees to the full family of hierarchical abstractions is a natural continuation.

Target Audience

This paper is most valuable to machine learning theory researchers working on GNN expressivity and the Weisfeiler-Leman hierarchy, and to researchers studying the Lottery Ticket Hypothesis and network pruning from a theoretical standpoint. It will also interest practitioners working with relational, temporal, or hierarchical graph models who need principled guidance on sparsification, and readers already familiar with Wałęga & Rawson (2025) and Kummer et al. (2025b) who want to see those lines of work unified. The paper presumes comfort with formal graph definitions, injectivity arguments, and probabilistic bounds, so it is not an introductory read.

Authors’ abstract

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