All-Pass Backpropagation for Deep Graph Networks

A graph convolution replaces each node's features with an average over its neighbors. In signal-processing terms it is a low-pass filter: it keeps patterns that vary smoothly across the graph and suppresses sharp node-to-node differences. That averaging is why graph networks help on citation graphs. It is also why they break when stacked deeply. Repeated averaging collapses every node onto the same vector, a failure called over-smoothing. Recent theory adds a second half to this story. The gradients flowing backward during training pass through the same averaging operator and get smoothed too. As a result, the early layers of a deep graph network receive almost no usable learning signal, even though weights that would avoid collapse provably exist (Backward Oversmoothing; Graph Neural Networks (with Proper Weights) Can Escape Oversmoothing).

We propose to keep the forward low-pass filter exactly as it is and change only how the gradient travels backward. In the backward pass, each averaging step is replaced by an "all-pass" version of the same operator: one with the same frequency directions and signs, but unit gain in every frequency band. Gradients therefore reach early layers without their high-frequency, node-distinguishing content being erased. The proposal has two uses. As a method, it tests whether deep low-pass networks become trainable once the backward smoothing is removed. As a causal probe, it answers a question the literature has left tangled: when deep graph networks fail, how much is due to features collapsing on the way forward, and how much to gradients collapsing on the way back?

Core Claim

Write a layer as $H_l = \sigma(S H_{l-1} W_l)$. Here $S$ is the symmetric normalized adjacency with self-loops, $W_l$ is the layer's weight matrix, and $\sigma$ is the activation. With $\delta_l$ denoting the gradient with respect to the layer's pre-activation, ordinary backpropagation sends $\partial \mathcal{L}/\partial H_{l-1} = S\,\delta_l W_l^\top$ to the previous layer. Because this multiplies by $S$ once per layer, gradients are low-pass filtered exactly as features are. This is Keriven's backward over-smoothing.

Let $S = U \Lambda U^\top$ be the eigendecomposition of $S$. We define the all-pass (polar) factor

$$P = U\,\mathrm{sign}(\Lambda)\,U^\top,$$

and in the backward pass we substitute $P$ for $S$. Computing $P$ exactly requires a full eigendecomposition, which we avoid. Instead we apply a degree-$q$ Chebyshev approximation of the sign function to $S$, which costs $q$ sparse matrix–vector products per layer.

The substitution is biased, but it is not arbitrary. Since $S = P|S|$, where $|S| = U|\Lambda|U^\top$ is positive semidefinite, the substituted and true gradients at a single layer satisfy

$$\langle S\delta,\; P\delta\rangle = \delta^\top |S|\, \delta \ge 0 .$$

So each layer's modified signal never points against the true one. The alignment is weakest only in frequency bands the forward pass has already nearly deleted.

Our claim is specific. On deep low-pass graph networks at 16 to 64 layers, all-pass backpropagation should keep the node-wise diversity of gradients at early layers, keep the forward feature rank from being driven down by training, and recover much of the accuracy lost with depth. It should do so without changing the forward model, and it should add to weight-norm control rather than duplicate it. If it fails to beat Frobenius weight normalization, the conclusion is also informative: backward spectral smoothing is then not the binding constraint once gradient norms are controlled.

Relation to Prior Work

The obvious bridge between the two directions has already been built. Over-smoothing is repeated low-pass filtering (Deeper Insights Into Graph Convolutional Networks proves convergence to a degree-proportional rank-one state), and the standard remedy is to change the forward filter. Several works do this:

All of these change what the model computes. None of them analyzes the gradient path, and each changes the function class, which confounds the comparison. We leave the function class fixed and change only credit assignment.

