Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning

1 INTRODUCTION

• Message passing's limitations matter across graphs and tasks, but rapid research can promote positive findings while overlooking contradictory evidence.The introduction names oversmoothing, oversquashing, topological bottlenecks, heterophily, and long-range information propagation.Source: §1 · p. 1
• The authors argue that these beliefs can create ambiguity and misunderstandings, making precise research questions harder to address.They say failure to acknowledge inconsistencies may spread questionable claims.Source: §1 · p. 2
• The paper identifies and groups nine common beliefs, then uses simple counterexamples to demystify them and separate distinct research questions.Its stated aim is to encourage critical thinking and foster further advances in graph machine learning.Source: §1 · p. 2
• The referenced works are not an exhaustive survey; the list mainly supports the paper's arguments.The authors state that their goal is not to pinpoint criticalities in previous works.Source: §1 · p. 2
• The paper organizes beliefs about oversmoothing, oversquashing, and homophily–heterophily, then discusses each with counterexamples and take-home messages.Table 1 summarizes the beliefs and papers where the authors found mentions of them.Source: §1 · p. 2, Table 1 · p. 2

2 IS OVERSMOOTHING A REAL ISSUE?

• OSM describes increasing embedding similarity with depth, but commonly used deviation and subspace-collapse metrics capture related intuitions rather than a single definition.The section frames its definition through a similarity or separation function on layer embeddings.Source: §2 · pp. 2–3

2.1 BELIEF: OSM IS A PROPERTY OF ALL DGNS.

• Whether embeddings collapse depends on training and architecture: frozen-weight studies can hide learning effects, and no proof establishes inevitable collapse under realistic training regimes.Cong et al. (2021, Figure 2) report OSM only for frozen-weight networks; adapting parameters preserves informative variance.Source: §2.1 · p. 3
• DE and RQ often disagree, small feature-transform rescaling can reverse trends, and some architectures do not collapse, so OSM is neither universal nor straightforward to diagnose.For GCN, DE collapses with vanilla aggregation but grows after rescaling while RQ stays essentially flat; GAT and SAGE show RQ decay.Source: §2.1 · pp. 3–4, Figure 1 · p. 4

2.2 BELIEF: OSM IS THE CAUSE OF PERFORMANCE DEGRADATION.

• Avoiding collapse need not improve generalization, and scaling embeddings can change DE without changing accuracy or separability.The section also notes that deep models can lose accuracy through other problems, including vanishing gradients and over-fitting.Source: §2.2 · pp. 4–5
• Embedding collapse does not by itself determine accuracy: label-correlated subspaces can preserve class separation, and within-class distances may shrink faster than between-class distances.Keriven (2022) describes faster collapse in some subspaces; Cong et al. (2021) discuss improved class separability despite global collapse.Source: §2.2 · pp. 4–5
• The paper recommends focusing on node-embedding separability and not attributing performance drops to OSM by default.Separability with respect to labels and its evolution during intermediate smoothing are identified as important considerations.Source: §2.2 · pp. 4–5

3 HOMOPHILY-HETEROPHILY AND THE ROLE OF THE TASK

• In node classification, homophily and heterophily describe neighbor similarity or dissimilarity, measured by labels, features, or both.The literature usually measures class labels, often implicitly.Source: §3 · p. 5

3.1 BELIEF: HOMOPHILY IS GOOD, HETEROPHILY IS BAD

• A one-layer sum-based graph convolution can perfectly classify a fully class-heterophilic bipartite graph via incoming degree, while a highly class-homophilic distance task may require information beyond nearby nodes.The distance task labels nodes by whether they are more than five steps from a specified node.Source: §3.1 · pp. 5–6, Figure 2 · p. 5

3.2 BELIEF: DIFFERENT CLASSES IMPLY DIFFERENT FEATURES

• If different classes have different feature distributions, class homophily implies feature homophily; under that assumption, a simple MLP may suffice unless the task depends on topology.The paper therefore motivates scenarios with overlapping class-feature distributions and topology that matters to the task.Source: §3.2 · p. 6

3.3 BELIEF: LONG-RANGE PROPAGATION IS EVALUATED ON HETEROPHILIC GRAPHS

• Long-range tasks need not be heterophilic, so assess propagation needs separately from the class labels induced by a task and consider feature, structure, and label interplay.The paper advises against generic claims linking homophily or heterophily to long-range problems.Source: §3.3 · p. 6

4 THE MANY FACETS OF “OVERSQUASHING” AND THEIR NEGATIVE IMPLICATIONS

• Computational bottlenecks belong to the message-passing architecture, whereas topological bottlenecks belong to graph connectivity; the paper argues they should be treated as distinct concepts.The computational bottleneck concerns the message-passing computational tree, where repeated walks can make multiple messages contribute even when they originate at duplicate nodes.Source: §4 · p. 7

4.1 BELIEF: OVERSQUASHING AS SYNONYM OF TOPOLOGICAL BOTTLENECK

• A grid graph can lack topological bottlenecks yet develop computational bottlenecks and low sensitivity as message-passing depth increases.Thus, low sensitivity does not by itself establish the presence of a topological bottleneck.Source: §4.1 · pp. 8–9, Figure 4 · p. 8

4.2 BELIEF: OVERSQUASHING AS SYNONYM OF COMPUTATIONAL BOTTLENECK

• Pruning the computational tree can interrupt communication between distant nodes when a graph has a topological bottleneck but only a mild computational bottleneck.The two bottlenecks therefore require separate consideration rather than assuming that reducing one always helps.Source: §4.2 · p. 9

4.3 BELIEF: OVERSQUASHING IS PROBLEMATIC FOR LONG-RANGE TASKS AS WELL

• Long-range tasks require classical message passing to use enough layers to span node distance, but high-degree hubs can create computational bottlenecks after one layer.Computational bottlenecks can therefore occur in short-range as well as long-range tasks.Source: §4.3 · p. 9, Figure 5 · p. 9

4.4 BELIEF: TOPOLOGICAL BOTTLENECKS ASSOCIATED WITH LONG-RANGE PROBLEMS

• Topological bottlenecks matter for long-range communication only when they lie on task-relevant paths, while computational bottlenecks can impede it without a topological bottleneck.Adding edges or nodes to reduce distances can also worsen the computational bottleneck by adding branches to the computational tree; solving a topological bottleneck is neither necessary nor sufficient to solve all long-range problems.Source: §4.4 · p. 10

5 CONCLUSIONS

• The paper argues that oversmoothing may not be an actual problem, and that embedding separability is a better place to look for performance degradation.It also argues that computational and topological bottlenecks clarify inconsistencies associated with the term “oversquashing,” while task context matters for claims about homophily, heterophily, and long-range dependencies.Source: §5 · p. 10

A TABLE OF COMMON BELIEFS WITH REFERENCES

• Table 2 lists common beliefs alongside a non-exhaustive list of papers that make those claims.Source: Table 2 · p. 19

B.1 DEEP GRAPH NETWORKS

• DGNs repeatedly process neighbors’ messages into a new message and use it to update each node’s representation.The message-processing and update steps use learnable functions to capture relevant graph correlations.Source: §B.1 · p. 20
• Synchronous message passing gives every node information from all neighbors at each iteration, enabling parallel computation independent of graph size.Source: §B.1 · p. 20
• Recurrent architectures reuse one learned function across iterations, whereas convolutional architectures learn separate parameters for a finite number of layers.Source: §B.1 · p. 20
• Permutation-invariant neighborhood aggregation supports learning on cyclic graphs without a consistent node ordering.The general mechanism uses learnable functions and a permutation-invariant aggregator; GCN is presented as a special case.Source: §B.1 · p. 20

B.2 SOME OSM DEFINITIONS

• The normalized Laplacian reduces node-degree influence through symmetric degree normalization; for undirected graphs with nonnegative weights, its eigenvalues lie in [0, 2].Source: §B.2 · p. 20
• Rayleigh Quotient can be interpreted as Dirichlet Energy normalized by embedding magnitude and measures relative smoothing independent of magnitude.Source: §B.2 · p. 21
• Other oversmoothing metrics capture neighbor cosine dissimilarity or average node-pair distance, while oversquashing measures cover sensitivity, topological proxies, and distance-based quantities.Source: §B.2 · p. 21
• Dirichlet Energy and Rayleigh Quotient are used in the main text, but oversmoothing metrics that share the intuition of lost discriminative variation can disagree in practice.Source: §B.2 · p. 21
• Known bounds show Dirichlet Energy decays exponentially with depth, with rate depending on weight spectra and graph eigenvalues.These results make assumptions on architecture, weights, and activation functions, and may change with skip connections, normalization, or rescaling such as 2W.Source: §B.2 · p. 21

