FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale

Training a graph neural network on a graph too big for GPU memory means repeatedly sampling small subgraphs, shipping their node features across the slow link from main memory, and computing over their sparse, irregular structure — and each of those three steps is slow in its own way; this paper from the Chinese Academy of Sciences builds FastGL, which speeds all three at once by reusing the features that consecutive subgraphs share, placing the most-touched data in the GPU's fastest memory, and fusing the sampler's bookkeeping into one pass, training up to 2 times faster than the best prior framework.

The argument in one glance

Problem

A graph too big for the GPU forces a slow sample-ship-compute loop

Real graphs are enormous — billions of nodes, terabytes of features — far too large to load into a GPU with tens of gigabytes of memory. So a graph neural network is trained by repeatedly sampling a small subgraph, shipping the features of its nodes from main memory across a narrow link into the GPU, and computing over its sparse connections. Every iteration pays all three costs, over and over, and together they make training so slow it holds back the use of these models on the large graphs where they matter most.
What people did

Cache node features in a slice of GPU memory

The step that dominates is shipping features across the slow link. The standard fix is to reserve part of the GPU memory as a software cache holding the most useful node features, so that when a sampled node is already cached, its features need not be fetched again from main memory.
Why it fell short

Large graphs leave no room to cache, and the other steps still drag

On a large graph the sampled subgraphs are themselves huge, so there is little or no GPU memory left to spare for a cache — one popular system hits under 20 percent on a big dataset, and shrinking the batch to free memory just multiplies the number of batches. Meanwhile the sampler burns time synchronizing threads, and the sparse computation leaves the GPU caches nearly empty and its arithmetic units idle. Fixing one step alone leaves the others as bottlenecks.
This paper's idea

Speed all three steps using the graph structure and the GPU hierarchy

FastGL accelerates all three phases at once. For shipping, it exploits that consecutive sampled subgraphs share up to 93 percent of their nodes, reusing features already on the GPU and reordering batches to maximize that overlap — with no cache and no extra memory. For computing, it places the data touched most often in the GPU's fastest memory. For sampling, it fuses the identifier bookkeeping into a single pass that needs no thread synchronization.

Why this problem is worth solving

The training method exists because the graphs are too big to handle any other way, and that method sets the whole cost structure.

Sampling-based training is how graph neural networks are trained when the graph will not fit in GPU memory. Rather than loading the whole graph, the system repeatedly draws a mini-batch of target nodes, samples a bounded neighborhood around each — a subgraph — ships the features of those sampled nodes from main memory into the GPU, and runs the network forward and backward over the subgraph, one iteration per mini-batch. The graph topology and the node features stay in the large host memory; the GPU only ever sees a subgraph at a time. This makes arbitrarily large graphs trainable, but it splits every iteration into three distinct phases — sample, ship features across the link, compute — each of which is a separate performance problem, and none of which a technique aimed at one phase can fix for the others. That three-way split is the structure the whole paper is organized around.

The reason the computation phase in particular runs so far below the hardware’s potential is a mismatch with how GPU memory is built.

A GPU has several levels of memory with wildly different speeds: a small, very fast on-chip memory shared within a group of cores at roughly twelve terabytes per second; a larger, mid-speed second-level cache at three to five; and the large main GPU memory at under one terabyte per second — more than ten times slower than the fast on-chip level, but the only one big enough to hold the data. The catch is that the fast levels are tiny, so only a fraction of data can live there. In a graph network, the core operation is aggregation — each node gathering and combining features from its sampled neighbors — and because a graph’s connections are sparse and irregular, these accesses jump around unpredictably, so data fetched into the fast cache is often evicted before it is reused. The result is cache hit rates of a few percent and arithmetic units left starved, running at a small fraction of their peak. Which data sits in which level of this hierarchy is therefore the lever on how fast the computation runs.

What people did before, and where it broke