The optimization line of work motivates and constrains the proposal. Keriven proves that smoothed gradients create spurious stationary points: the final classifier fits the already-smoothed features, its gradient vanishes, and all earlier layers freeze. His analysis covers single-channel message passing with smooth activations. Graph Neural Networks (with Proper Weights) Can Escape Oversmoothing proves that good weights exist, and uses an input-dependent reparameterization (WeightRep) to help reach them, but still degrades beyond 16 layers. Taming Gradient Oversmoothing and Expansion measures gradient similarity across nodes and fixes it by normalizing weight norms, training residual networks to 512 layers. It is the closest competitor. Its tool is a uniform scalar gain on weights, which cannot restore frequency bands that $S$ has attenuated. Ours is a frequency-selective gain on the graph operator, so the two are complementary.

For measurement we reuse Are we measuring oversmoothing correctly?. That paper shows effective rank tracks accuracy (average Pearson correlation 0.91) while Dirichlet energy does not. Its warning that high rank is not sufficient shapes our design: we never inject rank directly, and we let the task gradient decide what the extra bands carry.

Research Program

The work has three parts.

The first part is the operator itself. We implement all-pass backpropagation as a custom autograd function in which the forward pass multiplies by $S$ and the backward pass multiplies by a Chebyshev sign approximation of degree $q \in \{4, 8, 16\}$. We also implement an interpolated variant $(1-\gamma)S + \gamma P$, so that backward equalization can be dialed in gradually.

Two costs need watching. First, a degree-$q$ polynomial spreads each node's gradient $q$ hops, farther than the true one-hop gradient, and this may blur credit assignment. The interpolated variant and a degree sweep measure that effect. Second, the extra matrix–vector products add training time. We report wall-clock time and compare at matched time.

The second part is diagnostics, run on every configuration, measured separately for the forward and backward passes:

  • Forward features: effective rank and numerical rank at each layer (Zhang et al.).
  • Backward gradients: the node-similarity measure $\mu$ of Park and Kim at each layer.
  • Gradient frequency profile: we project $\delta_l$ onto eigenvector bands on small graphs, and onto Chebyshev band filters on large ones, to see how much gradient energy survives outside the dominant eigenspace.

These diagnostics turn the method into a probe. If the forward operator and forward-pass accuracy at initialization are unchanged, any gain from the backward swap is attributable to the backward path.

The third part tests whether a filterbank alone escapes Keriven's trap. We apply the same diagnostics to a two-channel low/high-pass network in the style of FB-GNN, trained with standard gradients. This checks the untested conjecture that a parallel high-pass channel already un-smooths gradients. The answer decides whether all-pass backpropagation matters for filterbanks too, or only for pure low-pass stacks.

Baselines

The naive reference points are a vanilla deep GCN and a two-layer GCN at the same width. The deep GCN shows the failure: Partially trained graph convolutional networks resist oversmoothing reports that a 32-layer GCN on Cora falls to 10–20% accuracy. The shallow GCN is the practical default. Alongside these we run SGC (Simplifying Graph Convolutional Networks), which applies a fixed filter to the features and then a linear classifier, and so avoids deep backpropagation entirely. SGC reports 81.0% on Cora, 71.9% on CiteSeer and 78.9% on PubMed. We also run an MLP, which Keriven shows does not suffer the backward trap.

The strongest existing method on this exact question is Frobenius weight normalization (Taming Gradient Oversmoothing and Expansion). It targets gradient over-smoothing directly and reaches 512 layers with 100% training accuracy. No test accuracy for it appears in the file, so we will reproduce it rather than quote a figure. A second strong competitor is the partially trained wide GCN of Kelesis et al., which keeps above 70% on Cora at 32 layers and reaches 88.11% in the 14-layer cold-start Physics setting, but uses width 8192. We also include WeightRep, FB-GNN, and a GCNII-style initial-residual network. For GCNII we found no reported result on Lacuna, so it is reproduced as well.

Every method gets the same data splits, the same depth grid (2, 8, 16, 32, 64 layers), and the same width (256, except for the Kelesis reproduction, which is run at its native width and also at 256). Each method gets the same Bayesian-optimization budget of 60 trials over learning rate, weight decay and dropout, plus its own method-specific knob: $c$ for weight normalization, and $q$ and $\gamma$ for our operator. Results are averaged over 10 seeds.

