Alessio Borgi

Alessio Borgi

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

Cellular Sheaves on Graphs: A Rigorous Construction

6 minute read

Published:

TL;DR: A cellular sheaf F on a graph assigns a vector space (stalk) to each node and edge, plus a linear map (restriction map) per incidence pair. 0-cochains are node-level signals; the coboundary δ₀ measures edge-level disagreement. The Sheaf Laplacian Δ_F = δ₀ᵀδ₀ is an (Nd)×(Nd) positive semidefinite block matrix generalising the standard graph Laplacian. Its null space = space of global sections = signals with zero disagreement everywhere.

Setup: A Worked Example

Let G be the path graph: nodes {1, 2, 3}, edges {e₁₂, e₂₃}.

A cellular sheaf assigns:

  • F(1) = F(2) = F(3) = ℝ² (node stalks)
  • F(e₁₂) = F(e₂₃) = ℝ² (edge stalks)
  • Restriction maps: F_{1→e₁₂}, F_{2→e₁₂}, F_{2→e₂₃}, F_{3→e₂₃} ∈ ℝ^{2×2}

A 0-cochain is x = (x₁, x₂, x₃) ∈ ℝ² × ℝ² × ℝ² = ℝ⁶.

The coboundary is:

δ₀ x = ( F_{2→e₁₂} x₂ − F_{1→e₁₂} x₁ , F_{3→e₂₃} x₃ − F_{2→e₂₃} x₂ ) ∈ ℝ² × ℝ² = ℝ⁴

x is a global section if and only if δ₀ x = 0, i.e., F_{2→e₁₂} x₂ = F_{1→e₁₂} x₁ and F_{3→e₂₃} x₃ = F_{2→e₂₃} x₂.

Formal Definition

Definition (Cellular Sheaf). A cellular sheaf F on a graph G = (V, E) consists of:

  1. A vector space F(v) ∈ ℝ^{d_v} for each node v ∈ V
  2. A vector space F(e) ∈ ℝ^{d_e} for each edge e ∈ E
  3. A linear map F_{v▷e} : F(v) → F(e) for each incident pair (v, e) where v is an endpoint of e

No compatibility axioms beyond this are required for a 1-dimensional complex.

In the uniform-stalk case (all stalks ℝ^d), the restriction maps are d×d real matrices.

The Cochain Complex

0-cochains C⁰(G, F) = ∏_{v∈V} F(v) ≅ ℝ^{Nd} — all possible node assignments.

1-cochains C¹(G, F) = ∏_{e∈E} F(e) ≅ ℝ^{Ed} — all possible edge assignments.

The coboundary operator δ₀ : C⁰ → C¹ is the matrix:

[δ₀]_{e,v} = F_{v▷e} · (orientation sign of v in e)

Concretely, for a chosen orientation of each edge e = (u→v):

[δ₀]_{e,u} = −F_{u▷e} , [δ₀]_{e,v} = +F_{v▷e}

This makes δ₀ an (Ed) × (Nd) matrix. The choice of orientation is arbitrary — the Sheaf Laplacian Δ_F = δ₀ᵀδ₀ is orientation-independent.

The Sheaf Laplacian: Block Structure

Δ_F = δ₀ᵀ δ₀ ∈ ℝ^{Nd × Nd}

The (u, v)-block of Δ_F for u ≠ v (adjacent via edge e):

[Δ_F]_{uv} = −F_{u▷e}ᵀ F_{v▷e} ∈ ℝ^{d×d}

The (v, v)-diagonal block:

[Δ_F]_{vv} = Σ_{e incident to v} F_{v▷e}ᵀ F_{v▷e} ∈ ℝ^{d×d}

Properties:

  • Δ_F is symmetric: [Δ_F]{uv} = [Δ_F]{vv}ᵀ ✓ (since F_{u▷e}ᵀF_{v▷e} and F_{v▷e}ᵀF_{u▷e} are transposes)
  • Δ_F is positive semidefinite: xᵀΔ_F x = δ₀ x ² ≥ 0 ✓
  • Δ_F ≽ 0 with null space = ker(δ₀) = space of global sections ✓
  • When F_{v▷e} = I for all (v, e): Δ_F = L ⊗ I_d (graph Laplacian ⊗ identity) ✓

Worked Block Computation: Path Graph

For the path 1–2–3 with stalk dimension d=2 and maps:

  • F_{1▷e₁₂} = A₁, F_{2▷e₁₂} = A₂, F_{2▷e₂₃} = B₂, F_{3▷e₂₃} = B₃ (all 2×2)

The 6×6 Sheaf Laplacian is:

       node1     node2             node3
Δ_F = [ A₁ᵀA₁  | −A₁ᵀA₂         |  0    ]   (node 1 row)
      [−A₂ᵀA₁  |  A₂ᵀA₂+B₂ᵀB₂  | −B₂ᵀB₃]   (node 2 row)
      [  0      | −B₃ᵀB₂         |  B₃ᵀB₃]   (node 3 row)

With identity maps (A₁=A₂=B₂=B₃=I):

Δ_F = L ⊗ I₂ = [ 1  -1   0 ] ⊗ I₂
                [-1   2  -1 ]
                [ 0  -1   1 ]

Global Sections: The Null Space

The null space ker(Δ_F) = ker(δ₀) consists of all x = (x_v) such that:

F_{u▷e}ᵀ F_{v▷e} = F_{v▷e}ᵀ F_{u▷e} ∀(u,v,e) and F_{u▷e} x_u = F_{v▷e} x_v ∀(u,v,e)

Standard case (identity maps): global sections = constant functions (all x_v equal). Dimension = d.

Orthogonal maps (F_{v▷e} ∈ O(d)): global sections = “parallel transported” signals. These can vary nontrivially — a node’s value is the result of composing rotations along a path from a reference node. Dimension of ker = d for connected graphs with consistent holonomy; can be higher when holonomy has non-trivial kernel.

Learned maps (NSD): global sections depend on the learned maps and can have any structure. The dimension of ker(Δ_F) is data-dependent.

Why the null space matters for oversmoothing: In standard GCN, iterating the diffusion h ← (I − αL)h converges to the d-dimensional space of constants. Any information orthogonal to constants is destroyed. In sheaf diffusion, the attractor is the space of global sections — which can be d·c-dimensional for a c-component sheaf, carrying much richer information. This is why sheaf diffusion avoids oversmoothing even at large depth.

The Sheaf Dirichlet Energy

The Sheaf Dirichlet energy of a signal x is:

E_F(x) = xᵀ Δ_F x = ||δ₀ x||² = Σ_{e=(u,v)} ||F_{v▷e} x_v − F_{u▷e} x_u||²

This measures total inconsistency: how far the signal x deviates from the space of global sections. Sheaf diffusion minimises this energy:

dX/dt = −Δ_F X → X(t) = exp(−Δ_F t) X(0)

as t → ∞, X(t) projects onto ker(Δ_F). The equilibrium is not a constant but a global section — a signal that satisfies all pairwise restrictions.

Normalisation

The raw Δ_F is not normalised. In NSD, the normalised Sheaf Laplacian is used:

Δ_F^{norm} = D_F^{-1/2} Δ_F D_F^{-1/2}

where D_F is the block-diagonal matrix of diagonal blocks of Δ_F: [D_F]{vv} = [Δ_F]{vv}. The eigenvalues of Δ_F^{norm} lie in [0, 2] — analogous to the normalised graph Laplacian L^{norm} = D^{-1/2}LD^{1/2}.

Summary

ObjectFormulaDimension
0-cochainx ∈ C⁰ = ∏_v F(v)Nd
1-cochainy ∈ C¹ = ∏_e F(e)Ed
Coboundary δ₀(δ₀ x)e = F{v▷e}x_v − F_{u▷e}x_uEd × Nd
Sheaf LaplacianΔ_F = δ₀ᵀδ₀Nd × Nd
Dirichlet energyE_F(x) = xᵀΔ_Fxscalar
Global sectionsker(Δ_F)≥ d (for connected G)

References

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.