# How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 54 references that are in the map.
- First posted on arXiv 29 Jan 2026.

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

- [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)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [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)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [Coloring graph neural networks for node disambiguation](https://mlsanity.com/paper/1912.06058/) (2019)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Decidability of Graph Neural Networks via Logical Characterizations](https://mlsanity.com/paper/2404.18151/) (2024)
- [Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats](https://mlsanity.com/paper/2405.14606/) (2024)
- [The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic](https://mlsanity.com/paper/2505.08021/) (2025)
- [Logical Characterizations of GNNs with Mean Aggregation](https://mlsanity.com/paper/2507.18145/) (2025)
- [Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization](https://mlsanity.com/paper/2506.13911/) (2025)
- [Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2](https://mlsanity.com/paper/2508.06091/) (2025)
- [A Logical View of GNN-Style Computation and the Role of Activation Functions](https://mlsanity.com/paper/2512.19332/) (2025)

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

- [Towards Understanding the Expressive Power of GNNs with Global Readout](https://mlsanity.com/paper/2604.22870/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data, based on local aggregation over neighbors. GNNs have close connections to logic. In particular, their expressive power is linked to that of modal logics and bounded-variable logics with counting. In many practical scenarios, graphs processed by GNNs have node features that act as unique identifiers. In this work, we study how such identifiers affect the expressive power of GNNs. We initiate a study of the key-invariant expressive power of GNNs, inspired by the notion of order-invariant definability in finite model theory: which node queries that depend only on the underlying graph structure can GNNs express on graphs with unique node identifiers? We provide answers for various classes of GNNs with local max- or sum-aggregation.