Admitting Graph Layers to the Vote Only Before They Collapse

A graph neural network classifies each node by repeatedly averaging information from its neighbors. Every averaging step widens what the node can see, but it also blurs nodes together. After enough steps, nodes in different classes end up with nearly identical representations, a failure called over-smoothing. A common remedy is to attach a small classifier to every layer and combine their outputs. Each layer's classifier then acts as a voter in an ensemble, and shallow and deep views of the graph get to disagree. The weak point is how the votes are combined. Existing methods average them uniformly, pick one layer per node using degree-like heuristics, or weight them by each classifier's own confidence. An over-smoothed deep layer, however, tends to be confidently wrong. It has pulled the node toward the majority label of its neighborhood. It is also a near-copy of the other deep layers, so a plain vote counts the same mistake several times.

We propose a decision-level fix that needs no labels at test time. For each node and each layer, we measure how similar the node's representation has become to the representations of its neighbors. We then learn, from labeled validation nodes, a per-layer similarity threshold above which that layer's vote is dropped, along with a calibrated weight for the votes that remain. The threshold works like the similarity cutoffs used in retrieval and matching, except that here it decides which layers may vote. The surviving votes are weighted by measured error rate, as in minimum-error ensemble weighting. The central bet is falsifiable: this collapse score predicts when a layer's answer for a particular node is wrong, and it carries information that the layer's softmax confidence does not.

Core Claim

Over-smoothing damages individual nodes at individual depths, not whole graphs at a fixed depth. A per-node, per-layer similarity signal, once calibrated against held-out errors, can therefore choose which layers to trust for each node better than confidence weighting, uniform voting, centrality-based routing, or learned attention over layers. The threshold has a specific job beyond down-weighting. Collapsed deep layers make strongly correlated errors, so even moderately accurate collapsed layers, added up, outvote a correct shallow layer. This is the "clone" problem that Hidden Clones: Exposing and Fixing Family Bias in Vision-Language Model Ensembles documents for vision-language model ensembles, where models from the same family share errors and overwhelm a correct minority. Excluding votes past a calibrated cutoff is our structural answer to that over-counting.

Concretely, let $h_i^{(l)}$ be node $i$'s representation at layer $l$, let $\bar h_{\mathcal N(i)}^{(l)}$ be the mean representation of its neighbors at that layer, and let $p_i^{(l)}$ be the class probabilities from layer $l$'s classifier. The collapse score is $s_i^{(l)} = \cos(h_i^{(l)}, \bar h_{\mathcal N(i)}^{(l)})$. The ensemble prediction is

$$\hat y_i = \arg\max_c \sum_{l=1}^{K} \mathbb 1\left[s_i^{(l)} \le \tau_l\right]\, \hat a_l\!\left(s_i^{(l)}\right)\, p_{i,c}^{(l)},$$

where $K$ is the number of layers and $\tau_l$ is the per-layer admission threshold. The function $\hat a_l(\cdot)$ is a monotone (isotonic) fit of layer $l$'s validation accuracy as a function of its collapse score. Both $\tau_l$ and $\hat a_l$ are fit on validation nodes by cross-fitting, which totals roughly $K$ thresholds plus a few bins per layer. If every threshold excludes a node's votes, we fall back to the shallowest layer.

We will also test a global variant of the score, the similarity to the graph-wide mean, which is closer to the "distance to the stationary state" used by NAFS and NDLS. Which variant predicts errors better is an empirical question we settle first.

Relation to Prior Work

Four lines of work combine information across depth, and each leaves a specific opening.

Two of them combine layers without asking how reliable each one is. Representation Learning on Graphs with Jumping Knowledge Networks pools intermediate representations by concatenation, max, or LSTM-attention inside the network. Addressing Over-Smoothing in Graph Neural Networks via Deep Supervision trains a classifier at every layer under a uniform average of the per-layer losses. Neither calibrates per-layer trust against errors.

