Choosing a graph neural network (GNN, a model that updates each node's features by repeatedly averaging in its neighbours' features) usually means training many candidate designs and keeping the best one. The one exhaustive benchmark for this, NAS-Bench-Graph, needed about 8,000 GPU hours to train its 26,206 candidates on nine datasets. In vision, people avoid this cost with "zero-cost proxies": scores computed from an untrained network in one forward and backward pass that predict how well it will do once trained. Nobody has built such a score for graph models. Graph models also fail in a particular way. Stacked averaging makes node features look alike (over-smoothing), and recent work suggests that the backward pass, the gradients that tell the network how to update, smooths out too.
We propose a training-free score that checks both directions. The forward check asks whether the matrix of node features keeps its rank, meaning its number of independent directions, as it moves through the layers. The backward check asks whether the gradients reaching the inner layers still differ from node to node after the final classifier has been fitted. The bet is specific. An architecture can look expressive at initialization and still fail because its inner layers stop receiving useful gradients. A score that sees both failures should rank graph architectures better than rank-only proxies, size counts, or vision proxies, and the gap should be largest for deep networks and for graphs whose linked nodes tend to have different labels (heterophilic graphs).
Core Claim and Positioning
The obvious combination of these directions is to take NEAR and run it on NAS-Bench-Graph. NEAR sums the effective rank of each layer's activations in an untrained network and reaches a Spearman correlation of 0.70 on NAS-Bench-101. It was never tested on GNNs. Its authors also state that it measures capacity, not trainability.
Are we measuring oversmoothing in graph neural networks correctly? motivates the forward half. It shows that effective rank of node features tracks accuracy loss with depth (average Pearson 0.91) where Dirichlet energy does not. It uses rank only as a diagnostic on networks that have already been trained, and it warns that high rank is necessary but not sufficient for accuracy.
Backward Oversmoothing motivates the backward half. It proves a specific failure mode: once the final classifier has fitted the smoothed features, the gradients backpropagated through message passing become nearly constant across nodes. The inner layers then freeze at their random initial weights.
Our contribution is a cheap way to simulate that trap at initialization and measure it with the same rank tools. Running NEAR on graphs is one of our baselines, not our method.
Two other papers constrain the design. The Oversmoothing Fallacy finds that collapse comes mainly from the weight multiplications and nonlinearities, not from the neighbour averaging. It also shows that skip connections and batch normalization rescue 1,024-layer GCNs. The score therefore has to reward those components and must not simply penalize aggregation. NAS-Bench-Graph reports that later layers matter more than early ones. This fits a backward-trap story in which early layers are the ones left untrained.
The Score
Let $X$ be the input node features and $H_l$ the $n \times d$ node feature matrix after layer $l$ of an untrained candidate with $L$ layers. Here $n$ is the number of nodes and $d$ the feature width. Erank is the exponentiated entropy of normalized singular values, as defined in the over-smoothing measurement paper.
To simulate the trap, we fit the output head $W^\star$ in closed form by ridge regression of the training labels on $H_L$. This is cheap and needs no gradient steps. We then backpropagate the training loss once and collect $G_l = \partial \mathcal{L} / \partial H_l$, the gradient with respect to each layer's node features. The score is
$$ S = \frac{1}{L}\sum_{l=1}^{L} \log \frac{\mathrm{Erank}(H_l)}{\mathrm{Erank}(X)} \;+\; \lambda \min_{l} \log \mathrm{Erank}(G_l). $$
The first term rewards forward rank retention measured relative to the input. Dividing by the input's rank means a model is not rewarded for rank it did not preserve.
The second term targets the weakest link in the backward pass. If any layer's gradient matrix has nearly collapsed to rank one, that layer will barely move during training.
The weight $\lambda$ is set once on Cora and frozen for every other dataset. Using node labels is legitimate in this setting, because node-classification search always has training labels. We also report a label-free variant that uses random targets.
Research Program
The work has three parts.
Score all candidates on NAS-Bench-Graph. We score all 26,206 architectures on the nine NAS-Bench-Graph datasets and compare against the stored accuracies. This step costs seconds per architecture.
Build a deep extension. NAS-Bench-Graph architectures contain at most a few message-passing layers, so the backward trap may barely appear there. We therefore build a deep extension: the same seven operators, optional skip connections and batch normalization, and depths from 8 to 64. We train a few hundred sampled architectures each on Cora, Chameleon, Squirrel and Amazon Ratings. NAS-Bench-Graph's cost works out to roughly 0.03 GPU-hours per shallow architecture–dataset pair, so this extension should cost tens to low hundreds of GPU hours.
Analyze the debate. Across the 26,206 architectures, we regress forward and backward rank loss on operator type, normalization, skip connections and depth. This gives a large-scale measurement on the question of whether aggregation, transformation, or the backward pass drives collapse.
Baselines
Do-nothing and size references. The naive point of comparison is random selection. Selection by parameter count and by FLOPs (floating-point operations) is the reference that NAS-Bench-Suite-Zero found surprisingly hard to beat. Every proxy will also be reported as a partial correlation with parameter count held fixed, to expose any bias toward bigger models.
Vision proxies. We include grad_norm, SNIP, GraSP, Fisher, SynFlow and jacob_cov from Zero-Cost Proxies for Lightweight NAS, together with their SynFlow+jacob_cov+SNIP vote. That vote reports Spearman 0.82 on NAS-Bench-201; no reported result found on Lacuna for these proxies on NAS-Bench-Graph.
Strongest single proxy. The strongest single competitor is NEAR run directly on the GNN layers, which reports Spearman 0.70 on NAS-Bench-101. It is strongest because it uses the same rank quantity, so any gain we show must come from graph-specific normalization and the backward term. No reported result found on Lacuna for NEAR on graphs.
Strongest combined baseline. Following NAS-Bench-Suite-Zero, which improved correlation by up to 42% by combining 13 proxies, we train an XGBoost surrogate on all the above proxies.
Fairness rules. All proxies use the same minibatch, three initialization seeds, and the same random-train/test split of architectures for the surrogate. No proxy gets per-dataset tuning beyond what ours gets.
Ablations. These isolate the key ingredient:
- forward term only;
- backward term only;
- backward rank computed at a random head instead of the ridge-fitted head;
- Dirichlet energy instead of effective rank.
What counts as winning. Beating NEAR means a higher Spearman correlation and a better top-1% hit rate on a majority of datasets, with confidence intervals from seeds that do not overlap. Beating the XGBoost surrogate means that adding our score to it improves it significantly, or that our score alone matches it.
Why not just…?
Why not just run random search on the benchmark? NAS-Bench-Graph itself reports that random search beats reinforcement-learning and evolutionary search on some datasets. But it was given free table lookups that cost 8,000 GPU hours to build. We compare at matched cost. We run proxy-filtered random search, which scores many candidates and trains only the top few. We run plain random search with the same number of full trainings. We report the test accuracy of the architecture each one finds.
Why not just use parameter count? NAS-Bench-Graph's observation that top performers are rare and frequently small and fast suggests size will rank them poorly. This is an empirical question, settled by the partial-correlation analysis. If size explains most of what our score captures, we will report that.
Why not just fit a linear classifier on the random features and use its accuracy? This is the real threat. On Random Weights and Unsupervised Feature Learning is the origin of the idea that untrained networks already carry signal. Our score already computes this ridge probe as an intermediate step, so its accuracy is a free baseline. If probe accuracy alone matches $S$, the rank terms add nothing and we will say so. The prediction that would separate them is the deep extension. There, a probe on the final features cannot see that early layers will receive almost no gradient, while the backward term can.
Why not just use a standard GCN with skip connections and batch normalization? The Oversmoothing Fallacy shows this backbone is strong. NAS-Bench-Graph's finding that "transferability is a trap" argues that one design will not be best on every dataset. We include this backbone, tuned at matched budget, as a fixed reference in the deep extension. If search rarely beats it, that is a useful negative finding about graph architecture search, not a failure of the proxy.
Decisive Checks
Does the score use graph structure at all? We recompute every proxy after randomly rewiring the edges while keeping node degrees the same. A score that truly reads graph structure should lose correlation on homophilic graphs. A score that does not change is effectively an MLP proxy (a proxy that ignores the edges entirely).
Does the backward term matter in deep networks? It should add little on shallow NAS-Bench-Graph architectures and clearly improve correlation in the deep extension. Within the deep extension, architectures with low backward rank should show early layers whose weights barely move during training. We verify this directly by measuring the distance each layer's weights travel from initialization.
Does it hold up on heterophilic graphs? The score should keep a positive correlation on Chameleon, Squirrel and Amazon Ratings, where smoothing hurts and vision proxies are expected to break down. If it fails there too, the claim narrows to homophilic graphs, and the paper says so.
References
- NAS-Bench-Graph: Benchmarking Graph Neural Architecture Search
- NEAR: A Training-Free Pre-Estimator of Machine Learning Model Performance
- Are we measuring oversmoothing in graph neural networks correctly?
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?
- The Oversmoothing Fallacy: A Misguided Narrative in GNN Research
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies
- Zero-Cost Proxies for Lightweight NAS
- On Random Weights and Unsupervised Feature Learning