Tile-Shaped Neighbor Sampling for Graph Neural Networks

Graph neural networks (models that update each node by repeatedly averaging information from its neighbors) hit two walls when trained on large graphs. The first is neighbor explosion: with $L$ layers, one node's prediction depends on its whole $L$-hop neighborhood, which grows exponentially. Training therefore samples a few neighbors per node at each layer. The second is sparsity overhead: the sampled graph is an irregular sparse matrix. GPUs are built for dense, contiguous blocks of arithmetic, so the scattered memory reads cost more than the arithmetic that was skipped. Today these problems are handled separately. Samplers minimize how many nodes they touch and ignore memory layout. Fast sparse kernels need an expensive offline repacking step that cannot be repeated for every freshly sampled mini-batch.

We propose a sampler whose basic random choice is a whole tile: a block of 16 target nodes paired with a block of 16 source nodes that are contiguous in a fixed node ordering. Each sampled mini-batch adjacency matrix then comes out already arranged as dense 16×16 blocks that GPU matrix units (Tensor Cores) can multiply directly. Its feature reads are contiguous, and the same source block is shared by all targets in a tile, much as correlated samplers share neighbors. A per-tile reweighting keeps the aggregate an unbiased estimate of the full-neighborhood average. The open question is whether real graphs, after one offline reordering, have enough block density for this sampling to keep accuracy while reducing end-to-end training time.

Core Claim

The expensive irregularity in mini-batch training comes from the sampler, so the fix belongs in the sampler and not in a post-hoc kernel. The plan has two steps. Reorder the static full graph once offline so that neighborhoods cluster into contiguous index ranges. Then sample at the granularity of (target tile, source block) pairs and weight each kept tile by its inverse inclusion probability. The sampled adjacency is born in a block-sparse format with no per-batch conversion, and the estimator stays unbiased.

Concretely, let $T$ be a tile of target nodes and $B$ a block of source nodes. Let $a_{ij}$ be the normalized edge weight and $x_j$ the source feature. Each nonempty pair $(T,B)$ is kept with probability $p_{T,B}$, recorded by an indicator $z_{T,B}$ with $\mathbb{E}[z_{T,B}]=p_{T,B}$. The layer aggregate for $i \in T$ is

$$\hat h_i = \sum_{B} \frac{z_{T,B}}{p_{T,B}} \sum_{j \in B} a_{ij}\, x_j ,$$

which equals the full-neighborhood aggregate $\sum_j a_{ij} x_j$ in expectation, by linearity of expectation. Each kept term is one dense 16×16 block times a 16-row feature slab.

We set $p_{T,B}$ proportional to the block's edge mass, capped at one, so the per-tile budget plays the role of the per-node fanout in standard sampling. The added variance compared with independent per-edge sampling comes from treating a block's edges as all-or-nothing. It should therefore grow with how unevenly edge mass is spread inside a block, which is exactly what the offline reordering tries to reduce.

Relation to Prior Work

Two lines of work motivate the proposal by documenting the gap.

A Unified Lottery Ticket Hypothesis for Graph Neural Networks jointly prunes weights and edges. It finds the adjacency matrix is the main compute cost and removes most multiply-accumulates, but its authors state that the resulting unstructured sparsity gives no GPU wall-clock gain. Our work targets wall-clock time and runs inside mini-batch sampling, not full-graph pruning.

Layer-Neighbor Sampling — Defusing Neighborhood Explosion in GNNs (LABOR) shares one random variable per candidate neighbor across the batch. This sharply cuts unique sampled vertices on Reddit. However, it optimizes vertex counts and leaves the sampled matrix irregular, and it reports small gains on sparse graphs such as Flickr. We borrow its central idea, correlating sampling decisions so that work is shared, and move the correlation to the level of hardware tiles.

Three papers supply methods we reuse.

We pay SMaT-style reordering exactly once, on the static full graph, and let the sampler preserve block structure. That is the step neither paper takes.

Two papers constrain the design.

Research Program

Offline reordering. We compare three orderings of the full graph: graph-partitioner order, SMaT's Jaccard row reordering, and degree-bucketed order. For each we measure block density, meaning the fraction of nonzeros within occupied 16×16 tiles. This is a one-time cost and is reported as such.

Sampler. We implement the tile sampler on GPU. It needs one random draw per (tile, block) pair, not one per edge. Inclusion probabilities are set from block edge mass, and the per-tile budget is chosen to match the edge count that standard fanout sampling would produce. Multi-layer sampling proceeds layer by layer: the source blocks kept at layer $\ell$ become the target tiles at layer $\ell-1$, so tile alignment carries through all layers.

Kernel. The aggregation kernel multiplies the sampled block list against contiguous feature slabs using standard FP16 Tensor Core instructions. It requires no Ampere 2:4 sparsity support, which avoids the hardware restriction noted for Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch. As a secondary variant, we enforce 2:4 sparsity inside each block, drawing on that same paper, to test whether the extra hardware skipping is worth the added sampling constraint.

