Source-linked AI summary
A Survey on The Expressive Power of Graph Neural Networks
Ryoma Sato
TL;DR
GNNs have strong empirical performance but face theoretical limits in distinguishing graphs and solving combinatorial problems. This survey synthesizes their expressive power, connects message-passing GNNs with WL algorithms and distributed algorithms, and reviews more powerful variants. It concludes that higher-order and randomized extensions address some limitations, while practical and complexity constraints remain.
Problem
Although GNNs are empirically successful, theoretical results show limits in graph distinction and in the combinatorial problems they can solve.
Method
The survey analyzes GNN expressive power through connections with WL algorithms and distributed local algorithms, and reviews higher-order and randomized variants.
Results
The survey establishes that message-passing GNNs are at most as powerful as 1-WL, while GINs, higher-order GNNs, and random features provide stronger expressivity or approximation capabilities under stated conditions.
Takeaways & Limitations
The survey organizes GNN, WL, and distributed-algorithm relationships as the XS correspondence and identifies random features as a way to improve approximation ratios drastically.
Takeaways & Limitations
Higher-order GNN universality results often assume fixed or bounded graph size, and their parameter counts can be impractical because Bell numbers grow super-exponentially.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) are effective machine learning models for various graph learning problems. Despite their empirical successes, the theoretical limitations of GNNs have been revealed recently. Consequently, many GNN models have been proposed to overcome these limitations. In this survey, we provide a comprehensive overview of the expressive power of GNNs and provably powerful variants of GNNs.
1 Introduction
GNNs are effective across graph-learning applications, but theoretical results expose limits on what they can distinguish and compute. This survey focuses on those theoretical properties, standard message-passing models, and the functions and graph structures within their expressive scope.
- Motivation: GNNs support graph-related tasks in cheminformatics, recommender systems, question answering, and combinatorial problems.The survey situates GNNs across several application areas before turning to their theoretical analysis.
- Motivation: Theoretical results show that some graph pairs cannot be distinguished by GNNs, limiting correct classification when their labels differ.The limitation holds for any parameters on such graph pairs and contrasts with multilayer perceptrons’ universal approximation power.
- Scope: The survey examines node and graph classification functions because GNNs cannot model all functions on graphs.Its problem settings take a graph and node as input for node classification or a graph as input for graph classification.
- Standard GNNs: The survey reviews message-passing GNNs, including GraphSAGE-mean, GCNs, and GATs, where nodes aggregate neighboring messages to update embeddings.When node features are unavailable, one-hot degree vectors provide the initial embeddings; one-layer models can therefore assign identical embeddings to some nodes.
2 Graphs That GNNs Cannot Distinguish
Elementary examples show that message-passing GNNs can fail to distinguish non-isomorphic graphs, including regular and non-regular molecular graphs. The shared final embeddings arise because neighborhood messages remain identical, making different labels impossible to separate.
- Regular graphs: Message-passing GNNs cannot distinguish k-regular graphs with the same size and identical node features.Decaprismane and dodecahedrane are presented as 3-regular molecular examples with 20 nodes.
- Regular graphs: Non-isomorphic regular graphs may receive identical final embeddings because every node produces identical messages in both graphs.The example graphs differ structurally, including in triangle presence, yet message passing yields the same node representations.
- Non-regular graphs: GNNs also fail on many non-regular, non-isomorphic graph pairs, including examples with added leaves, additional node features, and molecular structures.The survey identifies Decalin and bicyclopentyl as real-world molecular examples that remain indistinguishable.
- Characterization: These examples motivate characterizing indistinguishable graphs through the Weisfeiler–Lehman algorithm.The survey next introduces results connecting GNN distinguishability to WL-based graph comparisons.
3 Connection with The WL Algorithm
The survey connects message passing GNNs to the 1-WL algorithm and organizes more expressive architectures through higher-order WL variants and invariant/equivariant constructions. These correspondences characterize both distinguishability guarantees and practical limitations such as memory, parameter, and graph-size requirements.
- Higher-order WL variants: For every k ≥2, (k + 1)-WL is strictly more powerful than k-WL, and 3-WL can detect triangles that 1-WL cannot.The hierarchy provides progressively stronger graph-distinguishing procedures, although higher-order variants can still fail on some non-isomorphic graphs.
- Connection between GNNs and 1-WL: GINs match 1-WL by using injective aggregation and update functions, with guarantees under bounded node degrees and finite node-feature support.A fixed parameter set can distinguish every graph pair separated by 1-WL within the stated graph class.
- Higher-order GNNs: k-GNNs operate on k-node subsets and are as powerful as set k-WL, but maintaining O(n^k) embeddings creates a substantial memory cost.The set k-WL algorithm is strictly weaker than k-WL; for example, set 3-WL cannot distinguish a pair that 3-WL separates using 4-cycles.
- Invariant and equivariant GNNs: Higher-order invariant and equivariant GNNs use orthogonal bases for invariant and equivariant linear transformations, supporting permutation-respecting graph representations.The survey also describes higher-order GNN universality results, while noting fixed-size and parameter-growth constraints.
4 Connection with Combinatorial Problems
The survey connects GNN expressive power to distributed local algorithms and shows that port numbering, consistent port numbering, and random features strengthen what GNNs can compute.
- 4.1 Distributed Local Algorithms: Distributed local algorithms run for constant time, with identical programs making decisions after constant-round communication with neighboring nodes.The survey uses this framework to analyze graph problems such as minimum dominating set and vertex cover.
- 4.2 Connection with Local Algorithms: VVC-GNNs use port numbering to send different messages to different neighbors, whereas MB-GNNs send the same message to every neighbor.The resulting hierarchy is VVC-GNNs strictly more expressive than MB-GNNs, which are strictly more expressive than SB-GNNs.
- 4.2 Connection with Local Algorithms: Theorem 13 establishes an exact correspondence between MB-, SB-, and VVC-GNNs and their respective distributed local-algorithm models.Each algorithm can be represented by a corresponding GNN, and each such GNN can be represented by an algorithm.
- 4.2 Connection with Local Algorithms: Fixed parameters of CPNGNNs can approximate any VVC-GNN on bounded-degree graphs with finite node-feature support.This lets CPNGNNs inherit the computational problem boundaries studied for the VVC(1) model.
- 4.2 Connection with Local Algorithms: CPGNNs achieve tight approximation boundaries: ∆+1 for minimum dominating set, 2 for minimum vertex cover, and no constant-factor approximation for maximum matching.Under the unique games conjecture, the factor-2 vertex-cover guarantee is optimal in approximation ratio.
- 4.2 Connection with Local Algorithms: Adding weak 2-coloring to degree features enables better approximation results for minimum dominating set and maximum matching.The survey describes weak 2-coloring as a two-color assignment where every node has a neighbor of the other color.
- 4.3 Random Features Strengthen GNNs: Random-feature GINs distinguish wider classes of graphs, including node–triangle incidence, while maintaining n embeddings and linear input-size runtime.They can generalize to unseen graphs despite drawing different random features during testing and can handle graphs larger than those used for training.
5 XS Correspondence
The XS correspondence links GNNs with the WL algorithm and distributed local algorithms. These links allow known results from logic, games, linear programming, and distributed computation to inform GNN design and expressive-power analysis.
- 5 XS Correspondence: The XS correspondence summarizes concrete relationships among GNNs, the WL algorithm, and distributed local algorithms.The survey presents these relationships as a framework for transferring theoretical results across the three areas.
- 5 XS Correspondence: Distributed-local-algorithm round bounds and WL-round bounds can guide the choice of GNN layers.The survey notes that results on random-graph recognition justify two-layer GNNs, while distributed 2-approximation bounds also inform depth selection.
- 5 XS Correspondence: The k-WL algorithm connects GNN analysis to first-order logic with counting quantifiers, pebbling games, linear programming, and Sherali–Adams relaxations.These connections provide additional theoretical tools for understanding graph indistinguishability and expressive power.
- 5 XS Correspondence: The VVC(1) model recognizes graded multimodal logic on corresponding Kripke models, and graded multimodal logic can simulate every VVC(1) algorithm.Distributed local algorithms can also be converted to constant-time algorithms.
- 5 XS Correspondence: The WL–first-order-logic connection has been used to construct more powerful GNNs.The survey identifies this as an example of how the XS correspondence supports new GNN designs.
6 Conclusion
The survey synthesizes GNN expressive power through connections to WL algorithms and distributed algorithms, including limitations and improvements from random node features.
- Message passing GNNs are at most as powerful as the one-dimensional WL algorithm.
- The survey explains how GNNs can be generalized to the k-dimensional WL algorithm.
- Connections with distributed algorithms characterize limitations through approximation ratios for combinatorial algorithms computable by GNNs.
- Adding random features to each node improves approximation ratios drastically.
- The survey summarizes relationships among GNNs, the WL algorithm, and distributed local algorithms as the XS correspondence.