Effective Diameter: Over-Smoothing in the Context of Limited Problem Radii

Over-smoothing is widely considered to be one of the main reasons why Graph Neural Networks (GNNs) achieve their best performance with only a few message passing layers. In this paper, we critically examine this assumption on real-world literature benchmarks. Over-smoothing is theoretically well understood and effectively mitigated by established techniques. In experiments on common node classification benchmarks, we show that these mitigation techniques largely stabilise GNN performance for depths of up to 64 layers, but deep models still fail to significantly outperform shallow ones. As an alternative explanation for shallow optimal GNN models, we propose the *effective diameter*, a data-based statistic free of any model assumptions that estimates the size of the task-relevant receptive field. It builds on the shell *separability gap*, which aims to measure the feature-based class discriminative power of a $k$-shell. On all investigated datasets, the separability gap decays within a few hops, and the best-performing models rarely lie beyond the estimated effective diameter. This suggests that the small optimal depth of GNNs is caused by the lack of task-relevant information in large receptive fields rather than by over-smoothing.