Recent years have witnessed a surge of interest in representation learning on graph-structured data, which are pervasive in diverse real-world domains, spanning fundamental physical interactions, biological systems, social networks, and logic circuits. However, there is a strong tension between the accuracy and efficiency of existing graph representation learning (GRL) models. Firstly, many real-world graphs (e.g. social networks and logic circuits) are notably large, comprising millions or even billions of nodes and edges, which poses a substantial challenge on model efficiency for training and deployment. Additionally, different domains have complex and diverse graph structures, which are also exposed to adversarial attacks that perturb graph topology via adding or removing nodes and edges. These graph properties necessitate sophisticated model architectures to produce high-quality graph representations, which often come with nontrivial computation cost and memory usage. In this dissertation, we present research solutions that cover scalable, hardware-friendly, expressive, and robust GRL models for accurate and efficient representation learning on large-scale graph applications. We firstly propose GraphZoom, a multi-level approach for fast and accurate GRL. GraphZoom leverages lightweight algorithms that iteratively reduce graph size for GRL and progressively refine graph representations with theoretical guarantees based upon spectral graph theory. This results in a 40.8x training speedup over prior arts with comparable or even better accuracy. Secondly, we develop HOGA for scalable and generalizable GRL on large-scale circuits, via adopting a hop-wise graph attention scheme. HOGA not only outperforms prior GRL models on challenging circuit problems, but is also friendly to distributed training by mitigating communication overhead caused by graph dependencies. This renders HOGA applicable to industrial-scale circuit applications. Thirdly, we introduce Polynormer, an expressive graph transformer model with linear complexity. We theoretically demonstrate the superior expressivity of Polynormer through the lens of polynomial functions. Our extensive experiments indicate that Polynormer not only achieves state-of-the-art results across a wide variety of mainstream graph datasets, but also outperforms a popular baseline model by 31.8% on an industrial-scale dataset provided by Google for predicting AI model runtime on TPU. Last but not least, we propose an efficient graph topology learning approach called GARNET for accurate GRL under graph adversarial attacks. We theoretically show that GARNET can effectively recover critical structures from an adversarial graph with nearly-linear complexity. This leads to an accuracy improvement of up to 10.23% over previous robust GRL models on a broad range of adversarial graphs.