Cooperative Sheaf Neural Networks: Listening Without Speaking
Published:
Authors: André Ribeiro, Ana Luiza Tenório, Juan Belieni, Diego Mesquita (Getulio Vargas Foundation), Amauri H. Souza (Federal Institute of Ceará)
Preprint: arXiv:2507.00647v2, September 2025
The question: can a sheaf network cooperate?
Finkelshtein et al.’s cooperative GNNs treat nodes as players who pick an action each layer: PROPAGATE (send only), LISTEN (receive only), STANDARD (both), ISOLATE (neither). An auxiliary action network chooses, trained through discrete choices with a straight-through Gumbel-Softmax estimator. The motivation is oversquashing: if a node can decline to relay, exponentially growing neighbourhoods stop being compressed into fixed-size vectors.
Sheaf networks look like they should already have this. A restriction map \(\mathcal{F}_{i \trianglelefteq e}\) is a full \(d \times d\) matrix per incident pair — surely setting it to zero silences that channel? The paper asks precisely this and answers negatively.
Why one restriction map cannot do both jobs
The cleanest version of the argument is the picture rather than the proposition. In a flat vector bundle there is a single orthogonal map \(O_i\) per node, used for every incident edge. The off-diagonal Laplacian blocks are \(-O_i^{\top}O_j\), so \(O_i = 0\) zeroes both the block that feeds \(j\) into \(i\) and the block that feeds \(i\) into \(j\). One knob, two directions. The only reachable actions are STANDARD and ISOLATE.
Sheaves on directed graphs
The fix is to give each node two maps instead of one, by treating each undirected edge as a pair of directed edges. A cellular sheaf over a directed graph assigns stalks \(\mathcal{F}(i)\) and \(\mathcal{F}(ij)\), and for each node two families of restriction maps: \(\mathcal{F}_{i \trianglelefteq ij}\) where \(i\) is the source, and \(\mathcal{F}_{i \trianglelefteq ji}\) where \(i\) is the target. Four maps per undirected pair instead of two.
Directed graphs have two Laplacians, and so do directed sheaves:
For the trivial sheaf these reduce to \((L^{\mathrm{out}})^{\top}\) and \(L^{\mathrm{in}}\), the standard out- and in-degree graph Laplacians.
Flat bundles over directed graphs keep the parameter count down: assign each node a source conformal map \(S_i\) and a target conformal map \(T_i\), and set \(\mathcal{F}_{i\trianglelefteq ij} = S_i\), \(\mathcal{F}_{i \trianglelefteq ji} = T_i\) for every neighbour. That is \(2n\) maps rather than \(4m\).
The layer
CSNN composes the two, using the out-degree Laplacian and the transposed in-degree Laplacian:
With flat bundles the operators collapse pleasantly:
Note that the two share their off-diagonal blocks, \(-T_i^{\top}S_j\): the target map of the receiver times the source map of the sender. That factorisation is the whole design. Whether \(i\) receives is governed by \(T_i\) alone; whether \(j\) is heard is governed by \(S_j\) alone.
Proposition 4.1 confirms the design does what it should: \(T_i = 0\) gives \(((L^{\mathrm{in}}_{\mathcal{F}})^{\top}L^{\mathrm{out}}_{\mathcal{F}}X)_i = 0\), and \(S_k = 0\) for a neighbour \(k\) removes \(x_k\) from \(i\)’s update. (The prose introducing it has the equalities inverted — it reads “Setting \(T_i \neq 0\) drives \(i\) to LISTEN” where the proposition establishes the \(T_i = 0\) direction. A typo, but it inverts the meaning of the paragraph.)
Doubling the receptive field
Proposition 4.2: in each layer, a node can be affected by nodes up to \(2t\) hops away rather than \(t\). The mechanism is visible in the expanded composition: there is a sum over neighbours \(j\) of \(i\) and, nested inside, a sum over neighbours \(u\) of \(j\). Composing two Laplacians buys two hops per layer.
Proposition 4.3 is the sharper claim: for \(i\) and \(j\) at distance \(t\), CSNN can route \(j\)’s information to \(i\) by layer \(t\) while ignoring every intermediate node on the path. Example 4.4 makes it concrete on the four-node path \(1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4\): at layer 1 set every map to zero except \(T_{3,1}\) and \(S_{4,1}\), so only \(x_3\) updates, to \(-2T^{\top}_{4,1}S_{4,1}x^{(0)}_4\); at layer 2 keep only \(T_{2,2}, S_{3,2}\); at layer 3 only \(T_{1,3}, S_{2,3}\). The result is that \(x^{(3)}_1\) depends on \(x^{(0)}_4\) and on nothing else.
Against the standard oversquashing bound \(\lvert \partial x^{(t)}_i / \partial x^{(0)}_j\rvert \le c^t \hat{A}^t_{ij}\), the point is that CSNN’s Jacobian “can be as high as the values of the non-zero \(T_i\) and \(S_i\) permit” — the conformal scalars are unbounded above, so sensitivity need not decay with distance.
The cost: the operator is no longer a Laplacian
One sentence in Section 5 deserves to be in the abstract:
The in- and out-Laplacians we defined here are not particular cases of the Laplacians over quivers: they obtain a positive semi-definite matrix while our Laplacians can have complex eigenvalues with negative real parts.
Results
The clearest experiment is the synthetic one. Alon and Yahav’s NeighborsMatch benchmark builds binary trees of depth \(r\) in which the root must be matched to a leaf by neighbour count, so information has to survive a journey of length \(r\) through a bottleneck. CSNN reaches 100% training accuracy for every \(r\) from 2 to 8. GCN and GIN stop fitting the data at \(r = 4\), GAT and GGNN at \(r = 5\), and all four have fallen below 0.2 by \(r = 8\).
Real graphs come next, using Platonov et al.’s benchmarks with the filtered versions of Squirrel and Chameleon that remove the duplicate-node leakage:
| Dataset | CSNN | Best baseline | O(\(d\))-NSD |
|---|---|---|---|
| roman-empire | 92.63 ± 0.50 | BuNN 91.75 | 80.41 |
| minesweeper | 99.07 ± 0.25 | BuNN 98.99 | 92.15 |
| tolokers | 85.45 ± 0.53 | CO-GNN 84.84 | 78.83 |
| questions | 79.31 ± 1.22 | BuNN 78.75 | 69.69 |
| squirrel (filt.) | 41.18 ± 2.23 | GCN 39.47 | 35.79 |
| chameleon (filt.) | 43.09 ± 3.17 | CO-GNN 41.14 | 37.93 |
| amazon-ratings | 52.07 ± 1.00 | CO-GNN 54.20 | 42.76 |
That is six of seven, but the margin over \(O(d)\)-NSD is the more striking number: 12.2 points on roman-empire, 9.6 on questions, 6.9 on minesweeper. Whatever the theoretical cost, the directed formulation is doing a great deal of empirical work relative to plain sheaf diffusion.
The older Pei et al. splits tell a similar story with one exception. CSNN takes Texas at 87.30, Wisconsin at 90.00 and Film at 38.03, all best in table, then loses Cornell at 81.62 against Diag-NSD’s 86.49.
Finally, on the Peptides datasets from the Long Range Graph Benchmark, under a 500k parameter budget and averaged over four seeds, CSNN takes peptides-struct at 24.32 ± 0.04 MAE. That is the best result in the table and by some way the tightest variance. On peptides-func it comes second at 71.58 ± 0.80, behind BuNN’s 72.76 ± 0.65.
What the paper actually establishes
The contribution splits in two, and the halves are worth different amounts.
The impossibility result is the durable part. It is a short structural observation about why one restriction map per incident pair cannot express asymmetric participation, and it identifies an expressive limit that had gone unnoticed across a literature built entirely on symmetric incidence. It also answers, concretely, the last of the five open questions Hansen and Ghrist posed in 2019, which asked how directedness and asymmetric relations might be modelled on sheaves.
The architecture is the other half: strong empirically, thinner theoretically. Nine of eleven benchmarks and a perfect NeighborsMatch result are not in doubt. But the operator has left the spectral world, the cooperative-behaviour propositions are existence claims that no experiment tests, and the doubled receptive field is never isolated against a depth-matched baseline. The authors name scaling as the open problem and extending to cell and simplicial complexes as the next direction. A spectral theory for \((\Delta^{\mathrm{in}})^{\top}\Delta^{\mathrm{out}}\) belongs on that list as well.
✅ Key Takeaways
- A standard sheaf Laplacian's off-diagonal block \(-\mathcal{F}^{\top}_{i\trianglelefteq e}\mathcal{F}_{j \trianglelefteq e}\) governs both directions at once, so a node that stops listening also stops speaking: PROPAGATE collapses to ISOLATE.
- Directed cellular sheaves give each node a source map \(S_i\) and a target map \(T_i\). The shared off-diagonal block becomes \(-T_i^{\top}S_j\) — receiver's target times sender's source — decoupling the two roles.
- Conformal maps (orthogonal × learned positive scalar) make block diagonals scalar multiples of the identity, so normalisation is stable, and let a channel close continuously.
- Composing the two Laplacians doubles reach to \(2t\) hops in \(t\) layers, and Prop. 4.3 shows a path can be routed while ignoring every node on it.
- The composed operator is not positive semi-definite — stated once, in related work. That discards the kernel-equals-global-sections identity, Dirichlet-energy contraction, and NSD's separation theory.
- Best on 9 of 11 node-classification benchmarks, beating \(O(d)\)-NSD by up to 12.2 points, and 100% on NeighborsMatch out to radius 8. Loses Cornell to Diag-NSD by 4.87 and amazon-ratings to CO-GNN by 2.13.
- Best MAE on peptides-struct (24.32 ± 0.04); second on peptides-func.
References
- Ribeiro, A., Tenório, A. L., Belieni, J., Souza, A. H., & Mesquita, D. (2025). Cooperative Sheaf Neural Networks. arXiv:2507.00647.
- Finkelshtein, B., Huang, X., Bronstein, M. M., & Ceylan, İ. İ. (2024). Cooperative Graph Neural Networks. ICML 2024, PMLR 235, 13633–13659.
- Bodnar, C., Di Giovanni, F., Chamberlain, B. P., Liò, P., & Bronstein, M. (2022). Neural Sheaf Diffusion. NeurIPS 2022.
- Bamberger, J., Barbero, F., Dong, X., & Bronstein, M. (2025). Bundle Neural Networks for Message Diffusion on Graphs. ICLR 2025.
- Alon, U., & Yahav, E. (2021). On the Bottleneck of Graph Neural Networks and Its Practical Implications. ICLR 2021.
- Agaev, R., & Chebotarev, P. (2005). On the Spectra of Nonsymmetric Laplacian Matrices. Linear Algebra and its Applications, 399, 157–168.
- Sumray, O., Harrington, H. A., & Nanda, V. (2024). Quiver Laplacians and Feature Selection. arXiv:2404.06993.
- Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). A Critical Look at the Evaluation of GNNs Under Heterophily. ICLR 2023.
- Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Liò, P., & Bronstein, M. (2023). On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. ICML 2023, PMLR, 7865–7885.
- Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., & Beaini, D. (2022). Long Range Graph Benchmark. Advances in Neural Information Processing Systems 35, 22326–22340.
- Hansen, J., & Ghrist, R. (2019). Toward a Spectral Theory of Cellular Sheaves. Journal of Applied and Computational Topology, 3(4), 315–358.
- Mhammedi, Z., Hellicar, A., Rahman, A., & Bailey, J. (2017). Efficient Orthogonal Parametrisation of Recurrent Neural Networks Using Householder Reflections. ICML 2017, PMLR, 2401–2409.