Graphs in Unsupervised Machine Learning

Abstract

Graphs are versatile data structures that represent individual data points and the intricate relationships between them, making them invaluable for modelling complex real-world systems. Their flexibility allows them to be applied to a wide range of problems, and with appropriate algorithms, they have become crucial in many domains. In particular, unsupervised machine learning – where patterns are discovered without labelled data – has greatly benefited from integrating graphs. This thesis presents an introduction to unsupervised machine learning on graphs, focusing on clustering and representation learning. We explore the strengths and challenges of applying graphs to machine learning, emphasizing these two specific tasks. Our contributions span two distinct perspectives within unsupervised learning on graphs. In the first part, we pro- pose a novel clustering method inspired by the concept of tangles from mathematical graph theory. Tangles are used to detect densely connected subsets within a graph, and we adapt this idea to cluster data across various domains. Our approach yields a soft clustering hierarchy that is often inherently interpretable. We provide theoretical performance guarantees across different data types and validate the method’s effective- ness through extensive empirical evaluations. The second part of this thesis delves into representation learning on graphs. We investigate the inductive biases of graph auto- encoders, connecting their non-linear architecture to a linear model. Our empirical findings show that linear models can match or surpass the performance of non-linear graph auto-encoders when node features are effectively leveraged. Additionally, we analyze the constraints imposed by features on the solution space, offering theoretical and empirical evidence that these features are the key to achieving strong performance in this setting.