Over-squashing as Transport Congestion: A Sandpile Dynamics Perspective

Le résumé fourni par la source

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-squash­ing, 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. Experiments on long-range benchmarks, together with congestion and collision diagnostics, show that targeting sandpile-identified bottlenecks mitigates representation collapse and improves over standard baselines. Project Page: https://sandpile-gnn.github.io/

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.