Oversmoothing, "Oversquashing'', Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning
Authors: Adrian Arnaiz-Rodriguez
Federico Errica
Venue: ICLR 2026 Poster (2026)
Keywords: oversmoothing
oversquashing
heterophily
long-range propagation
graph neural networks
graph machine learning
Primary area: learning on graphs and other geometries & topologies
TL;DR: This paper challenges some of the common beliefs and assumptions in the graph machine learning community.

Abstract: After a renaissance phase in which researchers revisited the message-passing paradigm through the lens of deep learning, the graph machine learning community shifted its attention towards a deeper and practical understanding of message-passing's benefits and limitations. In this paper, we notice how the fast pace of progress around the topics of oversmoothing and oversquashing, the homophily-heterophily dichotomy, and long-range tasks, came with the consolidation of commonly accepted beliefs and assumptions -- under the form of universal statements -- that are not always true nor easy to distinguish from each other. We argue that this has led to ambiguities around the investigated problems, preventing researchers from focusing on and addressing precise research questions while causing a good amount of misunderstandings. Our contribution is to make such common beliefs explicit and encourage critical thinking around these topics, refuting universal statements via simple yet formally sufficient counterexamples. The end goal is to clarify conceptual differences, helping researchers address more clearly defined and targeted problems. The hope is to clarify the distinction between the different issues and promote separate but intertwined research directions to address them.

Published as a conference paper at ICLR 2026
OVERSMOOTHING, "OVERSQUASHING" HETEROPHILY, LONG- RANGE, AND MORE: DEMYSTIFYING COMMON BELIEFS IN GRAPH MACHINE LEARNING
Adrian Arnaiz-Rodriguez"
Federico Errica'
ELLIS Alicante adrian@ellsallcantee.
NEC Laboratories Europe
federico. erricafneclab. eu
ABSTRACT
After a renaissance phase in which researchers revisited the message-passing paradigm through the lens of deep learning, the graph machine learning commu- nity shifted its attention towards a deeper and practical understanding of message- passing's benefits and limitations. In this paper, we notice how the fast pace of progress around the topics of oversmoothing and oversquashing, the homophily- heterophily dichotomy, and long-range tasks, came with the consolidation of com- monly accepted beliefs and assumptions under the form of universal statements that are not always true nor casy to distinguish from each other. We argue that this has led ambiguities around the investigated problems, preventing researchers from focusing on and addressing precise research questions while causing a good amount of mmsunnderstandings. Our contribution is make such common beliefs explicit and encourage critical thinking around these topics, refuting universal state- ments via simple yet formally sufficient counterexamples. The end goal is clar- ify conceptual differences, helping researchers address more clearly defined and targeted problems.
INTRODUCTION
The last decade has seen an increasing scholarly interest in machine learning for graph-structured
data (Sperduti Starita 1997 Micheli Sestito 2005 Gori 2005 Baceiu et al. 2020).
After an initial focus on the design of various message- passing architectures Gilmer et al. 2017).
inheriting from the recurrent (Scarselli al., (209) and convolutional (Micheli 2009) Deep Graph
Networks (DGN), together with the analysis of their expressive power (Xu et al.
2019 Morris et al.)
2023), researchers later turned their attention to the intrinsic limitations of the message-passing strategy and the relation between the graph, the task, and the attainable performance. We refer, in particular, to the fact that node embeddings may become increasingly similar to each other as more message-passing layers are used (Rusch et al. (023)), the loss of information that results from aggregating too many messages onto a single node embedding (Alon & Yahav 2021). the presence of topological bottlenecks (Topping et al.) (0022). the existence of neighbors of different classes (Wang et al. 2024), and the propagation of information between far ends of a graph (Dwivedi et al.) 2022). Addressing these limitations makes difference when applying message-passingg models, including foundational ones (Beaini et al. 2024), to large and topologically varying graphs at different scales, from proteins with hundreds of thousands of atoms (Zhang et al., 2023) dynamically evolving social networks (Longa et al., 2023) with billions of users. where such limitations manifest together.
pace of research so rapid can sometimes lead, however, the premature consolidation of ideas and beliefs that have not been thoroughly verified. There are several reasons for this to happen: the (perhaps too) intense pressure to publish, follow the latest scientific trends, and demonstrate state- of-the-art performance. As result, we may end up putting the spotlight on positive findings but overlooking contradictory evidence, eventually accepting hypotheses as canon.
'Equal Contribution

---

Published as a conference paper at ICLR 2026
Table 1: List of common beliefs. For a non-exhaustive list of papers that make those claims, please refer to Table 2 in the Appendix.
Beliefs
Beliefs
OSM
OSM is the cause of performance degradation.
OSQ synonym of a topological bottleneck.
2. OSM is property of all DGNs.
OSQ synonym of computational bottleneck.
Hom-Het
Homophily good, heterophily is bad.
OSQ problematic for long-range tasks as well.
4. Long-range propagation is evaluated on het-
9. Topological bottlenecks associated with long- range problems.
erophilic graphs.
5. Different classes imply different features.
In this paper, we argue and provide evidence that this is potentially the case for the afore-mentioned issues of oversmoothing (OSM), oversquashing (OSQ) heterophily, and long-range dependencies, driving researchers away by the difficulty of cireumventing common beliefs while concurrently introducing novel contributions. Scientific progress is therefore slowed down both in terms of reduced workforce and clarity of the problems be addressed; failure acknowledge existing inconsistencies may well lead to a reiterated spreading of questionable claims.
Contribution: While reviewing the literature, we identified and grouped together nine common beliefs that cause great confusion and ambiguities in the field, especially when taken separately. We then demystify such beliefs by providing simple counterexamples that should be easy to recall. By encouraging critical thinking around these issues and separating the different research questions, hope to foster further advancements in the graph machine learning field.
Disclaimer: We remark that the goal of this paper is not explicitly pinpointing criticalities in previous works; on the contrary, these works were fundamental to forming our current understanding and ultimately producing this manuscript. We also acknowledge that the list of referenced works cannot be exhaustive, due to the field's s size, and it mainly serves to support our arguments.
Table D summarizes our findings about common beliefs in the literature, together with the list of We logically divide common beliefs about OSM,
papers where we could find mentions of them H OSQ, and the -heeepilyy dichotomy. the following sections, we discuss each belief, provide counterexamples, and summarize our arguments with home-home messages.
For readers that are less familiar with the topic and its definitions, Appendix provides brief introduction to message-passing models. In addition, Appendix E provides discussion with alternative perspectives on the issues discussed in this paper. The code we use to run experiments available at ltttss:/ com/ Adr anArnaiz http://deysstiiiyieeeeearr
IS OVERSMOOTHING A REAL ISSUE?
Oversmoothing broadly refers the phenomenon where, we stack more message-passing layers in DGN, the node embeddings become increasingly similar to each other, eventually collapsing
into a low-dimensional (Huang et al.) 22200] Oono Suzuki| (2020) or even single-vector (Cai & Wang subssss This creates an almost constant representation, independent of the original node-feature distribution, and can potentially result loss of discriminative power (Li al. 2018
Cai & Wang 2020 Oono & Suzuki, 2020).
Formally, let H RR be the matrix of node embeddings after message-passingg layers in a DGN, where n is the number of nodes and d is the hidden dimension. Consider similarity (or separation) function ): H + R, where H = nxd is the space of all possible embedding matrices. We say that DGN experiences OSM if
lim (1I" = c. 80000
We discuss and address the troubling abuse the term "oversquashing" in later sections. Sometimes we found overly general claims in the first sections, later refined, which nonetheless contribute the spreading of common beliefs.
2

---

Published as a conference paper at ICLR 2026
where is some constant indicating collapse of embeddings. Deviation metrics (e.g., Dirichlet Energy (Cai & Wang, 2020), MAD (Chen et al. 2020al) and subspace-collapee criteria (Oono &
Suzuki 2020 Huang al.) 2024 Roth & Liebig 2024) all measure the same intuition: as depth
increases, node embeddings shrink toward a nearly constant subspace or degree-propoorional vectors.
2.1 BELIEF: OSM IS A PROPERTY OF ALL DGNS.
widespread claim in the literature is that OSM happens regardless of the specific architecture or the underlying graph. Early theoretical works support this view by analyzing message- nessage-passing passing propagation as diffusion process: iterated normaizzedLLallaiinn updates converge degree- weighted stationary distribution (Cai & Wang 2020 Giraldo et al. (2023), while heat-kernel diffusion converges constant vector (Oono & Suzuki 2020 Arnaiz-Rodrigus
Velingker 2024). The resulting bounds quantify the rate of OSM in terms of the singular values of the feature transform W and the eigenvalues of the graph structure G.
These conclusions, however, rely on restrictive assumptions. Later work has relaxed them by intro- ducing learnable feature transforms, non-linear activations, and more elaborate architectures (Oono Suzuki 2020 Cai & Wang/ 2020; Wu et al.. 2023a), yet existing proof shows inevitable collapse under realistic training regimes. In practice, remedies such as residual/skip connections, normaliza- tion layers, gating mechanisms explicitly architectural changes designed to maintain local distinctions, calling into question the universality of this OSM claim.
In addition, many studies probe OSM with untrained (weights frozen at initialization) linear GCN stacks, an experimental choice that hides the effect of learning and may lead to the wrong conclusions, as noted by /Zhang al. (2025). Indeed, Cong et al. (2021] Figure 2) report OSM only for frozen- weight networks; once parameters start adapting, the models preserve informative variance. Together, these observations suggest that OSM not an inevitable consequence of message-passingg but rather a contingent outcome that depends on training dynamics and architectural design choices.
Empirical Example We show a simple training scenario where we see how OSM is not a property of all DGNs and how different elements make it difficult to draw clear conclusions. We used several DGNs under two propagation variants: the vanilla AXW update and the rescaled AX AX()W), following the same experimental procedure as Roth & Liebig (2024) Figure 1). We measure OSM with 2 different metrics: Dirichlet Energy (DE) and its norm-nor normalized version, the Rayleigh Coefficient (RQ), which was also previously used in some works (Cai & Wang 2020
Di Giovanni
ct al. 2023b Roth & Liebig 2024;
Maskey et al. 2023), defined as:
"HH H
DE(H = ((H LH) Σ
Σ h. h 0.VEE
RQ
where L is the graph Laplacian and H' is the node embedding matrix layer f. DE measures the raw smoothness of the embeddings, while RQ normalizes this smoothness by the overall scale of the embeddings. providing relative measure of how much the embeddings are collapsing compared to their norm. Appendix B.2 provides more details on these metrics and their relation to OSM.
Figure shows three key facts: (i) some architectures never collapse, (ii) minor rescaling can reverse the trend, and (iii) DE and RQ often disagree. Hence, OSM is neither universal nor straightforward to diagnose.
First, OSM, as measured by DE, is not universal: GIN's s DE explodes instead of collapsing in the vanilla setting (a), which shows that changing the aggregation-function may lead to an opposite behavior of the OSM effect.
Second, a minor scaling in the feature transformation (2W instead of W) flips the behavior of several models: curves that decayed in (a) now grow or stabilize, and vice-versa; this behavior is thcoretically analyzed in Di Giovanni et al. (2023b). Similar small tweaks (normalization layers, self-loops, alternative aggregators) can likewise create remove DE collapse, which has been leveraged by prior work to propose OSM mitigation approaches, such as the ones based on feature normalization (Wul et al. 2019 Zhao & Akoglu 2020 Zhou et al. 2020).
Finally, whether OSM is observed depends on the measure of choice. DE reflects raw smoothness, whereas the RQ normalizes by the feature norm. As result, the same model can exhibit mutually
3

---

Published as a conference paper at ICLR 2026
DE and Norm
Durchler Energy
DC and Nomm:
Norm
RO2
CCN
GAT
SAGE
GIN
SAGE GIN
10 19 36
10
35
61
19 36 61
30
(a) W: DE and Norm
(b) 2W: DE and Norm
(c) W: RQ
(d) 2W: RQ
Figure I: (a-b): We depict the evolution, with increasing number of layers, of the DE, using W and 2W feature transformations for different architectures. (c-d): Evolution of the RQ for W and 2W as before. Experiments run on the Cora dataset for 50 random seeds. A larger version for better visualization is available in Fig. 8
contradictory trends for different metrics (Zhng al. 2025) First, GCN's DE collapses under the vanilla aggregation (a), explodes with a simple rescaling (b), yet RQ remains essentially flat in both normalised plots (c-d), indicating that GCN embeddings are being rescaled, not necessarily oversmoothed. On the contrary, GAT and SAGE, which had similar behavior as GCN in (a) and (b), decay using RQ (c-d) at a (roughly) linear rate, highlighting how different architectures respond differently to the use of RQ instead of DE. Furthermore, subfigure (d) shows that (X()W) can stabilize RQ for certain methods, suggesting that normalizations or small parameter adjustments do not affect all models uniformly. Therefore, conclusions about OSM depend heavily on metric and model, an observation that we rarely found in the literature.
In conclusion, OSM is neither inevitable nor uniquely defined: its observation hinges on the archi- tecture, on secmingly innocuous adopts (Zhang et al. 2022). Therefore, natural question arises: Does OSM actually limit the mod- els' predictive accuracy? We investigate this question in the next section.
and on which stability metric (DE vs. RQ) one
2.2 BELIEF: OSM IS THE CAUSE PERFORMANCE DEGRADATION.
Part of the literature focuses on the narrative that OSM is the cause of lower test accuracy in DGNs. The hypothesis that if embeddings collapse to a non-meaningful space, then the separability the nodes will become challenging, and accuracy decreases.
However, this hypothesis ignores some critical aspects, such as i) the separability of node embeddings with respect to the nodes' labels, and fi) how such separability evolves in the intermediate OSM phase (if it happens, as we discussed before).
Regarding the first statement, although it is true that if there is total collapse to the same value then the embeddings will not be informative at all, the main problem remains the node embeddings' separability. As shown in the previous section, some changes in the architectures but they might have no impact on the overall accuracy. For instance, multiplying by two the weight matrix leads general increase in DE for all architectures; however, the accuracy will remain the same since the embeddings have been simply scaled up, and the embeddings' separability is not affected negatively. In addition, avoiding an embedding collapse does not necessarily lead to an improvement in generalization accuracy. For instance, comparing a GCN with and without bias, both versions show decrease in performance as the number of layers increases, whereas only GCN shows a collapse in DE (Rusch et al., 2023 Figure 3).
avoid OSM,
On the other hand, and related to the second statement, embedding collapse will not always lead to a decrease in accuracy. OSM happens faster in some subspaces than in others, and this effect will be beneficial if labels are correlated with those subspaces (Keriven 2022). For instance, we classify points into two classes, and all nodes of distinct classes collapse into different points, the OSM metric will detect such a collapse. However, the separability of the node embeddings will remain possible, illustrating also the limits of widely used OSM metrics with respect label information.
This intuitive behavior has been identified in the literature as form of "beneficial" smoothing phase (Keriven 2022 Roth & Liebig 2024 Wu et al.) 2023b). In this phase, the nodes of each class first collapse into a class- deaenden point before the potential second stage, at which point all nodes converge the same representation. Finally, although overall pairwise distances might shrink in
4

---

Published as a conference paper at ICLR 2026
deep layers, within-class distances might contract more than between-class ones, class separability improves despite the global collapse, as discussed by Cong et al. (2021).
In conclusion, low accuracy in DGNs cannot be attributed to OSM alone. The separability of node
embeddings plays major role, where other training problems such as vanishing gradients or over-
fitting also arise when using big number of layers (Zhao & Akoglu 2020 Cong et al. [0021 Yang
et al. 2020 Arroyo et al. 2025 Park et al. 2025).
Call to Action
not assume OSM applies to all DGNs
ii) Avoid attributing performance drops to OSM by default. The performance is related to node embeddings' separability, which also be affected by many other elements, such as vanishing gradients over-fitting.
iii) Shift research towards achieving separability of node embeddings and, optionally, how OSM relates to that.
HOMOPHILY- AND THE ROLE OF THE TASK
In the context of node classification, the term homophily (resp. heterophily) generally refers to some form of similarity (resp. dissimilarity) between node and its neighbors (McPherson et al. 2001). This (dis)similarity can be measured with respect to class labels, node features, or both; the vast majority of works in the literature opt for the first, but this choice is often implicis and taken for granted, making some statements hard to interpret when one is aware the other ways to measure it.
3.1 BELIEF: HOMOPHILY GOOD, HETEROPHILY BAD
A recurrent narrative in the literature is that the pesssage-passing mechanism of DGNs is particularly suited for homophilic graphs, whereas is unfit for heterophilic graphs. The apparent motivation is that, in homophilic graphs, all you need to do to solve node classification task is to look at similar neighbors, and local in contrast class heterohetropiiiic graph, where there exist neighboring nodes of different class that might make it harder for message-passinn to isolate the "relevant information", intended as neighbors of the same class. Such belief is supported by empirical evidence rather restricted set benchmarks (Sen et al. 2008 Namata et al., 2012 Pei et al.) 2020) with varying levels of homophilyyheterophilyy
strategy implements just the right inductive bias. This
class 0
23
class
distance(s)2
a6
1 IV
Figure 2: Left: fully heterophilic graph inspired by Ma et al. (002 where a 1-layer, sum-based DGN can perfectly classify the nodes due to a difference homophilic graph where the task is to predict if node is at distance greater than five from specific node. Here, the performances of a DGN will be poor unless information from nodes of another community from the perspective of class-O node is captured.
the node degree. Right: highly
Researchers already tried to challenge these considerations in the past (Ma et al. 2022 Errica 2023
Luan et al. 2023: Platonov et al. 2023b] Wang et al. 2024). Consider Figure 2 (left,. where bipartite graph with identical node features fully glass-htterophilis If we apply single sum-based graph convolution, the nodes can be perfectly classified as the resulting embeddings depend on the incoming degree. Therefore, there exist heterophilic graphs where DGN can achieve perfect classification.
5

---

Published as a conference paper at ICLR 2026
On the contrary, Figure 2 (right) depicts highly class-homophilie graph, where nodes belong to of two classes if they are at distance greater or lower than five from a given node s. In this case, the information the nodes does not matter; if we were to follow the above belief, encouraged to use a few layers of message- message-passing, and as a result we could never solve the task perfectly. These considerations have motivated the definition of new metrics that put homophily and heterophily in relation with performance under certain assumptions, for instance in Ma et al. (2022).
would be
3.2 BELIEF: DIFFERENT CLASSES IMPLY DIFFERENT FEATURES
In the previous section, we deliberately ignored the interplay between node's features and its class label, which is induced by the task at hand. The reason is that we wanted to clarify the distinction with another, more subtle, and problematic belief: nodes belonging different classes should have different (i.e., separable) feature distributions. Under this assumption, class homophily implies feature homophily.
Such an assumption is often key in arguments supporting the belief of Section 3.1 Indeed, if nodes of different classes have different feature distributions, then applying local ceassage-psssingg iteration to highly class-homophilic graph should "preserve the distance" between node embeddings of different classes. On contrary, in a heterophilic setting, a graph convolution would mix information coming from different feature distributions, which may be detrimental to performance.
The logic is not incorrect per-se, but our key counterargument is the following: different classes imply different feature distributions, why would one need to apply DGN rather than simple MLP? In other words, either there is a very strong assumption that the task does not depend on the topological information, the feature-class distributions induced by the task allow to somehow take shortcut in terms of learned function, neglecting the role that the topology might have. Note that this discussion is irrespective of the denoising/regguarriing effects of DGNs semi-supervised Errica 2023).
scenarios compared to MLPs (Hoang et al. 2021
appears therefore necessary to consider less trivial and more fine- ane-grained scenarios, where the feature distributions of different classes partially or totally overlap, the topology has key role in the task definition, and topological properties induce positive/negative effect on the performance of cassage-passingg models as done, for instance, in recent works (Castellana & Errica 2023 Zheng
al. 2024).
3.3 BELIEF: LONG-RANGE PROPAGATION IS EVALUATED HETEROPHILIC GRAPHS
The common beliefs of Sections 3.1 and 3.2 have been used to support yet another argument, namely that we should evaluate the ability of DGNs to propagate long-range information on heterophilic graphs. The rationale seems be that, in order for DGNs to perform well, nodes of given class should focus on information of similar (w.rt. class and/or features) nodes; therefore, in a heterophilic graph, it may be necessary capture information far away (i.e., long-range) from the immediate neighborhood.
Once more, what is really important is to distinguish the task, e.g., that depends on long-range propagation, from the class labels the task induces on the nodes. As a matter of fact, the "long- range" task of Figure 2
(right) induces highly homophilic graph, while the heterophilic graph of Figure 2 (left) is not associated with a long-range propagation task. Therefore, we cannot draw generic relation between long-range tasks and heterophily without making further assumptions.
Call to Action
Do not rely generic claims about the performance of DGNs under homophily and heterophily, nor about their relation with long-range problems.
ii) Treat homophily/heterophily properties as task dependenn,,,,, not the converse.
iii) Move past the coarse comophily-hcteropee dichotomy and focus more on the task and the interplay between features, structure, and class labels.

