Relevance-Weighted Rank: Telling Harmful Over-Smoothing Apart from Useful Forgetting in Deep GNNs

Graph neural networks compute each node's representation by repeatedly averaging it with its neighbors. Stack enough of these layers and every node ends up looking the same. This is called over-smoothing, and it is the standard explanation for why deep graph networks lose accuracy. The current best way to detect it is to measure how many independent directions remain in the node-feature matrix, a quantity called effective rank. But effective rank cannot see which directions survive. A network that keeps many directions of pure noise looks healthy. A network that deliberately drops useless directions looks collapsed. We propose to fix this with a tool from kernel methods, automatic relevance determination (ARD), which learns one "lengthscale" per input direction. A short lengthscale means the prediction changes quickly along that direction. A very long one means the direction is ignored. Weighting each surviving direction of a layer's representation by its learned relevance gives a rank measure that counts only the directions the label actually depends on.

In two sentences: fit an ARD probe to each layer's node representations to learn how much each principal direction matters for the labels, then measure collapse only in the directions that matter. This should separate harmful over-smoothing from harmless pruning, keep working when noise inflates ordinary rank, and give a regularizer that protects useful directions instead of all directions.

Core Claim

Are we measuring oversmoothing in graph neural networks correctly? motivates this work. It shows that Dirichlet energy (the summed squared feature difference across edges) misses collapse in trained networks. It shows that effective rank (Erank) tracks accuracy with an average Pearson correlation of 0.91 across Cora, Citeseer, Pubmed, Squirrel, Chameleon, Amazon Ratings and ogbn-arxiv. The same paper names the remaining weakness itself: random noise has maximal rank and zero usefulness, so high rank is necessary but not sufficient.

The tension the research file raises between ARD and anti-smoothing guarantees is the same problem from the other side. ARD wants uninformative directions to vanish. ACMP and PairNorm work to keep all variation alive, isotropically: ACMP guarantees a positive lower bound on Dirichlet energy, and PairNorm holds total pairwise distance constant.

Our claim is that both problems disappear once collapse is measured in a relevance-weighted geometry. We make two predictions. First, on clean benchmarks the weighted measure should track accuracy at least as well as plain Erank. Second, under controlled perturbations where plain Erank is known to mislead, the weighted measure should keep tracking accuracy while plain Erank does not. The two perturbations are injected noise channels and deliberately sparse readouts.

Concretely, let $H_l \in \mathbb{R}^{N \times d}$ be the node representations at layer $l$, with singular values $\sigma_k$ and right singular vectors $v_k$. We fit a Gaussian process with an ARD kernel to the labeled nodes' coordinates $z_{ik} = h_i^\top v_k$. This yields one lengthscale $\ell_k$ per principal direction. The ratio $\sigma_k/\ell_k$ counts how many "lengthscales" of spread the nodes cover along direction $k$. Roughly, it measures how much room the label function has to vary there. The relevance-weighted rank is

$$\mathrm{RRank}(H_l) = \exp\Big(-\sum_k q_k \log q_k\Big), \qquad q_k = \frac{\sigma_k/\ell_k}{\sum_j \sigma_j/\ell_j}.$$

Plain Erank is the special case where every $\ell_k$ is equal. A noise direction with large $\sigma_k$ but $\ell_k \to \infty$ adds nothing to this rank. A pruned direction that was irrelevant anyway costs nothing either.

We fit ARD in the principal-component basis on purpose. Hidden channels of a neural network have no privileged axes, and diagonal ARD in an arbitrary basis is not rotation-invariant. Working in the singular basis also keeps the measure a direct reweighting of the spectrum Erank already uses.

Research Program

The method borrows from three lines of ARD work. Seeger's Bayesian model selection for kernel classifiers and ARD for least-squares SVMs supply the mechanism: per-dimension lengthscales fit by maximizing the marginal likelihood, which drives irrelevant dimensions toward infinite lengthscale. On Feature Learning of Recursive Feature Machines and ARD supplies a second, label-free estimator. That paper shows that the diagonal of the average gradient outer product (AGOP, the averaged outer product of a model's input-gradients) correlates closely with ARD weights on tabular data. It also shows that the full AGOP captures correlated directions that diagonal ARD misses. We therefore build two versions of the measure. The first fits ARD on labeled nodes. The second applies AGOP to the trained network's own downstream layers, differentiating its output with respect to $H_l$ over all nodes, labeled or not. Testing whether the two agree on graphs is itself a finding, because that comparison has only been made on independent tabular data.

The program has three stages. In the first, we measure. We train GCN and GAT models (Kipf & Welling), with and without PairNorm and residual connections, at depths 2 to 64. At every layer we compute Dirichlet energy, Erank, ARD-RRank and AGOP-RRank.

In the second stage, we stress-test the measures with two constructions where the right answer is known.

The first construction is noise injection. We append $k$ channels of independent Gaussian noise to the inputs or to a hidden layer. We also add an auxiliary loss that rewards high total rank, which forces the network to keep those channels alive. Accuracy should fall while plain Erank stays high or rises.

The second construction is benign pruning. We train with an L1 penalty on the readout so the network deliberately discards most directions. Plain Erank should fall while accuracy holds.

A useful measure must move with accuracy in both constructions.

