Distance Budgets Across Depth for Deep Graph Networks

Graph neural networks compute each node's representation by repeatedly averaging it with its neighbors' representations. Stack many such layers and every node ends up looking the same, a failure called over-smoothing. A second line of work, from learning theory, explains why huge networks generalize: their weights stay close to where random initialization put them, so the right measure of complexity is the distance $\|W - W_0\|$ between trained weights $W$ and initial weights $W_0$. This proposal joins the two. It uses that distance, measured layer by layer, as a diagnostic for why deep graph networks fail to train. It then uses the same distance as a control: a hard cap on how far each layer may move.

The hypothesis is simple. Deep graph networks fail because training spends its distance in the wrong place. The last layer, a linear classifier, moves far and fits the training labels quickly on smoothed features. Once it has, the gradients reaching the internal layers collapse, and those layers stay frozen near $W_0$. If that is the mechanism, then capping how far the classifier may travel from its initialization should keep the training signal alive long enough for internal layers to move and learn to resist smoothing. This should work at ordinary widths of a few hundred units, with no residual connections and no normalization layers.

Core Claim

Backward Oversmoothing proves that in deep message-passing networks the gradients sent backward through the layers collapse toward a node-constant signal at an exponential rate. Once the final layer converges, training sits at a high-loss stationary point with internal weights near initialization. That paper diagnoses the problem but offers no constructive fix, and it reports no accuracy numbers. Partially trained graph convolutional networks resist oversmoothing shows the opposite extreme also works. It freezes every layer except one at its random initialization, so those layers travel zero distance, and it resists smoothing at 32 to 64 layers. The catch is that it needs width 8,192, so that wide random matrices act as decorrelators. We read these two results as the endpoints of one design axis: how much distance from initialization each layer is allowed.

Our claim is that a non-uniform, initialization-relative budget beats both endpoints. The budget is tight on the classifier and on late layers, and loose on internal layers. Concretely, we project each layer after every optimizer step onto the ball

$$\|W^{(\ell)} - W_0^{(\ell)}\|_{\mathrm{MARS}} \le \gamma_\ell,$$

where $W_0^{(\ell)}$ is the layer's initial weight matrix and $\|\cdot\|_{\mathrm{MARS}}$ is the maximum absolute row sum norm. The method follows Distance-Based Regularisation of Deep Networks for Fine-Tuning, which showed in vision fine-tuning that hard projection onto such a ball beats soft $\ell_2$ penalties. The radius $\gamma_\ell$ is set per layer and is small for the classifier.

What is new is the use of distance from initialization as a resource allocated across depth to fight over-smoothing. The ingredients, distance bounds and topology-aware initialization, exist separately.

Relation to Prior Work

Several papers motivate the gap. Reducing oversmoothing through informed weight initialization (G-Init) scales initial weight variance by node degree. Old can be Gold pairs degree-aware isometric initialization with skip connections inserted when gradient norms drop below a threshold. Principles for Initialization and Architecture Selection derives a graph-specific He initialization and proves that smoothing with fixed aggregation is unavoidable at depth. All three choose $W_0$ carefully. None constrains or even measures how far training moves from it, and that trajectory is exactly what we control.

Taming Gradient Oversmoothing and Expansion supplies the closest competing method. It rescales each weight matrix to a fixed Frobenius norm, $W \leftarrow cW/\|W\|_F$, and trains residual networks to 512 layers. That is an absolute-norm constraint applied uniformly to every layer. Ours is anchored at $W_0$ and varies by layer. One of our ablations separates these two choices directly.

MLPInit moves the anchor to weights pre-trained as a plain multilayer perceptron. It explicitly leaves open whether this helps against over-smoothing, and it leaves the fine-tuning displacement unconstrained. We test that anchor as a secondary condition.

The theory papers, The role of over-parametrization in generalization and Gradient Descent with Early Stopping is Provably Robust to Label Noise, supply the lens. Movement from initialization is the quantity that tracks what a network actually learns. Clean signal is fit within a small radius, while fitting noise requires traveling far. Both results are for shallow networks on independent Euclidean inputs, so we treat them as motivation, not as guarantees on graphs.

Research Program

The first phase is measurement. For vanilla graph convolutional networks of depth 2 to 64 we log the relative travel $\|W_t^{(\ell)} - W_0^{(\ell)}\|_F / \|W_0^{(\ell)}\|_F$ of every layer through training. We do the same for networks trained with G-Init, GCNII (Simple and Deep Graph Convolutional Networks), PairNorm (PairNorm), and the Frobenius normalization above. Alongside travel we record three other quantities. The first is the spread of node representations at the last hidden layer, measured as the total pairwise squared distance from PairNorm. The second is the variance across nodes of the gradient each layer receives, which detects backward collapse. The third is the step at which the classifier's training loss saturates.

The prediction is a "travel profile" that separates working from failing configurations. Failing networks should show classifier travel that is large relative to internal travel, and internal travel that stops when the classifier saturates. If successful methods show no such pattern, the hypothesis is wrong, and we will report that before building anything.