---

Published as a conference paper at ICLR 2026
4 THE MANY FACETS OF "OVERSQUASHING" AND THEIR NEGATIVE IMPLICATIONS
The term oversquashing originated from Alon & Yahav (202 and referred to "exponentially growing information into a fixed-size vector" by repeated application of message-passing, In other words, oversquashing was associated with the computational tree (Figure 3) induced by message- passing layers on each node of the graph. Later, oversquashing was connected by Topping et al. (2022) to the existence of topological bottlenecks: "edges with high negative curvature are those causing the graph bottleneck and thus leading to the squr-squa phenomenon". Since then, researchers have adopted one or even both definitions of oversquashing at the same time, contributing to an apparent understanding that these definitions subsume the same problem.
In this section, we argue that this is not the case and that, as a community, we should clearly separate the term "oversquashing" into (at least) two separate terms:
Computational Bottlenecks and Topological Bottlenecks
Computational bottlenecks, defined in Def. are inevitably related to the message-passingg architec- ture, for which the graph is the computational medium, whereas topological bottlenecks refer the graph connectivity, usually measured with spectral or curvature metrics defined in Appendix [B3.2] Therefore, the topological bottlenecks are intrinsic the graph, while the computational bottleneck is intrinsic to the architecture or procedure. While these bottlenecks are clearly intertwined, in the following we show that they do not always coexist, hence makes sense to treat them as fundamen- tally distinct concepts.
Computational and Topological Bottleneck definitions. Although both bottlenecks have been previously used to measure "oversquashing" their definitions and measurement approaches also differ across the literature. There is no universally accepted formal definition of a topological bottleneck; instead, it is typically characterized using proxy metries, most often involving the spectral gap of the curvature. Some of the most significant metrics are summarized in B.3.2
On the other hand. the computational bottleneck has been usually measured using the receptive field (Chen et al. 2018 Alon & Yahav, 2021 ,, N as the set of K-hopp neighbors, which grows
exponentially with the number of layers.
However, when evaluating the actual computational graph produced by message-passing, shown in Figure 3 (right), duplicate nodes become significant: node appearing in multiple branches of the computation tree contributes repeatedly, as each unique walk generates a distinct message. Consequently, employ multiset notation formally define the computational tree for a node s:
M
= No. M = =M MK-1
Nu
WEM
Therefore, can define the notion of an pypoonentiallyggooinng receptive field" (Alon & Yahav 2021) as follows:
Definition 4.1 (Computational Bottleneck). For a given node e and number of message passing layers K, the computational bottleneck of node v is defined as |M J.
We refer the reader to B.4 for further insights, related work, and connections between this definition and matrix matrix-power power interpretations of message passing.
Figure 3 visualises the difference between the set size |AR| and the multiset size |M on toy graph and on a simple graph.
4.1 BELIEF: OVERSQUASHING AS SYNONYM OF TOPOLOGICAL BOTTLENECK
The prolific line of work that associates "oversquashing" with topological bottlenecks seems to have gained popularity with Topping et al. (2022). In that paper, edges with negative curvature first associated with (topological) bottlenecks, then theorem puts in relation message-passing
7

---

Published as a conference paper at ICLR 2026
I = 24
N 9
N
Figure 3: We intuitively visualize what happens when we repeatedly aggregate the neighborhood of the star node using the message- paassaggg paradigm, where define the computational bottleneck as the size of the computational tree (24 computational nodes) for k = 3 vs the receptive field for = that includes three-hop neighbors).
graph containing bottleneck with the Jacobian sensitivity of node representations, typically defined by [(,, v) [| / | and denoting how much the final representation of node after K layers influenced by the initial representation of node (Xu al., 2018). Put simply, topological bottleneck may imply low sensitivity. However, the converse is not necessarily true: we can have low sensitivity on graph where there are no bottlenecks. Figure (left) shows grid graph where there are topological bottlenecks. The repeated application of message passing will, however, quickly generate a computational bottleneck. Therefore, saying that there are no topological bottlenecks does not imply that there
computational bottlenecks.
To improve on topological bottlenecks, a widely investigated approach is graph rewiring (Attali et al. 2024b), which was also the subject of scrutiny recently (Tortorella & Micheli 2022 Tori et al. 2025). Rewiring is based on the intuition that improving topological bottlenecks metrics should improve the performance of DGNs
et al. 2022 Banerjee al.) [022 Karhadkar al.) 2023
Deac et al. ) by reducing the distance between nodes that should communicate. At same time, should become clear that, under the DGN paradigm, rewiring might worsen the computational bottleneck as long as the same number of pessage-passingg layers used while improving the topological one. This perspective was also put forward by EEriiaa al. (2025), with a theoretical analysis on how message filtering as shown in Figure 4 (middle), reduces both the computational bottleneck and sensitivity yet improves performances while leaving the graph structure unaltered.
h
Computational Bottleneck: Severe Topological Bottleneck: No Sensitivity: Decreases with L.
Computational Bottleneck: Mild Topological Bottleneck: Yes Sensitivity: Decreases with
21
x6
Figure 4: Left: grid graph, the computational bottleneck grows very quickly, there is no topological bottleneck. Middle: A visualization of the computational graph rooted at node v3 E V, for two message passing layers, highlighting how pruning messages reduces the computational bottleneck. Right: In this graph, there is topological bottleneck and mild computational bottleneck. As with the grid graph (Appendix C the sensitivity decreases with the number of message- paaaggg- layers.
Thhe concept of message filtering refers to message passing architectures with the ability to learn how many messages exchange between nodes and which messages to filter
8

---

Published as a conference paper at ICLR 2026
Another, slightly more technical way to why low Jacobian sensitivity does not imply the presence of any topological bottlenecks is to follow the chain of upper bounds that link the metrics used to measure the computational and topologiaal bottlenecks (Black al. 2023
Di Giovanni et al. 2023a
Karhadkar et al. 2023 Ammiz-Rodriguez et al. 2022).
Several recent works (Black al. 2023 Di Giovanni et al.
2023a have shown that sensitivity is
upper bounded by term that includes the effective resistance, a purely topological distance metric that quantifies the expected commute time of random walk between nodes and (Klein & Randič 1993). In particular, the bound subtracts the lower bound on the maximum effective resistance, which depends on the inverse of the spectral gap -a proxy for topological bottlenecks- (Chandra al., 1989: Lovász 1993). This connection provides useful intuition: as the topological bottleneck gets worse, the lower bound on the maximum effective resistance increases, which in turn reduces the upper bounds on the sensitivity of Black et al. 2003)..
However, the converse does not hold. There are graphs where the maximum effective resistance between distant nodes is large despite the absence of topological bottlenecks. For instance, consider example of grid graph Figure 4 (left) where there is no topological bottleneck, yet the effective resistance between diagonally opposite corners grows linearly with the grid size. As result, sensitivity between those nodes decays with depth, even though the graph has no identifiable topological bottlenecks. This illustrates that computational bottlenecks can arise independently of topological ones, and that low sensitivity does not necessarily imply the presence of either of them.
4.2 BELIEF: OVERSQUASHING AS SYNONYM OF COMPUTATIONAL BOTTLENECK
We briefly complement the previous section with discussion on "oversquashing" as a computational bottleneck, which was introduced by Alon & Yahav (202I) and has been the (often implicit) study subject of works that prune, some extent, the computational tree induced every node by the iterative message-passeen exist cases where reducing the computational bottleneck may be harmful: Figure (right) shows graph where there is topological bottleneck but no severe computational bottleneck (for a limited number of layers). In this case, excessive pruning of the computational tree might cause distant nodes to interrupt all communications, Therefore, computational and topological bottlenecks are problems that should be tackled separately.
process [Rong et al. 2020; Errica et al. 2025). Also this case, there
4.3 BELIEF: OVERSQUASHING PROBLEMATIC FOR LONG-RANGE TASKS WELL.
oversquashing has often been considered problem long-range tasks. The reason stems from its relation to the exponentially growing computa- tional tree the number of message-passing layers increases: whenever node has to receive in- formation from another node at distance d, classical (synchronous) message- message-passing architectures need to apply at least d layers to capture that information. As result, the relevant information may get lost due to the exponentially large computational bottleneck. Importantly, topological bottlenecks can only make the problem worse, by forcing the information of a group of messages to be squeezed through an edge please refer the next section for a discussion about Long-range tasks and topological bottlenecks.
Since its definition by Alon & Yahav 2021
The main message here is that longerange tasks "force" classical passaag-ppassigg architecture to create a computational bottleneck to propagate the necessary information, but one can observe computa- tional bottlenecks even in short-range tasks. An obvious example the high-degree node of Figure where, after just one layer, the center node receives high number of messages, effectively creating a computational bottleneck in terms of information to be squashed into fixed-size vector. Therefore, while the task of long-range is related to computational bottlenecks under classical DGNs, compu- tational bottlenecks not prerogative of long-range tasks.
Figure 5: Hubs can exhibit computational bottlenecks.

---

Published as a conference paper at ICLR 2026
4.4 BELIEF: TOPOLOGICAL BOTTLENECKS ASSOCIATED WITH LONG-RANGE PROBLEMS
The last belief we discuss is that topological bottlenecks are the primary obstacle solving long- range tasks. This intuition stems from the fact that narrow cuts impede information flow between distant parts of the graph. is indeed true that a topological bottleneck can worsen communication between distant nodes, especially if the bottleneck lies along path that connects them. However, this perspective is limited two important ways.
First, topological bottleneck is only harmful if it lies on the information paths between nodes that are supposed to communicate. topological bottleneck may exist without affecting task-relevant dependencies. Second, the graph topology worsen the long-range communication even in the absence any identifiable topological bottleneck, by inducing computational bottlenecks. As discussed in Section [4.]] the grid graph is an illustrative case: despite the lack of topological bottlenecks, to connect the opposite corner nodes we need, at least, as many message-passiee layers the distance between them, thus leading to huge computational bottleneck that will likely hamper the ability to process long-range dependencies.
In addition, some of the techniques that reduce topological bottlenecks rely on introducing more far-away away nodes that should communicate. It is important to note that, although these approaches might be beneficial for the task at hand, they also worsen the computational bottleneck by adding more branches to the computational tree.
edges or nodes into the graph, with the aim of reducing the distance between far-
In conclusion, this highlights deeper issue: long-range problems are not solely caused by topo- logical bottlenecks, rather they can be understood as a form information attenuation caused by computational bottlenecks in the message-passing mechanism, which can potentially be exacerbated by topological bottlenecks. Thus, solving a topological bottleneck is neither necessary nor sufficient to solve all long-ran range problems.
Call to Action
Stop using the ambiguous "Oversquashing". which led to unclear research statements. Talking about computational and topological bottlenecks, instead, better defines the research scope paper, since they are two fundamentally distinct concepts.
ii) There can be computational bottlenecks but topological should create ad-hoe benchmarks for each type of bottleneck rather than relying solely on real-world tasks, where is not as easy to distinguish the combined effect of the two bottlenecks.
and vice-versa. This also means
iii) Keep in mind that computational bottlenecks can happen in short-range as well as long-range tasks.
iv) Do not attrihute long-range performance issues solely to topological bottlenecks - account for computational bottlenecks as well.
5 CONCLUSIONS
This paper posits that the fast pace of advances in the graph machine learning field has generated several commonly accepted beliefs and hypotheses, rooted in the notions of oversmoothing, "over- squashing", long-range tasks, and heterophily, which are the cause of misunderstandings between re- searchers. Our contribution was to highlight such beliefs in plain sight, provide an explanation for their emergence, and demystify them when necessary with simple counterexamples. First, we argued that OSM may not an actual problem and that node embeddings' separability should be preferred when looking for the root causes of performance degradation. Then, showed how talking about compu- tational and topological bottlenecks resolves most, if not all, inconsistencies generated by the inflated of the "oversquashing" term. Finally, highlighted the role of the task in statements involv- ing homophily, heterophily, and long-range dependencies. By providing around these aspects, hope foster further advancements in the graph machine learning field.
clarifications
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
A.A. has been partially supported by a nominal grant received at the ELLIS Unit Alicante Foundation from the Regional Government of Valencia in Spain (Resolución de la Conselleria de Industria, Turismo, Innovación Comercio, Dirección General de Innovación) and a grant by the Banc Sabadell Foundation.
REFERENCES
Ralph Abboud, Radoslav Dimitrov, and Ismail IIkan Ceylan. Shortest path networks for graph property prediction. The 1st Learning on Graphs Conference (LoG), 2022.
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. Proceedings of the 36th International Conference Machine Learning (ICML), 2019.
Singh Akansha. Over-squashing in graph neural networks: A comprehensive survey. arXiv preprint arXiv:2308, 15568, 2023.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
Adrian Arniz--Rorrigeez and Ameya Velingker. Graph Learning: Principles, Challenges, and Open Directions. In 41st International Conference on Machine Learning (ICML), 2024. Tutorial.
Adrian Araiz-RRdriguez, Ahmed Begga, Francisco Escolano, and Nuria M Oliver. DiffWire: Inductive Graph Rewiring via the Lovász Bound. In Proceedings of the 1st Learning on Graphs Conference (LoG), 2022.
Adrian Amaiz-Rodriguu Georgina Curto Rex, and Nuria Oliver. Structural group unfaimesss Measurement and mitigation by means of the effective resistance. Proceedings of the International AAAI Conference Web and Social Media, 19(1):33-06,, Jun. 2025.
Álvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xi- aowen Dong, Michael Bronstein, and Pierre Vandergheynst. On vanishing gradients, over- smoothing, and over-squashing in gnns: Bridging recurrent and graph learning. arXiv preprint arXiv:2502.1088 10818, 2025.
Hugo Attali, Davide Buscaldi, and Nathalic Pernelle. Delaunay graph: Addressing over- ver-squashing and over-smoothing using delaunay triangulation. In Proceedings of the 41 International Conference Machine Learning (ICMI), 2024a.
Hugo Attali, Davide Buscaldi, and Nathalie Pernelle. Rewiring techniques to mitigate oversquashing and oversmoothing in gnns: A survey. arXiv preprint arXiv:2411.17429 2024b.
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs Neural Networks, 129, 2020.
Julia Balla. Over-squashing in riemannian graph neural networks. In Proceedings of the 2nd Learning on Graphs Conference (LoG), 2023.
Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Oversquash- ing in gnns through the lens of information contraction and graph expansion. In Proceedings of the 58th Annual Allerton Conference Communication, Control, and Computing (Allerton), 2022.
Federico Barbero, Ameya Velingker, Amin Saberi, Michael M. Bronstein, and Francesco Di Giovanni. Locality-awarr graph rewiring in GNNs. Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024.
11

