Towards Invariance to Node Identifiers in Graph Neural Networks
cs.LG
Submitted: 2025-02-19
Updated: 2026-10-31
Comments: arXiv admin note: text overlap with arXiv:2411.02271
Code: https://github.com/mayabechlerspeicher/ICON
License: http://creativecommons.org/licenses/by/4.0/
The gist: Message-Passing Graph Neural Networks (GNNs) are known to have limited expressive power, due to their message passing structure.
Terminology
Abstract
Message-Passing Graph Neural Networks (GNNs) are known to have limited expressive power, due to their message passing structure. One mechanism for circumventing this limitation is to add unique node identifiers (IDs), which break the symmetries that underlie the expressivity limitation. In this work, we highlight a key limitation of the ID framework, and propose an approach for addressing it. We begin by observing that the final output of the GNN should clearly not depend on the specific IDs used. We then show that in practice this does not hold, and thus the learned network does not possess this desired structural property. Such invariance to node IDs may be enforced in several ways, and we discuss their theoretical properties. We then propose a novel regularization method that effectively enforces ID invariance to the network. Extensive evaluations on both real-world and synthetic tasks demonstrate that our approach significantly improves ID invariance and, in turn, often boosts generalization performance.
Sources
- The Surprising Power of Graph Neural Networks with Random Node Initialization
- Learning Invariances in Neural Networks
- Can Graph Neural Networks Count Substructures?
- A Generalization of Transformer Networks to Graphs
- Generalization and Representational Limits of Graph Neural Networks
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- What graph neural networks cannot learn: depth vs width
- DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks
- Random Features Strengthen Graph Neural Networks
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis