A gentle introduction to sheaves on graphs

Jakob Hansen

Abstract

This document is an introduction to the language and theory of cellular sheaves

on graphs with an eye toward engineering and other applications. No familiarity
with topology or commutative algebra is assumed. However, a basic familiarity with
graphs, particularly spectral graph theory, and a working knowledge of linear algebra
from an abstract perspective (e.g. abstract vector spaces, quotients, direct sums and
tensor products, inner products) are necessary.

1 Motivation: connections and relationships

Networks are everywhere. The patterns of connectivity between different entities (e.g.,
people, computers, ideas, neurons) have important consequences for the properties of
systems constructed of these entities. This is the foundational insight behind network
science and its allied fields, and it has proven immensely useful.
But sometimes, just knowing that two things are connected is not enough. We
need to know something about the relationship implied by the connection. Sheaves
offer a mathematically rigorous for approaching problems like this. They describe
the local relationships associated to data on a network, and prescribe how those local
relationships combine to give global structure to the data. Sheaves have a sophisticated
and deep algebraic theory, as well as a nascent spectral theory, both of which offer
powerful tools for understanding networks and systems.
Some of the things that sheaves can do:
• Collate high-dimensional data associated with nodes of a network
• Describe complex relationships between different nodes
• Provide multilayer and multiresolution views of network structures
• Implement sophisticated types of consensus dynamics
• Represent various engineering and physical systems.

1
 I aim here to give an accessible introduction to the theory of sheaves on graphs,
with hints at its potential applications.

2 What is a sheaf?
Sheaves are the canonical mathematical structure for attaching data to spaces. In al-
gebraic topology and geometry, this can take many sophisticated, subtle forms, but
we will deal with a simple version adapted to graphs and simplicial complexes. For
our purposes, a graph is a collection of vertices and edges, together with an incidence
relation, which tells us when a given vertex is incident to a given edge. That is:

Definition 2.1 (Graphs). A graph G consists of a set V of vertices and a set E of edges,
with an incidence relation P, where we write v P e if v is one of the endpoints of the
edge e. There may be more than one edge joining a given pair of vertices.

A sheaf is a way of specifying data spaces associated to edges and vertices of a

graph, with extra information telling us how the data over different parts of the graph
should be related. Our data will be vector valued, so our theory will involve linear
algebra. We will deal only with real vector spaces that carry an inner product, although
this restriction is not necessary. Most of the theory works for vector spaces over any
field, unless an inner product is required. This restriction means that there is little lost
by considering every vector space in sight to be isomorphic to Rn for some n, with the
standard inner product.

Definition 2.2 (Sheaves). Let G be a graph. A sheaf F on G consists of a vector space

F(v) for each vertex v of G, a vector space F(e) for each edge e of G, and a linear
transformation Fv P e : F(v) → F(e) for each incident vertex-edge pair v P e.

The vector spaces F(v) and F(e) are called the stalks of F over v or e. The linear
maps Fv P e are sometimes called restriction maps. In agricultural terminology, a sheaf
is a collection of stalks of grain bound together by twine; in mathematical terminology,
a sheaf is a collection of stalks of data bound together by linear maps. The script letter
F is frequently used to denote a sheaf; it is short for faisceau, the French word for sheaf.
The maps Fv P e encode consistency requirements for our data. Whenever consis-
tency can be verified locally, we have a sheaf structure. The simplest example of this is
checking whether a real-valued function on the vertices of a connected graph is con-
stant. This consistency condition can be verified locally: one only needs to check that
the function is constant across each edge. Sheaf theory vastly generalizes this sort of
local consistency checking.

2
 F1
a F2
a
F(1) F(a) F(2)

1 a 2
F1
d F2
b

F(d) d b F(b)

F4
d F3
b
4 c 3
F(4) F(c) F(3)
F4
c F3
c

Figure 1: An illustration of the structure of a sheaf over a graph.

Definition 2.3 (Sections). Let F be a sheaf on a graph G, and let W be a subset of the
vertices of G. A section of F over W is an choice of vectors xv ∈ F(v) for each v ∈ W,
such that whenever v and v 0 are vertices incident to an edge e, we have Fv P e (xv ) =
Fv 0 P e (xv 0 ).

Note that there is a natural way to add any two sections of F over W, simply by
adding their values in each stalk. Because the restriction maps are linear, the sum
of two sections is again a section. Similarly, there is a natural scalar multiplication
on sections, computed stalkwise. This means that the sections of F over W form a
vector space. This space is variously denoted F(W), Γ (W; F), or H0 (W; F). The space
Γ (G; F) of sections of F over all vertices in G is called the space of global sections of F.
Further, note that a global section (xv ) uniquely determines values xe on the edges, by
xe = Fv P e (xv ) = Fv 0 P e (xv 0 ).

Exercise. Verify these claims, that is, show that Γ (W; F) satisfies the axioms of a vector
space, with the specified addition and scalar multiplication operations.

Remark. The term section comes from “cross section.” One often thinks of a sheaf as
having a horizontal portion given by the underlying graph, with a vertical dimension
added by the stalks. A section consists of choosing a consistent copy of the graph
within the stalks of the sheaf, or a cross section of the vertical part of the sheaf.

Example. Let V be a vector space. The constant sheaf V on G has the stalks V(v) = V
for all vertices v and V(e) = V for all edges e, and the restriction maps Fv P e all equal
to the identity. For any subset of vertices W, Γ (W; V) consists of the locally constant

3
 R
1 1
u
R R
1 1
v w
R R R
−1 1

Figure 2: A sheaf with no nontrivial global sections.

functions on W with values in V. (A function is locally constant if it is constant on

each connected component of the subgraph induced by W.)

Example. As a subexample of the previous example, let V = R. The constant sheaf R

plays a special role in the theory of sheaves. Its relationship to a sheaf F determines
the existence of global sections of F.

Every sheaf has at least one global section: the constant section which is zero ev-
erywhere. (This is a consequence of the fact that the space of global sections of a sheaf
is a vector space, and every vector space has a zero element.) However, many sheaves
have no other global sections.

Example. Consider the sheaf in Figure 2. Suppose there is a global section taking value
xu on the vertex u. The condition to be a global section then means xv = xu due to the
upper left edge, and similarly xw = xu due to the upper right edge. But the bottom
edge forces xw = −xv , meaning xu = −xu , which can only be satisfied if all three
values are zero.

In fact, having nontrivial global sections is a very special property. If G is a con-

nected graph with at least one cycle and all stalks have the same dimension, almost any
choice of restriction maps yields a sheaf with no global sections. One consequence of
this fact is that if we try to build a sheaf from noisy real-world measurements, the sheaf
is vanishingly unlikely to have global sections, and we will need either to denoise our
data, or to work with approximate global sections.

Definition 2.4 (Cochains). Let F be a sheaf over a graph G. There are two spaces of
cochains of F. A zero-dimensional cochain (or 0-cochain) is a choice of a vector xv ∈
F(v) for every vertex v; a one-dimensional cochain (or 1-cochain) is a choice of xe ∈

4
F(e) for every edge. The space of zero-dimensional cochains is denoted C0 (G; F), and
the space of one-dimensional cochains is denoted C1 (G; F).

In mathematical terms, the space of 0-cochains is the direct sum of the stalks over
vertices, and the space of 1-cochains is the direct sum of the stalks over edges. That is,

