Research on the Expressive Power of Graph Neural Networks: Current Status, Issues, and Prospects

In recent years, graph neural networks (GNNs) have been widely applied across various fields, and research into their expressive power has been continuously advancing. This article provides a comprehensive review of this body of research on expressive power and identifies several systematically overlooked issues, including: a lack of comprehensive characterization of GNN expressive power from a purely structural perspective; preprocessing costs that exceed those of the tasks used to demonstrate the model’s expressive power; and insufficient attention to node features. This article suggests that a potential solution to these problems could be the design of a computational model capable of effectively characterizing GNN behavior. For instance, an analysis framework based on the resource-constrained CONGEST model could be used to study the expressive power of GNNs.