  Machine learning on graphs, especially using graph neural networks (GNNs),
has seen a surge in interest due to the wide availability of graph data across
a broad spectrum of disciplines, from life to social and engineering sciences.
Despite their practical success, our theoretical understanding of the
properties of GNNs remains highly incomplete. Recent theoretical advancements
primarily focus on elucidating the coarse-grained expressive power of GNNs,
predominantly employing combinatorial techniques. However, these studies do not
perfectly align with practice, particularly in understanding the generalization
behavior of GNNs when trained with stochastic first-order optimization
techniques. In this position paper, we argue that the graph machine learning
community needs to shift its attention to developing a balanced theory of graph
machine learning, focusing on a more thorough understanding of the interplay of
expressive power, generalization, and optimization.
