Graph neural networks pass messages between neighboring nodes. Each layer sees only one hop further, so capturing distant interactions requires many layers. But deep stacks suffer from over-smoothing: node representations blur together until neighbors are indistinguishable, which destroys any label that changes sharply across edges. The common fix for limited reach is a global shortcut. Examples include a virtual node (an extra node wired to every other node), full self-attention, and hub-and-spoke routing. Papers in this area often credit these shortcuts with relieving over-smoothing as well as limited reach.
We argue this credit is misplaced. Any global channel that sends the same information to every node cannot create differences between nodes. At most it can amplify differences that already exist, by a factor set by the network's Lipschitz constant (a bound on how much the output can change when the input changes). The only thing that restores lost node distinctiveness is a per-node anchor: a signal that differs from node to node and is re-injected at every layer. Two examples are the raw input features and a symmetry-respecting structural encoding such as eigenvector features. We propose to prove this as an extension of an existing approximation lower bound. We will then test its sharpest prediction: on graphs whose input features carry no node-distinguishing information, only structural anchors with sufficient separating power let deep models fit high-frequency targets. Shortcuts and feature-based anchors should not.
Core Claim
Bridging Smoothness and Approximation supplies the starting point. It proves that a deep graph convolutional network's error on a target is bounded below by the target's modulus of smoothness, a measure of how much the target varies across edges. The reason is that high-frequency components decay as $|\mu_{high}|^{2K}$ with depth $K$. The authors restrict this result to isotropic polynomial filters and explicitly leave out virtual nodes and attention. Two other papers provide motivation. Understanding Virtual Nodes reports that standard virtual nodes accelerate homogenization. On the Connection Between MPNN and Graph Transformer reports empirical relief on long-range benchmarks. Taken together, these findings are confusing, and the open question is whether shortcuts remove the smoothness floor or only shift it.
Our central lemma uses the unnormalized Dirichlet energy $E(H)=\tfrac12\sum_{(i,j)\in\mathcal{E}}\|h_i-h_j\|^2$, which sums squared differences between connected node states $h_i$. Consider a generic layer $h_i'=\phi(h_i, m_i, g, a_i)$, where $m_i$ is the local neighbor aggregate and $g$ is any quantity shared by all nodes. Examples of $g$ include a virtual-node state, a pooled broadcast vector, or the entire state matrix $H$ in self-attention. The last term, $a_i$, is a per-node anchor. If $\phi$ has Lipschitz constants $L_h, L_m, L_a$ in its three node-specific arguments, then
$$E(H') \le 3\left(L_h^2\,E(H) + L_m^2\,E(M) + L_a^2\,E(A)\right),$$
because $g$ cancels in every difference $h_i'-h_j'$ and $(a+b+c)^2\le 3(a^2+b^2+c^2)$. Softmax attention fits this template. Each node's output is a function of its own query state and the shared $H$, so per-node attention weights differ only as far as node states already differ.
Three consequences follow, and they are the claims we will test.
First, without anchors, any global architecture can regain high-frequency energy only through large Lipschitz constants. Large constants are exactly the regime where Backward Oversmoothing locates exploding gradients. Under a fixed Lipschitz budget, Yang et al.'s floor therefore carries over to virtual nodes, graph transformers and hub routing.
Second, with anchors, deep high-frequency content is limited to Lipschitz functions of the anchor. The separation–approximation equivalence of Chen et al. and Azizian & Lelarge then implies that a non-smooth target is reachable at depth only if the anchor separates the nodes the target separates.
Third, feature anchors are useless when input features are uninformative, for instance on regular graphs with constant features. In that case only structural anchors help. Sign- and basis-invariant eigenvector encodings (SignNet/BasisNet) are the natural choice because they preserve permutation invariance.
The new elements are the extension of the lower bound to global architectures and the reframing of over-smoothing remedies as a question about anchor separating power. We do not claim a new routing operator.
Research Program
The theory work has three parts.
First, we will prove the lemma above for normalized and unnormalized energy. We will instantiate it for MPNN+virtual node, for GPS-style attention, and for the hub-and-spoke design of ReHub.
Second, we will combine the lemma with Yang et al.'s K-functional argument to obtain an explicit error lower bound. The bound will be stated in terms of depth, the Lipschitz budget and the high-frequency energy of the target, for anchor-free global models.
Third, we will prove a matching positive statement. A model that re-injects anchor $A$ at every layer can, at any depth, approximate any target that is a continuous function of $A$'s equivalence classes, uniformly in graph size. We will state this in the uniform sense of Distinguished In Uniform, because non-uniform guarantees can mask exactly this failure.
The empirical work makes the theory measurable. We will log per-layer Dirichlet energy in two forms: raw, and after projecting out the span of the anchor. This responds to the concern in Are we measuring oversmoothing correctly? that raw energy confuses collapse with ordinary training dynamics. We will also log each trained model's empirical Lipschitz constants, so that architectures can be compared at matched budgets. The anchored model itself is deliberately simple. It is the same backbone with a projection of $A$ concatenated into every layer's update. Its global channel is ablated in or out. Anchor choices are raw features, SignNet eigenvector encodings, or random node features. Random features are included as a control because they separate nodes but are invariant only in distribution.
Baselines
The naive reference is a shallow, well-tuned message-passing network with an MLP head, normalization and AdamW with cosine annealing, following Where Did the Gap Go?. That paper reports a test MAE of 0.2460 on Peptides-struct with a GCN and a macro F1 of 0.3880 on PascalVOC-SP with a GatedGCN. These are the numbers any deep model must at least match. Matching them shows the anchored model is not worse. Our theory makes predictions only about depth and high-frequency targets, so we do not expect to beat these numbers by a wide margin on LRGB.
The strongest global-shortcut competitors are MPNN+virtual node (Cai et al.), the structure-aware $VN_G$ (Southern et al.) and ReHub. They are strongest because each is the published answer to limited reach at linear cost. The file gives no absolute numbers for them on LRGB: no reported result found on Lacuna for GatedGCN+VN on Peptides-func/struct, nor for ReHub on any LRGB task. We will therefore rerun all three ourselves. Every model gets the same backbone, the same tuning protocol, a parameter budget near 500k and an equal number of hyperparameter trials.
Against over-smoothing specifically, we include three baselines. The first is PROXYDELETE, which reports 0.2470 MAE on Peptides-struct and lifts GCN on Roman-Empire from about 70% to about 78%. The second is HES from The Snowflake Hypothesis, which reports 23.96 accuracy for a 16-layer GCN on Squirrel versus 4.00 for DSpar. The third is UniFilter, which reports gains of 6.38% on Squirrel over prior methods. We also run APPNP and GCNII, because their initial-residual connection is a raw-feature anchor. No reported result found on Lacuna for GCNII or APPNP accuracies.
Beating a baseline means one of two things. On the symmetric synthetic tasks, it means lower error at depth 16–32 with a matched Lipschitz budget. On real benchmarks, it means accuracy that stays flat with depth while baselines fall, with no loss at shallow depth.
The key ablations isolate the anchor. We compare global channel without anchor, anchor without global channel, and both together. We also swap the anchor's type while holding everything else fixed.
Why not just…?
Why not just tune a shallow network? On LRGB this is a real threat. The tuned GCN at 0.2460 MAE already beats rewiring and transformers. We accept this result. It does not address targets whose variation across edges survives only at depth, and on those targets Yang et al.'s bound is unaffected by tuning. Our synthetic stochastic-block-model tasks with a controllable high-frequency label component will show whether shallow models fail when the required interaction distance exceeds their depth. If they do not fail, the practical case for depth weakens, and we will report that.
Why not just add a virtual node or attention? The lemma predicts that, at a matched Lipschitz budget, the depth–energy curve of these models should track their local backbone. The effect of a shortcut should then be confined to reach, as with commute time, and should not touch smoothing. This is directly falsifiable from our energy logs. If MPNN+VN keeps anchor-projected energy high without large weights, the lemma's practical relevance is refuted.
Why not just use GCNII or APPNP's initial residual? This is the most serious alternative, because it is an anchor. On feature-rich benchmarks such as Roman-Empire and Squirrel, we expect it to match anchored global models. The prediction that separates the two approaches is on constant-feature regular graphs (CSL-style) and on node tasks over random regular graphs. There, a raw-feature anchor carries zero energy, so the bound forces collapse. A SignNet anchor should still separate nodes. If GCNII succeeds there, our theory is wrong.
Why not just normalize (PairNorm) or add plain residuals? PairNorm is a shared rescaling. Under the lemma it raises energy only by amplifying existing differences, noise included. This is consistent with Elinas & Bonilla finding that PairNorm degraded deep-supervised models. It is also consistent with Yang et al. showing that ResGCN still decays at depth. We include both as baselines rather than argue the point.
Proposed Experiments and Decisive Checks
The decisive synthetic test has three parts. First, we train every model at depths 2 to 32 on stochastic-block-model graphs with targets of graded modulus of smoothness. Second, we train on CSL and on random regular graphs with constant features. On CSL, Chen et al. report that GIN reaches only 10% while Ring-GNN reaches 80%. Third, we train on the Square-function and $G_{l,r}$ tasks from Rosenbluth et al., evaluated on graph sizes beyond the training range.
The theory makes three predictions here. Anchor-free shortcut models should fit high-frequency targets only when their measured Lipschitz constants grow, with training instability following. Feature anchors should succeed on stochastic-block-model graphs and fail on constant-feature regular graphs. SignNet anchors should succeed on both wherever eigenvector invariants separate the target.
On real data we run Squirrel, Chameleon, Roman-Empire and Amazon-Ratings at 2–16 layers, and Peptides-func, Peptides-struct and PascalVOC-SP from LRGB. We additionally run ZINC, where PNA+SignNet reports 0.084 MAE, as a check that structural anchoring does not hurt graph-level regression.
We will report task metrics, anchor-projected energy per layer and Lipschitz estimates. The proposal fails if global shortcuts preserve energy without anchors at matched budgets. It also fails if SignNet anchoring gives no advantage over feature anchoring on symmetric graphs.
References
- Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks
- Understanding Virtual Nodes: Oversmoothing, Oversquashing, and Node Heterogeneity
- On the Connection Between MPNN and Graph Transformer
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?
- On the equivalence between graph isomorphism testing and function approximation with GNNs
- Expressive Power of Invariant and Equivariant Graph Neural Networks
- Sign and Basis Invariant Networks for Spectral Graph Representation Learning
- ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment
- Distinguished In Uniform: Self-Attention Vs. Virtual Nodes
- Are we measuring oversmoothing in graph neural networks correctly?
- Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
- The Snowflake Hypothesis: Training and Powering GNN with One Node One Receptive Field
- How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing
- Revisiting Over-smoothing in Graph Neural Networks
- Long Range Graph Benchmark