The second phase is intervention. We cap classifier and late-layer travel by projection. The anchor is either G-Init weights or standard Glorot weights. We sweep the classifier radius $\gamma_L$ across orders of magnitude, from zero, which freezes a random classifier, to unconstrained. Internal radii are left either free or uniform.

The third phase is a modest piece of theory on a two-block stochastic block model, a synthetic graph with two planted communities, using a deep linear graph network. The question is whether capping the classifier's distance removes the spurious stationary points Keriven identifies. The intuition is that a classifier that cannot fit the loss alone keeps the backward signal non-constant. We would state the result only for the linear case.

Baselines

The naive reference point is a vanilla graph convolutional network with Glorot initialization and unconstrained Adam. It is trained at the same width, depth, and tuning budget as everything else: an equal number of hyperparameter trials per method, chosen on validation accuracy, with ten seeds. Old can be Gold reports that this model falls to about 26% on Cora at 10 layers.

The strongest initialization-only competitor is G-Init. It reports 69.24% accuracy on Cora with a 64-layer network and 61.60% on Coauthor CS at 32 layers (G-Init). It is the right comparison because it also keeps the vanilla architecture and changes only optimization-side choices.

The strongest vanilla-architecture result in the file is Old can be Gold. It reports about 80% on Cora up to 64 layers and 72.28% on ogbn-arxiv. Strictly, its dynamically inserted skip connections change the architecture. Our method beats it only if it matches or exceeds these numbers with no skips at all. Matching them would already be informative, because it would show that a single radius can replace the paper's two tuned thresholds.

We also compare against partial training, which reports over 70% on Cora at 32 layers with width 8,192. It is the closest conceptual competitor. Beating it means reaching that accuracy at width 256 or less.

PairNorm reports 74.5% against 42.3% for plain simplified graph convolution on Cora with features missing from unlabeled nodes. We use that setting to compare against it.

GCNII is the residual-architecture reference. Its Cora number is not in the file, so we reproduce it under our protocol. Frobenius normalization reports 512-layer residual training to 100% training accuracy but gives no test accuracy in the file. We run it at matched depth.

The key ablation swaps the anchor from $W_0$ to the origin, with the same radii. If constraining distance from the origin works equally well, initialization-relativity is not the active ingredient. A second ablation applies uniform radii to every layer, which tests whether the allocation across depth matters or only the total amount of constraint.

Why not just…?

Why not just lower the classifier's learning rate, or freeze it? This is the most serious threat. A lower learning rate also slows the classifier, and freezing is the radius-zero case. We treat both as alternative implementations of the same hypothesis, and they run in the same sweep. A lower learning rate only delays displacement, while projection bounds it for the whole run. Gouk et al. found that the analogous soft control, penalizing distance, lets the loss gradient overpower the constraint (Distance-Based Regularisation). If learning-rate scaling matches projection on accuracy and travel profiles, we will say so. The contribution then becomes the diagnosis and the cheapest fix, not the projection operator.

Why not just add residual connections? Residual connections address forward collapse. But Taming Gradient Oversmoothing and Expansion shows that residual graph networks develop exploding, chaotic gradients beyond about 32 layers. GCNII further shows that connections to the previous layer only slow smoothing, and that holding performance at 64 layers requires an initial-residual connection plus an identity mapping. Residual connections are complementary to our method. We test whether distance budgets also stabilize residual networks, in place of Frobenius normalization.

Why not just use PairNorm? PairNorm fixes the forward representations but does nothing about collapse in the backward signal. Its own paper notes it does not raise peak accuracy on feature-rich graphs. Our phase-one measurements will show directly whether PairNorm networks still exhibit frozen internal layers. If they do not, PairNorm already solves the backward problem indirectly, and our gains should then be confined to unnormalized models.

Why not just widen the network and freeze it? Partial training needs width 8,192, which is impractical on ogbn-products. Our width sweep from 64 to 8,192 asks whether allowing a small amount of internal movement replaces width. That is the core quantitative bet of the proposal.

Proposed Experiments

Experiments cover Cora, CiteSeer, and PubMed at depths 2, 8, 16, 32, and 64. They also cover Coauthor CS and Physics, the heterophilic Chameleon and Squirrel graphs, the Cora missing-feature setting from PairNorm, ogbn-arxiv with its temporal split (Open Graph Benchmark), and corrected stochastic block models for controlled analysis. Metrics are test accuracy, the per-layer travel profile, representation spread, cross-node gradient variance, and memory use.

Two checks are decisive. First, in phase one, failing deep networks must show large classifier travel together with internal travel that stalls. Second, capping classifier travel must increase internal travel and test accuracy together at width 256 or less. If accuracy rises but internal travel does not, the mechanism is something other than the one we propose. If the origin-anchored ablation matches the $W_0$-anchored one, the initialization-relative framing should be dropped.