Load the whole graph and train on all of it (full-graph training). Keep the entire graph in GPU memory and compute over it directly, as several early systems did. Where it broke. It is capped by GPU memory capacity, so it simply cannot handle the large-scale graphs that need it — the reason sampling-based training exists at all.
Reserve GPU memory as a feature cache. Hold the most valuable node features in a slice of GPU memory so repeat accesses skip the slow link. Where it broke. On large graphs the sampled subgraphs are so big — a consequence of neighborhoods exploding as you sample more hops — that little or no memory is left for a cache, dropping hit rates below 20 percent and gutting the benefit exactly when it is needed most.
Shrink the mini-batch to free up cache room. Use smaller batches so more GPU memory is available to cache. Where it broke. A smaller batch proportionally increases the number of batches to train, so the extra per-batch overhead cancels the memory-IO savings.
Sample on the CPU. Run the subgraph sampling on the host processor, as some frameworks do. Where it broke. The CPU lacks the parallelism for this, so sampling balloons to as much as 97 percent of the entire training time.
Sample on the GPU but re-map identifiers. Use the GPU’s threads to sample fast, converting each node’s global identifier to a local one so only the sampled features load. Where it broke. Building that identifier map requires heavy thread synchronization, which alone can consume nearly 40 percent of the iteration.
Preprocess the graph to speed the computation. Restructure the graph up front for efficient aggregation, as a full-graph accelerator does. Where it broke. In sampling-based training a fresh subgraph appears every iteration, so the preprocessing must run every time and cannot be amortized — it grows to dominate the very phase it was meant to speed up.
The gap. Every prior approach optimized a single phase, and the most common one leaned on a cache that large graphs cannot afford. Nothing accelerated sampling, shipping, and computing together while respecting both the graph’s structure and the GPU’s memory hierarchy — which is precisely where the slack was.

How FastGL is put together

The three phases of an iteration, each accelerated by one technique

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Consecutive subgraphs overlap enormously, so reuse what is already there and reorder to overlap more. The dominant cost is shipping node features across the narrow link, and the standard remedy — a GPU-memory cache — fails because large graphs leave no room for one. FastGL sidesteps the cache entirely with an observation about structure: because a node in a dense large graph connects to many others, it gets drawn into many different sampled subgraphs, so consecutive mini-batches share a large fraction of their nodes — up to 93 percent on the graphs studied. The Match step exploits this directly: before shipping the features for a new mini-batch, it intersects that batch’s nodes with the batch already sitting on the GPU and ships only the non-overlapping remainder, reusing the shared features already resident. This costs no extra memory, because the previous batch’s features had to be there anyway. Because the overlap between different pairs of batches varies, a Greedy Reorder step then rearranges the computation order of a group of sampled batches so that each one follows the batch it shares the most with, squeezing out up to a further quarter of the traffic. Rearranging the order of work so that neighboring units share as much as possible, turning incidental overlap into deliberate reuse, is the same move the concurrent-graph-traversal work covered elsewhere on this site makes when it aligns many simultaneous traversals so they walk the graph together and share the memory they touch rather than each paying for it alone.

In the aggregation, some data is touched constantly and some barely, so put the constant data in the fast memory. The computation runs far below the GPU’s peak because its irregular accesses evict data from the fast caches before it can be reused, and those caches are hardware-managed, so software cannot pin anything in them. FastGL’s response is to look at how often each piece of data is actually touched. When a node aggregates features from its neighbors, its running partial sum and the per-edge weights are read over and over — once for every one of its neighbors, across every feature dimension — while each neighbor’s feature vector is read only once. So FastGL places the partial sums and weights in the GPU’s fast, software-managed on-chip shared memory, which has the same speed as the first-level cache but can be controlled explicitly, and leaves the seldom-read features in slow main memory. Because a node’s whole aggregation is confined to one thread block, the shared memory need hold only that block’s hot data at a time. The analysis puts the resulting access time about ten times lower. Deciding placement in a memory hierarchy by measuring which data is accessed most and promoting exactly that to the scarce fast tier is the same discipline the recommendation-embedding placement work covered elsewhere on this site applies, profiling access frequency so the small pool of fast memory holds the hot rows and nothing else.

