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 vector or embedding) for downstream tasks in social, technological, and biological domains. My dissertation advances the interpretability and robustness of algorithms that produce such embeddings and demonstrates their usefulness in accelerating combinatorial optimization problems (such as set cover) and improving clustering on real-world biological data, specifically gene co-expression networks. First, I introduce a framework to interpret each dimension of an embedding vector in a human-understandable way by relating them to well-known graph features such as degree, clustering coefficient, and PageRank. Second, I investigate how to make algorithms that embed nodes of a graph robust to adversarial attacks. To achieve this, I examine methods for capturing uncertainty in the input data and in the model, and then incorporate these uncertainties during training to produce embeddings that perform better, in terms of accuracy, under adversarial attacks by an average of 1.5\% compared to state-of-the-art methods. Third, I explore real-world applications of GNNs, specifically in combinatorial optimization problems represented as bipartite graphs. I present an approach that accelerates set cover problems by up to 10 times on average compared to Gurobi (a state-of-the-art commercial solver), and I present a pre-trained model using vector-quantized GNNs that can generalize across various mixed-integer programming instances. For the final part of my dissertation, I propose combining uncertainty quantification and vector quantization to unlock new insights in gene co-expression networks, underscoring the broader premise of trustworthy and scalable graph representation learning.