6  Cellular Sheaves on Graphs: Stalks, Restrictions, Sections

Purpose. Introduces cellular sheaves on graphs as concretely as possible — as “vector spaces glued along edges by linear maps” — and builds fluency with the definition before encountering the heavier machinery of cohomology and Laplacians.

6.1 Motivating example

Imagine a social network where each person \(v\) has a private opinion \(x_v \in \mathbb{R}^2\) (their position in a two-dimensional opinion space). Each pair of friends \((u, v)\) connected by an edge \(e\) also has a shared discourse — a space \(\mathcal{F}(e) = \mathbb{R}\) in which they can express a one-dimensional projected version of their opinions. Person \(u\) expresses their opinion on topic \(e\) as \(\mathcal{F}_{u \leq e}\, x_u \in \mathbb{R}\); person \(v\) expresses theirs as \(\mathcal{F}_{v \leq e}\, x_v \in \mathbb{R}\).

The two people agree on edge \(e\) if \(\mathcal{F}_{v \leq e}\, x_v = \mathcal{F}_{u \leq e}\, x_u\). A global consensus (global section) is an assignment of opinions to all people such that every pair agrees on every edge. [1] uses exactly this structure to model opinion dynamics; the sheaf encodes not just the network topology but how people translate private opinions into public discourse.

This is a cellular sheaf. The same definition, with the same notation, will carry the neural network forward pass in Ch. 7.

6.2 Key concepts and results

  • A cellular sheaf \(\mathcal{F}\) on a graph: stalks \(\mathcal{F}(v)\) and \(\mathcal{F}(e)\), restriction maps \(\mathcal{F}_{v \leq e}\).
  • The cochain spaces \(C^0(G;\mathcal{F})\) and \(C^1(G;\mathcal{F})\).
  • Sections: globally consistent 0-cochains.
  • Examples: the constant sheaf, the discourse sheaf, the path sheaf.
  • The coboundary \(\delta\) as a block matrix encoding all restriction maps.

6.3 Intuition

A cellular sheaf is a way of attaching “local data” to a graph that is compatible across edges. Each vertex carries a vector space of its own (the stalk), and each edge imposes a consistency requirement: the data at both endpoint vertices, when “projected” through the restriction maps into the edge’s stalk, must agree.

The new ingredient over a plain graph signal (where stalks are all \(\mathbb{R}\) and restrictions are \(\pm 1\)) is that the stalks can have different dimensions and the restriction maps can be arbitrary linear maps. This lets us encode much richer local data: entire vectors, matrices, or subspaces of data at each node.

The intuition for restriction maps: think of them as “projection operators” that describe how the data at a vertex is seen from the perspective of an adjacent edge. In the discourse sheaf, the restriction is a literal projection from private opinion space to a lower-dimensional public discourse. In the neural sheaf (Ch. 7), the restriction maps are weight matrices and ReLU projections.

6.4 Formal development

Definition

Definition 6.1 Definition 4.1 (Cellular sheaf on a graph, following [2]). A cellular sheaf \(\mathcal{F}\) on a finite graph \(G = (V,E)\) with chosen edge orientations consists of:

  1. a finite-dimensional real inner product space \(\mathcal{F}(v)\), called the stalk at \(v\), for each vertex \(v \in V\);
  2. a finite-dimensional real inner product space \(\mathcal{F}(e)\), called the edge stalk, for each edge \(e \in E\);
  3. a linear map \(\mathcal{F}_{v \leq e} : \mathcal{F}(v) \to \mathcal{F}(e)\), called the restriction map, for each incident pair \(v \leq e\) (i.e., \(v\) is an endpoint of \(e\)).

All stalks are identified with \(\mathbb{R}^n\) for the appropriate \(n\); all inner products are the standard Euclidean inner product; all restriction maps are identified with their matrices.

Notation. We write \(\mathcal{F}(v)\) for the stalk and \(\mathcal{F}_{v \leq e}\) for the restriction map. When the sheaf is clear from context, we write \(F_{ve}\) for the restriction. The notation \(v \leq e\) means “\(v\) is a face of \(e\)” in the cellular sense; for graphs, this just means \(v\) is an endpoint of \(e\).

The cochain spaces

The space of 0-cochains and space of 1-cochains are the direct sums over all vertices and edges: \[C^0(G;\mathcal{F}) = \bigoplus_{v \in V} \mathcal{F}(v), \qquad C^1(G;\mathcal{F}) = \bigoplus_{e \in E} \mathcal{F}(e).\]

A 0-cochain \(x \in C^0(G;\mathcal{F})\) assigns a vector \(x_v \in \mathcal{F}(v)\) to every vertex. A 1-cochain assigns a vector in \(\mathcal{F}(e)\) to every edge. Both spaces carry the direct-sum inner product: \(\langle x, y \rangle = \sum_v \langle x_v, y_v \rangle_{\mathcal{F}(v)}\).

The coboundary operator

The coboundary \(\delta : C^0(G;\mathcal{F}) \to C^1(G;\mathcal{F})\) is defined on each oriented edge \(e = u \to v\) by \[(\delta x)_e = \mathcal{F}_{v \leq e}\, x_v - \mathcal{F}_{u \leq e}\, x_u. \tag{4.1}\]

The value \((\delta x)_e\) is the discrepancy on edge \(e\): it vanishes precisely when the restriction maps at both endpoints produce the same vector in the edge stalk. As a block matrix, \(\delta\) has one block row per edge. For edge \(e = u \to v\), the block row has \(+\mathcal{F}_{v \leq e}\) in the column corresponding to \(v\) and \(-\mathcal{F}_{u \leq e}\) in the column corresponding to \(u\).

The total discrepancy of a 0-cochain is \[\|\delta x\|^2 = \sum_{e \in E} \|(\delta x)_e\|^2_{\mathcal{F}(e)},\] which measures how far \(x\) is from being a global section.

Global sections

Definition 6.2 Definition 4.2 (Global section). A 0-cochain \(x \in C^0(G;\mathcal{F})\) is a global section if \((\delta x)_e = 0\) for every edge \(e\), i.e., \(x \in \ker \delta\).

A global section is a consistent assignment of data to all vertices: for every edge \(e = u \to v\), the two restriction maps produce the same vector: \(\mathcal{F}_{v \leq e}\, x_v = \mathcal{F}_{u \leq e}\, x_u\).

In the neural sheaf (Ch. 7), a global section corresponds to a 0-cochain where every edge’s discrepancy vanishes. At the weight edges, this means \(z^{(\ell)} = \widetilde{W}^{(\ell)} \tilde{a}^{(\ell-1)}\) (the pre-activation equals the weighted post-activation). At the activation edges, this means \(a^{(\ell)} = R_{z^{(\ell)}} z^{(\ell)}\) (the activation applies correctly). A 0-cochain that is a global section encodes the forward pass.

6.5 Worked examples

Example 4.3: The constant sheaf

The constant sheaf \(\underline{\mathbb{R}}^k\) assigns the stalk \(\mathcal{F}(v) = \mathcal{F}(e) = \mathbb{R}^k\) to every vertex and edge, with all restriction maps equal to the identity \(I_k\). The coboundary (4.1) reduces to \[(\delta x)_e = x_{v^+(e)} - x_{v^-(e)},\] which is exactly the ordinary edge difference from Ch. 2. For \(k=1\), the constant sheaf recovers everything in Chapter 2: the graph Laplacian \(\mathcal{L}_{\underline{\mathbb{R}}} = L\), the Dirichlet energy, harmonic functions, and the Dirichlet problem. Global sections of \(\underline{\mathbb{R}}\) are constant functions on connected components.

Example 4.4: The discourse sheaf (Hansen–Ghrist)

Following [1], take a graph of \(n\) agents, each with private opinion space \(\mathcal{F}(v) = \mathbb{R}^d\) and each pair connected by an edge with a shared discourse space \(\mathcal{F}(e) = \mathbb{R}^k\) (for \(k \leq d\)). The restriction map \(\mathcal{F}_{v \leq e}\) is a \(k \times d\) matrix that projects the private opinion onto the relevant discourse axes.

Three-agent example. Take a path \(v_1 - e_{12} - v_2 - e_{23} - v_3\) with \(\mathcal{F}(v_i) = \mathbb{R}^2\) for all \(i\) and \(\mathcal{F}(e_{12}) = \mathcal{F}(e_{23}) = \mathbb{R}\). Let \[\mathcal{F}_{v_1 \leq e_{12}} = (1, 0), \quad \mathcal{F}_{v_2 \leq e_{12}} = (0, 1), \quad \mathcal{F}_{v_2 \leq e_{23}} = (1, 0), \quad \mathcal{F}_{v_3 \leq e_{23}} = (0, 1).\]

A global section satisfies: \(x_{v_1}^{(1)} = x_{v_2}^{(2)}\) (the first component of agent 1’s opinion equals the second component of agent 2’s opinion, via edge \(e_{12}\)) and \(x_{v_2}^{(1)} = x_{v_3}^{(2)}\) (via edge \(e_{23}\)). The space of global sections depends on the restriction maps; in general it may be \(\{0\}\) (no consensus possible) or nontrivial (partial consensus exists).

This example will be used in Chs. 4–6 to develop intuition before the neural sheaf construction in Ch. 7.

Example 4.5: The path sheaf (preview of the neural sheaf)

On the path graph \(v_0 - e_1 - v_1 - e_2 - v_2\) with stalks \(\mathcal{F}(v_0) = \mathbb{R}^2\), \(\mathcal{F}(v_1) = \mathbb{R}^2\), \(\mathcal{F}(v_2) = \mathbb{R}\), and edge stalks \(\mathcal{F}(e_1) = \mathcal{F}(e_2) = \mathbb{R}^2\), define restrictions \[\mathcal{F}_{v_0 \leq e_1} = W \in \mathbb{R}^{2\times2}, \quad \mathcal{F}_{v_1 \leq e_1} = I_2, \quad \mathcal{F}_{v_1 \leq e_2} = R \in \mathbb{R}^{2\times2},\quad \mathcal{F}_{v_2 \leq e_2} = P \in \mathbb{R}^{1\times2}.\] A global section satisfies: \(W x_{v_0} = x_{v_1}\) (weight edge) and \(R x_{v_1} = P^T x_{v_2}\) (activation edge, schematically). With \(W\) a weight matrix, \(R\) a ReLU projection, and \(P\) a projection onto the first coordinate, this is a one-hidden-layer neural sheaf in embryonic form. Chapter 7 develops this fully.

6.6 The coboundary as a block matrix

For computational purposes, write \(\delta\) explicitly. Order the 0-cochains as \((x_{v_1}, \ldots, x_{v_n})\) (stacking the stalk vectors) and the 1-cochains as \((y_{e_1}, \ldots, y_{e_m})\). The coboundary matrix is \[\delta = \begin{pmatrix} \cdots & \mathcal{F}_{v^+(e_1) \leq e_1} & \cdots & -\mathcal{F}_{v^-(e_1) \leq e_1} & \cdots \\ \vdots & & & & \vdots \\ \cdots & \mathcal{F}_{v^+(e_m) \leq e_m} & \cdots & -\mathcal{F}_{v^-(e_m) \leq e_m} & \cdots \end{pmatrix},\] where each row corresponds to an edge and each pair of columns corresponds to the two endpoints.

The dimension of \(\delta\) is \((\sum_e \dim\mathcal{F}(e)) \times (\sum_v \dim\mathcal{F}(v))\). In Ch. 5, \(\delta^T\delta\) is the sheaf Laplacian. The central structural observation of [3] — Lemma 3.2 — is that for the neural sheaf, the restriction of \(\delta\) to the free coordinates is a square matrix with determinant 1.

6.7 Exercises

4.1 (Warm-up — constant sheaf). Verify that the coboundary of the constant sheaf \(\underline{\mathbb{R}}\) on a path \(P_3\) reduces to the incidence matrix from Ch. 2. Compute \(\delta\) as a block matrix.

