Graph-structured data is prevalent across various domains, such as chemo- and bioinformatics, image analysis, and social network analysis. As a result, there has been a surge in the development of machine-learning methods explicitly tailored to graphs. Among these methods, (message-passing) graph neural networks (MPNNs) have emerged as the dominant paradigm. Despite their practical success, MPNNs’ capabilities and limitations are understood to a lesser extent. In this talk, we will overview our recent results connecting MPNNs’ expressive power and generalization abilities, using combinatorial und continuous tools.