- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper questions the common belief that over-smoothing is why deep GNNs do not beat shallow ones. The authors show that standard mitigation techniques do prevent over-smoothing up to 64 layers, yet deep models still do not significantly outperform shallow ones on 6 node-classification benchmarks. Alternatively, they propose the "effective diameter": a model-free statistic built on the shell separability gap , which measures whether the k-th shell of a node still carries feature information about the node's class. They find that decays within a few hops, and that the best-performing model depth rarely exceeds the estimated effective diameter. The conclusion is that the small optimal depth comes from the lack of task-relevant information in large receptive fields, not from over-smoothing.
Critical strengths
- Well-motivated question with clean logic. The counterfactual argument is convincing: if over-smoothing were the main bottleneck, fixing it should let deep GNNs win — they still don't, so the bottleneck likely lies elsewhere.
- Simple and cheap estimator. and the effective diameter are model-free, easy to compute ( via class-mean decompositions).
Critical weaknesses
W1 — The core statistics are heuristic and the threshold .
- is essentially a Fisher-style between/within second-moment ratio; the O(N²d) → O(Nd) simplification is not novel. The only justification given is a null-baseline argument (random relabeling drives the gap to zero), which is a necessary condition, not evidence that a large gap implies downstream-useful information. No quantitative link between and classification error is provided.
- The effective diameter depends on a hand-picked (0.005, 0.01 for Photo) with no selection rule and no sensitivity analysis: smaller τ gives a larger diameter, and the paper's only validation: "best depth ≤ effective diameter", a one-sided inequality that becomes trivially true as shrinks. Also, on Cora itself rises again after , which sits oddly with the "stagnation" story.
- "Deep models don't win" could also reflect an optimization bias toward shallow models rather than missing information (deep models are harder to train than shallow ones); no ablation separates the two.
W2 — The empirical study does not look reliable. Baseline numbers are inconsistently off from the literature in both directions: GCN on Cora gets 74.1% where the standard planetoid result is >80%. This inconsistency suggests implementation or protocol problems. The hyperparameter searching space is small, no weight decay and learning rate tuning. GCN on Cora at 4 layers collapses to 36.1 ± 13.4, which looks like a training failure rather than over-smoothing. On Roman-Empire, standard deviations of 10–15pp on the best models (GCNII, G2) are far larger than the depth effects being discussed (e.g., 55.1 vs 57.7). Appendix B claims OGBN-arXiv is included, but no arXiv results appear anywhere in the paper.
W3 — The statistic only covers the raw-feature, but the claim is stated generally. is computed on input features only. GNNs also do feature learning, and label/structure propagation alone can carry task-relevant signal even when features are uninformative (e.g., label propagation on feature-weak graphs). None of the 6 benchmarks can disentangle the feature channel from the label/structure channel, so "large receptive fields lack task-relevant information" is only shown for one channel, while the claim and conclusion state it without this qualifier.
W4 — The estimator cannot handle non-monotone informativeness across hops. The effective diameter is defined as the first k where , so it has no mechanism for information that reappears at larger hops, e.g., even-hop-dominant structure on heterophilic graphs (as in EvenNet-style arguments). The late spike of on Amazon-Computers (Figure 6) is acknowledged in one sentence but not incorporated into the estimator. Heterophilic datasets of this type (e.g., Pokec) are neither tested nor discussed.
Questions for authors
Q1 (for W1). How exactly is chosen, and how do the estimated effective diameters and the "best depth ≤ effective diameter" result change if varies over, say, [1e-3, 1e-2]? Can you rule out that shallow optima come from optimization preferences rather than missing information?
Q2 (for W2). Why do the GCN baselines deviate from the literature? Can you reveal more implementation details? Where are the OGBN-arXiv results announced in Appendix B?
Q3 (for W3). Does your conclusion hold on datasets where raw features are weak but structural/label information is strong?
Q4 (for W4). How would the estimator behave if informativeness is non-monotone in k (uninformative odd hops, informative even hops), like Pokec dataset?
4 comments
Rebuttal 2/2
Weak features (W3 & Q3): We investigated the robustness of our method against weak feature signals with an ablation study on Cora. We perturbed the raw input features with Gaussian noise scaled per feature by its empirical standard deviation : with . The noise level is therefore the ratio of noise to signal standard deviation for every feature. The noise is sampled once before training and stays fixed throughout. We ran the full grid search and evaluation of a GCN and ran the effective diameter estimator. We report the results in Table 3. The effective diameter is not affected by the noise. The optimal GCN depth increases with the level of noise. These results reflect the limitation of our method to graphs with task-relevant features, as we discuss in Section 5.4 of the manuscript. At low signal to noise ratios in the features, the features gradually stop being task-relevant.
Table 3: GCN performance and effective diameter on Cora with different levels of noise applied to the features.
| Noise Level | k=1 | k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 | k=9 | k=10 | Efffective Diameter | Best depth | Diameter | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Rel. gap (%) | 4.89 | 3.10 | 1.13 | 0.50 | 0.27 | 0.17 | 0.15 | 0.19 | 0.29 | 0.39 | 4 | 2 | 19 | |
| Accuracy (%) | 74.78 ± 0.61 | 80.27 ± 0.96 | 79.64 ± 1.00 | 76.84 ± 5.60 | 80.35 ± 0.91 | 78.48 ± 1.53 | 78.29 ± 1.80 | 75.57 ± 2.82 | 75.63 ± 2.48 | 73.58 ± 2.92 | ||||
| Rel. gap (%) | 4.52 | 2.86 | 1.06 | 0.47 | 0.25 | 0.16 | 0.14 | 0.18 | 0.27 | 0.36 | 4 | 2 | 19 | |
| Accuracy (%) | 70.70 ± 0.67 | 79.34 ± 0.59 | 78.44 ± 1.02 | 79.47 ± 0.66 | 76.36 ± 5.55 | 78.40 ± 1.88 | 76.68 ± 3.58 | 76.94 ± 1.39 | 75.40 ± 1.46 | 74.14 ± 2.27 | ||||
| Rel. gap (%) | 3.51 | 2.23 | 0.87 | 0.38 | 0.22 | 0.16 | 0.12 | 0.14 | 0.21 | 0.27 | 3 | 7 | 19 | |
| Accuracy (%) | 49.67 ± 0.68 | 68.52 ± 1.01 | 72.39 ± 0.77 | 73.27 ± 0.88 | 72.52 ± 1.26 | 69.83 ± 7.46 | 74.61 ± 1.12 | 72.64 ± 1.89 | 72.49 ± 2.36 | 67.68 ± 3.49 | ||||
| Rel. gap (%) | 3.21 | 2.06 | 0.81 | 0.35 | 0.21 | 0.16 | 0.12 | 0.12 | 0.18 | 0.24 | 3 | 8 | 19 | |
| Accuracy (%) | 37.61 ± 0.65 | 52.55 ± 1.27 | 60.88 ± 1.48 | 65.57 ± 1.37 | 67.30 ± 1.16 | 66.75 ± 2.61 | 66.71 ± 1.89 | 68.82 ± 1.39 | 68.65 ± 2.07 | 68.27 ± 1.54 |
Non-monotone informativeness (W4 & Q4): Non-monotone informativeness in general can be observed in the new results for the City Network datasets [2], which also include long-range dependencies. In Figure 7 of the revised manuscript, we can observe that the separability gap first grows, then shrinks and finally saturates for all four graphs. The effective diameter is in all cases much closer to the optimal model depth of 16 [2] than the graph diameter. We also applied our estimator to the pokec datasets. From the results in Table 4, we can not observe non-monotone informativeness and therefore chose to focus this discussion on the four city networks.
Table 4: Relative separability gap on the dataset Pokec.
| Dataset | k=1 | k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 | k=9 | k=10 | Horizon | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Pokec | Rel. gap (%) | 0.03 | 0.01 | 0.00 | 0.00 | 0.00 | -0.00 | 0.00 | -- | -- | -- | 1 |
[2] Liang et al. “Towards Quantifying Long-Range Interactions in Graph Machine Learning: A Large Graph Dataset and a Measurement.” International Conference on Learning Representations (ICLR), 2026.
Response to rebuttal
We thank the authors for the detailed rebuttal and the substantial amount of new experiments. My concerns are partially resolved. Please see the issues below.
(W1.3) The optimization-preference concern also stands: a per-depth hyperparameter search does not separate "no task-relevant information at this depth" from "this depth is harder to train", and no ablation distinguishes the two.
(W3) The feature-noise ablation undermines rather than supports the main claim. At sigma = 8, the effective diameter is 3 while the best GCN depth is 8: the paper's central inequality "best depth <= effective diameter" is violated by the authors' own table. In addition, the label/structure channel (Q3) was not tested: adding Gaussian noise to features is not the same as a feature-weak graph in which label propagation carries the signal.
(W4) My question was not directly answered. On Pokec the estimator reports Delta close to 0 with horizon 1, but the actual optimal depth on Pokec is not reported, so whether this constitutes a counterexample remains open.
Given the above, I maintain my rating of 2.
We thank you for your detailed additional comments.
(W1.3) We argue that suitable hyperparameter optimisation and adequate model selection do separate the relevant depth interpretation from optimisation problems: On the datasets PubMed and Roman-empire, the GCNII achieves the overall optimal performance at 64 and 32 layers, respectively. This shows that the model is very unlikely to have training problems. We would be grateful for further details on why this evidence is not sufficient and what ablation study could resolve this issue.
(W3) We included the limitation of our method to graphs with informative features in our manuscript. We are happy to refine this section if it does not cover the case that you are discussing.
(W4) We agree that the Pokec dataset does not help to clarify the behaviour of our estimator if the informativeness is non-monotone, as we cannot observe non-monotone informativeness in Pokec. The datasets of the City Network, however, show a non-monotone separability curve and demonstrate the practical usefulness of our method.
Rebuttal 1/2
We would like to sincerely thank you for your review. Below we respond to your weaknesses and questions jointly.
Quantitative link between Δ(k) and classification error (W1.1): We analysed the correlation between the predictive performance of the models GCN, GATv2 and GraphSAGE and the separability gap. We neglected the models with mitigation techniques here, as these architectures stabilise the performance. The results in Table 1 show a positive correlation.
Table 1: Correlation analysis of separability gap Δ and predictive performance.
Choice of τ (W1.2 & Q1): We chose τ by jointly observing the curves of the separability gap Δ and identifying a value of τ to visually fit the stagnation of Δ. In Table 1, we report the effective diameter for variations of τ, in comparison to the graph diameter and the best model depth. In all cases, the effective diameter remains more informative for the best number of GNN message passing layers than the graph diameter.
Sensitivity of τ (Q1): In Table 2, we report the effective diameter for variations of τ, in comparison to the graph diameter and the best model depth. In cases, where the threshold τ is never reached, we set the effective diameter to the radius with the smallest value of Δ. In all cases, the effective diameter remains more informative for the best number of message passings with a GNN than the graph diameter.
Table 2: Sensitivity analysis for the effective diameter for different values of τ.
Stagnation of Δ on Cora (W1.2): The increase of Δ after stagnation for long paths on Cora and other datasets can be attributed to the small number of paths of that length (as visible in the third row of plots in Figure 2 of our manuscript). The growth is not significant, as the variance is very high for these measurements. The same is true for the small decrease after the plateau at k>10 on Roman-empire.
Optimisation preference (W1.3 & Q1): We try to rule out an optimisation preference by searching for the optimal hyperparameters for each model depth individually. The stable results for the GCNII and G2 indicate that there is no optimisation problem with deep models in our experimental suite.
Statistical reliability (W2 & Q2): We investigated the results for the planetoid datasets and found the cause of the deviation from the literature. Initially, we conducted a cross-validation for the hyperparameter search and early stopping during testing on the combined training and validation set. The implementation of our GCN also deviated from the implementation by Kipf and Welling [1], as we did not apply dropout and row-normalisation to the raw input features before. We reran all hyperparameter optimisations and evaluations for all three citation networks, also including the learning rate as a hyperparameter and updated the tables and figures in our manuscript. The GCNII now has lower accuracy across all depths, possibly due to fixing the validation set instead of using cross-validation. The performance of the GCN has increased due to the exact replication of the implementation based on Kipf and Welling [1]. We also found a mistake in our implementation of the Errica protocol, which potentially caused the high variance on the Roman-empire dataset. We updated these results as well. The accuracy with a GCNII is much higher now, but the best depth remains low with 4 layers of message passing. Thank you for making us aware of the error of mentioning OGBN-arXiv; we removed it in the revised manuscript.
[1] Kipf, Thomas N., and Max Welling. “Semi-Supervised Classification with Graph Convolutional Networks.” International Conference on Learning Representations (ICLR), 2017.