4.2 (Restriction maps as matrices). For the discourse sheaf in Example 4.4, write out the coboundary matrix \(\delta\) explicitly. Compute \(\delta^T\delta\) and identify the structure of the sheaf Laplacian. What are its eigenvalues?

4.3 (Global sections of the discourse sheaf). For the three-agent discourse sheaf in Example 4.4, find all global sections. Under what conditions on the restriction maps is the space of global sections trivial?

4.4 (Coboundary and orientation). Let \(G\) be a triangle (3-cycle) with edges \(e_1 = v_0 \to v_1\), \(e_2 = v_1 \to v_2\), \(e_3 = v_0 \to v_2\) and the constant sheaf \(\underline{\mathbb{R}}\). (a) Write \(\delta\) and verify \(\|\delta x\|^2 = (x_1-x_0)^2 + (x_2-x_1)^2 + (x_2-x_0)^2\). (b) Now reverse the orientation of \(e_3\) to \(e_3 = v_2 \to v_0\) and rewrite \(\delta\). Verify that \(\delta^T\delta\) is unchanged.

4.5 (Adding an edge). Start with the sheaf from Example 4.5. Add an edge \(e_3 = v_0 \to v_2\) with stalk \(\mathbb{R}^2\) and restriction maps \(\mathcal{F}_{v_0 \leq e_3} = I_2\), \(\mathcal{F}_{v_2 \leq e_3} = P\). Write out the new coboundary. Does the space of global sections shrink or grow?

4.6 (Project — building and visualizing a sheaf). Implement a general CellularSheaf class in Python with methods coboundary() and total_discrepancy(x). Construct the discourse sheaf on a small social network (5 agents, 6 edges) and visualize the discrepancy map for random cochains. See lab-04-build-a-sheaf.

6.8 Coding lab

lab-04-build-a-sheaf — Implement the cellular sheaf data structure (stalks, restriction maps, coboundary matrix) from scratch. Construct the three-agent discourse sheaf, the constant sheaf on a cycle, and the path sheaf of Example 4.5. For each sheaf: compute the coboundary matrix \(\delta\) explicitly, evaluate the total discrepancy \(\|\delta x\|^2\) for several random cochains, and search numerically for global sections by minimizing the discrepancy. This lab is the foundation for the sheaf Laplacian (Ch. 5) and the neural sheaf construction (Ch. 7).

6.9 Further reading

The theory of cellular sheaves on cell complexes (of which graphs are the 1-dimensional case) is developed from a categorical perspective in [4]. The spectral theory of sheaves on graphs — including the sheaf Laplacian, the Hodge theorem, and convergence — is due to [2]. For the opinion dynamics motivation, see [1], whose discourse-sheaf construction is the direct predecessor of the neural sheaf. Ghrist’s Elementary Applied Topology [5] provides an accessible overview of sheaf theory and its applications.

6.10 FAQ / common misconceptions

Q: Why does the edge also need a stalk? In a plain graph, edges just “connect” vertices. In a plain graph, the edge is only a relation: agree or disagree. A sheaf allows the edge to have its own data space, separate from either endpoint. This is what makes sheaves genuinely more expressive than plain graph signals. The edge stalk is the “discourse space” in which the two endpoints’ data are compared; richer edge stalks allow richer compatibility conditions.

Q: Do the restriction maps have to be square? No. \(\mathcal{F}_{v \leq e} : \mathcal{F}(v) \to \mathcal{F}(e)\) can have any dimensions. In the neural sheaf, the weight-edge restriction maps are tall (edge stalk = \(\mathbb{R}^{n_\ell}\), vertex stalk = \(\mathbb{R}^{n_{\ell-1}+n_\ell}\) after the bias extension). What matters for the Laplacian is the composed operator \(\delta^T\delta\), whose positive semi-definiteness is guaranteed by construction.

Q: What is the relationship between cellular sheaves and sheaves in algebraic geometry? Sheaves in algebraic geometry are much more general: they are functors from a topology (or site) to a category, and they encode cohomological information about spaces. A cellular sheaf on a graph is a special case: the “topology” is the poset of cells (vertices and edges) of the graph, and the category is vector spaces. All the machinery in this book lives entirely at this concrete level; you do not need the general definition.