What Features Can Reach: A Controllability Ceiling for Deep Graph Networks

Deep graph neural networks, which update each node by repeatedly averaging its neighbors' feature vectors, are known to lose accuracy as layers are added. This is usually called over-smoothing. A long list of fixes now trains such networks to hundreds or even a thousand layers, yet there is still no agreed way to say how much of the failure is unavoidable given the graph and the input features, and how much comes from a fixable design or training problem. This note proposes to answer that with an old tool from control theory. Treat the node features as the "control input" that is injected into a linear diffusion on the graph. Then ask which directions in node-space that input can ever reach, at any depth and under any reweighting of the layers.

Control theorists already know that symmetry blocks reachability. When two nodes look identical to the rest of the network and receive identical inputs, no signal can push them apart. Directions that the inputs do not touch stay dark forever. Near-symmetries leave directions that are reachable only weakly. We propose to compute this reachable set and its graded strength, using a quantity called the controllability Gramian, from the graph and the features alone, before any training. We then test whether it predicts which nodes deep graph networks can and cannot classify, and how much each anti-smoothing method can possibly recover. The practical outcome is a training-free diagnostic. It separates "the data and graph make these nodes indistinguishable" from "the network failed to use what was available." It also yields a small symmetry-breaking intervention that targets only the dark directions.

Core Claim

Consider any linear message-passing network that outputs a polynomial in the normalized adjacency $\tilde A$ applied to the features $X \in \mathbb{R}^{n\times f}$, of the form $H=\sum_{k=0}^{L}\tilde A^k X\Theta_k$ with arbitrary weight matrices $\Theta_k$. This family covers plain stacking, residual and initial-residual sums, and polynomial spectral filters. The column space of $H$ is contained in the depth-$L$ reachable subspace of the pair $(\tilde A, X)$. That subspace is the range of the Gramian

$$G_L=\sum_{k=0}^{L}\tilde A^{k} X X^{\top} \tilde A^{k},$$

where $\tilde A$ is symmetric and $G_L$ is an $n\times n$ positive semidefinite matrix. Two consequences follow, and they connect the two literatures.

The first is exact. By the eigenvector test for controllability used in network control, any eigenvector $v$ of $\tilde A$ with $v^\top X=0$ is unreachable at every depth. Take any graph symmetry $P$ (a node relabeling with $P\tilde A=\tilde AP$) that also fixes the features ($PX=X$). Every node-space vector that is antisymmetric under $P$ is then dark, so the nodes $P$ swaps receive identical representations. This is the network-learning version of symmetry-induced uncontrollability. It extends to the coarsest equitable partition of the graph refined by the features. Nonlinear message passing also respects that partition, because activations act on each node separately. The binary part of this claim overlaps with folklore about the Weisfeiler–Lehman color-refinement limit of message passing, and we do not claim it as new.

The second consequence is graded, and it is the part we claim is new. Real graphs are rarely exactly symmetric once features are attached, but many are nearly so. Examples are leaves hanging off the same hub, which form the "sibling cells" of Laplacian Dynamics on Cographs: Controllability Analysis through Joins and Unions, and duplicated local motifs of the kind documented in Symmetry in Complex Networks. In these cases the eigenvalue spectrum of $G_L$ has a long tail of tiny values. We hypothesize three things. The effective rank of $G_L^{1/2}$ gives a training-free ceiling that tracks the depth-dependent accuracy of trained deep networks. The per-node error is concentrated on nodes whose distinguishing directions lie in that tail. Finally, the gap between the ceiling and what a trained network achieves isolates the part of the collapse caused by learned transformations and activations rather than by aggregation. That last quantity is exactly what The Oversmoothing Fallacy: A Misguided Narrative in GNN Research argues about but cannot measure.

Research Program

The work has three parts: a measurement instrument, an attribution study, and a targeted intervention.

