How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915761252990976 |
|---|---|
| author | Soeteman, Arie Benedikt, Michael Grohe, Martin Cate, Balder ten |
| author_facet | Soeteman, Arie Benedikt, Michael Grohe, Martin Cate, Balder ten |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21882 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How Expressive Are Graph Neural Networks in the Presence of Node Identifiers? Soeteman, Arie Benedikt, Michael Grohe, Martin Cate, Balder ten Logic in Computer Science Machine Learning I.2.6, F.4.1 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. |
| title | How Expressive Are Graph Neural Networks in the Presence of Node Identifiers? |
| topic | Logic in Computer Science Machine Learning I.2.6, F.4.1 |
| url | https://arxiv.org/abs/2601.21882 |