Over-Smoothing as a Temperature Problem in Graph Attention

Graph neural networks compute each node's representation by averaging messages from its neighbors, then repeat that step layer after layer. Stack enough layers and every node ends up with nearly the same vector, so the network can no longer tell nodes apart. This failure is called over-smoothing. Our observation is that the averaging step behaves like a soft version of a discrete choice: "which neighbors should this node listen to?" The softness of that choice is set by a temperature. A uniform average is the high-temperature extreme. Hard selection of a few neighbors is the low-temperature extreme. The well-studied trade-off for soft sorting and soft top-$k$ operators then carries over directly. High temperature gives smooth, well-behaved gradients but blurs the output. Low temperature is faithful to the discrete choice but has gradients that vanish or spike. Over-smoothing, on this view, is what the high-temperature end of that trade-off looks like when it is repeated across many layers.

We propose to make that temperature explicit in every message-passing layer, to anneal it during training from soft to sharp, and to test whether this one control can address two problems at once. The first is forward over-smoothing, the collapse in the rank of the representations. The second is backward over-smoothing, in which gradients flowing back through the layers are averaged into a constant and the internal layers stop learning. If the claim holds, deep graph networks become trainable through a schedule borrowed from differentiable optimization. Doing so needs no new normalization layer, no auxiliary loss at every layer, and no offline graph surgery.

Core Claim

Neighbor aggregation with a softmax over neighbors (as in graph attention) is a continuous relaxation of top-$k$ neighbor selection. Its contraction of feature differences is governed by the temperature $\tau$. Let $P_\tau$ be the row-stochastic aggregation matrix, so each row holds one node's weights over its neighbors. Write $\delta(P_\tau) = \tfrac12 \max_{i,j} \sum_k |P_{\tau,ik} - P_{\tau,jk}|$ for its Dobrushin coefficient. This coefficient bounds how much the spread between any two nodes' features can shrink in one aggregation step. With attention logits bounded in $[-B, B]$, every neighbor weight satisfies

$$P_{\tau,ik} \;\ge\; \frac{e^{-2B/\tau}}{d_i},$$

where $d_i$ is the degree of node $i$. Strictly positive overlap between rows is exactly what drives $\delta < 1$ and hence collapse over depth. As $\tau \to 0$ this lower bound vanishes, and hard-selection rows can have $\delta = 1$, meaning no guaranteed contraction. The same coefficient governs the transposed matrix that carries gradients backward.

High $\tau$ therefore causes both forward collapse and backward gradient smoothing. Low $\tau$ avoids both but saturates the softmax, so the gradient with respect to which neighbors to select dies. A schedule that starts soft, while neighbor selection is being learned, and ends sharp, once it is fixed, should get through this window. Neither fixed endpoint can. This is a hypothesis to be tested empirically. The inequality motivates it but does not prove it.

Relation to Prior Work

Two papers motivate the problem framing. Are we measuring oversmoothing in graph neural networks correctly? shows that effective rank tracks accuracy (average Pearson correlation 0.91), unlike the older measure, Dirichlet energy, which sums squared differences between neighboring features. It also proves rank collapse for linear and non-negative networks. We use effective rank as our forward diagnostic. We do not use it as a training penalty, because that paper also notes that random noise has maximal rank, so pushing rank up directly can reward noise. Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? shows that gradients are also smoothed by message passing, which creates spurious stationary points where internal layers freeze. Our claim is that the temperature is the knob shared by the forward and backward versions of the problem.

Three papers supply the method. DFWLayer: Differentiable Frank-Wolfe Optimization Layer uses a temperature-controlled softmax for vertex selection and shows that a cooling schedule $\tau_k = 2^{-\lfloor k/T \rfloor}$ is needed to move from stable gradients to exact solutions. We adapt this schedule to training epochs and to depth. SoftJAX & SoftTorch: Empowering Automatic Differentiation Libraries with Informative Gradients provides soft top-$k$ operators. It also warns that wrapping individual functions in straight-through estimators, which apply the hard operation forward and pass soft gradients backward, causes vanishing gradients under multiplicative interactions. Message passing stacks exactly such interactions, so we wrap the whole aggregation step rather than its pieces.

The closest prior work is Probabilistic Task-Adaptive Graph Rewiring. It learns which edges to add or delete with differentiable $k$-subset samplers, then feeds one rewired graph to a downstream network. It treats the sampler's relaxation sharpness as a black-box constant and never connects it to rank collapse. We differ in three ways. Our relaxation is the aggregation inside every layer rather than one upstream rewiring. The temperature is the object of study rather than a fixed setting. And we measure its effect on both forward rank and backward gradient flow.

GraTO (GraTO) also relies on a softmax relaxation, but over architecture choices, and it fights smoothing with a label-dependent penalty on similarity between nodes of different classes. Our method needs no labels in the anti-smoothing mechanism.

Finally, some prior work constrains our design. Revisiting Over-smoothing in Graph Neural Networks shows that stacking fixes can backfire: PairNorm combined with deep supervision did worse than deep supervision alone. So we test composition with our method explicitly rather than assuming it helps.

Research Program

We build a layer that, for each node, scores its neighbors with an attention function. It then applies a soft top-$k$ relaxation at temperature $\tau_\ell(t)$, which depends on the layer $\ell$ and training step $t$, and always includes a self-loop. At the final temperature it reduces to hard selection of $k$ neighbors. We study three schedules. The first is a global exponential cooling schedule in the style of DFWLayer. The second is depth-staggered, with deeper layers cooling later, because deeper layers are where backward smoothing starves updates first. The third is rank-triggered: a layer's temperature drops when its effective rank on a held-out batch falls below a threshold. This third variant uses rank as a control signal rather than a loss term, which sidesteps the "noise has maximal rank" objection.

The analysis has two parts. First, we sweep fixed $\tau$ at each depth and record three quantities layer by layer: effective rank, the gradient norm reaching each layer's weights, and the entropy of the attention weights. The aim is to show that over-smoothing tracks temperature. Second, we check whether the empirical contraction per layer follows the Dobrushin bound as $\tau$ varies.

Baselines

The naive reference points are a plain graph convolutional network and plain graph attention at depths from 2 to 64. We include the shallow 2–4 layer models because, on Cora and Citeseer, Revisiting Over-smoothing in Graph Neural Networks reports that they still achieve the highest absolute accuracy. Any deep model must be measured against that.

For depth on citation graphs, the strongest competitor is deep supervision (DSGNN) from the same paper. It attaches a classifier to every layer and averages their losses, and it reports 77.5% accuracy on Pubmed at 12 layers and 77.1% at 10 layers with missing features. Beating it means higher Pubmed accuracy at 12 or more layers without per-layer labels. Matching it while using no per-layer supervision would still be informative, because that supervision is unavailable in unsupervised and link-level settings.

PairNorm (PairNorm: Tackling Oversmoothing in GNNs) centers and rescales features to keep pairwise distances constant. It is the strongest baseline in the missing-feature regime, where a PairNorm-enhanced simplified graph convolution reaches 74.5% on Cora versus 42.3% for the vanilla version.

For heterophilic and long-range tasks, the strongest topology-based competitor is PROXYDELETE (Spectral Graph Pruning Against Over-Squashing and Over-Smoothing). It deletes edges offline using spectral estimates and reports Roman-Empire GCN accuracy of about 78% (from about 70%) and a Peptides-struct mean absolute error (MAE) of 0.2470. For learned rewiring, the competitor is the SIMPLE-sampler variant of probabilistic rewiring, which reports a ZINC MAE of 0.092 ± 0.004 with edge features. Our method should be compared against it on ZINC with the same GIN-style backbone.

The most dangerous baseline is graph attention with a learnable per-layer temperature, or equivalently a learnable scale on the attention logits, trained with no schedule. Our ablations are fixed high $\tau$, fixed low $\tau$, hard top-$k$ with a straight-through estimator from step zero, and annealing with a full softmax instead of soft top-$k$. The last one separates the effect of the schedule from the effect of sparsity.

Every method gets the same splits, ten seeds, the same hidden width and depth grid, and the same number of hyperparameter trials. For our method, the schedule parameters count against that trial budget.

Why not just…?

Why not just let graph attention learn its own sharpness? The scale of the attention logits is already a learnable temperature, so the schedule may be redundant. This is the real threat. Our argument is that, at depth, the gradient reaching the attention parameters is exactly what backward over-smoothing suppresses (Backward Oversmoothing). A learned scale therefore stays near its soft initialization. The learnable-temperature baseline settles the question directly. We will log the learned scales. If they sharpen on their own and match annealing, the contribution shrinks to a diagnosis rather than a method, and we will report it that way.

Why not just use PairNorm or deep supervision? Both are cheap and work. However, PairNorm does not raise peak accuracy on feature-rich citation graphs, and deep supervision needs labels at every layer. Neither addresses which neighbors a node mixes with, which matters on heterophilic graphs where averaging is harmful in the first place. We run both as baselines and also in combination with our layer, given the documented interference between these fixes.

Why not just keep the network shallow? On Cora and Citeseer it is the right answer, and we expect to tie rather than win there. Depth is needed on Peptides-struct, with missing features, and in molecular regression, where 16-layer DSGNN beats 6–8 layer models. Those are where we evaluate.

Why not just prune edges once with PROXYDELETE? It is fast, needs no labels, and is strong on Roman-Empire. But it is fixed before training and cannot adapt neighbor choice per layer or to the task loss. A head-to-head comparison on Roman-Empire, Squirrel, and Peptides-struct decides the question.

Proposed Experiments

We run depth sweeps (2 to 64 layers) on Cora, Citeseer, Pubmed, and OGBN-Arxiv. We use the missing-feature setting on Cora and Pubmed, the heterophilic graphs Roman-Empire, Amazon-Ratings, Squirrel, Chameleon, and Texas, the long-range benchmark Peptides-struct, and ZINC. Metrics are accuracy or MAE, plus per-layer effective rank, per-layer gradient norm, and attention entropy.

Three checks are decisive. First, at fixed depth of 16 or more, sweeping fixed $\tau$ should show effective rank decreasing monotonically in $\tau$ and accuracy peaking in the interior of the range. If rank does not depend on $\tau$, the core claim is wrong. Second, annealed selection should beat both fixed endpoints and the learnable-temperature baseline at depth, and it should restore gradient norm in the inner layers that the fixed high-$\tau$ model starves. Third, on Pubmed at 12 layers and Peptides-struct it should match or beat DSGNN's 77.5% and PROXYDELETE's 0.2470 MAE, respectively, under the shared tuning budget. A win only on the second check would support the diagnosis without a practical method. Failing the first would falsify the framing outright.