The instrument comes first. For each benchmark graph we compute two things. One is the feature-aware coarsest equitable partition, which gives the exact dark directions. The other is the Gramian spectrum of $G_L$ for $L$ up to several hundred. To keep this scalable, we use Lanczos or randomized range-finding on the Krylov block $[X,\tilde AX,\dots,\tilde A^LX]$ rather than forming $n\times n$ matrices, so cost grows with edges times $L$ times feature width. From the spectrum we derive a global ceiling, the effective rank in the same scale-invariant sense used by Are we measuring oversmoothing in graph neural networks correctly?. We also derive a per-node "reach score": the Gramian-weighted distance between a node and its most similar differently-labeled node.

That paper supplies our measurement convention. It showed that feature-matrix effective rank, measured after training, correlates with accuracy at Pearson 0.91 across datasets, whereas Dirichlet energy, a sum of squared feature differences across edges, can stay high while accuracy collapses. The same paper also warns that high rank is necessary but not sufficient, which is why we pair the global ceiling with the label-aware per-node score. Our quantity differs from theirs in two ways: it is computed before training, and it is a property of $(\tilde A, X)$ rather than of a trained model.

The attribution study comes second. We train a ladder of models at matched depth: a linear simplified graph convolution, a residual linear model, a ReLU graph convolution, and the bifurcation-based Sine/Tanh networks of Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors. We also train skip-connection-plus-BatchNorm models from the Fallacy paper and the normalization methods PairNorm and ContraNorm. For each model we decompose its effective rank into "ceiling" (the Gramian) and "achieved."

The linear models must stay under the Krylov ceiling by construction, so they serve as a correctness check. Nonlinear models can exceed it, because activations create new directions, but they cannot cross the exact equitable-partition barrier. How far they exceed the graded ceiling is itself a finding. The bifurcation paper's double-well dynamics act on symmetric nodes symmetrically, so we predict they cannot separate an exact orbit. The Fallacy paper's demonstration that graph convolutions "unsmooth" identical inputs relied on asymmetric positions, so on graphs with large orbits we predict that unsmoothing stops at the partition.

The study also covers the backward direction. Gradients flow through the transpose of the same linear map. The dual object, the observability Gramian of the loss, should therefore predict where the gradient plateaus described in Backward Oversmoothing: why is it hard to train deep Graph Neural Networks? appear. We will test this only on the linear and smooth-activation models that paper covers.

The intervention comes third. Control theory says how many inputs a symmetric network needs. On cographs, full controllability requires $n-p$ "leader" nodes, where $p$ is the number of sibling cells: every node in a cell except one must be driven. More generally, an equitable partition with $s$ cells caps the reachable dimension at roughly $s$ times the state width when leaders respect the partition, as shown in On the Controllability of Matrix-weighted Networks. We turn this into a cheap preprocessing step. A greedy procedure picks a small budget of leader nodes whose added one-hot input columns most increase the smallest significant eigenvalues of $G_L$. Each leader receives a learnable embedding. This is a targeted relative of random node features and positional encodings: it spends its extra inputs only on dark or dim directions.

Baselines

The naive reference point is a vanilla deep graph convolution with ReLU and no normalization. The file reports it falling to about 19% on Cora at 32 layers in ContraNorm: A Contrastive Learning Perspective on Oversmoothing and Beyond, and to below 30% beyond 20–50 layers in A Signed Graph Approach to Understanding and Mitigating Oversmoothing. Every other model is measured against this floor.

For the diagnostic question, whether pre-training quantities predict deep-network accuracy, the strongest competitor is post-hoc effective rank of the trained features from Are we measuring oversmoothing in graph neural networks correctly?, with a reported average Pearson correlation of 0.91 with accuracy. It is strong because it is the only measure in the file shown to work across homophilic and heterophilic data. It is also post-hoc, so it uses information about the trained model that our Gramian never sees. We compute both on identical checkpoints, datasets, and depths. Beating it does not require a higher correlation. Our training-free ceiling must come within a few hundredths of 0.91. It must also add explained variance in per-node correctness when both are entered into one logistic model. We also include Dirichlet energy, the spectral gap of $\tilde A$, the effective rank of $X$ alone, and the raw number of equitable-partition cells as weaker training-free predictors.