---

Published as a conference paper at ICLR 2026
Dominique Beaini, Shenyang Huang, Joao Alex Cunha, Zhiyi Li, Gabriela Moisescu- Parejja Oleksandr Dymov, Samuel Maddrell-Mander, Callum McLean, Frederik Wenkel, Luis Müller, Jama Hussein Mohamud, Ali Parviz, Michael Craig, Michat Koziarski, Jiarui Lu, Zhaocheng Zhu, Cristian Gabellini, Kerstin Klaser, Josef Dean, Cas Wognum, Maciej Syperkowski, Guillaume Rabusseau, Reihaneh Rabbany, Jian Tang, Christopher Morris, Mirco Ravanelli, Guy Wolf, Pru- dencio Tossou, Hadrien Mary, Therence Bois, Andrew W Fitzgibbon, Blazej Banaszewski, Chad Martin, and Dominic Masters. Towards foundational models for molecular learning on large-scale multi-task datasets. In Proceedings of the 12th International Conference on Learning Representa- tions (ICLR), 2024.
Wendong Bi, Lun Du Qiang Fu, Yanlin Wang. Shi Han, and Dongmei Zhang. Make heterophilic graphs better fit gnn: A graph rewiring approach. IEEE Transactions on Knowledge and Data Engineering. 2024.
Mitchell Black, Zhengehao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Hugh Blayney, Álvaro Arroyo, Xiaowen Dong, and Michael M Bronstein, glstm: Mitigating over- squashing by increasing storage capacity. arXiv preprini arXiv:2510.0884 2025.
Cristian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pietro Lio, and Michael Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. In Proceedings of the 36th Conference on Advances in Neural Information Processing Systems (NeurIPS), 2022.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. In Graph Repre- sentation Learning and Beyond Workshop, 37th International Conference on Machine Learning (ICML), 2020.
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph transformer. In Proceedings of the 40th International Conference on Machine Learning (ICML) pp. 3408-3430, 2023.
Daniele Castellana and Federico Errica. Investigating the interplay between features and structures in graph learning. In MLG Workshop at ECML PKDD, 2023.
Ashok K Chandra, Prabhakar Raghavan, Walter L Ruzzo, and Roman Smolensky. The electrical resistance of a graph captures its commute and cover times. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 574-586, 1989.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the 34th AAAI conference on artificial intelligence (AAAI), 2020a.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020b.
Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenqing Zheng, Peihao Wang, Xia Hu, and Zhangyang Wang. Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3), 2022.
Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936- 9949, 2021.
Andreca Deac, Mare Lackenby, and Petar Veličković, Expander graph propagation. In Proceedings of the 1st Learning on Graphs Conference (LoG), 2022.
12

---

Published as a conference paper at ICLR 2026
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact width, depth, and topology. In Proceedings of the 40th International Conference Machine Learning (ICML), 2023a.
Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Michael M. Bronstein. Understanding convolution on graphs via energies. Transactions on Machine Learning Research, 2023b.
Francesco Di Giovanni, T. Konstantin Rusch, Michael Bronstein, Andreea Deac, Marc Lackenby, Siddhartha Mishra, and Petar Veličković. How does over-squashing affect the power of GNNs? Transactions on Machine Learning Research, 2024.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022.
Wendy Ellens, Floske M Spieksma, Piet Van Mieghem, Almerima Jamakovic, and Robert E Kooij. Effective graph resistance. Linear algebra and its applications, 435(10):2411-2506 201 1.
Bastian Epping, Alexandre René, Moritz Helias, and Michael Schaub. Graph neural networks do not always oversmooth. In Proceedings of the 38th Conference Neural Information Processing Systems (NeurIPS), 2024.
Federico Errica. On class distributions induced by nearest neighbor graphs for node classification of tabular data. Proceedings of the 37th Conference on Advances in Neural Information Processing Systems (NeurIPS), 2023.
Federico Errica, Henrik Christiansen, Viktor Zaverkin, Takashi Maruyama, Mathias Niepert, and Francesco Alesiani. Adaptive message passing: A general framework mitigate oversmoothing, oversquashing, and underreaching. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.
Lukas Fesser and Melanie Weber. Mitigating over-smoothing and over-squashing using augmentations of forman-ricci eurvature. In Proceedings of the 4th Learning Graphs Conference (LoG), 2024.
Rickard Brüel Gabrielsson, Mikhail Yurochkin, and Justin Solomon. Rewiring with positional encodings for graph neural networks. Transactions Machine Learning Research, 2023.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros. On the trade- off between over-smoothing and squassnu in deep graph neural networks. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management CaaaeeennIIKKKA (ICKM), 2023.
Chenghua Gong, Yao Cheng, Jianxiang Yu, Can Xu, Caihua Shan, Siqiang Luo, and Xiang Li. A survey learning from graphs with heterophily: Recent advances and future directions. arXiv preprint -.Xiv:2401.09769, 2024.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings of the International Joint Conference on Neural Networks (IJCNN), 2005. Schönlieb.
Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, and On oversquashing in graph neural networks through the lens of dynamical systems. In Proceedings of the 39th AAAI Conference Artificial Intelligence (AAAI), 2025.
13

