Over-Smoothing and Over-Squashing

Graph networks are shallow. Two to four layers is typical, and stacking more usually makes performance worse, which is the opposite of the pattern in every other deep architecture. Two separate mechanisms are responsible, they are frequently conflated, and they call for opposite responses.

Over-smoothing

Each message-passing layer averages a node's representation with its neighbours'. Repeated, this is a diffusion process, and diffusion converges: after enough steps every node in a connected component has essentially the same representation, determined by global graph properties rather than by anything local.

The consequence is that node-level tasks become impossible, because the network can no longer tell nodes apart. It is detectable directly by measuring the pairwise distance between node representations across layers, which contracts toward zero.

The responses are the familiar ones from deep learning plus graph-specific ones: residual connections so the original representation survives, concatenating representations from all layers rather than using only the last, normalisation that explicitly preserves feature variance across nodes, and simply not going deep.

Over-squashing

The opposite problem. Information from a node's \(k\)-hop neighbourhood must be compressed into a fixed-size vector, and the neighbourhood grows exponentially with \(k\) in most graphs. Thousands of nodes' information is squeezed through one vector, so distant information is lost regardless of depth.

This is why graph networks perform badly on tasks requiring long-range dependency: the information cannot get through, and adding layers to reach further makes over-smoothing worse without solving the bottleneck.

The mechanism is quantifiable. Sensitivity of a node's output to a distant node's input decays with the number of paths and with the bottleneck along them, and the relevant structural quantity is graph curvature: negatively curved edges, those bridging otherwise poorly connected regions, are where squashing concentrates.

The responses add capacity or shortcuts. Graph rewiring adds edges to relieve bottlenecks, guided by curvature. Global attention or a virtual node connected to everything gives every pair a two-hop path. Graph transformers abandon the sparse structure and attend over all nodes, using structural encodings to reintroduce the topology.

The tension

Over-smoothing says do not aggregate too much; over-squashing says aggregate from further away. Adding edges to relieve squashing accelerates smoothing; restricting aggregation to prevent smoothing worsens squashing. A deep graph network faces both simultaneously, which is why the practical answer has been shallow networks plus explicit long-range mechanisms rather than depth.

When it breaks

The two are diagnosed differently. Falling representation distance across layers indicates smoothing; failure on tasks requiring distant information while local tasks work indicates squashing. Applying the wrong fix, adding residual connections to a squashing problem, changes nothing and consumes a cycle.

Graph transformers trade the problem for cost. Attending over all nodes removes both failure modes and reintroduces quadratic complexity in node count, which is prohibitive on large graphs and is why sparse message passing persists.

Rewiring changes the object. Adding edges to relieve bottlenecks modifies the graph, and where the graph is the data, a molecule, a road network, the modified structure is no longer the thing being modelled. Whether that matters depends on whether edges carry meaning or are merely a computational substrate.