Theory of Graph Neural Networks: Representation and Learning

Explore a comprehensive lecture on Graph Neural Networks (GNNs) that delves into their theoretical foundations, representation capabilities, and learning properties. Gain insights into the approximation and learning characteristics of message passing GNNs and higher-order GNNs, with a focus on function approximation, estimation, generalization, and extrapolation. Discover connections between GNNs and graph isomorphism, equivariant functions, local algorithms, and dynamic programming. Examine the challenges and potential solutions for improving discriminative power, generalization, and extrapolation in GNNs. Analyze the computational structure and algorithmic alignment of these models, and consider open questions in the field. Enhance your understanding of GNNs' applications in machine learning tasks involving nodes, graphs, and point configurations.