Closed-Form Readouts as a Diagnostic for Deep Graph Network Collapse

Graph neural networks (models that update each node's features by repeatedly averaging in its neighbors' features) lose accuracy as layers are stacked. The usual explanation is over-smoothing: node features blur into near-identical vectors. A recent theory paper argues that the training procedure, not the architecture, is to blame. When gradients are passed backward through many averaging steps, they blur as well, and training stalls. This leaves a basic question unsettled. When a 32-layer graph network fails, does its internal representation no longer contain the answer, or does it contain the answer that gradient descent cannot find? This proposal answers that question with a tool from extreme learning machines (ELMs). An ELM keeps its hidden weights random and frozen and fits only a linear output layer, in closed form, by regularized least squares. That fit is the exact best linear readout of a given representation. It involves no gradients, so it cannot suffer from blurred gradients.

The same tool addresses a reproducibility problem. Over-smoothing results are mostly reported on one fixed data split. Yet Pitfalls of Graph Neural Network Evaluation. showed that rankings of graph networks flip under 100 random splits × 20 initializations. Under that protocol, a fairly tuned vanilla 2-layer graph convolutional network (GCN) beat GAT, GraphSAGE and MoNet. That protocol is rarely applied to deep models because 2,000 gradient-trained runs per configuration is expensive. A closed-form readout over semi-supervised labels costs a small linear solve. We can therefore afford the rigorous protocol across depth, width and dataset. We also report which anti-smoothing claims survive it.

Core Claim

Freeze any representation $H_k \in \mathbb{R}^{N\times L}$ at layer $k$ of a graph network, whether its weights are random or trained, and fit the ridge readout. Here $N$ is the number of nodes and $L$ the feature width:

$$\beta_k = H_{k,\ell}^{\top}\left(H_{k,\ell}H_{k,\ell}^{\top} + \lambda I\right)^{-1} Y_\ell .$$

In this formula, $H_{k,\ell}$ holds the rows for the $n_\ell$ labeled nodes, $Y_\ell$ is their one-hot labels, and $\lambda$ is a ridge penalty chosen on validation nodes. On Cora-sized benchmarks, $n_\ell$ is a few hundred, so this is a tiny solve even at width 8192. The resulting probe accuracy $A^{\text{probe}}_k$ bounds what any linear head could extract from $H_k$.

We use it to split the depth-induced accuracy loss of a trained network with accuracy $A^{\text{trained}}(D)$ at depth $D$:

$$\underbrace{A^{\text{trained}}(2) - A^{\text{trained}}(D)}_{\text{total loss}} = \underbrace{A^{\text{probe}}(2) - A^{\text{probe}}(D)}_{\text{forward collapse}} + \underbrace{\big[A^{\text{probe}}(D) - A^{\text{trained}}(D)\big] - \big[A^{\text{probe}}(2) - A^{\text{trained}}(2)\big]}_{\text{optimization gap}} .$$

The equation is an accounting identity, so any decomposition of this kind holds trivially. The content lies in the measurement. If backward over-smoothing is the dominant cause, as Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? argues, the optimization gap should dominate. Concretely, the probe on the trained network's own final layer should recover much of the lost accuracy. The probe on its trainable-but-untrained initialization should do so as well. If forward collapse dominates, the probe should fail too.

Our central prediction concerns the second layer, which has not been studied empirically at scale. For trained deep GCNs, the optimization gap is the larger term at moderate depths, roughly 8 to 32 layers. Forward collapse takes over only at much greater depths. Wide random networks with a closed-form readout, which we call deep graph ELMs, should sit close to the probe ceiling at all depths.

Research Program

The first study concerns the decomposition. We train vanilla GCNs at depths 2, 4, 8, 16, 32 and 64 under the Shchur protocol. For each run, we compute closed-form probes on every layer. We compute the same probes on the network at initialization. We report both terms with confidence intervals over splits and seeds.

This study tests Keriven's theory in the setting it leaves open. That setting uses ReLU rather than the smooth activations the proofs require, and it includes trained rather than only analyzed networks.

The second study reconciles a direct contradiction about random weights. Graph Neural Networks (with Proper Weights) Can Escape Oversmoothing argues that random weights, even with Xavier initialization, accelerate collapse. It proposes learned reparameterization (WeightRep) as the remedy. Partially trained graph convolutional networks resist oversmoothing instead freezes all layers but one at random. It widens them to 8192 units and argues, via random matrix theory, that wide random matrices decorrelate features.

Both can be right if a critical width exists that grows with depth. We sweep width over 64 to 8192 and depth over 2 to 64 for fully random, fully frozen GCNs. Because nothing is trained, a full grid under the 2,000-run protocol is affordable. At each cell, we measure the closed-form probe accuracy and the effective rank. Effective rank, defined in Are we measuring oversmoothing in graph neural networks correctly?, is the exponentiated entropy of the normalized singular values. The output is a phase map, and the reported curve is the width at which the probe accuracy of a deep random network falls within one standard deviation of the depth-2 probe. A boundary that moves with depth reconciles the two papers. No boundary, meaning random weights collapse at every width, would contradict Kelesis et al.'s mechanism.

The third study tests whether effective rank remains a valid over-smoothing metric in random networks. Zhang et al. report that effective rank correlates with accuracy at an average Pearson correlation of 0.91, but only for gradient-trained GCNs and GATs. They warn that random noise has maximal rank and no use for prediction.

Random networks are where that warning bites. We test whether effective rank still tracks probe accuracy across the phase map, and where it breaks down. We then test a simple corrected quantity: the effective rank of the projection of $H_k$ onto the span of the probe's predictions. This quantity is cheap because the probe is already in closed form. We expect it to separate "high rank and informative" from "high rank and noise". Dirichlet energy, a sum of squared feature differences across edges, is reported alongside. This makes it possible to check its reported failure in a new regime, and it is not used as evidence.