Beating the strongest baseline means two things. At 32 and 64 layers, all-pass backpropagation on a plain GCN must exceed weight normalization on a plain GCN in test accuracy by more than the seed standard deviation. And the combination of the two must exceed weight normalization alone. On cold-start Physics, matching or exceeding 88.11% at width 256 would show that the Kelesis result does not need its memory cost.

Four ablations isolate the key ingredient, which is preserving eigenvectors while equalizing gain:

  • Identity backward, $S \to I$: removes smoothing but destroys graph credit assignment.
  • A random orthogonal backward operator, in the style of feedback alignment: tests whether any non-smoothing backward operator is enough.
  • The $\gamma$ sweep: tests whether partial equalization suffices.
  • All-pass backward applied at only the last few layers versus all layers: tests Keriven's claim that the final-layer bottleneck is what matters.

Why not just…?

Why not just normalize weight norms, as Park and Kim do? This is the real threat. Their method already drives gradient similarity out of the collapsed regime and fits the training set perfectly at 512 layers. But the file reports no test numbers for it, and perfect training accuracy on small citation splits is fully compatible with memorization. A scalar gain on $W$ also multiplies all graph frequency bands equally, so it cannot restore bands that $S$ attenuates relative to the dominant eigenvector. The frequency profile of gradients under their method settles the question directly. If weight normalization alone already keeps early-layer gradient energy spread across bands and matches our test accuracy, we will report that the backward swap is redundant.

Why not just add a high-pass channel, as FB-GNN does? With separate weights per channel, a filterbank is no longer a single operator with one dominant eigenspace, so it might escape backward smoothing on its own. That is exactly the untested conjecture from Gap 1, and the third part of the program measures it. The objection to relying on it is that it changes the function class and brings the flexibility-trap risk documented for learnable filters (Automated Polynomial Filter Learning). Our operator adds no forward parameters.

Why not just stay shallow or use SGC? On homophilic citation graphs this may well be enough, and we expect SGC's 81.0% on Cora to be hard to beat by much. Depth pays only when information must travel far. That happens in cold-start settings, where features on unlabeled nodes are zeroed out, on OGB-Arxiv, and possibly on heterophilic graphs, where Taming Gradient Oversmoothing and Expansion argues depth helps. We therefore report results split by regime, and we treat a win confined to cold-start and large graphs as the honest scope of the claim.

Proposed Experiments

The first decisive check uses the synthetic contextual stochastic block model of Baranwal et al.. In this model, node features are drawn from class-specific Gaussians and edges are drawn with class-dependent probabilities, so the separability that one-layer filtering can reach is known. We sweep depth and the gap between intra- and inter-class edge probabilities, and train with smooth (GELU, tanh) and ReLU activations, since Keriven's proof covers only smooth ones. The prediction is that under standard backpropagation, early-layer weights barely move from initialization at depth 32, whereas under all-pass backpropagation they move and feature effective rank stays well above one. If early-layer weights still do not move, the backward-smoothing explanation is wrong for this setting.

The second check sweeps depth on Cora, CiteSeer and PubMed with standard splits, and on cold-start Physics and Amazon Computers following Kelesis et al.. We report test accuracy, per-layer effective rank, and gradient similarity $\mu$.

The third check covers the heterophilic graphs Chameleon, Squirrel, Texas and Cornell. We ask whether all-pass backpropagation lets a low-pass stack approach multi-frequency models such as GSAN, which reports 61.2% on Chameleon versus 28.2% for GCN. We expect a partial gap to remain there, since the forward filter is still low-pass. That gap measures how much of the heterophily problem belongs to optimization and how much to the model class.

The fourth check tests scale and cost. On OGB-Arxiv we compare accuracy at matched wall-clock time and matched GPU memory against the width-8192 partially trained network.

The whole proposal is decided by one pattern in these results: an accuracy gain that appears together with restored band-spread in early-layer gradients, persists on top of weight normalization, and disappears under the random-orthogonal ablation.