ADMP-GNN: Adaptive Depth Message Passing GNN is the closest multi-exit method. It routes each node to one exit layer using k-core and walk-count statistics. We differ in two ways: our signal comes from the learned representations rather than from graph structure, and we keep a weighted vote over all admitted layers instead of making one hard choice.

NAFS: A Simple yet Tough-to-Beat Baseline for Graph Representation Learning is the closest idea overall. It weights propagation hops per node with a softmax over an over-smoothing distance, but it works on untrained propagated features, it never checks the weights against errors, and it has no cutoff. Node Dependent Local Smoothing for Scalable Graph Learning does use a threshold, a graph-wide $\epsilon$ on structural influence convergence. It motivates our design by showing that smoothing speed differs strongly across nodes. Its threshold, though, ignores features and is never tuned against task error. We take its threshold-per-node intuition and calibrate the threshold on errors instead.

From the ensemble literature we reuse methods directly. A Minimum Error Weighting Combination Strategy for Chinese Semantic Role Labeling supplies the principle of fitting combination weights to minimize validation error; there it beat equal-weight voting, 80.45% vs 79.33% F1. APatt at SemEval-2023 Task 3 supplies the pairing of performance weights with a tuned cutoff. Both worked on independent text models, where the clone problem is mild.

The threshold-optimization literature constrains our design. It reports narrow sweet spots, as in An Ontology-Based Webpage Classification Approach for the Knowledge Grid Environment. It also reports cliffs and paradoxes, such as precision falling when the threshold is set too high, in Jiangjuan Wang et al.. These results are why we cross-fit the thresholds and report how sensitive accuracy is to them.

Two papers bear on the over-smoothing debate itself. The Oversmoothing Fallacy argues that degradation comes from the transformations and activations, not from neighbor averaging, and that residual connections plus batch normalization reach 1,024 layers. If that is right, our collapse score should carry little signal on such backbones. We treat this as a prediction to test, not a threat to explain away. Are we measuring oversmoothing in graph neural networks correctly? shows that graph-level similarity metrics can come apart from task performance. That is why our score is per node, and why we validate it against per-node errors before building anything on it.

Research Program

The work proceeds in three steps. First, we train multi-exit backbones: GCN and GAT with per-layer linear classifiers, at depths 2, 4, 8, 16, and 32. Each is trained once with deep supervision and once with ADMP-style sequential freezing, and each comes in plain and residual-plus-batch-norm variants. All later methods reuse these exact checkpoints, so every difference comes from the combination rule.

Second, we run a diagnostic study, before proposing anything. For every validation node and layer we record the collapse score, the classifier's confidence, node degree, and whether that classifier was correct. The key quantity is how well the collapse score predicts errors after controlling for confidence. We measure it as the error-prediction AUROC of the score within confidence bins, and as the gain in log-likelihood when the score is added to a logistic error model that already uses confidence and degree. We also measure agreement between deep layers to quantify the clone effect.

Third, we fit the admission thresholds and calibrated weights by cross-fitting on validation nodes, apply them to test nodes, and run the ablations below.

Baselines

The naive reference points are the final-layer classifier at each depth, and the best single depth chosen on validation. The latter is what most practitioners actually do, and our gain must be measured against it.

The uniform-vote baseline averages every layer's probabilities with equal weight. It isolates whether weighting matters at all; MEW's 1.12-point gain over equal weights in text suggests it should, but graphs are untested.

Confidence-weighted voting weights each layer by its max-softmax probability. This is the most dangerous simple competitor because it is also per node and needs no labels.

Learned stacking trains a small logistic model on the concatenated layer logits, fit on the same validation nodes. JK-Net with LSTM-attention is run as the end-to-end equivalent. The file reports 89.6% Cora accuracy for a 6-layer JK-Net with max-pooling and 88.2% for a 2-layer GCN JK-Net.

ADMP-GNN is the strongest published method on the multi-exit question. It reports 69.29% on ogbn-arxiv against 64.37% for standard GCN ADMP-GNN. We rerun it on our checkpoints and splits.

