Graph neural networks (GNNs) compute each node's representation by repeatedly averaging over its neighbors. Stack many of these averaging layers and two things go wrong. Node representations blur into one another, which is called over-smoothing. A recent analysis also shows that the training gradients blur in the same way: the error signal sent back to each layer becomes nearly identical for every node, and the deep network stalls at a high-loss point (Backward Oversmoothing). That analysis assumes exact, full-graph gradients. Large graphs are almost never trained that way. They are trained by sampling a few neighbors per node, and the resulting noise is exactly what variance-reduction methods such as VRGCN and MVS-GNN try to remove. If exact gradients are what trap deep GNNs, then removing sampling noise may push training toward the trap.
This note proposes to test that directly. The sampling noise is different for each node and follows the graph's structure. Those are the properties of the component that backward over-smoothing strips out of the gradient. We build an estimator that turns sampling variance up or down while keeping the expected computation and the per-step compute fixed. With it we measure whether this structured noise helps deep GNNs escape stalled training and whether noise of the same size without graph structure does the same. We then carry the answer into dynamic graphs, where cached node states go stale as edges arrive. That staleness adds a third error source, and it is biased rather than zero-mean.
Core Claim
Our hypothesis is that, at depths where backward over-smoothing appears (roughly 8 to 32 layers), zero-mean neighbor-sampling noise does useful work. It re-injects variation across nodes into the backward signal, and deep models trained with a moderate amount of it reach lower training loss and higher backward-gradient rank than models trained on exact gradients. Parameter-space noise of matched size should not do this, because it perturbs weights, which are shared by every node, rather than individual nodes. On dynamic graphs we expect the opposite for staleness: stale caches shift the expected update, so they should hurt even where zero-mean noise helps. The practical consequence would be a streaming training rule: refresh caches enough to remove the bias from staleness, but deliberately keep sampling variance above zero. The claim is falsified if matched isotropic noise gives the same benefit, if the benefit vanishes once residual connections are added, or if variance never helps at any depth.
The Variance Dial
We reuse the control-variate machinery of VRGCN. That method keeps a cached history $\bar h_u$ of each node's activation, samples $D$ neighbors, and corrects the sampled estimate against the cached average. VRGCN always applies the full correction. We add a coefficient $\beta \in [0,1]$ that scales it. For node $v$ with neighbor set $N(v)$, sampled subset $S_v$ of size $D$, and edge weights $a_{vu}$, the aggregated input to the next layer is estimated as
$$\hat z_v = \frac{|N(v)|}{D}\sum_{u \in S_v} a_{vu}\,(h_u - \beta \bar h_u) \;+\; \beta \sum_{u \in N(v)} a_{vu}\,\bar h_u .$$
This estimate is unbiased for the exact aggregation $\sum_{u\in N(v)} a_{vu} h_u$ at every value of $\beta$. Setting $\beta=0$ gives plain neighbor sampling. Setting $\beta=1$ gives VRGCN, whose variance tends toward zero as training converges. The cost is the same at every $\beta$ because the cached aggregate is maintained either way. Varying $\beta$ therefore changes the variance while holding the per-layer expectation and the compute fixed. The estimate is not exactly unbiased once nonlinear layers are composed. We will measure that residual bias against full-batch forward passes and report it.
To detect backward over-smoothing we record the gradient matrix $G^{(l)} = \partial \mathcal{L}/\partial H^{(l)}$ at each layer $l$, where $\mathcal{L}$ is the training loss and $H^{(l)}$ is the node-by-feature activation matrix. We compute its effective rank, an entropy-based count of how many directions carry signal, following Are we measuring oversmoothing correctly?. That paper showed effective rank tracks accuracy collapse (average Pearson correlation 0.91 with test accuracy) where Dirichlet energy fails. It applied the measure only to forward features in full-batch models, so applying it to gradients during sampled training is our extension. Backward over-smoothing predicts that the effective rank of $G^{(l)}$ falls toward 1 in the early layers. Our hypothesis predicts that this rank stays higher at intermediate $\beta$.
Research Program
Phase one (static graphs). We train depth sweeps of 2, 4, 8, 16 and 32 layers with plain GCN and GCN with residual connections. We use Cora, Citeseer, PubMed and Chameleon, which the backward-over-smoothing paper also uses, together with Coauthor CS and Reddit. We sweep $\beta$ and $D$ across a grid and run several seeds per configuration. For each run we log training loss, test accuracy, forward and backward effective rank per layer, and the variance of the sampled gradient. The central outcome is a map of which $\beta$ minimizes final training loss at each depth. The hypothesis predicts that this optimal $\beta$ drops below 1 as depth grows.
Phase two (dynamic graphs). We replay TGB temporal graphs as snapshot streams: tgbn-trade, tgbn-genre and tgbn-reddit for node affinity prediction (TGB). A deep GCN is trained with caches carried from one snapshot to the next. Here $\beta$ controls zero-mean variance, and a separate refresh policy controls staleness bias. We compare three refresh policies: full refresh at every snapshot, refresh only for nodes within $L$ hops of changed edges ($L$ being the network depth), and no refresh. We record staleness error directly as $\|\bar h - h_{\text{exact}}\|$, so bias and variance can be separated. This regime is where the open problem of staleness in the research file actually arises. MVS-GNN states that it assumes static graphs, and A-DGN names dynamic topologies as an open problem (A-DGN).
Baselines
The naive reference points are full-batch training with exact gradients, which is Keriven's setting, and plain neighbor sampling at $\beta=0$ with no history. On the dynamic tasks the naive reference is the Moving Average heuristic. TGB reports it at 0.559 NDCG@10 on tgbn-reddit, against 0.315 for TGN (TGB). No reported result was found on Lacuna for tgbn-trade or tgbn-genre. We do not expect a deep GCN to beat Moving Average. That comparison is there to calibrate performance, not to decide the hypothesis.
The strongest competitor on the variance question is full variance reduction at $\beta=1$. That means VRGCN, and it can be combined with the importance-sampling scheme of MVS-GNN, which samples nodes in proportion to their gradient norms. MVS-GNN reports 0.859 Micro-F1 on PPI against 0.781 for GraphSAGE (MVS-GNN). VRGCN reports a 7x speedup on Reddit with 2 neighbors per node (VRGCN). For depth robustness the strongest architecture is A-DGN. It reports a log10 MSE of -3.40 on single-source shortest paths against -1.13 for GCNII, and it holds accuracy at 30 layers on Coauthor CS, where GCN and GAT lose 24 to 78 percent (A-DGN). No reported result was found on Lacuna for raw deep-GCN accuracy on Cora or Citeseer, so we will produce those numbers ourselves.
Every method gets the same data splits, the same number of gradient steps, the same count of sampled neighbors, and the same tuning budget, with learning rate and weight decay selected on validation separately for each $\beta$. Two ablations isolate the key ingredient, which is noise that differs per node and follows the graph. The first adds isotropic Gaussian noise to the weight gradients at the magnitude measured at the best $\beta$, which removes both graph structure and node specificity. The second takes the sampling noise and randomly permutes it across nodes, keeping each node's noise magnitude but breaking its link to the graph. We count the proposal as beating the competitors if, at 16 layers or deeper, intermediate $\beta$ lowers training loss and raises test accuracy over both $\beta=1$ and full-batch training beyond seed variance, while both ablations fail to recover the gain.
Why not just…?
Why not just add residual connections? This is the most serious threat, because Keriven notes that skip connections already ease backward over-smoothing (Backward Oversmoothing). For that reason we run every depth sweep with and without residuals. If the benefit of intermediate $\beta$ disappears once residuals are added, the practical recommendation largely goes away. The mechanistic result would remain: sampling variance and residuals would be doing overlapping work, which explains why sampled deep models train better than theory for exact gradients predicts. We will report this outcome plainly if it occurs.
Why not just inject generic gradient noise? If noise alone breaks the stall, graph-structured sampling would be irrelevant. Our isotropic and permuted-noise ablations test exactly this. The theory gives a concrete reason to expect a difference: backward over-smoothing is collapse across nodes, and weight-space noise does not add per-node variation to $G^{(l)}$. We will check that prediction directly by measuring the backward rank under each noise type.
Why not just use a stable architecture like A-DGN, or stay shallow? A-DGN already trains at 30 layers, and shallow temporal models such as RepeatMixer reach 51.37 AP on tgbl-review-v2 with shallow mixing over first-order and high-order repeat contexts. Our aim is not to beat these models. We want to establish whether the sampling pipeline that every large-scale GNN depends on is quietly helping or hurting. We will run the $\beta$ sweep on A-DGN as well. If A-DGN shows no dependence on $\beta$, that supports the view that its non-dissipative dynamics remove the stall that noise would otherwise break.
Why not just refresh caches for touched nodes on dynamic graphs? This simple policy may remove most of the staleness bias, and it is one of the three policies we compare, so it is not a straw man. The new question is what to do after staleness has been handled. The proposal predicts that full variance reduction on top of touched-node refresh is still worse at depth than keeping moderate variance.
Decisive Checks
The static-graph test is the loss-versus-$\beta$ curve at 16 and 32 layers. Deep models should reach lower loss at intermediate $\beta$ than at $\beta=1$ or under full-batch training, and they should also keep a higher effective rank in their early-layer gradients. Isotropic and permuted noise should not reproduce either effect. The dynamic-graph test is a two-by-two comparison: refreshed versus stale caches, crossed with low versus moderate variance. Stale caches should hurt at every variance level, while moderate variance should help at depth. If both predictions fail, the conclusion is simple: variance reduction carries no hidden cost at depth, and streaming GNNs should concentrate on correcting staleness alone.
References
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?
- Stochastic Training of Graph Convolutional Networks with Variance Reduction
- Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
- Are we measuring oversmoothing in graph neural networks correctly?
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- Anti-Symmetric DGN: a stable architecture for Deep Graph Networks
- Repeat-Aware Neighbor Sampling for Dynamic Graph Learning