Pith. sign in

REVIEW 5 major objections 5 minor 59 references

Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win

T0 review · 5 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A sparse GNN keeps its full power exactly when pruning preserves its ability to distinguish non-isomorphic graphs, and the paper proves this is always possible in sufficiently wide moment-based networks.

desk verdict SELTH is a plausible and interesting conjecture with a solid empirical correlation, but Theorem 3.2's proof has two unclosed gaps—layer composition and aggregate collisions—so the theory is not yet a theorem. read the letter →

arxiv 2506.03919 v1 pith:PFSKP6ED submitted 2025-06-04 cs.LG

Lorenz Kummer , Samir Moustafa , Anatol Ehrlich , Franka Bause , Nikolaus Suess , Wilfried N. Gansterer , Nils M. Kriege This is my paper
classification cs.LG MSC 68T0705C6068R10
keywords lotterytickethypothesisgraphneuralnetworksexpressivityWeisfeiler-Lemantestnetworkpruningwinningticketsgradientdiversitymoment-basedGNNs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the lottery ticket phenomenon in graph neural networks is governed by expressivity: a sparse, randomly pruned GNN can match the full network only if it retains the ability to distinguish non-isomorphic graphs, as measured by the Weisfeiler-Leman (WL) test. It proves a Strong Expressive Lottery Ticket Hypothesis for moment-based GNNs: for any finite set of non-trivial graphs and any sufficiently wide network whose aggregation separates a node's own features from its neighbors' features, there is a pruned subnetwork whose paths and trainable weights still distinguish every pair of graphs that the $k$-iteration WL test distinguishes. It further links this expressivity to training dynamics, showing that more expressive sparse initializations yield higher gradient diversity, faster convergence, and better generalization, and it identifies pruning mistakes that destroy distinguishability irrecoverably. The practical stake is that pruning in safety-critical applications such as drug discovery can silently erase the difference between toxic and non-toxic stereoisomers, an error no amount of training can undo.

What carries the argument

The load-bearing object is the maximally expressive path set $P_{\Phi^{(k)},E}$: a subset of the MLP computational paths that remains after pruning, together with weights that make the GNN as expressive as the $k$-iteration WL test on the dataset. It is constructed through a layer-injectivity bound under random pruning, $\gamma \ge 1-\binom{N}{2}\rho^{km}$, where $N$ is the number of distinct inputs, $\rho$ the pruning rate, $m$ the layer width, and $k$ the minimum number of non-zero components in pairwise input differences; this guarantees that a sufficiently wide random sparse layer is injective on a finite input set with high probability. The argument also uses critical paths (pre-training), gradient diversity $\Delta_s$ as a bridge from embedding geometry to convergence, and structurally isomorphic, feature-divergent graphs (SIFDGs) as the worst-case objects for irrecoverable expressivity loss. A moment-based GNN here is a message-passing network whose layer update applies an MLP to the sum of a node's own embedding and the embeddings of its neighbors.

What would settle it

Take a finite dataset containing a pair of graphs distinguishable by the $k$-iteration WL test, choose a sufficiently overparameterized moment-based GNN satisfying the aggregation condition, and prune to the claimed sparsity; if some $k$-WL-distinguishable pair remains indistinguishable for every retained path set and every weight assignment, Theorem 3.2 is false. A cheaper targeted test: prune only the first layer so that two structurally isomorphic, feature-distinct graphs collapse, then train the remaining weights; Lemma 3.5 predicts the collapse persists for any training, so any restoration of separation would falsify that lemma.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 3.2: in any sufficiently overparameterized moment-based graph neural network whose aggregation rule can tell a node's own features apart from its neighbors' aggregate, there exist subsets of maximally expressive paths --- with trainable weights --- such that the pruned network reproduces the discriminative power of the $k$-iteration WL test on any finite dataset of non-trivial graphs. The proof runs through layer injectivity: with enough width, random pruning leaves an injective sparse linear layer with probability at least $1-\binom{N}{2}\rho^{km}$, and injective layers compose into an MLP that is injective on the finite set of neighborhood aggregates, which by the GIN-style sufficient condition makes the whole GNN as expressive as 1-WL. The paper calls this the Strong Expressive Lottery Ticket Hypothesis, a GNN-specific strengthening of the strong lottery ticket hypothesis, and derives that every critical path set --- paths whose removal would prevent separating two isomorphism types of different classes --- sits inside such a maximally expressive path set. Trainability of the surviving weights is shown separately by a backpropagation argument, so the pruned subnetwork is a genuine winning ticket candidate rather than merely an expressive function.

