Graph neural networks (GNNs) build each node's representation by averaging over its neighbors, then its neighbors' neighbors, and so on. A few layers deep, a single training node can depend on a large fraction of the graph. This is the "neighbor explosion" problem. One of the most effective fixes stores a table of each node's most recent intermediate representation and uses it as a control variate, meaning a cheap stored estimate whose known average lets you correct a noisy sample. With it, a network can train on two sampled neighbors per node and still converge Stochastic Training of Graph Convolutional Networks with Variance Reduction. Such tables are large and live naturally in the shared RAM of a many-core CPU. On a many-core CPU, the fastest way to train is lock-free: threads read and write shared memory with no waiting and no locks. Nobody has run control-variate GNN training this way. We argue that doing so is not a routine engineering port, because two assumptions that each method relies on break once they meet.
The first break concerns the stored table. Lock-free threads read stored vectors while other threads are rewriting them. The control-variate correction is then computed from two versions of the table that never coexisted, and its "variance goes to zero" property can turn into a bias that does not go away. The second break concerns delays. Threads handling high-degree "hub" nodes take longer, so their updates arrive staler. Modern asynchronous theory assumes delays are independent of gradient noise Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays, and on graphs that assumption fails by construction. Our central claim is that the leftover bias is predictable. It scales with how stale a node's stored entry is, multiplied by the local curvature of the softmax cross-entropy loss at the nodes that read it. Because cross-entropy, unlike squared loss, flattens on confidently classified nodes, staleness hurts mainly on hubs that feed low-margin nodes. A scheduler that refreshes table entries in order of degree times curvature, combined with batches balanced by edge count, should recover synchronous accuracy while scaling across cores.
Core Claim
Write $\bar h_u$ for the stored representation of node $u$ and $h_u$ for the freshly computed one. The estimator of Stochastic Training of Graph Convolutional Networks with Variance Reduction samples $D$ neighbors $\mathcal S_v$ of node $v$, which has neighbor set $\mathcal N(v)$, and forms
$$g_v = \frac{|\mathcal N(v)|}{D}\sum_{u\in\mathcal S_v}(h_u-\bar h_u) + \sum_{u\in\mathcal N(v)}\bar h_u .$$
This estimate is unbiased only if the same $\bar h$ appears in both terms. In practice the second term is a precomputed per-node aggregate. Under lock-free writes, that aggregate and the individual entries drift apart. The mismatch is a perturbation $\delta_v$ in node $v$'s logits that sampling does not average out.
For softmax cross-entropy with predicted probabilities $p_v$, the perturbation passes into the gradient through the loss Hessian $\mathrm{diag}(p_v)-p_vp_v^\top$, whose norm is at most $1-\max_k p_{v,k}$ up to a constant. Generalized self-concordance, the property that logistic and softmax losses share in Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization, bounds how fast that Hessian changes, by a factor of $\exp(\|\delta_v\|)$. This makes the first-order picture valid for moderate staleness. The resulting prediction is a bias floor of roughly
$$\mathrm{bias} \;\approx\; \sum_{v}\big(1-\max_k p_{v,k}\big)\,\Big\|\sum_{u\in\mathcal N(v)} s_u\Big\| ,$$
where $s_u$ is the staleness error of $u$'s stored entry. Under squared loss the Hessian is constant, so no such attenuation occurs. That contrast gives us a clean control experiment.
Hub entries appear in many sums, and under lock-free execution they are also the slowest to be rewritten. The floor is therefore dominated by hubs adjacent to ambiguous nodes. This is the loss-specificity direction acting as an analytical tool: the shape of the loss tells us where staleness matters.
Research Program
We will build a shared-memory CPU trainer. Worker threads sample target nodes, compute control-variate gradients, apply them lock-free to the weights with coordinate-wise atomic writes, and write fresh $h_u$ back to the table. Background threads perform forward-only refreshes, which is the decoupling idea from Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks, run here without epoch barriers. The design has three ingredients.
The first is snapshot-consistent correction. A worker records a per-row version counter when it reads $\bar h_u$. Instead of trusting the precomputed aggregate, it corrects the aggregate by the delta between the version it used and the version folded into the aggregate. Matching the two terms this way makes the bias floor depend only on staleness, not on torn reads.
The second is curvature-and-degree refresh priority. Refresh threads choose node $u$ with probability proportional to its degree times the summed $(1-\max p)$ of its out-neighbors. This targets the terms that dominate the predicted floor.
The third is edge-balanced batching. Batches are built to have roughly equal edge counts, so computation time, and therefore delay, stops tracking degree. This restores the independence assumption that delay-adaptive step sizes $\gamma\propto 1/\tau$ need Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays. Without balancing, those step sizes would systematically down-weight hub-heavy updates.
On the analysis side, we will extend the "after read" labeling of ASAGA: Asynchronous Parallel SAGA to multi-layer tables. ASAGA labels each update by the moment a thread finishes reading shared parameters, and it handles flat finite sums whose stored items are single coordinates. In our setting the stored items are vectors read across layers. The theorem we aim for is convergence to a neighborhood whose radius matches the bias expression above. Our working hypothesis is that the radius goes to zero as the rate of refresh relative to update grows.
The roles of prior work are as follows. ASAGA and the virtual-iterate analysis supply the proof technique. Their independence and finite-sum assumptions are exactly what graphs violate. REST supplies the forward-only refresh and its result that staleness bounds gradient error, which motivates the design. Its synchronous phases are what we remove. FastGCN FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling shows that hubs dominate variance, which motivates degree weighting. We apply degree weighting to refresh scheduling rather than to sampling.
Baselines
The naive reference point is the original control-variate trainer of Stochastic Training of Graph Convolutional Networks with Variance Reduction, run in two ways. One run uses a single thread. The other parallelizes within each mini-batch on the same cores and synchronizes every step. These runs fix the accuracy target, and the synchronous one fixes the wall-clock bar we must beat. On Reddit, the strongest reported accuracy in the file is FastGCN's Micro F1 of 0.937, reported in FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. Beating the baseline there means matching that F1 within run-to-run noise at a lower time-to-accuracy.
The strongest existing method for stale tables is REST applied to GAS-style historical embeddings Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks. It reports +3.6% over GAS on ogbn-products and a cut in MAG240M training time from about 42,000 to about 25,000 seconds. The file gives no absolute ogbn-products accuracy for REST, so no reported result was found on Lacuna for REST's absolute accuracy. We will re-run it ourselves on the same machine, with the same model width and depth and the same hyperparameter search budget. The mini-batch reference on ogbn-products is GraphSAINT at 79.08% test accuracy, reported in Open Graph Benchmark: Datasets for Machine Learning on Graphs. Our method beats these baselines if it reaches REST's accuracy, and at least GraphSAINT's 79.08%, in less wall-clock time at 16 or more cores.
The lock-free reference is Hogwild-style asynchronous SGD with plain neighbor sampling at a tuned fan-out. It tests whether the control variate is worth its memory once threads run free.
Ablations isolate each ingredient: we drop version-matched correction, replace priority refresh with uniform refresh, and replace edge-balanced batches with random batches. A loss-swap ablation trains the same model with squared loss on one-hot targets. If the curvature mechanism is real, priority refresh should give no gain over degree-only refresh under squared loss.
Why not just…?
Why not just run REST synchronously on all cores? This is the most serious threat. If the per-batch work is large enough, barrier overhead may be small. The deciding experiment is a scaling curve from 1 to 64 cores, run on uniform hardware and on hardware with injected stragglers. Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays argues the asynchronous advantage grows with the ratio of slowest to average worker time. On graphs, hub-heavy batches create this imbalance naturally. If synchronous REST matches us on uniform hardware and with edge-balanced batches, we will report that and narrow our claim to heterogeneous workloads.
Why not just put a lock or a sequence lock on each table row? Per-row locking prevents torn reads cheaply. It does not prevent staleness, and it does not decorrelate delay from degree. We include a seqlock variant. If it matches version-matched correction at equal throughput, that ingredient is unnecessary and the contribution reduces to scheduling and batching.
Why not just use pre-propagation models, which have no neighbor dependencies and parallelize trivially? On homophilic graphs, where neighbors tend to share labels, this may well win. On heterophilic graphs, plain pre-propagation trailed message passing by 11% on roman-empire, and closing that gap required re-propagating hidden states across up to seven synchronized stages Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation. We will run SIGN+/HRP on roman-empire and pokec under the same core budget. No reported absolute accuracy was found on Lacuna for roman-empire. We restrict our claim to graphs where our method beats this baseline.
Why not just use asynchronous neighbor sampling without a table? ASAGA beat Hogwild in wall-clock time on 10 cores precisely because removing variance avoids stalling near the optimum ASAGA: Asynchronous Parallel SAGA. On Reddit, the control-variate method needed 2 neighbors where GraphSAGE needed 250 Stochastic Training of Graph Convolutional Networks with Variance Reduction. The Hogwild baseline tests whether this advantage survives once threads run without coordination.
Proposed Experiments
We will run on Reddit, ogbn-arxiv and ogbn-products, which fit easily in RAM. Then we will run ogbn-papers100M with a two-layer table stored in reduced precision. This is a stretch goal, since the $O(VLA)$ table, which grows with nodes times layers times feature width, is roughly a hundred gigabytes. We add roman-empire and pokec for heterophily. Metrics are test accuracy (Micro F1 on Reddit), wall-clock time-to-target-accuracy, speedup per core up to 64 cores, and directly measured gradient bias. We measure bias against a periodic exact full-graph gradient on the smaller graphs.
The first decisive check is quantitative. The measured bias floor should track the predicted degree-times-curvature expression across staleness levels, and under squared loss it should follow degree alone. The second check is that priority refresh lowers the floor more than uniform refresh at equal refresh compute, under cross-entropy only. The third check is that edge-balanced batching removes the correlation between delay and degree, measured per update, and that this restores the benefit of $1/\tau$ step sizes. The fourth check is speedup. Speedups should stay near-linear past the roughly 20-core point where ASAGA: Asynchronous Parallel SAGA saturated memory bandwidth, or we should show that table traffic is what limits them.
If the first check fails and the floor does not follow curvature, the loss-specific part of the claim is wrong. The work would then reduce to an asynchronous REST, and we will say so.
References
- Stochastic Training of Graph Convolutional Networks with Variance Reduction
- Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays
- Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization
- Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
- ASAGA: Asynchronous Parallel SAGA
- FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation