Research map / Graph learning / GNN architectures

Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective

NeurIPS 2026 · Graph learning › GNN architectures · approach: Expressive equivariant message passing · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces sheaf effective resistance for flat vector bundles, proves it upper-bounds Jacobian-based over-squashing sensitivity, and uses FlatNSD (a message-passing NSD variant) to show competitive over-squashing mitigation without rewiring.

Problem

Over-squashing in GNNs is usually attributed to graph topology and addressed by rewiring; the paper asks whether the restriction maps of a cellular sheaf can instead control over-squashing without changing the graph.

Approach

Generalizes effective resistance to cellular sheaves (sheaf effective resistance), derives closed forms for flat vector bundles, and shows the Jacobian sensitivity bound from prior work is governed by sheaf ER, so learned orthogonal restriction maps can reduce bottlenecks while the graph stays fixed.

Key results

• On ECHO-Synth ecc, FlatNSD-SAGE reaches MAE 3.138 versus 4.527 for the next best (CSNN), over 30% lower.
• On TreeNeighborsMatch, FlatNSD-SAGE achieves perfect training accuracy for all tested r, matching CSNN and outperforming GCN, GIN, GAT, GGNN and BuNN; NSD with orthogonal maps reaches 0.05 at r=4.
• On heterophilic benchmarks FlatNSD-SAGE reaches 92.26 (roman-empire), 98.45 (minesweeper), 84.90 (tolokers), trailing BuNN and CSNN slightly on several datasets.

Surprising findings

• Sheaf ER can be lowered while the graph is unchanged, and a nontrivial sheaf can lower resistance between distant nodes while increasing it between neighbors.
• FlatNSD performs weakly on the homophilic Cora and Citeseer and on Chameleon, where it trails vanilla GCN on some datasets.

Limitations

• Theory is restricted to flat vector bundles and to the Jacobian-based upper bound; the link to actual over-squashing is shown empirically via correlations, not causality.
• FlatNSD does not consistently beat specialized sheaf models (BuNN, CSNN) or rewiring baselines on all datasets.
• Weak sheaf ER-accuracy correlation on node classification benchmarks, which the authors attribute to mild over-squashing there.

Experimental setup

Datasets: TreeNeighborsMatch ECHO-Synth Graph Transfer Enzymes IMDB Mutag Proteins roman-empire amazon-ratings minesweeper tolokers questions

Benchmarks: TreeNeighborsMatch ECHO-Synth Graph Transfer TUDatasets (Enzymes, IMDB, Mutag, Proteins) heterophilic node classification (roman-empire, amazon-ratings, minesweeper, tolokers, questions) Cora Citeseer Texas Cornell Wisconsin Chameleon

Metrics: accuracy MAE AUROC Spearman correlation training accuracy

Baselines: GCN GIN GAT GGNN BuNN CSNN GraphSAGE GT SDRF FOSR BORF DR

Builds on: Neural Sheaf Diffusion BuNN effective resistance rewiring (Black et al.) Topping et al. Jacobian bound CSNN

Closest papers by meaning

• Bundle Neural Network for message diffusion on graphs (ICLR 2025 · similarity 0.88)
• On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.88)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.87)
• Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing (NeurIPS 2026 · similarity 0.87)
• A Generalized Neural Diffusion Framework on Graphs (AAAI 2024 · similarity 0.87)
• Geometry-Aware Edge Pooling for Graph Neural Networks (NeurIPS 2025 · similarity 0.87)