Kernel Collapse Certificates for Training-Free Spatio-Temporal Graph Architecture Search

Searching for a good traffic- or sensor-forecasting network usually means training hundreds of candidate models. Most candidates fail for one predictable structural reason. They stack graph-averaging layers in a way that makes every node's representation look the same, a failure known as over-smoothing. We propose to detect this failure before any training happens. The tool is a closed-form calculation of what each candidate network computes when its layers are infinitely wide. In that limit a randomly initialized network becomes a Gaussian process, a distribution over functions fully described by a similarity matrix (a "kernel") between inputs. That matrix can be built layer by layer with exact formulas: graph averaging, ReLU, and temporal convolutions at several kernel sizes and dilations each have their own rule. If the final kernel over (node, time-window) pairs has collapsed toward rank one, the architecture cannot tell nodes apart, and it can be discarded without being trained. The surviving candidates are then ranked by how well their kernel lines up with the forecasting targets.

The opportunity is that spatio-temporal architecture search sits exactly where current cheap evaluators are weakest. Architecture search for these models still trains every candidate, either by random search in a hand-found good region or by sharing weights across a large "supernet." Meanwhile the zero-cost scores developed for image networks neither see graph structure nor detect homogenization. A per-architecture kernel computed analytically is deterministic, carries no seed noise, and can be cached and reused across architectures that share early layers. It also yields a testable prediction about why some layer orderings over-smooth and others do not.

Core Claim

For search spaces that mix graph message passing with multi-scale temporal convolutions, the largest source of variation in final accuracy is structural collapse of the node-wise representation. That collapse is fully visible in the infinite-width covariance at initialization. We claim a two-stage, training-free procedure will recover most of the top-performing architectures at a small fraction of the cost of training-based search. The first stage is a hard filter on the effective rank of the architecture's recursive kernel, called a "collapse certificate." The second stage ranks the survivors by kernel–target alignment.

We do not claim that static kernels predict fine-grained rank among good models. Demystifying the Neural Tangent Kernel from a Practical Perspective shows that initialization-time tangent-kernel proxies have negative rank correlation on NAS-Bench-101. The cause is "kernel twisting," in which the empirical kernel bends toward the labels in the first epochs of training. That paper constrains our design. We therefore use the kernel mainly as a filter for a failure mode that twisting cannot repair, namely rank collapse forced by the graph operator. We test explicitly whether a short warm-up is still needed to order the survivors.

Why this is not already done

The closest work splits into three groups, and none does what we propose.

Temp-G³NTK builds a recursive infinite-width kernel over temporal graphs and uses it directly as a predictor, with no training. It does not use multi-scale temporal convolutions, does not study whether its kernel degenerates with depth, and is never used to rank finite architectures.

SimpleSTG found empirically that stacking consecutive spatial modules causes over-smoothing and that good architectures interleave spatial and temporal operations. It still trains every candidate. AutoSTF speeds up the search by decoupling temporal and spatial search over a weight-sharing supernet. It analyzes neither over-smoothing nor kernels.

Are we measuring oversmoothing correctly? shows that effective rank of trained features tracks accuracy (average Pearson 0.91 on static node classification) far better than Dirichlet energy. It never uses rank as a pre-training search signal and never computes it on infinite-width kernels or temporal models.

The new combination is therefore threefold: analytic recursive kernels for multi-scale spatio-temporal architectures, an effective-rank collapse certificate on those kernels, and the use of both as a search filter.

Research Program

Kernel construction. The method side reuses the recursions from the infinite-width literature. Our contribution there is composing them for a new operator set. ReLU layers use the degree-1 arc-cosine map of Kernel Methods for Deep Learning, justified by the Gaussian-process limit of Matthews et al.. Temporal convolutions use the observation of Deep Convolutional Networks as shallow Gaussian Processes that, without pooling, only same-position covariances need tracking. A temporal convolution with width $k$ and dilation $d$ then becomes a weighted sum of covariances at offsets $0, d, \dots, (k-1)d$. Parallel multi-scale branches add their kernels; concatenation sums them with weights set by the branch widths. Graph aggregation with normalized adjacency $\hat A$ acts on the node index of the kernel as $K \mapsto \hat A K \hat A^\top$. A high-pass channel in the style of FB-GNN uses $I-\hat A$ instead. Skip connections add kernels.

Making the computation affordable. The kernel is built on a subsample of $M$ training windows. It is full in the (window, node) index and diagonal in time position. For PeMS08 with 170 nodes and $M=32$ windows, that is a matrix of roughly 5,400 by 5,400 per time step, which fits on one GPU. Candidates in a cell-based space share prefixes, so we store intermediate kernels in a prefix tree. Scoring the whole space then costs roughly the number of distinct prefixes, not the number of architectures.

Scores. Let $K_L$ be the final-layer kernel and $p_i$ its normalized eigenvalues. Let $\operatorname{erank}(K_L)=\exp(-\sum_i p_i\ln p_i)$ be its effective rank, the measure of Zhang et al.. Let $Y$ be the centered matrix of future values for the same windows and nodes. The alignment score is

$$ \mathcal{A}(K_L,Y)=\frac{\langle K_L, YY^\top\rangle_F}{\|K_L\|_F\,\|YY^\top\|_F}. $$

Stage one discards architectures whose $\operatorname{erank}(K_L)$ falls below a fraction $\rho$ of the input kernel's effective rank. Stage two ranks the remaining architectures by $\mathcal{A}$. Using a filter followed by a ranking, rather than a weighted sum, avoids tuning a trade-off coefficient. It also respects the warning in Zhang et al. that high rank is necessary but not sufficient: white noise has maximal rank.