In the third stage, which runs only if the first two succeed, we intervene. We add a regularizer that rewards high RRank, using AGOP relevance recomputed every few epochs. We compare it against a regularizer that rewards plain Erank and against PairNorm. The prediction is specific. The two regularizers should perform similarly on clean data. The relevance-weighted one should win when noise channels are present, because the plain-rank regularizer is rewarded for keeping noise.

The GP fitting is cheap in the regimes that matter. Citation benchmarks have a few hundred labeled nodes, and hidden widths are 64 to 256. For ogbn-arxiv we subsample about 5,000 labeled nodes per layer. The Open Graph Benchmark documents that full-batch methods do not scale further. The cubic-cost concerns raised in Efficient Network ARD apply at feature dimensions in the tens of thousands, not here.

That paper is the closest ARD-side neighbor. It learns a graph over outputs in multi-response regression and never touches message passing. Neural Sheaf Diffusion is the closest smoothing-side neighbor. It learns per-edge, per-channel transport maps end to end, which makes propagation anisotropic. But it never estimates which directions are relevant, and it offers no diagnostic. Our proposal changes neither the propagation rule nor the regression model. It changes what we count as collapse.

Baselines

The naive reference point is the shallow network. A 2-layer GCN reaches 81.5% on Cora according to Kipf & Welling. Any intervention that does not reach this number on clean Cora brings no practical gain there. In line with PairNorm's own finding, we expect deep methods to help mainly in the missing-feature setting, where unlabeled nodes have no features. There PairNorm-SGC reaches 74.5% against 42.3% for vanilla SGC on Cora.

The strongest diagnostic baseline is plain Erank from Zhang et al., with its reported 0.91 average Pearson correlation with accuracy. We compute it on exactly the same trained checkpoints, layers and node sets as RRank. Both measures therefore see identical representations and differ only in the weighting.

Beating it has two parts. RRank should come within a small margin of plain Erank on the clean benchmarks; we do not expect to clearly exceed 0.91 there. And RRank's correlation should hold up substantially better than plain Erank's under the noise-injection and benign-pruning constructions. If RRank merely matches Erank in the perturbed settings, the diagnostic claim fails.

Dirichlet energy is included as the weaker classical reference.

For the intervention, the strongest existing deep-network results in the file are ACMP's 80.30% on Cora at 128 layers and its 86.2% on Texas against 55.1% for GCN. PairNorm's 74.5% on missing-feature Cora is the other target. We rerun PairNorm, residual GCN and ACMP under our splits with the same tuning budget, a fixed number of random-search trials per method. We report our own reproductions next to the cited numbers.

The key ablation is the plain-Erank regularizer, identical to ours except that all lengthscales are equal. It isolates whether relevance weighting, rather than rank promotion in general, does the work. A second ablation compares diagonal ARD in the raw channel basis with ARD in the principal basis and with full AGOP. It tests whether rotation-invariance matters.

Why not just…?

Why not just track linear-probe accuracy at each layer? A per-layer probe does measure how much label information a layer holds, and we use it as a reference signal. But it returns a single number. It cannot say whether a drop comes from relevant directions merging or from noise crowding them out. It also needs labels, whereas the AGOP version of RRank does not. If RRank adds nothing beyond probe accuracy in predicting final accuracy, we will report that, and the contribution shrinks to the label-free variant and the intervention.

Why not just regularize plain effective rank? This is the most serious threat. On clean benchmarks it may perform as well as our regularizer, because trained networks rarely carry much pure noise. The noise-injection experiment exists to settle this. A regularizer that rewards all rank is rewarded for preserving injected noise channels, and ours is not. If the two still tie under noise, relevance weighting is unnecessary and we will say so.

Why not just let per-channel normalization gains or the weight matrices down-weight useless channels? LayerNorm gains and the layer weight matrices can rescale directions, so the network can in principle learn relevance implicitly. Zhang et al. report that normalization layers do not stop rank collapse and can make energy measures misleading. Learned rescaling also gives no readable signal of which directions matter. The diagnostic stages do not compete with this alternative at all: they measure what such networks end up doing. In the intervention stage, LayerNorm-with-gains is included in the comparison.

Why not just stay shallow, or select input features before propagating? On feature-rich citation graphs, staying shallow is often correct, and we treat the 2-layer result as the bar to clear. In the missing-feature regime, PairNorm's own numbers show that depth is required. Selecting input features in advance also ignores what propagation does to them. It cannot detect collapse that arises inside the network, which is the object of study here.

Decisive Checks

The datasets are Cora, CiteSeer, PubMed, Squirrel, Chameleon, Amazon Ratings and ogbn-arxiv, the same set used by Zhang et al., plus Texas and missing-feature Cora for the intervention.

The first decisive check is whether ARD-RRank keeps a high correlation with accuracy across depth when $k$ noise channels are injected, for $k$ from 0 to 4$d$, while plain Erank's correlation falls. The second is whether, in the benign-pruning construction, plain Erank drops while RRank and accuracy hold steady. The third is whether ARD-based and AGOP-based relevance agree on graphs: the rank correlation of their direction weights should match the high agreement reported on tabular data. The fourth is whether, in the noise-injected missing-feature setting, the relevance-weighted regularizer beats the plain-Erank regularizer and PairNorm by more than the spread across seeds.

A negative result on the first two checks would show that relevance weighting is unnecessary for diagnosis, and that would be worth reporting. A positive result would give the field a collapse measure that does not reward noise.