Graph Representation Learning (GRL) has emerged as a crucial area for modeling and understanding the structure of graph-structured data across diverse applications. This thesis advances GRL by addressing key challenges in both homogeneous and heterogeneous graphs, including modeling complex heterogeneous relational structures, designing generalizable augmentations for self-supervised learning, improving inductive link prediction in cold-start scenarios, and mitigating over-squashing in message-passing architectures.

Heterogeneous graphs present modeling difficulties due to the presence of multiple node and edge types. To address this, we propose a flexible random walk framework that removes the need for predefined domain knowledge such as meta-paths, enabling more effective and scalable modeling of complex relational structures.

In the self-supervised learning setting, current GRL methods often rely on manually designed graph augmentations that limit generalizability. This thesis introduces augmentation techniques that are task- and domain-agnostic, improving performance across varied graph types and structures.

Inductive link prediction remains challenging for GNNs, particularly in cold-start scenarios where target nodes lack topological context. We propose methods that support efficient and accurate inference without requiring access to neighborhood information of unseen nodes, addressing both scalability and generalization.

While GNNs are effective at capturing local structure, they often suffer from over-squashing, which restricts information propagation across long-range dependencies. To overcome this, we present strategies that improve the aggregation process, enabling GNNs to better preserve and prioritize critical signals from distant parts of the graph.

Through extensive experiments on benchmark datasets, the proposed methods demonstrate consistent improvements in node classification, link prediction, and graph property prediction tasks. Our approaches outperform strong baselines in settings involving heterogeneity, inductive generalization, and large-diameter graphs. Some methods significantly reduce inference cost, while others enhance model expressiveness and robustness by improving structural generalization. Collectively, these contributions show that principled and general-purpose solutions can effectively address long-standing challenges in graph representation learning.