:
1 2023 Symmetry and Geometry in Neural Representations

# Algebraic Topological Networks
via the Persistent Local Homology Sheaf

Gabriele Cesa<EMAIL_ADDRESS>
Arash Behboodi<EMAIL_ADDRESS>
Qualcomm AI Research, Amsterdam Qualcomm AI Research is an initiative of
Qualcomm Technologies, Inc.

###### Abstract

In this work, we introduce a novel approach based on algebraic topology to
enhance graph convolution and attention modules by incorporating local
topological properties of the data. To do so, we consider the framework of
_sheaf neural networks_ , which has been previously leveraged to incorporate
additional structure into graph neural networks’ features and construct more
expressive, non-isotropic messages. Specifically, given an input simplicial
complex (e.g. generated by the cliques of a graph or the neighbors in a point
cloud), we construct its _local homology sheaf_ , which assigns to each node
the vector space of its local homology. The intermediate features of our
networks live in these vector spaces and we leverage the associated sheaf
Laplacian to construct more complex linear messages between them. Moreover, we
extend this approach by considering the _persistent_ version of local homology
associated with a weighted simplicial complex (e.g., built from pairwise
distances of nodes embeddings). This _i)_ solves the problem of the lack of a
natural choice of basis for the local homology vector spaces and _ii)_ makes
the sheaf itself differentiable, which enables our models to directly optimize
the topology of their intermediate features.

###### keywords:

Graph, Simplicial, Sheaf, Laplacian, Homology, Topology

††editors: Sophia Sanborn, Christian Shewmake, Simone Azeglio, Nina Miolane

##  1 Introduction

Many works in the literature extended standard Graph Convolution Networks
(GCNs) Kipf and Welling (2016), which rely on isotropic message passing along
a graph’s edges, to more expressive message passing operators. Sheaf neural
networks Hansen and Gebhart (2020) provide a generic framework to encode more
structure into the features attached to a graph’s nodes, which can be
leveraged to define more expressive messages between the feature spaces of
neighboring nodes via the sheaf’s restriction maps and the _sheaf Laplacian_.
Briefly, a sheaf $\mathcal{F}$ on a space $X$ associates a (feature) vector
space $\mathcal{F}(U)$ to each (open) set $U\subset X$ and a linear map
$\mathcal{F}(U\subset V)$ to each pair $U\subset V$, i.e. the _restriction
map_. Two restrictions $\mathcal{F}(W\subset U)^{T}\mathcal{F}(W\subset V)$
can be combined to send messages between $U$ and $V$ via their intersection
$W=U\cap V$: this is the idea behind the _sheaf Laplacian_. While a sheaf
should also satisfy _locality_ and _gluing properties_ , these are not
necessary to construct the Laplacian and are usually ignored in neural
networks; see Apx. B for more details. In practice, sheaf neural networks
associate a feature vector space to each node in a graph and a linear map to
each edge, relating the feature spaces of connected nodes. With respect to the
graph Laplacian, this new Laplacian doesn’t enforce similarity between
neighboring nodes’ features, thereby circumventing the homophily assumption
Bodnar et al. (2022).

GCNs are the simplest example of sheaf neural networks: these architectures
rely on a sheaf which associates the same vector space to each node and whose
restriction maps are identities. This enables a simple weight sharing at the
cost of less expressive message passing. Other works can be interpreted under
this lens: de Haan et al. (2020) constructs a very expressive sheaf over
graphs where each node has a feature dimension for each of its neighbors and
restriction maps match dimensions corresponding to the same nodes111Messages
are actually constructed with something more similar to a cosheaf Laplacian by
leveraging the union rather than the intersection of open sets. The work also
supports more generic feature spaces.. Alternatively, since datasets rarely
come with a sheaf structure already defined, Bodnar et al. (2022) propose
learning to predict restriction maps from input features during inference.

#### Contributions

We use tools from algebraic topology Hatcher (2002) to construct a new sheaf
for neural networks: the Local Homology sheaf in the flag complex of a graph
Robinson et al. (2018). This sheaf catches local topological features of a
space: it associates to each node a feature vector space with a component for
each "relative cycle" in its neighborhood. Intuitively, an order $k$ local
relative cycle detects a subspace which locally looks like a $k$-dimensional
manifold. For this reason, the local homology sheaf is typically used for
stratification detection of triangulated spaces. Interestingly, sheaf
diffusion along the edges is sufficient to detect higher order (local and
global) homological properties of the space, with no need of higher-order
simplicial message passing.

Unfortunately, the homology sheaf doesn’t prescribe a natural choice of basis
for the feature vector space, which makes constructing learnable linear and
activation layers challenging. We tackle this limitation by considering
_weighted graphs_ and leveraging persistent homology, the standard tool in
_Topologial Data Analysis_ Carlsson (2009). Finally, this new construction
generates a sheaf whose Laplacian is _differentiable_ with respect to the
graph weights, which can be output of another learnable module (e.g. from
learnable node embeddings): this enables our model to learn the sheaf
structure or tune the weights in a topological informed way.

##  2 Simplicial Complexes, Homology and the Local Homology Sheaf

We first briefly review some essential concepts but see Apx. C for more
details.

Simplicial Complexes  Assume a _finite_ set $V$ of $|V|=N$ nodes. A simplicial
complex is a collection $S\subset 2^{V}$ of subsets of $V$; a subset
$\sigma\in S$ with $k+1$ elements is called a $k$-simplex. Simplicial
complexes generalize the common notion of _graph_ beyond pairwise
relationships. For example, if $G=(V,E)$ is a graph, its flag (or clique)
complex is a simplicial complex $S$ with nodes $V$ and containing a simplex
for each _clique_ in $G$, i.e. for each set of nodes in $G$ which form a
complete subgraph.

Chains and Boundaries  The graph Laplacian can be constructed from the
_incidence matrix_ $\partial\in\mathbb{R}^{|V|\times|E|}$ as
$\Delta_{0}=\partial\partial^{T}$. This construction generalizes to simplicial
complexes. A $k$-chain of $S$ is a scalar signal over (oriented)
$k$-simplicies; $C_{k}(S)$, or just $C_{k}$, is the vector space of all
$k$-chains. The incidence matrix is generalized by the boundary operator
$\partial_{k}\\!:\\!C_{k}\\!\to\\!C_{k-1}$, which models the relationship
between each $k$-simplex and its _faces_ (its $k$-dimensional subsets). The
$k$-th _Hodge Laplacian_ is defined as
$\Delta_{k}\\!:=\\!\partial_{k}^{T}\partial_{k}+\partial_{k+1}\partial_{k+1}^{T}\\!:\\!C_{k}\\!\to\\!C_{k}$
and has been used to construct a variety of simplicial neural networks
Papillon et al. (2023).

Cycles and Homology  A classical result in topology is that _a boundary of a
space has no boundary_ :
$\operatorname{im}\partial_{k+1}\subset\ker\partial_{k}$. The $k$-th homology
group is the _quotient vector space_
$H_{k}(S):=\ker\partial_{k}/\operatorname{im}\partial_{k+1}$. Its
dimensionality $\dim H_{k}$ is an important invariant counting the
$k$-dimensional holes in $S$ and its basis can be thought as a set of
independent $k$-dimensional cycles in $S$ ($0$-cycles are connected
components, $1$-cycles are loops, $2$-cycles are cavities).

fig:relative_homology [$H_{1}(S)$]
[$H_{2}(S,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>\backslash\operatorname{star}v_{1}})$]
[$H_{1}(S,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>\backslash\operatorname{star}v_{2})}$]

Figure 1: Examples of homology and relative homology. The  greyed out
simplices can be thought as being "collapsed" in a single point to compute
relative homology: then, the blue area $\beta$ turns into a $2$-sphere while
the  red line $\gamma$ turns into a $1$d ring.

Our construction is similar to (Robinson et al., 2018), which first introduced
the _Local Homology Sheaf_ over simplicial complexes. Given a $k$-simplex
$\sigma\in S$, define its star as $\operatorname{star}\sigma=\\{\tau\in
S:\sigma\subset\tau\\}$. An open subset $A\subseteq S$ is the union of sets of
the form $\operatorname{star}\sigma$; note that this is not necessarily a
simplicial complex. Instead, a subset $A\subseteq S$ is closed if it is a
subcomplex of $S$ (the faces of every simplex in $A$ are also in $A$). We also
define the closure $\operatorname{cl}A$ as the smallest subcomplex of $S$
containing $A$, the interior $\operatorname{int}A$ as the largest open set
contained in $A$ and the frontier as $\partial A=\operatorname{cl}A\
\backslash\ A$.

Relative Homology Let $A\subseteq S$ be a subcomplex of $S$. The $k$-th
relative homology $H_{k}(S,A)$ describes the $k$-th homology of the _quotient
space_ $S/A$ obtained from $S$ by identifying all its points within $A$, i.e.
by "collapsing" all points in $A$ in a single point. Fig.
LABEL:fig:relative_homology shows a few examples. However, note that the
relative homologies
$H_{k}(S,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>\backslash\operatorname{star}v})$ doesn’t depend on (most) gray simplices in
$S\backslash\operatorname{star}v$, but only on those in $\operatorname{star}v$
and its closest neighbors. This is the Excision Principle: if $A\subset
B\subset S$ are subsets of $S$ such that
$\operatorname{cl}A\subset\operatorname{int}B$, then $H_{k}(S,B)\cong
H_{k}(S\backslash A,B\backslash A)$. When $A\subset S$ is an open set,
$H_{k}(S,S\backslash A)\cong H_{k}(\operatorname{cl}A,\partial A)$.

Local Homology Sheaf As in Robinson et al. (2018), we consider the sheaf
$\mathcal{H}_{*}$ defined as $\mathcal{H}_{*}(A)=H_{*}(S,S\backslash A)\cong
H_{*}(\operatorname{cl}A,\partial A)$ for each open set $A\subset S$
($S\backslash A$ is closed if $A$ is open). The sheaf structure is naturally
given by the following _long exact sequence_ 222 An _exact sequence_ is a
sequence of maps s.t. the image of a map equals to the kernel of the
consecutive one. :

${{\cdots}}$${{\mathcal{H}_{k}(A\cup
B)}}$${{\mathcal{H}_{k}(A)\oplus\mathcal{H}_{k}(B)}}$${{\mathcal{H}_{k}(A\cap
B)}}$${\cdots}$$\scriptstyle{k_{*}-l_{*}}$$\scriptstyle{i_{*},j_{*}}$ (1)

where $k_{*},l_{*},i_{*}$ and $j_{*}$ are the sheaf restriction maps. This is
a special case of the well known Mayer-Vietoris sequence; see Apx. C.1. In
particular, $\mathcal{H}_{*}(\operatorname{star}v_{i})$ is called the local
homology of the vertex $v_{i}$. Intuitively, the local homology of a point in
a topological space contains information about what the space looks like
around that point. If the space is an $n$-manifold, the local neighborhood $U$
of any point looks like a $n$-ball, whose boundary $\partial U$ is isomorphic
to a $n-1$-sphere $\mathcal{S}^{n-1}$. Then, like in Fig.
LABEL:fig:relative_homology, via excision the local homology is
$H_{*}(U,\partial U)\cong\tilde{H}_{*}(\textnormal{S}^{n})$, i.e. the
(reduced) homology of an $n$-sphere, which only has one cycle of order $n$.
Hence, local homology _detects the local dimensionality of a space_. Moreover,
points at the boundary of the space have empty local homology. This idea was
used in Robinson et al. (2018), among others, for _stratification detection_.
Finally, note that the restriction maps constructed in Eq. 1 are identity maps
on $\mathcal{H}_{n}$ for points in the interior of an $n$-manifold333The local
homology sheaf $\mathcal{H}_{n}$ is closely related to the _orientation sheaf_
of an $n$-manifold..

Finally, recall that sheaf diffusion minimizes the _sheaf Dirichlet energy_ of
a signal Bodnar et al. (2022). At zero energy, the signal is in the
Laplacian’s kernel and, by the sheaf property, belongs to the global sections
of $\mathcal{H}(S)$ Hansen and Ghrist (2021). Because
$\mathcal{H}_{k}(S)=H_{k}(S,\emptyset)=H_{k}(S)$ (Corollary 20 Robinson et al.
(2018)), diffusion converges towards the global homology classes of $S$ of any
order $k$ while only relying on messages along edges.

Persistent Homology provides a richer structure than homology, by enriching
homology classes with a (differentiable) notion of resolution; see Apx. D.
Rather than building a single sheaf for a fixed complex $S$, we consider a
_filtration_ , i.e. a sequence of simplicial complexes $\\{S_{t}\\}_{t}$
related by inclusion, and build the local homology sheaf of the complex
$S_{t}$ at each time-step $t$. Cycles in the local homology at a step in the
filtration can "_persist_ " in the consecutive steps or disappear. This
enriches the local homology with a notion of time or scale, i.e. each cycle is
associated with a time-step where it emerges and a time-step where it
disappears. In practice, we define the "filtered" neighborhood of a node $i$
as $A_{i}^{t}=\operatorname{star}^{t}v_{i}\subset S_{t}$ and _compute the
persistent cycles_ in the persistent module
$\mathcal{H}_{k}^{\bullet}(A_{i})=\bigoplus_{t}H_{k}(S^{t},S^{t}\backslash
A^{t}_{i})$ as in Apx. E. Persistent cycles are shared among the time-steps
between their births and deaths, see Eq. 9. This _feature sharing strategy_
generates the persistent relative homology subspace
$\mathcal{H}_{k}(A_{i})\subset\mathcal{H}^{\bullet}_{k}(A_{i})$. Columns in
Fig. 2 are examples of persistent local homology.

##  3 Proposed Architecture

Given a graph $G=(V,E)$ with weighted edges (e.g. the distance matrix of a
point cloud), we construct the _Vietoris-Rips filtration_ 444 A simplex
appears in the filtration at a time step equal to the maximum weight of its
edges.  $\\{S_{t}\\}_{t}$ of its flag complex $S$. Unfortunately, while the
persistent module $\mathcal{H}^{\bullet}_{k}$ forms a sheaf, persistent local
homology $\mathcal{H}_{k}\subset\mathcal{H}^{\bullet}_{k}$ fails to be a sheaf
Palser (2019). To preserve the sheaf diffusion properties described before, we
prefer using the sheaf Laplacian of $\mathcal{H}^{\bullet}_{k}$. Hence, our
message passing on $\mathcal{H}_{k}$ first _embeds_ persistent homology
features in the sheaf $\mathcal{H}_{k}^{\bullet}$, then _applies_ the sheaf
Laplacian $\Delta_{\mathcal{H}_{k}^{\bullet}}$ and, finally, _projects_ the
output on $\mathcal{H}_{k}$ by averaging the features of a cycle along its
life span. Fig. 2 shows an example of Laplacian
$\Delta_{\mathcal{H}_{k}^{\bullet}}$. See Apx. F for details on the
implementation.

To complete our architecture, we need to include a learnable layer operating
on each node’s feature space $\mathcal{H}_{*}(A_{i})$. This involves two
challenges: _i)_ a persistent cycle is only _defined up to a sign_ (the
Laplacian constructed is equivariant to these sign changes) and _ii)_ each
node’s feature space looks different. _i)_ is related to the spectral
symmetries studied in Lim et al. (2023) and be can solved similarly: given
${\bm{x}}\in\mathcal{H}_{*}(A_{i})$, we construct a sign equivariant layer of
the form $\psi({\bm{x}})={\bm{x}}\circ\rho(|{\bm{x}}|)$. The learnable
operator $\rho$ can be modeled by a simple MLP. To share $\rho$ among
different nodes and solve _ii)_ , we learn a separate MLP $\Psi$ to output the
weights of $\rho$ for each node individually. Note that each persistent cycle
is uniquely identified by its order $k$ and its birth and death times
$s,t\in\mathbb{R}$, Then, we can parameterize a linear map on
$\mathcal{H}_{*}(A_{i})$ via $\Psi$ as follows: for each pair $(i,j)$ of
input/output persistent cycles, the $(i,j)$-th entry of the weight matrix is
parameterized by $\Psi(k_{i},s_{i},t_{i},k_{j},s_{j},t_{j})\in\mathbb{R}$. As
usual, this approach can be integrated in a multi-channel network, where the
features of the node include multiple copies of the vector space
$\mathcal{H}_{*}(A)$.

##  4 Limitations and Complexity

Persistent homology is computed by reducing the boundary matrices, with a
worst case complexity cubic in the number of simplices. Assuming $N$ nodes and
by considering only homology up to order $K$ (typically $K=2$ or $3$), there
are at worst $O(N^{K+1})$ simplices so the complexity is $O(N^{3K+3})$.
However, thanks to the excision principle, local homology can be computed by
using only a limited number of neighboring nodes. Assuming each node has
$O(n)$ neighbors, computing the local homology of each node costs only
$O(Nn^{3K+3})$. Moreover, the computation of each local homology can be fully
parallelized. For each par of nodes, the sheaf Laplacian is also computed via
a matrix reduction using the union of their local neighbors (with $O(2n)$
nodes): with a similar worst case complexity $O((2n)^{3K+3})$ for each pair of
nodes $O(nN)$, the overall complexity is then $O(Nn^{3K+4}2^{3K+3})$. Still,
we note that there exists optimized algorithms like Ripser Bauer (2021), which
are much faster on average by leveraging a number of smart heuristics; see
also Bauer et al. (2017) for a more detailed discussion. Additionally, the
number of neighbors $n$ can be chosen sufficiently low to control the overall
complexity. The main limitation we currently see is the fact that these
computations can not be performed on a GPU in a straightforward way. As a
result, computing the sheaf structure requires moving the edge weights to the
CPU during inference and, then, move the sheaf Laplacian data back on GPU.

##  5 Conclusions and Discussions

The proposed local homology sheaf Laplacian can be used to enhance existing
deep learning architectures by making them aware of the local and global
topology of the underlying data structure during inference. Previous works
(Rieck et al., 2019; Hofer et al., 2020; Carrière et al., 2020; Horn et al.,
2021) already successfully augmented graph neural networks with global
topological features by leveraging the persistent homology of weighted input
graphs. The proposed local homology sheaf can be used in a similar way to
enrich each node in a graph with its local topological features while the
sheaf Laplacian relates algebraically these local features. As argued at the
end of Sec. 2, global topological features are instead encoded in the global
sections of this sheaf, i.e. the kernel of the proposed Laplacian. We expect
this to be especially useful in tasks such as graph link prediction, mesh
reconstruction or simply where the data presents a variety of topologies. We
plan to experimentally evaluate this method on similar tasks in future works.

We thank Giovanni Luca Marchetti for the very insightful discussions about
efficiently computing the sheaf Laplacian, the Mayer-Vietoris sequences and
other algebraic topology ideas.

## References

  * Bauer (2021) Ulrich Bauer.  Ripser: efficient computation of vietoris–rips persistence barcodes.  _Journal of Applied and Computational Topology_ , 5(3):391–423, 2021.
  * Bauer et al. (2017) Ulrich Bauer, Michael Kerber, Jan Reininghaus, and Hubert Wagner.  Phat – persistent homology algorithms toolbox.  _Journal of Symbolic Computation_ , 78:76–90, 2017.  ISSN 0747-7171.  https://doi.org/10.1016/j.jsc.2016.03.008.  URL https://www.sciencedirect.com/science/article/pii/S0747717116300098.  Algorithms and Software for Computational Topology.
  * Blaser and Brun (2022) Nello Blaser and Morten Brun.  Relative persistent homology.  _Discrete & Computational Geometry_, pages 1–15, 2022.
  * Bodnar et al. (2022) Cristian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pietro Liò, and Michael Bronstein.  Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns.  _Advances in Neural Information Processing Systems_ , 35:18527–18541, 2022.
  * Brüel-Gabrielsson et al. (2019) Rickard Brüel-Gabrielsson, Bradley J Nelson, Anjan Dwaraknath, Primoz Skraba, Leonidas J Guibas, and Gunnar Carlsson.  A topology layer for machine learning.  _arXiv preprint arXiv:1905.12200_ , 2019.
  * Carlsson (2009) Gunnar Carlsson.  Topology and data.  _Bulletin of the American Mathematical Society_ , 46(2):255–308, 2009.
  * Carrière et al. (2020) Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda.  Perslay: A neural network layer for persistence diagrams and new graph topological signatures.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2786–2796. PMLR, 2020.
  * de Haan et al. (2020) Pim de Haan, Taco S Cohen, and Max Welling.  Natural graph networks.  _Advances in neural information processing systems_ , 33:3636–3646, 2020.
  * Hansen and Gebhart (2020) Jakob Hansen and Thomas Gebhart.  Sheaf neural networks.  _arXiv preprint arXiv:2012.06333_ , 2020.
  * Hansen and Ghrist (2021) Jakob Hansen and Robert Ghrist.  Opinion dynamics on discourse sheaves.  _SIAM Journal on Applied Mathematics_ , 81(5):2033–2060, 2021.
  * Hatcher (2002) Allen Hatcher.  _Algebraic Topology_.  Cambridge University Press, 2002.
  * Hofer et al. (2020) Christoph Hofer, Florian Graf, Bastian Rieck, Marc Niethammer, and Roland Kwitt.  Graph filtration learning.  In _International Conference on Machine Learning_ , pages 4314–4323. PMLR, 2020.
  * Horn et al. (2021) Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt.  Topological graph neural networks.  _arXiv preprint arXiv:2102.07835_ , 2021.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2016.
  * Lim et al. (2023) Derek Lim, Joshua Robinson, Stefanie Jegelka, Yaron Lipman, and Haggai Maron.  Expressive sign equivariant networks for spectral geometric learning.  In _ICLR 2023 Workshop on Physics for Machine Learning_ , 2023.
  * Palser (2019) Megan Palser.  An excision theorem for persistent homology.  _arXiv preprint arXiv:1910.03348_ , 2019.
  * Papillon et al. (2023) Mathilde Papillon, Sophia Sanborn, Mustafa Hajij, and Nina Miolane.  Architectures of topological deep learning: A survey on topological neural networks.  _arXiv preprint arXiv:2304.10031_ , 2023.
  * Rieck et al. (2019) Bastian Rieck, Christian Bock, and Karsten Borgwardt.  A persistent weisfeiler-lehman procedure for graph classification.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 5448–5458. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/rieck19a.html.
  * Robinson et al. (2018) Michael Robinson, Chris Capraro, Cliff Joslyn, Emilie Purvine, Brenda Praggastis, Stephen Ranshous, and Arun Sathanur.  Local homology of abstract simplicial complexes.  _arXiv preprint arXiv:1805.11547_ , 2018.
  * Sovdat (2016) Blaž Sovdat.  Text mining via homology, 2016.
  * Tralie et al. (2018) Christopher Tralie, Nathaniel Saul, and Rann Bar-On.  Ripser.py: A lean persistent homology library for python.  _The Journal of Open Source Software_ , 3(29):925, Sep 2018.  10.21105/joss.00925.  URL https://doi.org/10.21105/joss.00925.

##  Appendix A Example of persistent sheaf Laplacian

Figure 2: Example of persistent sheaf Laplacian. The three columns depict the
time evolution of the filtrations of the local neighborhood of three
simplices. At different time steps, some new relative cycles appear or
disappear and each cycle "persists" for an interval of time. In our
architecture, a single feature is stored for each persistent cycle; this
feature can be thought as been shared over all time steps within the cycle’s
life span. Moreover, the three columns share a  relative $1$-cycle
$\gamma_{1}$. Note that this cycle exists at different times intervals in the
three columns and, therefore, there exists a sheaf Laplacian only during the
intersection of these intervals $[t_{1},t_{3})$.

##  Appendix B Sheaves

Given a space $X$, a pre-sheaf $\mathcal{F}$ associates to each open set
$U\subset X$ a space $\mathcal{F}(U)$ and to each pair $U\subset V(\subset X)$
a map ${\mathcal{F}}(U\subset V):\mathcal{F}(V)\to\mathcal{F}(U)$
(_restriction map_), such that ${\mathcal{F}}(U\subset U)$ is the identity and
${\mathcal{F}}(U\subset V){\mathcal{F}}(V\subset W)={\mathcal{F}}(U\subset W)$
if $U\subset V\subset W$. We are mostly interested in the cases where
$\mathcal{F}(U)$ are vector spaces. An element of $\mathcal{F}(U)$ is called a
"local section", while an element of $\mathcal{F}(X)$ is called a "global
section".

Given an open cover $\\{U_{i}\subset U\\}_{i}$ of $U\subset X$, a sheaf is a
pre-sheaf satisfying two additional axioms:

  1. 1.

_locality_ : if two local sections $s,t\in\mathcal{F}(U)$ agree when
restricted on all $\\{U_{i}\\}_{i}$, then they are identical

  2. 2.

_gluing_ : if a set of local sections $\\{s_{i}\in\mathcal{F}(U_{i})\\}_{i}$
agree on all their overlaps, then there exists section $s\in\mathcal{F}(U)$
which agrees with $s_{i}$ when restricted on $U_{i}$, for all $i$

Given a sheaf $\mathcal{F}$, with $\mathcal{F}(U)$ vector spaces, we can
construct the _sheaf Laplacian_ Hansen and Gebhart (2020). To do so, consider
an open cover $\\{U_{i}\\}_{i}$ of the space $X$. For any $i,j$ s.t.
$U_{i}\cap U_{j}\neq\emptyset$, define the linear map

$\delta_{ij}:\mathcal{F}(U_{i})\times\mathcal{F}(U_{j})\to\mathcal{F}(U_{i}\cap
U_{j}),\quad x_{i},x_{j}\mapsto{\mathcal{F}}(U_{i}\cap U_{j}\subset
U_{i})x_{i}-{\mathcal{F}}(U_{i}\cap U_{j}\subset U_{j})x_{j}$

Then, the sheaf Laplacian is a block matrix defined as
$L_{\mathcal{F}}=\delta^{T}\delta$. Note that, if $i\neq j$, the $(i,j)$-th
block is defined as $[\Delta_{\mathcal{F}}]_{ij}=-{\mathcal{F}}(U_{i}\cap
U_{j}\subset U_{i})^{T}{\mathcal{F}}(U_{i}\cap U_{j}\subset U_{j})$.

Given a sheaf defined over a graph, the sheaf Laplacian generalizes the
classical graph Laplacian and provides a useful tool to build more expressive
message passing operators for neural networks.

To build message passing, the restriction map of a pre-sheaf is sufficient and
we do not actually need the additional two axioms of a sheaf. Still, since
local homology in Sec. 2 forms a sheaf with some interesting properties and to
keep the notation simpler, we use the word "sheaf" also in the message passing
architectures which don’t enforce these axioms.

##  Appendix C Simplicial Complexes, Boundary Maps and Homology

#### Simplicial Complex

Give a _finite_ set of nodes $V$, with $|V|=N\in\mathbb{N}$, a simplicial
complex $S$ is a mathematical objects that can be thoughts as a collection of
subsets of $V$, i.e. $S\subset 2^{V}$, such that $\forall\sigma\in
S,\tau\subset\sigma\implies\tau\in S$. Each such subset $\sigma\in S$ is
called a simplex. We usually refer to simplices with $k+1$ elements as
$k$-simplices. Simplicial complexes generalize the common notion of _graph_ ,
by thinking of an edge as a set containing two nodes. A $k$-simplex
$\sigma=\\{v_{0},\dots,v_{k}\\}\subset V$, like edges, is typically associated
with an orientation, i.e. a particular choice of ordering of its elements
$\sigma=[v_{0},\dots,v_{k}]\in S$. Two $k$-simplicies $\sigma,\sigma^{\prime}$
containing the same subset of nodes share the same orientation if they differ
by an _even permutation_ but have opposite orientation if they differ by an
_odd permutation_.

#### Chain Complexes and Boundary Operators

Let $S$ be a simplicial complex. A $k$-chain of $S$ is a scalar function
$f:S\to\mathbb{R}$ on the oriented $k$-simplicies of $S$ such that
$f(\sigma)=f(\sigma^{\prime})$ if $\sigma$ and $\sigma^{\prime}$ have the same
orientation (differ by an even permutation) and
$f(\sigma)=-f(\sigma^{\prime})$ if they have opposite orientation (differ by
an odd permutation). A chain complex $C_{\bullet}(S)$ is a sequence of vector
spaces $C_{0}(S),C_{1}(S),\dots$, where $C_{k}(S)$ is the vector space of all
$k$-chains. A chain complex is associated with a _linear_ boundary operator
(or _differential_) $\partial_{k}:C_{k}\to C_{k-1}$, defined on a $k$-simplex
$\sigma=[v_{0},v_{1},\dots,v_{k}]\in S$ (intended as one of the basis elements
of $C_{k}$) as555This definition should be extended linearly to the full space
$C_{k}$.

$\displaystyle\partial_{k}\sigma:=\sum_{i=0}^{k}(-1)^{i}[v_{0},\dots,\hat{v_{i}},\dots,v_{k}]$
(2)

where $[v_{0},\dots,\hat{v_{i}},\dots,v_{k}]$ is a $k-1$-simplex obtained from
$\sigma$ by removing the node $v_{i}$. We often use
$\partial_{\bullet}:C_{\bullet}\to C_{\bullet}$ to denote the operator acting
on each subspace $C_{k}$ of $C_{\bullet}$ with the corresponding operator
$\partial_{k}$.

#### Example

If $S$ is just a graph $G=(V,E)$, $C_{0}$ are functions over the nodes $V$
while $C_{1}$ are functions over the (oriented) edges $E$. Moreover, the
operator $\delta_{1}:C_{1}\to C_{0}$ maps an edge $e=(v_{0},v_{1})\in E$ to
$\partial_{1}(e)=[v_{1}]-[v_{0}]$ and, therefore, if $f\in C_{1}$, then

$\displaystyle(\partial_{1}f)(v_{i})=\sum_{e=[v_{j},v_{i}]\in
E}f(e)-\sum_{e=[v_{i},v_{j}]\in E}f(e)$ (3)

This boundary operator $\partial_{1}$ can be used to construct the _Graph
Laplacian_ as $\Delta_{0}:=\partial_{1}\partial_{1}^{T}$, which is typically
used to perform message passing in GCNs. The boundary operators can be used to
generalize this construction to a _Hodge Laplacian_ over a simplicial complex,
defined as
$\Delta_{k}:=\partial_{k}^{T}\partial_{k}+\partial_{k+1}\partial_{k+1}^{T}:C_{k}\to
C_{k}$, which can be used to construct a variety of higher-order simplicial
neural networks Papillon et al. (2023).

#### Cycles, Boundaries and Homology

A $k$-chain is said to be a boundary if it is the boundary of a $k+1$-chain;
the subspace of $k$-boundaries is indicated by
$B_{k}:=\operatorname{im}\partial_{k+1}$. A $k$-chain is said to be a cycle if
its boundary is zero; the subspace of $k$-cycles is indicated by
$Z_{k}:=\ker\partial_{k}$. A classical result in topology is that _a boundary
of a space has no boundary_ , i.e.
$\partial_{\bullet}\circ\partial_{\bullet}=\partial_{\bullet}^{2}=0$. It
follows that $B_{k}=\operatorname{im}\partial_{k+1}\subset
Z_{k}=\ker\partial_{k}$. The $k$-th homology group is defined as the _quotient
vector space_ $H_{k}(S):=Z_{k}/B_{k}$. The dimensionality $\dim H_{k}$ is an
important invariant and is equal to the $k-th$ _Betti number_ $\beta_{k}$ of
$S$, which counts the $k$-dimensional holes in $S$.

#### Topology, open sets and subcomplexes of a simplicial complex

Given a finite simplicial complex $S$, a subset $A\subseteq S$ is said to be
closed if it is also a simplicial complex (i.e. for each simplex in $A$, all
its faces are also in $A$), i.e. it is a subcomplex of $S$. Instead, an open
subset666Formally, we consider the Alexandrov topology of the simplicial
complex like in Robinson et al. (2018) $A\subseteq S$ is the union of sets of
the form $\operatorname{star}\sigma=\\{\tau\in S:\sigma\subset\tau\\}$; note
that this is not necessarily a simplicial complex. Finally, we define a few
useful operations on a subset $A\subseteq S$:

  * •

$S\backslash A$ indicates the standard set difference.

  * •

the closure $\operatorname{cl}A$ is the smallest subcomplex of $S$ containing
$A$.

  * •

the star $\operatorname{star}A$ is the set of all simplices in $S$ which
contain a simplex in $A$

  * •

the boundary (or frontier) $\partial
A=\operatorname{cl}A\cap\operatorname{cl}(S\backslash A)$

  * •

the interior $\operatorname{int}A$ is the largest open set contained in $A$

#### Relative Homology

Let $A\subseteq S$ be a subcomplex (i.e. a closed subset) of the simplicial
complex $S$. The relative $k$-chain space $C_{k}(S,A)\cong C_{k}(S)/C_{k}(A)$
is the vector space of $k$-chains over $S$ which are zeros over the simplices
in $A$. Clearly, $C_{k}(S,A)$ is a subspace of $C_{k}(S)$ so the map
$\partial_{k}:C_{k}\to C_{k-1}$ can be generalized to
$\partial_{k}:C_{k}(S,A)\to C_{k-1}(S,A)$. Then, the sub-space of relative
$k$-boundaries is indicated by $B_{k}(S,A):=\operatorname{im}\partial_{k+1}$
and the subspace of relative $k$-cycles is indicated by
$Z_{k}(S,A):=\ker\partial_{k}$. Finally, the $k$-th relative homology is
defined as $H_{k}(S,A)=Z_{k}(S,A)/B_{k}(S,A)$. Intuitively, $H_{k}(S,A)$
describes the $k$-th homology of the quotient space $S/A$ obtained from $S$ by
identifying all its points within $A$, i.e. by "collapsing" all points in $A$
in a single point777Note the difference between the set difference
$S\backslash A$ and the quotient space $S/A$..

###  C.1 Properties of Homology and Long Exact Sequences

#### Long Exact Sequence for the Relative Homology

If $A\subset S$ is a subcomplex of $S$, the relative chains give rise to a
chain complex of relative homology groups with the following short exact
sequence:

$\displaystyle\dots\to
H_{k}(A)\to^{i_{k}}H_{k}(S)\to^{j_{k}}H_{k}(S,A)\to^{\partial}H_{k-1}(A)\to\dots$
(4)

The map $i_{k}$ comes from the inclusion of $C_{k}(A)$ into $C_{k}(S)$ and,
intuitively, is relating the $k$-dimensional holes in $A$ with their copy in
$S$. The map $j_{k}$ comes from the projection of $C_{k}(S)$ into $C_{k}(S,A)$
and, intuitively, relates the holes in $S$ outside of $A$ with their copies in
$S/A$. Finally, the last map $\partial$ detects the $k$-dimensional holes in
$S/A$, not present in $S$, which have appeared by collapsing $A$ in a single
point. These $k$-dimensional holes can be related with $A$’s $k-1$-dimensional
boundary $\partial A\subset A$ and, therefore, included in $H_{k-1}(A)$.

#### Mayer-Vietoris Sequence

Given two subcomplexes $A,B$ and the union
$S=\operatorname{int}A\cup\operatorname{int}B$, there is another important
long exact sequence:

$\displaystyle\dots\to H_{k+1}(S)\to^{\partial_{*}}H_{k}(A\cap
B)\to^{i_{*},j_{*}}H_{k}(A)\oplus H_{k}(B)\to^{k_{*}-l_{*}}H_{k}(S)\to\dots$
(5)

Intuitively, if a $k+1$ cycle in $S$ is "broken" when $S$ is split into $A$
and $B$, the cycle splits into two $k+1$ chains in $A$ and $B$ which overlap
in $A\cap B$. The boundaries of the two $k+1$ chains are homologous, i.e. they
are a $k$-cycle in $A\cap B$, that is an element of $H_{k}(A\cap B)$.

This sequence holds also for relative homology, i.e. if
$T=\operatorname{int}C\cup\operatorname{int}D\subset S$, with $C,D\subset S$,
then

$\displaystyle\dots\to H_{k+1}(S,T)\to^{\partial_{*}}H_{k}(S,C\cap
D)\to^{i_{*},j_{*}}H_{k}(S,C)\oplus
H_{k}(S,D)\to^{k_{*}-l_{*}}H_{k}(S,T)\to\dots$ (6)

Eq. 6 can also be used to construct the sequence in Eq. 1 by replacing
$C=S\backslash A,D=S\backslash B$ and, therefore, $T=C\cup D=S\backslash(A\cap
B),C\cap D=S\backslash(A\cup B)$:

$\displaystyle\dots\to H_{k}(S,S\backslash(A\cup
B))\to^{i_{*},j_{*}}H_{k}(S,S\backslash A)\oplus H_{k}(S,S\backslash
B)\to^{k_{*}-l_{*}}H_{k}(S,S\backslash(A\cap B))\to\dots$ (7)

Note that the maps in this sequence are given by the restriction maps of the
sheaf and the exactness of the sequence proves exactly the gluing property of
a sheaf. See Proposition 19 Robinson et al. (2018) for a more precise proof.

##  Appendix D Persistent Homology

Given a finite simplicial complex $S$ and a function $f:S\to\mathbb{R}$ s.t.
$f(\sigma)\leq f(\tau)$ if $\sigma<\tau$, define the simplicial complex
$S_{t}=\\{\sigma\in S:f(\sigma)\leq t\\}\subset S$. Note that
$S_{t_{1}}\subset S_{t_{2}}$ if $t_{1}\leq t_{2}$ and there exists
$t^{-},t^{+}$ such that $S_{t}=\emptyset$ for any $t\leq t^{-}$ and $S_{t}=S$
for any $t\geq t^{+}$. Moreover, the sequence of simplicial complexes
$\\{S_{t}\\}_{t\in\mathbb{R}}$ only contains a finite number of different
complexes, so it can be replaced by a finite sequence $\\{S_{t}\\}_{t\in R}$
indexed by a subset $R\subset\mathbb{R}$. This sequence is called a filtration
of simplicial complexes.

The inclusion $S_{t_{1}}\subset S_{t_{2}}$ induces an homomorphism
$i_{k}^{t_{1},t_{2}}:H_{k}(S_{t_{1}})\to H_{k}(S_{t_{2}})$, whose image
$\operatorname{im}i_{k}^{t_{1},t_{2}}$ is the persistent homology group
$H_{k}^{t_{1},t_{2}}(S)$ and detects $k$-cycles in $S_{t_{1}}$ which are still
present in $S_{t_{2}}$. In particular, any $k$-cycles is born at a certain
"time" $t_{1}$ (is not in the image of $i_{k}^{t,t_{1}}$ for any $t<t_{1}$).
It can also disappear at a time $t_{2}$ (it is in the kernel of
$i_{k}^{t_{1},t}$ for any $t\geq t_{2}$) or persist forever (it is a cycle in
$H_{k}(S)$).

Note also that, if the complexes in the filtration only differ by a single
simplex (i.e. the function $f$ gives a total ordering of the simplices), each
time step a single $k$-simplex is added, which either creates a new $k$-cycle
or destroys a $k-1$ cycle. This is useful since the homology group $H_{k}(S)$
does not come with a natural choice of basis888 A basis for $H_{k}(S)$ can be
computed as the $0$-eigenvectors of the $k$-th Hodge Laplacian
$\Delta_{k}=\partial_{k}^{T}\partial_{k}+\partial_{k+1}\partial_{k+1}^{T}$.
However, this basis is not unique and numerical algorithms are not guaranteed
to return the same solution consistently. The lack of a choice of basis is
problematic to construct learnable neural operations like linear layers and
non-linearities, which depend on a specific basis. ; in this case, instead,
cycles are uniquely identified by their birth and death times, which
indirectly provides a choice of basis.

Relative persistent homology has also been studied in the literature, e.g. see
Robinson et al. (2018); Blaser and Brun (2022). However, as far as we know,
these works considered a slightly different formulation, assuming a filtration
of pairs $(S,A_{t})$, with $A_{t}\subset A_{t+1}\subset S$.

Instead, in this work, we consider a filtration of pairs in the following
form. Let $S^{\infty}=S$ and $A^{\infty}=A\subset S$. Let
$\mathbb{S}=(\dots,S_{t},\dots,S^{\infty}=S)$ be a filtration of $S$ and
$\mathbb{A}=(\dots,A_{t},\dots,A^{\infty}=A)$ be a filtration of $A$, with
$A_{t}=S_{t}\cap A$ (and, clearly, $S_{t}\subset S_{t+1}$ and $A_{t}\subset
A_{t+1}$). To simplify the notation, sometimes we just write $S$ instead of
$\mathbb{S}$ to indicate a filtration.