NAFS is run on the same propagation depths. No reported node-classification accuracy for NAFS was found on Lacuna; the file gives only clustering NMI and speed figures for it.

For heterophilic graphs we include SMEGCN, which reports 80.39% on Wisconsin SMEGCN. We also include PROXYDELETE, which reports raising GCN on Roman-Empire from about 70% to about 78% Spectral Graph Pruning.

The Cora figures across papers disagree: about 81% for GCN in ADMP-GNN versus 88.2% in JK-Net, presumably because of different splits. We therefore compare only against our own reruns on fixed public splits, with 10 seeds and the same hyperparameter-search budget per method (an equal number of trials). Every method that uses validation labels gets the same validation nodes.

Three ablations isolate the key ingredient. The first keeps the calibrated weights but removes the threshold, which tests the anti-clone role. The second keeps the threshold but replaces the calibrated weights with NAFS-style softmax weights on the same score, which tests whether calibration against errors matters. The third swaps the collapse score for confidence or degree inside the identical calibration pipeline, which tests whether the signal itself matters.

Beating the field means two things. On deep networks (eight or more layers), we need a statistically significant gain over best-single-depth, stacking, and ADMP-GNN on our reruns. On shallow networks, where there is little to fix, we must not underperform.

Why not just…?

Why not just weight layers by their own confidence? It is cheap and works per node. Our hypothesis is that over-smoothed layers become confident in the neighborhood's majority label, so confidence rises exactly when reliability falls. The diagnostic study tests this directly. If the collapse score adds nothing once confidence is controlled for, confidence weighting wins and we stop.

Why not just learn a stacking model or attention over layers? This is a real threat on large graphs like ogbn-arxiv, which have enough validation labels to fit a flexible combiner. On Cora-sized splits and on the small heterophilic graphs (Wisconsin, Cornell, Texas), a combiner with many parameters can overfit. The file notes this risk for JK-Net's LSTM-attention on small graphs. Our rule has about $K$ thresholds plus a few bins per layer. We compare both at matched validation budgets and also vary the number of validation labels, so we can report where each approach is preferable.

Why not just use residual connections and batch normalization, which reportedly train 1,024-layer GCNs? If The Oversmoothing Fallacy is right, deep residual backbones simply will not collapse, and our method should show no gain on them. We test this rather than argue it. Our method can still add value if residual backbones remain worse than shallow ones on heterophilic graphs, as the 70% to 78% Roman-Empire gain from edge pruning suggests. That gain shows plain averaging over cross-class edges still hurts.

Why not just estimate layer accuracies without labels, using spectral meta-learning? Estimating the accuracies of multiple classifiers without labeled data needs classifiers whose errors are conditionally independent. Layers of one network share every earlier computation, and collapsed layers are near-duplicates, so that assumption fails by construction. We include it as a baseline mainly to document the failure, and we expect it to rank deep clones highly.

Proposed Experiments and Decisive Checks

We evaluate on homophilic graphs (Cora, Citeseer, PubMed, ogbn-arxiv) and heterophilic graphs (Wisconsin, Cornell, Texas, Squirrel, Chameleon, Roman-Empire, Amazon-Ratings). We report accuracy, expected calibration error, and the gain over best-single-depth as a function of depth and of the edge-homophily ratio.

Three checks decide whether the idea holds. First, the collapse score must predict per-layer errors beyond confidence and degree on the plain backbones; if it does not, the proposal fails at the diagnostic stage. Second, the threshold-removal ablation must hurt most where deep layers agree most with each other; this confirms the anti-clone mechanism rather than merely re-weighting. Third, the gain should grow with depth and as homophily falls, and should shrink on residual-plus-batch-norm backbones. That last pattern turns the method into per-node evidence for or against the claim that neighbor averaging itself, rather than optimization, is what corrupts deep predictions.

Finally, we report how sensitive accuracy is to each $\tau_l$, because the threshold literature warns of sharp cliffs. A result that holds only at one finely tuned cutoff would not count as success.