# Towards Invariance to Node Identifiers in Graph Neural Networks

arXiv: https://arxiv.org/abs/2502.13660 · HTML: https://mlsanity.com/paper/2502.13660/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 33 references that are in the map.
- First posted on arXiv 19 Feb 2025.

## Builds on (most cited first, 25 of 25)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Spatial Transformer Networks](https://mlsanity.com/paper/1506.02025/) (2015)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [TI-POOLING: transformation-invariant pooling for feature learning in Convolutional Neural Networks](https://mlsanity.com/paper/1604.06318/) (2016)
- [Learning Invariances in Neural Networks](https://mlsanity.com/paper/2010.11882/) (2020)
- [Graph Positional and Structural Encoder](https://mlsanity.com/paper/2307.07107/) (2023)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Graph Neural Networks Use Graphs When They Shouldn't](https://mlsanity.com/paper/2309.04332/) (2023)
- [Graph Invariant Learning with Subgraph Co-mixup for Out-Of-Distribution Generalization](https://mlsanity.com/paper/2312.10988/) (2023)
- [Learning Invariant Representations of Graph Neural Networks via Cluster Generalization](https://mlsanity.com/paper/2403.03599/) (2024)

## Built on by (most cited first, 4 of 4)

- [Future Link Prediction Without Memory or Aggregation](https://mlsanity.com/paper/2505.19408/) (2025)
- [Principled Latent Diffusion for Graphs via Laplacian Autoencoders](https://mlsanity.com/paper/2601.13780/) (2026)
- [Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum](https://mlsanity.com/paper/2506.05530/) (2025)
- [Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices](https://mlsanity.com/paper/2509.21000/) (2025)

## Abstract (arXiv)

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.