Depth-Tied Low-Rank Weights for Training Deep Graph Networks

Graph neural networks compute a node's representation by repeatedly averaging it with its neighbors. Stack many such layers and every node ends up looking the same, a failure called over-smoothing. Most fixes change the forward pass: they add skip connections, renormalize features, or add high-pass filters. Recent theory points to a second culprit. During training, the gradients flowing backward through a deep graph network are averaged over the graph in the same way. As a result, layers far from the output never receive useful updates and stay close to their random initialization. This note proposes attacking that backward failure with a tensor decomposition. Stack all $L$ layer weight matrices into one three-way array of shape $d \times d \times L$, and constrain that array to be low-rank along the depth axis. Every layer then becomes a learned mixture of a few shared "basis" weight matrices. The informative gradient that reaches the layers near the output therefore also moves the layers near the input.

In two sentences: deep graph networks fail partly because their early layers are starved of gradient signal. Writing all layer weights as a low-rank tensor along depth lets every layer borrow gradient from the well-trained layers near the output. The proposal tests whether an intermediate depth-rank, between "every layer independent" and "one weight shared by all layers," escapes this trap better than either extreme or than existing anti-smoothing architectures.

Core Claim and Mechanism

Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? supplies the motivating diagnosis. It proves that backpropagated gradients in deep GNNs decay exponentially toward a non-informative constant. Combined with forward smoothing, this creates spurious stationary points. The last-layer classifier quickly fits the already-smoothed features, its gradient becomes small, and internal layers remain stuck at initialization, with loss plateauing near the label variance. Graph Neural Networks (with Proper Weights) Can Escape Oversmoothing constrains the problem from the other side: good deep weights exist. The bottleneck is therefore finding them, which is an optimization question, not an expressivity one.

The proposed parameterization writes the weight of layer $\ell$ as

$$ \mathbf{W}^{(\ell)} = \sum_{r=1}^{R} c_{\ell r}\, \mathbf{B}_r , $$

where $\mathbf{B}_r \in \mathbb{R}^{d \times d}$ are $R$ shared basis matrices and $c_{\ell r}$ are learned per-layer mixing coefficients. Together these are a factorization of the $d \times d \times L$ weight tensor with rank $R$ along the depth mode. Setting $R = L$ with $\mathbf{c}$ equal to the identity recovers an ordinary untied network. Setting $R = 1$ is full weight sharing up to a per-layer scale.

The gradient with respect to a basis matrix is

$$ \frac{\partial \mathcal{L}}{\partial \mathbf{B}_r} = \sum_{\ell=1}^{L} c_{\ell r}\, \frac{\partial \mathcal{L}}{\partial \mathbf{W}^{(\ell)}} . $$

So whenever the layers near the output receive a useful gradient, every layer that loads on the same basis moves too. This holds even when that layer's own backpropagated gradient has been smoothed into a constant.

The claim is falsifiable and has a predicted shape. Training loss at depth 32–64 should leave the label-variance plateau for intermediate $R$. Accuracy versus $R$ should follow an inverted U: $R = L$ is starved, while $R = 1$ forces every layer to apply the same transform, which cannot express depth-varying filtering.

Relation to Prior Tensor-and-Graph Work

Existing work that combines tensor decompositions with GNNs puts the tensor somewhere other than the depth axis of the weights.

High-Order Pooling for Graph Neural Networks with Tensor Decomposition replaces sum pooling over neighbors with a symmetric CP layer to capture multiplicative neighbor interactions. It studies shallow models and needed Tanh clamping and neighbor subsampling to avoid overflow. It does not analyze depth.

Self-supervised Graph Neural Networks via Low-Rank Decomposition sidesteps message passing altogether. It applies robust PCA and tensor nuclear-norm decomposition to stacked ego-network feature tensors, without supervised backpropagation through layers.

Nimble GNN Embedding with Tensor-Train Decomposition compresses only the input embedding table. It does report that the low-rank constraint improved ogbn-products accuracy by 3%, which warns that any gain here might be generic regularization; an ablation below targets exactly this.

hpGAT: High-Order Proximity Informed Graph Attention Network factorizes the adjacency matrix offline to avoid depth.

None of these four papers factorizes parameters across layers, and none targets the backward failure mode.

Are we measuring oversmoothing in graph neural networks correctly? supplies the measurement tool. It shows that effective rank (Erank, the entropy of the normalized singular values) of the feature matrix tracks accuracy, with an average Pearson correlation of 0.91, where Dirichlet energy does not. That analysis covers only forward features. This proposal applies the same Erank to the per-layer gradient matrices, giving a direct backward-smoothing measurement.

Research Program

The work has three parts.

Implementation. The depth-tied parameterization will be built on top of a plain deep GCN and on top of GCNII. It also admits optional within-basis low rank, $\mathbf{B}_r = \mathbf{U}_r \mathbf{V}_r^\top$. The basis matrices will be initialized orthogonally, following the column-orthogonal scheme used for tensor-train cores in the Nimble paper. The coefficient matrix $\mathbf{c}$ will be initialized so each layer starts near a distinct mixture.

Instrumentation. Training runs will log, per layer and per epoch:

  • forward Erank of the features;
  • Erank and norm of the gradient with respect to each layer's weights;
  • distance of each layer's weights from their initialization.