Load-bearing premise

The proof of layer injectivity assumes each MLP layer sees a fixed, finite set of continuous feature vectors whose pairwise differences have a known number of non-zero entries, but in a real GNN deeper layers see features produced by the same pruned weights under analysis, so the guarantee about those differences and their bounds does not automatically survive stacking layers.

Editorial extensions

If this is right

  • Pruning a GNN preserves predictive performance exactly when the subnetwork keeps distinguishing all WL-distinguishable graph pairs that belong to different classes; any mask that deletes a critical path cannot be a winning ticket.
  • For sufficiently wide moment-based GNNs, winning tickets exist at arbitrary non-trivial sparsity: a randomly pruned subnetwork can match the full model's expressivity and remains trainable.
  • High expressive sparse initializations should converge faster and generalize better, because diverse node embeddings raise gradient diversity, giving the lower bound $\Delta_s \ge \zeta \propto (\sum_{ij}|\cos\beta_{ij}|)^{-1}$.
  • Expressivity loss from pruning is generally not recovered by training: the empirical probability of moving from low pre-training expressivity to high post-training expressivity is in the low single digits in the paper's experiments.
  • In datasets with structurally identical graphs that differ only by features, a misaligned first-layer mask caps achievable accuracy at $1-(1-1/C)U/I$, making expressivity-preserving pruning a safety requirement rather than merely an efficiency option.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's results suggest a cheap screening rule the authors do not state: measure pre-training expressivity $\tau_{\mathrm{pre}}$ of a pruned candidate before training and reject tickets below a threshold, since recovery is empirically rare; this could replace expensive full training runs in pruning schedules.
  • Because the layer-injectivity guarantee depends on width and on the minimum number of non-zero components in pairwise input differences, feature sparsity weakens the guarantee: deeper layers fed by one-hot discrete features are the least protected, so architectures that map inputs to dense embeddings before message passing should be safer under aggressive pruning.
  • The same expressivity lens should transfer to node-level tasks and to higher-order WL hierarchies, where the analogous claim would be that a sparse subnetwork must preserve the relevant color refinement to remain a winning ticket.
  • A testable extension is to run the same $\tau_{\mathrm{pre}}$-versus-post-training-accuracy protocol on attention-based GNNs or graph transformers; if the correlation persists, expressivity rather than architecture is the dominant factor in lottery ticket success.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper investigates the lottery ticket phenomenon for graph neural networks and argues that the expressivity of a sparse initialization—its ability to distinguish non-isomorphic graphs relative to the Weisfeiler-Leman test—is a key determinant of whether the pruned subnetwork is a winning ticket. It formalizes a Strong Expressive Lottery Ticket Hypothesis (SELTH) and proves Theorem 3.2, claiming that for any finite dataset, a sufficiently overparameterized moment-based GNN contains pruned subnetwork paths that, with suitable weights, match 1-WL expressivity. It also proves a gradient-diversity bound (Theorem 3.3), identifies irrecoverable expressivity loss under first-layer pruning (Lemma 3.5), derives an accuracy ceiling under such pruning (Lemma 3.6), and reports extensive experiments on ten TU datasets with 13,500 training runs supporting a correlation between pre-training expressivity and winning-ticket probability.