The sampler’s identifier bookkeeping is two operations fighting each other, so fuse them into one. Sampling on the GPU is fast, but each subgraph needs its nodes’ global identifiers remapped to compact local ones so that only the sampled features, not the whole graph, are loaded — and building that map conventionally means calculating local identifiers and constructing a lookup table as separate steps that must synchronize across threads, a synchronization tax that can eat nearly 40 percent of the sample phase. FastGL’s Fused-Map merges the two into a single GPU kernel: as each thread atomically inserts a global identifier into a hash table, the same atomic operation reports whether that identifier was new, and if so the thread assigns it the next local identifier on the spot. Building the table and producing the mapping happen together, in one pass, with the atomic operations providing the only coordination needed, so the explicit thread synchronization disappears. Collapsing two passes that were forced to hand off through a synchronization barrier into a single fused pass that carries both computations at once is the same optimization the memory-bound-operator-fusion work covered elsewhere on this site is built on, stitching together operations that would otherwise stall waiting on each other into one kernel that pays the memory cost only once.

Following one mini-batch through FastGL

Sampling, shipping, and computing one mini-batch

One iteration of sampling-based GNN training as FastGL runs it, showing where each of the three techniques acts. A group of mini-batches is sampled together so they can be reordered.

Step 1 of 5

Sample the batch and build its identifier map in one pass

The GPU samples a bounded neighborhood for each target node in the mini-batch. As it does, Fused-Map builds the global-to-local identifier map in a single kernel: each thread atomically inserts a node into a hash table and, if the node is new, assigns it the next local identifier immediately.

The atomic insertion doubles as the coordination, so there is no separate synchronization step between calculating identifiers and building the table — the source of the old sampling overhead.

Why it works

Structural overlap makes reuse cheaper than caching. Consecutive subgraphs share up to 93 percent of their nodes because dense-graph nodes appear in many sampled neighborhoods → so reusing the features already resident from the previous batch skips shipping them again → cutting the dominant memory-IO cost with zero GPU memory overhead, exactly where a cache runs out of room.
Reordering turns incidental overlap into maximal overlap. The share of nodes two batches have in common varies widely across pairs → so greedily ordering batches to follow the one they overlap most → reduces the shipped traffic by up to a further quarter beyond plain reuse.
Access frequency, not data size, decides placement. In aggregation the partial sums and weights are read once per neighbor while features are read once → so promoting the frequently-read data to the fast on-chip memory and leaving the rarely-read features in slow memory → drops the access time roughly tenfold and raises achievable performance up to four times, without moving any more data.
Software-managed memory does what the cache cannot. The first-level cache is hardware-managed and evicts the hot data under irregular access → but the shared memory has the same speed and is controlled explicitly, scoped to a single thread block → so the framework can pin exactly the hot working set that the cache kept losing.
Fusing the sampler’s two passes removes their handoff. Calculating local identifiers and building the lookup table separately forced threads to synchronize between them → but doing both inside one atomic hash-table insertion carries the mapping alongside the table → so the synchronization that consumed up to 40 percent of sampling simply does not occur.

What it costs (trade-offs and scope)

