How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 20 of its 54 references that are in the map. First posted on arXiv 29 Jan 2026.
Builds on
20 of 54 references.
References · 20
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
- 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
- 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 273
- 2021Identity-aware Graph Neural Networkscited by 197
- 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
- 2019On the Limitations of Representing Functions on Setscited by 89
- 2021Universal Approximation of Functions on Setscited by 62
- 2019Coloring graph neural networks for node disambiguationcited by 49
- 2023Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theoremcited by 33
- 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
8 more
- 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
- 2024Decidability of Graph Neural Networks via Logical Characterizationscited by 13
- 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
- 2025Logical Characterizations of GNNs with Mean Aggregationcited by 6
- 2025The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logiccited by 5
- 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
- 2025Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2cited by 3
- 2025A Logical View of GNN-Style Computation and the Role of Activation Functionscited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.