Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Sheaves on Simplicial Complexes: Topological Deep Learning

6 minute read

Published:

TL;DR: Sheaves can be defined on simplicial complexes K by assigning stalks to every simplex (node, edge, triangle, ...) and restriction maps between incident simplices. This gives a sheaf cochain complex 0 → C⁰ → C¹ → C² → ... with Hodge Laplacians at each level. Message Passing Simplicial Networks (MPSN) are a special case; full sheaf networks on simplicial complexes learn restriction maps across all dimensions simultaneously.

From Graphs to Simplicial Complexes

A simplicial complex K consists of:

  • 0-simplices (nodes): the vertices V
  • 1-simplices (edges): pairs {u,v} ∈ E
  • 2-simplices (triangles): triples {u,v,w} ∈ T (when all three pairwise edges exist)
  • k-simplices: k+1-cliques, including all faces

A simplicial complex is closed under faces: if σ ∈ K, then all faces of σ are in K.

Why higher-order structure matters:

  • Triangles encode three-way interactions (not captured by pairwise edges)
  • Triangle structure carries topological information (cycles vs filled regions)
  • Many real-world datasets have natural higher-order structure: molecular bonds and angles, protein interaction triangles, social group membership

Cellular Sheaves on Simplicial Complexes

A cellular sheaf F on a simplicial complex K assigns:

  • A stalk F(σ) ≅ ℝ^{d_σ} to each simplex σ ∈ K
  • A restriction map F_{σ▷τ} : F(σ) → F(τ) for each face inclusion τ ≺ σ (τ is a face of σ)

The sheaf cochain complex is:

0 → C⁰(K, F) →^{δ₀} C¹(K, F) →^{δ₁} C²(K, F) →^{δ₂} ...

where:

  • C^k(K, F) = ∏_{σ ∈ K, dim σ = k} F(σ) — k-cochains (signals on k-simplices)
  • δ_k : C^k → C^{k+1} — coboundary, encoding disagreement between k-simplex data and (k+1)-simplex structure

The coboundary maps must satisfy δ_{k+1} ∘ δ_k = 0 — the chain complex condition.

The Sheaf Hodge Laplacians

At each level k, the sheaf Hodge Laplacian is:

Δ^k_F = δ_{k-1} δ_{k-1}ᵀ + δ_k^ᵀ δ_k

(setting δ_{-1} = 0 and δ_{dim K + 1} = 0 at the boundaries).

For k=0: Δ⁰_F = δ₀ᵀ δ₀ = Δ_F (the Sheaf Laplacian on nodes — the same as before)

For k=1: Δ¹_F = δ₀ δ₀ᵀ + δ₁ᵀ δ₁ (combines node-adjacency and triangle contributions for edges)

For k=2: Δ²_F = δ₁ δ₁ᵀ + δ₂ᵀ δ₂ (combines edge-adjacency and tetrahedra contributions for triangles)

The k-th cohomology:

H^k(K, F) = ker(δ_k) / im(δ_{k-1})

This generalises H⁰ (global sections) to all dimensions — measuring topological “holes” at every level.

Message Passing Simplicial Networks (MPSN)

Bodnar et al. (2021) introduced MPSN — message passing on simplicial complexes. At each level k, messages pass:

  • Down: from k-simplices to their (k-1)-simplex faces
  • Up: from k-simplices to their (k+1)-simplex cofaces

The message at simplex σ at level k:

m_σ = AGG({ MSG(h_τ, h_σ) : τ ≺ σ or τ ≻ σ })

where τ ≺ σ means τ is a face of σ and τ ≻ σ means τ is a coface of σ.

MPSN as a special sheaf: MPSN is a cellular sheaf on the simplicial complex where:

  • Each simplex has a stalk F(σ) ≅ ℝ^d
  • Restriction maps are identity or learned linear maps
  • The message is the coboundary applied to the stalk assignment
Why simplicial structure matters for node classification: Two graphs with the same edges but different triangle structure can have different MPSN representations — even if they are 1-WL equivalent. The triangle-level information (which edges form triangles) provides additional expressiveness that graph-only GNNs miss. Sheaves on simplicial complexes carry all this structure plus per-simplex relational geometry.

CW Networks: Going Beyond Simplicial Complexes

Bodnar et al. (2021b) introduced CW Networks — message passing on CW complexes (a more general class than simplicial complexes, where cells need not be simplices):

CW complex cells: 0-cells (nodes), 1-cells (edges, possibly with loops), 2-cells (faces, not necessarily triangular — could be hexagons, arbitrary polygons), k-cells (k-dimensional cells).

Why CW complexes? Many natural domains have non-triangular higher-order structure:

  • Molecular rings: 6-cycles (benzene) are 2-cells that are not triangulable
  • Grid graphs: 4-cycles (squares) as 2-cells
  • Graph coarsening: merged nodes/edges form higher-dimensional cells

CW Networks with sheaves on CW complexes can represent any regular cell complex, making them the most general form of topological sheaf learning.

Topological Deep Learning: The Unifying Framework

Giusti, Battiloro, Testa, Di Lorenzo, Sardellitti, & Barbarossa (2023) formalise Topological Deep Learning (TDL) as:

  • Data lives on cells of a CW complex
  • Models are sheaf networks on the complex
  • Message passing follows the coboundary structure of the complex
  • Learning is end-to-end over restriction maps and readout

This unifies: | Model | Complex | Signal levels | |—|—|—| | GCN, GIN, GAT | Graph (1D CW) | Level 0 (nodes) | | Line graph GNN | Graph | Level 1 (edges) | | MPSN | Simplicial complex | Level 0, 1, 2, … | | CW-Net | CW complex | Level 0, 1, 2, … | | Sheaf GNN (NSD) | Graph (1D CW) + sheaf | Level 0 with stalks | | Simplicial Sheaf GNN | Simplicial complex + sheaf | All levels with stalks |

Full TDL = sheaf GNN on CW complex — the most general setting.

Practical Implementation

Computing Δ^k_F for k > 0 requires:

  1. Constructing the complex: finding triangles (k=2) requires triangle enumeration — O(E·d_max) for sparse graphs
  2. Assembling coboundary maps: δ₁ has sizeT×E(triangles × edges) — sparse, computable in O(T·d²)
  3. Message passing: using Δ^k_F is analogous to using Δ_F but for edge/triangle signals

Current limitation: Constructing simplicial complexes from real-world graphs (clique complexes, Rips complexes, Vietoris-Rips) can be expensive for dense graphs. For sparse graphs (social networks, citation graphs), clique complex construction is manageable.

Datasets and Benchmarks

  • QM9 (molecular): Molecules have natural triangle structure (ring bonds); MPSN shows improvement over GNN
  • Synthetic WL-test benchmarks: MPSN distinguishes graphs that fool 1-WL and 2-WL, using triangle topology
  • Traffic networks: Roads form natural simplicial complexes (intersections → edges → triangular regions)
  • Social networks: Friend triangles are natural 2-simplices

References

  • Bodnar, C., Frasca, F., Wang, Y. G., Otter, N., Montufar, G. F., Liò, P., & Bronstein, M. M. (2021). Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks. ICML 2021 (MPSN: the foundational work on message passing on simplicial complexes — precursor to sheaves on complexes).
  • Bodnar, C., Frasca, F., Otter, N., Wang, Y. G., Liò, P., Montufar, G. F., & Bronstein, M. M. (2021). Weisfeiler and Lehman Go Cellular: CW Networks. NeurIPS 2021 (CW-Net: message passing on general CW complexes, subsuming simplicial complexes and graphs).
  • Giusti, G., Battiloro, C., Testa, L., Di Lorenzo, P., Sardellitti, S., & Barbarossa, S. (2023). Cell Attention Networks. arXiv 2023 (CAN: attention on cellular complexes — sheaf attention extended to higher-order cells).

You May Also Enjoy

Open Problems and Future Directions in Sheaf Neural Networks

5 minute read

Published:

Sheaf Neural Networks are a young field with many open research problems. This post surveys the most important unsolved questions: scalability to million-node graphs, stochastic sheaves for uncertainty quantification, sheaf autoencoders for generative models, connections to persistent homology, and unification with other topological deep learning frameworks.

Sheaf GNNs for Molecular Property Prediction

7 minute read

Published:

Molecular graphs are naturally heterophilic — atoms of different types bonded together — and have rich geometric structure (bond angles, torsion angles). Sheaf GNNs can encode this structure via restriction maps that represent the relational geometry between bonded atoms. This post explores how sheaf theory applies to molecular property prediction.

Sheaf GNNs for Heterophilic Node Classification: Benchmarks and Results

6 minute read

Published:

A systematic comparison of sheaf GNNs against baselines on standard heterophilic node classification benchmarks. Which datasets benefit most from sheaf structure? How does stalk dimension d affect performance? When do sheaves win — and when don’t they?

Sheaves Meet Attention: Transformer-Inspired Sheaf Models

6 minute read

Published:

Graph Transformers use global attention to capture long-range dependencies that local message passing misses. Sheaf Transformers combine sheaf-based local aggregation (with learnable relational geometry) with global attention (for long-range dependencies). This post surveys the design space of sheaf-augmented attention models.