Video summary

Oversmoothing, “Oversquashing”, Heterophily, Long-Range, and more

Main summary

Key takeaways

Educational

Main ideas / lessons conveyed

1) Motivation and purpose of the paper

  • The work originated as a position paper after the authors noticed that key concepts in graph machine learning (notably over-smoothing, over-squashing, and related long-range issues) often had:
    • unclear definitions
    • implicit assumptions
    • formalizations that caused confusion in the community
  • The authors aim to foster critical thinking, clarify definitions, and encourage new questions rather than criticize prior work.
  • They identify nine “common beliefs”, grouped into three blocks:
    1. beliefs about over-smoothing
    2. beliefs about over-squashing
    3. beliefs about (hetero)homophily

2) Over-smoothing: whether it always happens, and whether it always hurts

  • Intuition / definition:
    • Over-smoothing is the collapse of node embeddings into a non-meaningful subspace (or even a constant) as the number of message-passing layers increases.
    • In the limit of many layers, an embedding similarity metric tends toward constancy.
    • The intuition is linked to diffusion processes (e.g., random walks / heat kernel) reaching a steady distribution.
  • Methodological note: metrics matter
    • Different papers use different similarity metrics to measure over-smoothing, including:
      • Dirichlet energy and normalized variants (e.g., Rayleigh quotient / “Ritz quotient” as mentioned)
    • Because metrics differ, conclusions can differ.

Belief 1 (challenged): “Over-smoothing always happens”

Examples / counterpoints discussed:

  • Metric/architecture dependence
    • A counterexample: changing feature scaling (e.g., multiplying feature norms by 2) can alter behavior under a Dirichlet-energy-based definition—i.e., no collapse may occur for certain architectures.
  • Feature normalization / related critiques
    • Some works argue that observed effects depend on components like feature normalization.
  • Frozen-weight vs. learned-weight settings
    • Some analyses assume frozen weight networks, which may change observed outcomes.
  • Architectural dependence of asymptotics
    • A cited line of work (mentioned as “Giovani” / “Jeovani”) suggests that depending on the architecture, a coefficient can converge to either:
      • 0 (leading to over-smoothing), or
      • a maximum-frequency term (avoiding collapse).
  • Toy aggregation counterexample
    • Changing aggregation from mean to sum can produce behavior where (under the chosen metric) the quantity may explode rather than collapse.
  • Metric choice changes the story
    • Using Rayleigh quotient instead of Dirichlet energy can yield different outcomes.

Belief 2 (challenged): “Over-smoothing always degrades performance”

Core argument:

  • Embedding collapse does not necessarily correlate with worse accuracy.

Evidence types described:

  • In some settings (e.g., mean aggregation), Dirichlet energy reduction may correlate with accuracy.
  • Other aggregations can cause:
    • Dirichlet energy to explode
    • while accuracy remains low
    • (so “collapse/over-smoothing” is not the only driver).
  • Some works report:
    • models with no Dirichlet-energy collapse can still have bad accuracy
    • and conversely, “over-smoothing” might not prevent good performance.

Additional nuance:

  • Beneficial over-smoothing: Over-smoothing may initially help by aligning information from different communities, improving class separation early. Eventually, true collapse can become harmful.
  • Suggested research direction:
    • Move beyond global collapse; analyze class separability:
      • whether node embeddings for different classes remain distinguishable
      • and how this interacts with labels and performance.

Confounding factors:

  • Over-smoothing is often tied to increasing the number of message passing layers, but other issues can co-occur and confound attribution, such as:
    • vanishing gradients
    • overfitting
    • feature over-correlation
  • This makes it harder to isolate over-smoothing’s effect alone.

3) Over-squashing: definitions, measurement, and relation to long-range tasks

A major theme: over-squashing is currently ambiguous.

Background and terminology origin (as described)

  • The term is traced to earlier work (around 2021) with “exponential squashing of information” through bottlenecks.
  • Later influential works include over-squashing/bottlenecks via graph curvature, with a curvature-based metric.

Key distinction: two different bottleneck types

The authors argue that “bottlenecks” are not the same in all papers:

  1. Topological bottleneck

    • arises from graph structure
    • often measured via sensitivity:
      • sensitivity = norm of the Jacobian mapping how a representation at layer k changes when another node’s representation is perturbed (e.g., node v at initialization / layer 0).

  2. Computational bottleneck

    • arises from the computation graph / message-passing tree induced for a target node
    • measured by the size of the computational graph:
      • messages can include multiple copies of the same nodes (due to unfolding across layers)
      • more copies / larger computational graph ⇒ more information must be compressed into a single embedding.

Belief 1 (challenged): “Over-squashing ≈ topological bottleneck (sensitivity captures it)”

  • Examples are provided to show sensitivity can be misleading:
    • In one graph (two communities connected via a shared node), there appears to be a topological bottleneck, but the computational bottleneck is mild.
    • In a grid-like graph, computational bottleneck can be worse even without an evident topological bottleneck.
  • Additionally, sensitivity can decrease with depth in both cases—so low sensitivity does not reliably imply absence of topological bottlenecks.

