Theoretical Properties of Graph Neural Networks

Graph Neural Networks (GNNs) have emerged in recent years as a powerful tool to learn tasks across a wide range of graph domains in a data-driven fashion; based on a message passing mechanism, GNNs have gained increasing popularity due to their intuitive formulation, closely linked with the Weisfeiler-Lehman (WL) test for graph isomorphism, to which they have proven equivalent. In this thesis, we provide a broad overview of two essential properties of GNNs by a theoretical point of view, namely, their approximation power and their generalization capabilities. We show that modern GNNs are universal approximators, given that they are made by a sufficient number of layers, which is tightly linked to the stable node coloring of the 1-WL test. GNNs are shown to be universal approximators also on more complex graph domains, like edge-attributed graphs and dynamic graphs. Generalization capabilities of GNNs are investigated by different perspectives. Bounds on the VC dimension of GNNs are provided with respect to the usual hyperparameters and with respect to the number of colors derived from the 1-WL test. GNNs ability to generalize to unseen data is also explored by a neurocognitive point of view, determining whether these models are able to learn the so-called identity effects.