Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
This provides theoretical foundations for both lottery ticket hypothesis and GNN research, with potential applications in domains like drug discovery.
The paper tackles the lack of theoretical understanding of the lottery ticket hypothesis in graph neural networks (GNNs) by identifying graph expressivity as key for finding winning tickets, proving conditions where sparse subnetworks match full network expressivity and showing this can accelerate convergence and improve generalization.
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.