Graph Neural Networks: From Expressivity to Generalisation

Abstract

Graphs are mathematical representations widely used to describe complex relationships in various fields. Graph machine learning techniques, such as Graph Neural Networks (GNNs), have recently demonstrated remarkable success in extracting meaningful patterns from intricate graph data, enabling transformative applications in domains such as drug discovery, social science, combinatorial optimisation, and reasoning.

This thesis focusses on two key aspects of graph representation learning: expressivity and generalisation. Expressivity refers to a model's ability to approximate functions on graphs, while generalisation measures its capacity to adapt to unseen data. We address challenges in both paradigms by designing efficient and powerful models and providing theoretical guarantees that leverage graph topology.

The thesis is structured into three parts. First, we explore GNN limitations from a spectral perspective, particularly their performance on heterophilic graphs. We show that utilising higher frequency bands improves feature learning and propose a new adaptive GNN architecture that performs well on both heterophilic and homophilic graphs. We further demonstrate that restructuring graphs to enhance homophily using a modified spectral clustering technique boosts classical GNN performance by up to 25% on heterophilic datasets.

In the second part, we investigate GNN expressivity in distinguishing nonisomorphic graphs, which is traditionally limited by the Weisfeiler-Lehman (1-WL) test. We propose a novel vertex coloring scheme inspired by graph search algorithms that enhances GNN expressivity beyond 1-WL and effectively addresses graph biconnectivity problems. We introduce a new GNN model based on this scheme and theoretically prove its improved expressive capabilities.

The third part addresses GNN generalisation, an underexplored area compared to expressivity. We analyse the trade-off between expressivity and generalisation, challenging the assumption that highly expressive models overfit. By introducing a k-variance margin-based generalisation bound, we characterise structural properties of graph embeddings and identify the critical balance between intra-class concentration and inter-class separation for effective generalisation. Our framework, validated through experiments on real-world datasets, demonstrates how expressivity can enhance generalisation.

The findings in this thesis have significant implications for fields where complex networks are critical. By advancing GNN expressivity and generalisation, we enable the broader adoption of GNNs to solve real-world problems. For example, in drug discovery, where molecular graphs are often heterophilic, our methods empower practitioners to develop robust GNNs capable of identifying novel molecules with therapeutic potential.