Sheaf-Based Positional Encodings: Letting Node Features Into the Spectrum
Published:
Authors: Yu He, Cristian Bodnar, Pietro Liò
Venue: NeurIPS 2023 Workshop on Symmetry and Geometry in Neural Representations · PMLR 228
What a positional encoding is for
Message passing is local. A node’s representation is a function of its immediate neighbourhood, so two nodes with isomorphic neighbourhoods get identical embeddings — which is the 1-WL ceiling, and the reason GNNs fail on regular graphs and miss simple substructures.
Positional encodings break this by telling each node where it sits globally. The standard recipe: eigendecompose the graph Laplacian, take the eigenvectors of the smallest \(k\) eigenvalues, concatenate them to the node features. Laplacian eigenmaps embed the graph into Euclidean space in a way that respects its topology, so nearby nodes get nearby coordinates.
Graph Transformers need this even more acutely. Attending over a fully connected graph throws away the input structure entirely — the expressive power of a Transformer without PEs is that of DeepSets, since no edge remains. PEs are what put the topology back.
The sheaf Laplacian does not have this problem, because the restriction maps are functions of the node features. Its spectrum therefore encodes structure and semantics together.
Two ways to get the sheaf
ConnLap — precomputed. Constrain the restriction maps to be orthogonal and the sheaf Laplacian becomes the connection Laplacian, a discrete vector bundle whose transports approximate parallel transport on a manifold. For an edge \((v,u)\) the transport collapses to a single step,
because an edge gives a canonical one-step path. The maps come straight from Conn-NSD: local PCA over each node’s 1-hop neighbourhood produces an orthonormal tangent basis, and the SVD of \(O_v^{\top}O_u\) produces the aligning rotation \(O_{vu} = UV^{\top}\). This happens once at preprocessing, exactly like the graph Laplacian it replaces.
SheafLap — learned. Follow NSD instead: \(\mathcal{F}_{v \trianglelefteq e:=(v,u)} = \Phi(x_v, x_u)\) with \(\Phi(x_v,x_u) = \sigma(W[x_v \Vert x_u] + b)\) reshaped to \(d \times d\), restricted to orthogonal matrices to balance efficiency against generality.
Either way the PE construction is the same. Eigendecompose the \(nd \times nd\) matrix, take the eigenvectors of the smallest \(k\) eigenvalues, reshape to \(n \times kd\), and concatenate with the \(n \times d_x\) features to get \(X' \in \mathbb{R}^{n \times (d_x + kd)}\).
Node-level results
GCN base model — chosen precisely because it is known to fail on heterophilic graphs — with \(k = 8\) eigenvectors and stalk dimension \(d = 3\), on the usual nine datasets.
| Dataset | \(h\) | No PE | GraphLap | ConnLap | SheafLap |
|---|---|---|---|---|---|
| Texas | 0.11 | 57.30 | 58.22 | 58.38 | 61.08 |
| Wisconsin | 0.21 | 49.80 | 55.49 | 57.65 | 54.51 |
| Film | 0.22 | 25.20 | 25.13 | 26.53 | 23.80 |
| Squirrel | 0.22 | 46.62 | 47.56 | 47.92 | 51.11 |
| Chameleon | 0.23 | 63.97 | 64.28 | 65.57 | 65.20 |
| Cornell | 0.30 | 45.95 | 51.35 | 52.97 | 48.38 |
| Citeseer | 0.74 | 72.34 | 73.83 | 73.88 | 74.35 |
| Pubmed | 0.80 | 86.43 | 86.43 | 86.49 | 85.84 |
| Cora | 0.81 | 84.71 | 85.05 | 85.13 | 85.88 |
Three clean readings.
ConnLap beats GraphLap on all nine. Never by much — the largest margin is 2.16 on Wisconsin, and Pubmed moves by 0.06 — but the direction is unanimous. That is the paper’s central claim and the table supports it.
SheafLap is higher-variance in both directions. It takes the largest single gain in the study, +3.55 on Squirrel over Squirrel’s GraphLap, and wins Texas, Citeseer and Cora too. But on Film it scores 23.80, below the no-PE baseline of 25.20, and on Cornell it lands 3 points under GraphLap. Adding a learned positional encoding can make the model worse than adding none.
Every PE helps on heterophilic data, which is the real signal. Cornell moves from 45.95 to 52.97 and Wisconsin from 49.80 to 57.65. These are exactly the datasets where a GCN is worst, and where the positional information has the most to add.
The paper’s explanation for ConnLap’s greater stability is worth recording, because it is three concrete mechanisms rather than a hand-wave: the datasets have high feature dimension, so the manifold assumption ConnLap depends on is plausible; precomputation avoids the numerical trouble SheafLap occasionally hits in backpropagation; and the datasets are small enough that there may simply not be enough data to fit a sheaf.
Graph-level results, and the honest failure
On molecules the story changes, and the paper does not hide it.
| ZINC (MAE ↓) | ZINC + LSPE (MAE ↓) | MOLTOX21 (AUC ↑) | |
|---|---|---|---|
| No PE | 0.251 ± 0.009 | — | 77.2 ± 0.6 |
| GraphLap | 0.202 ± 0.006 | 0.196 ± 0.008 | 77.4 ± 0.7 |
| ConnLap | 0.249 ± 0.005 | 0.193 ± 0.014 | 77.9 ± 0.2 |
On ZINC, ConnLap barely improves on no encoding at all (0.249 against 0.251) while the plain graph Laplacian reaches 0.202. That is a substantial defeat, and the diagnosis is the interesting part: ZINC’s node features are one-hot atom types. Sparse one-hot vectors do not satisfy the manifold assumption in any meaningful way — there is no local geometry for PCA to find — so the construction has nothing to work with. MOLTOX21, whose nodes carry 9-dimensional feature vectors encoding atomic number, chirality and formal charge, behaves as expected and ConnLap wins.
The rescue is elegant. Letting the encoding evolve during training (LSPE) moves ConnLap from 0.249 to 0.193, overtaking GraphLap’s 0.196, while GraphLap barely improves (0.202 to 0.196). The sheaf structure is a good initialisation even where the manifold assumption fails; it just cannot be left frozen.
Across base models on MOLTOX21, both Laplacian PEs hurt PNA (75.5 with no PE, 75.2 and 75.3 with them), where a random-walk encoding reaches 76.1. The paper’s reading — that PNA’s multiple-aggregator scheme benefits from relative rather than global positional information — is a real limitation stated plainly, and it generalises beyond this paper.
Cost
This is the section most likely to decide whether you use the method. Seconds, from the appendix:
| Texas precompute | Citeseer precompute | Squirrel precompute | Citeseer / epoch | Squirrel / epoch | |
|---|---|---|---|---|---|
| GraphLap | 49.67 | 1,886.58 | 9,654.07 | 4.47 | 41.87 |
| ConnLap | 608.32 | 8,562.46 | 72,148.34 | 3.48 | 33.98 |
| SheafLap | 0 | 0 | 0 | 3,139.45 | 31,503.36 |
ConnLap’s preprocessing runs several times to an order of magnitude longer than the graph Laplacian’s, but it is a one-off per dataset and the per-epoch cost is comparable — so across a hyperparameter sweep it amortises to nearly nothing.
SheafLap has no preprocessing and pays for it every epoch, at roughly three orders of magnitude over the alternatives: 3,139 seconds per epoch on Citeseer against 4.47. Since training runs hundreds of epochs, the learned variant is not practical at any of these scales, whatever its accuracy. That is the paper’s own conclusion, and it explains why graph-level experiments use ConnLap only — batching complicates the learned route further, and “unbatching graphs during training” is left as future work.
Two smaller findings
Unnormalised beats normalised. Ablating the normalisation of the learned sheaf Laplacian, the unnormalised version wins in every case but one. Normalisation reduces the number of possible sign configurations, which should help with the ambiguity problem — but apparently not enough to pay for the expressiveness it costs.
More eigenvectors help, then stop helping. Accuracy rises with \(k\) up to a turning point and then declines: more eigenvectors mean more positional information but also more sign ambiguity. Cornell is the exception, showing no such curve, which the authors read as evidence that Laplacian PEs are simply a poor fit for that graph — and which retrospectively explains SheafLap’s poor Cornell showing in the main table.
✅ Key Takeaways
- Graph Laplacian PEs encode adjacency only. Sheaf Laplacian PEs encode adjacency and node data, because the restriction maps are parameterised by features.
- Two variants: ConnLap (precomputed via local PCA and tangent-space alignment) and SheafLap (learned via an MLP, orthogonal maps).
- ConnLap improves on graph-Laplacian PEs on all nine node-classification datasets — consistently, though usually by under a point.
- SheafLap has the highest single gain (+3.55 on Squirrel) and also drops below the no-PE baseline on Film. It is the less reliable of the two.
- On ZINC, ConnLap fails (0.249 vs GraphLap 0.202) because one-hot atom features violate the manifold assumption — then wins (0.193) once the encoding is allowed to evolve during training.
- ConnLap's preprocessing is a one-off costing several times the graph Laplacian's; SheafLap costs roughly 1000× more per epoch, which rules it out at these scales.
- Eigenvector sign ambiguity is inherited and made worse by the larger spectrum. SignNet is named as the fix and not applied.
References
- He, Y., Bodnar, C., & Liò, P. (2023). Sheaf-based Positional Encodings for Graph Neural Networks. NeurIPS 2023 Workshop on Symmetry and Geometry in Neural Representations, PMLR 228.
- 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 TAG-ML Workshop.
- Bodnar, C., Di Giovanni, F., Chamberlain, B. P., Liò, P., & Bronstein, M. (2022). Neural Sheaf Diffusion. NeurIPS 2022.
- Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2020). Benchmarking Graph Neural Networks. arXiv:2003.00982.
- Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2021). Graph Neural Networks with Learnable Structural and Positional Representations. ICLR 2022.
- Lim, D., Robinson, J., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. (2022). Sign and Basis Invariant Networks for Spectral Graph Representation Learning. arXiv:2202.13013.
- Kreuzer, D., Beaini, D., Hamilton, W. L., Létourneau, V., & Tossou, P. (2021). Rethinking Graph Transformers with Spectral Attention. NeurIPS 2021.
- Singer, A., & Wu, H.-T. (2012). Vector Diffusion Maps and the Connection Laplacian. Communications on Pure and Applied Mathematics, 65(8), 1067–1144.
- Sato, R., Yamada, M., & Kashima, H. (2019). Approximation Ratios of Graph Neural Networks for Combinatorial Problems. NeurIPS 2019.