Distance from initialization is the quantity Keriven's theory predicts stays near zero for untied deep models.

Theory. A small analysis on the linear GCN will ask whether the shared-basis gradient avoids the exponential backward decay. Under the linear model, each layer's gradient is a smoothed version of the output gradient, damped by the second-largest eigenvalue of the normalized adjacency raised to the layer's distance from the output. The basis gradient is a coefficient-weighted sum of these terms, so it should be dominated by the undamped near-output terms. Characterizing when such a sum yields weights that escape the spurious stationary point is the theoretical deliverable. Rank selection along depth will be swept by hand, with MARS: Masked Automatic Ranks Selection in Tensor Decompositions tried as an automatic alternative.

Baselines

Naive reference. The reference point is an untied deep GCN at each depth (2, 4, 8, 16, 32, 64), plus a 2-layer GCN as the "don't go deep" option. If the deep tied model cannot beat the 2-layer model on some dataset, depth is not useful there, and the result is only an optimization finding.

Strongest existing method. The strongest competitor is GCNII from Simple and Deep Graph Convolutional Networks. It combines an initial residual to the input features with an identity-plus-weight mapping, and it reached its best Cora result at 64 layers. The file reports no Cora accuracy value for it; the only scalar it gives is that GCNII* improved Wisconsin accuracy by over 12% relative to APPNP. Its value here is that the identity mapping already lets deep layers act as near-identity, which is a competing explanation for escaping the trap.

Second forward-pass baseline. PairNorm from PairNorm: Tackling Oversmoothing in GNNs re-centers and rescales features at every layer. Its reported number is 74.5% accuracy for PairNorm-enhanced SGC versus 42.3% for vanilla SGC on Cora with missing features on unlabeled nodes. We will rerun that missing-features setting so the comparison uses its own reported regime.

Fixed-weight baseline. Partially trained graph convolutional networks resist oversmoothing serves as the "don't train the deep layers at all" baseline.

Fairness. All methods share data splits, depth, hidden width, and optimizer. Each gets the same hyperparameter search budget over learning rate, weight decay, and dropout, with 10 seeds. Parameter counts are reported, so a tied model is also compared against an untied model shrunk to the same parameter count.

Ablations. Three ablations isolate the key ingredient:

  • Full sharing ($R = 1$) tests whether a shared basis alone suffices.
  • Frozen random coefficients $\mathbf{c}$ test whether learned mixing matters.
  • Within-layer low rank without tying across depth (each layer's own matrix factored as $\mathbf{U}_\ell \mathbf{V}_\ell^\top$ at matched parameter count) separates gradient sharing from generic low-rank regularization.

Success criterion. The proposal counts as beating a baseline if the tied model, at its best $R$ chosen on validation, exceeds it in test accuracy at depth ≥ 16 beyond seed variance. On GCNII the bar is lower: the tied GCNII must match plain GCNII's accuracy at equal or lower parameter count, and it must show measurably larger deep-layer weight movement.

Why not just…?

Why not just share one weight matrix across all layers? This is the most serious threat. Full sharing gives every layer the near-output gradient too, and recurrent graph models do exactly this. The rank sweep settles it directly. If $R = 1$ matches the best intermediate rank, the tensor structure is unnecessary and we will report weight sharing itself as the fix for backward smoothing. Our prior expectation for an intermediate optimum is that layers at different depths act on features of very different Erank, so a single transform should be a poor fit. The data decide, though.

Why not just use GCNII's residuals? Initial residuals keep the input features alive in the forward pass. Keriven's analysis argues that preventing forward collapse does not by itself remove the backward trap. The per-layer distance-from-initialization logs will show whether GCNII's deep layers actually train or merely pass the input through. If they train, depth-tying is a complement at best, and the experiment on a tied GCNII tests exactly that.

Why not just add an effective-rank penalty on the features, as the rank-measurement paper suggests? That paper itself notes that high rank is necessary but not sufficient: random noise has full rank and no task signal. A rank penalty can therefore be satisfied by meaningless features. We include an Erank-regularized deep GCN as an extra baseline under the same tuning budget. We expect it to raise Erank without lifting accuracy on CSBM, where class signal is known.

Why not just tune per-layer learning rates or initialization? Larger learning rates on early layers amplify a gradient that is already nearly constant. They do not add information. A per-layer learning-rate search under the same budget is included on WikiCS and CSBM to check this.

Proposed Experiments

The decisive test uses the synthetic contextual stochastic block model (a random graph generator with controllable class structure and homophily) and WikiCS. On these, Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? showed that deep GNNs plateau immediately while an MLP's loss decreases; the file reports no scalar for this. We will reproduce that plateau with a 32-layer untied GCN, then ask whether tied models at $R \in \{1, 2, 4, 8\}$ drive training loss below the label-variance floor. We will also check whether their gradient Erank and deep-layer weight movement stay higher.

Generalization will be tested on Cora, Citeseer, and Pubmed, on heterophilic graphs (Texas, Wisconsin, Chameleon, Squirrel), and on ogbn-arxiv for scale. Accuracy will be plotted against depth and against $R$. The proposal is refuted under any of three outcomes:

  • untied deep models do not plateau in our reproduction;
  • tied models plateau equally;
  • the within-layer low-rank ablation explains all of the gain.