Abstract: 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.