pith. sign in

arxiv: 2605.25750 · v1 · pith:LBXTLGS6new · submitted 2026-05-25 · 💻 cs.LG

Invariant-Based Weight Sharing for Message Passing

Florian Seiffarth This is my paper

Pith reviewed 2026-06-29 22:19 UTC · model grok-4.3

classification 💻 cs.LG
keywords message passing neural networksgraph invariantsweight sharingexpressivitygraph neural networkssubgraph countingShareGNN
0
0 comments X

The pith

Indexing weights by chosen graph invariants ties MPNN expressivity directly to those invariants' discriminative power.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a weight-sharing scheme for message-passing networks in which each weight is selected by a user-specified graph invariant rather than by feature values alone. This produces ShareGNNs whose learned adjacency and connectivity patterns reuse parameters across structurally equivalent subgraphs. The central result is that the resulting networks are at least as expressive as the invariants used to index the weights, so model capacity can be tuned by swapping invariants instead of by adding layers or hidden units. Experiments on synthetic graphs, real-world datasets, and subgraph counting tasks show gains over ordinary MPNNs and reach beyond 1-WL discrimination while remaining scalable.

Core claim

ShareGNNs are message-passing networks whose weights are indexed by graph invariants; their expressivity is at least as strong as the discriminative power of the chosen invariants, supplying explicit control over model complexity through the choice of invariant.

What carries the argument

Invariant-based weight sharing, which indexes each learnable weight by a user-chosen permutation-invariant function on the graph.

If this is right

  • Choosing stronger invariants yields networks that exceed 1-WL discrimination without architectural changes.
  • Parameter reuse across equivalent subgraphs reduces effective model size while preserving or increasing accuracy on graph tasks.
  • The same encoder-decoder structure supports both learnable adjacency and transformer-style connectivity within one framework.
  • Subgraph-counting performance improves because invariants can be chosen to capture the relevant structural patterns directly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach could be applied to other GNN layers whose parameters are currently indexed only by feature dimension.
  • Different invariants could be mixed within one model to create hybrid expressivity levels not achievable by a single WL iteration count.
  • The method supplies a concrete route to parameter-efficient scaling on large graphs by increasing invariant strength rather than width or depth.

Load-bearing premise

Indexing weights by graph invariants yields a well-defined, trainable network whose learned adjacency and connectivity patterns do not create optimization instabilities that erase the claimed expressivity control.

What would settle it

A pair of non-isomorphic graphs that an invariant distinguishes but on which the corresponding ShareGNN fails to produce different outputs after training, or a dataset where the model requires post-training adjustments that remove the expressivity guarantee.

Figures

Figures reproduced from arXiv: 2605.25750 by Florian Seiffarth.

