Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Authors: Lorenz Kummer
Samir Moustafa
Anatol Ehrlich
Franka Bause
Nikolaus Suess
Wilfried N. Gansterer
Nils Morten Kriege
Venue: ICML 2025 poster (2025)
Keywords: Lottery Ticket Hypothesis
Graph Neural Networks
Primary area: deep_learning->graph_neural_networks
TL;DR: The paper theoretically links the Lottery Ticket Hypothesis to GNN expressivity and moreover shows sparse, expressive initializations improve convergence and generalization, while poor pruning can cause irrecoverable expressivity loss.

Abstract: The lottery ticket hypothesis (LTH) is well-studied for convolutional neural networks but has been validated only empirically for graph neural networks (GNNs), for which theoretical findings are largely lacking. In this paper, we identify the expressivity of sparse subnetworks, i.e. their ability to distinguish non-isomorphic graphs, as crucial for finding winning tickets that preserve the predictive performance.
We establish conditions under which the expressivity of a sparsely initialized GNN matches that of the full network, particularly when compared to the Weisfeiler-Leman test, and in that context put forward and prove a Strong Expressive Lottery Ticket Hypothesis. We subsequently show that an increased expressivity in the initialization potentially accelerates model convergence and improves generalization. Our findings establish novel theoretical foundations for both LTH and GNN research, highlighting the importance of maintaining expressivity in sparsely initialized GNNs. We illustrate our results using examples from drug discovery.

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Lorenz Kummer 12
Samir Moustafa 12 Anatol Ehrlich 12 Franka Bause" 1
Nikolaus Suess' Wilfried N. Gansterer'
Nils M. Kriege 13
Abstract
et al., 2021; Gao et al., 2022: Wu et al., 2018; Xiong et al., 2021). One of the key fields in GNN research is expressiv- ity, that is, a GNN's ability to distinguish non isomorrp graphs. This expressivity is often benchmarked using the Weisfeiler-Leman (WL) test, with the 1-WL test being a standard baseline for many models. Key contributions to this field include Deep Sets (Zaheer al., 2017), which introduced permutation-invarian learning on sets, and the Graph Isomorphism Network (GIN) (Xu et al., 2019), which explicitly aimed to match the expressivity of the 1-WL test. GIN set a new standard in graph representation learning by using a simple yet powerful aggregation function that ensures the model's 's ability to distinguish non-isomorphic graphs at a level comparable the I-WL test. The combina- tion of these advances has shaped the current understanding of GNN expressivity, where models are judged by their ca- pacity to approximate or exceed the performance of 1-WL in distinguishing complex graph structures. A large amount of research has been devoted to improving the expressivity of GNNs, aiming to go beyond the limitations of 1-WI. and increase the model's capacity to distinguish between struc- turally distinct graphs (Morris al., 2023). Despite these efforts, the 1-WL test continues to distinguish most graphs in widely used benchmarks (Morris et al., 2021; Zopf, 2022), demonstrating that, in many scenarios, it is not necessary to go beyond this foundational approach.
The lottery ticket hypothesis (LTH) is well- studied for convolutional neural networks but has been validated only empirically for graph neural networks (GNNs), for which theoretical findings are largely lacking. In this paper, we identify the expressivity of sparse subnetworks, i.e. their abil- ity to distinguish non-isomorphic graphs, as cru- cial for finding winning tickets that preserve the predictive performance. We establish conditions under which the expressivity of a sparsely initial- ized GNN matches that of the full network, par- ticularly when compared to the Weisfeiler-Leman test, and in that context put forward and prove a Strong Expressive Lottery Ticket Hypothesis.
We subsequently show that an increased expres- sivity in the initialization potentially accelerates model convergence and improves generalization. Our findings establish novel theoretical founda- tions for both LTH and GNN research, highlight- ing the importance of maintaining expressivity in sparsely initialized GNNs. We illustrate our results using examples from drug discovery.
1. Introduction
Practically, in drug discovery and molecular property predic- tion, the impact of model expressivity on prediction quality is not entirely clear. Structurally similar molecules can exhibit drastically different potencies towards the same pro- tein target, phenomenon known as activity cliffs (Pérez- Villanueva et al., 2015). The accurate identification of these activity cliffs is a challenging but essential task, as misclas- sifications may result in a drug candidate being erroneously interpreted as safe or toxic. Furthermore, distinguishing be- tween stereoisomers is crucial, these are molecules with the same molecular formula and bond structure but differ only in the ditre-dimensionll spatial arrangement of their atoms. Even such small changes can significantly influence a molecule's 's biological activity and pharmacological profile.
Graph Neural Networks (GNNs) have emerged as power- ful tools for learning over graph-structured data. Complex objects such as molecules, proteins or social networks are represented as graphs. Nodes represent parts and edges their relations, both can be enriched with features. GNNs gener- alize established deep learning techniques and extend their applicability to new domains such as financial and social network analysis, medical data analysis, or chem- and bioin- formatics (Lu& & Uddin, 2021: Cheung & Moura, 2020; Sun
Faculty of Computer Science, University of Vienna, Vienna, Austria Doctoral School Computer Science, University of Vienna, Vienna, Austria 'Research Network Data Science University of Vienna, Vienna, Austria. Correspondence to: Lorenz Kummer <lorenz. @eanmmer@unnan @univic.ac.at...
The Lottery Ticket Hypothesis (LTH), originally proposed by Frankle & Carbin (2018). introduced the idea that large. randomly initialized neural networks contain smaller, train-
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
able subnetworks, or winning tickets, that can match the performance of the full network. This hypothesis has gained considerable traction, especially in the context of deep learn- ing, where iterative pruning techniques identify these subnet- works, significantly reducing model size and computational cost while preserving performance. LTH has since been extended to various domains, including GNNs. In GNNs, LTH has been explored primarily through the pruning of both graph structures (e.g., adjacency matrices) and model parameters (e.g., weights), leading to the discovery of Graph Lottery Tickets (GLTss, which maintain model performance while substantially reducing computational overhead (Chen et al., 202 Tsitsulin& & Perozzi, 2023). Liu et al. (2024) provide a comprehensive survey on LTH and related works.
initialized CNNs can be pruned into subnetworks approx- imating fully trained models. Zhang al. (2019) propose Eager Pruning, an LTH-based method that prunes DNNs early in training, reducing computation without accuracy loss. Their efficient hardware architecture achieves signif- icant speedups and energy efficiency over Nvidia GPUs, suiting energy-constrane applications. Chen et al. (2021b) embed ownership verification into sparse subnetworks via graph-based signatures, resilient to fine-tuning and pruning attacks, enabling verification without performance impact.
In GNNs, LTH approaches typically treat pruning the graph and the GNN's trainable parameters as a unified task. Specif- ically, Chen et al. (2021a) introduce the Unified GNN Spar- sification (UGS) framework, which prunes both graph ad- jacency matrices and model weights identify GLTs and sparse subnetworks that maintain performance while re- ducing computational cost. Wang et al. (2022) propose transforming random subgraphs and subnetworks into GLTss through hierarchical sparsification and regularization- pruming, achieving high performance with substantial spar- sity. Tsitsulin & Perozzi (2023) present the GLT Hypothe- sis, suggesting that any graph contains a sparse substructure capable of preserving the performance of graph learning algorithms. Efficient algorithms are developed to find these GLTs, demonstrating that GNN performance is retained even on sparse subgraphs. Sui et al. (2023) introduce a co- co-pruning framework that prunes input graphs and model weights in both inductive and transductive settings, identify- ing GLTs while maintaining performance at high sparsity levels. Hui et al. (2023) improve the UGS framework by introducing an auxiliary loss for better edge pruning and a min-max optimization for robustness under high sparsity, enhancing pruning effectiveness. Zhang et al. (2024) present an automated adaptive pruning framework to identify GLTs in GNNs, optimizing graph and GNN sparsity without man- ual intervention and improving scalability in deeper GNNs. Yuxin et al. (2024) introduce scalable graph structure learning method based on LTH, which prunes adjacency matrices and model weights to maintain performance under adversarial conditions. Finally, Yan et al. (2024) propose Multicoated Supermasks (M-Sup) and folding techniques to optimize GNNs based on SLTH, enhancing memory effi- ciency while maintaining performance.
Despite extensive work on LTH in GNNs, and analogous in- vestigations in related domains having yielded fundamental insights (Kummer et al., 2025), the link between LTH and GNN expressivity remains unexplored. While prior research focuses on efficiency, the effect of pre-training pruning on preserving expressivity is largely overlooked. Understand- ing this connection could reveal how sparse initialization impacts a GNN's ability to distinguish complex graph struc- tures, and addressing this gap could advance more efficient graph learning models that maintain expressivity. Our work contributes to closing this gap by providing both formal and empirical evidence that preserving expressivity in sparsely initialized GNNs is crucial for finding winning tickets.
1.1. Related Work
LTH posits that large, randomly initialized neural networks contain smaller subnetworks, or winning tickets, that can match the full network's ' performance when trained in isola- tion (Frankle & Carbin, 2018). Through iterative pruning, these subnetworks are identified, significantly reducing the parameter count while preserving performance. Frankle et al. (2019) enhance LTH by introducing Iterative Magni- tude Pruming (IMP) with rewinding, pruning subnetworks early in training rather than at initialization, thus finding sparse winning tickets in deep neural networks (DNNs) like ResNet-50, maintaining both accuracy and stability. Malach et al. (2020) extend LTH by proving the Strong Lot- tery Ticket Hypothesis (SLTH), showing over- paramparaeteei networks contain subnetworks that achieve high accuracy without training, with theoretical guarantees for deep and shallow networks. Zhang et al. (2021a) theoretically explain LTH's improved generalization, showing pruned networks enlarge the convex region the optimization landscape, enabling faster convergence and fewer samples for zero gen- eralization error. Additionally, Zhang et al. (2021b) use Iner- tial Manifold Theory to validate LTH, showing that pruned subnetworks match dense network performance without repeated pruning and retraining. Finally, da Cunha et al. (2022) prove SLTH for CNNs, showing that large, randomly
1.2. Contribution
We formally link GNN expressivity to LTH by establishing criteria that pruning mechanisms both graph and parame- ter pruning- must satisfy to preserve prediction quality. We demonstrate the existence of trainable subnetworks within mosent-based GNNs that match 1-WL expressivity, putting forward the Strong Expressive Lottery Ticket Hypothesis (SELTH) as a novel, GNN-specific extension of the classical SLTH. We subsequently argue that critical computational
2

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
paths (i.e., those whose removal degrades performance) are subsets of these maximally expressive subnetworks. Fur- thermore, we show that expressive sparse initializations can improve generalization and convergence. We also identify cases where expressivity loss is irrecoverable, exemplified by molecular property prediction in a medical context. Fi- nally, we empirically confirm that GNN parameter pruning impacts post-training accuracy and that more expressive sparse initializations are more likely to be winning tickets.
representing e's (-hop neighborhood (D' (D'Invemoo et al., 2021; Jegelka, 2022; Schulz al., 2022). We write G $wL.c H to denote that 1-WL distinguishes G and H at iteration t.
From Deep Sets to graph neural networks. Deep Sets (Zaheer et al., 2017) model tions, making them ideal for unordered multi colti-insttance data. Given (multi)set X = {x1, 22, In)). J. a function of the form f(X) - p (E x ((x)) is by design invariant to the order of elements and can represent any such func- tion for suitable choices of p and Φ. These two functions, typically realized by multi-layer perceptrons (MLPs), map elements feature space, aggregate them and transform the result into the final output. This approach generalizes to multisets (Xu et al., 2019), reflecting both element iden- tity and multiplicity, thus enabling permutation -nnvariant modeling of complex data distributions.
func-
2. Preliminaries
A graph G is a pair (V, E) of a finite set of nodes V and edges E S v[ CV). The set of nodes and edges of G is denoted by V(G) and E(G). respectively. The neighborhood of node v in V(G) is N(v) = {u E V(G) (u, v) E(G)]. If bijection yo: V(G V(H) with (u,v} E F(G) - (o(w),(()) E F(H) for all u E V(G) exists, we call the two graphs G and H isomorphic and write G = H. For two graphs with designated roots r E VG) and r' E (HH), the bijection must further satisfy ((r) r'. The equivalence classes induced by are referred as isomorphism types. A func- tion I: (G) + E with arbitrary codomain E is called node coloring. Then, node colored or labeled graph (G,1) is a graph G endowed with a node coloring I. We call I(v) label or color of v E V(G). For labeled graphs, the bijec- tion& &p must additionally satisfy ((v) = l(e') if ((v) = v for all v E VGG.. We denote a multiset by L...B.
GNNs can be viewed as stacked neural multiset functions, where each layer aggregates and combines node features- numerical attributes assigned tiset nature of graph neighborhoods. This process, known as message passing (MP), applies moment functions de- rived from sum-pooling: f( f(fx1, xx where f: V. + T is an MLP mapping elements to a vector space (Amir et al., 2024). This allows unique rep- resentations for distinct multisets, as shown in Deep Sets. Applying this principle in GNNs, an MLP in each layer's update rule distinguishes different graph structures, effec- tively extending Deep Sets to graphs. The update rule of this class of moment-basse GNNs employing this strategy can be generalized as in Equation (l), where hx(*) is the embedding of node v at layer k and (0) its initial feature vector. One-hot encoded input features ensure injectivity of summation at the first layer, even without an initial MLP. For graph-level tasks, the readout function aggregates out- puts across layers to compute the graph embedding hG. see Equation (2), where || denotes concatenation.
the mul-
}) = E f(x))
The Weisfeiler-Leman algorithm. Let (G,1) denote a labeled graph. In every iteration t > O, a node col- oring V() + Σ (where the subseript indicates the coloring is based on the initial labeling function 1) is computed, which depends on the coloring &f d(-1) of the previous iteration. At the beginning, the color- ing is initialized as (0) t. In subsequent iterations t 0, the coloring is updated according to q (()(w)
Hash (o) (o)- &et (w)) E N())B) where HASH is an injective mapping of the above pair to a unique value in Σ, that has not been used in previous iterations. The HASH function can be implemented by assigning consec- utive integers to pairs upon first occurrence (Shervashidze et al., 2011) 1). Let c (G) = cc(²) (v) | E ((G) } be the multiset of colors a graph displays in iteration t. The itera- tive coloring terminates if (c(f-")(G)== c (G)), i.e., the number of colors does not change between two iterations. For testing whether two graphs G and H are isomorphic, the above algorithm is run in parallel on both and H. If cf0 (G) # ct (H) for any t. 2 0, then G and H are not isomorphic. The label of (v) in the tth iteration of the 1- WL. test encodes the isomorphism type of the tree of height
1 = MT.P(K)
1)
+
Σ
h(-11)
(1)
ME NEN(w)
hg =
(() DEV(G)
Σ
(2)
k=
The update rule can be expressed in matrix form using the adjacency matrix A and node feature matrix H as (()) = MLP(() ((A + +I) (()))). The Graph Isomor- phism Network (GIN) (Xu et al., 2019) extends neural mul- tiset functions to graphs, ensuring distinct graph representa- tions and achieving expressivity equal to the I-WL test, the upper bound of ba-ed GNNs. Unlike Equation (1) (and its matrix notation), GIN's update rule includes a learnable parameter (1 + (k)) multiplying the ego node embeddings
3

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
(k-1), distinguishing between the feature of the node and he
3.1. Critical Paths
those of its neighbors, as captured in Lemma 2.1.
We analyze the expressivity of neural moment-based archi- tectures, defined in Equation (1), by investigating the critical computational paths within the MLPs they contain. Let the computational graph of an L-layer feed-forward MLP be represented as G = (V, E), where vertices V de- note neurons and edges E their connections. Each neuron is indexed as v(%), referring to the 2th neuron in the 3th layer. A layer is thus subgraph GD) = (VU), (()) with V C V and EG) C E,, characterized by the adjaceney matrix A E {0, 1J1V0)XxIV9 Defining input and out- put neurons as 7() C vG) and O0) c V such that I6) U UOS) v(i), the bipartite nature of G implies that A is symmetric and can, thus, be expressed via the bi-adjacency matrix A E {0, 1] (x))0))))) The forward pass through the 5th layer is then (xx () @ WG)), where W contains edge weights WV) {wx,z (UR, ur) EG),. with the Hadamard product @ and activation func- tion a. Let W represent the set of all weights across layers. A path p from input neuron (fto) to output neu- ron (KL) consists of a sequence (1((a)) ......,.(-- (1), with edges ((()))))))))))) E E for j = 0...., L 1. The total path length is L, and the set of all such paths is P. Pruning in the MLP applies a binary mask M dur- ing the forward pass: (xx(MU) @ A @ W(1).. Set- ting M() k.1 = O removes edge (0k, 21) from E yielding Bu) = EU) \ {(V,, Consequently, the pruned path set P becomes: P P 1ipe E P (vk, vt) E ph. removing all paths relying on the pruned edge (Uk, 21). These paths are crucial in GNN pruning, as GNNs rely on MI.Ps for trans- formations. In post-training pruning. where each MLP's weights W are fixed, a path is defined as critical if its re- moval degrades the GNN's classification performance. In the context of LTH, path is critical if its removal prevents learning the task. Specifically, if no weight configuration for the remaining paths allows the GNN to perform as well as the original, the removed path is critical.
Lemma 2.1 (Sufficient condition for the 1-WL expressiv- ity (Xu et al., 2019)). A moment-based GNN ((k) is as ex- pressive as the I-WL test after k iterations, for all layers jE (I....,K, k} the function MLP()) is injective on its input domain and the aggregation rule distinguishes a node's 's own features from the aggregated features of its neighbors.
Although a large body of work focuses on surpassing the expressivity of GIN and the I-WL test (Morris et al., 2023), neighhorhood aggregation remains prevalent, and 1-WL distinguishes most graphs in common benchmark datasets (Morris et al., 2021: Zopf, 2022).
3. Expressivity and Winning Tickets
We first establish fundamental criteria that any pruning mechanism, including those generating winning (graph) lottery tickets, must satisfy to maintain prediction quality. Let D be a finite sequence of tuples (A, X, 1), where graphs G are represented by adjacency and feature matrices A and X, with classification targets 1. The index E [o, |D] refers to the 1th tuple, denoted as Dj = (A, X, t), with shorthand G = Di (A, X] and 1 = Dr [ Let (p(k) be an MPNN with k message-passing layers as defined in Equation (1), map- ping graphs G. to an embedding space Q. Consider ((++1), +) the same MPNN with an additional classification layer C. Assume C is a perfect classifier that correctly assigns distinet embeddings from (ik) to their respective classes, regard- less of proximity in the embedding space. Specifically, for Ga, G. E D with to * tg and & (Ga) + (,()) (G.), it holds that: to = (((())(()))
((kz
# (((())(G)) = to. The existence of such a C is supported by the results of Chen et al. (2019), showing the equivalence between graph iso- morphism testing and universal function approximation. For (((++1) achieve the same prediction quality on a sequence of modified tuples D (containing, e.g., Di (A, X, t), where the 1h tuple's 's adjacency matrix has been pruned) as on D, this level of distinguishability must be preserved in pruned or otherwise adapted graphs. Similarly, any mod- ification of (A) to (A)) (such as pruning (Ak)ss 's trainable parameters) must maintain this distinguishability for F1k+1) to perform equivalently to (cA++1),
Definition 3.1 (Critical Paths (Pre- Training)). Let Waan = U² W. be the union of weights sets of the MLPs of the k MP layers of the moment- based GNN ((*), Then, if for some quality metric M to be maximized and dataset D it holds that no set of weights Wae, exists such that M( D) S M( D), we say Paisi Pace \ Piccs) is a critical path set.
Criterion 1. For 1(+++) (or 1((+1)) to classify all graphs in D (or D) correctly, ((b) (or T(k)) ) must distinguish all pairs of -oniisomo graphs of different classes.
The key question is which paths in GNNs are critical and how they are characterized. A path in a GNN is critical if its removal prevents the network from distinguishing two isomorphism types of different classes, regardless of the edge weights in any layer of any MLP. Any pruning mask that removes such a path (or an associated edge) cannot be a winning ticket, as it would degrade classification accu-
This requirement also applies to sparse initializations of the MLPs of the MP layers in (b(k,, representing winning tickets in the initialization lottery, which we analyze for neural moment- based architectures. As our work focuses on such sparse initializations, the subsequent sections exclusively address this setting.
4

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
racy. Conversely, pruning that preserves all critical paths can, in Seeory-disregardde practical issues such over- smoothing (Keriven, 2022), oversquashing (Di Giovanni et al., 2023), bottlenecks (Alon & Yahav, 2021) or vanish- ing gradients constitute a winning ticket.
3.2. Lottery Ticket Expressivity Impact on Training.
To examine the influence of expressivity on training, we con- sider its impact on gradient diversity (Yin et al., 2018), see Eq. (3). Originally devised for distributed training, gradient diversity has become a standard metric for assessing neural network learning in local settings as well (Kummer et al., 2023; Rajagopal et al., 2020). Specifically, low gradient diversity can slow convergence and necessitate more passes over the dataset to reach desired accuracy. This increases training time, especially with large batch sizes, as the effec- tive learning rate is diluted. Furthermore, models trained with low gradient diversity often converge to sharp minima, which are associated with poor generalization, particularly when using large batch sizes. Conversely, training with higher gradient diversity aligns with smoother loss surfaces and less sharp minima, improving the model's s generaliza- tion, as well convergence rates (Yin et al., 2018).
In the following theoretical considerations, we assume a class of injective continuously differentiable zero- fero-fixing activations with a nowhere-zero derivative for simplic- ity. However, our empirical results indicate that our theory generalizes to arbitrary activations for appropriately parame- terized GNNs, see Section 5. Due to the permutation invari- ance of GNNs, all theoretical results hold up to permutation. We do not assume a perfect classifier C for ((++1), unless stated otherwise. All proofs are provided in Appendix A.
Theorem 3.2 (Existence of maximally expressive paths). Let D be an arbitrary finite sequence of finite, non-trivial graphs (i.e., graphs with more than zero edges and at least one non-zero feature per node). Then, for any sufficiently overparameterized moment-based GNN ((k) with layers employing an aggregation rule that can distinguish between node's 's own features and the aggregated features of its neighbors, there exist subsets of maximally expressive paths P PgU0,E _ C P Paam for which trainable weights Wain, exist such that for any Ga. Gb E D it holds that if Ga Awink Go then (b(k)) (Ga) + (G.).
For graphs C, with label t, the weight update steps in gradient-based training are given by w W(: a Swi for a learning rate a and loss function loss C. Gradient diversity is then given follows for gradient ma- trices (using the Frobenius norm natural generalization of the Euclidean vector norm):
ace awe F
ac, aw (
11²)"
As
(3)
For this gradient diversity As, we formulate the following Theorem for moment-based GNNs, which captures the influ- ence of the geometry of the embeddings on As's magnitude. Theorem 3.3 (Gradient Diversity and Embeddings Or- thogonality). Assume G1, G2 with labels t1 + tt and let H (1-1) .. (111) be their corresponding embeddings at layer 1. Denote the rows of ([ as (ai} and the rows of H (1) as {b,}. Suppose there exist constants O < m S M <<<0 co s.l. for all i,j. m S ||a:llz bbyl2s M. Then, there exists ( s.t. As 2 Ç 2 with Ç x Eiglcos(BBr)) with Big being the angle between rows a, and by.
While the formal results of SLTH (Malach et al., 2020; da Cunha et al., 2022) make the existence of maximally expressive paths seem plausible, they are not strictly equiv- alent. The proven SLTH variants are limited to MLPs or CNNs applied to classification tasks. Therefore, The- orem 3.2 constitutes novel form of LTH, to which refer as Strong Expressive Lottery Ticket Hypothesis or SELTH.
In line with Criterion I, it immediately follows from Theo- rem 3.2 that for such a (((),, a (((++1 employing a per- feet classifier C could correctly classify every G E D and consequently M($(++)), I M($((+1), D) for P $000 Poc,) g-- Obviously, this existence statement is devoid of practical learning considerations, which we will address later. Before delving into those aspects, we first aim to explore how this result relates to the theory of crit- ical paths. Specifically, it further follows directly from Theorem 3.2 that in every P Pap00 there exist sufficiently expressive paths PQ(n)_s C Poot) for which Wa ex- ist such that for Ga, Go, E D) it holds that if t, A t, and G. ZwI,NN Go then (x)) (G.) 7 (<x) (G.). This is im- portant insight, as by the definition of critical path sets, each critical path set is then a sufficiently expressive path set, and therefore, at least in a sufficiently overparameterized GNN, every critical path set is also a subset of a maximally expres- sive path set, for which Theorem 3.2 shows the existence.
The theorem easily generalizes to any number of graphs (i.e., more than two). While the theorem specifically ad- dresses the angles between individual node embeddings of two graphs, it also carries implications for expressivity. For instance, two graphs with identical node embeddings will al- ways have at least as many codirectional embeddings as they have nodes (provided the graphs have the same number of nodes). Conversely, if the two graphs receive distinct node embeddings, their embeddings may still be codirectional but they can also be orthogonal, contributing zero to the sum of cosines, or otherwise divergent. Therefore, a model initial- ized such that two graphs do not receive (partially) identical node embeddings is likely to converge faster and general- ize more effectively and thus more likely to be a winning
5

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Caaa
Node
Agg(N)
Agg(N))
(a) 2-Layer MLPs (b)
NH
MH
Alom Type
23
23
3
Bonds
12
12
Stereo Info
1
2_
Inpur Holden Ouipun Input
Hislen Chrgui
Figure 1. Visualization of thalidomide (also known as under its trade name Contergan) and its embryotoxic stereoisomer as an exemplary SIFDG, for which failure to distinguish the two can have potentially life altering consequences for patients. As shown on the right-han side of the figure. the aggregates of nodes N1 and N₂ in the first layer differ by only single feature. A pruning mask removing the red dashed edges from the MLPs applied to these aggregates would irrecoverably cancel this difference; hence these edges are part of critical path sets (see Definition 3.1) of a GNN trained to predict different classes for the two molecules as in, e.g., toxicity categorization tasks.
ticket in the initialization lottery, as identical embeddings always codirectional.
ability to distinguish between the two graphs.
In the context of Theorem 3.2, this suggests pruning a GNN
In other words, for structurally isomorphic graphs that are only distinguishable by their node feature matrices, a prun- ing mask that cancels the differences in the messages before the update step in the first layer will-independent of the non-zero values of the MLP's weights- render both graphs' node embeddings indistinguishable at the layer's output. As they are structurally isomorphic, as a consequence they will remain indistinguishable for the rest of the forward pass, regardless of any subsequent transformations. In the context of Theorem 3.2, Lemma 3.5 implies the removal of a path from the maximally expressive path set and, depending on the class labels Gi and G2. is closely related to pruning of critical paths by Definition 3.1 and in violation of Criterion 1. We emphasize that Lemma 3.5 is considering the first layer of the first MP layer's MLP exclusively. In deeper layers, the input embeddings change during training due to changing transformations in upper layers, and what may prune away the distinction during the first iteration of training might not pose problem in subsequent itera- tions. However, Figure 1 (b) shows, the trait captured by Lemma 3.5 can extend beyond the first MLP layer, and even an extension beyond the first MP layer is plausible. Moreover, expressivity is not entirely lost if G1 and G2 do not have permutation permutation-cqqivalenn adjacency matrices, since subsequent layers can still approximate 1-WL, albeit with a different feature matrix for these graphs.
(R) s.t. a maximally expressive path set PaI.. remains and initializing the weights Wa.,, of this pruned ((k) ac- cordingly. Distinctness of node embeddings alone, though, does not rule out that they lie along the same line through the origin. However, depending on (())s width, the following Proposition holds:
Proposition 3.4 (Non-Colinearity under Random Pruning). For a sufficiently overparameterized moment-based GNN ((K) with weights drawn from continuous distribution and a finite sequence D of finite inpul graphs, almost any random initialization combined with random pruning yields a configuration where no codirectional embeddings occur.
Thus, the added constraint to Theorem 3.2 that for any two nodes i. j with pairwise distinguishable 1-WL colors it holds that ((x) (G.); & (ni (18) (Go), : Miy E RR \ {0)) is almost always satisfied for sufficiently overparameterized (8))
3.3. Edge Cases and Boundaries of Learnability
First, we outline GNN-specific scenarios where expressiv- ity is permanently and irrecoverably lost through pruning, regardless of the amount of training, and highlight prac- tical cases where such misaligned pruning could have substantial consequences. Finally, we establish bounds on the prediction quality a GNN can achieve in such cases.
In chemical datasets, structurally similar or identical graphs (i.e., adjacency matrices identical up to permutation) can have distinct input features, leading to vastly different chem- ical properties (see Figure 1). Failure to distinguish such graphs after the first layer can be critical. For example, toxic stereoisomers may appear identical to their non-toxic counterparts, such as thalidomide (Lenz & Knapp, 1962: Bösl, 2014). Non-stereoisommrric cases, like Ethanol and Ethanethiol
Irrecoverable cases. Whereas for general MP layers, re- duction in expressivity is associated with a reduction in gra- dient diversity and thus convergence speed (see Section 3.2), an irrecoverable loss of expressivity can for certain graphs occur the first layer is pruned incorrectly.
Lemma 3.5 (Irrecoverable Loss of Expressivity). Consider ad-
two graphs, G1 and Gz, with cermutation-equivalle jacency matrices but distinct feature matrices. If the prun- ing mask of the first layer of the MP layer's 's when applied in isolation renders the graph representations in- distinguishable, then no choice of weights can restore the
beverage ingredient, the other an odor- izer used in gas warning systems-illusttee illustraaee this further. An improperly pruned GNN may be unable to distinguish these graphs regardless of training. We call such graphs as Struc- turally Isomorphic, Feature-Divergent Graphs (SIFDGs).
6

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
0.6
0.1
for given p. Tpre
0.5
0.4
0.0
PWWTIGN)
-0.1
GNN, [c-D.33]
0.1
GIN,
6-0.33
GJN, 0-1.0
GCN, 9-0.66
.0.2
0.0
-0.3
Pruning Percentages (p)
Pruning Percentage (p)
Figure Probability that a sparse GIN or GCN winning ticket (WT), given pruning p E [10, 90), expressivity Tpre s.t. S Tprn S. 1 + tolerance (left). 1 and are used to group similar Tpre into intervals, as observing exact empirical value of Tpre is unlikely. Mean relative test accuracy, A | E iEs (A Aste) ((lem)(Aae (Asem) where Astan clean test accuracy of the dense, unpruned model, A post-training accuracy of pruned model and S contains models with Tyre 100 + a] (right). Results aggregated from training 13,500 rums over 10 datasets.
Prune %
1e-16
0.6
1e:34
0.4
20
70
1e:52
30
40
90
1e-70
50
Significance threshold
(p-0.0005)
GCN
GIN
0.0
GCN
GIN
Figure Statistical significance Pearson correlation between untrained pruned model expressivity Spre (p E [10, 90]%, GIN. GCN) and post-training accuracy (left). Pearson correlation coefficients (PCC) (right). Aggregated over 13,500 runs (750 per bar, 10 datasets).
Theoretical bounds the quality of lottery ticket. De- pending on the number of 1-WL. distinguishable isomor- phism types for which distinction in the first layer is neces- sary (i.e. SIFDGs) in order for the GNN to be able to learn to assign them to different classes, we can can-under certain assumptions regarding class distributions-estiaaan how good a GNN can be if pruning mask satisfying Lemma 3.5 applied to the first layer.
well. As such, we expect our upper bounds on achiev- able classification accuracy under misaligned pruning (e-g.. Lemma 3.6) also hold for GAT or GCN. However, refin- ing our formal analysis to architectures beyond this most general setting (including the effects of attention or edge features that modulate aggregation) a promising direction for future work, which might reveal additional, architecture- specific vulnerabilities not covered by our existing work.
Lemma 3.6. Let D be a dataset of N graphs, evenly dis- tributed across C classes of graphs each. Suppose has isomorphism types, of which U are indistinguishable from least one other type by the model (i.e. U < I), covering M graphs. Assuming uniform distribution, M R UN the maximum classification accuracy is: (1 2) T
We furthermore emphasize that Lemma 3.6 is theoretical bound requiring knowledge of all isomorphism types of dataset, which is impractical though tools like nauty' can identify them, and popular frameworks include them for certain benchmark datasets. Most datasets likely also lack the assumed uniform class distribution. The lemma is meant to conceptually illustrate how misaligned pruning limits a GNN's maximal accuracy. Refining it for more realistic settings is potential direction for future research.
If the U indistinguishable isomorphism types correspond to SIFDGs as derived from Lemma 3.5, then for any pruning mask satisfying the assumptions on data and class distribu- tion outlined in Lemma 3.6, the above expression represents the maximal achievable accuracy for such pruned GNN.
We point out that Theorem 3.3 does not directly guarantee improved convergence or generalization but instead links embedding distinctiveness to gradient diversity, a factor known to influence both. Empirically, see Section 4, since all models were trained for the same number of epochs, the consistently superior performance of sparse initializations with high expressivity suggests improved convergence and generalization, which is consistent with our theory.
3.4. Generality and Limitations
Our theoretical results apply to moment-based GNN archi- tectures (Section in general and we thus expect the formal insights developed ii.., the connection between prun- ing, critical path removal, and loss of expressivity (e.g., Theorem 3.2, Lemma 3.5)-to apply broadly across this architectural class. This includes, for example, Graph At- tention Network (Veličković et al., 2018) (GAT) or Graph Convolutional Network (GCN) (Welling & Kipf, 2016) as
Our work focuses on graph level tasks, but we expect our findings to be transferable to node level tasks as well.
'nttps://pallini.de uniromal. citoomalii///....... hntop:://pytorch-geen

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Prune %
Detaset
1.0
10.0
AIDS
20.0
ENZIIMES
0.8
30.0
IMDE-BINARY
ZIC
0.6
50.0
MSRC_9
0.4
60.0
MUTAG
80.0
70.0
NCI2
PROTEINS
0.2
83
83
PTC_ FM
0.0
Tyos
PYC
0.0
0.2
0.4 Tare
0.6
0.8
1.0
Figure 4. Visualization of untrained (Tpre) and post-training (Tpost) expressivity of pruned models (p E [10, 90]%, GIN, GCN). Each marker represents the mean over the samples obtained for the models on the given dataset. The dashed line (0,0) (1,1) indicates hypothetical pre-ppos-trraning equivalence. Results based on 13,500 training runs in total over 10 datasets.
Table 1. Prohability of post-training expressivity Tpnat 2 K. given a pre-training expressivity Tpre < for threshalds k. Result based on 13,500 training runs total (pruning percentages p E [10, 90),, GIN, GCN) over 10 datasets.
P(Tpaat 2 Tpre x)
0.00
0.03
0.04
0.03
0.04
0.03
0.03
0.03
0.03
0.03
0.02
0.02
1.00
0.92
0.83
0.75
0.67
0.58
0.50
0.42
0.33
0.25
0.17
0.08
4. Experiments
clude and were conducted on local server equipped with an NVIDIA H100 PCIe GPU (80GB VRAM), an Intel Xcon Gold 6326 CPU (500GB RAM) and a 1TB SSD.
We structure our experiments to address the primary re- search question, which also drove our theoretical analysis, namely how the pre-training expressivity of a lottery ticket affects its post-training accuracy. That is, to what extent can we determine whether a sparsely initialized GNN is a winning lottery ticket based solely on its ability to distin- guish non-isomorphic graphs? We investigate this research question by utilizing 10 real-world datasets from the TU- Dataset repository (Morris et al., 2020). These datasets, which are described in detail in Appendix B, are widely used in current studies. They include one-hot encoded node labels and span a variety of prevalent applications such as drug discovery (Xiong al., 2021; Rossi et al., 2020), bioin- formaties (Borgwardt et al., 2005), object recognition (Rossi & Ahmed, 2015), and social network analysis.
We measure expressivity 7 graph level pre- and post- training expressivity (denoted Tyre and Tpost in our exper- iments) via the percentage of non-isomorphic graphs of dataset for which the GNN's final MP layer (at depth n) outputs node embeddings that are distinguishable for FLOAT32 (emach = 1.19 x 10-7). Specifically, we retain one representative per isomorphism type, as isomorphic graphs yield identical embeddings by GNN permutation invariance. Let [G1,.... Gm) be such representatives with embeddings (ha.,.... he... }. he, = =.vvv(G, h!"") We mark each pair (bc. ha,) as indistinguishable if he. - ha, = O, which generally implies differing node- level embeddings: while distinet node embeddings can theoretically sum to the same vector, such collisions are extremely rare and occur only under measure-zero config- urations. The expressivity is the fraction that remains distinguishable. Alternative methods (e.g., exhaustive com- parisons or training accuracy) are more costly or reflect different notions of expressivity. We chose our approach for its scalability and direct assessment of whether a graph is distinguishable from the rest of the dataset. A sparsely initialized model is winning ticket its test accuracy de- grades by less than 0.05 relative to its dense counterpart.
We assess our research question on GIN (2 hidden layers per MLP) with 2 to 4 MP layers due to its direct relation to our theory. To show our theory extends to GCN, rep- resenting the class of spectral GNNs, we include GCN in our assessment. We use ReLU activations and initialize network parameters WG) randomly from uniform dis- tribution u(-
m with my = [262], following common variance scaling initialization schemes (Glorot & Bengio, 2010; He et al., 2015). The parameterization width is matched with the input graphs' features. All models are trained for 250 epochs with batch size of 32, learning rate of 0.01, using the Adam optimizer. In line with LTH, only non-zero weights are updated. The experiments took approximately 8 weeks with three parallel workers to con-
5. Results
Our experiments empirically confirm both our theoretical predictions made in Section 3. Specifically, our experiments show that sparse yet highly expressive (even if their weights are untrained), trainable subnetworks exist (Theorem 3.2).
'The code for reproducing our results is available at GitHuu: https: /ttp//gittttt/t com/ 1orenz0890 /l///22222 120251ettery
8

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Moreover, they show that for a given percentage of random weights pruning, the expressivity of the pruned network before training is at least one of the driving factors of its post-training accuracy.
versely, the Pearson correlation coefficients (right) show an inverse trend. We conjecture this reflects the greater likeli- hood of irrecoverable damage (compare Section 3.3) at high pruning ratios, while achieving good post-training predic- tion quality is generally more probable at low pruning ratios and less related to expressivity, leading to increased p-values and decreased correlation coefficients in both cases.
The probability that a GNN is a winning ticket given a certain pruning percentage and pre-training expressivity is high for high expressivity and low otherwise for all but the highest pruning ratios (Figure 2, left). To compute this probability, for each pruning ratio p. we set target i and collect runs with Tpre E [ = A run is labeled a "winning ticket" if its accuracy decreases by less than 0.05 relative to the unpruned model. The probability is the fraction of these runs, aggregated (with subset-size normalization) to visualize winning ticket probabilities across pruning levels and thresholds Given that we trained all our models for the same number of epochs, our results are consistent with the hypothesis put forward in Section 3.2 that an increased expressivity in the initialization potentially improves model convergences and generalization, as is indicated by Theo- rem 3.3. Up to 80% pruming. highly expressive sparse GINs outperformed dense unpruned models in post-training pre- diction, while less expressive models failed to match dense model quality (Figure 2, right).
Implications for practitioners and future research. As demonstrated in this work, the expressivity of sparsely ini- tialized GNNs influences convergence speed and general- ization quality. Irrecoverable pruning scenarios, where de- graded expressivity cannot be restored through training, underscore the need for careful pruning design. Preserving critical paths is essential to avoid catastrophic errors, such as misclassifying toxic and non-toxic stereoisomers.
Future work should seek to enhance convergence, gener- alization, and optimization by developing sparse yet ex- pressive initializations. For moment-based GNNs, injective aggregate and combine functions over dataset-defined do- mains are sufficient for maximal expressivity (i.c., I-WL -qquivaeence for GIN). A simple pre-training sparsification strategy could proceed layer-wise: for a fixed pruning ratio, sample l configurations and retain the one preserving in- put-output injectivity across all graphs. This is repeated per layer, increasing sparsity until no injective configuration is found within & trials. The result is maximally expressive, sparsified network. Adapting our results on winning tickets to settings such as those explored by Walega & Rawson (2025), Bause et al. (2024) or Kummer et al. (2024) is an- other promising direction. Pruning strategies that prioritize expressivity could improve LTH's practicality for GNNs, ensuring reliability and performance in critical domains.
Moreover, we find that GNN, when initialized with a cer- tain sparsity and non-zero weights trained in isolation, is highly unlikely to gain expressivity (Table 1). That is, if a GNN initialized, pruned and trained as described could reliably transition from low Tpre to high Tpost. then for some k, this transition would occur with probability exceeding a low single-digit percentage. Although we do not explicitly set threshold defining "high probability", Figure 4 illus- trates the trend outlined in Table 1. Consistent with Table I, Figure 4 shows that sparse GNNs rarely transition from low to high expressivity during training. Instead, the converse is the typical case, as all data points fall below the dashed Tpost- = Tpre line, indicating that Tpost is generally lower than Tpre: whereby low pruning percentages apparently aggerate the effect. This aligns with Lemma 3.5 (focused on the input layer) and highlights the broader trend suggested in Section 3.3: despite the depeneet differences apparent in Figure 4, recovery from a relatively low ex- pressivity sparse initialization is rare during training if only non-zero weights are updated, even if theoretically possible. As pre-training expressivity was low even at conservative pruning rates some datasets, we interpret this, following Proposition 3.4, as an indication that the underlying GNNs were insufficiently parameterized for the pruning rate.
6. Conclusion
In this work, we bridge the gap between GNN expressivity and LTH. We offer theoretical insights and empirical vali- dation that trainable sparse initializations with comparable expressivity to dense models exist. Moreover, we show that increased expressivity in the initialization potentially accelerates model convergence and improves generaliza- tion. Our findings highlight the risk of pruning strategies that fail to retain critical computational paths, in certain cases theoretically causing irreversible degradation in per- formance. Recovering expressivity loss induced by sparsity through training is generally unlikely, underscoring the need for sparsification approaches that safeguard key expressive capabilities. Our work also has practical implications: pre- serving critical paths during pruning is essential to prevent catastrophic errors, such as misclassifying toxic and non- toxic stereoisomers, particularly in critical applications like drug discovery or molecular property prediction.
Finally, Figure reveals an intriguing pattern: the statistical significance of the correlation between pre-training expres- sivity and post-training prediction quality (left) is lowest for mid to slightly above mid-pruning ratios but higher for very low and high pruning ratios (though still significant). Con-

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Acknowledgements
Cheung, M. and Moura, J. M. Graph neural networks for covid-19 19 drug discovery. In IEEE International Conference on Big Data, pp. 5646-56446 2020.
This work was supported in part by the Vienna Science and Technology Fund (WWTF) and the City of Vienna through grants [0047379/VRG19009) and [10.47379/CT22059)
da Cunha, A., Natale, E.,, and Viennot, I., Proving the strong lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations (ICIR), 2022.
Impact Statement
Di Giovanni, F., Giusti, L.,, Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neu- ral networks: The impact of width, depth, and topology. In International Conference on Machine Learning (ICML), pp. 7865 7865,7885.27 2023.
Our work highlights the critical role of preserving expres- sivity in sparsely initialized and trained GNNs, offering insights into how pruning can lead to irrecoverable expres- sivity loss. By demonstrating the risks associated with de- graded expressivity, we show the importance of careful pruning design to ensure reliable predictions, such distin- guishing toxic from non-toxic compounds in drug discovery. Moreover, via linking GNN expressivity with generalization and convergence, we show that degraded expressivity can hinder both training dynamics and model reliability. The broader societal benefit of our work lies in its potential to inform the development of nigh-peeffrmmncc and trustwor- thy GNNs in resource-constrraned settings, contributing to equitable access to advanced machine learning technologies and promoting their safe use in impactful domains.
D' Invermo, G. A., Bianchini, M., Sampoli, M. L., and Scarselli, F, A unifying point of view on expressive power of GNNs. CoRR, hax/2106.08992, 2021.
Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference Learning Representations (ICLR), 2018.
Frankle, J., Dziugaite, G. K., Roy, D. M., and Carbin, M. Sta- bilizing the lottery ticket hypothesis. CoRR, abs/1903.01611, 2019.
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.
References
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In International Conference Artificial Intelligence and Statistics (AISTATS), pp. 249-256, 2010.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. International Conference on Learning Representations (ICLR), 2021.
Amir, T.. Gortler, S., Avni, I., Ravina, R., and Dym, N. Neural injective functions for multisets, measures and graphs via finite witness theorem. Advances Neural Information Processing Systems (NeurIPS). pp. 42516 4265-42211122 2024.
Hc, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In International conference on computer vision (ICCV), pp. 1026-1034, 2015.
Bause, F., Moustafa, S., Langguth, J., Gansterer, W. N., and Kriege, N. M. On the two sides of redundancy in graph neural networks. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), pp. 371-388, 2024.
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.
Jegelka, S. Theory of graph neural networks: Representation and learning. CoRR, abs/2204,0766 007697, 2022.
Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S., Smola, A. J., and Kriegel, H.-P. Protein function prediction via graph kernels. Bioinformatics, 21:47-56, 2005.
Keriven, N. Not too little, not too much: a thcorctical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems (NeuriPS), 35:2268-222 228882222111111 2022.
Bösl, E. The contergan scandal. media, medicine, and thalidomide in 1960s west germany. Disability Histories, pp. 136-162, 2014.
Kummer, I.., 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.
Chen, T.. Sui, Y., Chen, X., Zhang, A., and Wang, Z. A uni- tied lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning (ICMI),, pp- 1695-1706, 2021a.
Kummer, L., Moustafa, S., Schritwieser, S., Gansterer, W. N., and Kriege, N. M. Attacking graph neural networks with bit flips: Weisfeiler and Leman go indifferent. In International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD), 2024.
Chen, X., Chen, T., Zhang, Z., and Wang. Z. You are caught stealing my winning lottery ticket! making lottery ticket claim its ownership. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1790-1791, 202th.
Chen, Z., Villar, S., Chen, L., and Bruna, J. On the equivalence between graph isomorphism testing and function approxima- tion with gnns. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1 15894- - 15902, 2019.
Kummer, L., Gansterer, W. N., and Kriege, N. M. On the rela- tionship between robustness and expressivity of graph neural networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2025.
10

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Lenz, W. and Knapp, K. Thalidomide embryopathy. Archives of Environmental Health: An International Journal, 542):14-19, 1962.
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.
Liu, B., Zhang, 7., He, P., Wang, Z., Xiao, Y., Ye, R., Zhou, Y., Ku, W.-S., and Hui, B. A survey of lottery ticket hypothesis. CoRR, ahs/2403.04861, 2024.
Sun, Z.., Yin, H., Chen, H., Chen, T., Cui, L.,, and Yang. F. Dis- ease prediction via graph neural networks. IEEE Journal of Biomedical and Health Informatics, 25(3):818-826, 2021.
Lu, H. and Uddin, S. A weighted patient network-based framework for predicting chronic diseases using graph neural networks. Scientific reports, 1111:222077, 2021.
Tsitsulin, A. and Perozzi, B.
The graph lottery ticket hypoth- esis: Finding sparse, informative graph structure. CoRR, abs/2312.04466,, 2023.
Malach, E., Yehudai, G., Chalev-Schwarle S., and Shamir, O
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, and Bengio, Y. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Proving the lottery ticket hypothesis: Pruning all you need. In International Conference on Machine Learning (ICML), pp. 6682 6691, 2020.
Walçga, P. A. and Rawson, M. Expressive power of temporal mes- sage passing. In Conference Artificial Intelligence (AAAI). volume 39, pp. 21000-21008, 2025.
Morris, C., Kriege, N. M.. Bause, F., Kersting, K., Mutzel, P., and Neumann, M. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Wang, K., Liang, Y., Wang. P., Wang, X., Gu, P., Fang, J., and
Morris, C., Fey, M., and Kriege, N. The power of the weisfeiler- leman algorithm for machine learning with graphs. In Interna- tional Joint Conference on Artificial Intelligence (IICAI), pp. 4550,, 2021.
Wang, Y. Scarching lottery tickets in graph neural networks: A dual perspective. In International Conference Learning Representations (ICLR), 2022.
Welling, M. and Kipf, T. N. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2016.
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 555333;1199,2000 2023.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenct: a benchmark for molecular machine learning. Chemical science, 53000, 2018.
Neumann, M., Garnett, R., Bauckhage, C., and Kersting, K. Prop- agation kerees:: efficient graph kernels from propagated infor- mation, Machine learning, 102:209-245, 2016.
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-1399 2021.
Pérez- Villamueva, J., Méndez-Lucio O., Soria-Arteche, O., and Medina-Franco, J. L. Activity cliffs and activity cliff generators based on chemotype-related activity landscapes. Molecular Diverxity, 1944):002- 2015.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
Rajagopal, A., Vink, D., Venieris, S., and Bouganis, C.-S. Multi- precision policy enforced training (MuPPET): : A precision- switching strategy for quantised fixed-point training of CNNs. In International Conference on Machine Learning (ICML), pp. 7943-7952, 2020.
Yan, J., Ito, H., Garefa-Arias, Á. L.. Okoshi, Y., Otsuka, H., Kawa- mura, K., Van Chu, T., and Motomura, M. Multicoated and folded graph neural networks with strong lottery tickets. In Learning on Graphs Conference (LoG), pp. 1 11-1, 2024.
Rossi, R. and Ahmed, N. The network data repository with in- teractive graph analytics and visualization. In Conference Artificial Intelligence (AAAI), 2015.
Yanardag, P. and Vishwanathan. S. Deep graph kernels. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 1365-1374, 2015.
Rossi, R. A., Jin, D., Kim, S., Ahmed, N. K., Koutra, D., and Lec,
J. B. On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications. ACM Transactions on Knowledge Discovery from Data, 14(5):1-37, 2020.
Yin, D., Pananjady, A., Lam, M., Papailiopoulos, D., Ramchan- dran, 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.
Schomburg, I.. Chang, A., and Schomburg, D. Brenda, enzyme data and metabolic information. Nucleic acids research, 30(1): 47-49. 2002.
Yuxin, W., Xiannian, H.. Jiaqing, X., Zhangyue, Y., Yunhua. Z., Xipeng, Q. and Xuanjing, H. Graph structure learning via lottery hypothesis at scale. Asian Conference on Machine Learning, pp. 1401-1416, 2024.
Schulz, T. H., Horváth. T., Welke, P., and Wrobel. S. A generalized weisfeiler-lehman graph kernel. Machine Learning, 111(7): 2601-2629, 2022.
Zaheer, M., Kottur, S., Ravanbakhsh. S., Póczos, B., Salakhutdi- nov, R., and Smola, J. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3391-3401, 2017.
Shervashidze, N., Schweitzer, P., Van Leeuwen, E, J., Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
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, J.,
Chen, X., Song, M., and Li, T. Fager pruning: Algo- rithm and architecture support for fast training of deep neural networks. In ACM/IEER Annual International Symposiun Computer Architecture (ISCA). pp. 292-303, 2019.
Zhang, S., Wang, M., Liu, S., Chen, P.-Y,, and Xiong, J. Why lot- tery ticket wins? a theoretical perspective of sample complexity on sparse neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2707-270720 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 (Neur[PS), pp. 30196 30210, 2021b.
Zopf. M. 1-WL expressiveness (almost) all you need. In Inter- national Joint Conference on Neural Networks, (ICNN), pp. 1-8, 2022.
12

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
A. Proofs
A.1. Proof of Theorem 3.2
Proof. The proof consists of two parts. In the first part, we show the existence of subsets paths for which weights exist such that any 1-WL distinguishable pair of graphs of a bounded dataset can be distinguished. In the second part, we show that the weights of these paths are trainable, i.e., that they can receive gradient updates.
As established in the literature (Lemma 2.1), neural moment-based GNN is maximally expressive if all of its MLPs are injective on their respective input domains; that is, if distinct inputs representing neighborhood aggregates are mapped to distinct outputs. Therefore, it is necessary to demonstrate the existence of sparse subnetworks capable of modeling such injective functions. Noting that an MLP is injective if all of its layers are injective, we begin by proving the following Lemma:
Lemma A.1 (Layer Injectivity under Random Pruning). Let W E R with < n S in be a linear transformation matrix where each entry is independently drawn from a continuous and bounded distribution over an interval [a, bj with a < b. Let RR- > R an injective elementwise activation function. Consider a finite inpute set X C Rh with cardinality N where each randomly prune W by independently setting each weight to
element has continous entries bounded by [e, d]. Suppose zero with probability (sparsity ratio), resulting in sparse weight matrix W'. Then, the function f = o W X - I.m is injective with probability y 2 1- -22) ptm where ls 2 1 is the minimum number of non-zero components in x., Xx for all distinct pairs Xa, X2 E
Proof. The function f fails to be injective if there exist distinct inputs Xx, E X s.t. f(xx) = (xx)). Since is injective, this implies that W'x, = W'x, Let ò = X., x, # O. Then, the condition W'x, = W'x, becomes W = 0.
For a fixed 8, we compute the probability that W = 0. Let be the number of non-zero components in 8, i.c. = || 1. Each weight w/y in W is then given by uh, Wry2rj where Wrj is the original weights and žrj an independent Bernoulli random variable:
0,
with probability p.
Σrj
1, with probability -
For each row r of W the r-th component of W is:
(W'5), Σ
w
urjoo =
Σ j=1
Wyj 2rjj2
1=1
If all 6, = 0: This occurs either 2rj (due to pruning) or 8, =
The probability that Z,j when o5 * 0 is p.
Since žrj are independent and there are non-zero 8,, the probability that all 2rj for those j is p..
If any 2rjō; * 0: Since W,j are continuous random variables over [a, b] and 6, * 0, the product w,,ō, is continuous random variable. Therefore, the sum (W'8), is also continuous random variable, and the probability that it equals zero is zero. That is, the set of weights elements of each row vector w, satisfying w = O forms a hyperplane in RR.. Since elements wrj are drawn independently from a continuous distribution, the probability that they fall on that hyperplane is practically 0, which is equivalent to every proper hyperplane having a zero Lebesgue measure in its ambient space.
Thus, the probability (W'8), is
P ((W'5), 8), 0) = p². Therefore, as the rows of 4 are independent because the why are independent across r, the probability that W -
P P(W'5 = 0) =p²t) km
13

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
There (5) distinct pairs (X X.) in X. By Boole's inequality, the probability that there exists at least one pair (Xus Xv)
such that W 0 is now most:
N
P(3 100:W8-2
km
2
Therefore, the probability that f' is injective over X at least:
7 1 N
Am
Since and p E (0, 1), p decreases exponentially with m, and for sufficiently large m, y will always be >> 0. That is, for p 0, and for fixed N, we choose m such that > log, ((1 (() k-1
Then, it immediately follows that for an MLP with I. layers, the probability of a random pruning leaving it injective is TL 2 (1- ( y with miin being the smallest number of neurons of any of the L layers. Note that treating the previous layer would decrease (size of distinct elements in input) for the subsequent layer and thus increase the probability of being injective w.r. these inputs.
layers independently is conservative, as non-injectivity
model GNN bounded dataset D of finite graphs. If there are at most N nodes in any graph in D and we have M MP layers, the total probability for the pruned GNN having injective MLPs is then NaNN 2 (1- (1- ) L,M, which corresponds to the probability that non-zero pruning rate (corresponding to pruning masks corresponding to edge- and therefore computational path-deletions) leaves a subset of paths intact in the GNN for which weights exist such that the GNN is maximally expressive (in the sense Lemma 2.1) on given dataset D, i.e., Gb. Gas Gb E then (G.) * T(k) (Gb), given a sufficient number of neurons m for each of the MLP layers.
Likewise,
G. FWLO)
Based on the above shown existence of PB0,, S Para and Wa such that any Ga, Go E D, H FWLO ((m) Go can be distinguished via (G.) + (G)),, focus on the most relevant interactions between trainable parameters and other components of MP, the proof only considers MP layers with single layer MLP (i.e., not hidden layers), but it can easily be generalized to an arbitrary number of layers per MLP.
show that these weights receive weights updates. For simplicity and to
Lemma A.2 (Trainability). Let ((k) be a GNN pruned an P Pam initialized to appropriate Wa g for dataset D, where D consists of bounded, non-trivial graphs (e.g., graphs with more than edges and at least one non-zero feature per node) Then, for any loss (G)(++))(G)))) # 0, at leust those weights relevant to the dislinction of G from other H E D are capable of receiving updates.
Proof. The general equations for backpropagation through GNN with Z = ( and H = (z of the ac
form Equation (I), where az@ (
w(IT
ac
A
JZ W(++1)T and ac are derived via chain rule as aWa
HH
aH
OC
2C @)
OW
OHO
ow
OC (H ()
T OZ (1) Ow
H IIT AT dc
(4)
OZ
OZ ac
(1-1)T AT
2H
= - ('(Z(1)) @ A dc
W(++1))
OZ
14

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
which, written as elementwise summation, yields
ac
4 1=1 p=1
H (1-1) App (2 wll+1)
dL
(5)
0z
To show pack-propagttion works for these paths, we show by induction the existence of non-zero gradients every layer.
Base Case. By assumption ((k) is pruned to an expressive path P initialized to appropriate Wi g allowing the distinction of WL distinguishable graphs. That means for any G in D, there must be least one node embedding the hthh layers output of (K) that distinguishes it from those H E D that are H $wZ G, as otherwise either P P would not be a maximally expressive path set or W5 would not be properly initialized as per Theorem 3.2. That is, at least one of the two graphs G or H must have at least one non-zero node embeddings and, for the sake of the argument, we let this graph be G. Let's further say p is one those nodes of where embeddings are distinguishing G from H.Then, this node p must have at least one non-zero embedding i at layer k. i.e., o (Zph)) # 0.
Now, we start at layer = k, right before the classifier layer. Assume ac w + 0, i.e. loss back propagated for the a2
tth feature of the 7h node from the classifier C used layer + 1 and the th weight of the jth neuron of the classifier also non-zero (which it is since assume dense classifier with random continuous weights).
Then we know by assumption o (Z/
(h) * that for some node p connected to r (or at least r = p) at least one feature of (12())) + 0 as a is injective and zero-fixing (i.e. only o0) = 0 and
node must have had a non-zero contribution to (Z
consequently, as a has nowhere-zero derivative, at least for these indices,
ac
= o' (k)
Oc 02
(k+1) (k-1)
W
+ 0.
(6)
t=1
rt
From the assumption oZz(1) + 0 and a being zero-fixing it further follows that
de
z(h
Apg
H
(k- 1) (k) #
(7)
which implies that for some node q connected to (orr q) the jth feature had a non-zero embedding at layer k 1, i.e.. (k-1)) + 0, and moreover, (R) expressive path set Pate)pp ..)
fi * 0 (which in turn implies inclusion of the edge ji of the computational graph in the
Thus, for the gradient update step.
ac
d
(1-1) Ap Ap o (Z
OC (k+1)
(w
Oz (++1) i
(8)
we find that indices exist which for which the non-zero weight w:(k) as part of the expressive path set receives a nonzero gradient and the loss gradient
dc that can be back propagated to the next layer.
az
Assumption. For some su and iu
OC
(++1 iu
+ 0.
az
Step. In the induction step, we show that the induction assumption implies that the error is back propagated through layer 1-1 and the weights at layer 1 1 receive updates via the recursive definition of backpropagation:
dC
n
a
(1-) ApprrpAono (2 (1-))) (o'(1
OC
(111)
w-(
(9)
ow aw!!
!-11 j
15

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
By the induction assumption, for some su and iu, also (2 for some as otherwise, no non-zero forward propagation could have happened. By the same argument, for some pi, a (Z ( + O, implying
ac a
(b)) W!++) * 0. As we also assume that o ( pi
W (1+1)
of for some pi,
ac a 17 # O for some node p. Thus, assuming W w A 0, as the edge is part the
expressive path set, it follows that 11(1-2) least for those node indices,
% # 0 for some qj. Then, if nodes pq, rp and sr connected or have self loops, aw). 13 # O.
ac
To summarize, we have shown that it follows from Lemma A.1 that for any arbitrary finite sequence of finite graphs D (e.g., graphs with more than zero edges and at least one non-zero feature per node). and any sufficiently overparameterized moment-based GNN (p() with layers employing an aggregation rule that can distinguish between node's own features and the aggregated features of its neighbors, there exist subsets of maximally expressive paths PąL,, E C Pacc for which weights Wa00, E exist such that for any Gas G5 E D it holds that if G. AWI()) Gb then (h) (G,) # (I and, from Lemma A.2, that these Waw., F for P (k)),, _ S (aa are trainable.
A.2. Proof of Theorem 3.3
Proof. Let G. with labels i, be graphs and L, be the loss w.r.f to the input graph G3 with label 4. Then, gradient diversity as given by (3) via Frobenius inner product expansion, can be rewritten as
aC: Ow
Oc; OWO
OC. aw
OC, Ow()) )
As
I
(10)
Obviously, the Frobenius inner product (a generalization of the dot product to matrices) between gradients of different data points dictates how large or small the gradients' diversity is: if all gradients are orthogonal, is maximal, whereas if they are codirectional, is minimal.
Let's now consider two graphs specific G1, G2 with labels o 12 and analyze this inner product product. Then, with
ac. aw
OC
1)T A
(11)
oz
from Equation (4) we obtain for the inner product
tr H
(H
1YT
AT
dL
T
H
IyT
A
0L2
( 1)T
H
AT
0L1
H.
(1-1T
A
OL.
(12)
az
az
(1)
az! !!)
F
which (via transposition and eyclicity of the trace of matrix products) is equal
tr
1)T
AT
OL2 dLi az
(1) A.) tr
((H) (HT
[
AT
OL1 T
H
111
A
OL2
(13)
oz
az
(5)
az! !!)
For this left hand side, without assumptions of definiteness of the matrices involved, an upper bound of it's magnitude (i.e. absolute value) is provided by
1)T AT OL2 0L1 o
OL2 UL,
|rr
H
A
11 | ( H 1)2
||AT
Aille.
(14)
oz! az
The first part of this product itself can be bounded by exploiting the relation between the Frobenius norm and the inner product
H
H
1)T 1
(max |a 1 Σ cos2 (Btg) 1.
(15)
and a; by the corresponding row vectors and Big the angle between each pair a, by and E,, the double sum over the common dimension of the two matrices. Thus, it follows that if all node embeddings are orthogonal, gradient diversity is maximal as their enclosing angles' cosines equal 0.
with j.j denoting rows of H(- 11-1)
H
16

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Furthermore, if there exist m, M s.t. for all i it holds that m || - by 2 M, then max |a.
b M and
thus [ "1 M / Eng cos (B:)), which is proportional up constant factor M to the sum of the cosine similarity of the node embeddings.
Consequentially, we can formulate for the two graphs G1; G2
ac: OW
ac; OW
OL2
0L1
+
M
cos (B6))) ||A
AIll))
(16)
az! az
f
for which it holds that for any E
BC, @w
P either As E (S+, 00) if0 < Ei=1
Dc, Sway
1| M v Eis cos cosg()::))
D4 ||A ac, ac, A Alle or As E 1s+, E Wiv 8 az!"
P2z M V Ei, cos? (3.g) ||
aCg a0 A F. 8
8Z
Thus, for any As, we obtain the proposed lower bound by choosing Ç = S+ for which it directly follows from equation (16)
that Ç x (Ei cos( 1-)))))
Coss
A.3. Proof of Proposition 3.4
Proof. Let the function
-= X
where W E Rmxx, 1 < n S m, with entries independently drawn from a continuous and bounded distribution over an interval (a, b) with b. We use injective elementwise activation independently setting each weight to with probability p. resulting in sparse matrix W'. Let X 1 be finite input set of cardinality N, with each element having continuous entries bounded by [c, d].
R. Suppose we randomly prune W by
Then, by Lemma A.1, with probability
7 2 (
( p
the map f a (W') ) is injective X, where & 2 1 is the minimum number of non-zero components in x Xx for all distinct pairs Xu, X. We also recall from the argument in the proof of Theorem 3.2 that, for p >> 0, y > 0, and fixed N, kt one obtains a sufficient condition on m, namely m 2 log, ((1 (?) kー
We now extend Lemma A.1 from injectivity to non-colinearity of the outputs. Specifically, wish to show that for any two distinct inputs Xu, X. E X, the probability that there exists nonzero scalar 17 IR with
fxx.) = 1y (x.)
negligible (indeed measure zero) under our assumptions on the continuous distribution of weights and the independent pruning process.
We proceed follows. Fix a single pair of distinct inputs x, + x, X. Denote by w/ the r-th row of W'. Then
f(xw) = (xx))
ow,, xx) nw xx.) for allr l,... m.
Because a is injective (elementwise), each equation
of w/," x.) = notl w x.)
for a fixed 1) imposes a fower-dimensional (measure-zero) constraint on the row w/ in R". Enforcing this condition across all r = 1...., m and with the same scalar yields an intersection of these measure- zero sets in Rm Consequently, the probability that
W W' Rm=x f(x.) =) (x.)
itself zero under our continuous distribution for W and subsequent Bernoulli pruning of entries (c.f. Lemma A.1). The only way the dimension of these constraints would fail to be negligible is if W had some degenerate structure (c.g. all-zero rows, or precisely tuned rows to force colinearity), but for almost all choices of non-pruned weights in a sufficiently
17

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
overparameterized W (i.c. with m 2 logp ( (+) -t) k- for + 1), such a degeneracy cannot occur with non-zero probability.
Hence, for any fixed pair x,; X E X, the probability that they become mapped to colinear outputs under is zero. A union bound (Boole's ' inequality) over the (2) distinct pairs in X remains a finite union of measure-zero events. Therefore, with probability 1, none of the pairs x,, X yield colinear outputs.
Putting all together:
Injectivity: already know from Lemma A.I that P(f(x,) + f(x,)xx, x,) 2 (p))
Non-colinearity; with probability 1, no two distinct inputs map to outputs that are scalar multiples of each other.
Since a measure-zero event does not further reduce the probability threshold from the injectivity part, second property effectively guaranteed almost surely in our random draw of W/ Therefore, for any two distinct points in X, both
f f(xa) # f(x.) and f(xu) & f(xo)
hold with high probability (and indeed the colinearity condition holds with probability 0).
Thus, if m chosen large enough to satisfy m 2 logp (?) - b- then 7 2 1 (7) p1 > 0, ensuring both injectivity and non-colinearity of the outputs as claimed.
A.4. Proof of Lemma 3.5
Proof. Let G1 and G2 be two graphs with adjacency and features matrices A A2 and Xı * X2, respectively, Let (1) be the first weight's matrix of the first MP layers MLP and M it's associated pruning mask. Suppose A = A,,,M(), Then, we need to show that for any weight matrix W()) A,X, = A2X,
Now, assume, for contradiction, that there exists a weight matrix ((1) such that A X, W + A,X, w()), Consider the elementwise product (1)) (1) W(1, Since ( and (1) are binary matrices, this product selects certain entries of W(I.
If A A W + (1), there must exist some i, for which
((A)))),, w ((A2))).. w!)
Since we can focus on the entries selected by (!)) O (1), we consider
((A1))) (M O A w()) and ((AgX2).. (M AA)) w()))
If these two inner products differ, then there exists at least one 1, such that
(A, (M, (1) A. ( (A2X)) (M (M w W
For this difference to depend (!),, the corresponding entries of (!) and ( must be nonzero. In particular, if there discrepancy when using W(1), then choosing (1)), such that it matches the nonzero structure selected by M and Á (1) would produce the same discrepancy. Hence, difference in A, W() and A,X, would imply a difference in A,X, (1)) and (1), contradicting the initial assumption.
Thus, our contradiction shows that no such (1)) can exist. Therefore, for any W(1,, it must hold that A W(). (())
A.5. Proof of Lemma 3.6
these M indistinguishable graphs, and the pairwise indistinguishabiliy of isomorphism types of different classes equivalent to
Proof. Under the assumption that classes are uniformly represented, each of the C' classes contains about M C
18

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
assigning all M graphs single class. Then, the model correctly classifies exactly those Af graphs that truly belong the chosen class. The other M- M (1-z) ?) graphs from the remaining C classes are misclassified.
For the remaining N .M graphs. which are distinguishable isomorphism types, the model can correctly classify all of them (assuming perfect separability in the distinguishable subset).
Hence, the total number of correctly classified graphs is
M (N- M) C
Dividing by N to obtain the accuracy:
NN
M) +
M C
M
M
N
N
CN
Since M& x T substitute this into the equation:
1 T TC
Factor out ::
U -
(1-
This expression gives the maximum fraction of correctly classified graphs under the stated assumptions.
B. DATASETS
Table 2. Overview of selected datasets.
DATASET
TYPE
#GRAPHS
AvG. NODES
AVG. EDGES
LABELS
TASK
MUTAG
CHEMICAL
188
17.9
19.8
NODE, EDGE
CLASS.
AIDS
CHEMICAL
2,000
15.7
16.2
NODE, EDGE
CLASS.
PTC_FM
CHEMICAL
349
14.1
14.5
NODE, EDGE
CLASS.
PTC_MR
CHEMICAL
344
14.3
14.7
NODE, EDGE
CLASS.
NCII
CHEMICAL
4,110
29.9
32.3
NODE
CLASS.
PROTEINS
PROTEIN
1.113
39.1
72.8
NODE
CLASS.
ENZYMES
PROTEIN
600
32.6
62.1
NODE
CLASS.
MSRC_9
IMAGE
221
40.6
72.4
NODE
CLASS.
MSRC_20
IMAGE
563
77.5
142.8
NODE
CLASS.
IMDB-BINARE
SOCIAL
1,000
19.8
96.5
CLASS.
To examine the complex relationship between the Lottery Ticket Hypothesis (LTH) and the expressivity of Graph Neural Networks (GNNs), we utilize diverse set of ten real-world datasets. Each dataset is carefully selected based its relevance to distinct graph structures and domain-specing tasks. These datasets are sourced from the widely recognized TUDataset collection (Moris et al., 2020), which serves as a standard benchmark for tasks involving graph classification and regression. detailed summary of these datasets is presented Table
The MUTAG, AIDS, PTC FM, PTC MR, and NCII datasets focus on chemical compounds, where molecular structures are represented as graphs, with nodes corresponding atoms and edges denoting chemical bonds. MUTAG, one of the earliest and most widely used datasets for graph classification, comprises nitroaromatic compounds labeled by their mutagenic effects on Salmonella typhimurium. The AIDS dataset contains molecular graphs relevant to anti-HIV drug discovery, aiming to predict inhibitory activity against HIV. The PTC datasets (FM and MR) involve compounds evaluated for rodent carcinogenicity, classified based on different experimental setups. NCI1, a larger dataset derived from the National Cancer Institute's 's screening program, involves classifying compounds according to their activity against non-small cell lung cancer.
Chemical Compounds:
19

---

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Protein Structures: The PROTEINS and ENZYMES datasets derived from bioinformatics, where graphs used represent protein structures. In the PROTEINS dataset, nodes correspond secondary structural elements, such helices and sheets, with edges reflecting spatial proximity. The classification task is to determine whether given protein functions as an enzyme. The ENZYMES dataset builds on this by categorizing enzymes into one of the six top-level classes defined by the Enzyme Commission (EC), based on the types of chemical reactions they catalyze (Borgwardt et al., 2005; Schomburg et al., 2002).
The MSRC and MSRC_ datasets, originating from the MSRC database, are designed for semantic image segmentation tasks. In these datasets, images are represented as graphs, where nodes correspond to superpixels and edges capture spatial relationships between them. The task requires GNNs to classify nodes into various categories based the visual content of the superpixels. MSRC_21C serves extended version, offering greater number of classes and increased complexity (Neumann al., 2016).
Image Segmentation:
Social Networks: The HIDB-BINARY dataset represents social networks, with each graph modeling the collaboration network of actors who have appeared together in movies. The classification task involves distinguishing these networks based on the movie genre, specifically differentiating between action and romance. This dataset highlights the complexities of real-world social networks, where nodes correspond to individuals and edges represent their interactions, challenging GNNs to capture nuanced social dynamics (Yanardag Vishwanathan, 2015).
These datasets collectively offer diverse evaluation framework, encompassing wide variety of graph structures and complexities, ranging from small molecular graphs to larger social networks and image-based graphs. Leveraging this extensive set of benchmarks allows our empirical analysis to thoroughly evaluate the hypothesis across multiple domains.
20


Reviews:
[{"review_id": "mhQMxJfSp9", "reviewer": "Reviewer_3Ejh", "summary": "This paper studies the role of Graph Neural Network (GNN) expressivity in Lottery Ticket Hypothesis (LTH), in particular, the conditions NN pruning mechanisms must satisfy to maintain prediction quality. They show that trainable sparse subnetworks exist within moment-based GNNs, matching 1-WL expressivity. They also show the importance of preserving critical computational paths to prevent performance degradation. The key claim is that expressive sparse initializations improve generalization and convergence, while improper pruning can lead to irrecoverable expressivity loss.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your detailed review. Below, we address your concerns and will incorporate the corresponding changes into the final version. We are looking forward to further discussions with you.\n\n> Abstract says that [...]\n\nWe acknowledge Theorem 3.3 does not directly guarantee improved convergence or generalization but links embedding distinctiveness to gradient diversity, a known factor influencing both -- hence our cautious use of “potentially” in the abstract. Empirically (Section 5), since all models were trained for the same number of epochs, the consistently superior performance of sparse initializations with high expressivity suggests improved convergence and generalization, consistent with our theory. \n\n> Section 1.2 says [...]\n\nWith \"graph pruning\", we refer to the removal of information from input graphs (i.e. pruning adjacency matrices, node features or edge features). Criterion 1 (Section 3) covers adjacency matrix pruning via modified tuples $\\widehat{D}$ (e.g., $D_l = (\\widehat{A}, X, t)$) and requires that non-isomorphic graphs from different classes remain distinguishable; otherwise, the maximal achievable accuracy degrades. Since we focus on parameter pruning, subsequent sections address only that case.\n\n> (a) how they measure expressivity\n\nAs no standard method exists, we adopt an approach that balances efficiency and clarity.\nFor expressivity measurement, we retain one representative per isomorphism type, as isomorphic graphs yield identical embeddings by GNN permutation invariance. Let $\\{G_1,\\ldots,G_n\\}$ be the $n$ non-isomorphic graphs with embedding vectors $\\{h_{G_1},\\ldots,h_{G_n}\\}$. We mark each pair $(h_{G_i}, h_{G_j})$ as indistinguishable if $h_{G_i} - h_{G_j} = 0$. The expressivity $\\tau$ is the fraction that remains distinguishable. Alternative methods (e.g., exhaustive comparisons or training accuracy) are more costly or reflect different notions of expressivity. We chose our approach for its scalability (over 13,500 runs) and direct assessment of whether a non-isomorphic graph is distinguishable from the rest of the dataset.\n\n> (b) how they measure [...] distinguishable or not\n\nFor efficiency, we assess distinguishability by checking whether $h_{G_1} - h_{G_2} \\neq 0$ after summation-based readout of the final MP-layer outputs. This generally implies differing node-level embeddings. While distinct node embeddings can theoretically sum to the same vector, such collisions are extremely rare and occur only under measure-zero configurations.\n\n> 1. [...] one sentence spans 6-7 lines. \n\nWe will revise the relevant sections to improve clarity and conciseness.\n\n> 2. [...] explain [...] $\\vartheta$, S, and [..] “clean accuracy”\n\nThe variables $\\vartheta$ and $\\varepsilon$ in Fig. 2 are used to group similar $\\tau$ values into intervals, as observing an exact empirical value of $\\tau$ is unlikely. The set $S$ used in computing $\\overline{\\Delta}$ contains models for which $\\tau_{\\mathrm{pre}} \\in [\\vartheta \\pm \\varepsilon]$. The term \"clean accuracy\" refers to the accuracy of the dense, unpruned model.\n\n> 3. [...] how you compute the probability in Fig. 2. \n\nWe fix a target $\\vartheta$ and collect runs with $\\tau_{\\mathrm{pre}} \\in [\\vartheta \\pm \\varepsilon]$. A run is labeled a “winning ticket” if its accuracy drops by less than $5$% compared to the unpruned model. The probability is the fraction of such runs, aggregated (with subset-size normalization) to plot winning ticket probabilities across pruning levels and thresholds.\n\n> 4. Mention which dataset [...] Fig. 2.\n\nFig. 2 displays data generated from all runs and therefore all 10 datasets, which are listed in Tab. 2, Appendix B.\n\n> 5. Fig. 4 is not an ideal [...]\n\nAs illustrated in our Fig.4, none of the data points fall in the upper left half, indicating that $\\tau_{\\mathrm{post}}$ is generally lower than $\\tau_{\\mathrm{pre}}$. This supports our claim that pruned models typically do not gain expressivity during training, underscoring the importance of expressive sparse initialization.\n\n> 6. Lines 409-412 says: [...]\n\nAll columns of Tab. 1 support our claim. If a GNN initialized and trained as in lines 409–412 could reliably transition from low $\\tau_{\\mathrm{pre}}$ to high $\\tau_{\\mathrm{post}}$, then for some $\\kappa$, this would occur with a probability above a low single-digit percentage. While we do not specify a threshold for high probability, Fig. 4 reflects the trend shown in Tab. 1.\n\n> Issues with Lemma 3.6 [...]\n\nLemma 3.6 is a theoretical bound requiring knowledge of all isomorphism types, which is impractical—though tools like nauty can identify them, and many benchmarks include them. Most datasets also lack the assumed uniform class distribution. The lemma is meant to conceptually illustrate how misaligned pruning limits a GNN’s maximal accuracy. Refining it for more realistic settings is a promising direction for future work.", "claims_and_evidence": "Mostly yes. A few problematic claims are as follows:\n1. Abstract says that - “… and subsequently show that an increased expressivity in the initialization potentially accelerates model convergence and improves generalization.” => I did not find any explicit, theoretical or empirical results that support this claim. Theorem 3.3 is not conclusive in this regard. It merely suggests the following, as per the authors,  “.. a model initialized such that two graphs do not receive (partially) identical node embeddings is likely to converge faster and generalize more effectively and thus more likely to be a winning ticket in the initialization lottery, as identical embeddings are always codirectional.” To my understanding, an empirical study is lacking in the paper that directly validates this statement.\n2. Section 1.2 says -“We formally link GNN expressivity to LTH by establishing criteria that pruning mechanisms—both graph and parameter pruning must satisfy to preserve prediction quality.” => However, if \"graph pruning\" refers to pruning the adjacency matrix structure, no explicit criteria are provided to ensure the preservation of prediction quality. The absence of a rigorous theoretical or experimental analysis for graph pruning makes this claim problematic.", "methods_and_evaluation_criteria": "1. The datasets make sense as they are well-known benchmarks for graph classification tasks. \n\n2. However, the evaluation criteria appear to be vague and under-explained in Section 4. In particular, I urge the authors to please explain, with examples, (a) how they measure expressivity $\\tau$, and (b) how they measure whether two embeddings are distinguishable or not.", "theoretical_claims": "I have not carefully checked the correctness of the proofs, hence cannot comment upon their correctness.", "experimental_designs_or_analyses": "The experiments and Results section seemed rushed lacking care and clarity. A few questions/suggestions include:\n1. There are instances such as lines 352-358, where one sentence spans 6-7 lines. Consider the first paragraph in Section 5 as another example. Please simplify such sentences to improve readability. \n2. Please explain the meaning of $\\vartheta$, $S$ and the term “clean accuracy” mentioned in the caption of Figure 2. \n3. Please discuss how you compute the probability $P(WT(GNN) | \\rho , \\tau_{pre}, \\epsilon)$ in Figure 2. \n4. Mention which dataset has been used to generate Figure 2.\n5. Figure 4 is not an ideal way to represent the result, there are too many data points to understand what story they tell. \\\n6. Lines 409-412 says: “Moreover, we find that a GNN, when initialized with certain sparsity level and non-zero weights trained in isolation, is highly unlikely to transition to a higher expressivity state (Table 1).” => Based on which column(s) in Table 1 did you draw this conclusion, and how?", "relation_to_broader_scientific_literature": "Relevant to the GNN community.", "essential_references_not_discussed": "None, to the best of my knowledge.", "other_strengths_and_weaknesses": "The study is original and significant. However many parts of the paper lack clarity and readability. Some claims are problematic and some experiments were not clearly explained. Some other issues include:\n1. Issues with Lemma 3.6 => The conditions in Lemma 3.6 appears to be unrealistic, for instance, how could  someone know the  isomorphism types $I$ of a given dataset apriori? Can you empirically validate Lemma 3.6 with some of your datasets?\n2. See the Experimental Designs Or Analyses section for details on experiment-related issues. \n3. See the Methods And Evaluation Criteria section for evaluation-related issues\n4. See the Claims And Evidence section for claim-related issues.", "other_comments_or_suggestions": "1. In Section 2, line 114 is incorrect. It should be => $(\\phi(u),\\phi(v))$ in $E(H)$ for all $(u,v)$ in $E(G)$\n2. Define $\\Sigma$ in line 120 where it is used for the first time. \n3. Line 120, “A function $V(G) \\rightarrow \\Sigma$”  => A function $l: V(G) \\rightarrow \\Sigma$. \n4. The notations in section 3 could be improved and made more unambiguous.", "questions_for_authors": "Could you please clarify the issues mentioned in the Claims And Evidence section, Experimental Designs Or Analyses section, the Methods And Evaluation Criteria section, and Other Strengths And Weaknesses section?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MiDHk86n8R", "reviewer": "Reviewer_3s8a", "summary": "This paper deals with the Strong Lottery Ticket Hypothesis (SLTH) in the context of graph neural network (GNN).\nParticularly, the authors argue that there exists an initialized GNN with sufficiently high expressivity that can match the original performance after training.\nTo demonstrate this, the authors theoretically show that there exists a sparse initialized GNN that matches 1-WL expressivity and the expressive GNN can generalized comparably to the dense one.\nThe experiments demonstrate that the more expressive a sparse initialized GNN is, the better the post-training network performs, supporting the theoretical analysis.\n\n## Update after rebuttal\n\nThe authors' response has effectively addressed the raised questions, including a way to find an expressive GNN and a way to find a GLT in the context of expressivity. Thus, the reviewer has decided to maintain the original rating, 'Accept'.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We hope that our response below addresses your questions satisfactorily.\n\n> How can we find a sparse GNN with significant expressivity?\n\nFor moment-based architectures (see line 126 right column, Lemma 2.6), such as those analyzed in our work, maximal expressivity (i.e., WL-equivalence for GIN) is achieved if all aggregation and combination functions are injective over their respective domains defined by the dataset and prior operations. A simple approach to expressive pre-training sparsification is to begin at the first message-passing layer and, after initialization, for a given pruning percentage, sample $k$ configurations of that layer and select the one for which the number of unique input node vectors equals the number of unique output node vectors over all graphs. This procedure is then repeated for subsequent layers, increasing the pruning ratio until no injective configuration is found within a computationally feasible sample size $k$. The resulting network, with guaranteed injective transformations, is sparsified yet maximally expressive. We will develop and analyze more sophisticated techniques in future work.\n\n> The existing methods on the graph lottery ticket (GLT) effectively can find such a subnetwork? \n\nExisting methods typically employ iterative and/or gradient-based approaches to prune graphs or transformations in GNNs. In many cases, expressivity is either omitted entirely (e.g., [1, 2, 3, 4]) or mentioned in a side note as an important concept without further formal analysis or empirical validation (e.g., [5]). To the best of our knowledge, we are the first to provide a clear formal analysis connecting the Lottery Ticket Hypothesis for GNNs with expressivity, defined strictly as the ability to distinguish non-isomorphic graphs.\n\n> Some suggestions for finding GLT and analyzing the previous GLT method in the context of expressivity would make this paper more interesting.\n\nWe do not search graph lottery tickets (GLTs), which prune the input graphs, but focus on the effect of pruning the parameters of the learnable transformations of a GNN on its expressivity. We consider developing practical, expressivity-oriented pruning methods based on the theoretical insights of our work and the comparison to existing pruning methods a highly relevant topic for future research that we definitely want to explore further.\n\n> In GNN, the authors analyze the lottery ticket hypothesis from the lens of expressivity. Then, I’d like to ask what the analogous concept of expressivity is in the context of other neural networks, such as CNNs or MLPs?\n\nIn the context of CNNs and MLPs, the analogous term typically used is expressive power. For MLPs, expressive power refers to the class of functions that can be approximated under architectural constraints (width, depth, activation), while for CNNs, it describes the types of features extracted by convolutional filters. However, the definition remains vague for CNNs and MLPs, lacking a baseline comparison like the WL test and its variants in GNNs.\n\n[1] T. Chen et. al, A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML, 2021\n\n[2] B. Hui et. al, Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR, 2023\n\n[3] A. Tsitsulin, The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure, CoRR/abs.2312.04762, 2023\n\n[4] Y.D. Sui et al., Inductive Lottery Ticket Learning for Graph Neural Networks, Journal of COmputer Science and Technology, 2023\n\n[5] K. Wang et al., Searching Lottery Tickets in Graph Neural Networks: A Dual Perspective, ICLR, 2023", "claims_and_evidence": "The authors claim that a sparse initialized GNN exists with maximally expressive paths, and such a network potentially generalizes comparably to a dense network.\nThe proposed theoretical and empirical evidence effectively support the authors' claim.", "methods_and_evaluation_criteria": "The authors do not propose a method and investigate the relationship between the expressivity of an initialized network and the performance (or expressivity) of a trained network.\nIn Figure 4, the authors present this relationship across various pruning ratios and datasets, and in Figure 3, the authors adopt Pearson correlation to evaluate the relationship.", "theoretical_claims": "In appendix A, the authors prove the existence of maximally expressive paths within an initialized GNN and the trainability of a sparse network with the paths.\nThe proofs are well derived, and I did not find any significant issues.", "experimental_designs_or_analyses": "For experiments, the authors focus on investigating the relationship between the expressivity of an initialized network and the performance (or expressivity) of a trained network.\nThe plot in Figure 4 and the Pearson correlation in Figure 3 clearly demonstrate the relationship.", "relation_to_broader_scientific_literature": "As someone unfamiliar with GNNs, I find that the authors effectively introduce the necessity of revealing the key to GNN generalization.\nIt is interesting to see the connection between pre-training expressivity and post-training generalization, and I believe this observation makes a significant contribution to the literature.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "All are mentioned in other sections.", "other_comments_or_suggestions": "How can we find a sparse GNN with significant expressivity?\nThe existing methods on the graph lottery ticket (GLT) effectively can find such a subnetwork?\nSome suggestions for finding GLT and analyzing the previous GLT method in the context of expressivity would make this paper more interesting.", "questions_for_authors": "In GNN, the authors analyze the lottery ticket hypothesis from the lens of expressivity.\nThen, I’d like to ask what the analogous concept of expressivity is in the context of other neural networks, such as CNNs or MLPs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L8CkW0L76V", "reviewer": "Reviewer_wwh4", "summary": "The paper explores the connection between the Weisfeiler-Lehman (WL) test and the Lottery Ticket Hypothesis (LTH). The authors establish criteria for pruning mechanisms, requiring that the pruned network remain as expressive as the original in terms of the WL test to preserve its performance. They define the concept of \"critical paths\"—key weight subsets essential for distinguishing non-isomorphic graphs—and demonstrate that there exists a subset of weights in the original network which will distinguish the same set of graphs as the original network. Additionally, they analyze how selecting suboptimal \"lottery tickets\" (in terms of expressivity) impacts classification accuracy, both theoretically and empirically.\n\n#### update\nI am satisfied with the author response to my questions. I think this is an interesting piece of work so I maintain my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your review and hope our response below satisfactorily addresses your questions.\n\n> However, I think one could further strengthen the experiments by also considering attention-based graph neural networks such as GAT.\n\nOur theoretical results apply to general moment-based GNN architectures and we thus expect the formal insights we develop -- e.g., the connection between pruning, critical path removal, and loss of expressivity (e.g., Theorem 3.2, Lemma 3.5) -- to apply broadly across this architectural class, which includes GAT as well. As such, our upper bounds on achievable classification accuracy under misaligned pruning (e.g., Lemma 3.6) also hold. We emphasize that these bounds are theoretical and are meant to illustrate structural limitations.\n\nHowever, refining our formal analysis to architectures beyond this most general setting, (including the effects of attention or edge features that modulate aggregation) is a promising direction for future work which might reveal additional, architecture-specific vulnerabilities not covered by our existing work.\n\nWe acknowledge that an empirical evaluation would underpin any theoretical deliberations concerning GAT and LTH.\n\n> Finally, the authors use random pruning but I wonder if the authors have thought of any heuristics for which we can use for pruning which intuitively align with keeping critical paths in the network?\n\nAs stated in our response to Reviewer 3s8a, an iterative pruning mechanism that enforces injectivity of each transformation on its local input domain would be maximally expressive on a given dataset, thus preserving the paths needed for the GNN to distinguish non-isomorphic graphs associated with different classes.\n\n> I believe that the authors mainly consider classification tasks in their paper (esp. re: Lemma 3.6 which considers how the quality of lottery tickets affects accuracy) -- it wasn't clear to me at first, so maybe they can mention that more clearly in their contributions. \n\nThis is correct—we consider the graph classification setting. However, with minor adjustments, our results could likely also be transferred to node classification scenarios. We will clarify this in the final version of the paper.\n\n> In particular, I would be interested to see if their results would hold empirically for less expressive architectures (such as max/min-aggregation GNNs) i.e. we see similar trends as GCN and GIN when we prune out weights for max/min aggregation networks or maybe because these networks are inherently less expressive, the drop in accuracy would not be as dramatic?\n\nThis is an interesting thought. The impact of pre-training pruning on expressivity might be less dramatic because there is simply less expressivity to lose. However, this also implies that the benefits of preserving expressivity (such as faster convergence and improved generalization) might not be as pronounced for these architectures. \n\nWe set up experiments to test your hypothesis for both min and max aggregation in GIN/GCN. Preliminary results indicate that a) at least for max aggregation and low pruning percentages (< 50%), the accuracy drop with respect to an unpruned model also using max aggregation appears to be less pronounced than for add aggregation and b) that the probability that a given sparse initialization is a winning ticket seems to be less dependent on the model (i.e. GCN or GIN), which make sense, considering that using max aggregation likely reduces the differences in expressivity of GCN and GIN in general. The overall trend and relation to expressivity we observe, however, appears to be comparable to the one we observed for GIN/GCN with add aggregation.\n\nGiven the timeframe of the rebuttal & discussion and the runtime of our setup (~8 weeks, compare line 352), we can likely only provide preliminary results, which might not be statistically reliable. We will consider including the full results for min/max aggregation in the final version of the paper.\n\n> (1) on line 187-190, the authors start using $\\widehat{D}$ and $\\widehat{\\Phi}$. I assume that this means a pruned set of graphs and a pruned network but I didn't see this defined previously. \n\nIndeed, in lines 187-190  $\\widehat{D}$ and $\\widehat{\\Phi}$ refer to pruned models or a dataset of pruned graphs, but we used the more general term “modified” there, as Criterion 1 is not only specific to pruning (which, at least for graphs, can take multiple forms—such as adjacency matrix pruning or node/edge feature pruning) but could potentially also be extended to, for example, quantization.\n\n> (2) In Lemma 3.6, they say and $U \\leq I$ guess that $U$ is the set of graph types which are not distinguishable by the model in question but perhaps they can say this more clearly.\n\n$U$ in Lemma 3.6 represents the number of isomorphism types of dataset $D$ which are indistinguishable from at least one other isomorphism type present in the dataset. We will clarify this in the final version of the paper.", "claims_and_evidence": "All claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The benchmarks make sense for the problem.", "theoretical_claims": "I checked the proof for Theorem 3.2 and I did not find any issues.", "experimental_designs_or_analyses": "Overall, the experiments are quite thorough -- the authors test on standard graph benchmarks. However, I think one could further strengthen the experiments by also considering attention-based graph neural networks such as GAT. I would also be curious to see if the results hold for \"less expressive\" GNN architectures which use max/min-aggregation. Finally, the authors use random pruning but I wonder if the authors have thought of any heuristics for which we can use for pruning which intuitively align with keeping critical paths in the network?", "relation_to_broader_scientific_literature": "Both the lottery ticket hypothesis and the Weisfeiler-Lehman test are well-studied in previous literature. In particular, [XHLJ '19] explicitly connect the WL-test to GNN expressivity and argue that any GNN with an injective aggregation and readout function will have the same expressivity as the WL test. Additionally, to the best of my knowledge, graph LTH was introduced in  [CSCZW '21] but it seems that most work in graph LTH is mostly empirical work which is focused on different pruning techniques. This paper connects GNN expressivity with LTH research and establishes conditions under which the expressivity of a trained network will be maintained even after pruning. \n\n\"How powerful are Graph Neural Networks\" [XHLJ '19]\n \"A unified lottery ticket hypothesis for graph neural networks\" [CSCZW '21]", "essential_references_not_discussed": "I am not aware of any essential references which are not discussed.", "other_strengths_and_weaknesses": "Strengths: To the best of my knowledge, the link between the lottery ticket hypothesis to the Weisfeiler-Lehman test (a common way for people measure the expressivity of GNNs) has not been explored so this paper represents an exciting contribution linking GNN expressivity with LTH. The theoretical contributions are also well-supported by the experiments and provide some theoretical insight as to how practitioners should prune networks and what kind of features they might want to preserve during pruning. \n\nWeaknesses: I already made a comment above regarding the experiments but I'll also make a comment here -- I think the experiments (while already extensive) could be further improved by considering more network varieties than just GIN and GCN. In particular, I would be interested to see if their results would hold empirically for less expressive architectures (such as max/min-aggregation GNNs) i.e. we see similar trends as GCN and GIN when we prune out weights for max/min aggregation networks or maybe because these networks are inherently less expressive, the drop in accuracy would not be as dramatic?", "other_comments_or_suggestions": "I believe that the authors mainly consider classification tasks in their paper (esp. re: Lemma 3.6 which considers how the quality of lottery tickets affects accuracy) -- it wasn't clear to me at first, so maybe they can mention that more clearly in their contributions. \n\nThere were also several places where I got a bit confused with the notation, maybe the authors can add some clarifications:\n\n(1) on line 187-190, the authors start using $\\hat{D}$ and $\\hat{\\phi}$. I assume that this means a pruned set of graphs and a pruned network but I didn't see this defined previously. \n\n(2) In Lemma 3.6, they say $U \\leq I$ and I guess that U is the set of graph types which are not distinguishable by the model in question but perhaps they can say this more clearly.", "questions_for_authors": "I have no questions which will change my evaluation of the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission mainly focuses on the lottery tickets hypothesis in graphs. Although there are lots of existing studies in GNN LTH, the authors study the problem from a novel angle. They theoretically show that there exists a sparse initialized GNN that matches 1-WL expressivity, and the expressive GNN can generalize comparably to the dense one. They also show the importance of preserving critical computational paths to prevent performance degradation. Overall, we believe it is a strong paper and we recommend an acceptance.
Decision: Accept (poster)