Significance. If the main theorem were fully established, the paper would provide a valuable theoretical bridge between the lottery ticket hypothesis and GNN expressivity, a connection that has so far been largely empirical. The concept of maximally expressive paths, the formal SELTH statement, and the irrecoverable-loss analysis for SIFDGs are original and potentially useful for designing principled pruning algorithms. The paper also ships reproducible code and a large-scale experimental study, which is a strength. However, the central proof currently contains load-bearing gaps: the layer-wise injectivity argument does not compose across GNN layers, the aggregation rule in Equation (1) does not satisfy the injectivity condition required by Lemma 2.1, and the trainability proof relies on assumptions that are incompatible with the experiments. The empirical correlation is also partly built into the definitions of expressivity and winning tickets. The result is therefore conditional rather than established.

major comments (5)
  1. [Appendix A.1, Lemma A.1 and proof of Theorem 3.2] Lemma A.1 does not compose across GNN layers. It assumes a fixed finite input set X whose elements have continuous entries bounded by [c,d] and a known value k = min number of non-zero components of pairwise differences. In the actual architecture, the first GNN layer receives one-hot discrete features, so the input set is not continuous, and every deeper layer receives outputs of the same pruned weights whose random pruning is the event being bounded. Consequently, neither the boundedness of entries nor the support size k of pairwise differences can be fixed a priori, and the product-style bound for the whole GNN given after Lemma A.1 treats dependent events as independent. The proof of Theorem 3.2 therefore does not establish the claimed existence of pruned weights that keep the entire GNN injective on D.
  2. [Section 2, Lemma 2.1 and Equation (1)] Lemma 2.1 is invoked as a sufficient condition for 1-WL expressivity, but the aggregation rule in Equation (1), s_v = h_v + sum_{u in N(v)} h_u, is not injective as a map from the WL-refined pair (h_v, multiset of neighbor features) to aggregate vectors. For scalar features, the pairs (h_v=0, multiset {1,2}) and (h_v=1, multiset {0,1}) both map to the same aggregate value 3. Distinct WL-refined pairs can therefore collide to the same MLP input, and Lemma A.1's layer-wise injectivity on the set of aggregate vectors cannot separate them; equality propagates through all later injective layers. Theorem 3.2 needs an additional non-collision argument showing that the chosen pruned weights produce distinct aggregates for every WL-distinguishable pair. Moreover, the hypothesis that the aggregation rule distinguishes a node's own features from neighbor aggregates is not satisfied by Equation (1), which lacks a (1+epsilon) term as in GIN.
  3. [Appendix A.2, Lemma A.2] The trainability proof is not valid for the architecture used in the experiments. It assumes an injective, zero-fixing activation with a nowhere-zero derivative, but the experiments use ReLU, which has zero derivative on the negative half-axis and is not injective. The proof also infers from a nonzero forward activation sigma(Z_pi) != 0 that the corresponding gradient factors in Equation (6) are nonzero, but with ReLU, sigma'(Z)=0 for Z<0, so the displayed terms can vanish. In addition, the backpropagation formulas in Equations (4)-(9) do not include the graph-level readout of Equation (2) or the (A+I) update of Equation (1), so the claim that every weight in a maximally expressive path set can receive a nonzero gradient is not proven for the actual forward pass.
  4. [Appendix A.4, Lemma 3.5] The proof of Lemma 3.5 does not correctly model pruning. It writes the condition A1 X1 M(1) = A2 X2 M(1), as if the mask M(1) were applied to the feature matrix, but in the forward pass the mask is applied to the weight matrix, not to the node features. The actual condition under which no surviving weight can distinguish the two graphs is a linear-algebraic statement about differences (X1 - X2) restricted to unpruned weight columns, and this condition is not derived in the proof. As stated, the irrecoverable-loss lemma is therefore unsupported.
  5. [Section 4 and Section 5] The empirical correlation between pre-training expressivity and winning-ticket probability is partly built into the measurement choices. Expressivity tau_pre is measured as the fraction of non-isomorphic graph pairs distinguished by the graph-level sum of node embeddings, and a winning ticket is defined by post-training accuracy degradation of less than 0.05 relative to the dense model. A model that cannot distinguish graphs of different classes cannot achieve high accuracy, so the positive correlation between tau_pre and winning-ticket probability is at least partially tautological. To support the causal interpretation in Section 5, the authors should control for accuracy ceilings, for example by restricting the expressivity measure to graph pairs of different classes or by conditioning on dense-model accuracy.