Analysis. For stacked $\hat A$ and ReLU steps, the node-wise correlation should contract toward a constant. Two forces drive this: the second eigenvalue of $\hat A$, and the known pull of the arc-cosine map toward correlation one. Temporal convolutions act only on the time index. Our prediction is therefore that, at infinite width, interleaving temporal layers does not by itself slow spatial collapse; skip connections and high-pass channels do. If this holds, SimpleSTG's "cherry region" effect would be explained by the skip connections that come with interleaving, not by the interleaving itself. If it fails, the infinite-width kernel misses something finite networks exploit. That would be equally informative and would limit how far our filter can be trusted.

Baselines

Training-based random search. The naive reference is random search with training inside the SimpleSTG search space, which SimpleSTG shows beats differentiable search. It reports PeMS08 MAE of 14.64, against 14.82 for AutoCTS. This is the strongest existing method on the question because it already encodes hand-found knowledge of where over-smoothing happens. We rerun it in our own pipeline with identical data splits, training recipe, and GPU-hour budgets. Beating it means matching its selected-architecture MAE within seed noise at a fifth of its compute, or improving MAE at equal compute.

Supernet search. AutoSTF is the strongest supernet competitor. The file reports no absolute AutoSTF MAE on PeMS08, only that it had the lowest MAE among its baselines and searched up to 13.48× faster than AutoCTS. We run it from released settings in our pipeline and compare both MAE and search wall-clock.

Off-the-shelf zero-cost proxies. These are synflow, NASWOT, grad-norm, snip, FLOPs, and parameter count, plus the XGBoost ensemble of all thirteen proxies from NAS-Bench-Suite-Zero. As reference points, EZNAS-A reports Kendall τ of 0.65 and NASWOT and synflow 0.57 on NAS-Bench-201 (EZNAS). The ensemble surrogate is trained on the same number of labeled architectures that our method uses to set $\rho$.

Warm-up alignment. Label-gradient alignment after one epoch from Demystifying the NTK reports rank correlation 0.308 on NAS-Bench-101. It is run with matched warm-up compute.

Ablations. The ablation that isolates our key ingredient replaces the analytic kernel with a Monte Carlo estimate: the empirical feature Gram matrix of finite random-width networks, averaged over a few seeds, at matched wall-clock. Further ablations use rank alone, alignment alone, the tangent kernel instead of the Gaussian-process kernel, and Dirichlet energy in place of effective rank.

Success criteria. On the trained-ground-truth sets, success means Kendall τ and top-10% recall above every zero-cost baseline. It also means a stage-one filter that removes at least half the space while discarding under 5% of the true top decile.

Why not just…?

Why not just run random search inside the known good region? This is a strong baseline. The good region was found by expensive sweeps over millions of skip configurations and hundreds of hyperparameter settings. Its location is specific to the datasets it was found on, and every candidate still needs training. Our transfer experiment applies a filter calibrated on PeMS08 to METR-LA and to KnowAir, where no such region has been published. It will show whether the kernel certificate finds a comparable region automatically. If random search in a SimpleSTG-derived region still wins at equal compute on new data, the filter's value is limited to the analysis.

Why not just use synflow, NASWOT, or the proxy ensemble? None of the thirteen standardized proxies sees graph homogenization. They are also known to track model size. The Suite-Zero ensemble is a real threat because a learned surrogate can absorb many signals. We therefore include it at an equal labeling budget, and also test adding our two scores as features to it. If the ensemble without our features already matches the ensemble with them, our scores add nothing.

Why not just measure effective rank of a randomly initialized finite network? This is the most serious alternative. The analytic kernel is the infinite-width expectation of that same Gram matrix, so a few random draws might approximate it well enough. Our answer is empirical. The Monte Carlo ablation at matched wall-clock decides it, measured by rank stability across seeds and by τ. The analytic version has two structural advantages: it carries no seed variance, and its intermediate kernels can be cached across shared prefixes, which finite random networks of different topologies cannot share. If the finite estimate is as accurate and as cheap at search-space scale, we will report the analytic kernel only as the explanatory model for the collapse analysis and recommend the finite estimate in practice.

Why not just warm up for one epoch and use label-gradient alignment? Kernel twisting is real, so warm-up may be needed to order the top candidates. We test it in two roles: as a competitor, and as an optional second stage applied only to the filtered survivors. The filter is worth keeping if it cuts warm-up cost by the pruned fraction without lowering top-decile recall.

Proposed Experiments

Ground truth. Because no tabular spatio-temporal benchmark exists, we build one. About 800 architectures are drawn uniformly from a search space with four choices: SimpleSTG-style ordering and skip choices, temporal operators with widths {2, 3, 7} and dilations {1, 2, 4} in single or parallel branches, low-pass versus high-pass spatial channels, and depth up to 10 blocks. Each is trained on PeMS08 and PeMS04 with three seeds, which we estimate at a few hundred GPU hours, and the results are released. As a sanity check on the static case, we also score NAS-Bench-Graph (Qin et al.), whose 26,206 trained GNNs give free ground truth on Cora, ogbn-arxiv and seven other datasets.

Metrics. We report Kendall τ, top-10% recall, the filter's false-discard rate, and the final test MAE, RMSE and MAPE of the architecture chosen under fixed GPU-hour budgets.

Decisive checks. Four checks decide the outcome. First, whether the certificate removes most of the space while retaining the top decile. Second, whether alignment ranking of the survivors beats synflow, NASWOT, and the ensemble. Third, whether the analytic kernel beats the finite random-network estimate at matched cost. Fourth, whether the predicted depth at which collapse begins, computed from the second eigenvalue of $\hat A$, matches the depth at which trained MAE degrades, and whether interleaved temporal layers delay collapse only when skip connections accompany them. A negative result on the fourth check would itself be a finding: it would mean that the remedy SimpleSTG found empirically works through finite-width training dynamics that the static kernel cannot see.