Abstract
dc:description.abstractTraining Graph Neural Networks (GNNs) at a large scale requires significant computational resources. One of the most effective ways to reduce resource requirements is minibatch training coupled with graph sampling. Existing methods encounter a significant bottleneck to scaling due to the Neighborhood Explosion Phenomenon (NEP). This thesis focuses on designing composable algorithms aimed at mitigating the effects of NEP and presents a GNN training framework incorporating optimized implementations of these algorithms. First, we present a novel sampling algorithm, LAyer-neighBOR (LABOR), which is designed to be a direct replacement for Neighbor Sampling (NS) with the same fan-out hyperparameter while sampling up to 7x fewer vertices, without sacrificing quality. LABOR is designed so that the variance of the estimator for each vertex is aligned with that of NS. Moreover, under the same vertex sampling budget constraints, LABOR converges faster than existing layer-sampling approaches and can use up to a 112x larger batch size compared to NS. Second, we present Cooperative Minibatching. We leverage the observation that the size of the sampled subgraph is a sublinear and concave function of the batch size, leading to noteworthy reductions in the workload executed per seed vertex as the batch size increases. Hence, it is favorable for processors equipped with a fast interconnect to work on a large minibatch together instead of working on separate smaller minibatches. We also show how to take advantage of the same phenomenon in serial execution by proposing Dependent Consecutive Minibatches. Our experimental evaluations demonstrate that increasing this dependency results in up to a fourfold reduction in bandwidth requirements for fetching vertex embeddings, without negatively impacting model convergence. Third, we present GraphBolt, an end-to-end GPU-accelerated data loading framework for large-scale GNN training. GraphBolt integrates LABOR sampling and Cooperative Minibatching within a composable pipeline built on PyTorch DataPipes, alongside system-level optimizations including software pipelining via asynchronous futures, dynamic multi-level feature caching across GPU, CPU, and SSD tiers, incremental graph caching, and GPU-accelerated sampling kernels with edge-parallel load balancing. GraphBolt requires no preprocessing for its caches and supports heterogeneous graphs, temporal graphs, node classification, and link prediction through shared, composable implementations. All of the algorithms presented above are composable, meaning that the savings increase in a multiplicative manner as we combine these approaches. GraphBolt demonstrates this by combining all of these techniques in a unified framework with optimized implementations, achieving significantly higher training throughput than existing frameworks such as DGL and PyG on large-scale GNN training workloads.
Degree
thesis:*- Name thesis:degree_name
- Computer Science, PhD
- Department thesis:degree_department
- Computational Science and Engineering
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Balin, Muhammed Fatih
- Advisor dc:contributor.advisor
-
- Çatalyürek, Ümit V.
- Committee members dc:contributor.committeemember
-
- Li, Pan
- Lin, Yingyan (Celine)
- Luo, Yunan
- Dai, Bo
- ORCID person:identifier.orcid
Rights
- Language dc:language.iso
- English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/81742