Invariant-Based Weight Sharing for Message Passing

• URL: http://arxiv.org/abs/2605.25750v1
• Date: Mon, 25 May 2026 12:02:31 GMT
• Title: Invariant-Based Weight Sharing for Message Passing
• Abstract summary: Message-passing neural networks (MPNNs) are a powerful framework for learning representations of graph-structured domains.<n>We introduce a novel structure-aware weight sharing principle that explicitly incorporates information inherent to the graph structure.<n>We present ShareGNNs, which instantiate this principle within a simple encoder-decoder architecture, resulting in an MPNN with learnable adjacency and transformer-like connectivity.
• Score: 0.2538209532048866
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

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)
• Plain Transformers are Surprisingly Powerful Link Predictors [57.01966734467712]
  Link prediction is a core challenge in graph machine learning, demanding models that capture rich and complex topological dependencies.<n>While Graph Neural Networks (GNNs) are the standard solution, state-of-the-art pipelines often rely on explicit structurals or memory-intensive node embeddings.<n>We present PENCIL, an encoder-only plain Transformer that replaces hand-crafted priors with attention over sampled local subgraphs.
  arXiv  Detail & Related papers  (2026-02-02T02:45:52Z)
• Parameter-Free Structural-Diversity Message Passing for Graph Neural Networks [8.462209415744098]
  Graph Neural Networks (GNNs) have shown remarkable performance in structured data modeling tasks such as node classification.<n>This paper proposes a parameter-free graph neural network framework based on structural diversity.<n>The framework is inspired by structural diversity theory and designs a unified structural-diversity message passing mechanism.
  arXiv  Detail & Related papers  (2025-08-27T13:42:45Z)
• Learning Efficient Positional Encodings with Graph Neural Networks [109.8653020407373]
  We introduce PEARL, a novel framework of learnable PEs for graphs.<n>PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power.<n>Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power.
  arXiv  Detail & Related papers  (2025-02-03T07:28:53Z)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• Learning Invariant Representations of Graph Neural Networks via Cluster Generalization [58.68231635082891]
  Graph neural networks (GNNs) have become increasingly popular in modeling graph-structured data. In this paper, we experimentally find that the performance of GNNs drops significantly when the structure shift happens. We propose the Cluster Information Transfer (CIT) mechanism, which can learn invariant representations for GNNs.
  arXiv  Detail & Related papers  (2024-03-06T10:36:56Z)
• DGNN: Decoupled Graph Neural Networks with Structural Consistency between Attribute and Graph Embedding Representations [62.04558318166396]
  Graph neural networks (GNNs) demonstrate a robust capability for representation learning on graphs with complex structures. A novel GNNs framework, dubbed Decoupled Graph Neural Networks (DGNN), is introduced to obtain a more comprehensive embedding representation of nodes. Experimental results conducted on several graph benchmark datasets verify DGNN's superiority in node classification task.
  arXiv  Detail & Related papers  (2024-01-28T06:43:13Z)
• Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks [0.27195102129094995]
  We use a random graph generator to investigate how the graph size and structural properties affect the predictive performance of GNNs. We present specific evidence that the average node degree is a key feature in determining whether GNNs can generalize to unseen graphs. We propose a multi- module GNN framework that allows the network to adapt flexibly to new graphs by generalizing a single canonical nonlinear transformation over aggregated inputs.
  arXiv  Detail & Related papers  (2022-09-14T12:13:59Z)
• Equivariant Subgraph Aggregation Networks [23.26140936226352]
  This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. While two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. We develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism, and prove lower bounds on the expressiveness of ESAN. We provide theoretical results that describe how design choices such as the subgraph selection policy and equivariant neural architecture affect our architecture's expressive power.
  arXiv  Detail & Related papers  (2021-10-06T16:45:07Z)

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.