minor comments (5)
  1. [Section 4] The claim that sum-level FLOAT32 collisions 'are extremely rare and occur only under measure-zero configurations' is not justified for one-hot discrete inputs and small network widths; the paper should report node-level comparisons or multiple random projections to make the expressivity measurement more robust.
  2. [Table 1] The table header and row order are hard to read: the threshold values are listed in decreasing order while the probability row is not visually aligned with the threshold columns, and the first entry (0.00 at kappa=1.00) is easy to misread as a measurement rather than a boundary value.
  3. [Figure 3] The caption refers to 'left' and 'right' panels, but the panels are not explicitly labeled in the caption text; please label them (a) and (b) and refer to them consistently in Section 5.
  4. [Equation (15)] The bound involving M and the cosine terms is correct up to the squared norm bound, but the transition from the Frobenius norm bound to the sum of absolute cosines in the statement of Theorem 3.3 should be made explicit, as the lower bound zeta also depends on the other gradient factors in Equation (16).
  5. [Section 2 and throughout] The paper alternates between 'moment-based GNN' as defined by Equation (1) and GIN-style updates with a learnable (1+epsilon) factor; please state once which aggregation rule Theorem 3.2 applies to, since Equation (1) and Lemma 2.1 describe different architectures.

Circularity Check

2 steps flagged · score 4.0 of 10

Partial tautology in the expressivity-accuracy link, while the main WL-existence theorem is an independent formal result.

  1. self definitional [Section 3, Criterion 1 (page 4)]
    "Criterion 1. For Φ(k+1) (or bΦ(k+1)) to classify all graphs in D (or bD) correctly, Φ(k) (or bΦ(k)) must distinguish all pairs of non-isomorphic graphs of different classes."

    This is a definitional necessary condition: 'classify correctly' is operationalized through a perfect classifier C that assigns distinct embeddings to distinct classes, so if two graphs of different classes receive the same embedding, correct classification is impossible by construction. The paper subsequently uses this criterion to argue that expressivity is crucial for winning tickets, and the empirical finding that low pre-training expressivity predicts low post-training accuracy is partly this same identity, because a winning ticket is defined by test accuracy and accuracy is capped by the fraction of distinguishable different-class pairs.

  2. self definitional [Section 3.3, Lemma 3.5 (page 6)]
    "If the pruning mask of the first layer of the MP layer's MLP—when applied in isolation—renders the graph representations indistinguishable, then no choice of weights can restore the ability to distinguish between the two graphs."

    The 'irrecoverable loss of expressivity' is a direct consequence of the meaning of the assumption: once the first-layer representation is rendered indistinguishable, every downstream transformation is a deterministic function of that representation, so no later weights can create a distinction that the input no longer contains. The proof restates this by assuming A1X1M(1) = A2X2M(1) and then concluding equality for all weight matrices under the masked forward pass, which is essentially the same indistinguishability condition expressed algebraically. It is a valid necessary-condition observation, but it is definitional rather than an independent derivation of an expressivity boundary.

full rationale

The central contribution, Theorem 3.2 (SELTH), is a formal existence argument built on Lemma A.1 and the externally sourced Lemma 2.1 (Xu et al., 2019), and it is not fitted to the experiments; the same holds for Theorem 3.3 and Proposition 3.4. There are no load-bearing self-citations: the Kummer et al. references are motivational or directional, not the basis of the uniqueness or existence claims. The circularity burden is limited to the definitional coupling between expressivity and classification: Criterion 1 states the tautological necessary condition that different labels require distinguishable embeddings, and Lemma 3.5 derives irrecoverability from the assumed indistinguishability. Consequently, the empirical correlation between pre-training expressivity and winning-ticket probability is partly built in at the low-expressivity end, though the formal WL-expressivity theorems remain independent content. Correctness concerns about Lemma A.1's composition over GNN layers and about possible collisions in aggregate vectors are substantive but are not circularity, so they do not raise the score further.

