mlsanityData to 14 Oct 2026

A Unifying Relational Perspective on Expressive Lottery Tickets

arXiv 2608.18819 ↗First posted 19 Aug 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 34 of its 59 references that are in the map. First posted on arXiv 19 Aug 2026.

Builds on

34 of 59 references.

References · 34

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,262
  3. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,694
  4. 2017Deep Setscited by 1,421
  5. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  6. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 652
  7. 2020Temporal Graph Networks for Deep Learning on Dynamic Graphscited by 530
  8. 2020Inductive Representation Learning on Temporal Graphscited by 462
  9. 2019Composition-based Multi-Relational Graph Convolutional Networkscited by 396
  10. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 247
  11. 2020Proving the Lottery Ticket Hypothesis: Pruning is All You Needcited by 201
  12. 2023Temporal Graph Benchmark for Machine Learning on Temporal Graphscited by 138
22 more
  1. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  2. 2021A Unified Lottery Ticket Hypothesis for Graph Neural Networkscited by 118
  3. 2020Gradient Flow in Sparse Neural Networks and How Lottery Tickets Wincited by 77
  4. 2023Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunitiescited by 61
  5. 2020Hierarchical Inter-Message Passing for Learning on Molecular Graphscited by 59
  6. 2022Provably expressive temporal graph networkscited by 56
  7. 2022Neighborhood-aware Scalable Temporal Network Representation Learningcited by 54
  8. 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 34
  9. 2023A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphscited by 32
  10. 2022Weisfeiler and Leman Go Relationalcited by 28
  11. 2020Globally Injective ReLU Networkscited by 23
  12. 2023Rethinking Graph Lottery Tickets: Graph Sparsity Matterscited by 23
  13. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  14. 2022Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphscited by 12
  15. 2021Adaptive Precision Training (AdaPT): A dynamic fixed point quantized training approach for DNNscited by 8
  16. 2024Expressive Power of Temporal Message Passingcited by 7
  17. 2022Mitigating Relational Bias on Knowledge Graphscited by 6
  18. 2023The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structurecited by 6
  19. 2025On the Relationship Between Robustness and Expressivity of Graph Neural Networkscited by 3
  20. 2023Multicoated and Folded Graph Neural Networks with Strong Lottery Ticketscited by 2
  21. 2025Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphscited by 2
  22. 2026XIMP: Cross Graph Inter-Message Passing for Molecular Property Predictioncited by 1

Built on by

Not cited yet.