Making Over-Smoothing Harmless: Feature-Augmented Graphs with Exact-Zero Neighbor Gates

Graph neural networks (GNNs) classify nodes by repeatedly averaging each node's features with those of its neighbors. Stack enough of these averaging steps and every node in a connected graph ends up with the same representation, a failure called over-smoothing. Two other problems make this worse. Many real graphs are heterophilic, meaning edges often join nodes of different classes, and many are sparse, leaving some nodes with no useful neighbors at all. A common fix for sparsity is feature-based augmentation: add edges between nodes whose attributes look alike, for example through a k-nearest-neighbor (kNN) graph in feature space. But added edges make the graph more connected, and theory says greater connectivity speeds up collapse. Learned neighbor weights such as attention do not rescue this. They provably only slow the collapse, because softmax gives every existing edge a strictly positive weight.

This note argues that the goal should not be to stop smoothing but to aim it. If the propagation operator, built over the union of original and feature-similarity edges, assigns exactly zero weight to edges that cross class boundaries, then deep propagation does not collapse to a single point. It converges to one consensus value per class-aligned component, which is the behavior a classifier wants. The proposal builds such an operator with exact-zero neighbor gates trained end to end. It also derives a simple, measurable quantity, the operator's cross-class leakage, that predicts how deep a model can usefully go. The regime where this matters is label-scarce, sparse graphs, where information must travel many hops and shallow models cannot reach it.

Core Claim

Let $P_\ell$ be the row-normalized propagation matrix at layer $\ell$, defined over original plus feature-kNN edges with learned nonnegative weights. Partition nodes into the components of the graph that keeps only the edges the gates leave nonzero. Write $\varepsilon$ for the largest per-row weight mass a node sends outside its own component, and $\lambda_w$ for the largest second eigenvalue of the within-component blocks. The disagreement of a node with its component consensus then shrinks roughly like $\lambda_w^{t}$ after $t$ layers. Cross-component collapse cannot start until the accumulated leakage $t\varepsilon$ is of order one. This follows from a standard perturbation argument on products of nearly block-diagonal stochastic matrices. The predicted useful depth window is therefore

$$\frac{\log(1/\delta)}{1-\lambda_w} \;\lesssim\; t \;\lesssim\; \frac{c}{\varepsilon},$$

where $\delta$ is the target within-component agreement and $c$ is a constant.

With $\varepsilon = 0$ the upper limit disappears. The infinite product converges to a matrix whose rank equals the number of components, not one. This is exactly the escape from the rank-one collapse proved for softmax attention in Demystifying Oversmoothing in Attention-Based Graph Neural Networks, whose Lemma 2 relies on strictly positive weights.

The claim has two parts. First, a feature-augmented graph whose gates can output exact zeros will turn deep propagation into useful long-range label spreading on sparse, label-scarce graphs. Second, measured $\varepsilon$ and $\lambda_w$ of the learned operator will predict where accuracy peaks and where it falls off.

Relation to Prior Work

Several papers motivate the gap. Wu et al. (Demystifying Oversmoothing) model attention GNNs as time-varying dynamical systems and prove that collapse continues under attention. They propose no constructive escape and do not consider augmented edges, which is the case we study. Two Sides of the Same Coin shows that heterophily and over-smoothing share a cause: cross-class mixing, including "pseudo-heterophily" from nodes misclassified at intermediate layers. Our leakage $\varepsilon$ is a direct, operator-level measure of that mixing. Are we measuring oversmoothing in graph neural networks correctly? notes that standard metrics cannot separate harmless class-level clustering from global collapse. We adopt a class-aware measure for that reason.

Other papers supply pieces we reuse or contrast against. AM-GCN (AM-GCN) builds a static cosine kNN graph beside the topology graph and fuses shallow channels with attention. We borrow the kNN channel but make edge weights learnable down to exactly zero, and we study depth, which AM-GCN does not. DHGR (Make Heterophily Graphs Better Fit GNN) adds homophilic edges and removes heterophilic ones as a fixed preprocessing step, using Ball-Tree top-K search, which we reuse for scalability. It relies on training-label statistics, so it should weaken exactly in the label-scarce regime we target. GRAPHITE (Graph homophily booster) raises homophily through hubs for discrete features and does not study depth. Our kNN construction covers continuous features.

The closest competitors in mechanism also define what we do not do. DYNAMO-GAT (A Dynamical Systems-Inspired Pruning Strategy) prunes correlated attention edges to zero, but only on the original topology, and its authors flag sparse graphs as a risk. Our method prunes cross-class edges and adds within-class ones, so sparse graphs are the target rather than a failure case. SBP (A Signed Graph Approach) prevents collapse through calibrated repulsive negative edges and shows a narrow stability band. We choose zeros over negative weights deliberately, because zeros cannot cause divergence. Comparing the two is part of the program. MTGCN (Multi-Track Message Passing) also blocks cross-class mixing by routing messages along category-specific tracks. It costs memory linear in the number of classes and never adds edges. Our gates achieve separation inside one operator.

Finally, one paper constrains the whole evaluation. A critical look at the evaluation of GNNs under heterophily shows that duplicate-node leakage inflated many heterophily results. It also shows that simple ego-neighbor separation, meaning keeping a node's own features apart from its aggregated neighbors, beats most specialized designs. Every comparison here therefore runs on its de-duplicated benchmarks, and every model gets ego-neighbor separation.

Research Program

The model starts from a candidate edge set: the original edges plus a kNN graph computed with approximate nearest-neighbor search over input features. Both sets are refreshed every few epochs using learned embeddings, so the edges are no longer fixed at preprocessing time.

