Search papers, labs, and topics across Lattice.
This paper investigates how parameter sparsity influences the expressivity of relational and temporal graph neural networks (GNNs) through the Strong Expressive Lottery Ticket Hypothesis (SELTH). It establishes that sufficiently parameterized relational GNNs can contain sparse subnetworks that retain 1-Weisfeiler-Leman expressivity, providing a probabilistic framework for understanding the likelihood of such subnetworks arising from random pruning. The findings are validated through experiments that connect expressivity to optimization behavior and prediction quality across various benchmarks, highlighting the practical implications for model efficiency in GNNs.
Sparse subnetworks in relational GNNs can maintain expressivity, challenging the notion that larger models are always necessary for performance.
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.