Figure 1
Figure 1. Figure 1: Invariant-based message passing (left) and graph attention (right) for the molecular [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Non-isomorphic graph pairs 𝐺1, 𝐺2 and 𝐺3, 𝐺4 that are indistinguishable by the 1-WL test, and therefore by standard message-passing GNNs, but distinguishable by ShareGNN. Node colors indicate 1-WL labels. Arrows mark messages in ShareGNN that enable distinguishing the graphs. Multi-Heads While encoder and decoder operate with a single set of invariants, ShareGNNs naturally extend to a multi-head architectu… view at source ↗
Figure 3
Figure 3. Figure 3: Ablation Study. (3a) ShareGNN performance for different maximum message-passing [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Invariant-based message passing (ShareGNN encoder layer) for a molecule from DHFR. [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Update (𝑣𝑖) in the encoder (left) and aggregation of the final node embeddings in the decoder (right) 𝑎 ∈ ℕ0 such that 𝐴 ∶= ∑𝑣∈𝑉 𝟏𝑙(𝑣)=𝑎 ≠ ∑𝑣∈𝑉′ 𝟏𝑙(𝑣)=𝑎 =∶ 𝐴 ′ with 𝟏 being the indicator function. For example, we can define 𝑙 to be the (𝑘 + 1)-Weisfeiler-Leman labels with 𝑘 being the maximum of the treewidths of 𝐺 and 𝐺 ′ [Dvor´ak, 2010]. Let ShareGNN consist of only a decoder layer based on the labeling f… view at source ↗
Figure 6
Figure 6. Figure 6: Example graphs taken from the RingTransfer1 dataset. decoder layers to capture different invariants in one layer. More precisely, for the encoder layer and decoder layer we use 5 heads each. The graph invariants respectively labeling functions used in the heads are simple cycles of length 3, 4, 5, 6 and the degree of the nodes. In case of the encoder for the cycles we use only distance 0 information, corre… view at source ↗
Figure 7
Figure 7. Figure 7: Example graphs taken from the RingTransfer2 dataset. Graph Label: 0 Graph Label: 1 Graph Label: 2 Graph Label: 3 1 [PITH_FULL_IMAGE:figures/full_fig_p025_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Example graphs taken from the RingTransfer3 dataset. molecules, and 22 and 18 options for the social datasets, respectively. Thus, in total we test 100 different hyperparameter configurations for the molecules and 396 for the social datasets. We did no hyperparameter search on the valid triples  as we used a fixed 𝐷 to determine the maximum distance between node pairs for which we compute shared weights. … view at source ↗
Figure 9
Figure 9. Figure 9: Example graphs taken from the CLS dataset. Graph Label: 0 Graph Label: 1 Graph Label: 2 Graph Label: 3 1 [PITH_FULL_IMAGE:figures/full_fig_p026_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Example graphs from the Snowflakes dataset. The brown node in the circle is labeled by 1 and the other nodes by 0. The label of the graph is determined by the subgraph attached to the brown node. NCI1, NCI109 and Mutagenicity the training time is less than 1 second per epoch. In general, runtime is not a problem for our approach as the preprocessing time is negligible and the training time is reasonable, … view at source ↗
Figure 11
Figure 11. Figure 11: Graphs 𝑀0, 𝑀1, 𝑀2 and 𝑀3 [Naik et al., 2024] that are not distinguishable by the 1-WL test. distance 8. For RingTransfer3 we use two encoder layers with the original node labels and define shared weights only for node pairs with distance 8 in the first layer and for node pairs with distance 4 in the second layer. For CSL we use node labels induced by patterns consisting of simple cycles up to length 10 an… view at source ↗
Figure 14
Figure 14. Figure 14: Number of occurrences of the message-passing weights of the encoder layer summed [PITH_FULL_IMAGE:figures/full_fig_p037_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Values of the trained message-passing weights of the respective datasets. The weights [PITH_FULL_IMAGE:figures/full_fig_p038_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: See Figure 15, but this time the model is trained only with message-passing weights [PITH_FULL_IMAGE:figures/full_fig_p039_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: ShareGNN performance for different maximum message-passing distances [PITH_FULL_IMAGE:figures/full_fig_p039_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: ShareGNN performance (mean accuracy and standard deviation) for different number of [PITH_FULL_IMAGE:figures/full_fig_p040_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: ShareGNN performance (mean accuracy and standard deviation) for different number of [PITH_FULL_IMAGE:figures/full_fig_p040_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: Visualization of the weights for the respective dataset. The first column of each subfigure [PITH_FULL_IMAGE:figures/full_fig_p041_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: Visualization of the weights for the respective datasets. The first column of each subfigure [PITH_FULL_IMAGE:figures/full_fig_p041_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: Molecular graphs of ethylene (left) and cyclopropenylidene (right). The numbers denote [PITH_FULL_IMAGE:figures/full_fig_p042_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: Computational graphs of a simple ShareGNN with one encoder layer for the molecular [PITH_FULL_IMAGE:figures/full_fig_p042_23.png] view at source ↗
Figure 24
Figure 24. Figure 24: Representation of a 5x5 partial image as a grid graph with diagonal edges. The left [PITH_FULL_IMAGE:figures/full_fig_p042_24.png] view at source ↗
Figure 25
Figure 25. Figure 25: Representation of a sample text as labeled path graph. First, the text is parsed through [PITH_FULL_IMAGE:figures/full_fig_p043_25.png] view at source ↗
Figure 26
Figure 26. Figure 26: Encoder Layer: Message passing in the labeled path graph generated by the GPT-2 [PITH_FULL_IMAGE:figures/full_fig_p043_26.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper introduces ShareGNNs, which apply a novel invariant-based weight sharing principle to MPNNs. Weights are indexed by user-chosen graph invariants (permutation-invariant functions), enabling reuse across structurally equivalent subgraphs. The architecture is an encoder-decoder MPNN with learnable adjacency and transformer-like connectivity. The central theoretical claim is that ShareGNN expressivity is at least as strong as the discriminative power of the selected invariants, giving explicit control over complexity. Experiments on synthetic data, real-world graphs, and subgraph counting tasks report consistent gains over standard MPNNs and expressivity beyond 1-WL.

Significance. If the expressivity theorem holds and the weight-indexing construction yields a well-defined, trainable model without hidden instabilities, the work supplies a principled mechanism for modulating GNN expressivity via invariant choice. This is a potentially useful addition to the literature on structure-aware GNNs, especially if accompanied by reproducible code or machine-checked proofs (none mentioned in the abstract).

minor comments (1)
  1. The abstract states expressivity results and experimental gains but supplies neither the derivation, data splits, nor statistical details; the full manuscript must be examined to confirm these claims.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of our manuscript on ShareGNNs. We appreciate the acknowledgment of the potential value of invariant-based weight sharing for controlling MPNN expressivity. Below we respond to the points raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The abstract states a claim that ShareGNN expressivity is at least as strong as the discriminative power of chosen invariants but supplies no equations, derivations, or proofs. No self-citations, fitted parameters renamed as predictions, or self-definitional constructions are visible. Without load-bearing steps that reduce to inputs by construction, the derivation (if present in the full text) cannot be shown to be circular from the supplied material; the result is treated as self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are stated in the provided text.

pith-pipeline@v0.9.1-grok · 5684 in / 1036 out tokens · 26544 ms · 2026-06-29T22:19:28.677638+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    URL https://doi.org/10.48550/arXiv.2403.07849

    doi: 10.48550/ARXIV.2403.07849. URL https://doi.org/10.48550/arXiv.2403.07849. Raffaele Paolino, Sohir Maskey, Pascal Welke, and Gitta Kutyniok. Weisfeiler and leman go loopy: A new hierarchy for graph representational learning. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Adva...

    work page doi:10.48550/arxiv.2403.07849 2024

  2. [2]

    Graph Attention Networks

    doi: 10.24963/IJCAI.2021/214. URLhttps://doi.org/10.24963/ijcai.2021/214. Quang Truong and Peter Chin. Weisfeiler and lehman go paths: Learning topological features via path complexes. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on In...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.24963/ijcai.2021/214 2021

  3. [3]

    Each dataset is split into 10 predefined train/test folds

    we also adopt the widely used standard protocol. Each dataset is split into 10 predefined train/test folds. Models are trained on the training folds with a grid of hyperparameter settings, and the configuration with the best average test accuracy across folds is used for final reporting (Table 12). ResultsIn the standard evaluation (Table 12), the perform...

    work page arXiv 2024