Graph neural networks (models that update each node by averaging in its neighbors' features, layer after layer) lose node individuality as they get deeper. All node representations drift toward the same vector, a failure called over-smoothing. Nearly everything known about it comes from two sources: loose bounds on a fixed graph as depth goes to infinity, and experiments on a handful of real benchmarks where depth is rarely needed anyway. Neither tells us how the onset of collapse depends on the graph's multi-scale structure, or how it scales as graphs grow.
A separate literature on deterministic recursive graphs offers exactly that missing lever. These are graphs grown generation by generation through fixed rules such as edge-attached triangles, copied modules, or Kronecker products. For them, the full spectrum of generation $t+1$ follows from generation $t$ through an explicit low-degree map, a result called spectral decimation. We propose to use these graphs as exactly solvable laboratories for over-smoothing. From the decimation recurrences we derive closed-form laws for how many layers a graph network survives before its representations collapse, how that number scales with graph generation, and how fast backward gradients die. We then plant labels at known structural scales, test which existing remedies obey or break these laws, and check whether graph families with matched statistics predict failure modes on real benchmarks.
Core Claim
In a linear message-passing network with normalized propagation matrix $\hat A$, the part of the features that distinguishes nodes decays like $\rho^L$. Here $L$ is depth and $\rho(G) = \max_{i \ge 2} |\mu_i(\hat A)|$ is the largest non-trivial eigenvalue magnitude. The effective rank trajectory, the entropy-based rank measure shown by Are we measuring oversmoothing in graph neural networks correctly? to track accuracy loss better than Dirichlet energy, depends on the whole spectrum and on eigenvalue multiplicities.
For recursive families, decimation gives $\mu(G_{t+1}) \in f^{-1}(\mu(G_t))$ plus explicitly counted new eigenvalues. Multiplicities come from the same combinatorics. Both $\rho_t$ and the full rank trajectory are therefore computable exactly for graphs of $10^9$ nodes without any matrix computation. The collapse depth for tolerance $\varepsilon$ is
$$L^*(t,\varepsilon) = \frac{\log(1/\varepsilon)}{\log(1/\rho_t)},$$
which follows from the geometric decay above. Tracking $\rho_{t+1} = g(\rho_t)$ through the decimation map turns this into a scaling law in $t$.
Our claim is that different recursive families fall into qualitatively distinct regimes. In small-world pseudo-fractal and triangulated webs (Xie et al., Rong et al.), we expect $\rho_t$ to stay bounded away from 1, so collapse happens at a fixed depth independent of size. In hierarchical modular copies (Yuan et al., High Modularity Creates Scaling Laws), we expect $\rho_t \to 1$ geometrically. Collapse there slows down, but the depth needed to see across modules grows at the same time. Bipartite families such as $q$-subdivision graphs (Spectra, Hitting Times and Resistance Distances of q- Subdivision Graphs) carry eigenvalue $-1$ and oscillate rather than collapse, unless self-loops are added.
What is new is that these laws make falsifiable, per-family predictions about which remedy should help. Normalization should matter only when collapse depth is shorter than the needed receptive field. High-pass channels should matter when labels live in high-frequency eigenvectors. Hierarchical shortcuts should matter mainly in the modular regime. Existing work never makes predictions of this kind, because the graph is always held fixed.
Research Program
The theory component derives $\rho_t$, the multiplicity-weighted spectrum, and the linear-model effective rank of $\hat A^L X$ for four families. These are pseudo-fractal webs with clique attachment (Zhu et al.), iterated triangulations, hierarchical modular copies, and Kronecker graphs (Leskovec et al.). We reuse the normalized Laplacian transformation functions of Xie et al. and the characteristic polynomial recurrences of Qi et al. as the method supply.
One caveat is important. Decimation results are stated for the random-walk or symmetric normalized operator without self-loops. The self-loop operator used in standard graph convolutional networks shifts degrees non-uniformly, so for it we will compute spectra numerically up to about $10^5$ nodes and report where the closed form stops being exact. The same recurrences give the decay rate of backpropagated gradients in the linear setting. This extends the backward over-smoothing analysis of Backward Oversmoothing, which showed that gradients through deep message passing are low-pass filtered and trap earlier layers, from a fixed graph to a growing family.
The empirical component turns each family into a node-classification task with known ground truth. A node's label is the index of its level-$k$ module copy, or its creation generation, or its position within a triangle. Features are fully removed on unlabeled nodes, following the missing-feature setting of PairNorm in which depth is genuinely required. Because the label lives at a known scale, the minimum useful receptive field $L_{\min}(k)$ is known exactly. The central quantity is then the ratio $L^*/L_{\min}$. We predict that trained nonlinear networks fail when this ratio falls below 1, and that each remedy shifts the failure boundary by an amount we can measure.
We train on generations $t$ small enough for full-batch training, then test whether the fitted boundary extrapolates to larger $t$ using only the closed-form spectrum. The transfer step matches real graphs (Cora, Chameleon, ogbn-arxiv) to the recursive family whose measured $\rho$ and spectral decay profile they most resemble. We then ask whether that family's predicted remedy ranking holds on the real graph.
Baselines
The naive reference points are a two-layer graph convolutional network and a deep plain one. The shallow model tests whether depth is needed at all on a given task. The deep plain model is the collapse case whose behavior the theory must predict. Both are run on identical graphs, splits, and feature masks.
The residual baseline adds an identity or initial-residual shortcut at every layer. This is the remedy most practitioners reach for, and the one Backward Oversmoothing identifies as partially fixing gradient traps.
The strongest normalization competitor is PairNorm, which re-centers and rescales node features to keep their total pairwise distance fixed. It is the reference for the missing-feature regime. Its reported number is 74.5% accuracy for PairNorm-SGC on Cora with all unlabeled-node features missing, against 42.3% for vanilla SGC, and it holds accuracy to 60 layers.
For frequency remedies we use the filterbank network of Complete the Missing Half, which adds a high-pass channel and is reported to gain roughly 10% on Texas and Cornell. We also use Geometric Scattering Attention Networks, which adds wavelet band-pass channels and reports 61.2% on Chameleon versus 28.2% for GCN.
For hierarchical remedies we use Hierarchical Multi Scale Graph Neural Networks, which builds a $k$-means supernode hierarchy with Haar wavelets. That paper reports stability to 64 layers and up to 3% node-classification gains on ogbn-arxiv, but no reported result was found on Lacuna for its absolute arxiv accuracy. We also use the METIS-partition fractal nodes of Are Graph Transformers Necessary?, which report 0.7018 average precision on Peptides-func.
The key ablation replaces each recursive graph with a degree-preserving random rewiring. This keeps the degree sequence but destroys the recursive structure, and it isolates whether exact self-similarity, rather than degree heterogeneity, drives the predicted regime.
All methods get the same hidden width, the same depth grid (2 to 128), the same 50-trial hyperparameter search, and 10 seeds. Since this is a science proposal rather than a method proposal, "beating" a baseline means something specific. The derived laws must predict each baseline's failure depth within a factor of 1.5, and the predicted remedy ranking per family must hold across at least three of the four families. That is a stronger standard than any single accuracy number.
Why not just…?
Why not just eigendecompose the graph numerically instead of using decimation? For graphs under about $10^5$ nodes, numerical computation gives the same answers, and we use it as the check. The closed form earns its place in two ways. It gives the asymptotic law in $t$, which numerics can only extrapolate. It also gives exact eigenvalue multiplicities, which effective rank depends on and which numerical solvers blur in near-degenerate spectra. If the extrapolation experiment shows the closed form adds nothing over a curve fit to small-$t$ numerics, we will say so. That would weaken the theoretical contribution, though not the benchmark contribution.
Why not just use stochastic block models as the synthetic testbed? Block models are the standard choice, and they are a real competitor. Their spectra, however, are known only in expectation and at a single scale, so they cannot represent labels nested at several scales with known receptive fields. We will include a hierarchical block model matched to the modular family's edge densities. If it reproduces the same failure boundaries, then exact recursion is unnecessary, and we will report that result.
Why not just run deep networks on real benchmarks and compare? On feature-rich benchmarks, depth is rarely needed (PairNorm). In addition, label scale, graph bottlenecks, and feature quality are all confounded, which is why remedies are rarely separated cleanly. The transfer experiment below tests whether our controlled laws say anything about real graphs, so the real-benchmark comparison is included rather than replaced.
Why not just add residual connections and stop worrying? Residual connections may well flatten every regime, and we would treat that as a finding. The theory predicts they will not in one case: modular graphs where $L_{\min}$ grows with $t$. There, the missing ingredient is receptive field rather than collapse, and hierarchical shortcuts should win.
Proposed Experiments
The first decisive check tests the linear theory. We compare the predicted and measured effective rank and gradient norm of $\hat A^L X$ across all families, for $t$ up to the largest size that can be computed numerically. The theory fails if the error exceeds 5% in the self-loop-free setting.
The second check is the phase diagram. For each family and remedy, we plot accuracy over depth $L$ and label scale $k$, then overlay the predicted boundary $L^* = L_{\min}(k)$. The central claim fails if the boundaries of the deep plain and residual models do not track $\rho_t$, or if the rewired ablation shows the same boundaries.
The third check tests extrapolation. We fit on $t \le 5$, predict failure depth at $t = 7$ and $8$ from closed-form spectra, and verify by training.
The fourth check is transfer. We match Cora in the missing-feature setting, Chameleon, ogbn-arxiv, and Peptides-func to their nearest family by spectral profile, and ask whether the predicted remedy ranking holds. The comparison points are PairNorm's 74.5% on Cora, GSAN's 61.2% on Chameleon, and fractal nodes' 0.7018 on Peptides-func. The proposal succeeds even if no new model tops these numbers, provided the laws correctly predict which of these remedies wins where and at what depth each one breaks.
References
- Are we measuring oversmoothing in graph neural networks correctly?
- On the spectrum of the normalized Laplacian of iterated triangulations of graphs
- A deterministic small-world network created by edge iterations
- Average distance in a hierarchical scale-free network: an exact solution
- High Modularity Creates Scaling Laws
- Spectra, Hitting Times and Resistance Distances of q- Subdivision Graphs
- Resistance Distances In Simplicial Networks
- Kronecker Graphs: An Approach to Modeling Networks
- The normalized Laplacian spectrum of subdivisions of a graph
- Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?
- PairNorm: Tackling Oversmoothing in GNNs
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Geometric Scattering Attention Networks
- Hierarchical Multi Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
- Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs