Many graph neural networks spend most of their time doing something simple. They repeatedly average each node's feature vector with its neighbors' vectors, often ten or more times per forward pass in diffusion-style models such as personalized-PageRank propagation. On a GPU this step is limited by memory bandwidth, not by arithmetic. Every propagation step streams the full feature matrix out of off-chip memory and writes it back, and the arithmetic per byte is tiny. Existing optimizations make each step cheaper, through fused kernels, segment reductions, reordered operators, or quantized features. All of them still reread the whole feature matrix once per step.
This note proposes to fuse many propagation steps into one pass over memory. The graph is cut into regions using its small separators, meaning small sets of vertices whose removal disconnects the graph. Each region is loaded on-chip together with the neighbors it needs from just outside its border (its halo), and all $s$ steps are run locally before the region is written back. Separators bound how large the halo can get, so the structural property studied in graph algorithms is exactly what decides whether this trade pays off. The project also predicts where it fails: power-law social graphs with no small separators. The goal is a method together with a measurable theory of its operating regime, not a universal speedup.
Core Claim
For $K$ steps of linear propagation $H \leftarrow \hat{A} H$ on a graph with small, recursively available separators, the method fuses $s$ steps per pass. Here $\hat{A}$ is the normalized adjacency matrix and $H$ is the $n \times d$ feature matrix. Off-chip feature traffic drops from roughly $K$ full reads and writes of $H$ to about $K/s$ of them, inflated by the halo fraction. Results are exact up to floating-point summation order. Concretely, if the graph is split into regions $R$, and $N_s(R)$ denotes the vertices within $s$ hops of $R$, then feature traffic per $s$ fused steps is
$$ B_{\text{fused}} \approx \sum_{R} |N_s(R)| \cdot d \cdot b \quad\text{versus}\quad B_{\text{layerwise}} \approx s \cdot n \cdot d \cdot b , $$
where $b$ is bytes per feature entry. The expected gain is $s / (1+\eta_s)$, where $\eta_s = \sum_R |N_s(R) \setminus R| / n$ is the halo fraction. In graphs with bounded growth and separator size near $\sqrt{|R|}$, such as road networks, spatial cutoff graphs and meshes, the halo grows roughly like $s$ times the region boundary, so $\eta_s$ stays small for on-chip-sized regions. In expander-like graphs, $N_s(R)$ swallows most of the graph within two or three hops, and the gain vanishes. The claim is that $\eta_s$ can be computed cheaply before running and predicts measured DRAM traffic and speedup. That turns a graph-structure quantity into a hardware decision rule: whether to fuse at all, and what $s$ and region size to pick.
The idea comes from communication-avoiding methods in numerical linear algebra, which compute matrix powers in blocks. It is new in two respects relative to the papers below. It targets GNN propagation, and it uses the separator hierarchy itself, rather than a generic tiling, as the object that sets on-chip tile boundaries.
Relation to Prior Work
Three systems papers fuse or reorder GNN work within a single layer.
- Understanding GNN Computational Graph fuses scatter, edge-apply and gather into one kernel and reports a 6.89× memory-IO reduction.
- FlashSchNet fuses molecular message passing into on-chip memory and replaces atomic scatter-add with compressed-sparse-row segment reductions.
- Cached Operator Reordering chooses between $\hat{A}(X\Theta)$ and $(\hat{A}X)\Theta$ by feature width.
These papers supply our per-step kernel design. All three still round-trip the feature matrix through off-chip memory at every layer, and that per-layer round trip is what we remove.
Two hardware papers motivate the problem from the memory side. Piccolo shows that conventional graph tiling wastes bandwidth through repeated topology loads and the mismatch between 8-byte updates and 64-byte bursts. It fixes this with in-memory scatter-gather. ReGraph shows that splitting partitions by vertex degree into dense and sparse sets helps saturate HBM channels on FPGAs. We keep commodity GPUs and use a deeper structural invariant than degree. Unlike Piccolo, we do not need new DRAM logic.
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth supplies the structural motivation in two ways. It organizes computation along an elimination tree, which is a separator hierarchy, and it reports that real Netlib constraint matrices have treewidth between $n^{1/2}$ and $n^{3/4}$. That supports the view that moderate separators are common in structured instances. Its analysis treats memory accesses as uniform cost, and we measure the bytes instead.
Can Tensor Cores Benefit Memory-Bound Kernels? (No!) constrains the design. Its roofline analysis shows that adding arithmetic hardware cannot rescue sparse kernels that are memory-bound. We therefore attack bytes moved, not FLOPs, and we accept redundant halo arithmetic as cheap.
BiFeat cuts bytes per feature by quantization. It is orthogonal to cutting reads per step, and we test the two together. SHAKE-GNN reduces edge work by coarsening the graph. That changes the model being computed, whereas our method computes the same function exactly.
Research Program
The first component is an offline planner. It computes a nested-dissection separator tree with a standard partitioner and cuts the tree at two levels: regions sized to the L2 cache, and sub-regions sized to per-processor shared memory. For each candidate depth $s$ and region size, it computes the halo fraction $\eta_s$ exactly by multi-source breadth-first search. The planner's cost is reported and must be amortized. Training reuses one plan for every epoch, and inference reuses one plan for every query on a fixed graph.
The second component is a GPU kernel family. Each thread block loads a region's halo features and local sparse adjacency on-chip, runs $s$ propagation steps with segment reductions (no atomic operations), and writes back only the region interior. On each pass the halo shrinks inward by one hop per step. Both forward and backward passes are supported. For linear propagation the backward pass is the same operator applied with $\hat{A}^\top$, so the same plan serves both.
The primary targets are three diffusion-style computations:
- APPNP-style personalized-PageRank propagation during training, with $K = 10$ and the propagation rerun every iteration on new MLP outputs;
- label propagation;
- polynomial spectral filters.
A secondary target is full-graph inference of GCN-style models with nonlinear layers. There the per-layer weights are small enough to stay on-chip and are applied inside the fused tile.
The analysis question is whether the traffic model above, evaluated with measured $\eta_s$, predicts the DRAM bytes and runtime recorded by the profiler on each graph family. Specifically, we ask whether $\eta_s$ separates graphs where fusion helps from graphs where it hurts, better than simple statistics such as average degree or degree skew.
Baselines
The naive reference point is layer-by-layer propagation in PyTorch Geometric with CSR sparse-dense multiplication, on the original vertex order, in fp32 and fp16. It is the default most practitioners run and anchors absolute numbers.
The strongest straightforward competitor is layer-by-layer cuSPARSE CSR multiplication after a locality-improving reordering. We include both reverse Cuthill–McKee and the same nested-dissection ordering our planner uses. This is the most dangerous baseline because reordering alone recovers much of the cache locality that tiling provides, and it gives the competitor our ordering for free.
The strongest published method is per-layer fused execution in the style of Understanding GNN Computational Graph and Cached Operator Reordering. The file reports up to 2.75× end-to-end speedup over DGL and a 6.89× IO reduction for the former, and up to 2.43× over PyTorch Geometric for GCN for the latter. Those numbers are on Cora, Citeseer, PubMed, Flickr and Reddit-scale GCN and GAT. No reported result was found on Lacuna for APPNP-style multi-step propagation with either method, so we will reimplement the per-layer fused kernel with our own segment-reduction code. That way the only difference between the baseline and our method is cross-step fusion.
All methods use the same GPUs, the same feature precision and the same orderings where applicable. Each gets an equal tuning budget over block size and, for ours, over $s$ and region size. Correctness is checked to within fp tolerance against the naive version.
Two ablations isolate the key ingredients. The first runs our kernel with $s = 1$, so the separator tiles are kept but no steps are fused; this isolates the fusion. The second runs our kernel at the same $s$ with regions of equal size grown by breadth-first search from random seeds instead of separator-tree regions; this isolates the role of structure.
Our method beats the field if it cuts measured DRAM bytes and wall-clock time of the propagation stage relative to the reordered, per-layer fused baseline on the small-separator family. The minimum target is 1.5× at $K = 10$. This threshold is our own target, not a reported figure. We also require that the planner's $\eta_s$ correctly predicts which graphs lose.
Why not just…?
Why not just reorder the vertices and keep layer-by-layer kernels? Reordering improves the reuse of gathered neighbor rows within one step. It cannot avoid streaming the whole $n \times d$ matrix once per step once that matrix exceeds L2. For ogbn-products, with roughly 2.4 million nodes and 100-dimensional features, the matrix is about a gigabyte in fp32 against tens of megabytes of L2. This is a real threat on small graphs whose features fit in L2, where we expect no gain. The $s = 1$ ablation, which uses identical orderings, settles how much of any win comes from reordering versus fusion.
Why not just quantize the features? BiFeat shows that quantization cuts PCIe and memory volume sharply, with compression ratios above 30× via vector quantization, but vector quantization needs up to a day of preprocessing on MAG240M. The paper's argument is that neighbor averaging cancels quantization noise. Fused multi-step propagation keeps intermediate states on-chip, so it cannot hurt that argument. Quantization shrinks bytes per read, and fusion shrinks the number of reads, so the effects should multiply. We run scalar quantization with and without fusion to test this. If fusion adds nothing on top of quantization, we will report that.
Why not just precompute $\hat{A}^K X$ once, as simplified decoupled models do? That works only when propagation is applied to fixed input features. It is not available for APPNP-style models, which propagate learned MLP outputs every iteration. It is also unavailable for label propagation on changing labels and for backward passes. Our evaluation is restricted to these repeated-propagation settings, and we state that for precomputable pipelines the one-off cost makes our method unnecessary.
Why not just use in-memory hardware like Piccolo? Piccolo reports a 43.2% geometric-mean reduction in memory transactions, but it requires modified DRAM and caches. Our method runs on existing GPUs. In principle the two are complementary, but we cannot run Piccolo, so we compare only on DRAM-traffic accounting and do not claim superiority.
Proposed Experiments
The decisive controlled experiment uses Watts–Strogatz graphs, the family used in the Piccolo evaluation. We sweep the rewiring probability, which moves the graph continuously from a ring lattice with tiny separators toward a random graph with none. We plot measured $\eta_s$, profiler DRAM bytes, and speedup over the reordered per-layer fused baseline. The hypothesis predicts a crossover where $\eta_s$ approaches $s - 1$ and speedup falls to or below 1. If speedup tracks average degree but not $\eta_s$, the structural claim is wrong.
The real graphs fall into three groups:
- Small-separator family: OpenStreetMap road extracts at increasing scale (PIM-FW used an 8,192-node one), and spatial cutoff graphs from the fast-folding protein systems used by FlashSchNet, batched to large sizes.
- Intermediate case: ogbn-products from the Open Graph Benchmark.
- Expected failure cases: ogbn-papers100M and the Twitter, Friendster and Kronecker graphs.
For APPNP on ogbn-products, task accuracy must match the unfused model within run-to-run noise. The OGB paper's GraphSAINT figure of 79.08% test accuracy serves as a sanity reference for the dataset, not as a comparable APPNP number.
Metrics are propagation-stage wall-clock time, end-to-end epoch time, profiler-measured DRAM read and write bytes, achieved bandwidth as a fraction of peak, planner time and its amortization over epochs, and the correlation between predicted and measured traffic across all graphs. We sweep $K$ over 2, 5, 10 and 20, $s$ from 1 to $K$, and feature width over 32, 64, 128 and 256. The width sweep tests whether wider features shrink the feasible region size enough to erase the gain. The result counts as a success if it shows two things: separator-tiled fusion clearly beats the strongest per-layer baseline where $\eta_s$ is small, and the cheap offline estimate of $\eta_s$ tells a practitioner in advance whether to use it.
References
- Understanding GNN Computational Graph: A Coordinated Computation, IO, and Memory Perspective
- $\texttt{FlashSchNet}$: Fast and Accurate Coarse-Grained Neural Network Molecular Dynamics
- Cached Operator Reordering: A Unified View for Fast GNN Training
- Piccolo: Large-Scale Graph Processing with Fine-Grained in-Memory Scatter-Gather
- ReGraph: Scaling Graph Processing on HBM-enabled FPGAs with Heterogeneous Pipelines
- A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
- Can Tensor Cores Benefit Memory-Bound Kernels? (NO!)
- BiFeat: Supercharge GNN Training via Graph Feature Quantization
- SHAKE-GNN: Scalable Hierarchical Kirchhoff-Forest Graph Neural Network
- Open Graph Benchmark: Datasets for Machine Learning on Graphs