Holding Back the Readout: A Test of Why Deep Graph Networks Stop Training

Graph neural networks compute each node's representation by repeatedly averaging it with its neighbors' representations. Stack many such layers and the representations of all nodes drift toward the same vector, a failure called over-smoothing, and accuracy collapses. A standard 10-layer graph convolutional network on the Cora citation graph falls to about 26% accuracy (Old can be Gold), against 81.5% for a 2-layer one (Semi-Supervised Classification with Graph Convolutional Networks). A recent theory recasts this as an optimization failure rather than a limit on what the model can represent. In Backward Oversmoothing, Keriven proves that gradients flowing backward through the network get averaged in the same way, so every inner layer receives nearly the same useless signal. The final linear classifier, which reads predictions off the representations, sees heavily smoothed features and fits quickly. Once it has fit, the only part of the error that could still travel backward is gone, and the whole network stalls at a high-loss stationary point. This is a concrete instance of the gap between convex optimization theory and deep learning: under convexity, a point where gradients vanish is a solution, but here it is a trap created by the network's own structure.

Keriven locates these traps but leaves open how training reaches them, and whether a change to the optimizer can steer around them. This note proposes to treat the trap as a race between two learning speeds. The readout, meaning the final classifier, learns fast, and the inner layers learn slowly. The proposal is to model that race in a linear graph network on synthetic graphs, derive how long the inner layers have before the readout closes the window, and test the prediction that slowing or freezing only the readout keeps a deep, plain graph network trainable. If the prediction holds, it isolates the mechanism behind deep-GNN failure with a one-line intervention. If it fails, it shows that the gatekeeper effect is not the binding constraint. Either result is useful.

Core Claim

Backward averaging shrinks every part of the error signal except its smoothest component: the part that is nearly constant across a connected region of the graph, which lies along the top eigenvectors of the averaging operator. That smooth component is exactly what the readout's weights and bias remove first. Inner-layer gradients therefore carry real signal only while the readout has not yet absorbed the smooth part of the error.

For a depth-$L$ linear graph network with averaging operator $\hat A$ whose second-largest eigenvalue magnitude is $\lambda < 1$, the size of the inner-layer gradient splits roughly into two terms:

$$\|\nabla_{W_\ell}\mathcal{L}\| \;\lesssim\; \|r_{\text{smooth}}(t)\| + \lambda^{L-\ell}\,\|r_{\text{rough}}(t)\|.$$

Here $r_{\text{smooth}}(t)$ is the projection of the error vector at training time $t$ onto the top eigenvectors, and $r_{\text{rough}}(t)$ is the remainder. The second term is exponentially small in the distance $L-\ell$ from the output, which is the content of backward oversmoothing. The first term decays at a rate set by the readout's learning rate $\eta_{\text{out}}$ times the squared norm of the smoothed features. The open question is whether inner weights can grow enough during that window, under the gradient carried by $r_{\text{smooth}}$, to undo the forward averaging. Keriven notes that sufficiently large weights would counteract forward smoothing.

The claim is that they can, and that the window's length scales like $1/\eta_{\text{out}}$. This yields a falsifiable prediction: lowering the readout's learning rate relative to the inner layers, by a factor that grows with depth and with $\lambda$, should move a deep plain network out of the plateau. A plain network here means one with no skip connections, no normalization and no gates. The plateau is the regime where training loss stays near the label variance.

There is a real reason this might fail, and the proposal states it up front. The surviving signal $r_{\text{smooth}}$ is nearly constant across nodes. It may only teach inner layers to amplify the shared, non-discriminative direction, which would raise loss-free capacity without separating classes. The experiments below are designed to tell these outcomes apart.

Research Program

The analysis has three parts. The first is a two-timescale analysis of gradient flow for a linear graph network on contextual stochastic block models. These are synthetic graphs with planted communities whose node features and edge homophily can be tuned. Keriven also uses them, so the analysis inherits his setting and extends it from where the traps sit to how training reaches them. The outputs are the window length as a function of $\eta_{\text{out}}$, depth and spectral gap, and the condition under which inner-weight growth inside the window is enough to escape.

The second part checks the analysis against real graphs. During training we log three quantities. The first is the smooth and rough error components, computed from the leading eigenvectors of $\hat A$. The second is the ratio of inner-layer to readout gradient norms. The third is the effective rank of each layer's representations, an entropy measure of how many independent directions the node representations span. Are we measuring oversmoothing correctly? reports that effective rank tracks accuracy (Pearson 0.91) where the older Dirichlet-energy measure does not. The specific prediction is that inner-layer gradient collapse happens when $\|r_{\text{smooth}}\|$ hits zero, not when depth alone would predict it.

The third part is the intervention itself: readout lag. We test three forms of it. One sets a separate, smaller readout learning rate. One freezes the readout at its random initialization for the first $T$ steps. One removes the readout bias, testing whether the bias is what absorbs the smooth error. The analysis predicts that removing the bias delays the trap but does not prevent it, because readout weights acting on near-constant features behave like a bias.

