Graph neural networks (GNNs) are models that update each node's features by averaging in its neighbors' features, layer after layer. When too many such layers are stacked, the representations of different nodes become indistinguishable, a failure called over-smoothing. The field usually treats over-smoothing as a property of the graph and the depth. Recent work has argued for a different measurement: whether the matrix of node features has lost rank, meaning it has collapsed onto a few directions. Rank, however, ignores the labels entirely. This proposal starts from the opposite premise. Averaging is harmful only when it mixes nodes the task needs kept apart, and helpful when it mixes nodes that share a label. The same graph and the same depth can therefore over-smooth for one prediction task and be fine for another.
We propose to make this concrete and test it. The first piece is a label-relative collapse measure: the separation between class means compared with the spread within classes, tracked layer by layer. The second is a cheap pre-training predictor of the depth at which a given propagation rule will fail for a given task. The test uses identical graphs carrying different label sets. If over-smoothing is task-relative, the collapse depth should shift across label sets while label-blind measures such as effective rank fail to explain the shift. If this holds, it yields a practical, low-compute rule for choosing the propagation operator per task, and it clarifies when the large family of heterophily and anti-smoothing architectures is needed at all.
Core Claim
Two Sides of the Same Coin showed in a linear model that over-smoothing behaves like "pseudo-heterophily". Deep layers push nodes across a class boundary, and once misclassified those nodes act as wrong-class neighbors for the nodes around them. This framing is inherently label-relative. The dominant diagnostic, by contrast, is label-blind. Rethinking Oversmoothing: A Rank-Based Perspective and Are we measuring oversmoothing correctly? replace Dirichlet energy, the summed squared difference between connected nodes, with effective rank, which correlates with accuracy at Pearson 0.9103. Those authors and the research file both note that high rank does not imply usefulness, since random noise has maximal rank.
Our claim is that the right quantity is how much of the class-separating signal survives each layer. Let $H^{(l)}$ be the node features at layer $l$ and let $S_B^{(l)}$ and $S_W^{(l)}$ be the between-class and within-class scatter matrices of those features, computed on training nodes only. We track
$$\rho^{(l)} = \frac{\mathrm{tr}\, S_B^{(l)}}{\mathrm{tr}\, S_W^{(l)} + \mathrm{tr}\, S_B^{(l)}},$$
the fraction of feature variance that lies between class means. We predict three things. First, $\rho^{(l)}$ tracks depth-wise accuracy better than effective rank in trained networks. Second, on a fixed graph, the depth at which $\rho$ falls depends on the label set. Third, this depth can be forecast before training any deep model.
The forecast comes from the propagation operator alone. For an operator $P$ (for example the normalized adjacency, or one of the parameterized operators below) and input features $X$, we define $\hat\rho(L)$ as the same ratio computed on $P^L X$ over training nodes. The intuition is that repeated multiplication by $P$ preserves only the label signal carried by its large-magnitude eigen-directions. Labels aligned with those directions survive deep propagation, and labels concentrated elsewhere are erased within a few steps. Computing $\hat\rho(L)$ costs one sparse matrix multiply per depth.
Research Program
The program has three parts. The first is measurement. We train standard GCN, GCNII-style residual networks, and representative anti-smoothing and heterophily models at depths 2 to 64. At every layer we record $\rho^{(l)}$, effective rank, numerical rank, and Dirichlet energy. We then ask which quantity best predicts test accuracy across layers and models. This extends the correlation analysis of the rank papers with a label-aware competitor.
The second part is the same-graph, different-task test, which is the heart of the proposal. ogbn-arxiv supports both subject-area labels, which are homophilous, and the arxiv-year labels, which are heterophilous, on the same citation graph. Centrality Graph Shift Operators reports arxiv-year accuracy of 47.27% for its centrality GCN against 38.55% for GCN, which confirms that the task changes which operator is right. We supplement this with contextual stochastic block graphs, where we hold the edges and features fixed and reassign labels to sweep homophily from 0.1 to 0.9. Here the "task-dependent topology" direction enters as a question rather than a method: how far does the optimal propagation depend on the task when the graph is literally the same?
The third part is operator selection. We define a small candidate family of operators: the symmetric normalized adjacency, the PGSO family from Learning Parametrised Graph Shift Operators, centrality operators from CGSO, a two-channel low/high-pass filterbank from Complete the Missing Half, and GGCN-style signed weights. For each task we pick the operator and depth that maximize $\hat\rho(L)$, and compare that choice with full validation search at matched compute. We also test $\rho$ as a training regularizer on intermediate layers, though we expect a strong ablation to threaten that variant (see below).
Prior work plays three roles here. Pseudo-heterophily motivates the label-relative view. The rank papers constrain it, because any new measure must beat their 0.91 correlation. PGSO, CGSO, and the filterbank models supply the operator family. Neural Sheaf Diffusion and HMH (Hierarchical Multi Scale GNNs) already learn signed or sheaf-valued, task-dependent propagation end to end. We therefore do not propose another such architecture, and the research file's "Gap 2" is largely closed by them. Instead we ask when their machinery is needed, and whether a cheap label-aware forecast can tell in advance.
Baselines
The naive reference points are a feature-only multilayer perceptron, which ignores edges, and a 2-layer GCN. The research file reports that vanilla GCN reaches only 52.16% on Texas (Geom-GCN) and that MLPs often beat it under heterophily (Beyond Homophily). Any operator-selection rule must beat both.
For the diagnostic, the main competitor is effective rank. It is the strongest label-blind measure, at Pearson 0.9103 with accuracy (Rethinking Oversmoothing). Dirichlet energy, at −0.7179 in the same work, is a secondary baseline. We will compute all measures on the same checkpoints. $\rho$ wins if its correlation with accuracy is higher on held-out models and datasets. On the same-graph tests, it wins if it explains the change in collapse depth across label sets where rank does not.
For accuracy, the strongest reported methods are the following. MTGCN (Multi-Track Message Passing) reports 92.10% on Texas and 90.20% on Wisconsin. CGATv2 reports 80.78% on Wisconsin, and the centrality GCN reports 47.27% on arxiv-year. GGCN reports the best average rank, 1.78, across nine datasets. We found no reported result on Lacuna for any of these methods on ogbn-arxiv subject labels, so we will run them ourselves.
Fairness rules apply throughout. All methods use the same splits and the same hyperparameter budget, measured in GPU-hours. MTGCN, NSD, and GGCN are run from their published configurations and then retuned within that budget. Our selection rule does not need to beat MTGCN outright. It succeeds if the operator it picks, trained once, comes within the seed variance of the best validation-searched operator from the same family. The ablation that isolates the key ingredient replaces $\hat\rho$ with a label-blind score, the effective rank of $P^L X$, inside the identical selection procedure. If label-blind selection does as well, the task-relative claim fails.
Why not just…?
Why not just tune depth and operator on the validation set? This is the real threat to the selection part of the proposal. Validation search is the gold standard, and $\hat\rho$ can only win on cost, by training one model instead of many. We will plot accuracy against total compute for both. If validation search with the same compute matches us, the practical claim collapses. The diagnostic and same-graph findings would still stand.
Why not just use a shallow network? On many benchmarks this is the right answer, and our forecast should say so: $\hat\rho$ should peak at small $L$ on WebKB graphs. The Tree-NeighborsMatch failure of GCN and GAT beyond depth 5, reported by MTGCN, shows that some tasks need depth. The same-graph experiments test whether the right depth is task-specific rather than graph-specific.
Why not just add a supervised class-center or contrastive loss on hidden layers? The $\rho$ regularizer is close to this kind of intermediate-layer supervision, and we expect them to perform similarly. We will run both under the same tuning budget. If they match, we will report the regularizer as subsumed and keep $\rho$ only as a diagnostic.
Why not just use effective rank, which already correlates at 0.91? Rank cannot, by construction, distinguish two label sets on the same features and graph. The arxiv and arxiv-year comparison and the synthetic label sweep test exactly the case where it must fail if our claim is right.
Proposed Experiments
The decisive check uses synthetic stochastic block graphs with fixed edges and features and labels swept across homophily levels, plus ogbn-arxiv with subject versus year labels. With the operator and depth held fixed, we measure the layer at which test accuracy drops by half its peak gain over the MLP. Pre-registered success means two things. First, this layer varies with the label set by at least a factor of two. Second, $\hat\rho(L)$ computed before training predicts it with rank correlation above 0.8 across settings, while effective rank of the same features does not.
The secondary checks are threefold. The first is the measure comparison on Cora, CiteSeer, PubMed, Texas, Wisconsin, Cornell, Squirrel, Chameleon, and Actor, at depths up to 64. The second is operator selection accuracy against validation search at matched compute. The third tests whether $\hat\rho$ correctly predicts when a plain two-channel filter suffices and when sheaf or multi-track models are worth their cost. A negative result on the decisive check would also be informative: it would mean trained over-smoothing is dominated by label-independent rank collapse, contrary to the pseudo-heterophily view.
References
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
- Rethinking Oversmoothing in Graph Neural Networks: A Rank-Based Perspective
- Are we measuring oversmoothing in graph neural networks correctly?
- Centrality Graph Shift Operators for Graph Neural Networks
- Learning Parametrised Graph Shift Operators
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs
- Hierarchical Multi Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
- Geom-GCN: Geometric Graph Convolutional Networks
- Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
- Multi-Track Message Passing: Tackling Oversmoothing and Oversquashing in Graph Learning via Preventing Heterophily Mixing