As earlier, the inclusion $S_{t_{1}}\subset S_{t_{2}}$ induces an homomorphism
$i_{k}^{t_{1},t_{2}}:H_{k}(S_{t_{1}},A_{t_{1}})\to
H_{k}(S_{t_{2}},A_{t_{2}})$, whose image
$\operatorname{im}i_{k}^{t_{1},t_{2}}$ is the persistent relative homology
$H_{k}^{t_{1},t_{2}}(S,A)$ and detects relative $k$-cycles in
$S_{t_{1}}/A_{t_{1}}$ which are still present in $S_{t_{2}}/A_{t_{2}}$. Given
an open set $U\subset S_{\infty}$, define the persistence module

$\displaystyle\mathcal{H}^{\bullet}_{k}(U)$
$\displaystyle=\bigoplus_{t}H_{k}(S_{t},S_{t}\backslash U)$ (8)

Then, our persistent homology feature spaces can be formally defined as the
quotient

$\displaystyle\mathcal{H}_{k}(U)$
$\displaystyle=\left(\bigoplus_{t}H_{k}(S_{t},S_{t}\backslash
U)\right)/\left(\bigoplus_{t_{1}<t_{2}}\operatorname{im}i_{k}^{t_{1},t_{2}}\right)=\mathcal{H}_{k}^{\bullet}(U)/\left(\bigoplus_{t_{1}<t_{2}}\operatorname{im}i_{k}^{t_{1},t_{2}}\right)$
(9)

The quotient removes the copies of a persistent cycle through its life
interval. Hence, the resulting space has a dimension for each unique
persistent cycle.

Sovdat (2016) studied a similar sequence where $A_{t}\subset S_{t}$ but not
necessarily $A_{t}=S_{t}\cap A_{\infty}$ (i.e. a simplex can enter $S$ at a
time step but also enter in $A$ at a later time step) and proposed an
algorithm to compute this relative persistent (co)homology.

Apx. E describes how persistent relative homology can be computed while Apx. F
describes a method to construct the corresponding sheaf Laplacian.

##  Appendix E Computing Relative Homology and Relative Persistent Homology

#### Computing Persistent Homology

The Ripser library implements an efficient algorithm to compute persistent
homology Bauer (2021); Tralie et al. (2018). This algorithm can be easily
adapted to also return the indices of the simplices which created and
destroyed each homology class / persistent cycle; indeed, these indices are
needed to implement a differentiable version of persistent homology Brüel-
Gabrielsson et al. (2019). Note that this software actually computes
persistent co-homology and also returns representative cochains, which can be
thought simply as the transpose of representative chains. In the rest of this
section, we will work with co-homology groups $H^{k}(\cdot)$ rather than
homology groups $H_{k}(\cdot)$ to better reflect the algorithm but we first
emphasize that these groups are isomorphic.

Unfortunately, Ripser only compute absolute (co)homology. Sovdat (2016)
previously described a very similar algorithm to compute the persistent
_relative_ homology of a sequence of pairs $\\{(S_{t},A_{t})\\}_{t}$. As
discussed in Apx. D, they consider more general filterations than ours and,
therefore, their algorithm is unnecessarily complicated for us.

Instead, we note that the Ripser algorithm from Bauer (2021) essentially
performs an (optimized) _Gauss reduction_ of the co-boundary matrix
$\partial^{\bullet}_{S}:C^{\bullet}(S)\to C^{\bullet}(S)$, with rows and
columns (corresponding to different simplices in the filtration) sorted by
decreasing weight / birth time. This algorithm can be used to compute the
relative (co)homology $H^{\bullet}(S,A)$ by simply removing those rows and
columns of $\partial^{\bullet}_{S}$ which belongs to $A$; indeed, by
definition one obtains precisely the relative co-boundary map
$\partial^{\bullet}_{S,A}:C^{\bullet}(S,A)\to C^{\bullet}(S,A)$ which defines
relative (co)homology.

Moreover, as most existing persistent homology tools, Ripser only supports
finite fields $\mathbb{F}=\mathbb{Z}/p\mathbb{Z}$ (for $p$ prime), while our
sheaf requires features in the real field $\mathbb{F}=\mathbb{R}$.
Fortunately, the algorithm described in Bauer (2021) works for any generic
field $\mathbb{F}$, so Ripser can be easily adapted to compute (co)homology
with $\mathbb{F}=\mathbb{R}$ coefficients.

##  Appendix F Computing the sheaf Laplacian

Let $A^{\prime},B^{\prime}\subset S$ be two open sets and
$C^{\prime}=A^{\prime}\cap B^{\prime}\subset S$ their intersection. To
construct the sheaf Laplacian between these two open sets
$\Delta_{B^{\prime},A^{\prime}}^{k}=-\left[{\mathcal{H}}^{k}(C^{\prime}\subset
A^{\prime})\right]^{T}\circ{\mathcal{H}}^{k}(C^{\prime}\subset B^{\prime})$ we
need to construct the two restriction maps
${\mathcal{H}}^{k}(C^{\prime}\subset
A^{\prime}),{\mathcal{H}}^{k}(C^{\prime}\subset B^{\prime})$ and then find
equivalent cocycles in their images.

The following Mayer-Vietoris sequence for relative cohomology suggests a way
to perform this computation. Let $D^{\prime}=A^{\prime}\cup B^{\prime}$ the
union of the two open sets and $D=S\setminus D^{\prime}$ its complementary;
then the following sequence is exact:

$\displaystyle\dots\to
H^{k-1}(S,D)\to^{\partial^{k-1}}H^{k}(S,C)\to^{i_{*}\oplus-
j_{*}}H^{k}(S,A)\oplus H^{k}(S,B)\to^{k_{*}+l_{*}}H^{k}(S,D)\to\dots$ (10)

where the maps $i_{*}$ and $j_{*}$ are adjoint of the restriction maps
${\mathcal{H}}^{k}(C^{\prime}\subset
A^{\prime}),{\mathcal{H}}^{k}(C^{\prime}\subset B^{\prime})$. The co-boundary
map $\partial^{k-1}$ detects the $k$ relative cycles in $C^{\prime}$, not
present in neither $A^{\prime}$ nor $B^{\prime}$, which have appeared when
collapsing $C\setminus D$ in a single point (e.g. a line with it extremes in
$D^{\prime}\setminus C^{\prime}$ is a connected component, i.e. a $0$-cycle,
in $H^{0}(S,D)$, but when $D^{\prime}\setminus C^{\prime}$ is collapsed, the
two extremes merge and the $0$-cycle becomes a $1$-cycle in $H^{1}(S,C)$).

This sequence implies that $H^{k}(S,C)$ splits as the co-image
$\operatorname{coim}(i^{*}\oplus-j^{*})$ (i.e. the image of the restriction
maps) and the image $\operatorname{im}\partial^{k-1}$. In other words, the
restrictions of two cocycles in $H^{k}(S,A)$ and $H^{k}(S,B)$ are equivalent
if their difference is zero modulo $\operatorname{im}\partial^{k-1}$.

Hence, we set up an _extended coboundary matrix_ ${\mathcal{B}}^{k}$ whose
reduction computes the sheaf Laplacian.

Columns The matrix columns are divided in two sets. First, it contains all
columns of $\partial^{\bullet}(S,D)$ as used in Apx. E to compute the
persistent relative cohomology $H^{k}(S,D)$. Second, it contains a column for
each persistent cocycle found previously in $H^{k}(S,A)$ and $H^{k}(S,B)$.
Like in Apx. E, the columns in the first set are sorted inversely by the
weight of each $k-1$ simplex in $D^{\prime}$. Instead, the columns in the
second set are sorted inversely by their corresponding cocycle’s birth time
(cocycles of $A^{\prime}$ and $B^{\prime}$ are mixed by sorting). These two
sets split the matrix in two sub-matrices
${\mathcal{B}}^{k}=[{\mathcal{B}}^{k}_{D},{\mathcal{B}}^{k}_{AB}]$.

Rows in ${\mathcal{B}}^{k}_{D}$ Columns in ${\mathcal{B}}^{k}_{D}$ simply
contain the coboundaries in $D^{\prime}$ of each simplex, sorted by decreasing
weight, as in Apx. E.

Before defining the rows in ${\mathcal{B}}^{k}_{AB}$, let’s first recall some
details about the algorithm in Bauer (2021). A cocycle in $H^{k}(S,A)$ (or
$B$) can be represented by the column of the reduction matrix used to reduce
$\partial^{k}_{A}$. This vector expresses a $k$-cocycle as a linear
combination of $k$-simplices in $A^{\prime}$. The non-zero simplex with lowest
weight defines the birth time of the cocycle. The corresponding reduced column
contains the coboundary and the first non-zero $k+1$ simplex (the _pivot_)
defines the death time of the cocycle (since, after that time, the cocycle
doesn’t belong to the kernel of the coboundary map anymore).

Rows in ${\mathcal{B}}^{k}_{AB}$ The columns in ${\mathcal{B}}^{k}_{AB}$
contain three sets of row. Each column, corresponding to a certain cocycle to
restrict, has

  1. 1.

one row for each $k$-simplex in $D^{\prime}$: these rows contain a copy of the
reduction vector representing the cocycle as above (note that
$A^{\prime},B^{\prime}\subset D^{\prime}$). These are also the same rows in
${\mathcal{B}}^{k}_{D}$

  2. 2.

one row for each $k+1$ simplex in $A^{\prime}$: these rows contain a copy of
the coboundary of the cocycles in $A^{\prime}$

  3. 3.

another row for each $k+1$ simplex in $B^{\prime}$: these rows contain a copy
of the coboundary of the cocycles in $B^{\prime}$

Note that each $k+1$ simplex in $D$’ appears twice in the rows.

A linear combination of the columns of this extended reduction matrix is a
linear combination of cocycles in $H^{k}(S,A)$, $H^{k}(S,B)$ and
$H^{k-1}(S,D)$. This represents a pair of cocycles $\gamma_{A}\in H^{k}(S,A)$
and $\gamma_{B}\in H^{k}(S,B)$ and the rows in the resulting column model the
three constraints we are trying to enforce. Indeed, a non-zero value in a row
implies

  * •

if the row is a $k+1$-simplex in $A^{\prime}$ (or $B^{\prime}$), the cocycle
$\gamma_{A}\in H^{k}(S,A)$ (or $\gamma_{B}\in H^{k}(S,B)$) is dead at this
time step (and so must be also its restriction to $H^{k}(S,C)$ as proved in
Theorem F.1).

  * •

if the row is a $k$-simplex in $C^{\prime}\subset D^{\prime}$, it means that
the sum of $\gamma_{A}$ and $\gamma_{B}$ is not zero at this time step i.e.
their restrictions are not equivalent cocycles.

  * •

if the row is a $k$-simplex in $D^{\prime}\setminus
C^{\prime}=(A^{\prime}\setminus C^{\prime})\cup(B^{\prime}\setminus
C^{\prime})$, either $\gamma_{A}$ or $\gamma_{B}$ can not be restricted to
$H^{k}(S,C)$ at this time step.

Then, the matrix reduction algorithm trying to find pairs of cocycles which
satisfy these constraints for the longest time. Once this matrix is reduced, a
column in ${\mathcal{B}}^{k}_{AB}$ represents a pair of cocycles
$\gamma_{A}\in H^{k}(S,A)$ and $\gamma_{B}\in H^{k}(S,B)$ whose sum is $0$
when restricted to $H^{k}(S,C)$, modulo the coboundary of some cocycles in
$H^{k-1}(S,D)$, until the time step the _pivot_ of this column appears in the
filtration. Then, the pivot corresponds to the time step one of the three
constraints above is violated.

Hence, the reduced columns in ${\mathcal{B}}^{k}_{AB}$ can be used to
construct the sheaf Laplacian as follows. Let the $i$-th reduced column
correspond to a pair of cocycles $(\gamma_{A}^{i},\gamma_{B}^{i})$ which are
obtained by linearly combining the persistent bases of $H^{k}(S,A)$ and
$H^{k}(S,B)$ via the reduction vectors ${\bm{v}}_{A}^{i}$ and
${\bm{v}}_{B}^{i}$, respectively. Note that these reduction vectors
essentially construct the two restriction maps. Let $t_{i}$ be the time the
pivot of this column appear and let $s_{A}^{i}$ be the birth time of
$\gamma_{A}^{i}$ (i.e. the lowest weight of its simplices) and $t_{A}^{i}$ its
death time, and $s_{B}^{i}$ and $t_{B}^{i}$ those of $\gamma_{B}^{i}$. This
pair restricts to the same cocycle in $H^{k}(S,C)$ only in the time interval
$[s^{i},t^{i})$, with $s_{i}=\max(s_{A}^{i},s_{B}^{i})$ and $t_{i}\leq
s_{B}^{i},s_{A}^{i}$ due to Theorem F.1. The pair $(s^{i},t^{i})$ defines the
time interval during which an $i$-th sheaf Laplacian persists:

$[\Delta_{{\mathcal{H}}^{k}}^{i}]_{A^{\prime},B^{\prime}}={\bm{v}}_{A}^{i}({\bm{v}}_{B}^{i})^{T}$

We do not include the $-1$ sign since our constraint enforced
$\gamma_{A}+\gamma_{B}\cong 0$, i.e. $\gamma_{A}\cong-\gamma_{B}$. This
Laplacian is visualized also in Fig. 2.

Note that the non-zero coefficients in the vector ${\bm{v}}_{A}^{i}$ or
${\bm{v}}_{B}^{i}$ are associated with persistent cocycles of $H^{k}(S,A)$ or
$H^{k}(S,B)$ which might appear and die at different time steps. It follows
that each entry of $[\Delta_{{\mathcal{H}}^{k}}^{i}]_{A^{\prime},B^{\prime}}$
has an independent persistence interval given by the intersection of
$[s^{i},t^{i})$ with the intervals of the two cocycles of $A^{\prime}$ and
$B^{\prime}$ involved.

If we define ${\bm{v}}|_{t}$ as the components of ${\bm{v}}$ which are
"active" at time $t$, the sheaf Laplacian at a time step $t$ can be
constructed as

$[\Delta_{{\mathcal{H}}^{k}}^{t}]_{A^{\prime},B^{\prime}}=\sum_{i:t\in[t^{i},s^{i})}{\bm{v}}_{A}^{i}|_{t}({\bm{v}}_{B}^{i}|_{t})^{T}$

Finally, the embedding and projection operations mention in Sec. 3 can be
easily implemented by weighting the entry $(a,b)$ of the matrix
$[\Delta_{{\mathcal{H}}^{k}}^{i}]_{A^{\prime},B^{\prime}}$ by its own life
span $\min(t_{i},t_{a},t_{b})-\max(s_{i},s_{a},s_{b})$ divided by the output
cocycle life span $t_{a}-s_{a}$.

###  F.1 Other properties of the Local (Co)Homology Sheaf

The following properties guarantee the intuitive fact that (co)cycles appear
and disappear first in smaller neighborhoods than in larger ones. In other
words, if a (co)cycles is in the image of the restriction map
${\mathcal{H}}^{k}(A^{t}\subset B^{t})$ at time $t$, then it also needs to be
in the image at any previous time steps (until the birth time in
${\mathcal{H}}^{k}(B)$); similarly, if a (co)cycles is in the kernel of
${\mathcal{H}}^{k}(A^{t}\subset B^{t})$ at a time step $t$, it will also be at
any following time steps (until its death in ${\mathcal{H}}^{k}(B)$).

######  Theorem F.1 (The restriction of a cocycle dies earlier).

Consider the following _commutative_ diagram for relative persistent
cohomology and assume a single simplex is added to $\mathbb{S}$ at each time
step $t$:

${{\cdots}}$${{H^{k-1}(S_{t})}}$${{H^{k-1}(A_{t})}}$${{H^{k}(S_{t},A_{t})}}$${{H^{k}(S_{t})}}$${\cdots}$${\cdots}$${{H^{k-1}(S_{t+1})}}$${{H^{k-1}(A_{t+1})}}$${{H^{k}(S_{t+1},A_{t+1})}}$${{H^{k}(S_{t+1})}}$${\cdots}$$\scriptstyle{\partial^{k-1}_{t}}$$\scriptstyle{i_{t}^{*}}$$\scriptstyle{j^{*}_{t}}$$\scriptstyle{\partial^{k-1}_{t+1}}$$\scriptstyle{i_{t+1}^{*}}$$\scriptstyle{j^{*}_{t+1}}$$\scriptstyle{f^{t,t+1}_{A}}$$\scriptstyle{f^{t,t+1}_{S,A}}$$\scriptstyle{f^{t,t+1}_{S}}$$\scriptstyle{f^{t,t+1}_{S}}$
(11)

Let $\gamma\in\operatorname{im}{i^{*}_{t}}\subset H^{k}(S_{t})$ be a cocycle
of $S_{t}$ at time $t$ which corresponds to a relative cocycle
$\bar{\gamma}\in H^{k}(S_{t},A_{t})$, i.e. $\gamma=i_{t}^{*}(\bar{\gamma})$.
Assume that at time $t+1$ a $k+1$-simplex $\sigma$ is added to $S_{t}$ such
that the cocycle $\gamma$ dies in $H^{k}(S_{t+1})$, i.e.
$\gamma\notin\operatorname{im}{f^{t,t+1}_{S}}$. Then,
$\bar{\gamma}\notin\operatorname{im}{f^{t,t+1}_{S,A}}$ either and, therefore,
the relative cocycle $\bar{\gamma}$ dies at time $t+1$, too.

######  Proof F.2.

Let $\gamma\in\ker{f^{t,t+1}_{S}}$ and let $\sigma$ be the $k+1$ simplex added
in $S_{t+1}$ which killed $\gamma$ (i.e. $S_{t+1}=S_{t}\cup\\{\sigma\\}$).
Assume $\exists\bar{\gamma}\in H^{k}(S_{t},A_{t})$ such that
$\gamma=i_{t}^{*}(\bar{\gamma})$.

Since $\sigma$ is a $k+1$-simplex, $H^{k-1}(A_{t+1})\cong H^{k-1}(A_{t})$ and
$H^{k-1}(S_{t+1})\cong H^{k-1}(S_{t})$. Because these cohomology groups did
not change, $\operatorname{im}{j^{*}_{t}}\cong\operatorname{im}{j^{*}_{t+1}}$
and, therefore, $\ker{\partial^{k-1}_{t}}\cong\ker{\partial^{k-1}_{t+1}}$. It
also follows that
$\operatorname{coim}{\partial^{k-1}_{t}}\cong\operatorname{coim}{\partial^{k-1}_{t+1}}$,
i.e. $\ker{i^{*}_{t}}=\ker{i^{*}_{t+1}}$.

Finally, because $\bar{\gamma}\notin\ker{i^{*}_{t}}\cong\ker{i^{*}_{t+1}}$,
$\bar{\gamma}\in
H^{k+1}(S_{t+1},A_{t+1})\cong\ker{i^{*}_{t+1}}\oplus\operatorname{coim}{i^{*}_{t+1}}$
if and only if $\bar{\gamma}\in\operatorname{coim}{i^{*}_{t+1}}$. This
requires that $\exists\gamma^{\prime}=i^{*}_{t+1}(\bar{\gamma})\in
H^{k}(S_{t+1})$. However, the commutativity of the diagram guarantees that
$i^{*}_{t+1}(f_{S,A}^{t,t+1}(\bar{\gamma}))=f_{S}^{t,t+1}(i^{*}_{t+1}(\bar{\gamma}))=0$,
which is a contradiction. Hence, $\bar{\gamma}\in\ker{f^{t,t+1}_{S,A}}$, i.e.
the relative cocycle $\bar{\gamma}$ must also die at time $t+1$.

A similar argument should work also for triples, i.e. projections
$H^{k}(S,B)\to H^{k}(S,A)$ with $B\subset A\subset S$ by replacing $H^{k}(S)$
with $H^{k}(S,B)$ and $H^{k}(A)$ with $H^{k}(A,B)$.

######  Theorem F.3 (The restriction of a cocycle appears earlier).

Consider again the _commutative_ diagram for relative persistent cohomology in
Eq. 11 (here, shifted right by two steps):

${\cdots}$${{H^{k}(S_{t},A_{t})}}$${{H^{k}(S_{t})}}$${{H^{k}(A_{t})}}$${{H^{k+1}(S_{t},A_{t})}}$${\cdots}$${\cdots}$${{H^{k}(S_{t+1},A_{t+1})}}$${{H^{k}(S_{t+1})}}$${{H^{k}(A_{t+1})}}$${{H^{k+1}(S_{t+1},A_{t+1})}}$${\cdots}$$\scriptstyle{i_{t}^{*}}$$\scriptstyle{i_{t+1}^{*}}$$\scriptstyle{f^{t,t+1}_{S,A}}$$\scriptstyle{f^{t,t+1}_{S}}$$\scriptstyle{j^{*}_{t}}$$\scriptstyle{\partial^{k}_{t}}$$\scriptstyle{j^{*}_{t+1}}$$\scriptstyle{\partial^{k}_{t+1}}$$\scriptstyle{f^{t,t+1}_{A}}$$\scriptstyle{f_{S,A}^{t,t+1}}$
(12)

Again, assume a single simplex is added to $\mathbb{S}$ at each time step $t$.
Let $\gamma\in H^{k}(S_{t})$ be a cocycle of $S_{t}$ which persists to
$S_{t+1}$, i.e. $\gamma\in\operatorname{im}{f_{S}^{t,t+1}}$.

Assume that there exists a relative cocycle $\bar{\gamma}\in
H^{k}(S_{t+1},A_{t+1})$ such that $\gamma=i_{t+1}^{*}(\bar{\gamma})$.

Then, $\bar{\gamma}\in\operatorname{im}{f^{t,t+1}_{S,A}}$, too. This implies
that the projection $\bar{\gamma}$ must always appear in the filtration at the
same time or earlier than the corresponding cocycle
$\gamma=i^{*}(\bar{\gamma})$.

######  Proof F.4.

Assume $\gamma\notin\operatorname{im}{i^{*}_{t}}$. Then, there exists a new
relative cocycle $\bar{\gamma}^{\prime}$ in $H^{k}(S_{t+1},A_{t+1})$ appearing
at time $t+1$, with $\gamma=i^{*}_{t+1}(\bar{\gamma}^{\prime})$. Let $\sigma$
be the $k$-simplex added to $S_{t}\setminus A_{t}$ which gave birth to it
(i.e. $S_{t+1}=S_{t}\cup\\{\sigma\\}$ and $A_{t}=A_{t+1}$). Since
$\sigma\notin A_{t+1}$, $H^{*}(A_{t+1})\cong H^{*}(A_{t})$. Moreover, since
$\sigma$ is a $k$-simplex, $H^{k+1}(S_{t},A_{t})\cong
H^{k+1}(S_{t+1},A_{t+1})$, too.

It follows that $\ker{\partial^{k}_{t}}\cong\ker{\partial^{k}_{t+1}}$ and,
therefore,
$\operatorname{coim}{j^{*}_{t+1}}\cong\operatorname{coim}{j^{*}_{t}}$. Since
$\gamma\in\operatorname{im}{i^{*}_{t+1}}$,
$\gamma\notin\operatorname{coim}{j^{*}_{t+1}}\cong\operatorname{coim}{j^{*}_{t}}$.
Hence, $\gamma\in\ker{j_{t}^{*}}\cong\operatorname{im}{i^{*}_{t}}$.

This a contradiction, so it must be the case that
$\gamma\in\operatorname{im}{i^{*}_{t}}$, too.

Now, let $\bar{\gamma}\in H^{k}(S_{t},A_{t})$ s.t.
$\gamma=i_{t}^{*}(\bar{\gamma})$. Then, by commutativity of the diagram,
$\gamma=f_{S}^{t,t+1}(i_{t}^{*}(\bar{\gamma}))=i^{*}_{t+1}(f_{S,A}^{t,t+1}(\bar{\gamma}))$,
which implies $\bar{\gamma}\in\operatorname{coim}{f_{S,A}^{t,t+1}}$. In other
words, $\bar{\gamma}$ is also a persistent cocycle in $H^{k}(S,A)$.

As earlier, a similar argument should work also for triples $B\subset A\subset
S$.