What is over-squashing in GNN?

Over-squashing in graph neural networks (GNN) is a problem where, during the aggregation of information from a large number of neighboring nodes, important details and differences are 'compressed' or lost.

When messages from neighbors are repeatedly combined into a single vector, it results in significant information compression, making it difficult for the model to effectively distinguish different structures or features, which degrades the quality of learning and predictions.

This is especially noticeable in deep GNNs, where the number of aggregations increases, and the signal from distant nodes becomes overly generalized.

To combat over-squashing, the following are used:

• Attention mechanisms to highlight important messages
• Architectures with skip connections
• Use of more local aggregations or hierarchical models

Thus, over-squashing is a loss of information due to excessive compression during aggregation in GNN.