Jacobian Rank Screening for Deep Graph Networks

Graph neural networks pass messages between neighboring nodes, and when many such layers are stacked they tend to fail. Node representations blur toward one shared vector (over-smoothing). There is also a second, less obvious failure: the training signal flowing backward blurs the same way, so the early layers never learn. We propose to score candidate graph architectures before any training by measuring how much of both kinds of node-to-node distinction survives through the untrained network. The quantity we use is the effective number of independent directions in which the network's outputs respond to perturbations of its inputs, and in which its intermediate layers receive gradient. The object that holds this information is the network's full Jacobian, a four-way array indexed by output node, output channel, input node and input channel. It is far too large to store for any real graph. Following the logic of implicit tensor methods, we never build it. We probe it with a handful of random forward-mode and reverse-mode derivative passes, and we read its rank off a small sketch.

The opportunity matters because the one existing search method for anti-smoothing graph architectures trains a full super-network and needs class labels. Meanwhile, cheap "zero-cost" scores for ranking architectures without training have been built and tested only on vision and language models. If a label-free score that costs a few forward passes can rank deep graph architectures nearly as well as short training does, searching for graph architectures that work at 16 to 32 layers becomes affordable. That depth is where missing-feature node classification and molecular property regression appear to need networks to operate.

Core Claim

Our claim is that over-smoothing, in both its forward and backward forms, is a collapse of the node dimension of the network's layer-to-layer Jacobians. We also claim that a randomized, matrix-free estimate of this collapse predicts trained performance across a mixed graph search space better than the rank of the activations alone. That search space includes normalization layers, residual connections and deep supervision.

Concretely, let $H^{(l)} \in \mathbb{R}^{n \times d}$ be the node representations at layer $l$ of an $L$-layer network on a graph with $n$ nodes. Draw $k$ random input perturbations $U_j \in \mathbb{R}^{n \times f}$, where $f$ is the input feature width, and $k$ random output directions $G_j \in \mathbb{R}^{n \times c}$, where $c$ is the output width. One forward-mode pass per $U_j$ gives the tangent $T^{(l)}_j = \partial H^{(l)}[U_j]$ at every layer at once. One reverse-mode pass per $G_j$ gives the cotangent $C^{(l)}_j = (\partial H^{(L)}/\partial H^{(l)})^\top[G_j]$ at every layer at once. Stacking these horizontally gives two $n \times kd$ sketches. These are, up to scaling, randomized range sketches of the node-mode unfolding of the Jacobian from the input to layer $l$ and of the Jacobian from layer $l$ to the output. The score is

$$S = \frac{1}{L}\sum_{l=1}^{L}\Big[\log \mathrm{Erank}\big([T^{(l)}_1,\dots,T^{(l)}_k]\big) + \log \mathrm{Erank}\big([C^{(l)}_1,\dots,C^{(l)}_k]\big)\Big],$$

Here $\mathrm{Erank}$ is the exponential of the entropy of the normalized singular values, as used by Are we measuring oversmoothing in graph neural networks correctly?. Each sketch is centered across nodes, so a collapse onto the constant vector counts as rank one.

The forward term asks how many distinct "which input node moved" signals survive to layer $l$. The backward term asks how many distinct "which output node needs to change" signals reach layer $l$. That second term is a direct, label-free reading of the backward over-smoothing described by Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?. The cost is about $2k$ passes plus a Gram eigenproblem of size $kd$, which is linear in $n$.

The method has an analytic check in the linear case. A linear graph convolution has Jacobian equal to the propagation matrix raised to the power $l$, tensored with a product of weight matrices. Its node-mode spectrum is therefore the spectrum of the propagation matrix raised to the power $l$, which collapses to rank one with depth. A residual block replaces that matrix with a mixture of it and the identity, and so decays more slowly. The sketch should reproduce these curves exactly on small graphs.

How this relates to prior work

Three papers motivate the proposal by finding the gap. GraTO searches over graph convolution types combined with PairNorm, DropEdge and its own feature-masking operation. It uses a differentiable super-network and adds a loss that pushes apart nodes of different classes. It needs labels and full super-network training, and it measures smoothing by mean pairwise distance. We keep a GraTO-like search space but replace the search signal with a training-free, label-free score. NEAR scores architectures by the effective rank of activations at initialization. It reports Spearman 0.70 on NAS-Bench-101, but it was never applied to message passing. Its authors also concede that activation rank captures expressivity and not trainability. We differ in measuring the rank of the network's sensitivity rather than of its outputs, and in adding the backward direction that targets trainability. Zhang et al. show that effective rank of embeddings tracks accuracy, with an average Pearson correlation of 0.91, across depths of fixed GCN and GAT models. Their result is evidence that rank is the right currency. It is not a search method, and it compares depths of a single architecture rather than ranking heterogeneous candidates.

Two papers constrain the design. Keriven's analysis implies that forward-only scores can be fooled by architectures whose features stay diverse while their gradients collapse, which is why the backward sketch exists. Revisiting Over-smoothing in Graph Neural Networks finds that PairNorm combined with deep supervision does worse than deep supervision alone. A useful score must therefore penalize some combinations of individually helpful operations rather than add up their benefits. Our search space includes exactly these combinations as a test.

Two papers supply the method. Estimating Higher-Order Moments Using Symmetric Tensor Decomposition evaluates contractions of a moment tensor directly from raw samples, never forming the tensor. It also initializes with a randomized range finder. We apply the same move to the Jacobian tensor: derivative passes play the role of their tensor-times-vector products, and random probes play the role of their range finder. DFacTo is the precedent for refactoring a product that would explode in size, here the Khatri-Rao product, into a sequence of sparse products. We do not reuse its code, but the principle is the same. The cost of implicit methods is repeated passes over data, a limitation noted by Sherman and Kolda. Here that cost becomes $2k$ graph passes, and we measure how small $k$ can be.

Research Program

The work has three parts. First, we build the estimator in a standard autodiff library using forward-mode and reverse-mode products. We validate it against exact Jacobians on graphs small enough to form them, such as Cora subgraphs with a few hundred nodes. We report sketch error as a function of $k$ and verify the linear-model spectra described above. This step also covers attention, PairNorm and residual blocks, where Keriven's theory does not reach. For these we will show empirically whether backward rank decays and how fast.

Second, because the file lists no tabular benchmark for graph architecture search, we build one. The search space has blocks drawn from GCN, GAT, GraphSAGE and SGC aggregators. Optional operations are PairNorm, DropEdge, residual connections and per-layer deep-supervision heads, and depth ranges from 2 to 32. We sample about 3,000 architectures and train each with a fixed recipe and three seeds. The datasets are Cora, Citeseer and Pubmed, each in the standard setting and in the PairNorm missing-feature setting; Chameleon, Squirrel and Amazon Ratings for heterophily; OGB-Arxiv for scale; and ESOL and Lipophilicity for graph-level regression. The resulting table of trained accuracies and errors is a contribution in its own right, since every graph proxy claim in the file currently lacks one.

Third, we score every architecture at initialization with our proxy and all baselines, using identical mini-batches and seeds. We then run an actual search with each score under a fixed wall-clock budget.

Baselines

The naive reference points are parameter count and FLOPs, together with the fixed choice of a 2-layer GCN. The FLOPs comparison matters because NAS-Bench-Suite-Zero found FLOPs among the most robust proxies across its 28 tasks, and found many proxies biased toward large models. For graphs, that bias should actively select deep, smoothed networks, and we will check whether it does. The 2-layer GCN represents the "just stay shallow" position. Beating it means a searched architecture wins on the missing-feature and molecular tasks. On those tasks the reported references are PairNorm-SGC at 74.5% on Cora with fully missing features, from PairNorm, and DSGNN at 0.694 RMSE on ESOL, 0.594 on Lipophilicity and 77.5% on Pubmed at 12 layers.

The standard zero-cost proxies are grad_norm, snip, synflow, jacob_cov and nwot, implemented as in NAS-Bench-Suite-Zero and adapted to graph inputs. We include the EZNAS-A proxy from EZNAS, which reports Kendall tau 0.65 on NAS-Bench-201 CIFAR-10 but was evolved for convolutional blocks. We also include a learned ensemble of all proxies, following the finding of NAS-Bench-Suite-Zero that ensembles improve correlation by up to 42%. Any fair win must beat this ensemble, not only its members.

