Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916778509074432 |
|---|---|
| author | Kummer, Lorenz Moustafa, Samir Ehrlich, Anatol Bause, Franka Suess, Nikolaus Gansterer, Wilfried N. Kriege, Nils M. |
| author_facet | Kummer, Lorenz Moustafa, Samir Ehrlich, Anatol Bause, Franka Suess, Nikolaus Gansterer, Wilfried N. Kriege, Nils M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03919 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win Kummer, Lorenz Moustafa, Samir Ehrlich, Anatol Bause, Franka Suess, Nikolaus Gansterer, Wilfried N. Kriege, Nils M. Machine Learning 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. |
| title | Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2506.03919 |