Graph neural networks (GNNs) are widely believed to perform best at shallow depths, a failure historically attributed to oversmoothing. The position paper 'The Oversmoothing Fallacy' (Park et al., 2025) argues this attribution is largely mistaken: with skip connections and batch normalization, deep GNNs can be trained without performance collapse, and the observed depth-related failures stem mainly from vanishing gradients rather than aggregation-induced oversmoothing. The paper explicitly leaves open the complementary question: given workable deep training, which datasets and tasks actually benefit from depth? It reports that optimal depth is strongly dataset-dependent and hypothesizes that measurable dataset characteristics — heterophily, required receptive field, scale, and required expressivity — govern it, without proposing or validating any predictor. This problem asks for a principled, dataset-level characterization: measurable statistics of a graph dataset and task that predict the optimal GNN depth and whether a deep GNN (with skip connections and normalization) will substantially outperform a shallow one, validated across GNN architectures, aggregation schemes, and scales.

Background

A graph neural network (GNN) learns representations of nodes in a graph by stacking layers, each of which combines three operations: aggregation (each node summarizes the features of its graph neighbors, e.g. averaging), linear transformation (a learned matrix multiplication of the aggregated features), and non-linear activation (a fixed function such as ReLU introducing non-linearity). The number of stacked layers is the network's depth; depth controls how many hops of the graph a node's representation can draw on, i.e. its receptive field.

When deep GNNs were observed to underperform shallow ones, the standard explanation was oversmoothing: the observation, formalized by Li et al. (2018) and proved asymptotically by Oono and Suzuki (2020), that repeated aggregation drives all node representations toward indistinguishable limits as depth grows, destroying class information. Wu et al. (2023) sharpened this to a non-asymptotic statement, showing that node-similarity measures decay at an exponential rate even at moderate depth, under fixed (non-learned) weights. In parallel, several works showed that deep GNNs are trainable when classical deep-learning remedies are applied — DeepGCNs (Li et al., 2019) trained 56-layer GCNs with residual connections (skip connections that add a layer's input to its output, easing gradient flow), Li et al. (2021) trained GNNs with hundreds of layers by managing memory, and GCNII (Chen et al., 2020) reached 64 layers with initial residuals and identity mappings.

The source paper, 'The Oversmoothing Fallacy: A Misguided Narrative in GNN Research' (Park et al., 2025), argues the community conflated oversmoothing with the vanishing gradient problem (the classical phenomenon, common to all deep neural networks, in which gradients shrink toward zero across layers and block learning): the paper contends that the exponential decay of similarity measures in practical GNNs is caused by the transformation and activation steps, not aggregation, and that with skip connections and batch normalization (a normalization of layer activations across a batch, stabilizing training) GCNs up to 1024 layers can be trained without degradation on standard benchmarks.

Yet the paper's own experiments show the optimum is dataset-dependent: many datasets peak at shallow depths even with these remedies, while heterophilic datasets — graphs where connected nodes tend to have different labels, so that useful information lies in distinguishable rather than similar neighborhoods (Platonov et al., 2023, showed such graphs are systematically hard) — and large datasets such as ogbn-arxiv peak at deeper depths, and replacing input features with uninformative ones pushes the optimum deeper. The paper concludes (Section 4.2) that the question 'whether GNNs inherently achieve optimal performance at limited depth remains open' and hypothesizes that optimal depth varies with measurable dataset characteristics such as homophily level, required receptive field, scale, and required expressivity (the discriminative capacity a model must recover from the data).

Problem Statement

Establish a principled, dataset-level characterization of whether and when depth helps graph neural networks. Specifically: identify measurable statistics of a graph dataset and its learning task — such as homophily/heterophily level, required receptive field, graph size, and the expressivity the task demands of the model — and characterize (theoretically and/or empirically) how these statistics are associated with the depth at which a GNN trained with standard depth-enabling remedies (skip connections and normalization) achieves its best performance, and with whether a deep GNN will substantially outperform a shallow one on that dataset. It is carried by statistics that are computable from the dataset and task alone, before training any deep model, and is tested on standard benchmarks spanning homophilic and heterophilic graphs, varying scales, and feature-informativeness regimes, reporting how well those statistics forecast both the measured optimal depth and the deep-over-shallow advantage relative to reasonable baselines (e.g. default shallow search or uninformed search), together with the strength and the limits of the association; a weak association, or one that holds only within a delimited scope, is a legitimate outcome of the characterization. The characterization is established across more than one GNN architecture or aggregation scheme, or else stated for the specific architectures, aggregation schemes, and scales for which it is established, with its scope delimited to those.

References

  1. MoonJeong Park, Sunghyun Choi, Jaeseung Heo, Eunhyeok Park, Dongwoo Kim. The Oversmoothing Fallacy: A Misguided Narrative in GNN Research. arXiv:2506.04653 (2025). DOI: 10.48550/arxiv.2506.04653. https://arxiv.org/abs/2506.04653
  2. Niklas Kormann, Benjamin Doerr, Johannes F. Lutzeyer. Position: Don't be Afraid of Over-Smoothing and Over-Squashing. arXiv:2601.07419 (2026). DOI: 10.48550/arxiv.2601.07419. https://arxiv.org/abs/2601.07419
  3. Asela Hevapathige, Asiri Wijesinghe, Ahad N. Zehmakan. Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily. arXiv:2511.06608 (2025). DOI: 10.48550/arxiv.2511.06608. https://arxiv.org/abs/2511.06608
  4. Adrian Arnaiz-Rodriguez, Federico Errica. Oversmoothing, "Oversquashing", Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning. arXiv:2505.15547 (2025). DOI: 10.48550/arxiv.2505.15547. https://arxiv.org/abs/2505.15547
  5. Kenta Oono, Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. arXiv:1905.10947 (ICLR 2020). DOI: 10.48550/arxiv.1905.10947. https://arxiv.org/abs/1905.10947
  6. Xinyi Wu, Zhengdao Chen, William Wang, Ali Jadbabaie. A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks. arXiv:2212.10701 (ICLR 2023). DOI: 10.48550/arxiv.2212.10701. https://arxiv.org/abs/2212.10701
  7. Guohao Li, Matthias Müller, Ali Thabet, Bernard Ghanem. DeepGCNs: Can GCNs Go as Deep as CNNs? arXiv:1904.03751 (2019). DOI: 10.48550/arxiv.1904.03751. https://arxiv.org/abs/1904.03751
  8. Guohao Li, Matthias Müller, Bernard Ghanem, Vladlen Koltun. Training Graph Neural Networks with 1000 Layers. arXiv:2106.07476 (2021). DOI: 10.48550/arxiv.2106.07476. https://arxiv.org/abs/2106.07476
  9. Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, Yaliang Li. Simple and Deep Graph Convolutional Networks. arXiv:2007.02133 (ICML 2020). DOI: 10.48550/arxiv.2007.02133. https://arxiv.org/abs/2007.02133
  10. Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? arXiv:2302.11640 (ICLR 2023). DOI: 10.48550/arxiv.2302.11640. https://arxiv.org/abs/2302.11640
  11. Qimai Li, Zhichao Han, Xiao-Ming Wu. Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning. arXiv:1801.07606 (AAAI 2018). DOI: 10.48550/arxiv.1801.07606. https://arxiv.org/abs/1801.07606