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. The same slot in the neural construction of Ch. 7 gets filled by linear maps built from the network’s weights and by the diagonal on/off projections induced by its activations.

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\).

Here is the forward pointer the rest of the book will cash out: once we build the neural sheaf (Ch. 7), a global section will be a labeling of vertex stalks whose per-edge discrepancies all vanish — and this labeling will turn out to encode exactly the network’s forward pass. Each kind of edge will contribute one familiar rule: weight edges will enforce that the pre-activation equals the weighted post-activation, and activation edges will enforce that the activation is applied correctly. Concretely (Ch. 7): at weight edges \(z^{(\ell)} = \widetilde{W}^{(\ell)} \tilde{a}^{(\ell-1)}\) and at activation edges \(a^{(\ell)} = R_{z^{(\ell)}} z^{(\ell)}\).

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\) becomes the sheaf Laplacian. A forward hint worth carrying: once we fix a neural sheaf and hold the inputs fixed, the part of \(\delta\) acting on the free (non-boundary) coordinates turns out to be a square matrix — and, remarkably, one whose determinant is always exactly 1. That single structural fact is what will make the network’s forward pass the unique equilibrium of the dynamics in later chapters (this is Lemma 3.2 of [3], formalized in Ch. 7).

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 Cellular 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. The point to internalize now is that individual restriction maps are allowed to be rectangular; what ends up mattering for the spectral theory is the composed operator \(\delta^T\delta\), whose positive semi-definiteness is guaranteed regardless. (In Ch. 7 the neural-sheaf weight-edge restriction maps are tall: edge stalk \(\mathbb{R}^{n_\ell}\), vertex stalk \(\mathbb{R}^{n_{\ell-1}+n_\ell}\) after a bias extension.)

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.