---

Published as a conference paper at ICLR 2026
Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dynamically rewired message passing with delay. In Proceedings of the 40th International Conference Machine Learning (ICML), 2023.
William Hamilton. Graph representation learning. Morgan & Claypool Publishers, 2020.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In Proceedings of the 37th International Conference Machine Learning (ICML), 2020.
NT Hoang, Takanori Maehara, and Tsuyoshi Murata. Revisiting graph neural networks: Graph filtering perspective. In Proceedings of the 25th International Conference Pattern Recognition (ICPR), 2021.
Keke Huang, Yu Guang Wang, Ming Li, and Pietro Lio. How universal polynomial bases enhance spectral graph neural networks: Heterophily, over-smoothing, and over-squashing. In Proceedings of the 41st International Conference Machine Learning (ICMI.), 2024.
Wenhing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over-smoothing for general graph convolutional networks. arXiv preprint arXiv:2008. 099444 2020.
EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. An analysis of virtual nodes in graph neural networks for link prediction (extended abstract). Proceedings of the 1st Learning on Graphs Conference (LoG), 2022.
Adarsh Jamadandi, Celia Aubio-Madrigal. and Rebekka Burkholz. Spectral graph pruning against over-squashing and over-smoothing, In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS), 2024.
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
Nicolas Keriven.
Not too little, not too much: a theoretical analysis of graph (over) smoothing. In Proceedings of the 36th Conference on Advances in Neural Information Processing Systems (NeurIPS), 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR), 2017.
Douglas J Klein and Milan Randić. Resistance distance. Journal of mathematical chemistry, 12: 81-95, 1993.
Niklas Kormann, Benjamin Doerr, and Johannes F Lutzeyer. Position: Don't be afraid of over- smoothing and over-squashing. arXiv preprint arXiv:2601.07419 2026.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the 17th IEEE/CVF International Conference on Computer Vision (ICCV), 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the 32nd AAAI conference artificial intelligence (AAAI), 2018
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-hooophilous graphs: New benchmarks and strong simple methods. In Proceedings the 35th Conference Neural Information Processing Systems (NeurIPS), 2021.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 338-3388 348, 2020.
14

---

Published as a conference paper at ICLR 2026
Yang Liu, Chuan Zhou, Shirui Pan, Jia Wu, Zhao Li, Hongyang Chen, and Peng Zhang. Curvdrop: A ricci curvature based approach to prevent graph neural networks from smoothig and over- squashing. In Proceedings of the ACM International World Wide Web Conference (WWWW). 2023a.
Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent CS Lee, and Shirui Pan. Beyond smoothing: Unsupervised graph representation learning with edge heterophily discriminating. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2023b.
Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, franco scarselli, and Andrea Passerini. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Trunsactions on Machine Learning Research, 2023.
László Lovász. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Chang, and Doina Precup. Is heterophily real nightmare for graph neural networks to do node classification? arXiv preprint 100.020099055441 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In Proceedings of the 36th Conference on Advances in Neural Information Processing Systems (NeurIPS), 2022.
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification? investigating the homophily principle node distinguishability. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In 10th International Conference on Learning Representations (ICLR), 2022.
Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing, In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023.
Miller McPherson, Lynn Smith-Lovin, and James Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27, 2001.
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20, 2009.
Alessio Micheli and Antonio Sestito. A new neural network model for contextual processing of graphs. In Proceedings of the Italian Workshop on Neural Networks (WIRN), 2005.
Yaaqov Mishayev, Yonatan Sverdlov, Tal Amir, and Nadav Dym. Short-range oversquashing. In Proceedings of The Fourth Learning on Graphs Conference (LOG), 2025.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24, 2023.
Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In Proceedings of the Workshop on Mining and Learning with Graphs (MLG), 2012.
Khang Nguyen, Nong Minh Hieu, Vinh Due Nguyen. Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and ovea-squ using ollivier-ricci curvature. In Proceedings of the 40th International Conference on Machine Learning (ICML., 2023.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
MoonJeong Park, Sunghyun Choi, Jaeseung Heo, Eunhyeok Park, and Dongwoo Kim. The over- smoothing fallacy: A misguided narrative in gnn research. arXiv preprint 20Xi:2506.006533 2025.
15

---

Published as a conference paper at ICLR 2026
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova, Characterizing graph datasets for node classification: Homophily--eeterophily dichotomy and beyond. In Proceed- ings of the 37th Conference Neural Information Processing Systems (NeurlPS), 2023a.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In Proceedings of the Ith International Conference on Learning Representations (ICLR), 2023b.
Huaijun Qiu and Edwin R Hancock. Clustering and embedding using commute times. IEEE Transactions on Puttern Analysis and Machine Intelligence, 29(1 29(11):1833-180 2007.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In Proceedings of the 8th International Conference on Learning Representutions, 2020.
Andreas Roth and Thomas Liebig. Rank collapse causes over-smoothing and over-correlation in graph neural networks. In Proceedings of the 3rd Learning on Graphs Conference (LoG), 2024.
Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprini arXiv:2303. 10993, 2023.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20, 2009.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Radd. Collective classification in network data. Al magazine, 29(3):93 2008.
Zhiqi Shao, Dai Shi, Andi Han, Yi Guo, Qibin Zhao, and Junbin Gao. Unifying over-smoothing and over-squashing in graph neural networks: physics informed approach and beyond. arXiv preprint wrXiv:2309.02769 2023.
Dai Shi, Andi Han, Lequan Lin, Yi Guo, and Junbin Gao. Exposition on over-squashing problem on gnns: Current methods, benchmarks and challenges. arXiv preprint arXiv:231 2023.
Joshua Southern, Francesco Di Giovanni, Michael Bronstein, and Johannes Lutzeyer. Under- standing virtual nodes: Oversmoothing, oversquashing, and node heterogeneity. arXiv preprint arXiv:2405. 01044005.3326 13526, 2024.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(3), 1997.
Stevan Stanovic, Benoit Gaüzère, and Luc Brun. Graph neural networks with maximal independent bet-based pooling: Mitigating over-smoothing and over-squashing. Pattern Recognition Letters, 187, 2025.
Qingyun Sun, Jianxin Li, Haonan Yuan, Xingcheng Fu, Hao Peng, Cheng Ji, Qian Li, and Philip S Yu. Position-aware structure learning for graph hopolgy-immallnne by relieving under-reaching and over-squashing In Proceedings of the 31 ACM International Conference on Information & Knowledge Management (ICKM), pp. 1848-1857, 2022.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
Floriano Tori, Vincent Holst, and Vincent Ginis. The effectiveness of curvature-based rewiring and the role of byperparameters in GNNs revisited. In Proceedings of the 13th International Conference Learning Representations (ICLR), 2025.
16

---

Published as a conference paper at ICLR 2026
Domenico Tortorella and Alessio Micheli. Leave graphs alone: Addressing over-squashing without rewiring. In The 1st Learning on Graphs Conference (LoG), 2022.
Aafaq Mohi ud din and Shaima Qureshi. Limits of depth: Over-smoothing and over-squashing in gnns. Big Data Mining and Analytics, 7, 2024.
Hongwei Wang and Jure Leskovec. Combining graph convolutional neural networks and label propagation. ACM Transactions on Information Systems, 40(4), 2021.
Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang. Understanding heterophily for graph neural networks. In Proceedings of the 41 International Conference on Machine Learning
(ICML), 2024.
Keqin Wang, Yulong Yang, Ishan Saha, and Christine AllenBBlancheter Understanding oversmooth- ing in gnns as consensus in opinion dynamics. arXiv preprint arXiv:2501. 19089, 2025.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention- based graph neural networks. In Proceedings of the 37th Conference on Advances in Neural Information Processing Systems (NeurIPS), 2023a.
Xinyi Wu, Zhengdao Chen, William Wei Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In Proceedings of the 11th International Conference Learning Representations (ICLR), 2023b.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over- smoothing in deep gens. arXiv preprint arXiv:2003. 2020.
Wenhang Yu, Xueqi Ma, James Bailey, Yibing Zhan, Jia Wu, Bo Du, and Wenbin Hu. Graph structure reforming framework enhanced by commute time distance for graph classification. Neural Networks, 168, 2023.
Kaicheng Zhang, Piero Deidda, Desmond Higham, and Francesco Tudisco. Rethinking oversmoothing in graph neural networks: rank- base- perspective. arXiv preprint arXiv:2502.0459), 2025.
Wentao Zhang, Zeang Sheng, Ziqi Yin, Yuezihan Jiang, Yikuan Xia, Jun Gao, Zhi Yang, and Bin Cui. Model degradation hinders deep graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2022.
Xuan Zhang, Limei Wang. Jacob Helwig, Youzhi Luo, Cong Fu, Yaochen Xie, Meng Liu, Yuchao Lin, Zhao Xu, Keqiang Yan, et al. Artificial intelligence for science in quantum, atomistic, and continuum systems. arXiv preprint arXiv:2307.084223 2023.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In Proceedings of the 8th International Conference on Learning Representations (ICLR). 2020.
Yilun Zheng, Sitao Luan, and Lihui Chen. What is missing in homophily? disentangling graph homophily for graph neural networks. arXiv preprint arXiv:2406.1888 18854, 2024.
Kaixiong Zhou, Xiao Huang. Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In Proceedings of the 34th Conference Advances in Neural Information Processing Systems (NeurIPS), 2020.
17

---

Published as a conference paper at ICLR 2026
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Proceedings of the 35th Conference on Advances in Neural Information Processing Systems (NeurIPS), 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), 2020.
18

