Metraipolis › archive › dc_9dd970d2f6d3
A Unifying Relational Perspective on Expressive Lottery Tickets — arXiv:2608.18819
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.18819
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T13:53:27.555Z
- SHA-256 of the archived text
78dce63d7ca07e82d1241f0b8835c901ab24d6f53bbfc75171dcbde34ace03d5- Stable URL of this page
https://metraipolis.com/documento/dc_9dd970d2f6d3
How to cite
A Unifying Relational Perspective on Expressive Lottery Tickets — arXiv:2608.18819 — arXiv (en), https://arxiv.org/abs/2608.18819 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9dd970d2f6d3 (Metraipolis archive dc_9dd970d2f6d3, sha256 78dce63d7ca07e82d1241f0b8835c901ab24d6f53bbfc75171dcbde34ace03d5)
BibTeX
@misc{dc9dd970d2f6d3,
title = {A Unifying Relational Perspective on Expressive Lottery Tickets — arXiv:2608.18819},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.18819},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9dd970d2f6d3; sha256 78dce63d7ca07e82d1241f0b8835c901ab24d6f53bbfc75171dcbde34ace03d5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.18819. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-20 in cs.LG). Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2608.18819 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-18T13:50:58.942Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-20?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).