Graph neural networks (GNNs) that pass messages only between neighbors struggle to move information across long distances. Each node must squeeze everything it hears into one fixed-size vector, and this failure is called over-squashing. The remedies that work best on large graphs add long-range shortcuts. Some insert "hub" nodes that connect to every node in a cluster; others add extra edges chosen to widen the graph's bottlenecks. On a graph with millions of nodes, though, these models must be trained on mini-batches, and a hub with a thousand neighbors leaves two bad options. Pulling in all its neighbors explodes memory. Sampling a few of them makes the hub's message noisy at exactly the place the shortcut was supposed to carry signal.
A known fix for such sampling noise comes from variance-reduced optimization. Keep a stored copy of each node's past activation, and correct a tiny random sample of fresh neighbor values against those stored copies. This control-variate estimator stays unbiased, and its noise shrinks as training settles. The catch is memory: the stored table grows with nodes × layers × width, so it fails on the deep or wide models that long-range tasks need. This note proposes storing that table in heavily compressed form. Each node keeps a per-cluster low-rank code, possibly quantized, instead of its full activation. The design rests on one observation that the existing method does not exploit. A control variate stays exactly unbiased no matter how crude the stored reference is, as long as the exact average of those same references is added back. Compression therefore costs some variance reduction but introduces no bias, and memory and noise can be traded off with a single knob.
Core Claim
The closest existing work is Stochastic Training of Graph Convolutional Networks with Variance Reduction. It ports the control-variate idea from SAGA/SVRG-style optimizers to neighbor aggregation. Each node $v$ keeps a historical activation $\bar h_v$ at every layer, a sample of only $D=2$ neighbors is drawn, and the method converges to the full-batch solution regardless of $D$. That paper stores the table at full precision, an $O(|V| \cdot L \cdot A)$ cost for $|V|$ nodes, $L$ layers and width $A$. It is evaluated only on two-layer networks over homophilic graphs such as Reddit and PPI, and it never touches hub or shortcut edges. This mirrors the storage problem in the optimization literature, where SAGA's per-sample gradient table costs $O(nd)$ and SVRG removes it only by paying for periodic full passes (loopless SVRG removes the outer loop but still needs snapshot evaluations).
Our estimator replaces $\bar h_v$ with a decoded reference $g_v = U_{p(v)} c_v$. Here $p(v)$ is the graph cluster containing $v$ (from METIS partitioning), $U_{p}$ is an $A \times r$ basis shared by that cluster, and $c_v$ is an $r$-dimensional code stored per node, optionally in 8-bit precision. The aggregated message to node $u$ is
$$\tilde z_u = \sum_{v \in S_u} \frac{\hat A_{uv}}{p(v\mid u)}\big(h_v - g_v\big) + \sum_{v \in \mathcal N(u)} \hat A_{uv}\, g_v ,$$
where $S_u$ is the sampled neighbor set, $\hat A_{uv}$ the normalized edge weight, $p(v\mid u)$ the sampling probability, and $h_v$ the fresh activation. The expectation of $\tilde z_u$ equals the exact aggregate for any choice of $g_v$. Its variance scales with $\sum_v \|h_v - g_v\|^2/D$. That residual splits into a staleness part (the weights have moved since the code was written) and a reconstruction part (compression error). The prediction that follows is that compression is essentially free whenever reconstruction error stays below staleness, and that a sharp accuracy knee appears at the rank where it does not.
For a hub node, the second sum covers its whole cluster. We never recompute that sum. Instead we keep a running per-hub sum of codes, and whenever a member's code is rewritten we add the difference, exactly as SAGA maintains its gradient average. This makes the hub's exact reference mean cost $O(r)$ per update. Hub messages then come from a two-node sample plus an exact compressed mean.
Two features of the over-squashing literature suggest a per-cluster low-rank basis should fit well. The fractal-node design deliberately low-pass filters within clusters, which makes cluster members' activations similar. GradPCA also reports that network gradient representations concentrate in low-dimensional subspaces. Neither result has been tested on GNN activations, so whether the fit holds is itself one of the measurements.
Research Program
The over-squashing direction supplies the regime and the models; the storage direction supplies the mechanism. Three architectures serve as targets. The first is the hub-augmented model of Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs. It adds one "fractal node" per METIS partition, connects it to every member, and mixes the fractal nodes globally at the last layer. On ogbn-products it trains with plain GraphSAGE sampling, which leaves the hub sampling problem untreated. The second is a relational GNN, meaning one with separate weights for original and added edges, trained on graphs rewired by FoSR. FoSR adds edges to enlarge the spectral gap and was designed and tested in full-batch mode on small graphs. The third is a deeper plain message-passing network with 8–16 layers, used to stress the table's size across many layers.
For Greedy Total Resistance rewiring, which bounds node-to-node influence by effective resistance, we use only the theory, as a diagnostic. Its full-spectrum computation is not practical at the scale we target.
We will build the compressed table in four variants, so that the source of any gain can be identified: full precision, int8, per-cluster low rank, and low rank plus int8. We will add the running hub aggregates. We will also add separate control variates for original and shortcut edge types, because they carry different weight matrices in relational models.
Three analyses accompany the method. The first is a variance decomposition logged during training, which splits the residual into staleness and reconstruction terms per edge type. The second is a memory-variance frontier as rank $r$ and bit width vary. The third is a direct test of whether the shortcut edges still deliver signal under tiny samples. For this test we measure, on held-out node pairs, the Jacobian-influence quantity that the effective-resistance paper uses to define over-squashing, and compare it against the full-batch model where full batch fits.
The scale stakes are concrete. A full-precision table for ogbn-products (2,449,029 nodes) at width 256 over 8 layers takes about 20 GB in fp32. Rank-16 int8 codes take about 0.3 GB plus small per-cluster bases.
Baselines
The naive reference point is standard GraphSAGE neighbor sampling with no stored activations, applied to the same hub-augmented and rewired models. The fractal-node paper reports 83.11% test accuracy on ogbn-products for GraphSAGE plus fractal nodes and 78.29% for plain GraphSAGE. OGB reports 78.50% for GraphSAGE (with 94.09% training accuracy) and 79.08% for GraphSAINT. The 83.11% figure is the strongest reported number on this benchmark in the file and is the bar to beat. gLSTM reports 81.52% there, but gLSTM is a different architecture with $d\times d$ node states, and we include it only as context. We will re-run GraphSAGE plus fractal nodes ourselves under identical partitions, depth, width, epochs and hyperparameter search budget. We will report it at several sample sizes, because the comparison that matters is accuracy at matched GPU memory and wall-clock time, not at the authors' original sampling budget.
The strongest variance-reduction competitor is the full-precision control variate of Stochastic Training of Graph Convolutional Networks with Variance Reduction. That paper reports reaching its accuracy on Reddit with 2 neighbors per node, against 250 for GraphSAGE, and running 7× faster than neighbor and importance sampling. The file quotes no Reddit accuracy figure, so we will reproduce it. Where its table fits in memory (shallow models, Reddit, ogbn-arxiv), it bounds what compression can achieve. Matching it within noise at a fraction of the memory counts as success. Where it does not fit (deep models on ogbn-products), it fails by running out of memory, and the comparison falls back to GraphSAGE.
The key ablation is "compressed stale substitution." It uses the same compressed table but plugs $g_v$ in directly for unsampled neighbors, without the exact-mean correction, the way historical-embedding caches typically work. Both arms share the same memory, so any gap isolates the unbiasedness ingredient. A second ablation removes the running hub aggregates and applies the control variate only to original edges, which tests whether the hub treatment matters. We count the proposal as beating the field if, on ogbn-products with the fractal-node model, it meets or exceeds 83.11% using $D\le 4$ samples per node, with at least 4× less peak GPU memory than GraphSAGE sampling at its tuned sample size.
Why not just…?
Why not just use plain neighbor sampling with a larger sample? This is the default, and the variance-reduction paper shows its noise and bias do not vanish as training converges. It also needed 250 neighbors on Reddit to compete with 2. A fractal hub makes this worse, because the sample that keeps the hub's message accurate grows with partition size. The baseline sweep over sample sizes will show directly whether a large enough sample closes the gap at acceptable memory. If it does, our contribution shrinks to a memory saving, and we will say so.
Why not just store the full table in CPU memory or at reduced precision? This is a real threat for shallow models, and int8 storage is one of our own variants, not something to argue against. The question is whether quantization alone suffices or low rank adds something. The frontier experiment settles it: if int8 at full rank dominates every low-rank point, the per-cluster basis is unnecessary. Host-memory offloading does not remove the bandwidth cost of streaming 20 GB per epoch for deep models. We will report transfer volume alongside accuracy.
Why not just keep the model shallow and let the hubs or rewiring handle long-range information? This is plausible, and it is why our primary target is the fractal-node model rather than very deep networks. Hubs shorten paths but make sampling worse, and our method addresses exactly that. Depth is a secondary axis. If shallow hub models already saturate accuracy on ogbn-products, we will drop the deep-model claim and keep the hub-sampling claim.
Why not just skip the correction and use cached stale activations directly? That is cheaper by one term, but it is biased, and the bias grows with compression error. The substitution ablation measures the accuracy cost of that bias at equal memory.
Proposed Experiments
The main runs train GraphSAGE plus fractal nodes and FoSR-rewired relational GNNs on ogbn-products, ogbn-arxiv and Reddit, with ogbn-papers100M as a stretch test of the memory claim. We report test accuracy, peak GPU memory, time per epoch and time to target accuracy, across $D\in\{2,4,8\}$ and ranks $r\in\{4,8,16,32,64\}$ with and without int8, over five seeds.
The first decisive check is whether the logged residual variance predicts the accuracy knee in rank: accuracy should hold until reconstruction error exceeds staleness, then drop. The second is that the unbiased estimator beats compressed stale substitution at equal memory, with the gap widening as rank falls. The third is the influence test. On ogbn-arxiv, where full-batch training fits, we compare Jacobian influence across shortcut and hub paths between full-batch training, GraphSAGE at $D=2$, and our method at $D=2$. The claim requires our method to track full batch while plain sampling falls short.
To check the long-range story outside citation and product graphs, we also run the deep variant on the ECHO synthetic shortest-path task. There, graphs with diameters of 17–40 hops need deep networks; ECHO reports a GCN MAE of 2.102 against 0.121 for the GRIT graph transformer. These graphs are small, so this is not a memory test. It tests only whether compressed control variates with tiny samples preserve the accuracy of exact aggregation in deep models.
The proposal fails if any of three things happens: compression below full rank consistently loses accuracy before it saves meaningful memory, the substitution ablation matches the unbiased estimator, or tuned GraphSAGE plus fractal nodes matches us at equal memory.
References
- Stochastic Training of Graph Convolutional Networks with Variance Reduction
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
- GradPCA: Leveraging NTK Alignment for Reliable Out-of-Distribution Detection
- Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs
- FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
- Understanding Oversquashing in GNNs through the Lens of Effective Resistance
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity
- Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation