FlatNSD Mitigates Over-squashing by Adjusting the Sheaf Rather than Rewiring the Graph, Leading on Long-range Benchmarks

Introduces sheaf effective resistance, generalizing classical effective resistance to a quantity that depends on the sheaf attached to the graph, with a closed-form expression for flat vector bundles. Classical effective resistance is determined solely by graph topology, whereas sheaf effective resistance varies with restriction maps, so it can be tuned on a fixed graph. Definition 4.1 and Proposition 4.2 provide the closed form; it reduces to classical effective resistance for the trivial sheaf, matching prior results.

Proves that for flat vector bundles the over-squashing sensitivity in the Jacobian sense is upper bounded by a quantity related to sheaf effective resistance. Prior work attributed over-squashing mainly to graph topology; here the bottleneck location is relocated to the sheaf. Theorem 4.1 gives the bound for non-bipartite graphs, extended to bipartite graphs (Theorem 4.3); Proposition 4.3 characterizes flat bundles that strictly decrease effective resistance.

Constructs FlatNSD, a message-passing variant of NSD under flat vector bundles, and shows it implicitly modulates total sheaf effective resistance. Indicates the message-passing paradigm itself, with appropriate restriction maps, suffices to alleviate over-squashing without leaving message passing or rewiring the graph. FlatNSD-SAGE reaches 100% accuracy on TreeNeighborsMatch, matching CSNN and surpassing BuNN and classical baselines; total sheaf effective resistance shows a strong inverse Spearman correlation with accuracy during training.

On real and synthetic benchmarks FlatNSD is competitive with rewiring methods and graph transformers, and restriction-map parameterization and stalk dimension are identified as key architectural choices. Provides evidence that much of the variation across sheaf-based models is explained by restriction-map parameterization rather than the underlying architecture. On heterophilic node classification FlatNSD stays close to BuNN and CSNN; on graph classification it shows a substantially higher relative average improvement; on ECHO-Synth's ecc task it outperforms the next best baseline CSNN by over 30%.

The result targets message-passing GNNs using flat vector bundles, in settings where over-squashing dominates long-range dependencies, such as the TreeNeighborsMatch, ECHO-Synth, and Graph Transfer stress tests. For researchers and engineers seeking to mitigate over-squashing without rewiring the graph, it offers a path of tuning restriction maps and provides sheaf effective resistance as a diagnostic. The authors note FlatNSD is intentionally kept simple to isolate and verify the mechanism, rather than to replace more expressive sheaf architectures.

The authors note FlatNSD can be strengthened by richer architectures, such as parallel multiple sheaves, directed-graph sheaves, or sheaves where each node can learn whether to send or receive messages; the effects of these directions remain to be tested. On real data the correlation between effective resistance and accuracy is weaker than in synthetic experiments, which the authors attribute to real tasks not being dominated solely by over-squashing. The authors also note that BuNN code was not publicly available at the time, limiting direct comparison. Readers may watch whether future directions such as sheaf curvature and sheaf spectral gap yield a more complete picture.