Graph Neural Networks Achieve Key-Invariant Expression with Unique Node Identifiers

Researchers are increasingly investigating the limits of graph neural networks (GNNs) when applied to real-world data, and a new study explores how unique node identifiers impact their capabilities. Arie Soeteman from the University of Amsterdam, Michael Benedikt, and Martin Grohe with Balder ten Cate also from the University of Amsterdam, demonstrate that the presence of these identifiers significantly alters what GNNs can effectively compute. This work initiates a focused study of ‘key-invariant’ expressive power , essentially, what structural queries can GNNs answer when each node has a unique label? Understanding this is crucial because it reveals fundamental constraints on GNNs and informs the development of more powerful models for tasks reliant on node-specific information.

This work initiates a focused study of ‘key-invariant’ expressive power, essentially, what structural queries can GNNs answer when each node has a unique label? Understanding this is crucial because it reveals fundamental constraints on GNNs and informs the development of more powerful models for tasks reliant on node-specific information.

GNN Expressivity with Unique Node Identifiers

This work addresses a fundamental question: which isomorphism-invariant properties can GNNs express on graphs augmented with these identifiers? Researchers were motivated by observations in randomised GNNs and the prevalence of unique identifiers in practical applications, such as geometric GNNs and those utilising positional encodings. The study unveils how these identifiers impact the capabilities of GNNs, drawing inspiration from order-invariant definability in finite model theory. Researchers provided answers for various classes of GNNs employing local max- or sum-aggregation functions, establishing a clearer understanding of their limitations and potential.

This approach builds on the established connection between GNNs and logic, specifically modal logics and bounded-variable logics with counting, extending these logical characterisations to accommodate the presence of unique node features. This research establishes a framework for analysing GNNs in scenarios where node features act as unique identifiers, a common occurrence in applications like geometric GNNs where node coordinates serve this purpose. The work opens avenues for assessing the expressiveness of GNNs invariant to bijections on these identifiers, crucial for maintaining desired properties like invariance under geometric transformations. Furthermore, the findings provide a foundation for investigating the expressiveness of GNNs utilising positional encodings, which often generate unique node features to enhance performance.

The team’s contributions are rooted in the observation that while adding random node features can increase a GNN’s ability to approximate functions, it compromises isomorphism invariance. By focusing on key-invariant expressiveness, the study offers a principled way to evaluate GNNs without sacrificing this crucial property. The research also draws parallels to finite model theory, where order-invariant logics have been extensively studied, providing a theoretical lens for understanding the capabilities of GNNs in the presence of unique identifiers and potentially leading to new insights in both fields.

Key-invariant GNN expressivity via aggregation functions

Researchers framed this as a question of determining what node queries these key-invariant GNNs can express. Experiments employed both LocalMax and LocalSum aggregation functions within the GNN architecture, systematically varying the combination functions used, including ReLU-FFNs, continuous functions, semilinear functions, and arbitrary functions. The team meticulously analysed closure properties, assessing invariance under bisimulation and colour refinement to understand the GNNs’ capabilities. Lower and upper bounds were established by comparing expressive power to variants of graded modal logic, order-invariant first-order logic, and first-order logic with counting.

To rigorously evaluate performance, the research developed specific case studies focusing on queries like Qeven, which determines if a node has an even number of neighbours, and QGu, testing isomorphism to a specific graph Gu. The study generated results summarised in Tables 1 and 2, visually depicting the relative key-invariant expressive power of different GNN classes in Figures 2 and 3. This approach enabled the discovery that, unlike unkeyed GNNs where LocalMax networks with ReLU functions are equivalent, key-invariant LocalMax networks exhibit a strict hierarchy based on combination function type. Key-invariant LocalMax GNNs with arbitrary combination functions are subsumed by order-invariant first-order logic, while key-invariant LocalSum GNNs with arbitrary functions achieve completeness, expressing all strongly local node queries. The team highlighted that requiring a specific output policy, positive values for yes-instances and negative for no-instances, limits the expressive gain from keys, whereas relaxing this restriction unlocks increased power.

Key-invariant GNN expressivity and LocalMax hierarchy are tightly

This work establishes a framework for understanding what node queries, questions about a graph focused on a specific node, can be answered by these key-invariant GNNs. Data shows that while all key-oblivious LocalMax GNNs are equivalent to those with ReLU-FFN combination functions, key-invariant versions exhibit increasing expressiveness with more complex functions. Similarly, tests prove that key-invariant LocalSum GNNs benefit from discontinuous functions, enhancing their ability to discern graph properties beyond what continuous functions can achieve. Without this restriction, the inclusion of keys demonstrably increases expressive capacity. Table 1 summarises these findings, alongside collapse and lower bound results. Figures 2 and 3 visually depict the relative key-invariant expressive power of the various GNN classes investigated.

GNN Expressiveness with Unique Node Identifiers is crucial

The work builds upon the established link between GNNs and modal logics, specifically exploring how unique identifiers impact their capabilities. The findings demonstrate that GNNs with sum-aggregation can express graded modal logic and are contained within first-order logic with counting. Importantly, the authors establish limitations of basic GNN architectures, noting that many natural queries remain beyond their expressive reach. They acknowledge that augmenting graphs with random node features, while increasing expressive power, compromises isomorphism invariance, a challenge also present when using generated unique identifiers.

Future research could explore how to achieve greater expressiveness while maintaining invariance properties, particularly in applications like geometric GNNs and those employing positional encodings. The authors highlight the relevance of this research to geometric GNNs, where coordinates serve as unique identifiers, and to recent trends in graph machine learning utilizing positional encodings. Determining the isomorphism-invariant properties expressible by GNNs with unique identifiers provides a lower bound for the expressiveness of these models, even when considering transformations like translations or rotations. Acknowledging a limitation, the study focuses on theoretical expressiveness rather than practical implementation details or computational complexity. Further work might investigate the trade-offs between expressiveness, invariance, and computational efficiency in real-world graph learning scenarios.