Deep graph neural networks, which pass messages between neighboring nodes layer after layer, suffer from over-smoothing: as layers are stacked, node features drift toward a common value until nodes can no longer be told apart. Recurrent sequence models had a closely matching problem across time. Repeatedly multiplying a hidden state by a transition matrix made memories vanish. The recent linear-recurrence literature, built so recurrent models could train in parallel like attention, fixed this by designing transitions whose eigenvalues sit near magnitude one and never exceed it. This proposal treats network depth in a graph network the way those models treat time. It builds a graph layer from the same ingredient: an error-correcting "delta rule" step whose mixing operator is signed, norm-bounded, and continuously driven by the input. It also asks whether this escapes a known impossibility result for attention-based graph networks.
That result is the reason the opportunity exists now. Demystifying Oversmoothing in Attention-Based Graph Neural Networks proves that graph attention only slows exponential collapse and cannot stop it. The proof needs softmax weights that are nonnegative, sum to one over each neighborhood, and are strictly positive on every edge. The efficient-attention line drops exactly these properties for speed. Parallelizing Linear Transformers with the Delta Rule over Sequence Length uses state transitions that are generalized reflections with eigenvalues in [-1, 1]. No one has checked whether softmax-free, error-correcting aggregation inherits the collapse. If it does not, we get deep graph models that keep node identity, need no softmax, and cost one sparse multiply per layer.
Core Claim
We propose a graph layer in which each node corrects its state toward a prediction from its neighbors. The correction uses a step size chosen per node by a small gating network, and a fresh injection of the input features is added at every layer:
$$X^{(\ell+1)} = \big(I - B^{(\ell)}(I - P^{(\ell)})\big)\,X^{(\ell)} + X^{(0)}U_\ell .$$
Here $X^{(\ell)}$ is the node-feature matrix at layer $\ell$ and $P^{(\ell)}$ is a nonnegative, normalized, edge-supported mixing matrix whose weights come from a sigmoid-gated similarity rather than a softmax. $B^{(\ell)} = \mathrm{diag}(\beta_i)$ holds input-dependent per-node step sizes, and $U_\ell$ is a learned projection of the input $X^{(0)}$. The step sizes are bounded so that the mixing operator has norm at most one, which allows values above the "plain averaging" point $\beta=1$. This plays the role that the range $\beta\in(0,2)$ plays in DeltaNet's reflections. When $\beta_i > 1$ the node overshoots its neighborhood mean, the diagonal turns negative, and the operator stops being stochastic, so Wu et al.'s theorem no longer applies.
The input-injection term keeps the system driven rather than a pure matrix product. We borrow this from the linear recurrent unit design in Resurrecting Recurrent Neural Networks for Long Sequences, which interleaves linear transitions with position-wise nonlinear layers. Following that paper, we keep transitions linear across blocks of layers and place nonlinear networks between blocks. This keeps the depth dynamics exactly analyzable.
Three properties could each break collapse: signed mixing, input drive, and node-dependent selectivity. The central scientific claim is that we can measure which of them is responsible, and that their combination matches graph transformers on tasks needing very long-range propagation at the cost of local message passing.
Relation to Prior Work
Wu et al. motivate and constrain the work. Their joint-spectral-radius argument tells us which assumption to violate and gives us a proof template for the inhomogeneous, time-varying products we must analyze. The linear recurrent unit paper and DeltaNet supply the method: stability by eigenvalue parameterization rather than by normalization. Both are confined to one-dimensional sequences, and we transfer their transition design to the depth axis of a graph network.
The closest existing work is Mamba-Based Graph Convolutional Networks: Tackling Over-smoothing with Selective State Space, which already places selective state-space transitions inside deep graph convolution. It provides no frequency-response or collapse analysis, and the research file contains no reported numbers for it. Our proposal differs in three ways. It uses a specific softmax-free, norm-bounded, signed operator chosen so that a non-collapse statement can be proved. It isolates the three candidate mechanisms by ablation. It evaluates on ECHO's very long-range tasks with wall-clock cost.
Graph Signal Processing Meets Mamba2: Adaptive Filter Bank via Delta Modulation shows that multi-head state-space models collapse into redundant low-pass filters on one-dimensional line graphs. It supports our premise that step-size modulation controls frequency response, but it never leaves the line graph.
Two filterbank papers show that keeping high-frequency signal rescues heterophilic graphs. Complete the Missing Half adds a high-pass channel with scalar mixing weights. Geometric Scattering Attention Networks attends over precomputed scattering wavelets. Our overshooting step realizes a learned, per-node high-pass response without precomputed filters, and that makes these two papers the most dangerous comparison.
Research Program
The theoretical part extends Wu et al. to driven, signed operators. First we characterize the joint spectral radius of the family of mixing operators on the subspace orthogonal to the dominant mode, as a function of the allowed step-size range. Second we show that with input drive the representation stays within a bounded distance of an input-dependent fixed point whose rank is bounded below by the rank of the projected input, so it cannot converge to rank one. Third we identify when the undriven, signed-only operator still collapses. We expect it to: on a non-bipartite graph the most negative eigenvalue of the mixing operator stays above -1 unless the step size is tuned to the spectrum, so signedness alone should preserve only a few extreme-frequency modes. If the theory confirms this, input drive is the real mechanism, and selectivity matters only for where the fixed point lies. We will state that plainly rather than credit the delta rule.
The engineering part implements the layer with sparse kernels at cost proportional to edges times feature width per layer, with no softmax. It also adds an optional global branch: a bidirectional linear-attention memory updated by one permutation-invariant delta-rule regression step over all nodes, at cost linear in the number of nodes. This branch tests whether a softmax-free global channel addresses over-squashing, the distinct failure where information is lost at narrow bottlenecks, which local depth cannot fix. It is kept separate so that the main claims about over-smoothing do not depend on it.
The diagnostic part sweeps depth from 2 to 128 layers. At every layer it tracks Dirichlet energy, a measure of how much features differ across edges, and effective rank, using the measurement guidance of Are we measuring oversmoothing in graph neural networks correctly?. This tests directly whether accuracy failures on long-range benchmarks coincide with representational collapse or with optimization problems.
Baselines
The naive reference is a standard graph convolutional network with residual connections at matched depth. On ECHO-Synth single-source shortest path, Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation reports 2.102 MAE for it.
The strongest accuracy competitor on long-range propagation is the GRIT graph transformer, reported at 0.121 MAE on that task in the same paper. On ECHO-Energy, GPS is reported at 5.257 MAE. Both use full softmax attention, which is the very thing whose cost and collapse we want to avoid.
The strongest cost competitor is the non-dissipative differential-equation family. SWAN is reported at 6.109 × 10⁻³ MAE on ECHO-Charge, and A-DGN is reported at roughly 12.8 seconds per epoch against roughly 788 for GPS.
On LRGB the strongest baselines are the tuned message-passing networks of Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. That paper reports a tuned GCN at 0.2460 MAE on Peptides-struct and a tuned GatedGCN at 0.3880 macro F1 on PascalVOC-SP.
On heterophilic node classification the strongest file-reported result is GSAN at 61.2% on Chameleon. FB-GCN is reported as roughly 10% better than GCN on Texas and Cornell, with no absolute figure in the file. ReHub is relevant as a linear-cost global model, but the file reports only rankings ("top two" on Peptides-func), not numbers. For MbaGCN the file has no reported result; we will rerun it from its description where possible.
For fairness, every model gets the tuned recipe from the Where Did the Gap Go paper: a multi-layer prediction head, normalization, and warmup with cosine learning-rate decay. Every model also gets the same parameter budget per benchmark (the LRGB 500k convention), the same number of hyperparameter trials, and the same seeds and splits. Wall-clock time is measured on identical hardware.
The ablations that isolate the key ingredient each remove one property while keeping the rest. The first fixes step sizes at or below 1 (unsigned, stochastic). The second fixes step sizes at a constant above 1 (a static high-pass filter, essentially a filterbank patch). The third removes input injection. The fourth replaces the sigmoid-gated mixing with softmax.
Beating the field means two things. On ECHO-Synth and ECHO-Charge, we must come within GRIT's error range while running at differential-equation-network cost, and not lose to SWAN. On Peptides-struct and PascalVOC-SP, we must at least tie the tuned message-passing numbers.
Why not just…?
Why not just tune a classic GCN with an MLP head? On LRGB this may well be enough, and we expect at best a tie on Peptides-struct against 0.2460 MAE. ECHO is the setting where tuning has not been shown to help, since a GCN there sits at 2.102 MAE against 0.121 for GRIT. Our depth sweep will show whether that gap tracks measured collapse. If a tuned GCN closes most of the ECHO gap under our identical recipe, the over-smoothing story is wrong for these tasks and we will report that.
Why not just add a static high-pass channel, as in FB-GNN? This is a real threat, because an overshooting step with a constant step size is close to a fixed high-pass filter. The fixed-step ablation answers it directly. If constant overshoot matches node-dependent overshoot on Chameleon, Texas, Cornell, and ECHO, the selective part adds nothing, and the contribution reduces to the theory and the input-drive finding.
Why not just use a non-dissipative differential-equation GNN such as A-DGN or SWAN? These already avoid collapse cheaply, and SWAN's ECHO-Charge result is strong. The distinction is mechanism. They keep information by constraining feature-space weight matrices so the dynamics conserve energy. We do it through the spectrum of the node-mixing operator plus input drive, without an ODE solver. Whether that difference matters empirically is unknown, so the head-to-head on ECHO-Charge and ECHO-Energy at matched epochs and time is decisive. Losing on both accuracy and cost would argue against the method.
Why not just keep softmax graph attention with residual connections, or use ReHub? Wu et al. prove softmax aggregation only delays collapse. The softmax-swap ablation tests whether that delay, combined with residuals, is already adequate at the depths ECHO needs.
Proposed Experiments
The decisive check comes first and is the depth sweep. For each ablation we plot Dirichlet energy and effective rank against depth on ECHO-Synth line, ladder, tree, and lobster graphs. The theory predicts exponential decay for the softmax and unsigned variants and a nonzero floor for the input-driven variants. A floor that appears only with signed steps would support the delta-rule framing. A floor that appears with input drive alone would show that the mechanism is driving the recurrence, not the delta rule.
Second, we train at the hop counts ECHO requires and report MAE on the shortest-path, eccentricity, and diameter tasks, ECHO-Charge, and ECHO-Energy, with seconds per epoch, against GRIT, GPS, SWAN, and A-DGN.
Third, we run the LRGB suite (Peptides-func, Peptides-struct, PascalVOC-SP, COCO-SP, PCQM-Contact) under the tuned recipe. PCQM-Contact, where local message passing is reported to fail and transformers excel, is the test that motivates the optional global delta-rule memory. We report results with and without that branch.
Fourth, we run heterophilic and homophilic node classification (Chameleon, Texas, Cornell, Wisconsin, Cora, CiteSeer, PubMed) and Flickr for scale, against GSAN and FB-GCN.
The proposal succeeds if the depth sweep shows a non-collapsing floor that tracks the predicted mechanism and ECHO accuracy approaches GRIT at differential-equation-network cost. It fails informatively if tuned message passing or static high-pass filtering matches it.
References
- Demystifying Oversmoothing in Attention-Based Graph Neural Networks
- Parallelizing Linear Transformers with the Delta Rule over Sequence Length
- Resurrecting Recurrent Neural Networks for Long Sequences
- Pointsoup: High-Performance and Extremely Low-Decoding-Latency Learned Geometry Codec for Large-Scale Point Cloud Scenes
- Graph Signal Processing Meets Mamba2: Adaptive Filter Bank via Delta Modulation
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Geometric Scattering Attention Networks
- Are we measuring oversmoothing in graph neural networks correctly?
- Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation
- Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark