Conn-NSD: Computing the Sheaf Instead of Learning It

The dilemma this paper is stuck between

The sheaf literature had, at this point, exactly two ways of getting a sheaf.

Hand-craft it. Hansen and Gebhart’s original Sheaf Neural Network used a sheaf Laplacian constructed from full knowledge of a synthetic data-generating process. That works when you have the knowledge and does not generalise when you do not.

Learn it. Neural Sheaf Diffusion parameterises each restriction map as \(\mathcal{F}_{v \trianglelefteq e:=(v,u)} = \Phi(x_v, x_u)\) with an MLP, trained by backpropagation. Fully general, applicable to any dataset, and — as the paper puts it — prone to overfitting, computational overhead, and optimisation trouble.

The two options are described as “diametrically opposed”, which is fair. Conn-NSD proposes a middle: compute the maps deterministically at preprocessing time, using geometry rather than gradients.

The manifold assumption, and what it buys

The construction rests on the manifold assumption: although the data lives in a high-dimensional ambient space \(\mathbb{R}^p\), correlations between dimensions mean it actually lies on a \(d\)-dimensional Riemannian manifold \(\mathcal{M}^d\) with \(d \ll p\).

Grant that, and a great deal follows. At every point \(x_i\) the manifold has a tangent space \(T_{x_i}\mathcal{M}\) — which is precisely the role a stalk \(\mathcal{F}(v)\) plays. The mechanism for moving vectors between tangent spaces at nearby points is a connection, or parallel transport — which is precisely the role the transport maps \(\mathcal{F}^{\top}_{v\trianglelefteq e}\mathcal{F}_{u \trianglelefteq e}\) play.

The recipe comes from vector diffusion maps (Singer & Wu, 2012), and it has two steps.

Step 1 — local PCA for a tangent basis. Around \(x_i\), collect neighbours \(x_{i_1},\dots,x_{i_{N_i}}\) and centre them:

Take the SVD \(\hat{X}_i = U_i \Sigma_i V_i^{\top}\) and keep the first \(d\) left singular vectors as \(O_i\). Its columns are orthonormal by construction and span a \(d\)-dimensional subspace of \(\mathbb{R}^p\) — the estimate of \(T_{x_i}\mathcal{M}\).

Step 2 — optimal alignment. For an edge \((i,j)\), take the SVD \(O_i^{\top}O_j = U\Sigma V^{\top}\) and set

This is the orthogonal matrix that best aligns the two bases (an orthogonal Procrustes solution), and Singer and Wu show that for nearby \(x_i, x_j\) it approximates the parallel transport operator.

The graph-aware modification

Singer and Wu worked with point clouds, so their neighbourhood is a metric ball \(\mathcal{N}_{x_i, \epsilon_{PCA}}\) of radius \(\sqrt{\epsilon_{PCA}}\), and their \(N_i \times N_i\) weighting matrix \(D_i\) down-weights distant neighbours, giving \(B_i = \hat{X}_i D_i\).

Conn-NSD makes two changes, and they are the paper’s actual contribution:

1. Use the graph. Replace the metric ball with the 1-hop neighbourhood \(\mathcal{N}^1_{x_i}\). The edges are information Singer and Wu did not have; using them is what makes the procedure graph-aware. The authors believe this is novel.
2. Drop the weighting. Since every 1-hop neighbour is at the same graph distance, set \(D_i = I\), so \(B_i = \hat{X}_i\).

Two practical wrinkles. Estimating \(d\) is non-trivial: the construction is ill-defined if a neighbourhood has fewer than \(d\) members, because \(B_i\) would not have \(d\) singular vectors. Where Singer and Wu estimate \(d\) from the data, Conn-NSD leaves it as a hyperparameter and keeps it small so most nodes have enough neighbours. And when a node genuinely has fewer than \(d\) neighbours, the shortfall is filled with the nearest non-neighbours by Euclidean distance — falling back to the original point-cloud procedure for exactly those nodes.

Assuming unit cost per SVD, runtime grows linearly in the number of data points. Crucially, all of it happens once, before training — so the sheaf Laplacian is a fixed input, and no gradient ever flows through \(\Phi\).

What the baselines are for

The evaluation includes two constructions that exist purely to answer a sceptic: does the geometry matter, or would any orthogonal sheaf do?

• RandEdge-NSD — sample a Haar-random orthogonal matrix per edge.
• RandNode-NSD — sample a Haar-random \(O_i\) per node, then derive transports \(O_{ij}\) from them as usual.

These are the right controls. RandNode in particular preserves the structure of the construction (per-node frames, consistently derived transports) while destroying its content.

Results

Same nine datasets, same 10 fixed 48/32/20 splits as NSD.

Three readings.

The controls are convincingly beaten. Conn-NSD outperforms both random baselines on every dataset, decisively so where it matters: Chameleon 65.21 against 47.72 and 50.68, Squirrel 45.19 against ~34, Cora 83.74 against 74.00. The learned NSD variants beat them too. Whatever a sheaf is contributing, it is not just the extra parameters — the specific geometry is doing work.

It wins where the graph is small. Conn-NSD takes Texas (86.16, above every learned variant) and Film (37.91, likewise), with fewer learnable parameters. The authors attribute this to regularisation: removing \(\Phi\) removes capacity that small datasets cannot support.

It loses badly where the graph is large. Squirrel is the clearest failure — 45.19 against \(O(d)\)-NSD’s 56.34, an 11-point gap — with Chameleon behind by 3.5 and Cora by 3.6. Squirrel has 5,201 nodes and 198,493 edges, by far the densest dataset here, and its underlying MLP scores poorly (28.77). The paper’s proposed explanation is that learned sheaves help most exactly when the features alone are uninformative, which is a testable hypothesis rather than a result — but it is the honest framing, and the paper offers it rather than burying the losses.

The speed argument

Moving the Laplacian to preprocessing removes the need to backpropagate through it. Mean seconds per epoch, against the directly comparable \(O(d)\)-NSD:

The largest datasets benefit most, which is the expected shape — but note the tension with the accuracy table. The speed-up is largest on Squirrel, which is also where the accuracy loss is largest. The trade is real, and it points the wrong way: you save most where you can least afford to.

The per-epoch figures are also only part of the cost. The preprocessing itself is not free — a later paper using the same construction for positional encodings measures it at roughly an order of magnitude more than building a graph Laplacian. It is a one-off per dataset, so it amortises over a hyperparameter sweep, but it is not zero.

What it establishes

The headline claim is modest and well supported: sometimes you do not need to learn the sheaf. Where node features are rich enough for the manifold assumption to hold and the graph is small enough that extra parameters hurt, a deterministic geometric construction is competitive — and it is a genuine regulariser, not merely a shortcut, since it removes parameters rather than constraining them.

The framing the authors choose for future work is the interesting one: computing sheaves non-parametrically with an objective independent of the downstream task. That is a self-supervised framing of sheaf construction, and it is a different research programme from the one the field mostly pursued afterwards.

References

• Barbero, F., Bodnar, C., Sáez de Ocáriz Borde, H., Bronstein, M., Veličković, P., & Liò, P. (2022). Sheaf Neural Networks with Connection Laplacians. ICML 2022 Workshop on Topology, Algebra, and Geometry in Machine Learning, PMLR 196, 28–36.
• Singer, A., & Wu, H.-T. (2012). Vector Diffusion Maps and the Connection Laplacian. Communications on Pure and Applied Mathematics, 65(8), 1067–1144.
• Bodnar, C., Di Giovanni, F., Chamberlain, B. P., Liò, P., & Bronstein, M. (2022). Neural Sheaf Diffusion. NeurIPS 2022.
• Hansen, J., & Gebhart, T. (2020). Sheaf Neural Networks. NeurIPS 2020 Workshop on Topological Data Analysis and Beyond.
• Hansen, J., & Ghrist, R. (2019). Toward a Spectral Theory of Cellular Sheaves. Journal of Applied and Computational Topology, 3(4), 315–358.
• Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., & Yang, B. (2020). Geom-GCN: Geometric Graph Convolutional Networks. ICLR 2020.
• Meckes, E. S. (2019). The Random Matrix Theory of the Classical Compact Groups. Cambridge University Press.