We are excited to share that the paper A Unifying Relational Perspective on Expressive Lottery Tickets by Lorenz Kummer, Samir Moustafa, Anatol Ehrlich, Franka Bause, Marco Nennstiel, Przemysław Andrzej Wałęga, and Nils M. Kriege has been accepted as a Spotlight at ICML 2026 in Seoul, South Korea!

In this work, we study how parameter sparsity affects the expressivity of relational and temporal graph neural networks. We introduce Relational SELTH (RSELTH), extending the Strong Expressive Lottery Ticket Hypothesis from static GNNs to multi-relational and temporal settings.

Our main result shows that sufficiently wide RGNNs contain sparse subnetworks that preserve 1-RWL expressivity, and we derive an explicit lower bound on the probability that random pruning finds such an expressive subnetwork. We also show how the theory extends to TGNNs and cross-graph message passing architectures, and analyze how pre-training expressivity relates to optimization and predictive performance.