How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
This work addresses a foundational theoretical problem in machine learning for graph-structured data, with implications for understanding GNN limitations and design.
The paper investigates how unique node identifiers affect the expressive power of graph neural networks (GNNs) in processing graph-structured data, establishing theoretical bounds on which structural queries GNNs can express with identifiers.
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.