Non-parametric modelling of signals on graphs

Abstract

Graphs are simple yet powerful data structures that describe entities and their relationships between each other using nodes and edges, making them popular candidates for modelling a wide variety of real-world objects, ranging from molecules to social or biological networks. As a result of their suitability for various modelling scenarios, machine learning on graph-shaped data has emerged as an important field of research in the last few years. While powerful when coupled with machine learning models, graphs pose unique challenges to those models, which need to be able to adapt to not only highly diverse data but also a highly diverse graph domain that may vary in size, connectivity patterns, and its interaction with node features, to name a few. In this work, I hypothesise that Gaussian processes, a class of Bayesian non-parametric models, are particularly well suited for modelling data on graph domains. To provide evidence for this hypothesis, I demonstrate the merits of Bayesian non-parametric modelling for graph data by deriving Gaussian process models for three of the most important tasks in graph machine learning: link prediction, graph-level prediction, and node-level prediction. The resulting models exhibit a number of strengths, including good model fit and robustness against overfitting due to their non-parametric nature, in addition to well calibrated uncertainty estimates. Moreover, the capability of Gaussian processes to optimise hyper-parameters allows designing models that adapt to a graph's particular characteristics, such as the smoothness and multi-scale structure of a graph signal or the locality of features. These strengths of the proposed models and in particular their competitive performance compared to a range of baseline models are confirmed in extensive experiments on a wide range of real-world data sets.