The headline reuse depends on high overlap, which is not universal. Match-Reorder works because these graphs and this neighbor-sampling scheme produce up to 93 percent overlap between consecutive subgraphs; on graphs or samplers that produce little overlap the benefit would shrink. The authors show a random-walk sampler still helps, but low-overlap regimes are not stressed, so the gains are strongest exactly where structure is favorable.
Match reuses only the immediately previous batch. It intersects each batch with the one still resident, not with batches further back, since keeping more resident would cost memory — so it captures pairwise, greedy reuse rather than the full overlap across a whole group.
Reorder is a greedy heuristic with its own cost. The ordering is nearest-overlap-first, not provably optimal, and it computes a full pairwise overlap matrix for each group of batches; this is cheap relative to the IO it saves, but it is extra work and can leave reuse on the table.
Memory-Aware moves no less data; it only speeds access. The technique does not reduce the total bytes read, only the time to read them by placing hot data in faster memory, and the roughly tenfold figure is an analytical estimate — the measured computation speedup is a more modest 1.1 to 6.7 times, and it requires custom GPU kernels that each network layer must adopt.
One baseline is used outside its design. The full-graph accelerator it beats by up to nine times was built for a setting where preprocessing runs once; forcing it into per-iteration sampling makes preprocessing dominate, so that comparison partly measures a tool used out of its regime, as the authors acknowledge.
The averages hide large per-dataset variance. The biggest speedups — up to 29 times over CPU-sampling frameworks, up to 5 times over the strong GPU baseline — are best cases on smaller graphs or against weak baselines; on the largest graphs the gain over that GPU baseline is closer to 1.2 to 1.3 times, so the picture is workload-dependent.
It is single-machine, not distributed. Everything is evaluated on one server with up to eight GPUs; large scale here means large single-machine graphs, not the billion-node distributed training that some deployments need.
The contribution is three stacked optimizations, not one idea. FastGL is a well-engineered bundle of three phase-specific accelerations that happen to compose; its strength is coverage of all three phases rather than a single unifying mechanism.

The evaluation

Four sampling-based GNN training frameworks

Property	DGL (GPU sample + prefetch)	GNNLab (GPU-memory cache)	GNNAdvisor (full-graph compute)
How it handles feature shipping
Works when GPU memory is scarce	Not applicable		Not applicable
Computation optimization
Sampling overhead		GPU, parallel sampling	Borrows another sampler
Result	Baseline	Strong, but discounts on large graphs	Preprocessing dominates

Comparison of sampling-based GNN training frameworks on five graph datasets (up to 111 million nodes) across GCN, GIN, and GAT models, measured on two RTX 3090 GPUs. FastGL improves average training efficiency by 11.8, 2.2, and 1.5 times over PyG, DGL, and GNNLab respectively.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

FastGL’s strength is that it attacks all three phases of sampling-based GNN training at once, and its central observation — that consecutive subgraphs overlap heavily, so features can be reused with no cache and no spare memory — is a genuinely good fit for the large-graph regime where caching fails. But the wins are structural and workload-dependent. Match-Reorder relies on high overlap between batches, which holds for these graphs and neighbor sampling but would fade on low-overlap graphs or samplers; it reuses only the immediately previous batch, and its reorder is a greedy heuristic. Memory-Aware moves no less data, only speeds access, and its tenfold figure is analytical against a measured 1.1-to-6.7-times computation speedup, needing custom kernels per layer. The comparisons are partly against baselines outside their intended setting — a full-graph accelerator forced to preprocess every iteration — and the headline multipliers up to 29 times are best cases against weak CPU-sampling baselines, with gains over the strong GPU baseline on the largest graphs closer to 1.2 to 1.3 times. Everything is single-machine, up to eight GPUs, so large scale means large single-machine graphs, not distributed billion-node training. Read it as a solid, well-measured engineering bundle whose reuse idea is the durable contribution, rather than a single breakthrough.

Background

Why graph learning strains the memory system so badly

It is worth stepping back to see why graph neural networks are such an awkward fit for GPUs in the first place, since that is the pressure every technique here responds to. A conventional neural network processes dense, regular data — an image, a batch of vectors — where memory access is predictable and the hardware’s caches and wide arithmetic units are kept fed. A graph is the opposite: connections are sparse and irregular, every node has a different number of neighbors, and following an edge is a jump to an unpredictable location. Worse, the neighborhood a node depends on explodes as you look more hops out, because each neighbor brings its own neighbors, so the working set balloons even as you sample to contain it. This combination — irregular access, exploding working sets, features far larger than the fast memory — is exactly what defeats the GPU memory hierarchy, and it is why so much systems work on graph learning is really about memory management rather than arithmetic. The same neighborhood-explosion pressure drives the large-scale-GNN-training work covered elsewhere on this site, which has to partition the swelling neighborhood just to fit a single batch in GPU memory. FastGL is one more response to the same underlying fact: for graph networks, the bottleneck is almost never the math — it is getting the right data to the right place fast enough, and the graph’s own structure is both the source of the difficulty and, cleverly used, part of the cure.