M M
C0 (G; F) = F(v), C1 (G; F) = F(e).
v∈V e∈E

The space of 0-cochains differs from the space of global sections because we do not
impose any consistency requirements on our choices of vectors in each stalk. There-
fore, the space of global sections is a subspace of the space of 0-cochains. In fact, the
space of global sections is the kernel of a particular linear map from the space of 0-
cochains to the space of 1-cochains. This map is called the coboundary map, and is de-
fined as follows: First choose an orientation for the edges of G. This means selecting a
direction for each edge, and yields an incidence number [v : e] ∈ {±1} for each incident
vertex-edge pair v P e so that each edge has both a positive and a negative incidence
number associated to it. This is done by letting [v : e] = +1 if e is directed toward v
and −1 if it is directed away from it.
The coboundary map δ : C0 (G; F) → C1 (G; F) is given on vertex stalks by δ(xv ) =
P
v P e [v : e]Fv P e (xv ), and extends by linearity to all of C0 (G; F). When necessary,
we will disambiguate the sheaf to which δ pertains by a superscript: δF . We can also
define δ by its output on each edge stalk: (δx)e = Fv P e xv − Fu P e xu , where e is an
edge oriented from u to v.

Example. The coboundary map of the constant sheaf R on G, given in matrix form, is
the transpose of the (signed) incidence matrix of G.

Example. Consider again the sheaf in Figure 2. We can represent C0 (G; F) by R3 , and
we can also represent C1 (G; F) by R3 . If we orient each edge so that it is negatively
incident to the vertex with higher number, the coboundary map is given by the matrix
 
1 −1 0
 
δ=  1 0 −1  .

0 −1 −1

Note that this matrix has a trivial nullspace, which reflects the fact that the only global
section of this sheaf is the zero section.

Remark. The term “cochain” comes from algebraic topology. One of its major tools,
homology, deals with understanding “chains” in a topological space, or formal sums

5
of geometrically simple subspaces. For technical reasons, it is often useful to dualize
this theory, producing cohomology, which studies cochains, or linear functionals on
the space of chains. The cochains of sheaves on graphs are algebraically similar to these
cohomological cochains, which is what provoked this use of terminology. Indeed,
sheaf cohomology was a major motivation for the development of sheaf theory.
This cohomological connection is what leads to the common terminology of the
zeroth cohomology (or degree-zero cohomology) for H0 (G; F) = ker δ. We also consider
the cokernel of δ, which is the quotient space C1 (G; F)/(im δ). This space is denoted
H1 (G; F), and is called the first (or degree-one) cohomology of the sheaf F. As a quotient
space, its direct interpretation is less natural than that of the space of global sections of
F. However, the space im δ is analogous to the cut space of a graph. The cut space of a
graph is the space of all real-valued functions on edges spanned by indicator functions
of cut sets. A quick argument shows that this is equal to the space im BT , where B is
the signed incidence matrix of the graph. This is the matrix B with columns indexed
by edges of the graph and rows indexed by vertices of the graph, where Bve = [v : e].
The coboundary matrix is a sort of generalized incidence matrix, so we can interpret
im δ as the space generated by “cuts” of the data communication structure described
by F.
The incidence matrix is most famous in spectral graph theory as a building block
for the graph Laplacian: L = BBT . In order to use spectral methods with sheaves, we
build a Laplacian out of the coboundary map. To do this, we use the inner product on
the stalks (and hence on the spaces of cochains) to construct an adjoint δ∗ to δ. If we
think of δ as simply a block matrix by identifying our vector spaces with the standard
Rn , this adjoint δ∗ is simply the transpose δT .

Definition 2.5 (Sheaf Laplacian). If F is a sheaf on a graph G with coboundary map δ,

the sheaf Laplacian of F is LF = δ∗ δ.

The Laplacian LF is a linear map from C0 (G; F) to itself. It is positive semidefinite

by construction: hx, LF xi = hx, δ∗ δxi = hδx, δxi > 0. Further, its kernel is equal to
H0 (G; F), since ker LF = ker δ∗ δ = ker δ.

Proposition 2.1 (Structure of the sheaf Laplacian). If F is a sheaf on a graph G, the ma-
trix of the sheaf Laplacian LF has a symmetric block structure, with the columns divided into
one partition for each vertex of G. If v1 and v2 are distinct and both incident to the edge e,
then the entry in the (v2 , v1 ) block is −Fv∗2 P e Fv1 P e , and the entry in the (v1 , v1 ) block is
P
v1 P e Fv1 P e Fv1 P e .
∗

Exercise. Show this is true by writing down the block matrices for δ and δ∗ and calcu-

6
Figure 3: Illustration of a graph incidence matrix and a sheaf coboundary matrix.

lating. Use this to show that

X
(LF x)v = Fv∗ P e (Fv P e xv − Fu P e ).
u,v P e

One way to think about cellular sheaves is as a generalization of incidence matrices

and Laplacians of graphs. The coboundary operator for a sheaf looks like an incidence
matrix, but with arbitrary block entries instead of just ±1. See a suggestive illustration
in Figure 3. TODO: Make this figure better

3 Operations on sheaves
3.1 Sheaf morphisms
When we define mathematical objects, we usually want to know how to define rela-
tionships between them. Often the objects themselves are less important than the maps
we can build between them. Linear algebra is a prime example of the supremacy of
maps over objects. Vector spaces, as objects, exist so that we can study linear trans-
formations. Linear maps are far more interesting than vector spaces themselves. We
can take this to an extreme and forget all the internal structure of our objects, looking
instead at the structure of the relationships between different objects of the same type.
This is the point of view of category theory, which serves as a deep organizing prin-
ciple for much of mathematics. A category is formally a collection of objects together
with morphisms between those objects.
The same is true for sheaves. Sheaves have more structure than vector spaces,
enough to be interesting on their own, but relationships between sheaves are still es-
sential. This is why we define mappings or morphisms between sheaves. All we need

7
to deal with to define maps between two sheaves on the same graph is linear algebra.

Definition 3.1 (Sheaf morphisms). Let F and G be two sheaves on a graph G. A mor-
phism or map ϕ : F → G consists of a linear map ϕv : F(v) → G(v) for each vertex v
of G and a linear map ϕe : F(e) → G(e) for each edge e, such that these linear maps
commute with the restriction maps. That is, for each incident vertex-edge pair (v, e),
we have ϕe ◦ Fv P e = Gv P e ◦ ϕv .

This condition is easy to visualize in a diagram showing the relevant vector spaces
and maps between them. The diagram commutes if any two paths along the arrows
represent equal maps.

ϕv
F(v) G(v)
Fve Gve
ϕe
F(e) G(e)
A sheaf morphism can be represented by a large commuting diagram with many
squares like the one above. The fact that the two sheaves are over the same graph
means that the structure of a morphism is easy to define. The individual maps defin-
ing a sheaf morphism assemble into two maps ϕ0 : C0 (G; F) → C0 (G; G) and ϕ1 :
C1 (G; F) → C1 (G; G), and the fact that the maps on stalks commute with restric-
tion maps means that the amalgamated maps commute with the coboundary maps:
δG ◦ ϕ0 = ϕ1 ◦ δF .
Because sheaf morphisms are made out of linear maps, they share a number of
properties with them. Every linear map has a kernel, and so does every sheaf mor-
phism. What may be surprising is that the kernel of a sheaf morphism is a sheaf. The
stalks are easy to define: (ker ϕ)(v) = ker ϕv and (ker ϕ)(e) = ker ϕe . We can restrict
Fv P e to ker ϕv , getting a map Fv P e |ker ϕv : ker ϕe → F(e). If the image of this map lies
in ker ϕe , we have produced a restriction map Fv0 P e : (ker ϕ)(v) → (ker ϕ)(e). Sup-
pose x ∈ ker ϕv . Then ϕv x = 0, so Gv P e ϕv x = 0. Because Gv P e ◦ ϕv = ϕe ◦ Fv P e ,
we know ϕe Fv P e x = 0. But this means that Fv P e x ∈ ker ϕe , as required.
Remark. The sort of argument used above is known as a diagram chase. They can become
quite complicated, and proofs of this kind are usually best communicated by drawing a
commutative diagram, and pointing at various objects in the diagram while discussing
the fate of an element as it is transferred through various maps.
A similar diagram chasing argument shows that sheaf morphisms can be com-
posed just like linear maps. Composing the stalkwise maps of two sheaf morphisms
yields another sheaf morphism. Similarly, the image of a sheaf morphism is again a
sheaf.

8
Exercise. Show that if ϕ : F → G and ψ : G → H are sheaf morphisms, then the
collection of linear maps (ψσ ◦ ϕσ )σ defines a sheaf morphism F → H.

Exercise. Suppose ϕ : F → G is a sheaf morphism. Use an argument similar to the

one that shows that ker ϕ is a sheaf to show that there is a naturally defined sheaf im ϕ
whose stalks are (im ϕ)(σ) = im ϕσ and whose restriction maps are induced by those
of G.

For every sheaf F, there is an identity morphism id : F → F, which restricts to the

identity map on each stalk. A sheaf morphism ϕ : F → G is an isomorphism if there
exists a morphism ψ : G → F which is an inverse of ϕ; that is, ϕ◦ψ = id and ψ◦ϕ = id.
One way to think of a sheaf isomorphism is as representing a “change of basis” of the
sheaf. From an algebraic perspective, two isomorphic sheaves behave identically.

Exercise. Show that a sheaf morphism ϕ : F → G is an isomorphism if and only if

each component linear map ϕσ is invertible.

However, if we care about the inner product structure of the stalks of a sheaf, there
is a finer distinction to be made. Invertible matrices preserve all algebraic properties
of the vector spaces they map between, but they do not in general preserve the inner
product structure. Similarly, sheaf isomorphisms do not automatically preserve the
inner product structure. A unitary sheaf isomorphism is one where the maps on stalks
are unitary maps of inner product spaces; that is, these maps must preserve the inner
product.
Just as the space of linear maps from one vector space to another forms a vector
space itself (consider the space of m×n matrices as the space of linear maps Rn → Rm ,
for instance), so does the space of sheaf morphisms. The sum of two sheaf morphisms,
taken by adding the component maps on stalks, is again a sheaf morphism. Scalar
multiples of sheaf morphisms are again sheaf morphisms as well. We denote the space
of sheaf morphisms F → G by Hom(F, G). That is, ϕ ∈ Hom(F, G) if it is a sheaf
morphism φ : F → G.

Exercise. Show that Hom(F, G) is a vector space under the operations described above.

Example. Let F be a sheaf on G, and consider the set of morphisms from the constant
sheaf R to F. A linear map ϕv : R → F(v) is completely determined by ϕv (1), so
we may think of a morphism ϕ : R → F as a collection of elements xv ∈ F(v) and
xe ∈ F(e). The commutativity condition for being a sheaf morphism is that Fve ◦ ϕv =
ϕe ◦ Rv P e . Since Rv P e is the identity, we have Fv P e xv = xe . In other words, a
morphism from R to F is the same as a choice of xv ∈ F(v) and xe ∈ F(e) so that

9
Fv P e xv = xe whenever v P e. This is precisely the same information that we get from
a global section of F! Therefore, we have

Proposition 3.1 (Global sections are morphisms). If F is a sheaf on G, there is a natural

isomorphism between the vector spaces Hom(R, F) and Γ (G; F).

Proposition 3.2 (Global sections are functorial). Let ϕ : F → G be a sheaf morphism. This
morphism induces a natural linear map Γ (ϕ) : Γ (G; F) → Γ (G; G). Further, if ψ : G → A is
another sheaf morphism, we have Γ (ψ ◦ ϕ) = Γ (ψ) ◦ Γ (ϕ).

Proof. Note that ϕ induces a map ϕ0 : C0 (G; F) → C0 (G; G) that commutes with the
coboundaries of F and G. In particular, then, if x ∈ ker δF , then δG ϕ0 (x) = ϕ1 δF x = 0,
so ϕ0 (x) ∈ ker δG . This means that ϕ0 induces a map Γ (ϕ) : Γ (G; F) → Γ (G; G) by
restriction to ker δF . It is obvious that ψ0 ◦ ϕ0 = (ψ ◦ ϕ)0 , and since Γ (ψ),Γ (ϕ), and
Γ (ψ ◦ ϕ) are obtained by restriction of these maps, we get Γ (ψ ◦ ϕ) = Γ (ψ) ◦ Γ (ϕ).

Remark. The operation of taking global sections takes a sheaf and produces a vector
space. The fact that this operation behaves nicely with respect to sheaf morphisms and
linear maps means that taking global sections is functorial. It translates information
from the category of sheaves to the category of vector spaces in a way that respects
relationships between sheaves.
Remark. The isomorphism Hom(R, F) ' Γ (G; F) is natural in the sense that it com-
mutes with sheaf morphisms. That is, given a sheaf morphism F → G, we get mor-
phisms Hom(R, F) → Hom(R, G) and Γ (G; F) → Γ (G; G), and the square
'
Hom(R, F) Γ (G; F)

'
Hom(R, G) Γ (G; G)

commutes. This means that for every purpose which we can understand categorically,
we can consider Hom(R, F) and Γ (G; F) to be “the same thing.”

Exercise. What is the linear map Hom(R, F) → Hom(R, G) in the diagram above?

3.2 Homological Algebra

This section is motivated by a very natural question, but takes an unavoidable detour
through some more sophisticated mathematical theory. It may be advisable to skip it
on a first reading.
A sheaf morphism ϕ : F → G induces a morphism Γ ϕ : H0 (G; F) → H0 (G; G). But
even if the component maps of ϕ are all surjective, the induced linear transformation

10
 ϕ
ker(ϕ) F G
0 1
0 R R
0 1 0

1 0
R R 0

0 1 0
0 1
0 R R

Figure 4: An exact sequence of sheaves with a non-exact sequence of global sections.

Γ ϕ might not be. That is, G might have global sections that do not come from global
sections of F. This is a bit surprising: when a linear map T : Rn → Rm is surjective,
we can always solve an equation of the form T (x) = y.

Example. Consider the two sheaves F and G in Figure 4. The sheaf F is the constant
sheaf R, while G has vertex stalks R and edge stalk 0. There is an easily constructed
sheaf morphism ϕ : F → G which is the identity on vertex stalks and the zero map
on the edge stalk. Note that H0 (G; F) is one-dimensional, consisting of constant func-
tions, while H0 (G; G) ' C0 (G; G) is two-dimensional. Thus Γ ϕ : H0 (G; F) → H0 (G; G)
cannot be surjective.

Homological algebra is one approach to understanding why this breaks down: why
is it not always possible to “lift” a global section over a surjective sheaf morphism
F → G?
We first observe that this strangeness only happens with surjective sheaf morphisms.
An injective sheaf morphism induces an injective map on global sections. Somehow,
injectivity is a local condition, while surjectivity requires us to integrate global infor-
mation.

Exercise. Show that if ϕ : F → G is an injective morphism—that is, ϕσ is an injective

linear map for each vertex or edge σ—then Γ ϕ is an injective linear map H0 (G; F) →
H0 (G; G).

The central concept of homological algebra is the exact sequence of maps. This is a
series of sheaf morphisms or linear transformations
ϕk−1 ϕk ϕk+1
··· Fk−1 Fk Fk+1 ···

11
where the image of one morphism is equal to the kernel of the subsequent morphism.
That is, im ϕi−1 = ker ϕi for all i. A special sort of such morphism is a short exact
sequence. This has five terms, two of which are zero.

i q
0 H F G 0

Such a sequence is very special. It must be the case that H = ker q and G = F/H. Short
exact sequences therefore encode a sheaf F, a subsheaf H thereof, and the quotient
G = F/H.
We can take the global sections of each sheaf in a short exact sequence of sheaves,
and we get a sequence

i q
0 H0 (G; H) H0 (G; F) H0 (G; G) 0.

Unfortunately, this sequence is no longer exact in general. In particular, the condition

im q = ker(0) = H0 (G; G) does not hold. This is exactly the problem we noticed before,
that a surjective sheaf morphism does not necessarily turn into a surjective morphism
on global sections.
Homological algebra comes to the rescue by extending this sequence in a way that
makes it exact. We get what is called the long exact sequence on the cohomology of the
sheaves in the original sequence:

i q d i
0 H0 (G; H) H0 (G; F) H0 (G; G) H1 (G; H) ···

This now says that im q = ker d. If we know d, we can see which sections of G lift
to sections of F by checking if they lie in ker d. In particular, if H1 (G; H) is the zero
vector space, ker d must in fact be all of H0 (G; G), so every section of G can be lifted to
a section of F. In short:

Proposition 3.3. Suppose ϕ : F → G is a surjective sheaf morphism, and H1 (G; ker ϕ) = 0.

Then any global section of G lifts to a global section of F.

In fact, sections lift precisely when d is the zero map. We say that the connecting
morphism d measures the failure of q to induce a surjective map on sections. The exis-
tence of the map d relies on the quotienting performed in the construction of H1 : it is
only well-defined as a map to equivalence classes.

Example. Continuing the simple example in Figure 4, the kernel of ϕ is the sheaf
ker(ϕ) with vertex stalks 0 and edge stalk R. Then H0 (G; ker(ϕ)) = 0 and H1 (G; ker(ϕ)) '
R, which illustrates the possibility that Γ φ may not be surjective.

12
 This result gives one interpretation for the first cohomology of a sheaf, in terms of
what it says about relationships between different sheaves. While these concepts may
seem even more hopelessly abstract than the already-abstract notions of sheaves and
morphisms, the reader should rest assured that the exposition here is far simpler than
nearly any other explanation of sheaf cohomology or homological algebra.
These tools are leveraged in [9, 10] to build a sheaf-based theory of signal sampling.
The signals one desires to sample are sections s of a sheaf F, and but we are only able
to observe the sections ϕ(s) of some sheaf G induced by a sheaf morphism ϕ : F → G.
When H1 (ker ϕ) is zero, sampling makes sense: every sampled signal corresponds to
at least one actual signal. When H0 (ker ϕ) is zero, perfect reconstruction of signals is
possible.
Homological algebra is a vast subject, with branching realms of application, and
this discussion only scratches the surface of it. The interested reader might consult
a book like [2], but a warning is in order: a typical prerequisite for reading and un-
derstanding a book on homological algebra is to have read and understood a book on
homological algebra.

3.3 Sheaves and graph homomorphisms

There are several different notions of graph homomorphism. The definition we will
use is more permissive than some. For our purposes, a graph homomorphism f from
G = (VG , EG ) to H = (VH , EH ) is given by a map fV : VG → VH and a map fE :
EG → EH ∪ VH such that if v is incident to e, then either fV (v) is incident to fE (e) or
fV (v) = fE (e). This means that an edge (or indeed an entire induced subgraph) can
be collapsed onto a single vertex. A competing definition of graph homomorphism
is a map on vertices that preserves the adjacency relation, which is not well suited
to our purposes. The explicit treatment of edges in our notion of homomorphism is
necessary for use with sheaves, since both edges and vertices carry data.
Remark. This notion of graph homomorphism is what we get when we consider graphs
as cell complexes or simplicial complexes, and as such it extends to higher-dimensional
structures than graphs.
If f : G → H is a graph homomorphism, we can transfer sheaves on G or H across f
to get sheaves on H or G. These operations are known as the pushforward and pullback
of sheaves across f.

Definition 3.2 (Pullback). Let f : G → H be a graph homomorphism, and let F be a

sheaf on H. The pullback of F over f, f∗ F, is a graph on G with stalks (f∗ F)(σ) = F(f(σ))
and restriction maps (f∗ F)v P e = Ff(v) P f(e) .

13
 We can lift cochains of F on H to cochains of f∗ F on G, and in fact sections of F lift
to sections of f∗ F.

Proposition 3.4. There exist linear maps (f∗ )i : Ci (H; F) → Ci (G; f∗ F) that commute with
∗F
the coboundary maps of F and f∗ F. That is, δf ◦ (f∗ )0 = (f∗ )1 ◦ δF .

Proof. For any vertex v of H, there is an obvious map F(v) → f∗ F(v 0 ) whenever f(v 0 ) =
v. We can assemble these into a map F(v) → f(v 0 )=v f F(v ). Then combining
∗ 0
L
∗ )0 : C0 (H; F) =
v∈H F(v) →
L
these maps
L over verticesv of H, we get a map (f
f(v 0 )=v f F(v ) = v 0 ∈G f F(v ) = C (G; f F). A completely analogous
∗ 0 ∗ 0 0 ∗
L L
v∈H
argument furnishes a map (f∗ )1 : C1 (H; F) → C1 (G; f∗ F). Another, perhaps simpler,
way to think of this map is as letting ((f∗ )i x)σ = xf(σ) .
∗F
Commutativity will be satisfied if for every edge e of H, we have (δf (f∗ )0 x)e =
((f∗ )1 δF x)e . The right hand side is equal to (δF x)f(e) , while the left hand side is equal
to

(f∗ F)h(e) P e ((f∗ )0 x)h(e) − (f∗ F)t(e) P e ((f∗ )0 x)t(e)

= Ff(h(e)) P f(e) xf(h(e)) − Ff(t(e)) P f(e) xf(t(e)) = (δF x)f(e) .

If x ∈ C0 (H; F), f∗ x ∈ C0 (G; f∗ F), and if δF x = 0, then δf

∗F
f∗ x = f∗ δF x = 0. Thus,
if x is a section of F, f∗ x is a section of f∗ F. Not every section of f∗ F necessarily arises
in this way, of course, but this property is a major reason for constructing f∗ F.
The pushforward of a sheaf is a little bit more complicated to define.

Definition 3.3 (Pushforward). Let f : G → H be a graph homomorphism, and let F be

a sheaf on G. The pushforward of F over f, f∗ F, is a sheaf on H with stalks f∗ F(σ) =
Γ (f−1 (σ); F).
The restriction maps are slightly more complicated to specify. Given an element
x ∈ Γ (f−1 (v); F) and an edge e incident to v, every edge e 0 ∈ f−1 (e) is incident to a
unique vertex v(e 0 ) ∈ f−1 (v). The local section x has a value xv(e 0 ) at each of these
P
vertices, and hence we can define (f∗ F)v P e (x) = e 0 ∈f−1 (e) Fv(e 0 ) P e 0 (xv(e 0 ) ).

If a graph homomorphism sends edges only to edges, the pushforward is easier to

define. In this case, f∗ F(σ) = f(τ)=σ F(τ) and (f∗ F)v P e = f(σ)=v,f(τ)=e Fσ P τ .
L L

Sections of F over G push forward to sections of f∗ F over H. In fact, these two

sheaves have the same space of global sections.

Proposition 3.5. There is an isomorphism f∗ : H0 (G; F) → H0 (H; f∗ F).

14
Proof. We will prove this in the case that f does not send any edge to a vertex, although
it is true in general. This means that f∗ F(v) ' f(u)=v F(u) for every vertex v of H,
L

and similarly for edges. Let x be a section of F and define (f∗ x)v = f(u)=v xu . This
L

is clearly an injective map into C0 (H; f∗ F). Note that if v, v 0 P e,

M
f∗ Fv P e (f∗ x)v = Fu P e xu
f(u)=v
f(h)=e

and
M
f∗ Fv 0 P e (f∗ x)v 0 = Fu 0 P e xu 0 .
f(u 0 )=v 0
f(h)=e

For each edge h of G with f(h) = e, the corresponding terms in the sum are equal,
because this is the condition for x to be a section of F. Thus f∗ x is a section of f∗ F.
Conversely, this same equation shows that the condition for some y to be a section of
f∗ F is precisely the requirement that it be in the image of f∗

There are two operations which combine two sheaves on the same graph into a
single sheaf.

Definition 3.4 (Direct sum). If F and G are sheaves on a graph G, their direct sum F ⊕ G
is the sheaf with stalks (F⊕G)(v) = F(v)⊕G(v), (F⊕G)(e) = F(e)⊕G(e) and restriction
maps (F ⊕ G)v P e = Fv P e ⊕ Gv P e .

One should think of the direct sum of two sheaves as combining two different data
structures over the graph G in an independent way. Neither influences the other. A
section of F ⊕ G is equivalent to a pair of a section of F and a section of G.

Example. The zero sheaf 0, which assigns the zero vector space to each vertex and
edge, is an identity for the direct sum. That is, for any sheaf F, F ' 0 ⊕ F.

Definition 3.5 (Tensor product). If F and G are sheaves on a graph G, their tensor prod-
uct F ⊗ G is the sheaf with stalks (F ⊗ G)(v) = F(v) ⊗ G(v), (F ⊗ G)(e) = F(e) ⊗ G(e)
and restriction maps (F ⊗ G)v P e = Fv P e ⊗ Gv P e .

The tensor product is harder to interpret. Words like “twisting” and “multiplica-
tion” tend to come up when trying to describe this operation. One way to think of this
is that it is possible to “add” and “multiply” sheaves, and these operations satisfy at
least a distributive property: F ⊗ (G ⊕ H) ' (F ⊗ G) ⊕ (F ⊗ H).

Example. The constant sheaf R is an identity of sorts for the tensor product. That is,
for any sheaf F, F ' R ⊗ F.

15
Exercise. Show why R ⊗ F ' F for any sheaf F.

One can naturally identify the coboundary map of F ⊕ G with the direct sum of the
respective coboundary maps; the analogous statement does not hold for the cobound-
ary map of F ⊗ G. (This is because direct sums of vector spaces do not distribute over
tensor products.)
Why care about these operations? One reason to like pushforwards is that they cor-
respond naturally to a sort of abstraction or modularization process. Suppose we have
a sheaf on a graph G that represents some system, made of atomic pieces. We might
want to view this system “from farther away,” by treating subsystems—represented
by induced subgraphs of the graph—as black boxes connected together. The resulting
graph G 0 of the zoomed-out system has one vertex for each subsystem, with the same
edges between systems. This means that there is a homomorphism G → G 0 , which
sends all vertices and edges in a subsystem to the vertex representing them in G 0 ; the
pushforward over this homomorphism represents the black-boxed system.
The exact semantics of pushforwards and other sheaf operations will depend on
the choices made in modeling the system. They are tools that offer formal ways to
represent things we might do to systems—ways to combine or transform them.

3.4 Product graphs

There are several notions of the product of two graphs. Perhaps the most intuitive is
the Cartesian product GH. This is the graph with vertex set V(G) × V(H), and an
G = vG and vH ∼ vH or vG ∼ vG and
0 , v 0 ) if either v
edge between (vG , vH ) and (vG 0 0 0
H
0 . That is, the edge set is E(G) × V(H) ∪ V(G) × E(H). (See Figure 5.) This
vH = vH
graph carries two projection homomorphisms πG : GH → G and πH : GH → H.
If G and H carry sheaves F and G, there is a natural sheaf on GH given by F  G =
π∗G F ⊗ π∗H G. More concretely, F  G(vG , vH ) = F(vG ) ⊗ G(vH ), and the stalk associated
0 , v ) is F(v ∼ v 0 ) ⊗ G(v ), and similarly for
with the edge between (vG , vH ) and (vG H G G H
0 ). The restriction map from (v , v ) to (v ∼
the edge between (vG , vH ) and (vG , vH G H G
0 , v ) is F
vG 0 ) ⊗ IdG(v ) .
H vG P(vG ∼vG H

If F and G are the constant sheaf R on their respective graphs, then F  G is the
constant sheaf R on GH.
Remark. The notation F  G is adapted from the topological world, where the most
important product is the Cartesian product, and this “outer product” of sheaves is
frequently useful.

16
 u1 f u2

(v1 , f)
v1
(v1 , u1 ) (v1 , u2 )

(e, u1 )

(e, u2 )
e

(v2 , u1 ) (v2 , u2 )
v2
(v2 , f)

Figure 5: A simple Cartesian product graph.

4 Spectral sheaf theory

The sheaf Laplacian as defined in Section 2 is an invariant of sheaves on a labeled graph
with specified stalks and orthonormal bases. Unlike the graph Laplacian, however, it
is not a complete invariant. That is, there are non-isomorphic sheaves on the same
graph which have the same sheaf Laplacian. A trivial reason for this is that the sheaf
Laplacian does not record very much about the structure of the sheaf over the edges of
the graph, but even more generally, there is too much room for redundant realizations
of the same matrix structure.

Example. The two sheaves in Figure 6 both have sheaf Laplacian

" #
2 −2
−2 4

but are not isomorphic.

Remark. One important fact about sheaves is that the algebraic structure can make
parts of the underlying graph “invisible.” We can effectively delete a vertex or edge
by assigning it the zero vector space. This is an extension of the way that one may
delete edges from a graph by setting their weights to zero. Note that this then allows
for “half-open” edges that are incident to only one vertex.
Although the sheaf Laplacian is not a complete invariant of sheaves, it does con-
vey a lot of information about the sheaf. One obvious piece of data preserved by the
Laplacian is the space of global sections, since ker LF = ker δ. The smallest nontrivial

17
 p p
1 2 2 2
R R R R R R

1 0 0
p
2

R R R R

0 0 0 0
0 0

Figure 6: Two nonisomorphic sheaves with identical sheaf Laplacians

eigenvalue of a sheaf Laplacian gives us information about how close the sheaf is to
having more global sections. This is a consequence of the Courant-Fischer theorem,
which states that for an n × n symmetric matrix A with eigenvalues λ1 6 λ2 6 · · · λn ,
 
hy, Ayi
λk = min max .
dim Y=k y∈Y,y6=0 hy, yi

Applying this to the sheaf Laplacian, with k = dim(H0 (G; F)) + 1, we see that Y must
contain H0 (G; F) as well as the eigenvector of LF corresponding to λk , which mini-
mizes
hy, LF yi kδyk2
=
hy, yi kyk2
subject to the constraint that y is orthogonal to H0 (G; F).
The spectrum of the sheaf Laplacian interacts in interesting ways with the sheaf
operations described above. These often generalize results known for the spectra of
graph Laplacians.

4.1 Basic facts about sheaf Laplacians

Proposition 4.1. Let V be the constant sheaf on a graph G. The sheaf Laplacian of V, with
respect to an orthonormal basis of V, is LG ⊗ idV , where LG is the graph Laplacian of G.

A common question in spectral graph theory is how the spectrum of a graph changes
as we manipulate the graph. These tend to be the easiest results to extend to spectral
sheaf theory, since the analogous theorem statements are usually immediately evident.
A useful concept when studying the spectra of related matrices is the interlacing
of eigenvalues.

Definition 4.1. Let A, B be n×n matrices with real spectra, and let λ1 6 λ2 6 · · · 6 λn
be the eigenvalues of A and µ1 6 µ2 6 · · · 6 µn be the eigenvalues of B. We say the

18
eigenvalues of A are (p, q)-interlaced with the eigenvalues of B if for all k, λk−p 6
µk 6 λk+q . (We let λk = λ1 for k < 1 and λk = λn for k > n.)

We now show that the eigenvalues of sheaf Laplacians are interlaced after deleting
a subgraph.

Theorem 4.2 (Eigenvalue interlacing for the sheaf Laplacian). Let F be a sheaf on a graph
G, C a collection of edges of G, and let H = G \ C denote G with the edges in C removed.
Let G be the sheaf with the same vertex stalks as F but with all edge stalks over edges not in C
set to zero. Then the eigenvalues of LH are (t, 0)-interlaced with the eigenvalues of LG , where
t = codim H0 (G; G) = dim C0 (G; F) − dim H0 (G; G).

Proof. This is a standard sort of argument in spectral graph theory. We use Rayleigh
quotients to bound eigenvalues in terms of the quadratic form defined by the Lapla-
cian. Notice that LH = LG −LC , where LC is the Laplacian of G. By the Courant-Fischer
theorem, we have
 
hy, LG yi − hy, LC yi
µk = min max
dim Y=k y∈Y,y6=0 hy, yi
 
hy, LG yi
> min max
dim Y=k y∈Y∩H0 (G;G),y6=0 hy, yi
 
hy, LG yi
> min max = λk−t
dim Y=k−t y∈Y,y6=0 hy, yi

and
 
hy, LG yi
λk = min max
dim Y=k y∈Y,y6=0 hy, yi
 
hy, LG yi − hy, LC yi
> min max = µk .
dim Y=k y∈Y,y6=0 hy, yi

Definition 4.2 (Covering map). A graph morphism f : G → H is called a covering map

if for every v ∈ H, the number of vertices u with f(u) = v is constant, there are no
edges that map to vertices, and the number of edges incident to u ∈ G is the same as
the number of edges incident to f(u) ∈ H. (See Figure 7.)

Proposition 4.3. Let f : G → H be a covering map of graphs. If F is a sheaf on H, the

spectrum of Lf∗ F contains the spectrum of LF .

19
 f∗ F(u1 ) = F(v)
G
f∗ F(u2 ) = F(v)
f

F(v)

Figure 7: A covering map of graphs and the sheaf pullback

Proof. Consider the map f∗ : Ci (H; F) → Ci (G; f∗ F) given by (f∗ x)v = xf(v) . If x is an
eigenvector of LF with eigenvalue λ, we have
X
(Lf∗ F f∗ x)v = ((f∗ F)∗ve (f∗ F)ve (f∗ x)v − (f∗ F)∗ve (f∗ F)we f∗ xw )
v P e,w P e
X
∗ ∗
= Ff(v)e Ff(v)e xf(v) −Ff(v)e Ff(w)e xf(w) = (LF x)f(v) = λxf(v) = λ(f∗ x)v .
f(v) P e,f(w) P e

Since every eigenvector of LF produces a corresponding eigenvector of Lf∗ F with the

same eigenvalue, the spectrum of Lf∗ F contains the spectrum of LF .

Note that this strengthens the result that sections of F lift to sections of f∗ F to state
that when f is a covering map, eigenvectors of LF lift to eigenvectors of Lf∗ F .
Cartesian products of sheaves have spectra completely determined by their factors.
This is a generalization of a result for Cartesian products of graphs.

Proposition 4.4. Let F be a sheaf on a graph G and G a sheaf on a graph H. The Laplacian
spectrum of the sheaf F  G on GH consists of all sums λ + µ, where λ is an eigenvalue of
LF and µ is an eigenvalue of LG .

Proof. Let’s look at C0 (GH; F  G) and C1 (GH; F  G). Note that

   
M M M
C0 (GH; F  G) = F(u) ⊗ G(v) '  F(u) ⊗  G(v) .
u∈V(G) u∈V(G) u∈V(H)
v∈V(H)

20
This is simply C0 (G; F) ⊗ C0 (H; G). Similarly,
   
 M   M
C1 (GH; F  G) '  F(u) G(f) F(e) G(v)

 ⊗ ⊕
  ⊗ 

u∈V(G) e∈E(G)
f∈E(H) v∈V(H)
       
M M M M
' F(u) ⊗  G(f) ⊕  F(e) ⊗  G(v)
u∈V(G) f∈E(H) e∈e(G) v∈V(H)

= C0 (G; F) ⊗ C1 (H; G) ⊕ C1 (G; F) ⊗ C0 (H; G) .

With a little work, best done in the privacy of one’s own home, it can be shown that
under this identification, the coboundary matrix of F  G is
" #
idC0 (G;F) ⊗δG
δFG = ,
δF ⊗ idC0 (H;G)

from which we can conclude that LFG = idC0 (G;F) ⊗LG + LF ⊗ idC0 (H;G) . This means
that if x is an eigenvector of LF with eigenvalue λ and y is an eigenvector of LG with
eigenvalue µ, then LFG x ⊗ y = idC0 (G;F) ⊗LG x ⊗ y + LF ⊗ idC0 (H;G) x ⊗ y = λx ⊗ y +
µx ⊗ y = (λ + µ)(x ⊗ y).

A number of other interesting results related to sheaves and their Laplacians may
be found in [7]. Among these are results on:

• spectra of pushforward sheaves

• a version of “effective resistance” for sheaves, treating them as a sort of general-

ization of an electrical network.

• spectral sparsification of sheaves, where a number of edges may be removed from

a graph while keeping the sheaf Laplacian spectrum approximately the same.

• harmonic functions on sheaves, which are the nearest one can get to a section
when certain values have been specified.

TODO: reproduce some of these results here

5 Directions for applications

It’s finally time to talk about what this all might be good for. I will here sketch a few
points of contact between sheaf theory and problems and phenomena we might see in
the real world. These are not fully developed applications. No one (as far as I know)

21
has built anything using them yet. But I think they are sufficiently varied and convinc-
ing to show that sheaves are a natural way to represent a number of different real-world
situations.

5.1 Sensors
Here’s a simple example of a sheaf that suggests itself in certain applications. Consider
a set of sensors observing subsets of some domain, with fields of view that overlap.
Say that sensor i can see some subset Ui ⊆ X. We build a graph G using the data of
these subsets: add one vertex for each sensor, and an edge between sensor i and sensor
j when Ui ∩Uj 6= ∅. We assume that what each sensor observes is a function Ui → Rn .
Clearly, if sensor i and sensor j are looking at the same thing, the functions they see
should agree on the intersection of Ui and Uj . This condition translates into a sheaf
on G. For the vertex corresponding to sensor i, the stalk is F(i) = {f : Ui → Rn }, the
vector space of functions on Ui with values in Rn . The stalk over the edge between i
and j is F(i ∼ j) = {f : Ui ∩ Uj → Rn }, the space of functions on the overlap of the
two sensor domains. The restriction maps are then just restriction of functions to the
common domain.
Remark. One might call this the sheaf of functions subordinate to a cover. It is one of the
canonical examples of a sheaf, and this is where the term “restriction maps” originates—
they abstract the notion of restriction of functions to a smaller domain.
Under the assumption that the sensors see the whole domain X, the global sections
of this sheaf are precisely the functions X → Rn . Why is this a useful result? It al-
lows us to check the conditions of consistency locally, without having to construct a
global picture explicitly. If sensors can communicate according to the connections in
the graph G, they can check consistency completely locally.

5.2 Diffusion
The existence of a Laplacian immediately suggests consideration of its associated dif-
ferential equation. This is the Laplacian flow, or diffusion

ẋ = −LF x.

Since LF is positive semidefinite with kernel equal to H0 (G; F), the trajectories of this
dynamical system converge to global sections of F. With a little more work (write
out the closed form solution in terms of the eigendecomposition of LF ) it’s possible to
show that the limiting section is in fact the orthogonal projection of the initial condition

22
onto H0 (G; F). This could be combined with the sensing sheaf above to give a simple
distributed algorithm for ensuring consistency of sensor observations: just run the
diffusion algorithm until convergence.

5.2.1 Opinion dynamics

Graph Laplacian-based diffusions are often used as a building block for the construc-
tion or study of network dynamics. Sheaf Laplacians can add richness to these models
while remaining analytically tractable. Opinion dynamics in social networks offer an
illustrative example. Perhaps the simplest model of opinion dynamics posits a social
network described by a graph G, where each agent has a one-dimensional space of
opinions. The dynamics are described by the graph Laplacian flow on G, and eventu-
ally converge to consensus.
Replacing G with a sheaf on G allows us to model various more interesting aspects
of the system:

• We can add extra dimensions to the opinion space by increasing the dimension
of the vertex and edge stalks

• We can implement links that force opinions apart for certain agents by changing
the sign of one of the restriction maps on an edge

• We can model the difference between an agent’s privately-held opinion and the
one communicated to others by changing edge stalks and restriction maps.

While these additions are still limited by the fact that the overall dynamics are
linear, they introduce interesting behavior in such a system, and can all be analyzed
within the sheaf framework. Further, the linear dynamics can be used as a building
block for more sophisticated models. Some ideas in this direction are explored in [8].

5.3 Distributed consensus

Diffusion on graphs is also used to specify consensus dynamics on networks specifi-
cally designed for the purpose. Suppose we have a collection of agents connected ac-
cording to the edges in a graph, and each has some internal state in some vector space
V. We want them to communicate over the edges of the graph in order to come to an
agreement on a value. We can represent this condition as saying we wish the agents
to reach a global section of the constant sheaf V. This can be achieved by having them
follow the Laplacian flow associated to the sheaf.
This requires each agent to communicate its full state to all of its neighbors. This is
perhaps an onerous requirement, but is not necessary. Sheaf theory can help us reduce

23
the bandwidth requirements.

Definition 5.1 (Approximation to a sheaf). Let G be a graph, and let G be a sheaf on

G. We say that a sheaf F on G is an approximation to G if there exists a morphism a :
F → G which is an isomorphism on vertex stalks, and which induces an isomorphism
Γ (G; G) → Γ (G; F).

If V is a vector space, we denote the constant sheaf with stalk V by V, and say that
F is an approximation to the constant sheaf if F is an approximation to V.

Proposition 5.1. If F is an approximation to V, then it is isomorphic to a sheaf with vertex

stalks V where the restriction maps Fv P e : V → F(e) and Fv 0 P e : V → F(e) are equal.

Proof. Note that because a : V → F is an isomorphism on vertex stalks, F is clearly

isomorphic to a sheaf with vertex stalks V. For every edge e we have the diagram

1
V V
1 Fv P e
ae
V F(e)
,
1 Fv 0 P e
1
V V

and the only way it can commute is if Fv P e = Fv 0 P e = ae .

The proof of this proposition shows that specifying an approximation to V is the

same as specifying a morphism ae : V → We for each edge e of G. Further, in order
to produce an approximation to V, the ae must assemble to a map a : C1 (G; V) →
C1 (G; F) = e∈E We such that ker(a ◦ δV ) = ker δV . This holds if ker a is contained
L

in a complement to im δ; equivalently, the projection map π : C1 (G; V) → H1 (G; V)

must be an isomorphism when restricted to ker a.
This inspires a way to construct an approximation to the constant sheaf. Choose a
subspace Ke of V for each edge e of G and define ae to be the projection map V → V/Ke .
If e∈E Ke has the same dimension in H1 (G; V) as in C1 (G; V), then a =
L L
e∈E ae
defines the edge maps giving an approximation to V. (The vertex maps may be taken
to be the identity.)
A spectrally good approximation to the constant sheaf (satisfying a few other con-
ditions) is analogous to an expander graph. It is possible that expander sheaves would
allow for implementations of faster consensus algorithms for high-dimensional data

24
 on graphs by reducing the amount of communication needed to ensure convergence.
Some exploration of these ideas in a language closer to that of traditional spectral graph
theory is in [4]. Constructing such sheaf approximations and expanders is a surpris-
ingly deep problem.

5.4 Distributed optimization

Graph consensus dynamics are often used as a component in more complex algo-
rithms, like distributed optimization. The standard formulation casts an optimization
problem with local objectives fv corresponding to vertices with the goal of minimizing
P
v fv (x). This is converted into a more naturally distributed problem by duplicating
P
state variables: minimize v fv (xv ) subject to the constraint that xv = xu for all ver-
tices u and v.
Those who have developed a sense for the applicability of cellular sheaves1 will
immediately interpret this condition as saying that the collection of the xv must form
a section of the constant sheaf. Various approaches can then be used to design a dis-
tributed algorithm to solve the optimization problem. Typically these will combine a
local optimization process, like gradient descent, with a consensus process, like local
averaging. The natural question, then, is whether we can extend these algorithms to
solve distributed optimization problems over other sheaves, and whether there might
be any use for this.
The answer to both questions is yes. Sheaf diffusion is the key component. The
sheaf Laplacian can serve as a drop-in replacement for the graph Laplacian in algo-
rithms designed for standard distributed optimization. This straightforward general-
ization is discussed in [5].
When would you want to optimize over the sections of a non-constant sheaf? One
situation where this might be useful comes from the sensor network example that be-
gan this section. A network of sensors observing different regions of a domain (or
different aspects of some abstract domain) could use a properly constructed optimiza-
tion problem to cooperatively improve their local estimates of the observed data.

5.5 Learning sheaves

From a network science perspective, it may be interesting to try to find a sheaf for which
a given collection of signals is close to being sections. That is, we are given a number
of vectors xi ∈ C0 (G; F), and wish to find both a graph G and a sheaf F on G so that
1
Currently a somewhat rarefied group! The purpose of these notes is to expand it.

25
P T is small. It turns out that the space of sheaf Laplacians is a convex cone, so
i xi LF xi
P
we can cast this as a convex optimization problem. Seeking to minimize i xTi LF xi
alone leads to a minimum at LF = 0, so we need to add regularization terms. Details
can be found in [6].
What does the learned LF tell us? We can extract an underlying graph structure
from the sparsity pattern of the Laplacian. These are connections implied by the data.
Each edge further includes a description of the tendencies of the relationships in the
data: an edge “pushes” the data on its incident vertices to lie in some algebraic rela-
tionship.

6 Where to go from here

6.1 Beyond graphs
In algebraic topology, graphs have higher-dimensional generalizations known as sim-
plicial complexes and cell complexes. Graphs are one-dimensional cell complexes, and
simple graphs are one-dimensional simplicial complexes. Sheaves can be defined on
cell complexes and simplicial complexes by adding stalks for higher-dimensional cells
and restriction maps for each incidence relation between cells. These give us a way to
encode higher-order consistency conditions, but these do not appear in quite the way
one might expect. The coboundary map extends to a sequence of coboundary maps
between cochain spaces of adjacent cell degrees, but the significance of the kernel of
higher coboundary maps is less obvious.
Even more generally, it is possible to define a sheaf over a partially-ordered set; this
is the approach taken by Michael Robinson in his work on sheaves and data analytics.
This case subsumes the cell complex case, since the face relations of a cell complex
form a poset.
There are versions of sheaves for general topological spaces and even more exotic
structures like sites, but these have the downside in applications that they are not typ-
ically amenable to computation. When computations are possible, they typically re-
duce to operations equivalent to those taken with cellular sheaves.

6.2 Beyond vector spaces

There is nothing in the definition of a sheaf that requires the stalks actually be vector
spaces. One may construct a sheaf valued in any number of other categories. For in-
stance, the stalks might be simply sets, and the restriction maps just functions. Or they

26
might be groups, and the restriction maps group homomorphisms. The difficulty here
is that the tools we have developed for sheaves of vector spaces do not have immediate
analogues when the stalks are not vector spaces. One situation that allows some of
the machinery developed for vector spaces is the case of sheaves of semimodules over
a semiring. (A semiring is the analogue of a ring without the requirement that every
element have an additive inverse.) These give a natural way to model nonnegativity
constraints and directionality.

6.3 Turning things around

Some relationships we would like to model are more naturally expressed with maps
going the opposite way. Rather than restriction maps going from vertex stalks to edge
stalks, we want to consider extension maps going from edge stalks to vertex stalks.
In category theory, it is common to take the dual of a construction by reversing the
direction of all relevant morphisms. When we do this to a sheaf, we get what is called
a cosheaf.
Cosheaves are somewhat less intuitive than sheaves. Rather than global sections,
they have cosections, which are assignments to vertex stalks modulo an equivalence
relation given by the edges. Similarly, rather than cohomology, they have homology,
and the cosections of a cosheaf are precisely the elements of the degree zero homology
space H0 . This homology is computed by constructing a boundary map ∂ : C1 → C0 .
We can think of the construction of a sheaf Laplacian as pairing a sheaf with its dual
cosheaf; the boundary of the cosheaf is the adjoint of the coboundary of the sheaf, i.e.,
∂ = δ∗ . In some situations there is a natural applied interpretation of both a sheaf and
its dual cosheaf.

6.4 Further reading

Most other resources about sheaves have a heavier topological and algebraic emphasis,
and more prerequisites. The goal of these notes is to prepare the reader interested in
applications to tackle the more sophisticated treatments.
Elementary Applied Topology, by Robert Ghrist [3]. This book serves as an intro-
duction to algebraic topology and its applications to a wide variety of problems. The
penultimate chapter discusses sheaves, but is not accessible without a good deal of the
previous material in the book.
Topological Signal Processing, by Michael Robinson [11]. This book is written
from a more explicit engineering point of view, with examples of specific applications.

27
Not everything in here is relevant to the study of sheaves on graphs, though, and it fo-
cuses less on networks. Robinson also has slides and video from a seminar on sheaves
and data he presented for DARPA: Tutorial on Sheaves in Data Analytics [12].
Sheaves, Cosheaves, and Applications, by Justin Curry [1]. Justin’s thesis is a
perennial source of new insights, but is written from the most abstract perspective of
any of these resources. It is not likely to be a fruitful read for anyone not comfortable
with the material in Elementary Applied Topology.
Toward a Spectral Theory of Cellular Sheaves, by Jakob Hansen and Robert Ghrist [7].
This is an expository paper intended for an audience in applied topology. It contains
more general versions of most of the results discussed in this introduction.

References
[1] J. Curry. Sheaves, Cosheaves, and Applications. PhD thesis, University of Pennsyl-
vania, 2014.

[2] S. I. Gelfand and Y. I. Manin. Methods of Homological Algebra. Springer Mono-

graphs in Mathematics. Springer-Verlag, Berlin, second edition edition, 2003.

[3] R. Ghrist. Elementary Applied Topology. CreateSpace,

https://www.math.upenn.edu/ ghrist/notes.html, 2014.

[4] J. Hansen. Expansion in Matrix-Weighted Graphs. arXiv:2009.12008 [math], Sept.

2020.

[5] J. Hansen and R. Ghrist. Distributed optimization with sheaf homological con-
straints. In 57th Annual Allerton Conference on Communication, Control, and Com-
puting, Monticello, IL, 2019.

[6] J. Hansen and R. Ghrist. Learning sheaf Laplacians from smooth signals. In
Proceedings of ICASSP, 2019.

[7] J. Hansen and R. Ghrist. Toward a spectral theory of cellular sheaves. Journal of
Applied and Computational Topology, 3(4):315–358, Dec. 2019.

[8] J. Hansen and R. Ghrist. Opinion dynamics on discourse sheaves.

arXiv:2005.12798 [math], May 2020.

[9] M. Robinson. The Nyquist theorem for cellular sheaves. In Proceedings of the 10th
International Conference on Sampling Theory and Applications, 2013.

[10] M. Robinson. A sheaf-theoretic perspective on sampling. arXiv:1405.0324 [math],

May 2014.

28
[11] M. Robinson. Topological Signal Processing. Mathematical Engineering. Springer
Berlin Heidelberg, Berlin, Heidelberg, 2014.

[12] M. Robinson. Tutorial on Sheaves in Data Analytics.

http://www.drmichaelrobinson.net/sheaftutorial/, 2015.

29