Graph neural networks (GNNs) are models that update each node's representation from its neighbors. Searching automatically over GNN designs, such as which layer type to use at each depth and how layers are wired, works well, but it is expensive because every candidate must be trained. In vision, "zero-cost proxies" avoid that cost. These are scores computed from an untrained network on one batch of data, and they predict which architectures will train well. They have never been tested on graph architecture search. They are also likely to fail there in a specific way. Graph-learning tools developed on one layer type (the graph convolutional network, or GCN) routinely break on others, such as attention layers (GAT) or sum-aggregation layers (GIN). Most zero-cost proxies are gradient-saliency formulas, and in a GNN the gradient is entangled with the input graph differently for each layer type. A search space that mixes GCN, GAT, GIN and others may therefore get proxy scores that mostly encode which operators an architecture contains, not how well it will fit this particular graph.
We propose to measure this failure on the one exhaustive graph architecture benchmark available. We then test a replacement that is compatible with any operator by construction. The replacement runs a single forward pass with random weights over the full data graph. It scores how well the resulting node embeddings already separate the training labels. It uses no gradients and no operator-specific theory. It depends on the data graph, so it can in principle predict that the best architecture on Cora differs from the best on PubMed.
Core Claim
We make two claims, each testable on NAS-Bench-Graph. That benchmark contains 26,206 six-node GNN architectures built from GCN, GAT, GraphSAGE, GIN, ChebNet, ARMA, k-GNN and identity layers, each fully trained on nine datasets.
The first claim is diagnostic. Off-the-shelf zero-cost proxies on this space carry an "operator-composition bias," analogous to the big-model bias that NAS-Bench-Suite-Zero found in vision. Concretely, the counts of each operator type in an architecture explain much more of the proxy's variance than of the variance in true accuracy. As a result, rank correlation among architectures with the same operator counts is much lower than the correlation measured across the whole space.
The second claim is constructive. A label-aware alignment score computed on random-weight embeddings ranks architectures better than gradient-based proxies at comparable cost. It should also track how rankings shift from one dataset to another. That would be the first training-free evidence that a graph architecture's quality can be estimated jointly with the data graph rather than independently of it.
The alignment score works as follows. Let $H \in \mathbb{R}^{n \times d}$ be the final-layer embeddings of the $n$ training nodes under random initialization, and let $Y$ be their one-hot labels. Let $K = HH^\top$, and let $K_c$ be $K$ after centering. The score is the kernel–target alignment
$$ S = \frac{\langle K_c,\; YY^\top \rangle_F}{\lVert K_c \rVert_F \,\lVert YY^\top \rVert_F}, $$
averaged over a few random seeds. Here $\langle\cdot,\cdot\rangle_F$ is the elementwise inner product. A sampled-pair estimate avoids forming $K$ on large graphs.
Relation to Prior Work
The motivation comes from the cross-architecture literature. GASSIP searches architectures while pruning edges, and shows that GCN, GAT and GIN regard largely disjoint edge sets as redundant. GATT shows that naively averaging attention fails for attribution, scoring an explanation AUROC of 0.1768 against its own 0.8477 on BA-Shapes. Its fix requires an architecture-specific computation-tree blueprint. GraNT derives a graph neural tangent kernel result to select training data for a fixed GCN, and leaves the extension to GAT open. Taken together, these papers show that tools derived from one message-passing form do not transfer to others. We treat zero-cost proxies as one more such tool.
GraNT also constrains our design. Building a proper kernel theory per operator is exactly the step that has not been generalized, so we deliberately avoid gradients and tangent kernels. We use only a forward pass, which every operator supports identically. This choice follows the observation in On Random Weights and Unsupervised Feature Learning that untrained architectures already carry much of their inductive bias.
The method draws on three sources. Zero-Cost Proxies for Lightweight NAS supplies the gradient proxies (grad_norm, snip, grasp, fisher, synflow, jacob_cov). NAS-Bench-Suite-Zero supplies the evaluation protocol, the nwot proxy and the XGBoost proxy-ensemble surrogate. Rethinking Performance Estimation in NAS frames truncated training as the cost-matched alternative.
Two graph-specific lines are close but answer different questions. GENNAPE predicts performance from the network's computation graph alone and was tested only on CNN and vision-transformer spaces. It never sees the data graph, and our score is defined by it. GAUSS makes supernet search scale to Papers100M, raising Kendall's $\tau$ from about 20% to over 72%, but it still trains a shared network; we train nothing.
Research Program
The first stage is the audit. We compute all six gradient proxies, nwot, parameter count and FLOPs for all 26,206 architectures on all nine NAS-Bench-Graph datasets, using full-graph forward and backward passes. On ogbn-proteins this may require neighbor-sampled batches; if so, we report that separately. We then report Spearman and Kendall correlations with the benchmark's final test accuracy, together with top-k recall.
For the bias diagnostic, we regress each proxy and the true accuracy on operator-count features and on the macro wiring pattern (A–I). We compare the explained variance between the two. We then recompute the correlations within strata of identical operator counts. If proxies lose most of their correlation inside strata while accuracy still varies substantially there, the operator-composition bias is confirmed.
The second stage builds the alignment score and two variants that isolate its ingredients. The label-free variant replaces $YY^\top$ with the embedding's effective rank, which is close in spirit to nwot. The graph-blind variant runs the same architecture with the adjacency replaced by self-loops only, which isolates how much of the score comes from the interaction with the data graph.
The third stage tests dataset sensitivity. For each pair of datasets, we ask whether the change in proxy rank of an architecture predicts the change in its true rank. NAS-Bench-Graph's finding that Cora winners rarely transfer to PubMed gives this test real stakes.
Baselines
The naive reference point is random search, which NAS-Bench-Graph found surprisingly strong against reinforcement learning, evolution and DARTS. We run it with the same number of fully trained evaluations that a proxy-filtered search is allowed. Proxy-guided search counts as useful only if it reaches a given top-k accuracy with fewer trained candidates.
Parameter count and FLOPs are the trivial proxies, computed for free on the same architectures. The alignment score must beat both in overall and within-stratum correlation. Otherwise it is merely tracking size, the same failure NAS-Bench-Suite-Zero documented in vision.
The strongest training-free competitor is the NAS-Bench-Suite-Zero recipe of feeding all proxies into an XGBoost surrogate. We train it on the same small labeled subset of architectures, with sizes from 50 to 500, and give it the same hyperparameter-tuning budget as any learned version of our score. The closest reported figure for a proxy ensemble is Spearman 0.82 for the synflow, jacob_cov and snip vote on NAS-Bench-201, from Zero-Cost Proxies for Lightweight NAS. That figure comes from a vision space. There is no reported result on Lacuna for any zero-cost proxy on NAS-Bench-Graph, so the audit itself produces the reference numbers. Beating this baseline means a higher within-stratum Spearman correlation and a higher top-1% recall on a majority of the nine datasets, with seed-bootstrap confidence intervals that exclude zero difference.
The strongest overall competitor is truncated training. NAS-Bench-Graph logs per-epoch validation accuracy, so we can read off one-epoch and few-epoch accuracy at no extra compute. We compare at matched wall-clock cost, measured on the same GPU, because the gap between FLOPs and wall-clock time documented by Abdelfattah et al. makes FLOP parity misleading.
The key ablations are the label-free and graph-blind variants of our score. If either matches the full score, the claimed mechanism is wrong.
Why not just…?
Why not just run random search? Random search is strong on NAS-Bench-Graph, but only because the benchmark's lookup table makes evaluation free. Outside the table, each evaluation is a training run, which cost 12 GPU hours for search on PubMed in Graph Neural Architecture Search. Random search is our naive reference, and the trained-evaluations-to-target curve shows directly whether proxy filtering saves anything.
Why not just rank by parameter count or FLOPs? NAS-Bench-Graph reports that top architectures span widely varying latencies. GASSIP found models that keep only 6% of GAT's parameters on Physics while still outperforming it. Size alone should therefore miss strong small models. The within-stratum test settles this, because size varies little among architectures with identical operator counts.
Why not just train each candidate for one or two epochs? This is the real threat. On Cora-sized graphs an epoch costs about as much as a forward pass, so truncated training may simply win. We accept that outcome and report it. The proposal's value claim then narrows to the regime where it can hold: large graphs such as ogbn-arxiv, ogbn-proteins and Coauthor-Physics, where one full-graph forward pass with no backward pass and no optimizer state costs meaningfully less than an epoch, and full-space screening of tens of thousands of candidates. If truncated training also wins at matched wall clock on the large datasets, the constructive claim is falsified, and the audit becomes the contribution.
Why not just search on a small subgraph and transfer the winner? NAS-Bench-Graph shows that winners do not transfer across datasets, and GAUSS shows that subgraph training collapses ranking consistency to roughly $\tau \approx 0.2$. We nonetheless include a cheap version as a check: alignment computed on a 10% induced subgraph. This measures whether our score inherits the same collapse.
Decisive Checks
Three results decide the proposal. First, the operator-composition bias must appear: on most of the nine datasets, gradient proxies should show a gap between overall and within-stratum correlation that accuracy itself does not show. Second, the alignment score must beat the XGBoost proxy ensemble and parameter count within strata, and must match or beat one-epoch training at equal wall clock on at least ogbn-arxiv and Physics. Third, the graph-blind ablation must lose clearly on the dataset-shift test. That would show the score's advantage comes from reading the data graph. If the first check fails, gradient proxies are more operator-agnostic than the cross-architecture literature suggests, which is itself worth reporting. If the third fails, the idea of estimating architecture quality jointly with the data graph at initialization does not hold up.
References
- NAS-Bench-Graph: Benchmarking Graph Neural Architecture Search
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies
- Towards Lightweight Graph Neural Network Search with Curriculum Graph Sparsification
- Faithful and Accurate Self-Attention Attribution for Message Passing Neural Networks via the Computation Tree Viewpoint
- Nonparametric Teaching for Graph Property Learners
- On Random Weights and Unsupervised Feature Learning
- Zero-Cost Proxies for Lightweight NAS
- Rethinking Performance Estimation in Neural Architecture Search
- GENNAPE: Towards Generalized Neural Architecture Performance Estimators
- Large-Scale Graph Neural Architecture Search
- Graph Neural Architecture Search