Belief 2 (challenged / reframed): “Over-squashing = computational bottleneck”

  • The authors treat over-squashing as a computational bottleneck in that sense.
  • Mitigation idea (from the computational bottleneck perspective):
    • Prune messages / paths in the induced computational graph to reduce compression into the target embedding.
  • Tradeoff caution:
    • Pruning may separate communities and prevent long-range information flow, harming tasks requiring connectivity.

Relationship between over-squashing and rewiring

  • The two bottlenecks respond differently to changes:
    • Rewiring can improve topological reachability.
    • From the computational bottleneck view, adding edges can increase the number of messages, potentially worsening the computational bottleneck.

Over-squashing vs long-range tasks

  • Common claim: over-squashing is especially problematic for long-range tasks.
  • Counter-clarification:
    • If over-squashing is interpreted as a computational bottleneck, it can occur in short-range tasks as well, not only long-range ones.
    • Long-range tasks often require more message passing layers, which tends to increase computational bottlenecks.
  • Topological bottlenecks and long-range prediction:
    • Authors caution against assuming topological bottlenecks are inherently critical for long-range prediction.
    • A topological bottleneck might not matter if alternative structural paths still allow solving the task.
    • Rewiring intended to remove topological bottlenecks could hurt performance if it forces different traversal paths than the task needs.
  • Interplay:
    • Topological bottlenecks can worsen computational bottlenecks “inside” the computational bottleneck, making the problem more severe.

4) Homophily vs heterophily: challenging simplistic beliefs

They end with (hetero)homophily, arguing literature contains common but misleading assumptions.

Definitions (as stated)

  • Homophily: connected nodes tend to be similar in terms of:
    • features, or
    • labels
  • Heterophily: that similarity pattern does not hold.

Belief 1 (challenged): “Homophily is good and heterophily is bad”

  • The authors argue this often appears in paper introductions but can be invalid depending on the task.
  • Key reasoning:
    • Message passing has an inductive bias to use local neighborhoods, which seems suited to homophilic settings—but success depends on what the task requires.
  • Examples described:
    • A fully homophilic graph can have tasks where neighbors are not needed (e.g., a long-range rule), so message passing may not help.
    • A fully heterophilic graph can have tasks solvable with one message passing layer.
  • Emphasis: the task induces effective homophily/heterophily patterns; graph properties and task requirements interact.

Belief 2 (challenged): “Long-range interactions on heterophilic graphs are hard for message passing”

  • Some benchmarks on heterophilic datasets show message passing underperforming MLPs, but the authors claim counterexamples exist where heterophilic graphs are still easily solved by message passing.

Subtle underlying assumption they question

  • Often papers assume:
    • different classes correspond to different node features
    • and those features are sufficiently separable
  • If features are already separable, then a simple MLP may be enough—so why use message passing?
  • They connect this to over-smoothing: what matters is not just collapse, but how well embeddings remain separable.

Takeaway / proposed direction

  • Study the interplay among:
    • the task
    • the graph structure
    • and the node features
  • Progress may require:
    • analyzing message passing in simplified toy settings
    • making strong assumptions explicit
  • Final message: embrace critical thinking
    • re-check the assumptions behind conclusions in existing papers
    • don’t rely on overly generic claims

Methodology / instruction-like content (as presented)

Paper structure / presentation plan

  • Provide motivation for the paper’s goals (definition clarity + critical thinking).
  • Cover three problem areas in order:
    1. Over-smoothing (define intuition + challenge “always” claims)
    2. Over-squashing (argue ambiguity; distinguish bottleneck types; relate to long-range)
    3. (Hetero)homophily (challenge “homophily good/heterophily bad”; emphasize task-induced patterns)

Recommended analysis focus (explicit suggestion)

  • For over-smoothing research:
    • prioritize analyzing class separability of node embeddings
    • and how it interacts with labels and performance, rather than embedding collapse alone.

Recommended conceptual framing (implicit instruction)

  • When discussing over-squashing, explicitly state whether you mean:
    • topological bottleneck (sensitivity/Jacobian-based) and/or
    • computational bottleneck (size of message-passing computational graph / message copies).

Speakers / sources featured

Speakers (featured in the video)

  • Fabric (host/moderator; thanks the panel and introduces the talk)
  • Adrian (presenter; leads the over-smoothing section)
  • Federico (presenter; leads the over-squashing + long-range discussion)

External sources / prior work mentioned

  • Over-squashing term origin / related 2021 work (authors named indirectly as “Urian and Yahav Erin Yahav”—exact names likely correspond to well-known figures in the field)
  • Topping & colleagues: work on “Understanding over-squashing and bottlenecks on graphs via curvature”
  • “Giovani” / “Jeovani” line of work discussing convergence behavior of an RA-type coefficient depending on architecture
  • A referenced tutorial (Adrian mentions making a tutorial with “Binger” in ICML—exact bibliographic details not provided)
  • Mentions of additional over-smoothing analyses involving:
    • activation functions
    • architectures
    • feature normalization
    • frozen weight networks
  • Specific dataset/benchmark mentioned:
    • Squirrel and TATs (likely common heterophilic graph benchmarks; subtitle text is unclear)

Original video