Trustworthy Graph Machine Learning with Applications to Combinatorial Optimization and Clustering Problems

In the 21st century, graph machine learning has been dominated by graph representation learning and graph neural networks (GNNs). These methods map each node (or edge) of a given graph to a low-dimensional vector (also known as an embedding) for downstream tasks in social, technological, and biological domains. My dissertation advances the interpretability, robustness, and utility of such representations, demonstrating their effectiveness in accelerating combinatorial optimization and in extracting biological insights from gene co-expression networks. First, I introduce a framework to interpret each dimension of an embedding vector in a human-understandable way by relating it to well-known graph features such as degree, clustering coefficient, and PageRank. Second, I investigate how to make graph embedding algorithms robust to adversarial attacks. I present a method that captures two distinct sources of uncertainty - uncertainty in the input data via spectral decomposition and uncertainty in the model output via a student-teacher learning paradigm - and incorporates these during training. This produces embeddings that, under adversarial attacks, outperform state-of-the-art methods by an average of 1.5\% in classification accuracy. Third, I explore the use of GNNs to accelerate combinatorial optimization. I present a method that predicts a reduced subgraph containing the optimal solution, achieving up to $10\times$ speedup for the shortest path attack problem. I then generalize this subgraph-selection paradigm to set cover problems, demonstrating reduction of problem size by 60-80\% and up to $10\times$ runtime speedup over Gurobi while preserving solution quality. To address the limitation that each optimization problem currently requires its own model, I introduce a pre-trained model trained on diverse mixed-integer programming instances using a vector-quantized graph autoencoder. This single model generalizes across problem types - set cover, combinatorial auctions, graph isomorphism, and maximum vertex cover. Finally, I combine uncertainty quantification and vector quantization to analyze gene co-expression networks from a $16$-lake stickleback transplant experiment across five years. This work demonstrates that the representation learning techniques developed for combinatorial optimization transfer directly to biological discovery, underscoring the broader premise of trustworthy and scalable graph representation learning.