Over-Squashing

In a k-layer GNN, each node's receptive field grows exponentially to encompass O(d^k) nodes, where d is the average degree. All information from this vast neighborhood must be compressed into a single fixed-dimension vector, creating an information bottleneck. For example, in a cellular topology with 1,000 base stations and average degree 5, a 3-layer GNN attempts to compress data from up to 125 nodes into one embedding.

Over-squashing is strongly correlated with negative graph curvature, where the topology resembles a tree-like structure with narrow bridges. Information from distant nodes must pass through these bottlenecks, causing distortion. In cellular networks, this manifests when a rural base station connects to the core network through a single relay, forcing all traffic data through one edge.

As GNN depth increases to capture long-range dependencies, over-squashing intensifies. Key indicators include:

• Node representations become indistinguishable from their immediate neighbors
• Gradient signals vanish for distant node pairs during backpropagation
• Task accuracy plateaus or degrades beyond 3-4 layers in standard GNNs This directly limits the model's ability to coordinate interference management across large cellular clusters.

Graph rewiring techniques modify the adjacency structure to alleviate over-squashing without changing the underlying data. Methods include:

• Spectral rewiring: Adding edges based on graph Laplacian optimization
• Curvature-based rewiring: Augmenting connections in negatively curved regions
• Multi-hop message passing: Allowing direct communication between non-adjacent nodes In a cellular interference graph, this might mean adding direct edges between base stations that share overlapping coverage zones but were not originally connected.

Graph Transformers inherently resist over-squashing by enabling global attention—every node can directly attend to every other node regardless of graph distance. This bypasses the recursive neighborhood aggregation bottleneck entirely. The trade-off is O(N²) computational complexity, making them suitable for moderate-sized cellular topologies but requiring sparse attention variants for large-scale deployments with thousands of nodes.

A distinct but related failure mode where node representations become indistinguishable after too many message-passing layers. Unlike over-squashing, which compresses information from distant nodes into a fixed-size vector, over-smoothing causes all node embeddings to converge to a similar value, losing local discriminative power. This is driven by the low-pass filtering effect of repeated graph convolutions and is particularly problematic for node classification tasks in large cellular topologies.

A structural property of the graph itself that causes over-squashing. A bottleneck occurs when information from a large number of source nodes must pass through a small set of edges or nodes to reach a target node. In cellular networks, a base station serving as the sole backhaul connection for many small cells creates a topological bottleneck. The Cheeger constant and spectral gap of the graph Laplacian mathematically quantify this susceptibility.

An architecture that applies the global self-attention mechanism of a Transformer directly to graph nodes. By allowing each node to attend to every other node in a single operation, Graph Transformers bypass the sequential neighborhood aggregation that causes over-squashing. The trade-off is quadratic computational complexity with respect to the number of nodes, making them challenging for large-scale cellular deployments without efficient approximations like linear attention or sparse kernels.

A technique that injects information about a node's absolute or relative position within the graph structure into its initial features. Common encodings include Laplacian eigenvectors and random walk structural encodings. By providing explicit spatial context, positional encodings help GNNs distinguish topologically similar nodes and can partially mitigate over-squashing by giving the model a direct signal about long-range structure that does not rely on lossy message passing.