A Unifying Relational Perspective on Expressive Lottery Tickets

• URL: http://arxiv.org/abs/2608.18819v1
• Date: Wed, 19 Aug 2026 11:16:14 GMT
• Title: A Unifying Relational Perspective on Expressive Lottery Tickets
• Abstract summary: We study how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants.<n>We show that common TGNNs and cross-graph message passing schemes admit RGNN reformulations such that they inherit these guarantees.<n>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.
• Score: 3.151556208794165
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning [63.602658976990874]
  Graph neural networks (GNNs) are typically conceptualized as message-passing neural networks.<n>We present a retrieval-augmented view of GNNs: each layer makes predictions by applying anvariant to a node representation together with a permutation-in summary of retrieved graph context.<n>Motivated by this perspective, we propose RTA, a simple aggregation-based framework that replaces structural message passing with label-aware retrieval and propagation.
  arXiv  Detail & Related papers  (2026-08-27T07:25:44Z)
• Gaussian Sheaf Neural Networks [10.93842826346962]
  We propose a principled framework that incorporates inductive biases into graph-based learning.<n>Building on the theory of cellular sheaves, we derive a new Laplacian operator that generalizes the sheaf Laplacian to this setting and preserves its key properties.
  arXiv  Detail & Related papers  (2026-05-20T17:26:32Z)
• Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win [5.523076080195755]
  Lottery ticket hypothesis (LTH) is well-studied for convolutional neural networks but has been validated only empirically for graph neural networks (GNNs)<n>We identify the expressivity of sparseworks, i.e. their ability to distinguish non-isomorphic graphs, as crucial for finding winning tickets that preserve the predictive performance.<n>Our findings establish novel theoretical foundations for both LTH and GNN research, highlighting the importance of maintaining expressivity in sparsely GNNs.
  arXiv  Detail & Related papers  (2025-06-04T13:10:59Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [29.47675861430167]
  We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness.<n>We show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems.<n>Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective.
  arXiv  Detail & Related papers  (2024-10-02T08:01:50Z)
• Non-convolutional Graph Neural Networks [46.79328529882998]
  We design a simple graph learning module entirely free of convolution operators, coined random walk with unifying memory (RUM) neural network. RUM achieves competitive performance, but is also robust, memory-efficient, scalable, and faster than the simplest convolutional GNNs.
  arXiv  Detail & Related papers  (2024-07-31T21:29:26Z)
• Comparative Analysis of Interval Reachability for Robust Implicit and Feedforward Neural Networks [64.23331120621118]
  We use interval reachability analysis to obtain robustness guarantees for implicit neural networks (INNs) INNs are a class of implicit learning models that use implicit equations as layers. We show that our approach performs at least as well as, and generally better than, applying state-of-the-art interval bound propagation methods to INNs.
  arXiv  Detail & Related papers  (2022-04-01T03:31:27Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  Graph Neural Networks (GNNs) are proposed without considering the distribution shifts between training and testing graphs. In such a setting, GNNs tend to exploit subtle statistical correlations existing in the training set for predictions, even though it is a spurious correlation. We propose a general causal representation framework, called StableGNN, to eliminate the impact of spurious correlations.
  arXiv  Detail & Related papers  (2021-11-20T18:57:18Z)
• Implicit vs Unfolded Graph Neural Networks [29.803948965931212]
  We show that implicit and unfolded GNNs can achieve strong node classification accuracy across disparate regimes.<n>While IGNN is substantially more memory-efficient, UGNN models support unique, integrated graph attention mechanisms and propagation rules.
  arXiv  Detail & Related papers  (2021-11-12T07:49:16Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  Graph neural networks (GNNs) are emerging machine learning models on graphs. Permutation-equivariance and proximity-awareness are two important properties highly desirable for GNNs. We show that existing GNNs, mostly based on the message-passing mechanism, cannot simultaneously preserve the two properties. In order to preserve node proximities, we augment the existing GNNs with node representations.
  arXiv  Detail & Related papers  (2020-09-05T16:46:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.