B.3 SOME OSQ DEFINITIONS

• Oversquashing measures include node-to-node sensitivity, topological bottleneck proxies, and distance-based quantities that upper-bound information flow.Source: §B.3 · p. 21

B.3.1 SENSITIVITY

• Influence Score is introduced as a first oversquashing proxy, while summed pairwise sensitivities provide a graph-level indicator of information loss.Source: §B.3.1 · p. 22

B.3.2 TOPOLOGICAL BOTTLENECKS

• The Cheeger Constant is the graph’s minimum-cut size; a small value means two large-volume parts can be separated by removing few edges.Cheeger’s inequality links this quantity to the normalized Laplacian’s second eigenvalue, λ2.Source: §B.3.2 · p. 22

B.3.3 PAIRWISE DISTANCES

• Effective resistance is commute time divided by graph volume, and is computed using the pseudoinverse of the Laplacian.Source: §B.3.3 · p. 22
• Maximum effective resistance is connected to the Cheeger Constant and bounded by the spectral gap; total effective resistance also equals a sum over the spectrum of L+.Source: §B.3.3 · pp. 22–23

B.3.4 CONNECTING SENSITIVITY AND TOPOLOGICAL DISTANCES

• Lower effective resistance is associated with lower summed pairwise sensitivities, while higher resistance corresponds to higher symmetric Jacobian obstruction.Source: §B.3.4 · p. 23

• A set-based receptive field consists of K-hop neighbors and can grow exponentially with the number of layers.A rooted b-ary tree has 1 + b + b^2 + … + b^(K−1) distinct neighbors within K layers.Source: §B.4 · p. 23
• The computational tree counts each distinct walk separately because each walk contributes a message, so repeated appearances of a node count multiple times.Source: §B.4 · p. 23
• The computational bottleneck of a node is defined as the size of its computational tree for a given number of message-passing layers.Source: §B.4 · pp. 23–24
• The multiset definition counts all length-ℓ walks and matches the computational-tree size through row sums of adjacency-matrix powers.Earlier work called the expanding aggregate a “contextual window”; skip connections or global pooling can curb its growth.Source: §B.4 · p. 24
• The multiset receptive-field size counts path multiplicity and is therefore at least as large as the set-based field’s support.Source: §B.4 · p. 24

C SENSITIVITY DECREASES ON A GRID GRAPH WITHOUT TOPOLOGICAL BOTTLENECKS

• On a 10 × 10 grid, sensitivity decreases as message-passing depth increases, while larger embeddings postpone sensitivity collapse.Source: C SENSITIVITY DECREASES ON A GRID… · p. 25, Figure 7 · p. 25

D OVERSMOOTHING DOES NOT ALWAYS HAPPEN

• Figure 8 tracks Dirichlet Energy, feature norm, and Rayleigh Coefficient across layers for W and 2W transformations and different architectures on Cora over 50 seeds.Source: Figure 8 · p. 26, D OVERSMOOTHING DOES NOT ALWAYS HAPPEN · p. 26

E ALTERNATIVE VIEWS

• Blayney et al. (2025) retain “oversquashing” for topological bottlenecks and computational-tree depth, while this paper frames separating concepts as pedagogical rather than a practical diagnostic.Source: E ALTERNATIVE VIEWS · p. 27
• Mishayev et al. (2025) separate computational bottlenecks from vanishing gradients, but the paper notes both can occur in long-range tasks and their synthetic tasks include topological bottlenecks.The paper describes its conceptual-separation goal as complementary to theirs.Source: E ALTERNATIVE VIEWS · p. 27
• Kormann et al. (2026) report at most weak correlation between oversmoothing metrics and performance, hypothesize most real tasks rely on short-range dependencies, and question curvature’s emphasis.Source: E ALTERNATIVE VIEWS · p. 27