Each candidate edge receives a gate computed from the two endpoint embeddings, as in Graph Attention Networks. The scores are normalized with sparsemax rather than softmax, so the gate can output exactly zero. Gates are shared across blocks of layers. Shared gates keep the operator close to time-invariant, which makes the measured $\varepsilon$ and $\lambda_w$ meaningful. Ego-neighbor separation and a light residual connection are applied in every variant, including the baselines, so that the gate is the only difference being tested.

A small auxiliary loss pushes down the gate mass on edges whose endpoints are confidently predicted to be in different classes. Because it uses predictions and not labels, it stays usable when labels are scarce.

The analysis side has three parts. We formalize the depth window above. We compute $\varepsilon$ (with respect to both the true classes and the learned components) and $\lambda_w$ from the trained operator. We then test whether these quantities predict the shape of each accuracy-versus-depth curve.

Baselines

The naive reference points are an MLP and a residual MLP that ignore the graph. They matter because Graph homophily booster reports that on Actor, 23 recent specialized GNNs fail to beat a basic MLP. A gain over a well-tuned MLP is the minimum bar on every dataset.

The strongest existing method on de-duplicated data is a GAT or GraphSAGE with ego-neighbor separation and residuals, as recommended by A critical look at the evaluation of GNNs under heterophily. It is the strongest competitor because it took most of the top places on the filtered benchmarks with no rewiring at all. No absolute numbers for these baselines were found on Lacuna, so we rerun them. We train them shallow and at matched depth, and give them the same tuning budget as our model.

The deep-propagation competitors are SBP and DYNAMO-GAT. The file reports SBP at roughly 80% Cora accuracy at 300 layers, against GCN below 30% (A Signed Graph Approach). It reports DYNAMO-GAT at 75.3% on ogbn-products, against 73.9% for G2GAT (DYNAMO-GAT).

The augmentation competitors are AM-GCN, DHGR followed by a GCN, and GRAPHITE where features are discrete. For GRAPHITE the file gives only relative figures (a 5.35% gain on Chameleon-F) and no absolute accuracy, so we rerun it.

Two ablations isolate the key ingredient, the exact-zero gate on the augmented graph:

  1. The same candidate graph with softmax gates. This tests whether exact zeros matter.
  2. The original graph with sparsemax gates. This tests whether the added edges matter.

All runs share data splits, label rates, a fixed hyperparameter search budget per model, and comparable GPU time. Beating the strongest baseline means a statistically significant gain over the tuned ego-separated GNN, measured over 10 splits. That gain must appear at label rates of 5% or below on at least four of the filtered heterophily datasets. We must also show no loss on Cora, CiteSeer, and PubMed.

Why not just…?

Why not just use a shallow ego-separated GNN? This is the real threat. At standard label rates it may well match us, since Platonov et al. show it is hard to beat. Our claim is specifically about label scarcity and sparse or stray nodes, where two hops cannot reach a labeled node. The label-rate sweep settles the question. If the shallow model matches us at 1–5% labels, the depth argument fails and we will report that.

Why not just run label propagation or APPNP on a static kNN graph? If feature similarity already separates the classes, plain diffusion over a fixed kNN graph performs a clustering-like spreading with no learning at all. We include this as a baseline, together with a correct-and-smooth style post-processing step. The prediction that separates the two approaches is that a static kNN graph has larger $\varepsilon$ than the learned gates, especially on Roman-Empire and Minesweeper, where raw features are weak. If the measured leakages are equal and accuracies match, the learned gate is unnecessary.

Why not just add normalization or residuals, or use signed edges as SBP does? SBP's own analysis treats normalization and residuals as implicit negative edges and outperforms PairNorm and ContraNorm on 8 of 9 datasets. So the signed approach is the competitor that matters, not normalization alone. We run SBP on the same augmented candidate graph. If repulsion matches exact zeros in accuracy, we additionally compare stability across depth and learning rate, where SBP's threshold result predicts a narrower usable region.

Proposed Experiments

The datasets are Roman-Empire, Amazon-Ratings, Minesweeper, Tolokers, Questions, Chameleon-F, Squirrel-F, Actor, Cora, CiteSeer, PubMed, and ogbn-arxiv for scale. We use the metrics from A critical look at the evaluation of GNNs under heterophily for its datasets and accuracy elsewhere. We sweep label rates over 1%, 5%, 20%, and the standard split. We also run a variant where 30% of original edges are removed, following the edge-removal setting of Li Shu et al.. Depth ranges from 2 to 128 layers.

Over-smoothing is measured with a class-aware ratio of between-class to within-class representation distance, per Are we measuring oversmoothing in graph neural networks correctly?.

Two checks decide the project:

  1. Does the depth window predict the curves? Across datasets and ablations, the measured $1/\varepsilon$ of each trained operator should correlate with the depth at which its accuracy begins to fall. The softmax-gate ablation should show a finite window that shrinks as edges are added. The sparsemax model should show a plateau instead. If the window does not predict the curves, the mechanism is wrong even if accuracy improves.
  2. Does the gain survive the hardest baselines in the target regime? At low label rates, the full model must beat both the tuned shallow ego-separated GNN and static-kNN label propagation. The gain should be concentrated on nodes with zero labeled nodes within two hops, which is the subgroup the claim predicts should benefit.

A clean negative result on either check would still be informative. It would show that feature augmentation without exact-zero gating speeds up collapse, as the theory of Wu et al. implies, or that depth adds nothing once ego separation is in place.