Graph neural networks that pass messages between neighbouring nodes lose information when a signal must travel far across a graph. This failure is called over-squashing. The standard explanations measure how strongly one node's output responds to a distant node's input, using the derivative between them, graph curvature, or effective resistance. Those quantities describe how loud a distant signal is when it arrives. They say little about how much distinct information can arrive. Physicists who simulate quantum circuits with tensor networks have a sharp answer to the second question. A tensor network is a graph of small tensors glued together along shared indices. In such a network, the amount of correlation that can pass between two regions is capped by the total size of the indices (the "bond dimension") on the smallest cut separating them. We propose to carry this min-cut bound over to message passing. When an $L$-layer network is unrolled over nodes and layers, a target node can only receive information about a distant region through the hidden states of the nodes that separate them. So the receivable information is capped by the summed hidden width of that separator, counted over the layers when the signal can cross.
This reframing makes a concrete, testable architectural prediction. If the bottleneck is separator width, then hidden capacity should go only to the nodes on small separators, not to every node. Those separators can be found with the tree-decomposition and contraction-planning tools that tensor-network simulators already use. Uniform widening is known to overfit, and full matrix states are known to cost quadratic memory. Width placed only on separators, as tensor networks place bond dimension only where correlations need it, should recover long-range performance at a fraction of the parameters.
Core Claim
Let $A$ be a set of source nodes, $v$ a target node, and $S$ a vertex separator, meaning a set of nodes whose removal disconnects $A$ from $v$. Let $d_s$ be the hidden width of node $s$ and $T_S$ the number of layers at which a signal from $A$ can pass through $S$ and still reach $v$ by layer $L$. Any message-passing network computes $\mathbf{h}_v^{(L)}$ as a function of $\mathbf{x}_A$ that factors through the separator states at those layers. Therefore
$$\operatorname{rank}\frac{\partial \mathbf{h}_v^{(L)}}{\partial \mathbf{x}_A} \;\le\; \min_{S}\; T_S \sum_{s\in S} d_s .$$
This is exactly the tensor-network min-cut bound on the space-time unrolling of the network. For a linear network the bound is literally a statement about the bond dimensions of a contracted tensor network. For nonlinear networks it still holds pointwise for the Jacobian.
The bound is complementary to the magnitude bounds of Understanding over-squashing and bottlenecks on graphs via curvature, which bounds the Jacobian norm with Balanced Forman curvature. It also complements On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology, which ties sensitivity to commute time and shows that widening helps but overfits. Those results say a distant signal is attenuated. Ours says how many independent directions of a distant signal can survive at all, and that this count is set by separator size times width rather than by curvature.
The claim we will test has two parts. First, a rank-type bound predicts where models fail on long-range tasks better than curvature or resistance does. Second, a network that adds width only on small separators matches or beats uniformly wide and matrix-state models at matched parameter count.
The closest prior work motivates this framing. gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity showed that over-squashing is partly a storage capacity limit of fixed-size vectors. It fixed the limit by giving every node a $d\times d$ matrix memory updated by outer products, and it notes the quadratic memory cost. We keep gLSTM's diagnosis but change the remedy. Capacity is a property of cuts, not of individual nodes, so it should be spent non-uniformly.
Research Program
The work has three parts.
The first part is theoretical. We will state and prove the separator bound for general message-passing networks, including gated and matrix-state variants. In the matrix-state case, gLSTM's state contributes $d^2$ to the sum. We will then relate it to treewidth. A graph of treewidth $w$ has balanced separators of size at most $w+1$, so chains such as peptides and tree-like graphs have separators of size one or two. This explains why they are hard.
qTorch: The quantum tensor contraction handler bounds contraction cost by line-graph treewidth via tree decompositions computed with QuickBB, and it notes that treewidth explodes on graphs of regularity five or more. We reuse that machinery for the opposite purpose. In simulation, small separators make contraction cheap. In learning, small separators are exactly where information gets stuck.
The second part is a diagnostic. For linear message-passing networks on synthetic graphs, we will contract the full input–output map as a tensor network using the cotengra planner exposed in TensorCircuit: a Quantum Software Framework for the NISQ Era. We will then measure the exact Jacobian rank and compare it with the bound. For trained nonlinear models, we will measure the numerical rank of the Jacobian from source sets to targets, and check whether task failure tracks that rank rather than the Jacobian norm.
The third part is an architecture, which we call separator-width allocation. We will compute a tree decomposition of each input graph, either exactly or with greedy heuristics as qTorch does when exact decomposition is too expensive. From it we score each node by how often it appears in small separators between balanced parts. A fixed extra-width budget $\Delta$ is then distributed in proportion to this score.
The extra width is implemented by padding to a maximum width with per-node masks. That keeps batching simple, and we count only the active parameters and activations. We will build two variants. The first widens vector states in a GatedGCN backbone. The second gives matrix gLSTM memory only to high-score nodes and plain vectors to everyone else. The second variant directly attacks gLSTM's quadratic cost.
Baselines
The naive reference point is a GatedGCN or GCN at uniform width, tuned with the same budget. We also need the parameter-matched uniform-width version, in which the extra budget $\Delta$ is spread evenly over all nodes. This isolates allocation from total capacity. Black et al. predict that uniform widening helps but generalizes worse; we treat that as the "do nothing clever" control.
The strongest existing competitor on capacity is gLSTM. It reports average precision 0.7250 on Peptides-func against 0.6860 for its own GCN baseline. Note that Long Range Graph Benchmark reports 0.5930 for GCN and 0.6439 for SAN, so baselines differ sharply with tuning. We will therefore rerun gLSTM ourselves under our splits and hyperparameter budget rather than quote numbers across papers. Beating gLSTM means matching its average precision within seed noise with substantially fewer state parameters and less memory, or exceeding it at equal memory.
On the synthetic ECHO tasks from Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation, the strongest reported numbers are a mean absolute error of 0.121 for the GRIT Transformer on shortest-path regression, against 2.102 for GCN. On ECHO-Charge the strongest is 6.109×10⁻³ for SWAN. We will compare against a reproduced GPS from Recipe for a General, Powerful, Scalable Graph Transformer and against A-DGN, reporting accuracy alongside wall-clock time per epoch. Topology-side baselines are SDRF rewiring and the heterogeneity-aware virtual node $VN_G$ from Understanding Virtual Nodes: Oversquashing and Node Heterogeneity; the file gives no reported Peptides number for $VN_G$, so we will run it ourselves.
The ablations that isolate the key ingredient are three alternative allocation rules, each spending the same budget $\Delta$. One is random allocation. One is degree-based allocation. The most important is curvature-based allocation, which widens the endpoints of the most negatively curved edges. If curvature-based allocation does as well as separator-based allocation, our claim that rank capacity is the distinct mechanism fails. Every method gets the same data, the same number of tuning trials, and the same GPU-hour cap, and reports mean and standard deviation over at least four seeds.
Why not just…?
Why not just use a Graph Transformer? Global attention removes separators entirely and is the accuracy leader on ECHO shortest-path. However, GPS costs about 788 seconds per epoch on ECHO-Charge versus about 12.8 for A-DGN, per the ECHO benchmark paper. GPS's own authors also note that linear attention loses precision and needs a local message-passing anchor. We do not expect to beat GRIT's accuracy everywhere. The claim is a better accuracy-per-compute frontier, and we will report both axes so readers can judge.
Why not just rewire the graph with SDRF? This is a real threat. Adding shortcut edges enlarges separators, so in our terms rewiring and widening are two ways to buy the same cut capacity. SDRF improved Texas accuracy from 61.19% to 70.35% in Topping et al. It also ignores features, distorts topology, and needs costly curvature preprocessing. We will compare at matched added capacity: k added edges versus the equivalent added separator width. If rewiring wins, we will report that separator capacity is the right quantity and that edges are the cheaper currency. That would still be a finding, but it would downgrade the architectural contribution.
Why not just widen everything, or give every node gLSTM's matrix memory? Black et al. prove that global widening inflates sensitivity indiscriminately and overfits. gLSTM's own results show that wider GCNs still collapse beyond 8 neighbours on Neighbor Associative Recall, while matrix memory holds past 32. The matrix approach works, so the question is efficiency. The parameter-matched uniform baseline and the "gLSTM only on separators" variant settle whether targeted allocation keeps the gains at lower cost.
Why not just add a virtual node? A virtual node does enlarge every separator, by one hub. But the hub is itself a single vector, so by our bound it adds only its own width per layer. Hwang et al. show the plain version cannot distinguish nodes beyond two hops. We include $VN_G$ as a baseline and also test widening the virtual node's state, which our bound says should matter.
Decisive Experiments
The first test is a new synthetic task we call bridge recall, which extends the recall task of gLSTM. We store $k$ key–value pairs in one clique and query them from a second clique. The two cliques are joined by $w$ parallel paths of length $\ell$, and we sweep $k$, $w$, $\ell$, and $d$.
The separator bound predicts a failure threshold $k^*$ that grows linearly in $w\cdot d$. Effective-resistance and curvature arguments predict degradation with $\ell$, but no sharp threshold in $k$ at fixed topology as $d$ changes. Whichever prediction fits the measured threshold curves decides the theoretical claim. We will also check on CliquePath and on the line, ladder, tree, and lobster families of ECHO-Synth, whose separator sizes are known exactly. There we test whether per-target error on shortest-path, eccentricity, and diameter correlates with the separator bound after controlling for distance and resistance.
The second test is practical. On Peptides-func, Peptides-struct, ECHO-Charge, and ECHO-Energy, we compare separator-width allocation against the baselines above at three matched parameter budgets. We report average precision or mean absolute error, peak memory, and time per epoch. The idea succeeds if the separator-allocated gLSTM variant matches full gLSTM on Peptides-func at clearly lower state memory. It also needs to beat the curvature-allocated ablation on at least the synthetic suite. Failing either check would mean the tensor-network lens is explanatory but not useful as an architecture, and we would report it that way.
References
- Understanding over-squashing and bottlenecks on graphs via curvature
- On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology
- gLSTM: Mitigating Over-Squashing by Increasing Storage Capacity
- qTorch: The quantum tensor contraction handler
- TensorCircuit: a Quantum Software Framework for the NISQ Era
- Long Range Graph Benchmark
- Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation
- Recipe for a General, Powerful, Scalable Graph Transformer
- Understanding Virtual Nodes: Oversquashing and Node Heterogeneity