Bit-Sliced Control Variates for Memory-Light GNN Training

Training a graph neural network (GNN, a model that updates each node by averaging its neighbors' features layer after layer) on a large graph runs into neighbor explosion. A node's prediction at depth $L$ depends on roughly $d^L$ other nodes, where $d$ is the average degree, so even small mini-batches end up touching much of the graph. The cleanest known fix is the control-variate method of Stochastic Training of Graph Convolutional Networks with Variance Reduction (VR-GCN). It keeps a stored "historical" copy of every node's activation, samples as few as two neighbors per node, and corrects with the stored copies so that neighbor-sampling noise shrinks toward zero. The cost is a table holding every node's activation at every layer. On a graph with a hundred million nodes, that table no longer fits in GPU memory, and it can strain host memory as well.

This note argues that the table can be stored at 2–4 bits per value with little loss, and explains why. In a control-variate estimator the stored copy only serves as a reference value that is subtracted and then added back. Errors in that copy therefore raise variance but introduce no bias in the neighbor aggregation. Caches that substitute stored values for real ones, as in GAS-style methods, are different: there, compression error goes straight into the gradient as bias. If the stored activations are kept as packed binary bit-planes (a "bit-sliced" layout) and the graph is kept as a block bitmap, the expensive full-neighborhood sum over historical values becomes a bitwise AND-and-count kernel on the GPU. That is the same kind of kernel that Accelerating matrix-centric graph processing on GPUs through bit-level optimizations showed to be very fast, but only for unweighted graph analytics.

Core Claim

For a target node $u$ at layer $l$, VR-GCN estimates the neighbor average as

$$\tilde{g}_u = \frac{1}{|N(u)|}\sum_{v \in \hat{N}(u)} \frac{h_v - \bar{h}_v}{p(v)} + \frac{1}{|N(u)|}\sum_{v \in N(u)} \bar{h}_v .$$

Here $h_v$ is the current activation of neighbor $v$, $\bar{h}_v$ is its stored copy, $\hat{N}(u)$ is the small sampled neighbor set, $N(u)$ is the full neighbor set, and $p(v)$ is the probability of sampling $v$. Over the sampling of $\hat{N}(u)$, the expectation of this estimator equals the exact average of $h_v$ for any $\bar{h}$. Unbiasedness of the aggregation therefore holds even if the stored copy is a quantized version $\bar{h}_v = Q(h_v^{\text{old}})$. One condition is required: the same quantized values must appear in both sums.

The variance scales with the squared deviation $\lVert h_v - Q(h_v^{\text{old}})\rVert^2$. That deviation is at most the drift $\lVert h_v - h_v^{\text{old}}\rVert$ plus the quantization error $\epsilon_b$ at $b$ bits. This follows directly from the triangle inequality applied to the standard control-variate variance. Quantization therefore leaves a variance floor of order $\epsilon_b^2/k$, where $k$ is the number of sampled neighbors. It does not leave a bias floor.

The floor matters only if it is large compared with the noise that is already present from sampling which training nodes enter each mini-batch. VR-GCN never removes that node-sampling noise. The resulting prediction is concrete: there is a bit width $b$, plausibly 2–4, at which training with control variates matches full-precision VR-GCN, while a substitution cache quantized to the same $b$ visibly degrades.

One caveat must be stated plainly. Through multiple layers and nonlinearities, VR-GCN is only approximately unbiased even at full precision. The bias/variance asymmetry is therefore exact for a single aggregation and approximate end to end. The experiments test whether it survives in practice.

Research Program

The work has three parts.

The first part is the storage format. Each layer's activation table is stored as $b$ bit-planes with one scale per row. Symmetric graph normalization is split into two steps: the column factor $D^{-1/2}$ is folded into the values before quantization, and the row factor is applied after aggregation. With this split the adjacency stays strictly binary and can be held in the two-level bit-block format (B2SR) of Accelerating matrix-centric graph processing on GPUs through bit-level optimizations. That paper names the extension to multi-bit values as unaddressed. Bit-slicing is our route to that extension: a binary matrix times a $b$-bit matrix becomes $b$ binary products, recombined with shifts. The design also borrows two ideas from Dual-side Sparse Tensor Core, which computes packed offsets with popcount (counting set bits) and handles changing sparsity patterns with bitmaps. We apply those ideas to training-time aggregation; that paper applied them to inference.

The second part is updating the table. Whenever a node's real activation is computed in a mini-batch, its row is requantized and written back. The per-node full-neighborhood sum over historical values is recomputed with the bit kernel, so the two sums in the estimator always use identical values.

The third part is a variance-driven precision controller. During training we measure the neighbor-sampling variance of $\tilde{g}$ on a probe set and compare it with the node-sampling variance of the mini-batch gradient. A bit-plane is added when the first exceeds a fixed fraction of the second, and dropped otherwise. This brings in the stochastic-gradient-variance perspective: precision is spent only where it changes the variance that actually limits optimization. The analogy is subsampled variance reduction, as in Less than a Single Pass: Stochastically Controlled Stochastic Gradient. That work shows that a cheap, inexact reference point is enough when its error is small relative to the remaining stochastic noise. Our reference is cheap in bits rather than in batch size.

The memory arithmetic is simple. On ogbn-papers100M (over 111 million nodes per Open Graph Benchmark), a two-layer, 128-dimensional float32 history table takes on the order of 100 GB. At 2 bits it shrinks 16×, to a size that fits on a single accelerator.

Baselines

The naive reference is GraphSAGE-style fixed-fanout neighbor sampling with no stored activations. Open Graph Benchmark reports 78.50% test accuracy for GraphSAGE on ogbn-products and 79.08% for mini-batch GraphSAINT. These are the absolute accuracy anchors on that dataset.

The most direct competitor is full-precision VR-GCN. Stochastic Training of Graph Convolutional Networks with Variance Reduction reports it as 7× faster than neighbor and importance sampling on Reddit while using only 2 neighbors per node; the file gives no per-dataset accuracy. Our method must match its accuracy and convergence curve within noise while cutting history memory by at least 8×. It is the right comparison because it is exactly our estimator without compression.

The strongest staleness-aware substitution cache is GAS with REST from Haste Makes Waste. That paper reports gains over GAS of 3.6% on ogbn-products and 2.7% on ogbn-papers100M, and convergence in about 20 epochs against 75 on ogbn-products. No absolute REST accuracy was found on Lacuna. We will rerun it, and also S3 from Staleness-based Subgraph Sampling, in our own harness.

Fairness rules apply to every method. All methods use the same model width and depth. All get the same hyperparameter search budget, roughly twenty configurations each. All are measured on the same GPU and host-memory caps and report wall-clock to a fixed validation accuracy. Beating the cache baselines means matching or exceeding REST's accuracy within the memory budget at which REST must keep its cache in host memory, with lower peak memory and no slower time-to-accuracy.

The key ablation applies the identical $b$-bit quantizer to the GAS/REST cache, where stored values substitute for real ones. This isolates the claim that compression is cheap specifically for control variates.

A second ablation replaces bit-slicing with the "obvious" design for this intersection: thresholding small deltas $h_v - \bar{h}_v$ to zero and storing the survivors with occupancy bitmaps. This tests whether exploiting delta sparsity beats exploiting low precision.

Why not just…?

Why not just quantize the cache to int8 or fp16 with ordinary dense kernels? This is the most serious threat. It is close to our method, minus bit-slicing and the bit kernel. We will run dense int8 and fp16 control-variate variants directly. If 8 bits already saturates memory savings and dense kernels match the bit kernel's time, the systems contribution shrinks to the bias/variance finding plus the precision controller. The bit layout earns its place only if accuracy holds at $b \le 4$, where dense integer types give out, and the full-neighborhood historical sum runs faster than with dense kernels. Bit-GraphBLAS reports up to 40× SpMV speedups over cuSPARSE on binary matrices, which makes this plausible but unproven for the multi-bit case.

Why not just quantize a GAS/REST cache, since those methods are more accurate? Our analysis predicts that quantizing a substitution cache adds bias that later refresh passes cannot cancel. Quantizing a control-variate cache only adds variance. The matched-bit ablation tests this directly, so it is the decisive experiment rather than a side note.

Why not just use pre-propagation models and skip sampling entirely? Revisiting Pre-Propagation GNNs reports an 11% gap to message-passing models on roman-empire for standard pre-propagation, and multi-hop feature banks still grow with the number of hops. We include roman-empire and pokec to check whether compressed message-passing training retains that advantage.

Why not just sample more neighbors? Fanout cost grows exponentially with depth. VR-GCN already reaches its results with 2 neighbors where GraphSAGE used 250 on Reddit, so larger fanouts fix the wrong bottleneck.

Proposed Experiments

The benchmarks are Reddit, ogbn-products, and ogbn-papers100M for scale, plus roman-empire and pokec for heterophily. We measure test accuracy, peak GPU and host memory, epoch time, time-to-accuracy, and two estimator-level quantities. The first is the empirical variance of $\tilde{g}$. The second is the cosine and norm error of the mini-batch gradient against an exact full-neighborhood gradient, computed on a fixed subset of ogbn-products nodes.

Three results decide the question. First, as $b$ sweeps from 1 to 8, the control-variate variant's accuracy should be flat down to some $b^*$ of 2–4, while the substitution-cache variant degrades earlier. If both degrade together, the central claim fails. Second, the measured variance floor should scale like $\epsilon_b^2$ and should fall below node-sampling variance at $b^*$. If it does not, the controller has no basis. Third, on ogbn-papers100M the method should keep the entire history on one GPU and reach REST-level accuracy at lower wall-clock.

At the kernel level, we benchmark the bit-sliced historical aggregation against cuSPARSE SpMM on the same matrices. This shows whether the B2SR-style speedups survive the move from binary values to multi-bit values.