If you remember only three things

1. Training a graph neural network on a graph too big for GPU memory is done by sampling small subgraphs and training mini-batch by mini-batch, but every iteration is slow in three separate ways: the sampler wastes time synchronizing threads, the node features crawl across a narrow link from main memory that dominates the runtime, and the sparse computation leaves the GPU caches nearly empty — and prior frameworks each fix only one phase, most commonly with a GPU-memory cache that large graphs leave no room for.
2. FastGL accelerates all three phases together. Match-Reorder exploits that consecutive subgraphs share up to 93 percent of their nodes, reusing features already resident and greedily reordering batches to maximize that overlap, cutting the dominant shipping cost with no cache and no extra memory; Memory-Aware computation places the constantly-touched partial sums and weights in the GPU's fast on-chip shared memory while leaving once-read features in slow memory; and Fused-Map builds the sampler's identifier map in a single synchronization-free pass.
3. The result is up to 5.1 times faster training than the strong GPU baseline DGL and 2.0 times over the cache-based GNNLab on graphs up to 111 million nodes — but the reuse win depends on the high overlap that these graphs and samplers happen to have, Memory-Aware speeds access without moving less data, some comparisons use baselines outside their regime, and everything is single-machine, so it is best read as a well-engineered three-phase bundle whose structural-reuse idea is the lasting contribution.

Check yourself

Check your understanding

1. Why does the standard GPU-memory cache fail for large-scale GNN training?
2. What structural property does Match-Reorder exploit, and how?
3. How does Memory-Aware computation speed up the aggregation?
4. Which limitation most affects how FastGL's results should be read?

Sources

The paper is “FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale” by Zeyu Zhu, Peisong Wang, Qinghao Hu, Gang Li, Xiaoyao Liang, and Jian Cheng, published at ASPLOS 2024, pages 94-110, DOI 10.1145/3622781.3674167. The authors are at the Institute of Automation, Chinese Academy of Sciences, and collaborators.

This explainer is written from the full 17-page text. Everything above comes from the paper’s own sections: the introduction and background identifying the three bottlenecks of sampling-based GNN training and the breakdown across sample, memory-IO, and computation phases; the motivation section quantifying the memory-IO dominance (up to 77 percent), the failure of GPU-memory caches under scarce memory (a below-20-percent hit rate), the up-to-96-percent node overlap between subgraphs, and the low L1/L2 cache hit rates (4.41 and 19.6 percent) that starve the computation; the design section presenting the Match-Reorder strategy with its match-degree metric (up to 93.2 percent) and the greedy reorder algorithm, the Memory-Aware computation method with its access-frequency analysis and roughly tenfold access-time reduction placing partial sums and weights in shared memory, and the Fused-Map sampling method fusing local-identifier calculation with atomic hash-table construction to eliminate thread synchronization; the implementation on PyTorch with custom CUDA kernels and the comparison of framework capabilities; and the evaluation on GCN, GIN, and GAT over five datasets on RTX 3090 GPUs, reporting the up-to-28.9-times, 5.1-times, 8.8-times, and 2.0-times speedups over PyG, DGL, GNNAdvisor, and GNNLab, the per-technique breakdown (Match-Reorder dominant, Memory-Aware 1.6 times, Fused-Map smaller), the up-to-4.2-times GPU-performance and 1.1-to-6.7-times computation gains, the up-to-25-percent additional benefit from Greedy Reorder, and the scalability and memory-trade-off analyses.