Graph Neural Networks (GNNs) are widely believed to be limited by over-smoothing (node representations becoming indistinguishable with depth) and over-squashing (fixed-dimensional node embeddings failing to compress information from exponentially growing receptive fields), motivating a large literature of mitigation architectures. The position paper by Kormann, Doerr and Lutzeyer (arXiv:2601.07419) argues from extensive benchmark experiments that both phenomena are of little practical relevance, conjecturing that in most real tasks the label-relevant information is localised in a small k-hop neighbourhood and factorises into low-order components. To move this position from conjecture to evidence, the paper poses an unresolved problem: establish formal definitions and validated, model-independent estimators of the problem radius, localisation, and factorisation of label-relevant information that separate data-side task structure from model-side propagation effects, and apply them to determine whether real-world tasks exist in which over-squashing genuinely limits performance (including diagnostics for individual distant outlier nodes whose contributions are uniquely label-relevant). The paper further expects these statistics — the problem radius quantified in combination with an observation of the optimal smoothing depth, and measurements of the localisation of relevant information — to guide efforts in improving model architectures and targeted rewiring techniques. No resolution is known in the literature to date; the problem remains open.

Background

Graph Neural Networks (GNNs) learn on graph-structured data by message passing: at each layer, every node updates its representation by aggregating feature vectors from its direct neighbours. After LL layers, a node's representation depends on its LL-hop neighbourhood, called its receptive field, whose size typically grows exponentially in LL. Two failure modes dominate the literature on deep and wide GNNs. Over-smoothing is the convergence of node representations to (nearly) the same vector as depth grows, destroying task-relevant distinctions. Over-squashing, identified by Alon and Yahav (2020), is the inability of a fixed-dimensional node embedding to faithfully summarise information arriving from an exponentially growing receptive field, in particular when information must traverse bottleneck edges that connect sparsely interacting communities of the graph. Topping et al. (2021) linked over-squashing to discrete notions of Ricci-type graph curvature (negative curvature around an edge indicating a local connectivity deficit) and proposed curvature-based rewiring: methods such as SDRF (Stochastic Discrete Ricci Flow) and BORF (Batch Ollivier-Ricci Flow) iteratively add and remove edges to improve curvature; expander graph propagation (EGP) instead periodically replaces the edge set by a sparse expander graph (a sparse graph of low diameter, so that any two nodes remain connected by a short path), and graph transformers replace local aggregation by global attention over all node pairs. Di Giovanni et al. (2023) proved that network width can mitigate over-squashing at the cost of sensitivity, that added depth is dominated by vanishing gradients, and that topology plays the greatest role; they also formalised long-range task dependencies as label-relevant information residing at large graph distance from the node being represented. The term problem radius — the number of hops actually required by a learning task, i.e. the radius of the smallest neighbourhood that already contains all label-determining information — is proposed by the position paper itself, which asks for statistics that quantify the label relevance of different-sized receptive fields. The Long Range Graph Benchmark (LRGB; Dwivedi et al., 2022) was designed to test long-range capability, but Tönshoff et al. (2023) showed that the reported performance gap between graph transformers and message-passing GNNs on LRGB largely vanishes under proper hyperparameter optimisation. Against this background, the position paper of Kormann, Doerr and Lutzeyer (2026) reports experiments on seven node-level and four graph-level standard benchmarks indicating that accuracy and over-smoothing measures are mostly uncorrelated, that optimal model depth stays small even with mitigation techniques, that EGP/BORF/SDRF yield no significant gains, and that curvature is largely uncorrelated with accuracy. It conjectures that for most real datasets the distribution of label-relevant information is localised within a small kk-hop neighbourhood and factorises, meaning the joint distribution of label-relevant information over a node's receptive field decomposes into node-marginal (or otherwise low-order) components, so that subsets of the receptive field can be processed independently and the entire receptive field need not be jointly observed. Two 2025 works began quantifying long-range interactions: Bamberger et al. (2025) formalised long-range graph tasks and introduced a range measure for operators on graphs, and Liang et al. (2025) proposed the City-Networks dataset together with a Jacobian-based measurement of distant-hop influence (the Jacobian of a network output with respect to input features quantifying how strongly distant nodes affect a prediction). The position paper acknowledges both as first attempts but objects that Jacobian-based statistics entangle the effects of the model with those of the underlying graph and data, so they cannot decide whether a task itself requires joint long-range observation.

Problem Statement

The problem, as posed by Kormann, Doerr and Lutzeyer (arXiv:2601.07419, Outlook passages of Sections 2.2 and 3.2 and the Section 4 Conclusion), is to replace the position-paper debate about over-smoothing and over-squashing with data-side evidence. All requested results serve one shared objective: to determine, from properties of the learning task and dataset alone, whether the phenomena that motivate deep-GNN mitigation research actually limit real-world graph learning. Concretely: (i) give formal definitions and validated estimation algorithms for statistics that quantify the problem radius (the minimal receptive-field radius the task requires), the localisation of label-relevant information (how much information about the label is concentrated in small kk-hop neighbourhoods versus in distant nodes), and the factorisation of the label distribution over a kk-hop receptive field (whether the joint distribution of label-relevant information decomposes into node-marginal or low-order components, so that the receptive field need not be jointly observed); these statistics must be defined on the data side, i.e. independently of any particular model, so that data-side task structure and model-side propagation effects (such as Jacobian-based influence measures) can be diagnosed separately, unlike existing operator- and Jacobian-based measures that entangle the two. (ii) Use these statistics to identify natural real-world datasets and learning tasks whose labels demonstrably depend on long-range joint receptive-field observation — tasks where factorisation fails, individual distant outlier nodes carry uniquely label-relevant information, and over-squashing is a practical limiter — including diagnostic procedures that can detect such individual distant nodes instead of averaging over entire kk-hop neighbourhoods. Because the source explicitly calls for real-world rather than synthetically constructed examples, tasks whose labels are constructed from global graph structure do not settle (ii): they certify long-range dependence by construction instead of demonstrating it for a natural task. The paper additionally notes that the quantification of the problem radius, in combination with an observation of the optimal smoothing depth, should guide efforts in improving model architectures, and that investigating the localisation of relevant information can help understand interaction along low-curvature edges and long-range relationships, to guide targeted rewiring techniques; these guidance applications motivate the statistics but are not posed as separate deliverables in the source.

References

  1. Kormann, N., Doerr, B., Lutzeyer, J. F. (2026). Position: Don't be Afraid of Over-Smoothing And Over-Squashing. arXiv:2601.07419. https://arxiv.org/abs/2601.07419
  2. Bamberger, J., Gutteridge, B., le Roux, S., Bronstein, M. M., Dong, X. (2025). On Measuring Long-Range Interactions in Graph Neural Networks. arXiv:2506.05971. https://arxiv.org/abs/2506.05971
  3. Liang, H., Sáez de Ocáriz Borde, H., Sripathmanathan, B., Bronstein, M., Dong, X. (2025). Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement. arXiv:2503.09008. https://arxiv.org/abs/2503.09008
  4. Arnaiz-Rodriguez, A., Errica, F. (2025). Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning. arXiv:2505.15547. https://arxiv.org/abs/2505.15547
  5. Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., Bronstein, M. (2023). On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. arXiv:2302.02941. https://arxiv.org/abs/2302.02941
  6. Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., Bronstein, M. M. (2021). Understanding over-squashing and bottlenecks on graphs via curvature. arXiv:2111.14522. https://arxiv.org/abs/2111.14522
  7. Alon, U., Yahav, E. (2020). On the Bottleneck of Graph Neural Networks and its Practical Implications. arXiv:2006.05205. https://arxiv.org/abs/2006.05205
  8. Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., Beaini, D. (2022). Long Range Graph Benchmark. arXiv:2206.08164. https://arxiv.org/abs/2206.08164
  9. Tönshoff, J., Ritzert, M., Rosenbluth, E., Grohe, M. (2023). Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. arXiv:2309.00367. https://arxiv.org/abs/2309.00367
  10. Miglior, L., Tolloso, M., Gravina, A., Bacciu, D. (2025). Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation. arXiv:2512.17762. https://arxiv.org/abs/2512.17762
  11. Mishayev, Y., Sverdlov, Y., Amir, T., Dym, N. (2025). Short-Range Oversquashing. arXiv:2511.20406. https://arxiv.org/abs/2511.20406
  12. Tori, F., Bini, L., Sorbi, M., Marchand-Maillet, S., Ginis, V. (2026). Probing Graph Neural Network Activation Patterns Through Graph Topology. arXiv:2602.21092. https://arxiv.org/abs/2602.21092
  13. Nagar, E., Lin, Y.-W. E., Levie, R. (2026). Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observables. arXiv:2605.13383. https://arxiv.org/abs/2605.13383
  14. Gan, G., Chen, L., Kim, J. H. (2026). The spectral smoothing bias in AI-based air quality forecasting: a graph spectral diagnostic framework. Machine Learning: Science and Technology. DOI: 10.1088/2632-2153/ae7f69. https://doi.org/10.1088/2632-2153/ae7f69