Assumptions & free parameters 3 free parameters · 6 assumptions · 2 invented entities

The central claim rests on a chain of assumptions: the known GNN expressivity lemma (Xu et al.), continuous bounded weight and input distributions, a restrictive activation class, a perfect classifier, and an ideal uniform class distribution for the accuracy bound. The most fragile are the continuous-input assumption and the activation restriction, because the experiments use one-hot discrete features and ReLU.

free parameters (3)
  • winning ticket accuracy threshold delta = 0.05 relative accuracy decrease
    Hand-chosen threshold in Section 4 that decides whether a sparse model is called a winning ticket; all empirical probabilities depend on it.
  • expressivity bin tolerance epsilon = not reported
    Used in Figure 2 to group runs with tau_pre in intervals [theta +/- epsilon]; the value is not stated and affects the probability estimates.
  • float32 exact-equality criterion for expressive pairs = 0.0 (exact equality)
    The expressivity measure tau declares a graph pair indistinguishable only when summed node embeddings are exactly equal in float32; this is an operational definition rather than a fitted value, but it strongly shapes all reported expressivity numbers.
assumptions (6)
  • domain assumption A moment-based GNN with injective MLPs and aggregation that separates a node's own features from neighbor aggregates matches 1-WL expressivity (Lemma 2.1, from Xu et al., 2019).
    Taken as a known result and used to define what maximal expressivity means in Theorem 3.2.
  • domain assumption Weight matrices are drawn independently from a continuous bounded distribution, and each layer has width m large enough to satisfy m >= log_rho((1-gamma)/C(N,2)) * k^{-1} (Lemma A.1).
    Required for the probabilistic injectivity bound and the definition of 'sufficiently overparameterized'.
  • ad hoc to paper The input set X to each MLP layer consists of vectors with continuous entries bounded by [c,d].
    Assumed in Lemma A.1; not satisfied by one-hot first-layer features and not established for deeper layers whose inputs depend on the same random pruned weights.
  • domain assumption The activation function sigma is injective, continuously differentiable, zero-fixing, and has nowhere-zero derivative.
    Stated in Section 3 before Theorem 3.2; it excludes ReLU, which is used in the experiments.
  • domain assumption A perfect classifier C exists that maps distinct embeddings to distinct class labels (supported by Chen et al., 2019).
    Used to derive classification guarantees from Theorem 3.2.
  • domain assumption For Lemma 3.6, classes are evenly distributed and indistinguishable isomorphism types are spread uniformly across classes, so M is approximately U*N/I.
    The paper itself notes this is impractical for most datasets; it is only a conceptual bound.
invented entities (2)
  • SIFDG (Structurally Isomorphic, Feature-Divergent Graphs)
    purpose: Names the class of graphs with permutation-equivalent adjacency matrices and distinct feature matrices for which first-layer pruning can irrecoverably remove distinguishability (Lemma 3.5).
    A definitional taxonomy introduced in the paper; it makes no falsifiable prediction outside the paper.
  • SELTH (Strong Expressive Lottery Ticket Hypothesis)
    purpose: The claim that sufficiently overparameterized moment-based GNNs contain sparse subnetworks that match 1-WL expressivity at initialization and are trainable.
    A named hypothesis argued for entirely within this paper; its only support is the paper's own proof and experiments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win." pith.science (2026). https://pith.science/paper/PFSKP6ED

@misc{pith2026250603919,
  author       = {Pith},
  title        = {Pith review of: Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PFSKP6ED}},
  note         = {Machine review of arXiv:2506.03919}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2506.03919 by the authors.