For the intervention question, the strongest existing methods are three. The first is Structural Balanced Propagation, which reaches about 80% on Cora at 300 layers (paper above). The second is skip connections plus BatchNorm, trained to 1,024 layers in the Fallacy paper. The third is PairNorm, which reports 74.5% versus 42.3% for vanilla SGC on Cora when unlabeled features are entirely missing, in PairNorm: Tackling Oversmoothing in GNNs. Structural Balanced Propagation deserves care because its label-wired variant adds label-dependent edges. That changes $\tilde A$, so it can legitimately escape a ceiling computed on the original graph. We will compute its ceiling on the rewired graph, and we predict its feature-wired variant stays under the original one.

All methods get the same splits, the same depth grid, and the same hyperparameter search budget in trials per method. Leader embeddings are added on top of the strongest backbone. Two ablations isolate the key ingredient. One uses an equal number of leaders chosen at random. The other uses random node features of matching width. If Gramian-chosen leaders do not beat both at equal budget, the control-theoretic selection adds nothing.

Why not just…?

Why not just run color refinement and count partition cells? It gives the exact symmetry barrier for free, and on graphs where exact symmetry dominates it may be all that matters. Real featured graphs, however, have few exact feature-preserving symmetries. The question is whether near-symmetry, which cell counting cannot see, explains residual errors. The decisive comparison is per-node: among nodes in singleton cells, does a low reach score predict misclassification? If not, the graded half of the proposal fails and we report the binary result alone.

Why not just measure effective rank of the trained network? It works, with a reported 0.91 correlation, but it requires training each architecture at each depth. It also cannot say whether low rank is forced by the data or caused by optimization. The ceiling-minus-achieved gap is the quantity that settles the aggregation-versus-transformation dispute. That dispute is between the Fallacy paper and the classical narrative, and post-hoc rank alone cannot resolve it.

Why not just add random node features or positional encodings to break all symmetry? This is a real threat to the intervention. Random features break exact symmetry trivially and may perform comparably on large graphs. We will run them at matched width as an ablation. Our prediction is that they help only on nodes in large cells and degrade generalization elsewhere, while targeted leaders help the same nodes at a fraction of the added dimensions. If random features match leaders at equal budget, we will drop the intervention claim and keep the diagnostic.

Proposed Experiments

The first check uses exact controls. On synthetic cographs, where the $n-p$ leader rule is exact, we verify that linear networks with fewer leaders leave exactly the predicted number of indistinguishable node pairs. We repeat this on contextual stochastic block models with planted sibling cells and tunable feature noise, where the reach score should track the error as noise breaks symmetry. We also place synthetic labels on the highly symmetric real topologies described in Symmetry in Complex Networks, such as the mouse regulatory network, where symmetry alone accounts for 142 of 191 zero eigenvalues. There, every architecture, including Sine/Tanh bifurcation networks and SBP without labels, should fail on the same orbit-mixed nodes.

The second check is a sharp, falsifiable prediction on public data. The Fallacy paper reports that graph convolutions with uniform input features reach over 91% of full-feature accuracy on Chameleon. With uniform features, the dark directions are exactly those of the graph's coarsest equitable partition. Our predicted ceiling is the accuracy of majority-label-per-cell, and trained models should match it from below and never exceed it.

The third check is the main study. It runs on Cora, Citeseer, Pubmed, Texas, Wisconsin, Cornell, Chameleon, Squirrel, Amazon-ratings, and ogbn-arxiv, at depths from 2 to 256. We report correlation of the training-free ceiling with accuracy against the baselines above, per-node prediction of errors, and the ceiling-minus-achieved gap per architecture. The proposal is confirmed if three things hold: the ceiling is never exceeded by linear models, it predicts accuracy close to post-hoc effective rank, and the per-node reach score explains errors beyond cell counts. It is refuted if the trained nonlinear models routinely and substantially exceed the graded ceiling on real data. That outcome would itself show that activations, not aggregation, are the main source of distinguishability, which is a useful answer to the open debate.