Title: Machine Learning via Spectral Graph Theory and Optimal Transport

Program: Mathematics MS

Committee Chair: Michael Perlmutter

Committee: Michael Perlmutter, Grady Wright, Kyungduk Ko

Abstract: Graph-structured data can be found in a variety of domains such as social and information networks, transportation and infrastructure, finance, and biology. In this paper, we explore machine learning for graph-structured data using various techniques, most of which are developed from spectral graph theory. We begin by reviewing the theory of spectral clustering, focusing on an asymptotic result on community recovery in the stochastic block model, which is formulated as a latent space model. For the purpose of image classification, we construct similarity graphs using Wasserstein distance between images, a concept from optimal transport. We perform spectral clustering on the Wasserstein distance-based similarity graphs, which shows that the spectral domain of these graphs contains valuable information for classification. Then, we demonstrate that graph neural networks trained on these graphs outperform dense neural networks in the semi-supervised setting. Overall, our results show that combining optimal transport with spectral graph-based methods yields geometry-aware graph representations which are conducive to data science problems. We also prove a tighter bound on the spectrum of a message passing operator in a widely-used graph neural network architecture known as the Graph Convolutional Network. Lastly, we explore signed directed graphs, and how they are encoded in matrices via the Magnetic Signed Laplacian. We evaluate spectral clustering on the Magnetic Signed Laplacian via the signed directed stochastic block model.