Baselines

The naive reference point is a plain deep graph convolutional network trained with Adam at a single learning rate. The file reports about 26% on Cora at 10 layers (Old can be Gold) and 10–20% at 32 layers (Partially trained GCNs). The shallow ceiling is 81.5% (Semi-Supervised Classification with Graph Convolutional Networks).

The strongest existing method is the approach of Jaiswal et al. in Old can be Gold. It is the closest competitor because it also keeps a vanilla network and targets gradient flow directly. It combines an initialization scaled by node degree with skip connections inserted on the fly whenever a layer's gradient norm drops. It reports about 80% on Cora up to 64 layers and 72.28% on ogbn-arxiv, beating GCNII and JKNet. We will run it from its described procedure on identical splits, depths and epoch budgets.

Two further competitors cover distinct mechanisms. Frobenius weight normalization from Taming Gradient Oversmoothing and Expansion caps each layer's Lipschitz constant. It reports 100% training accuracy for residual networks up to 512 layers; no test-accuracy figure was found on Lacuna for it. Gradient Gating from Gradient Gating for Deep Multi-Rate Learning on Graphs slows each node's update when it matches its neighbors; no reported Cora accuracy was found on Lacuna for it.

Every method gets the same hyperparameter search budget, counted as an equal number of trials, over its own knobs. For readout lag those knobs are the lag factor and the freeze length $T$. For Jaiswal et al. they are the threshold and skip ratio. Results are averaged over ten seeds.

Readout lag counts as beating the naive baseline if a 32- or 64-layer plain network moves off the label-variance plateau and reaches test accuracy within a few points of the shallow ceiling. It counts as matching the strongest method if it falls within seed variance of roughly 80% on Cora and 72.28% on ogbn-arxiv without adding any skip connections.

The key ablation applies the same lower learning rate to a randomly chosen inner layer instead of the readout. If that helps equally, the effect is generic learning-rate tuning and not the gatekeeper mechanism.

Why not just…?

Why not just add skip connections? Skip connections bypass the averaging rather than explaining the trap. Taming Gradient Oversmoothing and Expansion shows that skip connections in graph networks cause gradients to blow up in diverging directions beyond about 32 layers unless weights are normalized. Keriven also notes that their optimization behavior has no theory yet. This proposal keeps the network plain so the mechanism can be isolated, and it reports skip-connection results alongside rather than claiming to replace them.

Why not just rely on Adam's per-parameter scaling to amplify the tiny inner gradients? This is a real threat, because Adam divides each gradient by its running magnitude. Visualization and Analysis of the Loss Landscape in GNNs reports that Adam still stalls in the flat region while the curvature-aware method KFAC escapes. The likely reason is that rescaling a near-constant gradient amplifies an uninformative direction. We test this directly with Adam, SGD and KFAC, each with and without readout lag. If KFAC alone matches readout lag, the honest conclusion is that curvature correction already handles the gatekeeper, and our contribution narrows to explaining why.

Why not just train a single wide layer and freeze the rest? Partially trained GCNs does exactly this and keeps over 70% on Cora at 32 layers, but it needs widths up to 8192 and does not explain why end-to-end training fails. Readout lag is close to the mirror image of that approach: it slows the output layer rather than freezing the inner ones, and it runs at ordinary width. We include partial training at matched width as a baseline. If partial training at modest width also works, the gatekeeper explanation still predicts it, since a random readout cannot gatekeep.

Why not just insert normalization layers such as PairNorm? Are we measuring oversmoothing correctly? finds that BatchNorm and LayerNorm keep feature variance while effective rank still collapses and accuracy falls. Normalization therefore hides the symptom without addressing the backward signal. We run it as a secondary baseline.

Proposed Experiments

On synthetic block-model graphs, we sweep depth (4 to 64), homophily and the readout lag factor. We check three predicted scalings: that the time until inner gradients collapse grows like $1/\eta_{\text{out}}$, that the lag needed to escape grows with depth and with $\lambda$, and that collapse coincides with $\|r_{\text{smooth}}\|$ reaching zero.

On Cora, CiteSeer, PubMed and ogbn-arxiv (Open Graph Benchmark), we compare readout lag against the baselines above at depths 8, 16, 32 and 64. We report training loss relative to label variance, test accuracy and per-layer effective rank.

On the low-homophily graphs Squirrel and Chameleon, where neighbors usually have different labels, the useful signal is not smooth. Here the theory predicts that readout lag helps less. We treat this as a pre-registered negative-control prediction.

The decisive checks are three, and each separates a real mechanism from a lucky tuning effect. First, applying the lag to the readout must beat applying the same lag to a random inner layer. Second, the time of inner-gradient collapse must follow the readout's fit of the smooth error rather than depth alone. Third, effective rank must rise in the inner layers when the network escapes, which rules out the failure mode where inner layers learn only the shared, non-discriminative direction.