Deep graph neural networks (GNNs) are models in which each node repeatedly averages its neighbors' feature vectors and passes the result through a learned linear map. They usually get worse as layers are added. This failure is called over-smoothing. The usual explanation is that repeated averaging makes all node representations look alike. A sharper account appeared recently in Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?. That paper shows that weight settings which avoid forward collapse do exist, but gradient descent cannot reach them. The training signal sent back through the network is averaged over the graph at every layer just as the features are. It decays toward a constant, uninformative direction. Meanwhile the final classifier fits quickly to the already-smoothed features. Once the classifier has converged, the inner layers stop receiving any useful gradient. The result is a spurious stationary point: the gradient is near zero while the loss stays near the label variance. Keriven leaves open whether a different parameterization could keep optimizers out of these traps.
The maximal update parameterization (μP) answers a closely related question for ordinary networks. It is a recipe that scales initializations and per-layer learning rates with layer size so that each training step changes every layer's output by a size-independent amount (Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer). A side effect is that the best learning rate found on a small model also works on a large one. We propose to restate μP's central requirement in graph-frequency coordinates. Every layer should receive a size-independent update in the part of its representation that differs from node to node. Updates to the shared "consensus" component, which the graph averaging preserves, should not count. Our claim is that this single change makes the trap avoidable by construction. It should also make learning rates transfer across GNN width and depth, which no existing parameterization does for message-passing networks.
Core Claim
Write the propagation operator as $\tilde P = \tilde D^{-1/2}\tilde A\tilde D^{-1/2}$. Its top eigenvector $u \propto \tilde D^{1/2}\mathbf{1}$ (one per connected component) is the consensus direction toward which both features and gradients collapse.
Let $G^{(\ell+1)} \in \mathbb{R}^{N\times d}$ be the gradient of the loss with respect to the pre-activations of layer $\ell+1$, with $N$ the number of nodes and $d$ the hidden width. Let $H^{(\ell)}$ be the input features to layer $\ell$. The standard weight gradient is $(\tilde P H^{(\ell)})^\top G^{(\ell+1)}$.
Keriven's result implies that, as depth grows, $G^{(\ell+1)}$ becomes approximately $u g^\top$ for some vector $g$. The gradient then only moves the mean feature. Adaptive optimizers such as Adam rescale this gradient, but rescaling does not fix it, because Adam amplifies the uninformative direction too.
We split off the consensus part and update with the remainder:
$$ \Delta W^{(\ell)} = -\eta_\ell \,(\tilde P H^{(\ell)})^\top (I - u u^\top)\, G^{(\ell+1)} . $$
We then choose the layer learning rate $\eta_\ell$ to satisfy a graph-frequency analogue of the μP condition:
$$ \frac{1}{\sqrt{N d}}\,\big\|(I-uu^\top)\,\tilde P H^{(\ell)} \Delta W^{(\ell)}\big\|_F = \Theta(1) \quad \text{in } d \text{ and } L . $$
Here $L$ is network depth. In words, the non-consensus change in each layer's output per step stays of fixed size no matter how wide or deep the model is.
This is combined with μP's width rules for hidden and input layers and with μP's down-scaled readout multiplier. The readout scaling matters for a separate reason: it slows the final classifier. In Keriven's mechanism, the classifier converging first is exactly what triggers the trap.
The proposal therefore has two ingredients. The first is μP width and readout scaling, which governs when the readout converges. The second is the frequency-split, depth-normalized inner-layer update, which governs whether inner layers still receive signal. Ablations separate the two.
Relation to Prior Work
Three groups of papers play different roles.
Motivating work. Keriven's analysis supplies the failure mechanism and the open question we answer. It stops at locating stationary points; we target the optimization dynamics that lead into them.
Method sources. Several μP results supply the scaling logic. The original μP paper and A Proof of Learning Rate Transfer under μP establish the per-step invariance principle and prove transfer for MLPs. On the Provable Separation of Scales in Maximal Update Parameterization explains why short proxy sweeps predict large-model optima, but it assumes i.i.d. samples. GNN nodes are coupled through $\tilde P$, which is exactly what our split handles. Don't be lazy: CompleteP enables compute-efficient deep transformers achieves joint width-and-depth transfer in transformers by scaling residual branches. We borrow its depth logic, but CompleteP has no notion of a propagation operator that destroys gradient information.
Sparse maximal update parameterization is the closest structural analogue. It shows that ignoring a structural quantity (sparsity) shifts the optimal learning rate and breaks transfer. However, it treats sparsity as a uniform mask on weights, not as a degree-heterogeneous $N\times N$ operator acting across samples.
Constraining work. Prior GNN fixes act on activations or architecture rather than on updates. PairNorm: Tackling Oversmoothing in GNNs re-centers and rescales activations to preserve pairwise distances. It flattens depth decay, but the authors report that it does not raise peak accuracy on feature-rich benchmarks. That sets a bar our method must clear rather than match.
Simple and Deep Graph Convolutional Networks (GCNII) uses initial residuals and identity-mixed weights with hand-scheduled coefficients and reaches 64 layers. It also documents the "high-degree curse", in which high-degree nodes collapse faster. That is why our consensus vector is degree-weighted rather than uniform.
PairNorm's view that over-smoothing is purely structural and gradient-independent is in tension with Keriven's result. Our experiments test this directly. If the update rule alone, without any activation normalization, trains deep plain GCNs, the structural view is incomplete.
Research Program
Theory. We first derive the scaling exponents in a linearized deep GCN on the corrected stochastic block model (CSBM), a synthetic graph model with controlled homophily (how often linked nodes share a label) and controlled degree distribution. Keriven's proofs require smooth activations, so the derivation uses smooth nonlinearities; ReLU is tested only empirically. The goals are two:
- show that the non-consensus gradient norm under our rule does not decay exponentially with depth;
- predict how $\eta_\ell$ must scale with the second eigenvalue of $\tilde P$ and with $L$.
Practical rule. Next we turn the derivation into a cheap rule that needs no eigendecomposition. Projecting out $u$ only requires a degree-weighted mean per connected component. In mini-batch sampling this becomes a degree-weighted mean over the sampled subgraph. We will measure the error this approximation introduces on ogbn-products.
Measuring the trap. We instrument training to record, per layer and over time, two quantities. The first is the ratio of non-consensus to consensus gradient energy. The second is the time at which the readout's gradient falls below a threshold. Together these trace the optimizer's path into, or around, the spurious stationary points Keriven describes.
Interaction with weight decay. Finally, following Weight Decay may matter more than muP for Learning Rate Transfer in Practice, we scale weight decay alongside the learning rate. We also report transfer with weight decay held at zero, so that apparent transfer cannot be credited to a regularizer.
Baselines
Naive reference. A plain deep GCN in standard parameterization trained with Adam, with the learning rate tuned separately at every width and depth. This is the "do nothing" point. It shows the depth collapse and how much the best learning rate drifts with model size.
Vanilla μP. A GCN under μP or CompleteP rules that treats $\tilde P$ as a fixed matrix multiply. We include it because it is the cheapest way to import μP. If it already escapes the trap, our frequency split is unnecessary.
PairNorm with SGC and GCN backbones (PairNorm). This is the strongest normalization-based method. On Cora under the missing-features setting (SSNC-MV), it reports 74.5% accuracy versus 42.3% for vanilla SGC. We reproduce that setting, so beating it means exceeding 74.5% on SSNC-MV Cora with a plain GCN backbone.
GCNII (Simple and Deep Graph Convolutional Networks). This is the strongest architectural method for depth. It reports its best Cora result at 64 layers, but no reported numerical value was found on Lacuna for that accuracy. The paper also reports that GCNII* improves over APPNP by over 12% on Wisconsin. We therefore re-run GCNII ourselves with its published schedules.
Large-graph references. On ogbn-products, the Open Graph Benchmark paper (Open Graph Benchmark) reports 79.08% test accuracy for GraphSAINT and 78.50% for GraphSAGE.
Fair-comparison protocol. Every method gets the same tuning budget. That budget is a fixed number of trials over learning rate, weight decay, and dropout, plus each method's own extra coefficients (PairNorm scale; GCNII's α and λ). All methods use the same splits, epochs, and hardware.
What counts as a win. Our method wins on its main claim if it meets all three of the following:
- it matches GCNII's best accuracy using a plain GCN without residuals;
- it keeps that accuracy from 2 to 64 layers;
- its learning rate, tuned once at width 64 and depth 4, lands within 0.5 points of the per-size optimum at every larger size.
Ablations. Two ablations isolate the ingredients: μP readout scaling without the frequency split, and the frequency split without μP width scaling. A third ablation replaces the degree-weighted consensus vector with a uniform mean, which tests whether the high-degree curse matters for the update rule.
Why not just…?
Why not just add PairNorm? PairNorm keeps activations spread apart. It does not touch the gradient, and Keriven's trap is a gradient phenomenon: features can be well-spread while inner-layer gradients are still uninformative. PairNorm's authors also report no peak-accuracy gain on feature-rich graphs. Even so, PairNorm could plausibly do as well on depth robustness. Our depth sweep with and without PairNorm settles this. If PairNorm plus vanilla μP equals our method, we will report the frequency split as redundant.
Why not just use residual connections or GCNII? The GCNII paper itself states that ordinary residuals only slow smoothing. GCNII works, but its α and β schedules are hand-tuned and have no width or depth transfer guarantee. GCNII is a real competitor on accuracy. Our distinct claim is transfer, which the learning-rate-versus-size curves will confirm or refute. We also test our update rule on top of GCNII, to see whether the two are complementary.
Why not just apply standard μP, or rely on Adam's per-coordinate rescaling? This is the most serious threat, because μP's small readout may by itself delay readout convergence enough to avoid the trap. Our expectation is that this is insufficient at large depth. Once the backward signal has collapsed onto $u$, both μP's scale corrections and Adam's normalization amplify a consensus-only gradient. The "μP readout only" ablation on CSBM with known λ₂ decides the question. If it closes most of the gap, the paper's contribution becomes that finding, and the frequency split is dropped.
Proposed Experiments
Mechanism test on CSBM. On CSBM graphs swept over homophily and degree skew, we train GCNs with depth 2 to 64 and width 64 to 2048. We record per-layer non-consensus gradient energy and final training loss. The decisive check is that standard parameterization stalls near the label variance while our method continues to reduce training loss at depth 64. Matching Keriven's setup makes the comparison direct.
Real-graph sweeps. On Cora, Citeseer, Pubmed, CoauthorCS, WikiCS, Wisconsin, Chameleon, and Squirrel, we run the full depth sweep and the SSNC-MV setting on Cora. We report test accuracy, training loss, and Dirichlet energy. The Dirichlet energy is reported with the caveats raised in Are we measuring oversmoothing in graph neural networks correctly?.
Transfer test. We plot validation loss against learning rate for each width and depth. Transfer holds if the optima align across sizes for our method and drift for standard parameterization.
Scale test. On ogbn-arxiv and ogbn-products with neighbor sampling, we tune on a narrow, shallow proxy and train a wide, deep target once. We compare against the 79.08% GraphSAINT figure and against a GCNII tuned directly on the target with the same total trial budget.
References
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?
- Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer
- A Proof of Learning Rate Transfer under $\mu$P
- On the Provable Separation of Scales in Maximal Update Parameterization
- Don't be lazy: CompleteP enables compute-efficient deep transformers
- Sparse maximal update parameterization: A holistic approach to sparse training dynamics
- PairNorm: Tackling Oversmoothing in GNNs
- Simple and Deep Graph Convolutional Networks
- Weight Decay may matter more than muP for Learning Rate Transfer in Practice
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Are we measuring oversmoothing in graph neural networks correctly?