Invariant-Based Weight Sharing for Message Passing
For graph learning practitioners, this provides a principled way to incorporate structural information into MPNN weights, improving expressivity and performance without sacrificing scalability.
This work introduces a structure-aware weight sharing principle for MPNNs that indexes weights by graph invariants, enabling systematic reuse across structurally equivalent subgraphs. The proposed ShareGNNs achieve consistent improvements over standard MPNNs on synthetic and real-world tasks, including subgraph counting, with competitive expressivity beyond the 1-WL test.
Message-passing neural networks (MPNNs) are a powerful framework for learning representations of graph-structured domains. However, weights in MPNNs act on features only, limiting their ability to capture structural patterns. We introduce a novel structure-aware weight sharing principle that explicitly incorporates information inherent to the graph structure. Weights are indexed directly by user-chosen graph invariants, i.e., functions preserved under node permutations, enabling systematic reuse across structurally equivalent subgraphs. We present ShareGNNs, which instantiate this principle within a simple encoder-decoder architecture, resulting in an MPNN with learnable adjacency and transformer-like connectivity. We show that their expressivity is at least as strong as the discriminative power of the chosen invariants, providing explicit control over the model complexity. Experiments on synthetic and real-world data, as well as subgraph counting tasks, demonstrate consistent improvements over standard MPNNs, competitive expressivity beyond the 1-WL test, and scalability to large datasets.