On the expressive power of graph neural networks: beyond the Weisfeiler-Leman test

Graphs are pervasive in many applications, hence the quest for models that can learn effective representations of them. Graph Neural Networks (GNNs) have emerged among other architectures for graph processing, and the study of their theoretical properties has recently experienced a rapid rise. A special focus is dedicated to their expressive power, which consists in the ability of GNNs to differentiate nonisomorphic graphs and to approximate functions on graphs. These properties are strictly related to classification/regression tasks where distinguishing between different inputs is crucial for the final performance of the model. In this thesis, we address two main challenges: the lack of expressiveness results for GNNs on arbitrary graph types and the inherently limited expressive power of standard GNNs, which is upper bounded by the Weisfeiler-Leman (1-WL) test. For example, GNNs cannot count any substructure different from star graphs or even distinguish small non-isomorphic graphs. The fields that can benefit from a deeper understanding of the limitations of GNNs are countless, including biology, physics, and social network analysis. In such application domains, the types of graphs involved are varied: for example, data can find natural representations via directed or undirected, homogeneous or heterogeneous, static or dynamic graphs, and even via multigraphs and hypergraphs. However, foundational studies regarding the mentioned graph types are lacking. We aim to fill the gap by providing a comprehensive expressiveness investigation on GNNs for arbitrary graph types. In particular, we devise appropriate extensions of 1-WL and k-WL, identifying relations among them within an algebraic lattice framework. Then, we prove a universal approximation theorem for GNNs across all the aforementioned domains. In particular, the study extends to discrete dynamic graphs, widely used in practice, which require a peculiar analysis approach, due to the difference between dynamic architectures and static ones. We further propose a new, more expressive algorithm, Path-WL, modifying the aggregation mechanism of GNNs, from the topological neighborhood to a path-based one, enhanced with geodesic distance information. The corresponding model, Pain (PAth Isomorphism Network), is strictly more expressive than GNNs. Additionally, compared to other architectures known to be more powerful than GNN, we demonstrate that PAIN is not bounded by any of them. We characterize graph classes that can be distinguished by Path-WL and demonstrate the ability of Path-WL to count cycles of arbitrary length. This thesis aims to take a step forward in our understanding of GNN capabilities and proposes new strategies to overcome their limitations.