The expressivity and explainability of graph neural networks

Information stored as unary and binary facts is often referred to as a knowledge graph (KG). KGs are used in many applications, and different methods for learning on them have been proposed. Among these approaches, graph neural networks (GNNs) are effective and widely-used, due to their strong structural inductive biases. Message Passing Neural Networks (MPNNs) are a powerful variety of GNNs, of which Graph Convolutional Networks (GCNs) are a common instantiation. However, there are many open questions pertaining to the expressivity of GNNs: i.e., which functions GNNs are able to represent. A prominent subset of methods for analysing GNN expressivity is to compare them to formal logic. Furthermore, GNNs are black boxes that do not readily provide explanations for their predictions. Explainability and interpretability are crucial for models that operate in high-stakes domains. Thus, various methods seek to provide explanations for GNN predictions, including explanations based on logical rules. However, these rules are often not faithful to the predictions of the model, and there is increasing interest in logical explanations that faithfully characterize the predictions of GNNs. Such explanations have been shown to be attainable by restricting the weights of GCN models to be non-negative: these GCNs are called “monotonic”. In this thesis, I consider the expressivity and explainability of different MPNNs. First, I define a new class of graph functions that allow for symmetry-breaking and propose extensions to MPNNs to learn such functions. Next, I consider monotonic GCNs used with scoring functions for predicting binary facts, providing an upperbound on their logical expressivity and recovering sound rules for predictions. I also relax the constraint of non-negative weights for GCNs with sum aggregation, showing that, without adaptions to their training regime, they provably learn no sound rules in practice. Finally, I also consider monotonic GCNs with mean aggregation, proving the limited class of simple monotonic rules that can be sound for them and providing a rule language for sound explanations. My experiments validate my theoretical results, showing that my novel MPNNs can learn symmetrybreaking graph functions, that monotonic GCNs still perform well on benchmark datasets, and that sound rules for explanations can be recovered in practice.