Future Directions in Foundations of Graph Machine Learning
Christopher Morris Nadav Dym Haggai Maron İsmail İlkan Ceylan Fabrizio Frasca Ron Levie Derek Lim Michael Bronstein Martin Grohe Stefanie Jegelka
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 more balanced theory of
graph machine learning, focusing on a more thorough understanding of the
interplay of expressive power, generalization, and optimization.