---

Published as a conference paper at ICLR 2026
A
TABLE OF COMMON BELIEFS WITH REFERENCES
Table 2: List common beliefs together with a non-exhaustive list papers that make those claims.
Common Belief and references
OSM is the cause performance degradation.
[lamition
Wang
20206
Iaaaanzaeh
[lung
2020
Oversmoothing
2020 Zhoo & Alogiu
2020 Zhou et 2020
Wang & Leskoved
[02]
Zhou et 202]
Bodnar et al.
2022
Chen et
[Ewang et
1002
Rusch
2022
lortorelaa & Micheia
2022
Cai
2023
Maskey ct
2023
Neuven
2023
Kartadaar al.
2023
Rusch et
2023
nl din & Quacc
20.4 Wa
N0.30
Eaping ctal
204
lamalaadii
2014
Rith Ticbp
2014
Sumovic
Wing
M225
OSM a property of all DGNs.
Xu et
2018
Gasteiger at al.
2019 ct
2019
Chen al.
20200
Hamilton,
2020
Hasanzadeh et al. 2020 HHung et al.
2020 Zhao &
Akoglu 2020 Zhou et
2020
Aln Yahar
2021
Zhou al.
2021
Abbooo
2022
Arnazz Rodiiguez al.
2022 Chen al.
2022
[[wang al
Keriven
2022
Topping al
Rusch al
2022
Alknnhal
222
2010
Glowanm al
2023g Emiea
Nouyen
Qureshi
2024g b
Fewer Weber
2024
Jamadandi et
2024
Roth Liebig
2024
Armyy et
2025
Wang et
Homophily good, heterophily is bad.
Pci
2020
Zhon
2020
Lim
Lunn
Leskowee
Arnaiz-Rodiriuuzz
2022
Hemmophiy--Hetrrphee
Bochar
2022
2021
Goog
Roth
Liebup
2024
Zheng et
2024)
4. Long-range propagation is evaluated heterophilic graphs.
Arraiz-Rochigezz
Tomonolla Micheli
Akanshu
Black
2023
Maskey
Huang
2024
Giraldo
at.l.
2022
Attali
5. Different classes imply different features.
Abu-El-Haijj al, 2019 Pei
2020
Lim
2021
Loan etal, 2021 Ma
2022
Sun
2022
Luan
2022 Rusch
2023
2024a
Iuunn
Wang
2024
6. OSQ synonym of topological bottleneck.
Xu eu al.
2018 Amniz-Radriguez et al
2022 Banerjee er al.
2022 Chen
2022 Dene
2022
Sun
2022
Topping at.
2022
[osturelia Macholi 2022) Allaneha
2033 Balla
(Back
2023 Di Glovanni
2023g Lirrca
2025
Gareielsson
2023
2021g Nuuyen
2023
2023
Qureshi
atal. 2023
Anall et
2024g
(Barbero et al.
X01 Di Grovanni al. 2004 Pesser & Weber 2024
Hunng ct
Jamadandi et
2024
Smithern
Amryyo et al
XDX Ciravins al
MD23 Stanwic
Tom
Oversquashing
OSQ synonym computational bottleneck.
Yohay
Amaiz Rodrigues
Hanerjoe al.
Deac
2022 Hoppang et al.
3022 Toctorelia & Micheli
2022
Alkansha
2023
Halla
2023
Black et
2023
Dwivedi alal. 2022
Firic et
2025
Giraloo al. 2003
Goteedge
202
Mpayen elal
X03
Karlodkar ei
X02
Shato
203
Str
M02
bd dhm & Qureeci
2024
Albah 202
Burbero
2024
201
Southern al 2027
Arnyy
2025
Gravinu
2005
Staowic
2025
8. OSQ problematic for long-range tasks as well.
Alon & Yahay
2021
Abboud et
2022
Banajoe atal 2022 Chen ot al,
2022 Deae et al,
2002
Topping et 2022
Totorella Micheli
2039
Akansha
2023
Black [2023 Cl all 2023 Di Giovanni el
2023
Litiaa et al.
2025
Gabrillsso al. 302
Karhadkar
X0B
2023
2013 Burbero
Di
Glovanni
Weber 2024
Huang
Southera
Attal
Arroyo et
Gravina
Staovic
9. Topological bottlenecks associated with long long-range problems.
Tooping al.
2122
Tortorella & Micheli
2022
Akansha
2025
Black et al.
2023 Kartadkar
2023
Liu
2023a Shi et 2025
Fesser Weber
20024
19

---

Published as a conference paper at ICLR 2026
B BACKGROUND
B.1 DEEP GRAPH NETWORKS
We provide a brief excursus into Deep Graph Networks for readers new to the topic.
We can define a graph as a tuple 9 (Vg. Kg An)), with V. the set of nodes, E, the set of edges (oriented or not oriented) connecting pairs of nodes. Eg encodes the topological information of the graph and can be represented if there is an edge between u and v, and it is O otherwise. Additional node and edge features are represented by X2 Xy and auv Ag, respectively. Xg can be, for instance, R N
adjacency matrix: binary square matrix A where Aur is 1
The neighborhood of a node is the set of nodes that are connected to by an oriented edge, i.e., N₂ = {u Vul v) E }- J- If the graph undirected, we convert each non-oriented edge into two oriented but opposite ones.
The main mechanism of DGNs is the repeated aggregation of neighbors' information, which gives rise to the spreading of local information across the graph. The process is simple: i) at iteration &, each node receives "messages" (usually just node representations) from the neighbors and processes them into a single new message; ii) the message is used to update the representation of that node. Both steps involve learnable functions, so DGNs can learn to capture the relevant correlations in the graph.
Most DGNs implement synchronous message-passing mechanism, meaning each node always receives information from all neighbors every iteration step. This local and iterative processing is at the core of DGNs' efficiency since computation can be easily parallelized across nodes. In addition, being local means being independent of the graph's 's size. When one learns the same function for all message passing iterations, (2005); (Scaselll et al.] (2009); on the contrary, when one learns a separate parametrization for finite number iterations (also known as layers), we talk about convolutional architectures as the NN4G of Micheli & Sestito (2005); Micheli (2009).
talk about recurrent architectures, as the GNN Gori et al.
The neighborhood aggregation is usually implemented using permutation-invarian functions, which make learning possible on cyclic graphs that have no consistent topological ordering of their nodes. rather general and classical neighborhood aggregation mechanism for node layer/step + is the following:
=0 h = 02+1 (n', (ni, (1fo (b.) | u E N..))
4
where hτ is the node embedding of u at layer/step L, á and eb implement learnable functions, and is a permutation invariant aggregation function. Note that h X,- For instance, the Graph Convolutional Network of Kipf & Welling (2017) implements the following aggregation, which is special case of the above equation:
h h++1 (W Σ
aEN())
with É heing the normalized graph Laplacian, W is learnable weight matrix and a is non-linear activation function.
B.2 SOME OSM DEFINITIONS
In order to keep the paper self-contained and to illustrate the different ways OSM has been defined, we briefly review the most common definitions. The following subsection summarizes the most commonly used OSM metrics. Some of these metrics are used in the main text.
Let diag(dı,.... dn.) be the degree matrix with d, = Σ, Aun. The combinatorial graph Laplacian is defined as L = D A, with eigenvalues 0 \1 < Ag ... S An In addition. the (assuming d, > for all
symmetric normalized Laplacian, defined by L = I D A u), reduces the influence of node degrees through symmetric degree normalization. For undirected graphs with nonnegative weights, the eigenvalues É lie in the interval [0, 2]. Also, the multiplicity of eigenvalue 0 equals the number of connected components.
20

---

Published as a conference paper at ICLR 2026
The Dirichlet Energy (Chung 1997). used to measure OSM in Cai & Wang
2020
defined as
DE ( = Tr (H*)
LH
1
Σ
h
h.
(6)
2
Vd
de
(M,D)EE
Note that DE can also be computed using
DE(H') Tr (H²) LH
Σ (u.0)E
h.,
h
Other OSM metrics include those with respect to the norm of node embeddings. For instance, Rayleigh Quotient (RQ) (Chung. 1997p, which can be interpreted as DE normalized by embedding magnitude, is defined by
Tr (H)) LH
RQ =
(8)
H
Similarly, we can replace É with the normalized Laplacian L to obtain the Rayleigh Quotient with respect the normalized graph operator, denoted RQQ It was introduced for OSM analysis in Cai &
Wang (2020) and adopted by various subsequent works (Yang et al. 2020 Di Giovanni et al.) 2023b Roth & Liebig 2024, Maskey al., 2023). RQ captures whether embeddings become relatively
smoother, independent of magnitude.
Mean Absolute Deviation (Chen al. 2020a) averages cosine dissimilarity between node and its neighbors.
MAD - Σ
-
h
ueA
The smoothness metric SMV (Liu et al. 2020 pairs:
captures global node-distance average over all node
SMV n Σーー
Σ
h
h
(10)
h.,]]
VFEE
In the main text, we primarily consider DE and RQ. However, all notions convey the same intuition, loss of discriminative variation, yet, as we show, can disagree practice.
Convergence- rate results. Known theoretical bounds show DE(H**) decays exponentially with depth k. where the decay rate depends on weight spectra and graph eigenvalues (Oono Suzuki 2020 Huang et al. 2020). Such convergence rate results primarily make assumptions the architecture, weight matrix, and activation functions, and may be altered by skip connections, normalization layers, simple rescaling such as 2W (Roth & Liebig 2024).
For instance, Cai & Wang 2020) propose a bound on the DE of two consecutive message passing layers (similar bounds found in Oono & Suzuki (2020) and Zhou et al. (202T)
DE(H') S (1 - 2
max (E(
being s Smax the square of the maximum singular value of W and A2 the second smallest eigenvalue of the Laplacian, i.e., the spectral gap. The proof holds when s < 1/(11 X2).
In addition, Di Giovanni et al. (2023b) further relate Laplacian eigenvalues and weight spectra to explain whether RQ converges to 0 (collapse) or to Xmax (no collapse).
B.3 SOME OSQ DEFINITIONS
For completeness, we summarize some of the most commonly used metrics in the OSQ literature and their relationships. These quantities mainly measure three different aspects of the graph: (i) sensitiviiy/Jacobiann measures that capture how information from a distant node u affects a target node after K pessage-passsing layers; (ii) topological bottleneck proxies such Cheeger-type cut ratios, graph spectrum or curvature scores; and (iii distance- based quantities such as effective resistance that upper-hound information flow.
21

---

Published as a conference paper at ICLR 2026
B.3.1 SENSITIVITY
For K -layer GNN let ha denote the embedding of node at layer A first proxy for OSQ the Influence Score of Xu et al. 2018).
Oh
(u, v)
(11)
Th!
Black et (2023) sum these sensitivities over all unordered pairs,
2h
K
Σ
(12)
Th
VAVEE
to obtain a graph-level indicator of how much information is lost.
Di Giovanni et al. (2023a) propose symmetric Jacobian obstruction that removes self-influence and degree bias. They define the Jacobian obstruction of node v with respect to node u at layer m as
((m) (v, = de Oh.
The
(m)
+
ah.
(13)
(R) Va Thu
du (k)
Vd,d Oh.
being the extension to the Jacobian obstruction of node with respect to node after m layers defined as
m
ÕT (u, v)
Σ
J m (v. u)
(14)
B.3.2 TOPOLOGICAL BOTTLENECKS
Many OSQ papers measure topological (structural) bottlenecks using spectral or curvature quantities. Note that here we give an intuition based on the spectral metrics KAmaizz-Rdrignnn et al. 2022
2025 Karbadkar al. 2023 Banerjee et al. 2022). but significant part of the literature
metries
based on curvature (TTpppig et al. 2022 Liu et al. 2023a Giraldo et al. 2023
Nguyen et al. 2023).
First, the topological bottleneck be measured by Cheeger Constant (Chung 1997). which is the size of the min-cut of the graph.
Ke (u, v) : u S. E SH
hg
min
SCV
min(vol(S)) vol(S)}
small lG means one can separate G into large-volume parts by removing only few edges, i.., severe topological bottleneck. Cheeger's inequality links he to the spectrum of G:
h2
<
2hG:
2
where A is the second eigenvalue the normalized Laplacian.
B.3.3 PAIRWISE DISTANCES
The commute time between nodes (Lovász) 1993) is defined as the expected number steps that random walker needs to go from node to v and come back. The Effective Resistance between two nodes (Chandra al. 1989) Raes is the commute time divided by the volume of the graph (Klein Randič 1993), which is the sum of the degrees of all nodes in the graph. The effective resistance between two nodes is computed as
R = L Lt 2
being L = Ei>0 X O the pseudoinverse of L
Then, some measures derived from this metric can be connected with the topological bottle- neck (Chung 1997 Chandra al.] 1989 Qiu & Hancock (2007). For instance, the maximum effec- tive resistance of graph is connected with the Cheeger constant as per Rmax = max Rav
Rmax S h2
22

---

Published as a conference paper at ICLR 2026
and thus also bounded by the spectral gap
2
S Rmax S
nd2
A2
In addition, the total effective resistance Rio 1/2 1/2,,,EE Ruo is bounded to the spectral gap EI
lens al. 201T:
n(n -
Rus
22
A2
Note that the total effective resistance also equals the sum of the spectrum of L Run = n2 Σ2 1/>m
B.3.4 CONNECTING SENSITIVITY AND TOPOLOGICAL DISTANCES
The larger Total Effective Resistance (Rrot E(wpee Raw) is, the lower the sum of pairwise sensitivities (Black et al. 2023):
a (r)
Σ
S c(b Rest)
(15)
Oha
(0)
XVVVV
The larger the Effective Resistance is, the higher the Symmetric Jacobian Obstruction (Di Giovanni et al. 2023a):
ÔT (u, v)
(m) (v, (r, s Ru,"
(16)
B.4 COMPUTATIONAL BOTTLENECK
Oversquashing can also be seen through the perspective of the message-passing computational graph: each message-passing layer expands the set of nodes whose features can influence target node. If this receptive field grows fast, any fixed-width DGN "squash" many signals into a single vector.
Receptive Field Following Chen et al. (0188 and Alon & Yahav 2021) the receptive field was defined recursively as:
NCK = ACK (ww w E NG AuE AKK-1) and Nº = NN,
(17)
which can be also seen as the set of K-hop neighbors, i.e., nodes that are reachable from v within K hops The number of nodes in each node's receptive field grow exponentially with the number of layers | = O (exp(K)) (Chen et al. 2018 For instance, in a rooted binary tree each layer has b b² +....6 k O(bK).
exactly &tt new neighbors, so IN
When evaluating the actual computationnl graph resulting from message- passing, duplicates matter: a node that appears in several branches of the computation tree contributes multiple times, since each distinct walk contributes separate message. We therefore the multiset notation to define the computational tree for a node v in Eq. 3 reproduced here for convenience:
Computational Tree
M : No. M = M KK-1g R
+ uEM!
No.
(18)
Computational Bottleneck Therefore, we defined in Def. 4.1 the computational bottleneck of node the size of the computational tree, IM I. for given node v and number of message passing layers K.
The size of the computational bottleneck (multiset receptive field) at node v, be computed as:
K
M =
Σ
|4 311
Σ
(A (At).s
(19)
uEV
23

---

Published as a conference paper at ICLR 2026
This definition counts every distinct length-& walk from any node Equation equation 19 is exactly the row-sum the powers of the adjacency matrix; it therefore matches the size of the computational tree.
Note that the size of the set-based receptive field corresponds to the support of the multiset M denoted N₁K Mu Therefore, the multiset size [M is always greater than equal to the size of the support, IM, 2 |A since it accounts for path multiplicity.
In early deep-graph networks literature, Micheli 2009) introduced the idea by using the term "contextual window": deeper layers aggregate exponentially many paths unless skip connections or global pooling curb the growth. The multiset perspective in Eq. equation [9 makes this explosion explicit and the matrix computation directly links to matrix
interpretations of message passing.
Figure 6 visualises the difference between the set size | graph.
and the multiset size [M on toy
IM
N
N
Figure 6: Computational Bottleneck. Illustration of a receptive field defined with sets (K- hop neighborhood) and the definition of computational bottleneck measured as the size of the computational graph defined with multisets.
In conclusion, we note that in many distinct vertices are in the K K-hop neighborhood, but by the size of the computational graph.
the computational bottleneck is driven not by how
24

---

Published as a conference paper at ICLR 2026
C SENSITIVITY DECREASES ON A GRID GRAPH WITHOUT TOPOLOGICAL BOTTLENECKS
To show that low sensitivity does necessarily imply topological bottleneck, Figure 7 analyzes sensitivity's s decreasing trend when the number of message passing layers 7. increases on the grid graph of Figure 4 of size 10 10. Increasing the size of the embedding space postpones the collapse of the sensibility.
1750
12
Senvinvity
1000
750
300
250
Number of Message Passing Layurs
Figure 7: We plot the sensitivity of the grid graph of Figure for the Graph Convolutional Network (Kipf & Welling 2017) model for different node embedding sizes.
25

---

Published as a conference paper at ICLR 2026
D OVERSMOOTHING DOES NOT ALWAYS HAPPEN
For enhanced clarity and to allow for a more detailed examination of the OSM behavior discussed in
Section larger version of Figure is provided in Figure g
Dirichlet Energy
DE and Norm
1028
Norm
DE and Norm
10
10
10a5
10"
10.8
10-14
GCN
GAT
10
SAGE
GTN
104
3
5
10
19
35
64
3
10
19
35
64
(a) W: DE and Norm
(b) 2W: DE and Norm
10
10
RQ
10-1
RQ
10-
10-3
GCN * GAT
SAGE
GIN
10
35
64
10
19
35
(c) W: RQ
(d) 2W: RQ
Figure 8: Larger version Figure (a-b): We depict the evolution, with increasing number of layers, of the DE and the feature norm [X]],, using W and 2W feature transformations for different architectures. (c-d): Evolution of the RQ for W and 2W as before. Experiments run on the Cora dataset for 50 random seeds.
26

---

Published as a conference paper at ICLR 2026
E ALTERNATIVE VIEWS
One may argue that the common beliefs of Table [ be regarded as alternative views, which we have abundantly discussed and challenged in previous sections. However, we additionally discuss other alternative viewpoints.
One is put forward by Blayney al. 2025. which states that the oversquashing term is still useful to describe issues arising from topological bottlenecks and the depth in the computational tree. The authors argue that all performance issues related to "oversquashing" are caused by either model capacity or low sensitivity, and we do not intend to contest their observations in this space. Their alternative position on the use of the "oversquashing" term likely stems from an in-depth understanding of the distinction between topological and computational bottlenecks as well as the underlying assumptions, which, as this paper shows, cannot applied to the whole community yet. As matter of fact, proposal is pedagogical rather than practical: Section 4 does not propose how to identify specific problems (e.g. capacity or sensitivity), but how to better think about and approach them without confusing everything under single umbrella term. For this reason, believe that clear separation of concepts, rather than the use of the term "oversquashing" can have a profound impact the whole community in formulating
precise research questions.
Another alternative view is the recent one of Mishayev et al. (2025), which proposes, similarly to Blayney al. (2025) a problem-oriented dichotomy for the "oversquashing" phenomenon. They argue for the decoupling of this term into computational bottlenecks, which can happen in short-range tasks, and vanishing gradients, which seem be more related to long-range dependencies. However, because computational bottlenecks can appear in long-range tasks as well as vanishing gradients, we believe this work focuses more on identifying practical problems address rather than providing conceptual separation of concepts related to oversquashing. One evidence for this is that the synthetic tasks used in the paper, namely two-radius and ring transfer, contain a topological bottleneck that may have been important reaching some conclusions, Hence, our goal is complementary to that of Mishayev et al. (2025).
Finally, we mention the position Kormann et al. (2026). The authors highlight that improvements in over-smoothing metrics and model performance are, at best, weakly correlated. The hypothesis they investigate that most real tasks rely short-range dependencies. In addition, they question the focus on curvature in OSQ contributions and call for a more principled understanding supported by appropriate statistics. The authors' views and empirical observations are therefore complementary to ours.
27


Reviews:
[{"review_id": "qWJkImQI1k", "reviewer": "Reviewer_348B", "summary": "This paper revisits and critiques nine widely discussed beliefs in the field of Graph Machine Learning (GML), covering issues such as over-smoothing (OSM), over-squashing (OSQ), homophily/heterophily, and long-range dependency. Through a series of counterexamples, the authors reveal common misconceptions, for instance, that over-smoothing is not inevitable; it depends on model architecture, hyperparameters, and evaluation metrics, and bears no direct causal relation to performance. The paper aims to clarify these misunderstandings and calls for a more rigorous research in graph learning.", "questions": "Please see the weakness.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 3, "strengths": "1. The paper’s central motivation—to critically examine and challenge long-held opinions and assumptions in the GML community—is very interesting and valuable.\n\n2. The writing is clear and well-structured, using intuitive examples and accessible language to convey complex ideas effectively.", "weaknesses": "1. Lack of justification for the representativeness of rebutted claims. The paper does not convincingly establish whether the criticized viewpoints truly represent mainstream consensus in the field. For instance, is the claim that “all GNNs inevitably suffer from over-smoothing” genuinely a widely accepted belief, or is it only mentioned in a limited subset of works? To make the critique compelling, the authors should first demonstrate the prevalence and influence of these viewpoints in prior literature.\n\n2. Insufficient theoretical and empirical validation. The arguments rely heavily on qualitative reasoning and illustrative examples, with very limited mathematical formalism or empirical validation. I am not convinced. To strengthen credibility, the paper should incorporate formal theoretical derivations, quantitative experiments, or counterfactual analyses that can substantiate its claims.\n\n3. The manuscript attempts to address too many issues simultaneously, resulting in a lack of depth and weakened persuasiveness. I strongly recommend focusing on one or two truly dominant misconceptions and providing a rigorous, well-supported, and empirically validated analysis of these specific points. For example, the classic paper “Adversarial examples are not bugs, they are features” offers a good example: it concentrates on a single misconception and dismantles it thoroughly through both theoretical modeling and empirical evidence.\n\n4. Several arguments (e.g., regarding differences between homophilic and heterophilic graphs) have already been discussed—explicitly or implicitly—in prior works. For example, the development of heterogeneous graph neural networks (HGNNs) stems from recognizing that aggregation mechanisms in homophilic graphs are inadequate for heterophilic structures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HUCqYzyxzW", "reviewer": "Reviewer_4Aqk", "summary": "The paper analyzes nine common beliefs in Deep Graph Networks concerning issues such as over-smoothing, over-squashing, homophily/heterophily, and long-range tasks. It systematically elucidates their origins, identifies misconceptions through experimental validation and counterexamples, and aims to correct erroneous understandings, thereby contributing to the advancement of the graph learning field.", "questions": "Q1. The paper suggests that research should focus on node separability rather than OSM metrics. Could you provide a novel, quantifiable \"node separability metric\" as an alternative?\n\nQ2. Refining the tasks of distinguishing \"computational bottlenecks\" from \"topological bottlenecks\" is meaningful. I hope the authors can further discuss whether there are actual examples of such distinctions in real-world graph data, whether these distinctions are feasible, and how to differentiate them: is it possible to propose theoretically distinguishable metrics?\n\nQ3. Do the conclusions drawn in the paper remain valid in the context of Transformer-based GNNs or Graph Diffusion Models?\n\nQ4. The paper highlights that certain common misconceptions lack universality. Could the authors further elaborate on the scope of applicability for traditional beliefs? For example, in Section 3.1, the counterexample \"if a node is at a distance greater than five from a specific node\" relates solely to the topological properties of the graph, independent of homophily or heterophily. Under what circumstances is it meaningful to discuss homophily and heterophily?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The article systematically examines prevalent misconceptions and imprecise definitions within the field of DGN. It offers a reflective analysis aimed at clarifying commonly misunderstood concepts such as over-smoothing and over-squeezing, thereby facilitating researchers' comprehension and preventing misinterpretations. This critical review encourages ongoing reflection on entrenched perspectives, fostering a more rigorous and accurate understanding in the domain.\n\nS2. The paper refines the understanding of the \"over-squashing\" problem, elucidating the relationships among over-smoothing, over-squashing, homophily/heterophily, and long-range tasks. By redefining these issues and their key aspects, the discussion aims to promote advancements in the development of DGN methodologies.", "weaknesses": "W1. In refuting the claim that OSM is a property of all DGNs, the article relies solely on a simple experiment, which lacks rigorous proof and suffers from limited experimental evidence. The experiment, on one hand, uses only the Cora dataset, thereby failing to establish the universality of the conclusion; on the other hand, certain inferences merely suggest that the DE and RQ metrics, which reflect smoothing, are insufficiently convincing, yet they do not demonstrate that OSM is inevitably unavoidable. It is recommended that the authors provide more rigorous theoretical justification or more comprehensive experimental evidence when discussing the underlying causes of OSM.\n\nW2. The definitions of \"computational bottleneck\" and \"topological bottleneck\" rely primarily on intuitive explanations, lacking a unified mathematical framework or quantifiable metrics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "quvvl2vARf", "reviewer": "Reviewer_xBYT", "summary": "The submission under review argues that several “folklore beliefs” in graph ML — oversmoothing, oversquashing, homophily vs heterophily, long-range reasoning — are overstated or misinterpreted. It provides counterexamples, simple constructions, and some empirical plots (e.g., 1–64 layer GNNs on Cora with different scalings). \n\n12154_Oversmoothing_Oversquash\n\n The paper also proposes to retire the overloaded word “oversquashing” and instead talk about “computational bottlenecks” vs “topological bottlenecks,” which it claims are distinct.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper openly challenges sloppy community narratives about depth, heterophily, and “oversquashing,” and reminds readers that degradation in deep GNNs is not the same thing as classic oversmoothing, and that heterophily alone does not doom GNNs. \n2. The paper proposes to split “oversquashing” into two ideas: “computational bottlenecks” (information from exponentially many nodes being crammed into a fixed hidden vector); “topological bottlenecks” (structural choke points / narrow cuts in the graph).", "weaknesses": "1. The primary claims of this paper overlap significantly with established findings in the GNN literature.\n* On Over-smoothing: The observation that removing feature transformations and non-linearities can boost performance in moderately deep GNNs has been demonstrated by prior work, such as SGC [1] and a KDD'22 paper [2]. These studies have already established that performance degradation in models of the depth used in this paper (e.g., 64 layers) is often attributable to feature transformation and non-linearity, rather than over-smoothing alone, which typically manifests in much deeper architectures.\n* On Heterophily: The challenges of heterophily have been extensively analyzed. A well-known paper [3] provides a comprehensive treatment of this topic. Unfortunately, the current work does not seem to offer new perspectives or insights beyond what was presented in [3].\n------\n2. Given that the paper addresses topics with a rich history of research, a deeper investigation from novel perspectives or a rigorous theoretical analysis would be expected. However, the current analysis lacks the necessary depth.\n* The investigation into over-smoothing is confined to a few simple settings on a single dataset (Cora). This limited experimental setup is not convincing enough to reveal generalizable patterns or provide robust evidence for the claims made.\n* The discussion on heterophily relies on reusing a toy example from [3] without introducing new conceptual or empirical contributions. A more compelling argument would require novel experiments or theoretical formulations.\n\n------\n3. About the statement ‘if different classes imply different feature distributions, why would one need a DGN rather than a simple MLP?’\n\nI also disagree with the way that’s phrased in the submission.\nEven if different classes have different feature distributions, classification boundaries may still be ambiguous (e.g., overlapping Gaussians, noisy features, etc.). A plain MLP on node features alone may misclassify nodes in that overlapping region.\nA message-passing layer can still add value by smoothing / denoising via neighbors: even if node i’s own features are ambiguous, aggregating its neighbors’ features can push it toward the correct side of the decision boundary. This is exactly the classic semi-supervised “feature smoothing” or “label propagation” intuition behind GCNs.\n\nSo “why would you ever need a GNN if features are already somewhat class-dependent?” is a false dichotomy. You still may want graph convolution to regularize local decision boundaries and reduce local noise — especially when each node alone is borderline but its neighborhood is consistent.\n\n----\n4. Difference between “computational bottleneck” and “topological bottleneck” is unclear. As a core concept to support your claims, it is not wise to put it to appendix. The main text should be self-contained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1VZbdOIKrl", "reviewer": "Reviewer_SstW", "summary": "This paper clarifies recent concepts in the graph machine learning community, such as oversmoothing and heterophily, and raises simple but noteworthy counterexamples.", "questions": "1. Could you provide real-world examples of interactions between features, structure, and class labels?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well motivated as a position paper, covering a wide range of recent trends in graph machine learning.\n2. The paper is well structured, clarifying the nine beliefs step by step.", "weaknesses": "1. Section 3.1: The example is too specific—showing a heterophilic graph where a DGN can achieve perfect classification. Most examples in this paper are toy problems that can be solved by simple graph functions (degree, distance). These problems don't require DGNs.\n2. Some explanations are insufficient. For example, in Section 3.3, the authors argue that distinguishing the task is what really matters. However, there's no further analysis of which graph tasks should consider heterophily/homophily or distance. The argument relies on only two specific examples (degree, distance). As a position paper that may direct the future of this area, a deeper dive into this question is necessary.\n3. Line 358: Is it correct to refer to Figure 2? Also, please explain **message filtering** in Errica et al. (2025) and Figure 4 (middle) more clearly, as readers may not be familiar with it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)