Over-squashing

As explained in Graph Neural Networks in Action

Over-squashing is the compression of information from many distant graph nodes into limited-dimensional node representations, reducing useful signal.

Over-squashing limits how much information a graph neural network can use when distant nodes send messages into a fixed-dimensional node representation. As message passing spans more hops, the receptive field grows rapidly, causing important distant signals to be diluted by nearer-node information. section 5.5.2

The failure develops through a short message-passing pipeline:

• Each additional GNN layer expands a node’s receptive field to include information from farther graph neighborhoods. section 5.5.2
• Aggregating increasingly large neighborhoods compresses many distant signals into limited-dimensional representations. section 5.5.2
• Distant signals become less useful than nearby information, and node representations can become increasingly similar, leading toward over-smoothing. section 5.5.2

Figure 5.19 Visualization of over-squashing (Source: Alon and Yahav [7])

Use the visualization to inspect how information from distant graph regions becomes compressed during message passing. section 5.5.2

How Graph Neural Networks in Action covers it

How deep it goes

Explains receptive-field growth, signal dilution, and convergence toward over-smoothing without presenting mitigation methods.

Examples

Uses Figure 5.19 as a visualization of information compression across distant graph nodes.

What it assumes

Assumes basic GNN message passing and node embeddings while defining receptive fields and over-smoothing in context.

What you can do after

Evaluate when distant-node information may be diluted by deeper GNN message passing.

How it connects

Connects message passing, receptive fields, node representations, dimension reduction, representation learning, and over-smoothing.

liveBookmanning.com

Read Graph Neural Networks in Action on liveBook Get the book at manning.com

Related concepts

• residual connectionaddressed by · A residual connection is a neural-network pathway that carries an earlier representation around one or more transformations to a later computation, where it can be combined with the transformed representation.
• graph neural networkcontrasts with · A graph neural network is a neural-network model that learns representations or predictions from graph-structured data by combining information from connected entities.
• GraphSAGEaddressed by · GraphSAGE is an inductive graph-neural-network method that learns node representations by sampling and aggregating information from node neighborhoods.

This explainer was generated by Manning's knowledge graph from the text of Graph Neural Networks in Action. The section links point to the parts of the book it draws on.