Figure 1
Figure 1. Visualization of thalidomide (also known as under its trade name Contergan) and its embryotoxic stereoisomer as an exemplary SIFDG, for which a failure to distinguish the two can have potentially life altering consequences for patients. As shown on the right-hand side of the figure, the aggregates of nodes N1 and N2 in the first layer differ by only a single feature. A pruning mask removing the red dashed edges from… view at source ↗
Figure 2
Figure 2. Probability that a sparse GIN or GCN is a winning ticket (WT), given pruning ρ ∈ [10, 90]%, expressivity τpre s.t. ϑ − ε ≤ τpre ≤ ϑ + ε, tolerance ε (left). ϑ and ε are used to group similar τpre into intervals, as observing an exact empirical value of τpre is unlikely. Mean relative test accuracy, ∆ = |S| −1P i∈S (A (i) post − Aclean)(Aclean) −1 , where Aclean is clean test accuracy of the dense, unpruned model, A … view at source ↗
Figure 3
Figure 3. Statistical significance of Pearson correlation between untrained pruned model expressivity τpre (ρ ∈ [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 to the quality of a lottery ticket. De￾pending on the number of 1-WL distinguishable isomor￾phism types for which distinction in the first… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Visualization of untrained (τpre) and post-training (τpost) expressivity of pruned models (ρ ∈ [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) to (1,1) indicates hypothetical pre…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

59 extracted references · 53 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    and Yahav, E

    Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. International Conference on Learning Representations (ICLR), 2021

    work page 2021

  3. [3]

    Neural injective functions for multisets, measures and graphs via a finite witness theorem

    Amir, T., Gortler, S., Avni, I., Ravina, R., and Dym, N. Neural injective functions for multisets, measures and graphs via a finite witness theorem. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 42516--42551, 2024

    work page 2024

  4. [4]

    N., and Kriege, N

    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

    work page 2024

  5. [5]

    M., Ong, C

    Borgwardt, K. M., Ong, C. S., Sch \"o nauer, S., Vishwanathan, S., Smola, A. J., and Kriegel, H.-P. Protein function prediction via graph kernels. Bioinformatics, 21: 0 47--56, 2005

    work page 2005

  6. [6]

    The contergan scandal

    B \"o sl, E. The contergan scandal. media, medicine, and thalidomide in 1960s west germany. Disability Histories, pp.\ 136--162, 2014

    work page 2014

  7. [7]

    A unified lottery ticket hypothesis for graph neural networks

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

    work page 2021

  8. [8]

    You are caught stealing my winning lottery ticket! making a lottery ticket claim its ownership

    Chen, X., Chen, T., Zhang, Z., and Wang, Z. You are caught stealing my winning lottery ticket! making a lottery ticket claim its ownership. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 1780--1791, 2021 b

    work page 2021

Show all 59 references
  1. [9]

    On the equivalence between graph isomorphism testing and function approximation with gnns

    Chen, Z., Villar, S., Chen, L., and Bruna, J. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 15894 -- 15902, 2019

    2019

  2. [10]

    and Moura, J

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

    2020

  3. [11]

    Proving the strong lottery ticket hypothesis for convolutional neural networks

    da Cunha, A., Natale, E., and Viennot, L. Proving the strong lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations (ICLR), 2022

    2022

  4. [12]

    Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning (ICML), pp.\ 7865--7885, 2023

    2023

  5. [13]

    A., Bianchini, M., Sampoli, M

    D’Inverno, G. A., Bianchini, M., Sampoli, M. L., and Scarselli, F. A unifying point of view on expressive power of GNNs . CoRR, abs/2106.08992, 2021

    2021 arXiv

  6. [14]

    and Carbin, M

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

    2018

  7. [15]

    K., Roy, D

    Frankle, J., Dziugaite, G. K., Roy, D. M., and Carbin, M. Stabilizing the lottery ticket hypothesis. CoRR, abs/1903.01611, 2019

    1903 arXiv

  8. [16]

    Predicting the survival of cancer patients with multimodal graph neural network

    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 0 (2): 0 699--709, 2022

    2022

  9. [17]

    and Bengio, Y

    Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp.\ 249--256, 2010

    2010

  10. [18]

    Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

    He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In International conference on computer vision (ICCV), pp.\ 1026--1034, 2015

    2015

  11. [19]

    Rethinking graph lottery tickets: Graph sparsity matters

    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

    2023

  12. [20]

    Theory of graph neural networks: Representation and learning

    Jegelka, S. Theory of graph neural networks: Representation and learning. CoRR, abs/2204.07697, 2022

    2022 arXiv

  13. [21]

    Not too little, not too much: a theoretical analysis of graph (over) smoothing

    Keriven, N. Not too little, not too much: a theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems (NeurIPS), 35: 0 2268--2281, 2022

    2022

  14. [22]

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

    2023

  15. [23]

    N., and Kriege, N

    Kummer, L., Moustafa, S., Schrittwieser, S., Gansterer, W. N., and Kriege, N. M. Attacking graph neural networks with bit flips: Weisfeiler and L eman go indifferent. In International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD), 2024

    2024

  16. [24]

    N., and Kriege, N

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

    2025

  17. [25]

    and Knapp, K

    Lenz, W. and Knapp, K. Thalidomide embryopathy. Archives of Environmental Health: An International Journal, 5 0 (2): 0 14--19, 1962

    1962

  18. [26]

    A survey of lottery ticket hypothesis

    Liu, B., Zhang, Z., He, P., Wang, Z., Xiao, Y., Ye, R., Zhou, Y., Ku, W.-S., and Hui, B. A survey of lottery ticket hypothesis. CoRR, abs/2403.04861, 2024

    2024 arXiv

  19. [27]

    and Uddin, S

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

    2021

  20. [28]

    Proving the lottery ticket hypothesis: Pruning is all you need

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

    2020

  21. [29]

    M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M

    Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. TUD ataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020

    2020

  22. [30]

    The power of the weisfeiler-leman algorithm for machine learning with graphs

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

    2021

  23. [31]

    M., Grohe, M., Fey, M., and Borgwardt, K

    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 0 (333): 0 1--59, 2023

    2023

  24. [32]

    Propagation kernels: efficient graph kernels from propagated information

    Neumann, M., Garnett, R., Bauckhage, C., and Kersting, K. Propagation kernels: efficient graph kernels from propagated information. Machine learning, 102: 0 209--245, 2016

    2016

  25. [33]

    Pérez-Villanueva, 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 Diversity, 19 0 (4): 0 1021--1035, 2015

    2015

  26. [34]

    Multi-precision policy enforced training ( M u PPET ) : A precision-switching strategy for quantised fixed-point training of CNN s

    Rajagopal, A., Vink, D., Venieris, S., and Bouganis, C.-S. Multi-precision policy enforced training ( M u PPET ) : A precision-switching strategy for quantised fixed-point training of CNN s. In International Conference on Machine Learning (ICML), pp.\ 7943--7952, 2020

    2020

  27. [35]

    and Ahmed, N

    Rossi, R. and Ahmed, N. The network data repository with interactive graph analytics and visualization. In Conference on Artificial Intelligence (AAAI), 2015

    2015

  28. [36]

    A., Jin, D., Kim, S., Ahmed, N

    Rossi, R. A., Jin, D., Kim, S., Ahmed, N. K., Koutra, D., and Lee, J. B. On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications. ACM Transactions on Knowledge Discovery from Data, 14 0 (5): 0 1--37, 2020

    2020

  29. [37]

    Brenda, enzyme data and metabolic information

    Schomburg, I., Chang, A., and Schomburg, D. Brenda, enzyme data and metabolic information. Nucleic acids research, 30 0 (1): 0 47--49, 2002

    2002

  30. [38]

    H., Horv\' a th, T., Welke, P., and Wrobel, S

    Schulz, T. H., Horv\' a th, T., Welke, P., and Wrobel, S. A generalized weisfeiler-lehman graph kernel. Machine Learning, 111 0 (7): 0 2601–2629, 2022

    2022

  31. [39]

    J., Mehlhorn, K., and Borgwardt, K

    Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12 0 (9), 2011

    2011

  32. [40]

    Inductive lottery ticket learning for graph neural networks

    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

    2023

  33. [41]

    Disease prediction via graph neural networks

    Sun, Z., Yin, H., Chen, H., Chen, T., Cui, L., and Yang, F. Disease prediction via graph neural networks. IEEE Journal of Biomedical and Health Informatics, 25 0 (3): 0 818--826, 2021

    2021

  34. [42]

    and Perozzi, B

    Tsitsulin, A. and Perozzi, B. The graph lottery ticket hypothesis: Finding sparse, informative graph structure. CoRR, abs/2312.04762, 2023

    2023 arXiv

  35. [43]

    Graph attention networks

    Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018

    2018

  36. [44]

    Wa e ga, P. A. and Rawson, M. Expressive power of temporal message passing. In Conference on Artificial Intelligence (AAAI), volume 39, pp.\ 21000--21008, 2025

    2025

  37. [45]

    Searching lottery tickets in graph neural networks: A dual perspective

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

    2022

  38. [46]

    and Kipf, T

    Welling, M. and Kipf, T. N. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2016

    2016

  39. [47]

    N., Gomes, J., Geniesse, C., Pappu, A

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

    2018

  40. [48]

    Graph neural networks for automated de novo drug design

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

    2021

  41. [49]

    How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019

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

    2019

  42. [50]

    L., Okoshi, Y., Otsuka, H., Kawamura, K., Van Chu, T., and Motomura, M

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

    2024

  43. [51]

    and Vishwanathan, S

    Yanardag, P. and Vishwanathan, S. Deep graph kernels. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp.\ 1365--1374, 2015

    2015

  44. [52]

    Gradient diversity: a key ingredient for scalable distributed learning

    Yin, D., Pananjady, A., Lam, M., Papailiopoulos, D., Ramchandran, K., and Bartlett, P. Gradient diversity: a key ingredient for scalable distributed learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp.\ 1998--2007, 2018

    1998

  45. [53]

    Graph structure learning via lottery hypothesis at scale

    Yuxin, W., Xiannian, H., Jiaqing, X., Zhangyue, Y., Yunhua, Z., Xipeng, Q., and Xuanjing, H. Graph structure learning via lottery hypothesis at scale. In Asian Conference on Machine Learning, pp.\ 1401--1416, 2024

    2024

  46. [54]

    Zaheer, M., Kottur, S., Ravanbakhsh, S., P \' o czos, B., Salakhutdinov, R., and Smola, A. J. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 3391--3401, 2017

    2017

  47. [55]

    Graph lottery ticket automated

    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

    2024

  48. [56]

    Eager pruning: Algorithm and architecture support for fast training of deep neural networks

    Zhang, J., Chen, X., Song, M., and Li, T. Eager pruning: Algorithm and architecture support for fast training of deep neural networks. In ACM/IEEE Annual International Symposium on Computer Architecture (ISCA), pp.\ 292--303, 2019

    2019

  49. [57]

    Why lottery ticket wins? a theoretical perspective of sample complexity on sparse neural networks

    Zhang, S., Wang, M., Liu, S., Chen, P.-Y., and Xiong, J. Why lottery ticket wins? a theoretical perspective of sample complexity on sparse neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 2707--2720, 2021 a

    2021

  50. [58]

    Validating the lottery ticket hypothesis with inertial manifold theory

    Zhang, Z., Jin, J., Zhang, Z., Zhou, Y., Zhao, X., Ren, J., Liu, J., Wu, L., Jin, R., and Dou, D. Validating the lottery ticket hypothesis with inertial manifold theory. In Advances in Neural Information Processing Systems (NeurIPS), pp.\ 30196--30210, 2021 b

    2021

  51. [59]

    1-WL expressiveness is (almost) all you need

    Zopf, M. 1-WL expressiveness is (almost) all you need. In International Joint Conference on Neural Networks, (IJCNN), pp.\ 1--8, 2022

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.