Over-squashing as Transport Congestion: A Sandpile Dynamics Perspective

Shi, Yang; Chen, Lixian; Wang, Jingchao; Guo, Minzhe; Huang, Mingxuan; Chen, Yanhui; Xie, Yifeng; Chen, Xuhang; Lu, Liangsi

SIGKDD 2026

Over-squashing as Transport Congestion: A Sandpile Dynamics Perspective

Yang Shi^1,* Lixian Chen^1,* Jingchao Wang² Minzhe Guo¹ Mingxuan Huang³ Yanhui Chen¹ Yifeng Xie⁴ Xuhang Chen⁵ Liangsi Lu^1,†

¹Guangdong University of Technology ²Peking University ³Sun Yat-Sen University ⁴Hong Kong Baptist University ⁵Huizhou University

^*Equal contribution · ^†Corresponding author

Code Dataset

Conceptual comparison between standard MP-GNN propagation and sandpile-inspired SSL. — MP-GNN propagation can compress many distant signals through narrow graph regions; sandpile-inspired SSL treats overload as releasable transport congestion.

Abstract

A capacity-and-cut view of long-range message passing.

Message-passing graph neural networks (MP-GNNs) are widely used for learning on relational data. However, their performance drops on tasks requiring long-range interactions due to over-squashing, where exponential information compression overwhelms fixed-width embeddings. While existing analyses often attribute this to geometric bottlenecks under linear diffusion assumptions, thresholded nonlinearities in GNNs motivate a load-release view akin to Abelian sandpiles. Using the discrete sandpile model as a structural proxy, we show that graph bottlenecks force large stabilization cost, effectively creating zones of high transport congestion. We characterize stabilization-invariant equivalence classes induced by the reduced Laplacian and derive cut-based lower bounds linking bottlenecks to unavoidable stabilization effort. The resulting theory is discrete, whereas our implementation is a continuous vector-valued surrogate. The theory identifies the relevant design factors, namely capacity and cut size. Guided by these insights, we propose a differentiable Sandpile Stabilization Layer (SSL) and congestion-aware objectives designed to redistribute excess load and manage stabilization costs.

Core Idea

Over-squashing behaves like transport congestion.

The sandpile lens separates two structural levers: how much load a region can store, and how many edges let load leave that region.

Capacity

Nodes keep stable load up to a learned threshold, then release only the overload.

Cut Size

Small boundaries force many sources to share few transport routes across a bottleneck.

Odometer Proxy

Cumulative release becomes a differentiable congestion signal for regularization and rewiring.

Method

SSL stabilizes overload; rewiring expands bottlenecks.

The framework identifies narrow cuts, measures congestion with an odometer-like signal, and adds targeted cross-cut edges under a small budget.

Sandpile-inspired framework: bottleneck view, congestion quantities, SSL, and sandpile-guided rewiring. — The pipeline connects bottleneck structure to congestion quantities, then applies differentiable stabilization and targeted rewiring.

Cut-forced congestion

If a region receives more load than it can stably store, excess must cross its boundary. When that boundary is small, some node must repeatedly release load, producing a high congestion signal.

A graph region with many sources sending information through a small edge cut to a target. — Many sources in one region must pass through a small edge cut before reaching a target outside the region.