The strongest training-free competitor is NEAR applied to graphs: the summed effective rank of pre- and post-nonlinearity node activations at every layer. Alongside it we include Zhang et al.'s final-layer embedding effective rank. Both use the same batch as our proxy and exact eigendecomposition of the small $d \times d$ Gram matrix, which is cheap for node embeddings. No reported result was found on Lacuna for any rank-based proxy on a graph architecture space. The nearest numbers are NEAR's Spearman 0.70 on NAS-Bench-101 and Zhang et al.'s 0.91 Pearson across depths. Neither is directly comparable, and we will not treat them as targets.

The strongest overall competitor is short training, in the spirit of the budgeted early-stopping estimation of Rethinking Performance Estimation in Neural Architecture Search. Each candidate is trained for a few epochs, with the number of epochs chosen so that total compute is 10× and 100× our proxy's cost. Our proxy beats it if it matches the 10×-budget version's Kendall tau within 0.05 at a tenth of the cost. If it falls below the 10× version, we report a loss on this axis. GraTO itself is run with its released search space reduced to ours and given the same GPU-hours as our full search pipeline. The comparison is on the final test accuracy of the selected architecture. GraTO reports only integrative ranks in the file, so no reported GraTO accuracy was found on Lacuna to quote.

Three ablations isolate the key ingredients: forward sketch only, backward sketch only, and the sketch with exact Jacobians on small graphs. The first two test whether the backward term carries information beyond the forward term. The third tests whether randomization costs ranking quality.

Why not just…?

Why not just compute activation effective rank, as NEAR does? This is the real threat. Activation rank is already cheap for node embeddings, so the speed argument does not apply to it. Our bet is narrower. Normalization layers and residual connections can keep activations diverse while the network's sensitivity and gradients collapse. Zhang et al.'s observation that high rank is necessary but not sufficient points the same way. The decisive check is the subset of architectures with PairNorm, residual connections or deep supervision at depth 16 or more, together with the top-10% tau, where EZNAS notes that proxies degrade. If NEAR-for-graphs matches our proxy there, we will say so. The contribution then shrinks to the benchmark plus the finding that activation rank suffices.

Why not just train each candidate for a few epochs? Short training uses labels and actual optimization, so it naturally sees Keriven's late-stage trap, in which the final layer converges first and freezes everything earlier. An initialization score may miss that trap. We give short training a fair compute ladder and report the full cost-versus-correlation curve rather than one point. Our case rests on the low-cost end of that curve and on settings without labels, such as screening architectures before any annotation exists.

Why not just add PairNorm or deep supervision to every model? Elinas and Bonilla's negative interaction between the two, and PairNorm's own admission that it rarely raises peak accuracy on feature-rich benchmarks, suggest no single fixed recipe wins everywhere. The benchmark will show this directly. Fixed recipes appear as points in the search space, and we report how often each is the best architecture per dataset.

Why not just use randomized SVD on the activations and skip Jacobians? For activations this is fine, and we do so in the NEAR baseline. The implicit machinery is needed only because the object we care about, the node-to-node sensitivity, is an $n \times c \times n \times f$ array. That array cannot be formed even for Cora, but it can be probed in $2k$ passes.

Proposed Experiments and Decisive Checks

The primary metrics are Kendall tau and Spearman correlation between each score and trained performance per dataset. We also report tau within the top 10% of architectures and the test accuracy or RMSE of the architecture chosen by a fixed-budget evolutionary search driven by each score. Wall-clock time and peak memory are reported for every score.

Four results would decide the question. The first is estimator fidelity: on small graphs, sketch effective rank should be within 10% of exact Jacobian effective rank at $k \le 16$, and should reproduce the closed-form linear-GCN decay. The second is the backward term's value. On deep residual and PairNorm architectures, the backward sketch should separate trainable from untrainable networks where activation rank does not. The pattern we look for is high forward rank, collapsed backward rank, and low trained accuracy. Observing this would confirm Keriven's mechanism outside vanilla models, and its absence would weaken our core claim. The third is the interaction test: the score should rank deep supervision alone above deep supervision combined with PairNorm whenever training does. The fourth is search outcome. On missing-feature Cora and on ESOL and Lipophilicity, architectures selected by our score at a total screening cost under one GPU-hour should reach the cited PairNorm and DSGNN references. As a transfer sanity check, we also run the proxy on NAS-Bench-101 against NEAR's reported 0.70. We do not expect to win there, but a large drop would suggest the score is graph-specific in an uninteresting way.