Graphs are powerful data structures that are used to model some of the most complex systems in the world, such as interpersonal relationships in social networks, protein-protein interactions in biology, and user-item pairs in recommender systems. Generating representations that encode the rich information from graph data enables state-of-the-art solutions to many real-world applications across various domains.

This dissertation focuses on our recent work on representation learning for information-rich graphs. We first present a unified framework for random-walk based graph embedding approaches and analyze how different choices of model components affect downstream task performance. We then propose a novel embedding method for signed graphs, which incorporates social theory into random-walk dynamics to capture social polarization and enable effective signed link prediction. For attributed graphs, Graph Neural Networks have become the most popular representation learning paradigm. We address their limitations in combining structural and attribute information for link prediction and introduce the first global counterfactual explainer for their applications in graph classification. Finally, we investigate representation learning for multiscale graphs and discuss several related problems including semi-supervised node classification, community detection, and anomaly detection. Research in this dissertation demonstrates the importance of accounting for the interplay between the rich graph information and downstream task properties in successful graph representation learning models.