The World of Graph Neural Networks: From the Mystery of Generalization to Foundational Limitations

The tremendous importance of graph structured data due to recommender systems or social networks led to the introduction of graph neural networks (GNNs). After a general introduction to GNNs, we will discuss results about their amazing generalization capabilities. We will study the more specialized question to which extent GNNs are able to generalize to graphs, which describe a similar phenomenon as present in the training data set, as well as the fully general problem. We will present results for both message passing and spectral GNNs. We will finish with a word of caution when training GNNs on classical digital hardware, and present fundamental limitations.