Variance analysis. We measure gradient variance relative to full-neighborhood gradients and relate it to how unevenly edge mass is spread within blocks. If variance is too high, we add a historical-activation control variate restricted to dropped blocks.

Baselines

The naive reference point is uniform per-node neighbor sampling (GraphSAGE-style, fixed fanout) with stock gather-and-scatter aggregation. We run it with the same model (a 3-layer GraphSAGE-mean and a GCN), the same hidden size, the same GPU, and a learning-rate and fanout sweep of equal size to ours. On ogbn-products the Open Graph Benchmark paper reports 78.50% test accuracy for GraphSAGE and 79.08% for GraphSAINT (Open Graph Benchmark: Datasets for Machine Learning on Graphs). We must match these within noise for any speedup to count.

The strongest existing sampler is LABOR, which reports reaching the 91.5% target accuracy on ogbn-products in 38.2 s versus 43.8 s for neighbor sampling (Layer-Neighbor Sampling — Defusing Neighborhood Explosion in GNNs). We rerun LABOR ourselves on identical hardware and data loading, with equal tuning effort. Beating it means a lower time-to-target-accuracy on ogbn-products and Reddit at equal final test accuracy, since its published number comes from different hardware.

The strongest kernel-side competitor is LABOR's sampled batch converted each step into the weighted 16×16 block format of On Efficient Scaling of GNNs via IO-Aware Layers Implementations and run on Tensor Cores. We charge the per-batch conversion to its time. This isolates our claim that generating tiles is cheaper than converting to them.

The locality-biased baseline is GNNSampler-style sampling. Its key ablation is our own tile sampler with the $1/p_{T,B}$ reweighting removed, which isolates the role of unbiasedness. The second ablation keeps tile sampling but executes it with a standard sparse kernel. This separates the gains from memory locality from the gains due to Tensor Cores.

Why not just…?

Why not just precompute propagation and train an MLP? Pre-propagation removes sampling entirely and can be very fast; UltraGCN is reported 14× faster than LightGCN on Amazon-Book (Survey on Graph Neural Network Acceleration: An Algorithmic Perspective). However, Acceleration Algorithms in GNNs: A Survey notes that removing trainable aggregation limits expressiveness. Our claim only matters for models with learned, nonlinear message passing. We include SIGN-style precomputation as a reference. If it matches our accuracy at lower cost on every dataset, then for those datasets the proposal is moot, and we will say so.

Why not just partition the graph, as Cluster-GCN does, and train on dense-ish clusters? Partitioning gives contiguous blocks too, but it permanently deletes edges between clusters, so the estimator is biased. The adjacency inside each cluster also stays unstructured. Our sampler can draw any source block, including ones across partitions, with unbiased weights. A Cluster-GCN run on the same reordering is a direct comparison, and the reweighting ablation shows whether unbiasedness matters for accuracy.

Why not just sample normally and convert each batch into tiles, or simply fuse the kernels? This is the real threat. If per-batch conversion is cheap, or if aggregation is a small part of step time, then sampler co-design buys nothing. GNNSampler attributes over 60% of end-to-end time to sampling itself (GNNSampler), so faster aggregation alone could be irrelevant. The proposal answers this on two fronts. It also cheapens sampling (one draw per tile instead of per edge) and feature gathering (contiguous slabs). And we profile a full per-phase time breakdown, covering sampling, conversion, feature fetch, aggregation and the dense layers, for every method. If convert-then-tile matches us end to end, the idea is refuted.

Proposed Experiments

Decisive first check. Before building the sampler, we measure block density of the reordered full adjacency on Reddit, ogbn-products, Yelp, Flickr and ogbn-papers100M. If occupied 16×16 tiles are mostly padding on most graphs, the approach cannot pay off and we stop. We expect Reddit, which is dense with high clustering, to be favorable and Flickr to be unfavorable. This mirrors LABOR's weak gains on Flickr. For Yelp and Flickr no reported accuracy or speed results were found on Lacuna, so our runs of all baselines serve as the reference there.

Main comparison. Time-to-target-accuracy and final test accuracy on Reddit and ogbn-products against all baselines above, on one GPU, five seeds. We also report peak memory, unique vertices fetched per batch, and the per-phase time breakdown.

Variance check. Gradient variance versus full-batch gradients as a function of block budget. We also track accuracy against the unreweighted ablation, to test the claim that reweighting closes GNNSampler's accuracy gap.

Scale check. ogbn-papers100M, with features in host memory. This tests whether contiguous slab fetches reduce host-to-GPU traffic, compared directly with LABOR under the same loader.

The proposal succeeds if, on at least the high-clustering graphs, it beats rerun LABOR on time-to-accuracy while staying within noise of its test accuracy, and if the per-phase profile shows the gain is not reproducible by converting LABOR batches into tiles.