Baselines

The naive reference point is a fairly tuned 2-layer vanilla GCN under the full Shchur protocol. Shchur et al. report that this model reached the highest relative accuracy, 99.4%, and the best average rank across their datasets. No deep model is useful on a benchmark unless it beats this one. We run it with the same hyperparameter grid and early-stopping rule as every other gradient-trained model. A second naive reference is the same 2-layer feature propagation followed by the closed-form readout with no random hidden layer. This is the simple-graph-convolution-plus-ridge model. It isolates whether random nonlinear width contributes anything at all.

Two baselines represent the strongest deep competitors. The first is the partially trained wide GCN of Kelesis et al. It is the closest method to ours, since it also uses random frozen layers. It differs in training one layer by backpropagation, where we fit only a closed-form readout. They report that on Cora at depth 32, standard GCN accuracy drops to "near-random levels (10-20%)", while their 8192-wide model "maintained an accuracy of over 70%". On cold-start Physics, where features are zeroed so that depth is necessary, a 14-layer model reached 88.11%. The second is the gradient-flow-repaired vanilla GCN of Old can be Gold: Better Gradient Flow can Make Vanilla-GCNs Great Again. It reports about 80% on Cora up to 64 layers and 72.28% on OGBN-ArXiv, above GCNII and JKNet.

WeightRep and the convex kernel model of Graph Convolutional Kernel Machine versus Graph Convolutional Networks complete the comparison. The kernel model reports 83.3% on Cora with random splits against GCN's 80.6%. Its random-Fourier-feature variant is close kin to a graph ELM and must be included. All of these numbers come from each paper's own protocol, so none is directly comparable. We rerun every baseline under one protocol, with an equal hyperparameter search budget measured in configurations tried. For OGBN-ArXiv, we use the standard split with 20 seeds, since random resplitting is not standard there.

Two ablations isolate the key ingredients. Replacing the closed-form readout with a gradient-trained linear head on the same frozen random features isolates the solver. Replacing random hidden weights with the identity, which gives pure propagation, isolates random width.

The criteria for success are as follows. The deep graph ELM beats a baseline if its mean accuracy over the protocol is higher and the paired difference across splits excludes zero. We count matching Kelesis et al. within noise at a fraction of their training cost as a success on cost, not on accuracy. The decomposition itself has no baseline to beat. Its success criterion is that the optimization-gap term is estimated with tight enough intervals to be distinguishable from zero.

Why not just…?

Why not just use a logistic-regression probe trained by gradient descent? A well-tuned logistic probe would probably give similar numbers. The closed form is not essential for correctness of the decomposition, and we include the gradient probe as an ablation to check agreement. The closed form matters for two other reasons. First, it removes any doubt that the probe itself is under-optimized, which is the very confound under study. Second, it makes the 2,000-run protocol over a depth-by-width grid affordable. If the two probes disagree, that disagreement is itself evidence of optimization trouble even in a linear head.

Why not just report effective rank, which already correlates 0.91 with accuracy? That correlation was measured on trained networks. Zhang et al. themselves note that random noise maximizes rank, and random-weight networks are exactly where that failure should appear. If effective rank tracks probe accuracy across our random-network phase map, we will say so and treat the probe as redundant there. We expect it not to track probe accuracy in the wide, deep corner.

Why not just use a shallow tuned GCN, since deep models rarely help? On standard homophilous benchmarks, where linked nodes usually share a class, this alternative is a real threat. Shchur et al.'s result suggests the shallow GCN may win outright. We therefore do not claim deep graph ELMs beat it there. The decomposition is a scientific result regardless of which model wins. Our accuracy claims rest on regimes where depth is necessary: cold-start Physics with zeroed features, and Chameleon and Squirrel. In those two heterophilous graphs, linked nodes usually belong to different classes, and fixed low-pass smoothing is known to erase class separation.

Why not just precompute propagation and fit a classifier, as SGC or RpHGNN do? Efficient Heterogeneous Graph Learning via Random Projection uses fixed sparse random projections to compress multi-hop features before a gradient-trained encoder. It reaches peak OGBN-MAG accuracy in about 21 minutes. Our pure-propagation ablation is essentially this approach with a closed-form head. If it matches the deep random network at every depth, then random nonlinear layers add nothing, and we will report that rather than defend the more complex model.

Proposed Experiments and Decisive Checks

The datasets are Cora, CiteSeer, PubMed, Amazon Computers and Photo, Coauthor Physics in both normal and cold-start forms, Chameleon, Squirrel, and OGBN-ArXiv. For OGBN-ArXiv the labeled set is large, so we solve the $L\times L$ primal system instead of the dual. Metrics are mean and standard deviation of test accuracy over 100 splits × 20 seeds, the two decomposition terms, effective rank, numerical rank, the prediction-projected rank, Dirichlet energy, and wall-clock and memory cost.

Four outcomes are decisive. The first is whether the probe on a trained 32-layer GCN's final layer recovers most of the gap to its depth-2 accuracy on Cora. If it does, this is strong evidence for the backward account. If it stays near the trained model's 10–20%, forward collapse dominates and the backward account is not the main story in practice. The second is whether the random-network phase map shows a depth-dependent critical width, which would reconcile WeightRep with Kelesis et al. The third is whether the rankings of Kelesis et al., the gradient-flow-repaired GCN, WeightRep and the kernel machine survive the multi-split protocol. The fourth is whether a deep graph ELM matches the 88.11% cold-start Physics figure at a fraction of the cost.

Each outcome would be informative whichever way it falls, which is the main reason to run the study.