Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win

We thank you for your review and hope our response below satisfactorily addresses your questions.

However, I think one could further strengthen the experiments by also considering attention-based graph neural networks such as GAT.

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

However, 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.

We acknowledge that an empirical evaluation would underpin any theoretical deliberations concerning GAT and LTH.

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?

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

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.

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

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?

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

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

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

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

Indeed, 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.

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

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

Thank you for your thoughtful review. We hope that our response below addresses your questions satisfactorily.

How can we find a sparse GNN with significant expressivity?

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

The existing methods on the graph lottery ticket (GLT) effectively can find such a subnetwork?

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

Some suggestions for finding GLT and analyzing the previous GLT method in the context of expressivity would make this paper more interesting.

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

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?

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

[1] T. Chen et. al, A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML, 2021

[2] B. Hui et. al, Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR, 2023

[3] A. Tsitsulin, The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure, CoRR/abs.2312.04762, 2023

[4] Y.D. Sui et al., Inductive Lottery Ticket Learning for Graph Neural Networks, Journal of COmputer Science and Technology, 2023

[5] K. Wang et al., Searching Lottery Tickets in Graph Neural Networks: A Dual Perspective, ICLR, 2023

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.

Abstract says that [...]

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

Section 1.2 says [...]

With "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.

(a) how they measure expressivity

As no standard method exists, we adopt an approach that balances efficiency and clarity. For 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.

(b) how they measure [...] distinguishable or not

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

1. [...] one sentence spans 6-7 lines.

We will revise the relevant sections to improve clarity and conciseness.

2. [...] explain [...] $\vartheta$, S, and [..] “clean accuracy”

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

3. [...] how you compute the probability in Fig. 2.

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

4. Mention which dataset [...] Fig. 2.

Fig. 2 displays data generated from all runs and therefore all 10 datasets, which are listed in Tab. 2, Appendix B.

5. Fig. 4 is not an ideal [...]

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

6. Lines 409-412 says: [...]

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

Issues with Lemma 3.6 [...]

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