# Grounded persistent path homology: a stable, topological descriptor for
weighted digraphs

Thomas Chaplin  Mathematical Institute, University of Oxford  Corresponding
author<EMAIL_ADDRESS>Heather A. Harrington  Mathematical
Institute, University of Oxford  Ulrike Tillmann  Mathematical Institute,
University of Oxford

###### Abstract

Weighted digraphs are used to model a variety of natural systems and can
exhibit interesting structure across a range of scales. In order to understand
and compare these systems, we require stable, interpretable, multiscale
descriptors. To this end, we propose grounded persistent path homology (GrPPH)
– a new, functorial, topological descriptor that describes the structure of an
edge-weighted digraph via a persistence barcode. We show there is a choice of
circuit basis for the graph which yields geometrically interpretable
representatives for the features in the barcode. Moreover, we show the barcode
is stable, in bottleneck distance, to both numerical and structural
perturbations. GrPPH arises from a flexible framework, parametrised by a
choice of digraph chain complex and a choice of filtration; for completeness,
we also investigate replacing the path homology complex, used in GrPPH, by the
directed flag complex.

##  1 Introduction

Directed graphs with positive edge-weights arise both as natural objects of
mathematical study and as useful models of real-world systems (e.g. [3, 4, 30,
37]). A common task is to distinguish between weighted digraphs. Frequently,
this is achieved by defining an invariant, i.e. a map
$\operatorname*{\mathcal{I}}:\bm{\mathrm{WDgr}}\to X$ from weighted digraphs
into some set $X$, together with a metric $d$ on $X$. The metric allows us to
quantitatively measure to what extent a pair of weighted digraphs differ. When
$\operatorname*{\mathcal{I}}$ is well understood we may be able to explain
_why_ the weighted digraphs differ. In order to determine desirable
characteristics of such an $\operatorname*{\mathcal{I}}$, consider the
examples shown in Figure 1, in which edge weights correspond to length as
drawn.

$G_{1}$$G_{2}$$G_{3}$$G_{4}$

Figure 1: Four example weighted digraphs; weights correspond to length as
drawn.

Consider each $G_{i}$ from the perspective of a particle flowing through the
digraph, such that the particle may only traverse an edge in the direction
specified and the time it takes corresponds to the weight. To the particle,
loops (or circuits) in the graph are significant features. However, loops can
vary greatly based on the orientation and weight of constituent edges.

Despite sharing the same underlying undirected graph, $G_{1}$ and $G_{2}$
support very different flows since $G_{1}$ has a single source and a single
sink whereas $G_{2}$ has 4 sources and 2 sinks. To reflect this,
$d(\operatorname*{\mathcal{I}}(G_{1}),\operatorname*{\mathcal{I}}(G_{2}))$
should be large. In contrast, $G_{3}$ has a different undirected graph but can
be obtained from $G_{1}$ by simply subdividing each edge. In applications,
this may arise from a finer resolution image of the same system. A suitable
invariant should be relatively stable to such subdivisions, ideally converging
to a limiting value upon iterated subdivision. Finally, $G_{4}$ has a higher
circuit rank but the new loops are on a small scale, whilst the large scale
organisation is mostly similar to $G_{1}$. Therefore,
$d(\operatorname*{\mathcal{I}}(G_{1}),\operatorname*{\mathcal{I}}(G_{4}))$
should be small and the difference between
$\operatorname*{\mathcal{I}}(G_{1})$ and $\operatorname*{\mathcal{I}}(G_{4})$
should reflect this multiscale comparison.

For successful application, any invariant should be stable to a reasonable
noise model. A typical requirement is that $\operatorname*{\mathcal{I}}$ is
continuous (or better yet Lipschitz), with respect to a choice of metric on
$\bm{\mathrm{WDgr}}$. Designing metrics for graphs is an active area of
research but a common choice is the graph edit distance [18]. For this metric,
costs are assigned to operations such as deleting an edge or modifying a
weight, then the distance between two graphs is the minimal cumulative cost of
modifying one into the other. Since assigning costs to graph operations is
somewhat arbitrary, it is reasonable instead to require a bound on
$d(\operatorname*{\mathcal{I}}(G),(\operatorname*{\mathcal{I}}(\mathbb{O}{G}))$,
over a range of graph operations,
$\mathbb{O}{}:\bm{\mathrm{WDgr}}\to\bm{\mathrm{WDgr}}$.

Finally, in many applications (particularly in biology), it is important that
any invariant $\operatorname*{\mathcal{I}}$ is interpretable. That is, one
must be able to explain _why_ the invariant has the value it does. Typically
this is achieved through the identification of key contributing subgraphs.

In summary, we seek an invariant for weighted digraphs which

  1. (a)

distinguishes graphs with different flow profiles due to directionality;

  2. (b)

can detect and describe features (i.e. loops) across a range of scales;

  3. (c)

is stable to reasonable perturbations and converges under iterated
subdivision; and

  4. (d)

is interpretable, e.g. through the identification of important subgraphs.

Pursuant to these goals, we employ two tools from topological data analysis
(TDA) – path homology and persistent homology. A number of homology theories
for digraphs have been developed (see summary in Section 2 of [7]). Path
homology is one such theory [23], which is sensitive to directionality and has
useful functorial properties [12, 24]. Persistent homology is a tool for
developing stable descriptors [1] that extract relevant information in
multiscale scenarios. As such, persistent homology has seen successful
applications to fields including neuroscience [6, 20, 21, 38], vasculature
[32, 36] and financial networks [25], to name but a few [19]. A theory of
persistent path homology (PPH) was proposed by [12] [12] and is a stable
descriptor for directed networks. In a search to develop an interpretable
invariant for weighted digraphs, which respects the inert topology of the
underlying digraph, we are lead to an alteration of PPH which we prove meets
goals (a)-(d).

###  1.1 Contributions and outline

In Section 2 we give an overview of path homology and persistent homology, and
set up the categorical framework for the rest of the paper. In particular, we
define a category of weighted digraphs $\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}$
in which morphisms are digraph maps of the underlying digraphs as well as
contractions of the natural, shortest-path quasimetric.

In Section 3.1 we review a standard pipeline for extracting a topological
invariant of a weighted digraph, via PPH. Evaluating this invariant against
our stated goals, motivates an alteration of this pipeline, which we call the
‘grounded pipeline’. We define this new pipeline and describe categories upon
which the resulting invariant is functorial in Section 3.2.

Arising from the grounded pipeline, our main contribution is
Definition/Theorem 3.15, wherein we define grounded persistent path homology
(GrPPH). This new invariant is a functor

$\prescript{g}{}{\mathcal{H}}_{1}:\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}\to\bm{\mathrm{PersVec}}$
(1.1)

where $\bm{\mathrm{PersVec}}$ is the category of persistent vector spaces.
Couching this definition in category theory yields a strong framework for
comparing weighted digraphs through the invariant. Indeed, we use this
functoriality later in the paper to aid the proof of decomposition and
stability results.

Section 4 is devoted to developing an interpretation of GrPPH. The early
subsections are dedicated to understanding the features detected by
$\prescript{g}{}{\mathcal{H}}_{1}(G)$; the following theorem summarises our
findings.

######  Theorem 1.1.

Given a weighted digraph $G\in\bm{\mathrm{WDgr}}$, denote the underlying
undirected graph by $\mathcal{U}(G)$.

  1. (a)

All features in $\prescript{g}{}{\mathcal{H}}_{1}(G)$ are born at $t=0$;

  2. (b)

$\prescript{g}{}{\mathcal{H}}_{1}(G)$ at time $t=0$ is the (real) cycle space
of $\mathcal{U}(G)$; and moreover

  3. (c)

there is a choice of circuits in $\mathcal{U}(G)$ whose homology classes
generate $\prescript{g}{}{\mathcal{H}}_{1}(G)$.

These results demonstrate how GrPPH is sensitive to circuits in the digraph at
all scales, meeting goal (b), and can be interpreted through a persistence
basis of such circuits, meeting goal (d). We also discuss how to use
$\prescript{g}{}{\mathcal{H}}_{1}(G)$ to assign a ‘scale’ to any circuit in
$\mathcal{U}(G)$ in Section 4.2. In Section 4.4, we prove that if $G$ can be
decomposed into smaller parts, then GrPPH also decomposes.

######  Theorem 1.2.

Given a weighted digraph $G\in\bm{\mathrm{WDgr}}$, if $G$ decomposes as a
wedge decomposition $G=G_{1}\vee_{\hat{v}}G_{2}$ or a disjoint union
$G=G_{1}\sqcup G_{2}$ then

$\prescript{g}{}{\mathcal{H}}_{1}(G)\cong\prescript{g}{}{\mathcal{H}}_{1}(G_{1})\oplus\prescript{g}{}{\mathcal{H}}_{1}(G_{2}).$
(1.2)

In Section 5 we investigate the stability of
$\prescript{g}{}{\mathcal{H}}_{1}$. We prove a number of bounds on the
bottleneck distance of the barcode upon perturbing the input weighted digraph.
We find local stability to operations such as weight perturbation, edge
subdivision and certain classes of edge collapses and edge deletions. In
particular, edge subdivision stability automatically implies that our
invariant converges under iterated subdivision (Corollary 5.14). In contrast,
the descriptor is unstable to generic edge collapses and edge deletions, which
we demonstrate through a number of counter-examples. We argue that these
stability properties suffice to meet goal (c) and indeed stability to larger
classes of edge collapses and edge deletion would be undesirable. For a
summary of all stability results obtained, please consult Table 1.

In order to build intuition for what is measured by GrPPH, we compute a number
of illustrative examples in Section 6. In particular, in Section 6.1, we
consider a simple, cycle graph and determine the limiting value of GrPPH under
iterated edge subdivision. In Section 6.2, we compute the invariant for a
number of small square digraphs with varying edge orientations, illustrating
sensitivity to directionality, as required by goal (a).

GrPPH arises from the grounded pipeline after fixing a number of choices,
including path homology as a functor from digraphs to chain complexes. Another
popular method for producing chain complexes from digraphs is the directed
flag complex [29]. Replacing path homology with directed flag complex homology
yields an alternative descriptor, called grounded persistent directed flag
complex homology (GrPdFlH). For completeness, in Appendix A, we revisit each
of the results obtained in the main paper, replacing GrPPH with GrPdFlH. Of
particular note is Example A.13, in which we show that GrPdFlH is sensitive to
a particularly simple class of edge deletions. This stands in contrast to
GrPPH, which is unaffected by these deletions.

###  1.2 Computations

The software package Flagser allows the user to flexibly define filtrations of
directed flag complexes and subsequently compute persistent homology [28]. We
use an alteration of Flagser to compute grounded persistent directed flag
complex homology (available at [8]). An algorithm for computing PPH in
arbitrary degrees was proposed by [12] [12]; a more efficient algorithm for
computing PPH in degree $1$ was later proposed by [16] [16]. A slight
modification of the latter algorithm can be used to compute GrPPH. A software
package for computing both grounded homologies, as well as persistence bases,
in collaboration with G. Henselman-Petrusek, is forthcoming.

###  1.3 Acknowledgements

The first author would like to thank H. Byrne, A. Goriely, A. Ó hEachteirn and
T. Thompson for valuable discussions which motivated and aided the early
stages of this work. HAH gratefully acknowledges funding from a Royal Society
University Research Fellowship. The authors are members of the Centre for
Topological Data Analysis, which is funded by the EPSRC grant ‘New Approaches
to Data Science: Application Driven Topological Data Analysis’ EP/R018472/1.
For the purpose of Open Access, the authors have applied a CC BY public
copyright licence to any Author Accepted Manuscript (AAM) version arising from
this submission.

##  2 Background

###  2.1 Basic notation and category theory

We introduce some basic language for graphs and categories, and then recall
the definitions of path homology and persistent homology, the two theories we
combine later in a new way to define our invariant.

######  Notation 2.1.

For $d\in\mathbb{N}$, the  standard $d$-simplex is

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\Delta^{d}}:=\left\\{(x_{0},\dots
x_{d})\in\mathbb{R}^{d+1}\mathrel{}\middle|\mathrel{}\sum x_{i}=1,\text{ and
}x_{i}\geq 0\;\forall i\right\\}.$ (2.1)

######  Notation 2.2.

Given a category $\bm{\mathcal{C}}$, we denote the collection of objects
$\mathrm{Obj}(\bm{\mathcal{C}})$ and the collection of morphisms
$\mathrm{Mor}(\bm{\mathcal{C}})$. For two objects
$X,Y\in\mathrm{Obj}(\bm{\mathcal{C}})$, we denote the collection of morphisms
$X\to Y$ by  $\mathrm{Mor}_{\bm{\mathcal{C}}}(X,Y)$. Where it is clear from
object whether $\alpha$ is an object or a morphism, we simply write
$\alpha\in\bm{\mathcal{C}}$.

######  Definition 2.3.

Given two categories $\bm{\mathcal{C}}$ and $\bm{\mathcal{D}}$ we denote the
category of functors $\bm{\mathcal{C}}\to\bm{\mathcal{D}}$, where morphisms
are natural transformations, by
$\textbf{[}\bm{\mathcal{C}},\,\bm{\mathcal{D}}\textbf{]}$. For a morphism
$f\in\mathrm{Mor}_{\textbf{[}\bm{\mathcal{C}},\,\bm{\mathcal{D}}\textbf{]}}(M,N)$,
we denote the components of the natural transformation by $f_{x}:M(x)\to N(x)$
for each $x\in\bm{\mathcal{C}}$.

######  Lemma 2.4.

Given categories $\bm{\mathcal{C}}$, $\bm{\mathcal{D}}$ and
$\bm{\mathcal{D}}^{\prime}$ and a functor
$\mu:\bm{\mathcal{D}}\to\bm{\mathcal{D}}^{\prime}$, there is a functor
$\textbf{[}\bm{\mathcal{C}},\,\mu\textbf{]}:\textbf{[}\bm{\mathcal{C}},\,\bm{\mathcal{D}}\textbf{]}\to\textbf{[}\bm{\mathcal{C}},\,\bm{\mathcal{D}}^{\prime}\textbf{]}$.

###### Proof.

Given
$F\in\mathrm{Obj}(\textbf{[}\bm{\mathcal{C}},\,\bm{\mathcal{D}}\textbf{]})$,
we map $\textbf{[}\bm{\mathcal{C}},\,\mu\textbf{]}(F):=\mu\circ F$. Given a
natural transformation $\nu:F\Rightarrow F^{\prime}$ between functors
$F,F^{\prime}\in\textbf{[}C,\,D\textbf{]}$, $\mu\circ\nu$ is a natural
transformation $\mu\circ F\Rightarrow\mu\circ F^{\prime}$. This construction
satisfies the usual functorial axioms. ∎

######  Notation 2.5.

  1. (a)

We let  $\bm{\mathrm{R}}$ denote the poset of $\mathbb{R}$ equipped with the
$\leq$ relation, viewed as a category.

  2. (b)

We let  $\bm{\mathrm{Vec}}$ denote the category of $\mathbb{R}$-vector spaces
and $\bm{\mathrm{vec}}$ denote the subcategory of finite-dimensional
$\mathbb{R}$-vector spaces.

  3. (c)

We let  $\bm{\mathrm{Ch}}$ denote the category of chain complexes over
$\mathbb{R}$.

######  Definition 2.6.

Given a chain complex $C_{\bullet}\in\bm{\mathrm{Ch}}$, we denote the $k^{th}$
chain group by $C_{k}$ and the boundary map by $\partial_{k}:C_{k}\to
C_{k-1}$. For each $k\in\mathbb{N}$, the  $k^{th}$ homology group,  $H_{k}(C)$
is the quotient

$H_{k}(C):=\frac{\ker\partial_{k}}{\operatorname{im}\partial_{k+1}}.$ (2.2)

We can view $H_{k}$ as a functor $\bm{\mathrm{Ch}}\to\bm{\mathrm{Vec}}$.

###  2.2 Directed graphs

######  Definition 2.7.

  1. (a)

A  (simple) digraph is a tuple $G=(V,E)$ where $V$, the set of  vertices, is a
finite set and $E$, the set of  edges, is a subset of $V\times
V\setminus\Delta_{V}$ where

$\Delta_{V}:=\left\\{(i,i)\in V\times V\mathrel{}\middle|\mathrel{}i\in
V\right\\}.$ (2.3)

We call elements of $\Delta_{V}$ self-loops.

  2. (b)

A  directed acyclic graph (DAG) is a simple digraph $G=(V,E)$ such that there
is a linear ordering on the nodes $V=\\{v_{1},\dots,v_{n}\\}$ such that
$(v_{i},v_{j})\in E\implies i<j$.

  3. (c)

An  oriented graph is a simple digraph $G=(V,E)$ with no double edges, i.e.
$(i,j)\in E\implies(j,i)\not\in E$.

  4. (d)

A  weighted (digraph/DAG/oriented graph) is a triple $G=(V,E,w)$ such that
$(V,E)$ is a (simple digraph/DAG/oriented graph) and $w:E\to\mathbb{R}_{>0}$
is a positively-valued function on the edges.

  5. (e)

An  undirected graph is a tuple $G=(V,E)$ where $E$ is a multiset of 2-element
subsets of $V$.

  6. (f)

Given a digraph $G=(V,E)$, the  underlying undirected graph is
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathcal{U}(G)}:=(V,\mathcal{U}(E))$
where

$\displaystyle(i,j)\in E,(j,i)\not\in E$
$\displaystyle\implies\\{i,j\\}\in\mathcal{U}(E)\text{ with multiplicity }1,$
(2.4) $\displaystyle(i,j),(j,i)\in E$
$\displaystyle\implies\\{i,j\\}\in\mathcal{U}(E)\text{ with multiplicity }2.$
(2.5)

  7. (g)

Given two digraphs $G_{1}=(V_{1},E_{1})$, $G_{2}=(V_{2},E_{2})$ with
$V_{1},V_{2}\subseteq V$, their union is
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>G_{2}}:=(V_{1}\cup V_{2},E_{1}\cup E_{2})$. If $V_{1}$, $V_{2}$ are disjoint,
then we denote this
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>G_{2}}$.

######  Notation 2.8.

Fix a weighted digraph $G=(V,E,w)$.

  1. (a)

We denote
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}V(G)}:=V$,
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}E(G)}:=E$,
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}w(G)}:=w$.

  2. (b)

For an edge $e=(i,j)\in E$, we write
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\operatorname*{st}(e)}:=i$
and
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\operatorname*{fn}(e)}:=j$,
and say that $i$ and $j$ are  incident to $e$.

  3. (c)

For an edge $e=(i,j)\in E$, we write
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}w(i,j)}:=w(e)$.

  4. (d)

We write
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>j}$ to mean there is an edge $(i,j)\in E$.

######  Definition 2.9.

Fix a weighted digraph $G=(V,E,w)$.

  1. (a)

Given $V^{\prime}\subseteq V$, the  induced subgraph on $V^{\prime}$ is
$(V^{\prime},E^{\prime},w^{\prime})$, where $E^{\prime}=E\cap(V^{\prime}\times
V^{\prime})$ and $w^{\prime}$ is $w$ restricted to $E^{\prime}$.

  2. (b)

Given $E^{\prime}\subseteq E$, the  induced subgraph on $E^{\prime}$ is
$(V^{\prime},E^{\prime},w^{\prime})$, where $V^{\prime}$ is the set of all
vertices incident to some edges in $E^{\prime}$ and $w^{\prime}$ is $w$
restricted to $E^{\prime}$.

  3. (c)

For $v\in V$,

$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathcal{N}_{in}(v;G)}$
$\displaystyle:=\left\\{a\in V\mathrel{}\middle|\mathrel{}a\to v\right\\},$
(2.6)
$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathcal{N}_{out}(v;G)}$
$\displaystyle:=\left\\{b\in V\mathrel{}\middle|\mathrel{}v\to b\right\\},$
(2.7)
$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathcal{N}(v;G)}$
$\displaystyle:=\mathcal{N}_{in}(v)\cup\mathcal{N}_{out}(v)$ (2.8)

and the  neighbourhood graph, $\operatorname*{\mathcal{N\\!G}}(v;G)$, is the
induced subgraph on $\mathcal{N}(v)$. Where $G$ is clear from context, we omit
it from notation.

  4. (d)

For $F\subseteq E$,

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathcal{N}(F;G)}:=\left\\{\tau\in
E\mathrel{}\middle|\mathrel{}\exists\,e\in F\text{ such that }\tau,e\text{ are
incident to a common vertex}\right\\}$ (2.9)

and the  neighbourhood graph, $\operatorname*{\mathcal{N\\!G}}(F;G)$, is the
induced subgraph on $\mathcal{N}(F;G)$. Where $G$ is clear from context, we
omit it from notation.

  5. (e)

For two vertices $a,b\in V$, a  (directed) trail from $a$ to $b$ is an
alternating sequence of vertices, $v_{i}\in V$, and forward edges, $e_{i}\in
E$,

$p=(v_{0}=a,e_{1},v_{1},e_{2},\dots,e_{k},v_{k}=b)$ (2.10)

such that $e_{i}=(v_{i-1},v_{i})$. We write that  $p$ is a trail $a\leadsto
b$. In a simple digraph, the $e_{i}$ uniquely determine the $v_{i}$ (and vice
versa) so we occasionally omit one from the notation.

  6. (f)

A trail which does not repeat vertices is a  path.

  7. (g)

An  undirected circuit is an alternating sequence of vertices, $v_{i}\in V$,
and edges, $e_{i}\in E$,

$p=(v_{0}=a,e_{1},v_{1},e_{2},\dots,e_{k},v_{k}=a)$ (2.11)

such that
$\\{\operatorname*{st}(e_{i}),\operatorname*{fn}(e_{i})\\}=\\{v_{i-1},v_{i}\\}$
and $v_{0}=v_{k}$.

  8. (h)

Given an undirected circuit $p$, as above, if $v_{0},\dots,v_{k-1}$ are all
distinct then we say $p$ is  simple.

######  Notation 2.10.

Fix a weighted digraph $G=(V,E,w)$.

  1. (a)

Given a trail $p$, the  length of $p$ is defined as

$\operatorname*{len}(p):=\sum_{i=1}^{k}w(e_{i}).$ (2.12)

  2. (b)

We denote the set of all paths $i\leadsto j$ by
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathcal{P}(i,j)}$.

######  Definition 2.11.

For a weighted digraph $G$, the  shortest-path quasimetric $d:V(G)\times
V(G)\to\mathbb{R}\sqcup\\{\infty\\}$ is defined by

$d(i,j):=\begin{cases}\min_{p\in\mathcal{P}(i,j)}\operatorname*{len}(p)&\text{if
}\mathcal{P}(i,j)\neq\emptyset,\\\ \infty&\text{otherwise}.\end{cases}$ (2.13)

There is a notion of morphisms between (weighted) digraphs.

######  Definition 2.12.

  1. (a)

Given two simple digraphs $G,H$, a  digraph map (or simply  map), $f:G\to H$,
is a map on vertices, $f:V(G)\to V(H)$, such that

$i\to j\implies f(i)\to f(j)\text{ or }f(i)=f(j).$ (2.14)

Given a vertex map $f:V(G)\to V(H)$ satisfying condition (2.14), we say $f$
induces a digraph map $G\to H$.

  2. (b)

A digraph map $f:G\to H$ is called an  inclusion if $V(G)\subseteq V(H)$ and
$f$ is induced by the inclusion vertex map.

  3. (c)

Given two weighted digraphs $G,H$, a digraph map $f:G\to H$ is called a
contraction if for all nodes $i,j\in V(G)$, we have

$d_{H}(f(i),f(j))\leq d_{G}(i,j)$ (2.15)

where $d_{G}$ and $d_{H}$ are the shortest-path quasimetrics on $G$ and $H$
respectively.

######  Notation 2.13.

  1. (a)

For $e=(i,j)\in E(G)$, we denote
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}f(e)}:=(f(i),f(j))$.
Note that $f(e)\in E(H)\sqcup\Delta_{V(H)}$.

  2. (b)

Given a path $p=(v_{0},e_{1},\dots,e_{k},v_{k})$ and a digraph map $f:G\to H$,
the  image of $p$ is the path,
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}f(p)}$,
obtained from

$(f(v_{0}),f(e_{1}),f(v_{1}),\dots,f(e_{k}),f(v_{k}))$ (2.16)

by removing $f(e_{i})$ and $f(v_{i})$ from the sequence if $f(e_{i})$ is a
self-loop.

######  Remark 2.14.

Suppose $f:G\to H$ is a weighted digraph such that $w(H)(f(e))\leq w(G)(e)$
for every edge $e\in E(G)$ with $f(e)\not\in\Delta_{V(H)}$. Then for any path
$p:i\leadsto j$ in $G$, $f(p)$ is a path $f(i)\leadsto f(j)$ in $H$ and
$\operatorname*{len}(f(p))\leq\operatorname*{len}(p)$. Hence, $f$ is certainly
a contraction. However, this is not a necessary contraction since the shortest
path joining $f(i)\leadsto f(j)$ need not be the image of the shortest path
joining $i\leadsto j$.

Given these ways of mapping between (weighted) digraphs, a number of
categories naturally arise.

######  Definition 2.15.

  1. (a)

We denote the category of simple digraphs, directed acyclic graphs and
oriented graphs, where the morphisms are all digraph maps, by
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>respectively.

  2. (b)

We use the prefix
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>to denote the corresponding categories of _weighted_ digraphs where a morphism
is any digraph map of the underlying, unweighted digraphs. For example,
$\bm{\mathrm{WDgr}}$ is a category of weighted simple digraphs.

  3. (c)

For a category of weighted digraphs, we use the prefix
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>to denote the subcategory, containing all objects, with the additional
restriction that morphisms must be contractions.

  4. (d)

For a category of weighted or unweighted digraphs, we use the prefix
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>to denote the wide subcategory, containing all objects, with the additional
restriction that morphisms must be inclusions.

###  2.3 Path homology

Path homology is a homology theory for directed graph, which was first
introduced by [23] [23]. Subsequent papers prove Künneth theorems for
Cartesian products and joins [22], and invariance under an appropriate
notation of digraph homotopy [24] A directed network gives rise to a natural
filtration of digraphs which leads to a stable theory of persistent path
homology [12]. (Persistent) path homology has also been extended to vertex-
weighted digraphs [27]. Path homology can be defined for an arbitrary  path
complex; here we present the definition for a digraph.

Fix a ring $R$ and a simple directed graph $G=(V,E)$.

######  Definition 2.16.

The following definitions classify sequences of vertices in $V$:

  1. (a)

An  elementary $p$-path is any sequence $v_{0}\dots v_{p}$ of $(p+1)$
vertices, $v_{i}\in V$.

  2. (b)

An elementary $p$-path, $v_{0}\dots v_{p}$, is  regular if $v_{i}\neq v_{i+1}$
for every $i$. Otherwise, we say it is  non-regular.

  3. (c)

An elementary $p$-path, $v_{0}\dots v_{p}$, is  allowed if $(v_{i},v_{i+1})\in
E$ for every $i$.

######  Definition 2.17.

We freely generate $R$-modules from these sequences of vertices, for each
$p\geq 0$.

$\displaystyle\Lambda_{p}:=\Lambda_{p}(G;R)$
$\displaystyle:=R\big{\langle}\left\\{v_{0}\dots v_{p}\text{ elementary
}p\text{-path on }V\right\\}\big{\rangle}$ (2.17)
$\displaystyle\mathcal{R}_{p}:=\mathcal{R}_{p}(G;R)$
$\displaystyle:=R\big{\langle}\left\\{v_{0}\dots v_{p}\text{ regular
}p\text{-path on }V\right\\}\big{\rangle}$ (2.18)
$\displaystyle\mathcal{A}_{p}:=\mathcal{A}_{p}(G;R)$
$\displaystyle:=R\big{\langle}\left\\{v_{0}\dots v_{p}\text{ allowed
}p\text{-path in }G\right\\}\big{\rangle}$ (2.19)

For $p=-1$, we let $\Lambda_{-1}:=\mathcal{R}_{-1}:=\mathcal{A}_{-1}:=R$.

######  Definition 2.18.

Given $p\geq 0$, the  non-regular boundary map
$\partial^{\mathcal{N}}_{p}:\Lambda_{p}\to\Lambda_{p-1}$ is given on the
standard basis by

$\partial^{\mathcal{N}}_{p}(v_{0}\dots
v_{p}):=\sum_{i=0}^{p}(-1)^{i}v_{0}\dots\hat{v_{i}}\dots v_{p}$ (2.20)

where $v_{0}\dots\hat{v_{i}}\dots v_{p}$ is the $(p-1)$-path obtained by
removing $v_{i}$ from $v_{0}\dots v_{p}$.

######  Definition 2.19.

Since $\mathcal{R}_{p}\subseteq\Lambda_{p}$, let
$\pi:\Lambda_{p}\to\mathcal{R}_{p}$ denote the projection map onto
$\mathcal{R}_{p}$. The  regular boundary map
$\partial_{p}:\mathcal{R}_{p}\to\mathcal{R}_{p-1}$ is given by

$\partial_{p}:=\pi\circ\partial^{\mathcal{N}}_{p}.$ (2.21)

This boundary operator does not pass down to a boundary operator between the
$\left\\{\mathcal{A}_{p}\right\\}$ so we must define the following sub-
modules.

######  Definition 2.20.

The  space of $\partial$-invariant $p$-paths is

$\Omega_{p}:=\Omega_{p}(G;R):=\left\\{v\in\mathcal{A}_{p}\mathrel{}\middle|\mathrel{}\partial_{p}v\in\mathcal{A}_{p-1}\right\\}.$
(2.22)

######  Remark 2.21.

Note that $\partial_{p}$ restricts to a homomorphism
$\Omega_{p}\to\Omega_{p-1}$ and a standard check confirms that
$\partial_{p-1}\circ\partial_{p}=0$ [23, Lemma 2.9]

######  Definition 2.22.

The  regular path (chain) complex is

${\dots}$${\Omega_{2}}$${\Omega_{1}}$${\Omega_{0}}$${R}$${0}$$\scriptstyle{\partial_{3}}$$\scriptstyle{\partial_{2}}$$\scriptstyle{\partial_{1}}$$\scriptstyle{\partial_{0}}$$\scriptstyle{\partial_{-1}}$
(2.23)

The homology of the regular path complex is the  regular path homology of $G$,
the $k^{th}$ homology group is

$H_{k}:=H_{k}(G;R):=\frac{\ker\partial_{k}}{\operatorname{im}\partial_{k+1}}.$
(2.24)

The  $k^{th}$ Betti number is $\beta_{k}:=\operatorname{rank}H_{k}$.

######  Definition 2.23.

Given a digraph map $f:G\to H$, the  induced map
${f}_{\\#}:\mathcal{R}_{p}(G)\to\mathcal{R}_{p}(H)$ is given on the standard
basis by

${f}_{\\#}(v_{0}\dots v_{p}):=\begin{cases}f(v_{0})\dots f(v_{p})&\text{if
}f(v_{0})\dots f(v_{p})\text{ is regular}\\\ 0&\text{otherwise}\end{cases}$
(2.25)

######  Lemma 2.24 ([24, Theorem 2.10], [12, Proposition A.2]).

The induced maps restrict to maps ${f}_{\\#}:\Omega_{p}(G)\to\Omega_{p}(H)$
which commute with $\partial_{p}$ and hence form chain maps between the
regular path complexes. Moreover these chain maps are functorial, i.e.
${(f\circ g)}_{\\#}={f}_{\\#}\circ{g}_{\\#}$ and
${(\mathrm{id})}_{\\#}=\mathrm{id}$. Hence $\Omega$ is a functor
$\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$.

We will primarily be interested in the $1^{st}$ homology group $H_{1}$. Hence
the following characterisation of the low-dimensional chain groups will be of
use.

######  Proposition 2.25 ([23, § 3.3]).

For any simple digraph $G=(V,E)$, $\Omega_{0}(G)$ is isomorphic to the
$R$-module freely generated by the vertices and $\Omega_{1}(G)$ is isomorphic
to the $R$-module freely generated by the edges, i.e.

$\Omega_{0}(G)\cong R\\!\left\langle
V\right\rangle\quad\text{and}\quad\Omega_{1}(G)\cong R\\!\left\langle
E\right\rangle.$ (2.26)

######  Notation 2.26.

Note that an edge $e=(a,b)\in E$ gives rise to an allowed 1-path
$ab\in\mathcal{A}_{1}(G)$. Moreover, $ab\in\Omega_{1}(G)$. For ease of
notation, given an edge $e\in E$, we will also use $e=ab\in\Omega_{1}(G)$ to
refer to the generator in $\Omega_{1}(G)$.

Since $\Omega_{1}$ is generated by edges in $G$, any trail $p$ has a
representative.

######  Notation 2.27.

Given a directed trail $p=(e_{1},\dots,e_{k})$ in a digraph $G$, the
representative of $p$ is

$\mathfrak{R}({p}):=\sum_{i=1}^{k}e_{i}\in\Omega_{1}.$ (2.27)

Likewise, there is a representative for any undirected circuit.

######  Notation 2.28.

Given an undirected circuit $p=(v_{0}=a,e_{1},v_{1},\dots,e_{k},v_{k}=a)$ in a
digraph $G$, the  representative of $p$ is

$\mathfrak{R}({p}):=\sum_{i=1}^{k}\alpha_{i}e_{i}\in\Omega_{1}.$ (2.28)

where $\alpha_{i}=1$ if $e_{i}=(v_{i-1},v_{i})$, else $\alpha_{i}=-1$.

######  Remark 2.29.

The representative of a circuit $p$, does not depend on the starting point,
but if $p^{\prime}$ traverses the circuit in the opposite direction then
$\mathfrak{R}({p^{\prime}})=-\mathfrak{R}({p})$.

$i$$j$ (a)

$i$$j$$k$ (b)

$i$$j$$k$$m$ (c)

$i$$j$$m$$l$$k$ (d)

Figure 2: The three types of generators for $\Omega_{2}(G;\mathbb{Z})$ and
$\Omega_{2}(G;\mathbb{R})$: (a) A double edge. (b) A directed triangle. (c) A
long square (the dashed red edge must not be present). Finally (d) shows a
linear dependency between long squares.

######  Proposition 2.30 ([24, Proposition 2.9], [16, Theorem 3]).

Let G be a finite, simple digraph and $R=\mathbb{R}\text{ or }\mathbb{Z}$. Any
$\omega\in\Omega_{2}(G;R)$ can be written as a linear combination of
$\partial$-invariant $2$-paths of the following three types:

  1. (a)

$(iji)$ where $i\to j\to i$ (double edge);

  2. (b)

$(ijk)$ where $i\to j\to k$, $i\to k$ and $i\neq k$ (directed triangle); and

  3. (c)

$(ijk-imk)$ where $i\to j\to k$, $i\to m\to k$, $i\not\to k$ and $i\neq k$
(long square).

First note that all of the elements identified in Proposition 2.30 are
elements of $\Omega_{2}(G;R)$ and hence they form a generating set. However,
the generators corresponding to long squares are not necessarily linearly
independent. For example, in Figure 2(d), we see

$(ijk-ilk)=(ijk-imk)+(imk-ilk).$ (2.29)

Removing some long squares to account for these linear relations, we can
obtain a basis of $\Omega_{2}(G;\mathbb{R})$.

###  2.4 Persistent homology

Topological data analysis (TDA) is a field of applied mathematics which
employs the powerful, discriminative tools of algebraic topology to study
complex datasets . The cornerstone of the field is persistent homology (PH)
which yields a stable, discrete, topological invariant, called a barcode (see
[5, 9, 33] for an overview). The barcode summarises topological features in
the data (e.g. connected components and loops) and measures the range of
scales across which they persist.

######  Definition 2.31.

  1. (a)

A  persistent chain complex is a functor $\bm{\mathrm{R}}\to\bm{\mathrm{Ch}}$.

  2. (b)

A  persistent vector space is a functor $\bm{\mathrm{R}}\to\bm{\mathrm{Vec}}$.
We denote the category of such functors
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\bm{\mathrm{PersVec}}}:=\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]}$.

  3. (c)

A persistent vector space $M$ is  pointwise finite-dimensional (p.f.d) if
$M(t)$ is finite dimensional for all $t\in\mathbb{R}$, that is
$M\in\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{vec}}\textbf{]}$. We denote the
category of p.f.d persistent vector spaces
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\bm{\mathrm{Persvec}}}:=\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{vec}}\textbf{]}$.

  4. (d)

A persistent vector space $M:\bm{\mathrm{R}}\to\bm{\mathrm{Vec}}$ is  tame
[31] if

    1. (i)

$M(t)$ is finite dimensional for all $t\in\mathbb{R}$, and

    2. (ii)

there are finitely many $t\in\mathbb{R}$ such that there is no $\epsilon>0$
such that $M(t-\epsilon\leq t+\epsilon)$ is an isomorphism.

  5. (e)

For an interval $I\subseteq R$, we define the  corresponding interval,
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}P(I)}\in\bm{\mathrm{PersVec}}$,
in which the vector spaces are

$P(I)(t):=\begin{cases}\mathbb{R}&\text{if }t\in I,\\\
0&\text{otherwise},\end{cases}$ (2.30)

and $P(I)(s\leq t)$ is the identity if $s,t\in I$ and the trivial map
otherwise.

  6. (f)

Given $M,N\in\bm{\mathrm{PersVec}}$, their direct sum
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>N}\in\bm{\mathrm{PersVec}}$ is given pointwise by

$\displaystyle(M\oplus N)(t)$ $\displaystyle:=M(t)\oplus N(t),$ (2.31)
$\displaystyle(M\oplus N)(s\leq t)$ $\displaystyle:=M(s\leq t)\oplus N(s\leq
t).$ (2.32)

  7. (g)

A  morphism of persistent vector spaces is a morphism in the category
$\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]}$. That is, for
$M,N\in\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]}$ a morphism
$\phi:M\to N$ is a family of linear maps $\left\\{\phi_{t}:M(t)\to
N(t)\right\\}$ such that

$N(s\leq t)\circ\phi_{s}=\phi_{t}\circ M(s\leq t)$ (2.33)

whenever $s\leq t$. We say $\phi$ is an  isomorphism if each $\phi_{t}$ is an
isomorphism of vector spaces. If an isomorphism $M\to N$ exists, we write
$M\cong N$.

A (p.f.d) persistent vector space can be decomposed as a direct sum of
interval modules, the _indecomposable_ persistent vector spaces. Moreover,
this decomposition is unique, discrete and finite in all practical
applications.

######  Theorem 2.32 (Structure Theorem for p.f.d persistent vector
spaces,[15, Theorem 1.1],[10, Theorem 2.8]).

Given $M\in\bm{\mathrm{Persvec}}$, there is a multiset $\mathcal{B}{M}$ of
intervals of $\mathbb{R}$ such that

$M\cong\bigoplus_{I\in\mathcal{B}{M}}P(I)$ (2.34)

and any such decomposition is unique, up to reordering. We call
$\mathcal{B}{M}$ the  barcode of $M$.

######  Definition 2.33.

  1. (a)

A multiset of intervals of $\mathbb{R}$ is called a  barcode.

  2. (b)

We call an interval $I$ in a barcode a  feature. If $I$ starts at $a$ and ends
at $b$, we say the feature is  born at time $a$ and  dies at time $b$.

  3. (c)

Given a barcode $\mathcal{B}$, the  diagram of $\mathcal{B}$ is the multiset
of endpoints

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\operatorname{Dgm}(B)}:=\left\\{\\!\\!\left\\{(a_{k},b_{k})\mathrel{}\middle|\mathrel{}I_{k}\in\mathcal{B}\text{
has endpoints }a_{k}\leq b_{k}\right\\}\\!\\!\right\\}.$ (2.35)

  4. (d)

Given $M\in\bm{\mathrm{Persvec}}$, the  persistence diagram of $M$ is
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\operatorname{Dgm}(M)}:=\operatorname{Dgm}(\mathcal{B}{M})$.

The barcode can be used as a summary of the persistent vector space. When
arising as the homology of a filtration of topological spaces, this summary
captures how topological features are born and killed throughout the
filtration. In order to use this summary for further statistics, it is
desirable that this summary is _stable_ to noise and perturbations in the
input data. To quantify this stability, we require metrics on persistent
vector spaces and the resulting barcodes.

######  Definition 2.34 ([17]).

Given two multisets $D_{1},D_{2}\subseteq\mathbb{R}^{2}$, the  bottleneck
distance is

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}d_{B}(D_{1},D_{2})}:=\inf_{\gamma}\sup_{x\in
D_{1}\cup\Delta_{\mathbb{R}}}|\\!|x-\gamma(x)|\\!|_{\infty}$ (2.36)

where $\gamma$ is over all multi-bijections $D_{1}\cup\Delta_{\mathbb{R}}\to
D_{2}\cup\Delta_{\mathbb{R}}$ and
$\Delta_{\mathbb{R}}=\left\\{(x,x)\mathrel{}\middle|\mathrel{}x\in\mathbb{R}\right\\}$
is the diagonal with multiplicity $1$. Given barcodes $\mathcal{B}_{1}$,
$\mathcal{B}_{2}$, we define the bottleneck distance between them to be the
bottleneck distance between their diagrams

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}d_{B}(\mathcal{B}_{1},\mathcal{B}_{2})}:=d_{B}(\operatorname{Dgm}(\mathcal{B}_{1}),\operatorname{Dgm}(\mathcal{B}_{2})).$
(2.37)

######  Definition 2.35 ([14]).

Given $p\geq 1$ and two multisets $D_{1},D_{2}\subseteq\mathbb{R}^{2}$, the
$p$-Wasserstein distance [14] is

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}d_{W_{p}}(D_{1},D_{2})}:=\inf_{\gamma}\left(\sum_{x\in
D_{1}\cup\Delta_{\mathbb{R}}}|\\!|x-\gamma(x)|\\!|_{\infty}^{p}\right)^{1/p}$
(2.38)

where $\gamma$ is over all multi-bijections $D_{1}\cup\Delta_{\mathbb{R}}\to
D_{2}\cup\Delta_{\mathbb{R}}$ and
$\Delta_{\mathbb{R}}=\left\\{(x,x)\mathrel{}\middle|\mathrel{}x\in\mathbb{R}\right\\}$
is the diagonal with multiplicity $1$. The $p$-Wasserstein between two
barcodes $\mathcal{B}_{1}$, $\mathcal{B}_{2}$, is

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}d_{W_{p}}(\mathcal{B}_{1},\mathcal{B}_{2})}:=d_{B}(\operatorname{Dgm}(\mathcal{B}_{1}),\operatorname{Dgm}(\mathcal{B}_{2})).$
(2.39)

######  Definition 2.36 ([1]).

Given a category $\bm{\mathcal{C}}$, fix
$M,N\in\textbf{[}\bm{\mathrm{R}},\,\bm{\mathcal{C}}\textbf{]}$ and $\delta\geq
0$.

  1. (a)

The  $\delta$-shift of $M$ is
$M[\delta]\in\textbf{[}\bm{\mathrm{R}},\,\bm{\mathcal{C}}\textbf{]}$ where

$M[\delta](t):=M(t+\delta)\quad\text{ and }\quad M[\delta](s\leq
t):=M(s+\delta\leq t+\delta).$ (2.40)

  2. (b)

Given a morphism
$f\in\mathrm{Mor}_{\textbf{[}\bm{\mathrm{R}},\,\bm{\mathcal{C}}\textbf{]}}(M,N)$
the  $\delta$-shift of $f$ is $f[\delta]:M[\delta]\to N[\delta]$ in which
$f_{t}:=f_{t+\delta}$. When clear from context we often denote $f[\delta]=f$.

  3. (c)

The  $\delta$-transition morphism is a morphism
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathcal{T}(M,\delta)}:M\to
M[\delta]$ which at $t\geq 0$ is given by $M(t\leq t+\delta)$.

  4. (d)

A  $\delta$-interleaving is a pair of morphisms $\phi:M\to N[\delta]$ and
$\psi:N\to M[\delta]$ such that

$\psi[\delta]\circ\phi=\mathcal{T}(M,2\delta)\quad\text{ and
}\quad\phi[\delta]\circ\psi=\mathcal{T}(N,2\delta).$ (2.41)

  5. (e)

The  interleaving distance of $M$ and $N$ is

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}d_{I}(M,N)}:=\inf\left\\{\delta\geq
0\mathrel{}\middle|\mathrel{}\exists\;\delta\text{-interleaving}\right\\}.$
(2.42)

######  Remark 2.37.

Recall that, given a $\delta$-interleaving $\phi$ and $\psi$, in order to
constitute morphisms $M\to N[\delta]$ and $N\to M[\delta]$, they must satisfy
relations

$\phi_{t}\circ M(s\leq t)=N(s+\delta\leq t+\delta)\circ\psi_{s}\quad\text{ and
}\quad\psi_{t}\circ N(s\leq t)=M(s+\delta\leq t+\delta)\circ\phi_{s}$ (2.43)

for each $s\leq t$.

Now that we have metrics on persistent vector spaces and their barcode
summaries, we can state the isometry theorem. This guarantees that the barcode
is a stable summary of the input persistent vector space.

######  Theorem 2.38 (Isometry Theorem [1, Theorem 3.5]).

Given p.f.d persistent vector spaces $M,N\in\bm{\mathrm{Persvec}}$,

$d_{B}(\mathcal{B}{M},\mathcal{B}{N})=d_{I}(M,N).$ (2.44)

Finally, when a persistent vector space is tame, there are finitely many
critical values $t_{0}<\dots<t_{k}$ such that if $t_{i-1}<s\leq t<t_{i}$ then
$M(s\leq t)$ is an isomorphism [10]. Hence, all information of the persistent
vector space is contained within the maps $M(t_{i-1}\leq t_{i})$ for
$i=1,\dots,k$. In particular, any interval in the barcode must have its
endpoints at one of the critical values (or $\pm\infty$). In these scenarios,
it suffices to consider $M$ as a functor
$\textbf{[}\bm{k}\textbf{]}\to\bm{\mathrm{Vec}}$, where
$\textbf{[}\bm{k}\textbf{]}$ is the sub-poset of $\bm{\mathrm{R}}$ consisting
of the integers $0,\dots,k$ [31].

##  3 Motivation and definition of GrPPH

Firstly, in Section 3.1, we describe a standard pipeline for extracting a
topological summary from a weighted digraph, and illustrate a number of issues
that naturally arise. Motivated by this in Section 3.2, we alter the standard
pipeline in order to define a ‘grounded pipeline’. We prove that this new
pipeline is functorial in an appropriate sense, which we will later exploit
for stability results. The pipeline is parameterised by two choices; in
Section 3.3 we fix these choices in order to define our proposed descriptor.

###  3.1 Standard pipeline

A typical TDA pipeline for weighted digraphs consists of three ingredients:

  1. 1.

a map
$F:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]})$,
which assigns a filtration of digraphs to every weighted digraph;

  2. 2.

a chain complex functor $C:\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$ which maps
each digraph to a chain complex and induces chain map for every digraph map;
and finally

  3. 3.

a choice of homology functor $H_{k}:\bm{\mathrm{Ch}}\to\bm{\mathrm{Vec}}$ in
some degree $k$.

These components can then be combined into the following pipeline.

${\mathcal{H}_{k}:\bm{\mathrm{WDgr}}}$${\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}}$${\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}}$${\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]}}$$\scriptstyle{F}$$\scriptstyle{\textbf{[}\bm{\mathrm{R}},\,C\textbf{]}}$$\scriptstyle{\textbf{[}\bm{\mathrm{R}},\,H_{k}\textbf{]}}$

We obtain a map
$\mathcal{H}_{k}:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]})$
given by
$\mathcal{H}_{k}:=\textbf{[}\bm{\mathrm{R}},\,H_{k}\textbf{]}\circ\textbf{[}\bm{\mathrm{R}},\,C\textbf{]}\circ
F$. Since $F$ is not a priori functorial, neither is $\mathcal{H}_{k}$. Under
mild assumptions on $F$ and $C$, it is possible to define a subcategory of
$\bm{\mathrm{WDgr}}$ which makes this pipeline functorial.

######  Notation 3.1.

Given
$F:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]})$,
$G\in\bm{\mathrm{WDgr}}$ and $s\leq t$ we write

  1. (a)

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}F^{t}G}:=F(G)(t)$,
the image of $t$ under the functor $F(G)$; and

  2. (b)

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\iota(s,t)}:=F(G)(s\leq
t)$, the image of $s\leq t$ under the functor $F(G)$.

######  Definition 3.2.

  1. (a)

A  filtration map is any map
$F:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Incl}}\bm{\mathrm{Dgr}}\textbf{]})$
such that $V(F^{t}G)\subseteq V(G)$ for all $t\in\mathbb{R}$. In particular,
$\iota(s,t)$ must always be an inclusion.

  2. (b)

Given a filtration map $F$, a morphism of weighted digraphs
$f\in\mathrm{Mor}_{\bm{\mathrm{WDgr}}}(G,H)$ is called  $F$-compatible if for
every $t\in\mathbb{R}$ the underlying vertex map $f:V(G)\to V(H)$ restricts to
a vertex map $V(F^{t}G)\to V(F^{t}H)$ which in turn yields a digraph map
$F^{t}G\to F^{t}H$.

  3. (c)

Given a filtration map $F$, the  $F$-compatible category of weighted digraphs,
$\bm{\mathrm{WDgr}}_{F}$, is the subcategory of $\bm{\mathrm{WDgr}}$ such that
$\mathrm{Obj}(\bm{\mathrm{WDgr}}_{F})=\mathrm{Obj}(\bm{\mathrm{WDgr}})$ and

$\mathrm{Mor}(\bm{\mathrm{WDgr}}_{F})=\left\\{f\in\mathrm{Mor}(\bm{\mathrm{WDgr}})\mathrel{}\middle|\mathrel{}f\text{
is }F\text{-compatible}\right\\}.$ (3.1)

######  Lemma 3.3.

Any filtration map
$F:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Incl}}\bm{\mathrm{Dgr}}\textbf{]})$
induces a functor
$F:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$,
which we call a  filtration functor.

###### Proof.

Given $f\in\mathrm{Mor}_{\bm{\mathrm{WDgr}}_{F}}(G,H)$, since $f$ is
$F$-compatible, the underlying vertex map induces digraph maps $f:F^{t}G\to
F^{t}H$ for every $t\in\mathbb{R}$. Given $s\leq t$, both $F(G)(s\leq t)$ and
$F(H)(s\leq t)$ are digraph maps induced by the inclusion vertex map. Hence
the following square of morphisms in $\bm{\mathrm{Dgr}}$ commutes.

${F^{s}G}$${F^{s}H}$${F^{t}G}$${F^{t}H}$$\scriptstyle{F(G)(s\leq
t)}$$\scriptstyle{f}$$\scriptstyle{F(H)(s\leq t)}$$\scriptstyle{f}$

Hence $f$ induces a natural transformation between $F(G)$ and $F(H)$.
Moreover, since each $f:F^{t}G\to F^{t}H$ is fully determined by the
underlying vertex map $V(G)\to V(H)$, this construction is certainly
functorial. ∎

######  Remark 3.4.

Since any filtration map induces a filtration functor, it suffices to define a
filtration functor only as a map on objects.

When $F$ is a filtration map, it induces a functor
$\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$
and hence $\mathcal{H}_{k}$ is a functor
$\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]}$,
as desired. We will now consider an illustrative example of this pipeline.
Assuming the weight of an edge corresponds to a distance between its endpoints
(e.g. the time it takes for a particle to flow down the edge), a natural
choice of filtration functor is the following.

######  Definition 3.5.

The  shortest-path filtration is a map
$F_{d}:\bm{\mathrm{WDgr}}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$.
For $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and $t\in\mathbb{R}$, we define

$F_{d}(G)(t):=G^{t}:=(V,E^{t})\quad\text{ where }\quad
E^{t}:=\left\\{(i,j)\mathrel{}\middle|\mathrel{}d(i,j)\leq t\right\\}$ (3.2)

and $d$ is the shortest-path quasimetric on $G$. For $s\leq t$, the digraph
map $G^{s}\to G^{t}$ is induced by the identity vertex map $\mathrm{id}_{V}$.

$G_{1}$DeathBirth$1$$2$$\times 1$$G_{2}$DeathBirth$0.5$$1$$2$$\times 1$$\times
2$

Figure 3: Persistent path homology of the shortest-path filtration of flow
through a bifurcation network, before and after edge subdivision. In $G_{1}$
all edges have unit weight, in $G_{2}$ all edges have weight $0.5$.

######  Example 3.6.

Choosing $F=F_{d}$ as above and $C$ to be the regular path complex, we obtain
a functor
$\mathcal{H}_{k}:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]}$.
The shortest-path quasimetric of a weighted digraph is a directed network and
this pipeline measures the persistent path homology of that network. This
pipeline was first considered in [12] for cycle networks, alongside a
stability analysis of persistent path homology for arbitrary directed
networks.

In Figure 3 we apply this pipeline (with $k=1$) to a small bifurcating network
$G_{1}$, a toy model for vasculature networks, in which each edge is given
unit weight. The resulting barcode has a single feature with lifetime $[1,2)$.
The second network, $G_{2}$, is obtained by subdividing each edge in $G_{1}$,
giving all edges weight $0.5$. The resulting barcode is
$\left\\{\\!\\!\left\\{[0.5,1),[0.5,1),[0.5,2)\right\\}\\!\\!\right\\}$ which
has three features.

This example highlights three key issues with this pipeline:

  1. (a)

the number of features in the barcode changes upon subdivision;

  2. (b)

loops bounded by triangles or long squares are ‘killed’ as soon as they are
born; and

  3. (c)

the birth-time of each feature is an artefact of the ‘resolution’ of the
weighted digraph.

A subtler issue arises when we attempt to interpret the diagram. A feature
born at time $t$ is supported on edges of the digraph $G^{t}$, which may not
be edges in the original weighted digraph $G$. This makes interpretation of
features more challenging.

###  3.2 Grounded pipeline

We now describe an alteration to the standard pipeline which alleviates these
issues by including the underlying digraph $G$ in degree 1 for all
$t\in\mathbb{R}$. The main distinction is that we do not factor through a
filtration functor $F$. Instead, we use $F$ and
$C\in\textbf{[}\bm{\mathrm{Dgr}},\,\bm{\mathrm{Ch}}\textbf{]}$ to construct a
new functor
$\prescript{g}{}{C}_{F}:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}$.

${\bm{\mathrm{WDgr}}}$${\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}}$${\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}}$${\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Vec}}\textbf{]}}$$\scriptstyle{F}$$\prescript{g}{}{C}_{F}$$\scriptstyle{\textbf{[}\bm{\mathrm{R}},\,C\textbf{]}}$$\scriptstyle{\textbf{[}\bm{\mathrm{R}},\,H_{1}\textbf{]}}$

In order to define the map on objects, we only need a weaker condition on $C$.

######  Definition 3.7.

Given a filtration functor
$F:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$,
a functor $C:\bm{\mathrm{Incl}}\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$,
$G\in\bm{\mathrm{WDgr}}$ and $t\in\mathbb{R}$, the chain complex
$\prescript{g}{}{C}_{\bullet}(G,t;F)$ is the top row of the following diagram.

${\cdots C_{3}(F^{t}G)}$${C_{2}(F^{t}G)}$${C_{1}(G\cup F^{t}G)}$${C_{0}(G\cup
F^{t}G)\cdots}$${C_{1}(F^{t}G)}$${C_{0}(F^{t}G)}$$\scriptstyle{\partial_{3}}$$\scriptstyle{{\iota}_{\\#}\circ\partial_{2}}$$\scriptstyle{\partial_{2}}$$\scriptstyle{\partial_{1}}$$\scriptstyle{{\iota}_{\\#}}$$\scriptstyle{\partial_{1}}$$\scriptstyle{{\iota}_{\\#}}$

In the above, $\iota:F^{t}G\hookrightarrow G\cup F^{t}G$ is the inclusion
digraph map, induced by the inclusion vertex map. Then
${\iota}_{\\#}=C(\iota)$ is the image of this map under the functor $C$. The
boundary maps $\partial_{k}$ are derived either from the chain complex
$C_{\bullet}(F^{t}G)$ or $C_{\bullet}(G\cup F^{t}G)$.

We denote the chain groups as  $\prescript{g}{}{C}_{k}(G,t;F)$ and the
boundary maps as  $\prescript{g}{}{\partial}_{k}^{t}$. When $F$ and $t$ are
clear from context, we omit them from notation

We use the prescript $\prescript{g}{}{\square}$ to denote that this chain
complex is _grounded_ ; as we will show in Lemma 4.2, after appropriate
choices of $F$ and $C$, all degree $1$ homology classes have representatives
in the underlying digraph.

######  Lemma 3.8.

For each $t\in\mathbb{R}$ and $G\in\bm{\mathrm{WDgr}}$,
$(\prescript{g}{}{C}_{\bullet}(G,t;F),\prescript{g}{}{\partial}_{\bullet}^{t})$
is a chain complex.

###### Proof.

Since ${\iota}_{\\#}$ is a chain map $C(F^{t}G)\to C(G\cup F^{t}G)$ we have

$\partial_{1}\circ({\iota}_{\\#}\circ\partial_{2})={\iota}_{\\#}\circ\partial_{1}\circ\partial_{2}=0$
(3.3)

and hence $C_{\bullet}(G,t;F)$ defines a chain complex. ∎

######  Lemma 3.9.

Given a filtration functor
$F:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$
and a functor $C:\bm{\mathrm{Incl}}\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$, the
chain complex $\prescript{g}{}{C}_{\bullet}(G,t;F)$ is functorial in $t$.

###### Proof.

For each $s\leq t$ we require chain maps
${\prescript{g}{}{\iota(s,t)}}_{\\#}:\prescript{g}{}{C}_{\bullet}(G,s)\to\prescript{g}{}{C}_{\bullet}(G,t)$
which satisfy the usual functorial axioms in $t$. First note that
$\iota(s,t):F^{s}G\to F^{t}G$ is induced by the inclusion vertex map, which is
a restriction of the identity vertex map $V(G)\to V(G)$. Hence this identity
vertex map also yields a digraph map $G\cup F^{s}G\to G\cup F^{t}G$, which we
also denote $\iota(s,t)$. Applying the functor $C$ to these digraph maps, we
obtain two chain maps, which can be joined as shown in the following diagram.

${\cdots C_{3}(F^{s}G)}$${C_{2}(F^{s}G)}$${C_{1}(G\cup F^{s}G)}$${C_{0}(G\cup
F^{s}G)\cdots}$${C_{1}(F^{s}G)}$${C_{1}(F^{t}G)}$${\cdots
C_{3}(F^{t}G)}$${C_{2}(F^{t}G)}$ ${C_{1}(G\cup F^{t}G)}$${C_{0}(G\cup
F^{t}G)\cdots}$$\scriptstyle{\partial_{3}}$$\scriptstyle{{\iota(s,t)}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{A}}$$\scriptstyle{{\iota}_{\\#}\circ\partial_{2}}$$\scriptstyle{\partial_{2}}$$\scriptstyle{{\iota(s,t)}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{B}}$$\scriptstyle{\partial_{1}}$$\scriptstyle{{\iota(s,t)}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{C}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{D}}$$\scriptstyle{{\iota(s,t)}_{\\#}}$$\scriptstyle{{\iota}_{\\#}}$$\scriptstyle{{\iota(s,t)}_{\\#}}$$\scriptstyle{{\iota}_{\\#}}$$\scriptstyle{\partial_{3}}$$\scriptstyle{{\iota}_{\\#}\circ\partial_{2}}$$\scriptstyle{\partial_{2}}$$\scriptstyle{\partial_{1}}$

Squares
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{A}$
and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{B}$
and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{D}$
commute because all vertical maps are components of the same chain map –
either ${\iota(s,t)}_{\\#}:C(F^{s}G)\to C(F^{t}G)$ or
${\iota(s,t)}_{\\#}:C(G\cup F^{s}G)\to C(G\cup F^{t}G)$. Then, in the
following diagram, all vertex maps are induced by an inclusion vertex map so
the square of morphisms commute.

${F^{s}G}$${G\cup F^{s}G}$${F^{t}G}$${G\cup
F^{t}G}$$\scriptstyle{\iota}$$\scriptstyle{\iota(s,t)}$$\scriptstyle{\iota(s,t)}$$\scriptstyle{\iota}$

Applying the functor $C$ to this diagram and restricting to degree $1$, we
obtain square
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{C}$
which must, therefore, commute. Hence, we obtain a chain map, as required.
Functoriality follows because the components of this new chain map are
themselves components of chain maps induced by functors
$F(G)\in\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$ and
$C\in\textbf{[}\bm{\mathrm{Incl}}\bm{\mathrm{Dgr}},\,\bm{\mathrm{Ch}}\textbf{]}$.
∎

######  Definition 3.10.

Given a filtration functor
$F:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$
and a functor $C:\bm{\mathrm{Incl}}\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$, the
map
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\prescript{g}{}{C}_{F}}:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]})$
is given on objects by

$\prescript{g}{}{C}_{F}(G)(t):=(\prescript{g}{}{C}_{\bullet}(G,t;F),\prescript{g}{}{\partial}^{t}_{\bullet})$
(3.4)

and the morphism $\prescript{g}{}{C}_{F}(G)(s\leq t)$ is as constructed in the
proof of Lemma 3.9.

######  Notation 3.11.

  1. (a)

We denote the induced map on chain complexes by
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{\prescript{g}{}{\iota(s,t)}}_{\\#}}:=\prescript{g}{}{C}_{F}(G)(s\leq
t)$.

  2. (b)

In each homology degree $k$, we denote the induced map on homology by
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{\prescript{g}{}{\iota(s,t)}}_{\ast}}:=\textbf{[}\bm{\mathrm{R}},\,H_{k}\textbf{]}({\prescript{g}{}{\iota(s,t)}}_{\\#})$.

Thanks to Lemma 3.9, $\prescript{g}{}{C}_{F}$ gives us a map
$\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]})$,
which we can compose with homology to obtain a persistent vector space. Under
additional functorial assumptions on $C$, when we restrict to the appropriate
category $\prescript{g}{}{C}_{F}$ becomes a functor.

######  Theorem 3.12.

Given a filtration functor
$F:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Dgr}}\textbf{]}$
and a functor $C:\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$,
$\prescript{g}{}{C}_{F}$ is a functor
$\prescript{g}{}{C}_{F}:\bm{\mathrm{WDgr}}_{F}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}$.

###### Proof.

Given $f\in\mathrm{Mor}_{\bm{\mathrm{WDgr}}_{F}}(G,H)$ and $t\in\mathbb{R}$,
we need a chain map
${\prescript{g}{}{f}}_{\\#}:\prescript{g}{}{C}_{\bullet}(G,t)\to\prescript{g}{}{C}_{\bullet}(H,t)$.
Moreover, $f$ must satisfy the usual functorial axioms, as well as commute
with ${\prescript{g}{}{\iota(s,t)}}_{\\#}$, i.e. for any $s\leq t$ we need

${\prescript{g}{}{f}}_{\\#}\circ{\prescript{g}{}{\iota(s,t)}}_{\\#}={\prescript{g}{}{\iota(s,t)}}_{\\#}\circ{\prescript{g}{}{f}}_{\\#}.$
(3.5)

Note that $f$ is given by a vertex map $f:V(G)\to V(H)$ which induces a
digraph map $G\to H$. Moreover, since $f$ is $F$-compatible, it induces
digraph maps $F^{t}G\to F^{t}H$. Therefore $f$ must also induce digraph maps
$G\cup F^{t}G\to H\cup F^{t}H$. Applying the functor $C$ to these digraph
maps, we obtain two chain maps, which can be joined as shown in the following
diagram.

${\cdots C_{3}(F^{t}G)}$${C_{2}(F^{t}G)}$${C_{1}(G\cup F^{t}G)}$${C_{0}(G\cup
F^{t}G)\cdots}$${C_{1}(F^{t}G)}$${C_{1}(F^{t}H)}$${\cdots
C_{3}(F^{t}H)}$${C_{2}(F^{t}H)}$ ${C_{1}(H\cup F^{t}H)}$${C_{0}(H\cup
F^{t}H)\cdots}$$\scriptstyle{\partial_{3}}$$\scriptstyle{{f}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{A}}$$\scriptstyle{{\iota}_{\\#}\circ\partial_{2}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{B}}$$\scriptstyle{\partial_{2}}$$\scriptstyle{{f}_{\\#}}$$\scriptstyle{\partial_{1}}$$\scriptstyle{{f}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{C}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{D}}$$\scriptstyle{{f}_{\\#}}$$\scriptstyle{{\iota}_{\\#}}$$\scriptstyle{{f}_{\\#}}$$\scriptstyle{{\iota}_{\\#}}$$\scriptstyle{\partial_{3}}$$\scriptstyle{{\iota}_{\\#}\circ\partial_{2}}$$\scriptstyle{\partial_{2}}$$\scriptstyle{\partial_{1}}$

Squares
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{A}$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{B}$
and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{D}$
all commute because all vertical maps are parts of the same chain maps –
either ${f}_{\\#}:C(F^{t}G)\to C(F^{t}H)$ or ${f}_{\\#}:C(G\cup F^{t}G)\to
C(H\cup F^{t}H)$. Since the inclusion digraph map $\iota:G\to G\cup F^{t}G$ is
induced by an inclusion vertex map, it certainly commutes with $f$ and hence
square
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{C}$
commutes. Hence, the whole diagram commutes and yields a chain map.

This construction is functorial thanks to the functoriality of the underlying
induced chain maps. Finally, since $\iota(s,t)$ is always an inclusion vertex
map, $f$ must commutes with each $\iota(s,t)$. Hence, the two morphisms
commute past each other as required by equation (3.5). ∎

######  Notation 3.13.

Given a morphism $f\in\mathrm{Mor}(\bm{\mathrm{WDgr}}_{F})$, we denote the
induced map on chain complexes, constructed above, by
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{\prescript{g}{}{f}}_{\\#}}:=\prescript{g}{}{C}_{F}(f)$
and the induced map on homology in degree $k$ by
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}{\prescript{g}{}{f}}_{\ast}}:=\textbf{[}\bm{\mathrm{R}},\,H_{k}\textbf{]}({\prescript{g}{}{f}}_{\\#})$.

###  3.3 Definition of GrPPH

In order to investigate properties and stability of the grounded pipeline, we
make choice for both $F$ and $C$. As we have already discussed, since we
interpret edge-weights as a measure of distance, a natural choice for $F$ is
the shortest-path filtration. Choices for $C$ include the regular path
complex, non-regular path complex and the directed flag complex. However, the
latter two constructions are _not_ functors
$\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$. Henceforth, for the rest of the paper,
we fix $F$ to be the shortest-path filtration and $C$ to be the regular path
complex,

$F=F_{d}\quad\text{ and }\quad C=\Omega.$ (3.6)

Since $F$ is fixed, we will largely remove it from notation. We also use $C$
instead of $\Omega$.

######  Lemma 3.14.

The $F_{d}$-compatible category of weighted digraphs is the contraction
category of weighted digraphs (see Definition 2.15),
${\bm{\mathrm{WDgr}}}_{F_{d}}=\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}$.

###### Proof.

First note $f\in\mathrm{Mor}(\bm{\mathrm{WDgr}})$ is precisely a vertex map
$f:V(G)\to V(H)$ which induces a digraph map $G\to H$. A vertex map $f:V(G)\to
V(H)$ induces a digraph map $G^{t}\to H^{t}$ for every $t\in\mathbb{R}$ if and
only if

$d(f(i),f(j))\leq d(i,j)$ (3.7)

for every $i,j\in V(G)$. Hence, $f\in\mathrm{Mor}(\bm{\mathrm{WDgr}})$ is
$F_{d}$-compatible if and only if it is a contraction map. So a morphism
$f\in\mathrm{Mor}({\bm{\mathrm{WDgr}}}_{F_{d}})$ is precisely a contraction
digraph map $G\to H$. ∎

Now that we understand the category ${\bm{\mathrm{WDgr}}}_{F_{d}}$, applying
Theorem 3.12 yields a functor
$\prescript{g}{}{C}:\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}$.
Taking the first homology yields a persistent vector space in a functorial
way; this functor is our proposed invariant for weighted digraphs.

######  Definition/Theorem 3.15.

Grounded persistent path homology (GrPPH) is the functor

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\prescript{g}{}{\mathcal{H}}_{1}}:=\textbf{[}\bm{\mathrm{R}},\,H_{1}\textbf{]}\circ\prescript{g}{}{C}:\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}\to\bm{\mathrm{PersVec}}$
(3.8)

from the contraction category of weighted digraphs (see Definition 2.15) to
the category of persistent vector spaces (see Definition 2.31).

######  Notation 3.16.

Given $G\in\bm{\mathrm{WDgr}}$, in degree $k$ at filtration step $t$, we
denote

$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>space of grounded\ }k\text{-cycles}}\text{ by}$
$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\prescript{g}{}{Z}(G,t)}$
$\displaystyle:=\ker\prescript{g}{}{\partial}_{k}^{t};$ (3.9)
$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>space of grounded\ }k\text{-boundaries}}\text{ by}$
$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\prescript{g}{}{B}(G,t)}$
$\displaystyle:=\operatorname{im}\prescript{g}{}{\partial}_{k+1}^{t}$ (3.10)
$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>(degree }k\text{) grounded\ homology}}\text{ by}$
$\displaystyle{\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\prescript{g}{}{H}_{k}(G,t)}$
$\displaystyle:=\frac{\prescript{g}{}{Z}_{k}(G,t)}{\prescript{g}{}{B}_{k}(G,t)}.$
(3.11)

######  Remark 3.17.

Note that for any $t\in\mathbb{R}$,

$\displaystyle k>1$ $\displaystyle\implies\prescript{g}{}{H}_{k}(G,t)\cong
H_{k}(G^{t}),$ $\displaystyle k<1$
$\displaystyle\implies\prescript{g}{}{H}_{k}(G,t)\cong H_{k}(G\cup G^{t}).$

Therefore, the only new homology occurs in degree $k=1$, since it compares
$1$-cycles in $G\cup F^{t}G$ with $1$-boundaries from $G^{t}$. This justifies
our focus on degree $1$ homology in Definition/Theorem 3.15.

$G_{1}$$G_{2}$

Figure 4: A bifurcation network, before and after subdivision; all edges in
$G_{1}$ have unit weight, all edges in $G_{2}$ have weight $0.5$ (as in Figure
3). Highlighted in red, green and blue are circuits whose representatives
generate $\prescript{g}{}{\mathcal{H}}_{1}(G_{i})$.

######  Example 3.18.

In Figure 4, we consider again the bifurcating network example of Figure 3, in
which all edges have weight $1$. We see the barcodes of the grounded
persistent homology are both

$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{1})}=\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{2})}=\left\\{\\!\\!\left\\{[0,1),[0,1),[0,2)\right\\}\\!\\!\right\\}.$
(3.12)

In $G_{1}$ the two $[0,1)$ features correspond to the smaller $4$-node
circuits in the centre of the network, coloured in blue. These circuits birth
homological cycles in $G\cup G^{t}$ at $t=0$, which are then killed by long
squares when the edges appear in $G^{t}$ at $t=1$.

The $[0,2)$ feature corresponds to the large inner circuit (coloured in
green). Again this circuit births a homological cycle at $t=0$ which then
becomes null-homologous at $t=2$ when shortcut edges give rise to a new long
square.

The outer red cycle is a linear combination of the inner green and blue
cycles, hence it does not give rise to a fourth feature in the barcode.
Moreover, at $t=1$ the red and green cycles becomes homologous.

In $G_{2}$ the features correspond to the same circuits (once subdivided).

##  4 Interpretation of GrPPH

###  4.1 Decreasing Betti curves

In the first example we saw (Example 3.18) we saw that all features were born
at $t=0$. Indeed, this is always the case and $\prescript{g}{}{H}_{1}(G,0)$ is
in fact the real cycle space of $\mathcal{U}(G)$.

######  Lemma 4.1.

Given a digraph $G=(V,E,w)$, two distinct nodes $a,b\in V$ and a trail
$p:a\leadsto b$, then for all $t\geq\operatorname*{len}(p)$

$\mathfrak{R}({p})=\sum_{\tau\in
E(p)}\tau=ab\pmod{\prescript{g}{}{B}_{1}(G,t)}.$ (4.1)

###### Proof.

Fix arbitrary $t\geq\operatorname*{len}(p)$ and denote the vertices of the
path as $a=v_{0},\dots,v_{m}=b$. Whenever $i<j$ we can truncate $p$ to obtain
a path $v_{i}\leadsto v_{j}$ of length at most $t$ and so $(v_{i},v_{j})\in
E(G^{t})$. Hence, whenever $i<j<k$, there is a directed triangle
$v_{i}v_{j}v_{k}\in C_{2}(G^{t})$ and hence
$v_{i}v_{k}=v_{i}v_{j}+v_{j}v_{k}\pmod{\prescript{g}{}{B}_{1}(G,t)}$.
Therefore, inductively we can write

$ab=v_{0}v_{m}=v_{0}v_{1}+v_{1}v_{m}=v_{0}v_{1}+v_{1}v_{2}+v_{2}v_{m}=\dots=\sum_{i=1}^{m}v_{i-1}v_{i}\pmod{\prescript{g}{}{B}_{1}(G,t)}$
(4.2)

as required. ∎

######  Proposition 4.2.

Fix a weighted digraph $(G,w)$ and $t\geq 0$. For any cycle
$v\in\prescript{g}{}{Z}_{1}(G,t)$, there is an initial cycle
$v^{\prime}\in\prescript{g}{}{Z}_{1}(G,0)$, supported on the edge in $G$, such
that $v$ is homologous to ${\prescript{g}{}{\iota(0,t)}}_{\\#}v^{\prime}$.

###### Proof.

Given any edge $\tau=(a,b)\in E(G^{t})$, there is a path $p:a\leadsto b$ in
$G$ of length at most $t$. Denoting the edges of $p$ by
$(\tau_{1},\dots,\tau_{m})$, Lemma 4.1 tells us,
$\tau=\sum_{i=1}^{m}\tau_{i}\pmod{\prescript{g}{}{B}_{1}(G,t)}$. Now, since
$\tau_{i}\in E(G)$, we see
${\prescript{g}{}{\iota(0,t)}}_{\\#}\tau_{i}=\tau_{i}$ for each edge in $p$. ∎

######  Corollary 4.3.

Given $G\in\bm{\mathrm{WDgr}}$,

  1. (a)

any interval in $\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}$ has birth
time $0$;

  2. (b)

$\prescript{g}{}{H}_{1}(G,0)$ has a basis of simple undirected circuits; and

  3. (c)

$\\#\operatorname{Dgm}(\prescript{g}{}{\mathcal{H}}_{1}(G))$ coincides with
the circuit rank of the underlying undirected graph.

###### Proof.

The first point follows immediately from Lemma 4.2. To see the final two
points, consider the chain complex, $\prescript{g}{}{C}_{\bullet}(G,0)$ at the
start of the filtration. Since $G^{0}$ has no edges, the chain complex is
simply

${\cdots 0}$${0}$${C_{1}(G)}$${C_{0}(G)\cdots}$

Since $G$ is an orientation of $\mathcal{U}(G)$, the first homology of this
chain complex is precisely the real cycle space of $\mathcal{U}(G)$. Fix an
arbitrary spanning forest $T$ of $\mathcal{U}(G)$, and label the remaining
edges $e_{1},\dots,e_{k}$. Note $k$ is the circuit rank of $\mathcal{U}(G)$.
Let $p_{i}$ denote the simple undirected circuit in $G$ which traverses
$e_{i}$ and then returns to $\operatorname*{st}(e_{i})$ through the unique
path in $T$. Then $\\{\mathfrak{R}({p_{1}}),\dots,\mathfrak{R}({p_{k}})\\}$ is
a basis for $\prescript{g}{}{H}_{1}(G,0)$. ∎

###  4.2 Circuit lifetimes

While all features in the barcode (and hence all cycles) are born at time
$t=0$, their death times generally differ. We can assign a death-time to any
cycle $v\in\prescript{g}{}{Z}_{1}(G,0)$, as the first time $v$ becomes null-
homologous.

######  Definition 4.4.

Given $v\in\prescript{g}{}{Z}_{1}(G,0)$, the  death-time of $v$ is

${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\operatorname*{\mathcal{D}}(v)}:=\inf\left\\{t\geq
0\mathrel{}\middle|\mathrel{}{\prescript{g}{}{\iota(0,t)}}_{\ast}[v]=0\right\\}$
(4.3)

where we let $\operatorname*{\mathcal{D}}(v):=\infty$ if there is no such $t$.
The  lifetime of $v$ is the interval
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\operatorname*{\mathcal{L}}(v)}:=[0,\operatorname*{\mathcal{D}}(v))$.

######  Remark 4.5.

Let $p$ be an undirected circuit in $G$ and $p^{\prime}$ the same circuit,
traversed in the opposite direction so that
$\mathfrak{R}({p^{\prime}})=-\mathfrak{R}({p})$. Since
${\prescript{g}{}{\iota(0,t)}}_{\ast}$ is linear,
$\operatorname*{\mathcal{D}}(\mathfrak{R}({p}))=\operatorname*{\mathcal{D}}(\mathfrak{R}({p^{\prime}}))$.
Also, since $\mathfrak{R}({p})$ does not depend on the starting vertex of $p$,
neither does $\operatorname*{\mathcal{D}}(\mathfrak{R}({p}))$.

This pipeline gives us a method for associating a lifetime to an undirected
circuit in $G$ which is ‘geometric’ in the sense that it does not depend on
the starting vertex or direction. The length of this lifetime gives us a
‘size’ to the circuit from the perspective of the filtration. Since we use the
shortest-path filtration, we interpret this size as the time it takes for the
flow to ‘fill in’ the circuit.

######  Lemma 4.6.

Given $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and two directed paths
$p_{1},p_{2}:a\leadsto b$ between distinct vertices $a,b\in V$, let $p_{c}$
denote the undirected circuit which traverses $p_{1}$ forwards and then
$p_{2}$ in reverse. For $i=1,2$, define

$h_{i}:=\min\left\\{t\geq 0\mathrel{}\middle|\mathrel{}\exists v_{i}\in
V\text{ along }p_{i}\text{ such that }d(a,v_{i})\leq t\text{ and
}d(v_{i},b)\leq t\right\\}.$ (4.4)

Then $\operatorname*{\mathcal{D}}(p_{c})\leq\max(h_{1},h_{2})$.

###### Proof.

Denote $T:=\max(h_{1},h_{2})$. First assume that there are at least 2 edges in
each $p_{i}$. Then, by the definition of $h_{i}$, there exists $v_{i}\in
V\setminus\left\\{a,b\right\\}$ along each $p_{i}$ such that $d(a,v_{i})\leq
T$ and $d(v_{i},b)\leq T$. Hence there is a long square
$av_{1}b-av_{2}b\in\prescript{g}{}{C}_{2}(G,T)$. By Lemma 4.1,

$0=\prescript{g}{}{\partial}_{2}(av_{1}b-av_{2}b)=\mathfrak{R}({p_{c}})\pmod{\prescript{g}{}{B}_{1}(G,T)}.$
(4.5)

Finally, if $p_{1}$ contains one edge then $h_{1}=\operatorname*{len}(p_{1})$
so $d(a,b)\leq h_{1}\leq T$. The definition of $h_{2}$ ensures there is
$v_{2}\in V$ along $p_{2}$ such that $d(a,v_{2}),d(v_{2},b)\leq T$. Hence
there is a directed triangle $av_{2}b\in\prescript{g}{}{C}_{2}(G,T)$. By Lemma
4.1,

$0=\prescript{g}{}{\partial}_{2}(av_{2}b)=\mathfrak{R}({p_{c}})\pmod{\prescript{g}{}{B}_{1}(G,T)}$
(4.6)

which concludes the proof. ∎

$a$$b$$c$$d$$e$$f$$10$$10$$10$$10$$1$$1$$1$$1$$1$$1$ Figure 5: A simple
example of a weighted digraph for which the bound of Lemma 4.6 fails to be
sharp.

######  Example 4.7.

Note that the bound of Lemma 4.6 is by no means sharp. Consider for example
Figure 5. Let $p_{1}$ be the outer red path $(a,b,d)$, $p_{2}$ the lower red
path $(a,c,d)$ and $p_{c}$ the undirected circuit which traverse $p_{1}$
forward then $p_{2}$ in reverse. Then $h_{1}=h_{2}=10$ but
$\operatorname*{\mathcal{D}}(\mathfrak{R}({p_{c}}))=2$.

To see this is the correct death time, first note that
$\prescript{g}{}{H}_{1}(G,t)$ can only change at integer values. At $t=1$, the
only edges present in $G^{t}$ are the black ones drawn in in Figure 5. Hence,
$C_{2}(G,1)$ is generated by the long square $ebf-ecf$, whose boundary is not
$\mathfrak{R}({p_{c}})$.

However, at $t=2$ the edges $(a,b),(b,d),(a,c)$ and $(c,d)$ also appear in
$G^{t}$. These generate additional long squares and directed triangles. In
particular $abd-acd\in C_{2}(G,2)$ and

$\prescript{g}{}{\partial}_{2}(abd-acd)=\mathfrak{R}({p_{c}}).$ (4.7)

###  4.3 Representatives

After computing persistent homology, it is common to compute cycles with
represent the features of the barcode. In general, representatives are not
unique and may be quite complicated. In practice, one can often compute
representatives with integer (and even unit) coefficients [26]. These
representatives are frequently used for interpreting features (e.g. [2, 35]).

######  Definition 4.8.

A  persistence basis for $\prescript{g}{}{\mathcal{H}}_{1}(G)$ is a choice of
initial cycles $B=\left\\{b_{i}\in\prescript{g}{}{Z}_{1}(G,0)\right\\}$ such
that for each $t\geq 0$, the set
$\left\\{{\prescript{g}{}{\iota(0,t)}}_{\ast}[b_{i}]\right\\}\setminus\left\\{0\right\\}$
yields a basis for $\prescript{g}{}{H}_{1}(G,t)$. We call elements of a
persistence basis  representatives.

######  Lemma 4.9.

Given any $G\in\bm{\mathrm{WDgr}}$, a persistence basis for
$\prescript{g}{}{\mathcal{H}}_{1}(G)$ always exists.

###### Proof.

This follows from the structure theorem (Theorem 2.32) and Corollary 4.3. ∎

Obtaining a persistence basis $B\subseteq\prescript{g}{}{Z}_{1}(G,0)$ is
desirable because the constituent cycles _represent_ the features of the
barcode, in the following sense. If the barcode is
$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}=\left\\{\\!\\!\left\\{I_{1},\dots,I_{m}\right\\}\\!\\!\right\\}$
then there is an ordering on the cycles $B=\left\\{b_{1},\dots,b_{m}\right\\}$
such that $\operatorname*{\mathcal{L}}(b_{i})=I_{i}$ and

$\bigoplus_{i=1}^{m}P(I_{i})\cong\prescript{g}{}{\mathcal{H}}_{1}(G).$ (4.8)

Moreover, the isomorphism
$\phi:\oplus_{i=1}^{m}P(I_{i})\to\prescript{g}{}{\mathcal{H}}_{1}(G)$ is given
by mapping

$1\in I_{i}(t)\mapsto{\prescript{g}{}{\iota(0,t)}}_{\ast}[b_{i}]\text{
whenever }t\in I_{i}.$ (4.9)

This mapping gives an isomorphism because
$\\{{\prescript{g}{}{\iota(0,t)}}_{\ast}[b_{i}]\\}\setminus\\{0\\}$ is always
a basis for $\prescript{g}{}{H}_{1}(G,t)$. In this sense, the representatives
in $B$ generate $\prescript{g}{}{\mathcal{H}}_{1}(G)$.

Representatives live in $\prescript{g}{}{Z}_{1}(G,0)$ so they are just
$\mathbb{R}$-linear combinations of edges in $G$. However, a priori, the
coefficients of these linear combinations may be arbitrarily complicated. The
goal of this section is to show that grounded persistent homology always
admits a _geometrically interpretable_ persistence basis, in the following
sense.

######  Theorem 4.10.

Given $G\in\bm{\mathrm{WDgr}}$ with circuit rank $m$ there exist undirected
circuits $p_{1},\dots,p_{m}$ in $G$, such that
$\\{\mathfrak{R}({p_{1}}),\dots,\mathfrak{R}({p_{m}})\\}$ is a persistence
basis for $\prescript{g}{}{\mathcal{H}}_{1}(G)$.

$a$$b$$c$$d$$1$$1$$2$$2$$1$$a$$b$$c$$d$$1$$1$$1$$1$$2$$G_{1}$$G_{2}$ Figure 6:
Two weighted digraphs with the same underlying digraph but different
persistence bases, illustrating that not every circuit basis of
$\prescript{g}{}{H}_{1}(G,0)$ yields a persistence basis for
$\prescript{g}{}{\mathcal{H}}_{1}(G)$.

######  Example 4.11.

First, we note that it does not suffice to chose _any_ basis of undirected
circuits for $\prescript{g}{}{Z}_{1}(G,0)$. For example, consider the two
weighted digraphs pictured in Figure 6. In both digraphs, ignoring choice of
direction, there are three undirected simple circuits, whose representatives
we denote

$\displaystyle\gamma_{1}^{i}$ $\displaystyle:=ab+bc-ac,$ (4.10)
$\displaystyle\gamma_{2}^{i}$ $\displaystyle:=bc+cd-bd,$ (4.11)
$\displaystyle\gamma_{3}^{i}$ $\displaystyle:=ab+bd-cd-ac.$ (4.12)

where $\gamma_{j}^{i}\in\prescript{g}{}{Z}_{1}(G_{i},0)$. Note
$\gamma_{3}^{i}=\gamma_{1}^{i}-\gamma_{2}^{i}$. The GrPPH of these two
weighted digraphs is

$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{1})}=\left\\{\\!\\!\left\\{[0,2),[0,1)\right\\}\\!\\!\right\\}\quad\text{and}\quad\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{2})}=\left\\{\\!\\!\left\\{[0,2),[0,1)\right\\}\\!\\!\right\\}.$
(4.13)

A persistence basis for $\prescript{g}{}{\mathcal{H}}_{1}(G_{1})$ is
$\\{\gamma_{1}^{1},\gamma_{2}^{1}\\}$ with
$\operatorname*{\mathcal{L}}(\gamma_{1}^{1})=[0,1)$ and
$\operatorname*{\mathcal{L}}(\gamma_{2}^{1})=[0,2)$. Note that
$\\{\gamma_{2}^{1},\gamma_{3}^{1}\\}$ is _not_ a persistence basis for
$\prescript{g}{}{\mathcal{H}}_{1}(G_{1})$ because
$\operatorname*{\mathcal{L}}(\gamma_{3}^{1})=[0,2)$.

However
$\operatorname*{\mathcal{L}}(\gamma_{1}^{2})=\operatorname*{\mathcal{L}}(\gamma_{2}^{2})=[0,2)$,
hence $\\{\gamma_{1}^{2},\gamma_{2}^{2}\\}$ does _not_ form a persistence
basis for $\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$. At $t=2$, we see
${\prescript{g}{}{\iota(0,2)}}_{\ast}\gamma_{3}^{2}=0$ and hence
${\prescript{g}{}{\iota(0,2)}}_{\ast}\gamma_{1}^{2}={\prescript{g}{}{\iota(0,2)}}_{\ast}\gamma_{2}^{2}$.
Instead, a persistence basis for $\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$ is
$\\{\gamma_{2}^{2},\gamma_{3}^{2}\\}$.

This illustrates that an arbitrary choice of undirected circuit basis for
$\prescript{g}{}{H}_{1}(G,0)$ may not yield a persistence basis of
$\prescript{g}{}{\mathcal{H}}_{1}(G)$. Moreover, a correct choice of basis
does not depend only on $\mathcal{U}(G)$; we must incorporate information
about how cycles in $\prescript{g}{}{Z}_{1}(G,0)$ die, in order to choose a
persistence basis.

To begin tackling Theorem 4.10, since $G$ is finite, we note there are
finitely critical values $t_{1}=0,\dots,t_{m}$ where the chain complex
$\prescript{g}{}{C}_{\bullet}(G,t)$ changes. Therefore, it suffices to study
the following finite persistent chain complex instead.

${\cdots C_{2}(G^{t_{1}})}$${C_{1}(G\cup G^{t_{1}})}$${C_{0}(G\cup
G^{t_{1}})\cdots}$${\prescript{g}{}{H}_{1}(G,t_{1})}$${\cdots
C_{2}(G^{t_{2}})}$${C_{1}(G\cup G^{t_{2}})}$${C_{0}(G\cup
G^{t_{2}})\cdots}$${\prescript{g}{}{H}_{1}(G,t_{2})}$${\vdots}$${\vdots}$${\vdots}$${\vdots}$${\cdots
C_{2}(G^{t_{m}})}$${C_{1}(G\cup G^{t_{m}})}$${C_{0}(G\cup
G^{t_{m}})\cdots}$${\prescript{g}{}{H}_{1}(G,t_{m})}$$\scriptstyle{{\prescript{g}{}{\iota(t_{1},t_{2})}}_{\ast}}$$\scriptstyle{{\prescript{g}{}{\iota(t_{2},t_{3})}}_{\ast}}$$\scriptstyle{{\prescript{g}{}{\iota(t_{m-1},t_{m})}}_{\ast}}$

To the right of the chain complex we show the induced maps on homology
${\prescript{g}{}{\iota(t_{i-1},t_{i})}}_{\ast}$. By Lemma 4.2, these maps on
homology are always surjective. Our strategy is to find undirected circuit
bases for the kernel of each of these maps; Lemma 4.12 achieves this and is
the key result. We then collect these elements into a basis for
$\ker{\prescript{g}{}{\iota(0,t_{m})}}_{\ast}$. Together, these elements form
representatives for the homology classes with finite lifetime. To obtain
representatives for the infinite feature, we extend this to a basis for all of
$\prescript{g}{}{H}_{1}(G,0)$ and show that we obtain a persistence basis.

######  Lemma 4.12.

For each $i=2,\dots,m$, there is a basis $\\{b_{1},\dots,b_{k_{i}}\\}$ of
$\ker{\prescript{g}{}{\iota(t_{i-1},t_{i})}}_{\ast}$ such that
$b_{j}={\prescript{g}{}{\iota(0,t_{i-1})}}_{\ast}[\mathfrak{R}({p_{i,j}})]$
for some undirected circuit $p_{i,j}$ in $G$.

###### Proof.

For notational convenience, we define $r:=t_{i-1}$ and $s:=t_{i}$. When the
filtration increases from $t=r$ to $t=s$, some number of edges are added to
$G^{t}$ which yield new generators for both $C_{1}(G\cup G^{t})$ and
$C_{2}(G^{t})$. Our approach is to decompose
${\prescript{g}{}{\iota(r,s)}}_{\\#}$ into a sequence of chain maps. In the
first, all the new generators of $C_{1}(G\cup C^{s})$ are added, along with
sufficient new generators in $C_{2}(G^{s})$ to make the new edges homologous
to a sum of edges already present in $C_{1}(G\cup G^{r})$. Therefore, on
homology this first map is an isomorphism. We then add the remaining
generators of $C_{2}(G^{s})$ one at a time in order to find a basis for
$\ker{\prescript{g}{}{\iota(r,s)}}_{\ast}$. Since we are only interested in
degree $1$ homology, it suffices to restrict our attention to degrees $0,1$
and $2$.

Denote the set of new edges $E_{new}:=E(G\cup G^{s})\setminus E(G\cup G^{r})$.
Given an edge $e=(a,b)\in E_{new}$, there is some directed path $p:a\leadsto
b$ in $G$, of length at most $s$. Moreover this path must have at least one
vertex distinct from the endpoints of $e$, otherwise $e\in G$. Choose
arbitrary such $v_{e}\in V(p)$. Then $(a,v_{e},b)$ is a directed triangle in
$G^{s}$ so $w_{e}:=av_{e}b$ is a new generator of $C_{2}(G^{s})$. Repeating
this for all new edges we obtain a set of generators

$U_{new}:=\left\\{w_{e}\mathrel{}\middle|\mathrel{}e\in E_{new}\right\\}$
(4.14)

which were not present in $C_{2}(G^{r})$ and are linearly independent. Define
$W_{0}:=\left\langle U_{new}\right\rangle$ and let $Q_{0}$ denote the degree 1
homology of the chain complex

${C_{2}(G^{r})\oplus W_{0}}$${C_{1}(G\cup G^{s})}$${C_{0}(G\cup
G^{s})}$$\scriptstyle{\prescript{g}{}{\partial}_{2}}$$\scriptstyle{\prescript{g}{}{\partial}_{1}}$

which is a subcomplex of $\prescript{g}{}{C}_{\bullet}(G,s)$.

######  Claim 4.12.1.

The inclusion chain map

${C_{2}(G^{r})}$${C_{1}(G\cup G^{r})}$${C_{0}(G\cup
G^{r})}$${\prescript{g}{}{H}_{1}(G,{r})}$${C_{2}(G^{r})\oplus
W_{0}}$${C_{1}(G\cup G^{s})}$${C_{0}(G\cup
G^{s})}$${Q_{0}}$$\scriptstyle{q^{0}_{2}}$$\scriptstyle{q^{0}_{1}}$$\scriptstyle{q^{0}_{0}}$$\scriptstyle{q^{0}}$$\scriptstyle{\cong}$

induces an isomorphism on degree $1$ homology,
$q^{0}:\prescript{g}{}{H}_{1}(G,r)\to Q_{0}$.

###### Proof of Claim.

We define a chain map ${c}_{\\#}$ in the opposite direction and a homotopy
$P:C_{1}(G\cup G^{s})\to C_{2}(G^{r})\oplus W_{0}$ such that $c_{1}\circ
q^{0}_{1}=\mathrm{id}$ while $q^{0}_{1}\circ
c_{1}-\mathrm{id}=\prescript{g}{}{\partial}_{2}\circ P$. Hence, on degree 1
homology, ${c}_{\\#}$ induces an inverse to $q^{0}$. The chain map in degrees
$k\neq 1$ is given by

$c_{k}(v):=\begin{cases}v&\text{if }v\in\prescript{g}{}{C}_{k}(G,r),\\\
0&\text{otherwise},\end{cases}$ (4.15)

and $c_{1}$ is defined on the basis of $C_{1}(G\cup G^{s})$ by

$c_{1}(ab):=\begin{cases}av_{(a,b)}+v_{(a,b)}b&\text{if }(a,b)\in E_{new},\\\
ab&\text{otherwise}.\end{cases}$ (4.16)

The homotopy is given on the basis of $C_{1}(G\cup G^{s})$ by

$P(ab):=\begin{cases}w_{(a,b)}&\text{if }(a,b)\in E_{new},\\\
0&\text{otherwise}.\end{cases}$ (4.17)

where $w_{(a,b)}\in U_{new}$. A standard check of the two cases verifies that
${c}_{\\#}$ is a chain map and the relations $c_{1}\circ
q_{1}^{0}=\mathrm{id}$ and $q_{1}^{0}\circ
c_{1}-\mathrm{id}=\prescript{g}{}{\partial}_{2}\circ P$ hold.

Intuitively, ${c}_{\\#}$ collapses a new edge $e=(a,b)\in E_{new}$ onto the
sum of edges $av_{e}+v_{e}b$ in $G\cup G^{r}$. The homotopy $P$ shows the two
elements are homologous thanks to the presence of the directed triangle
$w_{e}\in U_{new}$. ∎

By Proposition 2.30, there exists $u_{1},\dots,u_{n}\in C_{2}(G^{s})$ such
that

$C_{2}(G^{s})=C_{2}(G^{r})\oplus W_{0}\oplus\left\langle
u_{1},\dots,u_{n}\right\rangle$ (4.18)

where each $u_{i}$ is amongst the generators identified in Proposition 2.30.
Define $W_{i}:=W_{0}\oplus\left\langle u_{1},\dots,u_{i}\right\rangle$. This
gives a sequence of inclusion chain maps

${C_{2}(G^{r})\oplus W_{i-1}}$${C_{1}(G\cup G^{s})}$${C_{0}(G\cup
G^{s})}$${Q_{i-1}}$${C_{2}(G^{r})\oplus W_{i}}$${C_{1}(G\cup
G^{s})}$${C_{0}(G\cup
G^{s})}$${Q_{i}}$$\scriptstyle{q^{i}_{2}}$$\scriptstyle{q^{i}_{1}}$$\scriptstyle{q^{i}_{0}}$$\scriptstyle{q^{i}}$

where each rows is a subcomplex of $\prescript{g}{}{C}_{\bullet}(G,s)$. We
denote the degree $1$ homology groups by $Q_{i}$, with
$Q_{n}:=\prescript{g}{}{H}_{1}(G,S)$, and the induced homology maps by
$q^{i}:Q_{i-1}\to Q_{i}$. Together these chain maps decompose
${\prescript{g}{}{\iota(r,s)}}_{\\#}$ and hence the $q^{i}$ decompose
${\prescript{g}{}{\iota(r,s)}}_{\ast}$, as show in the following diagram.

${C_{2}(G^{r})}$${C_{1}(G\cup G^{r})}$${C_{0}(G\cup
G^{r})}$${\prescript{g}{}{H}_{1}(G,{r})}$${C_{2}(G^{r})\oplus
W_{0}}$${C_{1}(G\cup G^{s})}$${C_{0}(G\cup
G^{s})}$${Q_{0}}$${C_{2}(G^{r})\oplus W_{1}}$${C_{1}(G\cup
G^{s})}$${C_{0}(G\cup
G^{s})}$${Q_{1}}$${\vdots}$${\vdots}$${\vdots}$${\vdots}$${C_{2}(G^{n})\oplus
W_{n-1}}$${C_{1}(G\cup G^{s})}$${C_{0}(G\cup
G^{s})}$${Q_{n-1}}$${C_{2}(G^{s})}$${C_{1}(G\cup G^{s})}$${C_{0}(G\cup
G^{s})}$${\prescript{g}{}{H}_{1}(G,{s})}$$\scriptstyle{{\prescript{g}{}{\iota(r,s)}}_{\ast}}$$\scriptstyle{q^{0}}$$\scriptstyle{\cong}$$\scriptstyle{q^{1}}$$\scriptstyle{q^{n}\circ\dots\circ
q^{1}}$$\scriptstyle{q^{2}}$$\scriptstyle{q^{n-1}}$$\scriptstyle{q^{n}}$

Note that $\dim Q_{i}$ drops by at most $1$ at each step, since $\dim
W_{i+1}=\dim W_{i}+1$. Let $J$ denote the subset of indices where the
dimension drops, i.e.

$J:=\left\\{i\in\mathbb{N}\mathrel{}\middle|\mathrel{}\dim Q_{i}=\dim
Q_{i-1}-1\right\\}.$ (4.19)

Then for each $i\in J$, the map on homology $q^{i}$ has nullity $1$ and a
basis for $\ker q^{i}$ is $\\{[b_{i}]\\}$ where
$b_{i}:=\prescript{g}{}{\partial}_{2}u_{i}\in C_{1}(G\cup G^{s})$.

Note that $[b_{i}]\in Q_{0}$ and $(q^{i-1}\circ\dots\circ
q^{1})[b_{i}]=[b_{i}]$ in $Q_{i-1}$. Since each $[b_{i}]$ for $i\in J$ dies in
a different $Q_{i}$, they must be linearly independent in $Q_{0}$. Moreover,
the nullity of $q^{n}\circ\dots\circ q^{1}$ is $\\#J$ so
$\left\\{[b_{i}]\mathrel{}\middle|\mathrel{}i\in J\right\\}$ gives a basis for
$\ker(q^{n}\circ\dots\circ q^{1})$. Hence
$\left\\{(q^{0})^{-1}[b_{i}]\mathrel{}\middle|\mathrel{}i\in J\right\\}$ forms
a basis for $\ker{\prescript{g}{}{\iota(r,s)}}_{\ast}$. It now remains to
prove that each $(q^{0})^{-1}[b_{i}]$ has a undirected circuit representative.

######  Claim 4.12.2.

For each $i\in J$, there exists an undirected circuit $p_{i}$ in $G$ such that
${\prescript{g}{}{\iota(0,r)}}_{\ast}[\mathfrak{R}({p_{i}})]=(q^{0})^{-1}[b_{i}]$.

###### Proof of Claim.

First we recall that $b_{i}=\prescript{g}{}{\partial}_{2}u_{i}$ where $u_{i}$
is either a double edge, a directed triangle or a long square in $G^{s}$. Some
of the boundary edges may be edges in $G^{r}$ but at least one boundary edge
is new in $G^{s}$. By the previous claim, a representative for
$(q^{0})^{-1}[b_{i}]$ is $c_{1}(b_{i})$.

We can write $b_{i}=\mathfrak{R}({p})$ where $p$ is the undirected circuit
which traces the outline of the generator $u_{i}$. Now $c_{1}$ maps edges in
$G^{r}$ to themselves and edges not in $G^{r}$ to a sum of two edges in
$G^{r}$ with the same boundary. Therefore, no matter which type of generator
$u_{i}$ is, we can write $c_{1}(b_{i})=\mathfrak{R}({\widetilde{p}})$ for some
undirected circuit $\widetilde{p}$ through $G^{r}$. Using Lemma 4.1, for each
edge $\tau\in E(\widetilde{p})$ in this circuit there is a directed path
$T_{\tau}$ through $G$ of length at most $r$ such that
$\tau=\mathfrak{R}({T_{\tau}})\pmod{\prescript{g}{}{B}_{1}(G,r)}$.
Concatenating the $T_{\tau}$ we obtain an undirected circuit $p_{i}$ through
$G$ such that
$\mathfrak{R}({p})=\mathfrak{R}({p_{i}})\pmod{\prescript{g}{}{B}_{1}(G,r)}$. ∎

This claim concludes the proof. ∎

######  Remark 4.13.

Note that the undirected circuits $p_{i,j}$ may not be simple. We conjecture
that it should be possible to choose every $p_{i,j}$ to be simple but do not,
as yet, have a proof.

$a$$b$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$1$$1$$2$$2$$2$$2$$1$$1$$a$$b$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$G$$G^{3}$
Figure 7:  An example weighted digraph with a single feature which dies at
$t=3$. To the right we show $G^{3}$, colouring the new edges in $G^{3}$ in
blue and highlighting the new generators in $C_{2}(G^{3})$ via blue and green
polygons.

######  Example 4.14.

To illustrate how the generators are added in the proof of Lemma 4.12,
consider Figure 7. First note that there is a single feature with
representative

$\gamma:=(av_{1}+v_{1}v_{2}+v_{2}v_{3}+v_{3}b)-(av_{4}+v_{4}v_{5}+v_{5}v_{6}+v_{6}b)$
(4.20)

which dies at $t=3$. Further note that new edges appear at integer values in
the shortest-path filtration and
$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}=\left\\{\\!\\!\left\\{[0,3)\right\\}\\!\\!\right\\}$.

The new edges which appear at $t=3$ are highlighted in blue. The new
generators of $C_{2}(G^{3})$ are the four blue directed triangles and the
central green long square. The blue directed triangles form the elements of
$U_{new}$ and the central long square is the sole remaining generator $u_{1}$.
So a basis for $\ker q^{1}$ is $\\{[\prescript{g}{}{\partial}_{2}u_{1}]\\}$.

To find a basis for $\ker{\prescript{g}{}{\iota(2,3)}}_{\ast}$ we must compute
$c_{1}(\prescript{g}{}{\partial}_{2}u_{1})$. Firstly
$\prescript{g}{}{\partial}_{2}u_{1}=av_{2}+v_{2}b-v_{5}b-av_{5}$. Then the
chain map $c_{1}$ maps each of the blue edges to a sum of edges in $G^{2}$. In
fact $c_{1}(\prescript{g}{}{\partial}_{2}u_{1})=\gamma$ which is the
representative of the sole simple undirected circuit in $G$.

The following Lemma follows by a standard linear algebra argument, since each
${\prescript{g}{}{\iota(t_{i-1},t_{i})}}_{\ast}$ is surjective.

######  Lemma 4.15.

Given $B_{i}\subseteq\prescript{g}{}{H}_{1}(G,0)$ such that
${\prescript{g}{}{\iota(0,t_{i})}}_{\ast}(B_{i})$ is a basis for
$\ker{\prescript{g}{}{\iota(t_{i},t_{i+1})}}_{\ast}$, the union
$\cup_{i=1}^{m-1}B_{i}$ is a basis for
$\ker{\prescript{g}{}{\iota(0,t_{m})}}_{\ast}$.

Certainly a basis of undirected circuits for $\prescript{g}{}{H}_{1}(G,0)$
exists (by Corollary 4.3). Therefore, we can always extend linearly
independent undirected circuits to a basis of such circuits for
$\prescript{g}{}{H}_{1}(G,0)$.

######  Lemma 4.16.

Given undirected circuits $p_{1},\dots,p_{k}$ such that
$[\mathfrak{R}({p_{1}})],\dots,[\mathfrak{R}({p_{k}})]$ are linearly
independent in $\prescript{g}{}{H}_{1}(G,0)$, there exists undirected circuits
$p_{k+1},\dots,p_{N}$ such that $\\{[\mathfrak{R}({p_{i}})]\\}_{i=1}^{N}$ is a
basis for $\prescript{g}{}{H}_{1}(G,0)$.

We now have all the ingredients we need to prove the main theorem.

###### Proof of Theorem 4.10.

Using Lemma 4.12 and Lemma 4.15, we obtain undirected circuits
$p_{1},\dots,p_{l}$ such that
$\left\\{\mathfrak{R}({p_{1}}),\dots,\mathfrak{R}({p_{l}})\right\\}$ forms a
basis for $\ker{\prescript{g}{}{\iota(0,t_{m})}}_{\ast}$. Using Lemma 4.16, we
extend this to a basis
$\left\\{\mathfrak{R}({p_{1}}),\dots,\mathfrak{R}({p_{l}}),\mathfrak{R}({p_{l+1}}),\dots,\mathfrak{R}({p_{N}})\right\\}$
for $\prescript{g}{}{H}_{1}(G,0)$. This is a persistence basis for
$\prescript{g}{}{\mathcal{H}}_{1}(G)$. ∎

######  Remark 4.17.

While we are guaranteed a basis of undirected circuits, this choice of basis
is by no means unique. As a simple example, consider again Example 4.11 and
Figure 6. Two possible persistence bases for
$\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$ are
$\left\\{\gamma^{2}_{1},\gamma^{2}_{3}\right\\}$ and
$\left\\{\gamma^{2}_{2},\gamma^{2}_{3}\right\\}$. The non-uniqueness of the
basis arises in the proof of Lemma 4.12. Namely, there is a choice of $v_{e}$
and $w_{e}$ for each $e\in E_{new}$, and a choice of order on the remaining
$u_{i}$.

###  4.4 Decomposition

$\hat{v}$$G_{1}\sqcup G_{2}$$G_{1}\vee_{\hat{v}}G_{2}$ Figure 8:
Illustrations of the disjoint union and wedge decomposition considered in
Section 4.4.

In order to more easily compute GrPPH, it is desirable to understand how
decompositions of the input weighted digraphs give rise to decompositions of
the descriptor. The simplest such decomposition is a disjoint union; as one
might expect, the descriptor decomposes as a direct sum.

######  Theorem 4.18.

Suppose $G\in\bm{\mathrm{WDgr}}$ decomposes as a disjoint union,
$G=G_{1}\sqcup G_{2}$, then

$\prescript{g}{}{\mathcal{H}}_{1}(G)\cong\prescript{g}{}{\mathcal{H}}_{1}(G_{1})\oplus\prescript{g}{}{\mathcal{H}}_{1}(G_{2}).$
(4.21)

###### Proof.

Note that for each $t\geq 0$,

$G^{t}=G_{1}^{t}\sqcup G_{2}^{t}\quad\text{ and }\quad G\cup G^{t}=(G_{1}\cup
G_{1}^{t})\sqcup(G_{2}\cup G_{2}^{t}).$ (4.22)

For each degree $k\geq 0$, if $H=H_{1}\sqcup H_{2}$ then
$C_{k}(H)=C_{k}(H_{1})\oplus C_{k}(H_{2})$. Therefore, for each $k\geq 0$,
$\prescript{g}{}{C}_{k}(G,t)$ splits as direct sum
$\prescript{g}{}{C}_{k}(G_{1},t)\oplus\prescript{g}{}{C}_{k}(G_{2},t)$. The
boundary operator respects this split, mapping
$\prescript{g}{}{C}_{k}(G_{i},t)\to\prescript{g}{}{C}_{k-1}(G_{i},t)$ and the
maps ${\prescript{g}{}{\iota(s,t)}}_{\\#}$ also respect this split, mapping
$\prescript{g}{}{C}(G_{i},s)\to\prescript{g}{}{C}(G_{i},t)$. Taking homology
in degree $1$ maintains this direct sum decomposition. ∎

######  Definition 4.19.

  1. (a)

Given a weighted digraph $G=(V,E,w)$, a  wedge vertex is a vertex $\hat{v}\in
V$ such that there is a decomposition

$V=V_{1}\cup V_{2}$ (4.23)

with $V_{1}\cap V_{2}=\\{\hat{v}\\}$ such that $E\subseteq(V_{1}\times
V_{1})\cup(V_{2}\times V_{2})$.

  2. (b)

Given a wedge vertex, $\hat{v}$ as above the corresponding  wedge
decomposition of $G$ is the pair $(G_{1},G_{2})$ where $G_{1}$ and $G_{2}$ are
the induced subgraphs on $V_{1}$ and $V_{2}$ respectively. We write
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color<EMAIL_ADDRESS>
  3. (c)

Given a wedge decomposition as above, a pair of vertices $a,b\in V$ are called
separated if they do not lie in a common $V_{i}$.

######  Remark 4.20.

Given a wedge decomposition $G=G_{1}\vee_{\hat{v}}G_{2}$ note that
$G=G_{1}\cup G_{2}$.

In the case of a wedge decomposition $G=G_{1}\vee_{\hat{v}}G_{2}$, since each
simple circuit is contained either entirely in $G_{1}$ or entirely in $G_{2}$,
one expects that GrPPH also decomposes. The proof is more complicated because,
in general, $G^{t}\neq G_{1}^{t}\vee_{\hat{v}}G_{2}^{t}$, since there may be
paths between separated vertices, through $\hat{v}$. However, using a chain
homotopy, we can show that these edges do not affect the homology.

######  Theorem 4.21.

For a weighted digraph $G=(V,E,w)$ and a wedge decomposition
$G=G_{1}\vee_{\hat{v}}G_{2}$,

$\prescript{g}{}{\mathcal{H}}_{1}(G)\cong\prescript{g}{}{\mathcal{H}}_{1}(G_{1})\oplus\prescript{g}{}{\mathcal{H}}_{1}(G_{2}).$
(4.24)

###### Proof.

There are natural inclusion digraph maps $j_{i}:G_{i}\to G$ which are also
contractions. Less obviously, there are contraction digraph maps $f_{i}:G\to
G_{i}$, where

$f_{i}(v):=\begin{cases}v&\text{if }v\in V_{i},\\\
\hat{v}&\text{otherwise}.\end{cases}$ (4.25)

Since these are all morphisms in $\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}$, we
obtain induced morphisms ${\prescript{g}{}{j_{i}}}_{\\#}$ and
${\prescript{g}{}{f_{i}}}_{\\#}$. We combine these morphisms to get two
morphisms as follows

$\displaystyle
J:\prescript{g}{}{C}(G_{1})\oplus\prescript{g}{}{C}(G_{2})\to\prescript{g}{}{C}(G),\quad$
$\displaystyle
J(\gamma_{1},\gamma_{2}):={\prescript{g}{}{j_{1}}}_{\\#}\gamma_{1}+{\prescript{g}{}{j_{2}}}_{\\#}\gamma_{2};$
(4.26) $\displaystyle
F:\prescript{g}{}{C}(G)\to\prescript{g}{}{C}(G_{1})\oplus\prescript{g}{}{C}(G_{2}),\quad$
$\displaystyle
F(\gamma):=({\prescript{g}{}{f_{1}}}_{\\#}\gamma,{\prescript{g}{}{f_{2}}}_{\\#}\gamma).$
(4.27)

Composing with homology in degree $1$, denote
${J}_{\ast}:=\textbf{[}\bm{\mathrm{R}},\,H_{1}\textbf{]}\circ J$ and
${F}_{\ast}:=\textbf{[}\bm{\mathrm{R}},\,H_{1}\textbf{]}\circ F$. In the rest
of the proof, we show that ${J}_{\ast}$ and ${F}_{\ast}$ are mutually inverse.

######  Claim 4.21.1.

In degree $1$, $F\circ J=\mathrm{id}$ is the identity map on
$\prescript{g}{}{C}(G_{1})\oplus\prescript{g}{}{C}(G_{2})$.

###### Proof of Claim.

First note that, $f_{i}\circ j_{i}$ is the identity digraph map
$\mathrm{id}_{i}:G_{i}\to G_{i}$. However, $f_{3-i}\circ j_{i}$ is the
constant digraph map $c_{i}:G_{i}\to G_{3-i}$ which maps all of $G_{i}$ to the
vertex $\hat{v}$. Hence, in matrix form, we can write $F\circ J$ as

$F\circ
J=\begin{pmatrix}{\prescript{g}{}{\mathrm{id}_{1}}}_{\\#}&{\prescript{g}{}{c_{2}}}_{\\#}\\\
{\prescript{g}{}{c_{1}}}_{\\#}&{\prescript{g}{}{\mathrm{id}_{2}}}_{\\#}\end{pmatrix}.$
(4.28)

Since the constant maps $c_{i}$ send all vertices to a single vertex,
${\prescript{g}{}{c_{i}}}_{\\#}$ maps every edge to $0$. Hence, in degree $1$,
${\prescript{g}{}{c_{i}}}_{\\#}$ is the zero map. Whereas, in degree $1$,
${\prescript{g}{}{\mathrm{id}_{i}}}_{\\#}$ is the identity map on
$\prescript{g}{}{C}_{1}(G_{i},t)$ at each $t$. Therefore, on degree $1$,
$F\circ J$ is the identity map on
$\prescript{g}{}{C}(G_{1})\oplus\prescript{g}{}{C}(G_{2})$. ∎

Composing with homology in degree $1$, we see
${F}_{\ast}\circ{J}_{\ast}=\mathrm{id}$ is the identity map on
$\prescript{g}{}{\mathcal{H}}_{1}(G_{1})\oplus\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$.

######  Claim 4.21.2.

In degree $1$, ${J}_{\ast}\circ{F}_{\ast}=\mathrm{id}$ is the identity map on
$\prescript{g}{}{\mathcal{H}}_{1}(G)$.

###### Proof of Claim.

First, we compute $J\circ F$ in degree $1$. Recall that
$\prescript{g}{}{C}_{1}(G,t)$ is freely generated by the edges in $G\cup
G^{t}$. Given an edge $e=(a,b)\in E(G\cup G^{t})$, if the vertices $a,b$ lie
in a common $V_{i}$ then $(J\circ F)(e)=e$. However, if $a,b$ are separated
then $(J\circ F)(e)=a\hat{v}+\hat{v}b$. So we see, at the level of chains,
$J\circ F$ does not compose to the identity.

If $e=(a,b)\in E(G\cup G^{t})$ but the endpoints are separated then we must
have $e\in E(G^{t})$. Hence, there is a path $p:a\leadsto b$ in $G$ of length
at most $t$. Moreover, this path must traverse the vertex $\hat{v}$. Hence,
$p$ decomposes into two paths $a\leadsto\hat{v}$ and $\hat{v}\leadsto b$, each
of length at most $t$. Therefore, the directed triangle $a\hat{v}b$ is present
in $G^{t}$ and is a generator of $\prescript{g}{}{C}_{2}(G,t)$. Note that the
boundary of $a\hat{v}b$ is

$\partial_{2}(a\hat{v}b)=a\hat{v}+\hat{v}b-(ab)=(J\circ F)(e)-e.$ (4.29)

This discussion show that we can define a map
$P:\prescript{g}{}{C}_{1}(G,t)\to\prescript{g}{}{C}_{2}(G,t)$ by

$P(ab):=\begin{cases}a\hat{v}b&\text{if }a,b\text{ are separated},\\\
0&\text{otherwise}.\end{cases}$ (4.30)

Then, $J\circ F-\mathrm{id}=\partial_{2}P$ as maps on
$\prescript{g}{}{C}_{1}(G)$. Composing with homology, we see
${J}_{\ast}\circ{F}_{\ast}=\mathrm{id}$ is the identity on
$\prescript{g}{}{\mathcal{H}}_{1}(G)$. ∎

Since ${J}_{\ast}$ and ${F}_{\ast}$ are mutually inverse, they induce
isomorphisms of persistent vector spaces. ∎

##  5 Stability analysis of GrPPH

$100$$0$

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$10$$10$$10$$100$$50$$10$$50$$10$

(a)

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$70$$90$$20$$30$$80$$20$$50$$100$

(b)

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$10$$10$$10$$40$$30$$30$$25$$25$$10$$50$$10$

(c)

$v_{e}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$60$$10$$60$$60$$10$$100$

(d)

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$10$$10$$10$$50$$10$$50$$10$

(e)

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$10$$10$$10$$100$$50$

(f)

Figure 9: Illustration of a number of operations for altering a weighted
digraph. (a) The initial weighted digraph $G$. (b) Weight perturbation
$\mathbb{O}^{p}_{w^{\prime}}{G}$. (c) Edge subdivision $\mathbb{O}^{s}_{S}{G}$
where the subdivision is $S:\\{(v_{0},v_{5}),(v_{5},v_{4})\\}\to\Delta^{2}$
where $S((v_{0},v_{5}))=(4/10,3/10,3/10)$ and $S((v_{5},v_{4}))=(1/2,1/2,0)$.
(d) Edge collapse $\mathbb{O}^{c}_{e}{G}$ where $e=(v_{0},v_{5})$. (e) Edge
deletion $\mathbb{O}^{d}_{e}{G}$ where $e=(v_{0},v_{5})$. (f) Vertex deletion
$\mathbb{O}^{d}_{v}{G}$ where $v=v_{4}$.

It is important that GrPPH is stable with respect to a reasonable noise model.
Typically this is shown by proving that $\prescript{g}{}{\mathcal{H}}_{1}$ is
Lipschitz with respect to reasonable metrics on $\bm{\mathrm{WDgr}}$ and the
bottleneck distance on $\bm{\mathrm{PersVec}}$. A common choice of metric on
graphs is the graph edit distance. However, assigning costs to operations such
as edge deletion or edge subdivision is somewhat arbitrary.

Therefore, in this section, we consider operations
$\mathbb{O}^{T}_{\theta}{}:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\bm{\mathrm{WDgr}})$
for editing weighted digraphs, where $T$ is the type of operation $\theta$ is
the parameter of the operation. For each type $T$, we derive bounds of the
form

$d_{B}(\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{T}_{\theta}{G})})\leq
f(G,\theta)$ (5.1)

and then say GrPPH is  stable to operations of type $T$.

Often the operations only alter the graph at a subset of vertices or edges. We
say that GrPPH is  locally stable to the operation if we obtain a bound as in
(5.1) and $f$ depends only on the neighbourhood graph around the altered
vertices/edges and $\theta$. If we can show that no such local $f$ exists (for
general $G$ and $\theta$) then we say GrPPH is  locally unstable. If, in
general, $f$ depends on all of $G$ then we say GrPPH is  non-locally stable to
the operation. Occasionally, some operations do not change the descriptor and
we can find an isomorphism
$\prescript{g}{}{\mathcal{H}}_{1}(G)\cong\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{T}_{\theta}{G})$.

Figure 9 illustrates all of the operations we consider, the precise
definitions of which of which are provided in the relevant subsection. Table 1
summaries our findings.

Operation |  Locally Stable |  Non-locally Stable |  Locally Unstable |  Isomorphism
---|---|---|---|---
Weight perturbation | Theorem 5.6 |  |  |
Edge subdivision | Theorem 5.11 |  |  |
Edge collapse | Theorem 5.17◆ |  | Theorem 5.20 |
Edge deletion | Corollary 5.23◆ | Theorem 5.22 | Theorem 5.25 | Theorem 5.28◆
Vertex deletion |  |  | Corollary 5.31 | Corollary 5.30◆
Table 1:  Stability and instability theorems for
$\prescript{g}{}{\mathcal{H}}_{1}$, under various digraph operations.
$\blacklozenge$ Denotes a theorem which only applies to a subset of such
operations.

###  5.1 Preliminaries

In order to prove stability, we will have to build interleaving chain maps.
Often, these will be constructed via maps of the underlying vertex sets.

######  Definition 5.1.

For $\delta\geq 0$, a  $\delta$-shifting vertex map, between two weighted
digraphs $G$ and $H$, is a vertex map $f:V(G)\to V(H)$ such that $f$ induces
digraph maps $G^{t}\to H^{t+\delta}$ and $G\cup G^{t}\to H\cup H^{t+\delta}$
for all $t\geq 0$.

######  Remark 5.2.

By Lemma 3.14, a $0$-shifting vertex map is precisely a contraction digraph
map.

######  Lemma 5.3.

Any $\delta$-shifting vertex map $f:V(G)\to V(H)$ induces a morphism

${\mathcal{S}(f,\delta)}_{\\#}:\prescript{g}{}{C}(G)\to\prescript{g}{}{C}(H)[\delta].$
(5.2)

Given another $\epsilon$-shifting vertex map $g:V(H)\to V(K)$,

${\mathcal{S}(g\circ
f,\epsilon+\delta)}_{\\#}={\mathcal{S}(g,\epsilon)}_{\\#}\circ{\mathcal{S}(f,\delta)}_{\\#}.$
(5.3)

Moreover, if $f$ is $0$-shifting then
${\mathcal{S}(f,0)}_{\\#}={\prescript{g}{}{f}}_{\\#}$.

###### Proof.

Fix $t\geq 0$. Since $f$ is a $\delta$-shifting vertex map, the functor $C$
induces chain maps ${f}_{\\#}:C_{\bullet}(G^{t})\to C_{\bullet}(H^{t+\delta})$
and ${f}_{\\#}:C_{\bullet}(G\cup G^{t})\to C_{\bullet}(H\cup H^{t+\delta})$.
These chain maps fit together into the following commutative diagram.

${C_{3}(G^{t})}$${C_{2}(G^{t})}$${C_{1}(G\cup G^{t})}$${C_{0}(G\cup
G^{t})}$${C_{1}(G^{t})}$${C_{1}(H^{t+\delta})}$${C_{3}(H^{t+\delta})}$${C_{2}(H^{t+\delta})}$
${C_{1}(H\cup H^{t+\delta})}$${C_{0}(H\cup
H^{t+\delta})}$$\scriptstyle{{f}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{A}}$$\scriptstyle{{f}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{B}}$$\scriptstyle{{f}_{\\#}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{C}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{D}}$$\scriptstyle{{f}_{\\#}}$$\scriptstyle{{f}_{\\#}}$

Squares
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{A}$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{B}$
and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{D}$
commute because they are parts of the same chain map. The inclusion digraph
maps $G^{t}\hookrightarrow G\cup G^{t}$ and $H^{t+\delta}\hookrightarrow H\cup
H^{t+\delta}$ are induced by the identity vertex maps. Therefore $f$ trivially
commutes with these inclusions and hence square
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{C}$
commutes. Hence we get a chain map which we denote
${\mathcal{S}(f,\delta)}_{\\#}:\prescript{g}{}{C}_{\bullet}(G,t)\to\prescript{g}{}{C}_{\bullet}(H,t+\delta)$.
Note, in the case $\delta=0$, this is precisely the same construction as
${\prescript{g}{}{f}}_{\\#}$, given in the proof of Theorem 3.12.

It remains to show that these chain maps (for each $t\geq 0$) constitute a
morphism $\prescript{g}{}{C}(G)\to\prescript{g}{}{C}(H)[\delta]$. Given $s\leq
t$, the chain map
${\prescript{g}{}{\iota(s,t)}}_{\\#}:\prescript{g}{}{C}_{\bullet}(G,s)\to\prescript{g}{}{C}_{\bullet}(G,t)$
is induced by the identity vertex map. The identity vertex map clearly
commutes with $f$. Hence, in each degree ${f}_{\\#}$ commutes with the
${\iota(s,t)}_{\\#}$. Therefore, ${\mathcal{S}(f,\delta)}_{\\#}$ commutes with
${\prescript{g}{}{\iota(s,t)}}_{\\#}$.

Simple composition of digraph maps confirms that $g\circ f$ is a
$\delta_{g}+\delta_{f}$-shifting vertex map. Note that in each degree the
chain map is constructed via the functor $C_{\bullet}$. Therefore, in each
degree, we have ${(g\circ f)}_{\\#}={g}_{\\#}\circ{f}_{\\#}$ which yields
equation (5.3). ∎

Recall that $\mathcal{T}(\prescript{g}{}{C}(G),\epsilon)$ at each $t\geq 0$ is
the chain map
${\prescript{g}{}{\iota(t,t+\epsilon)}}_{\\#}:\prescript{g}{}{C}(G,t)\to\prescript{g}{}{C}(G,t+\epsilon)$.
Shifting this by $\delta$,
$\mathcal{T}(\prescript{g}{}{C}(G),\epsilon)[\delta]$ is given at $t\geq 0$ by
the chain map ${\prescript{g}{}{\iota(t+\delta,t+\delta+\epsilon)}}_{\\#}$.

######  Lemma 5.4.

A $\delta$-shifting vertex map is a $\delta^{\prime}$-shifting vertex map for
any $\delta^{\prime}\geq\delta$ and

${\mathcal{S}(f,\delta^{\prime})}_{\\#}=\mathcal{T}(\prescript{g}{}{C}(H),\delta^{\prime}-\delta)[\delta]\circ{\mathcal{S}(f,\delta)}_{\\#}.$
(5.4)

###### Proof.

Clearly a $\delta$-shifting vertex map is a $\delta^{\prime}$-shifting vertex
map since $G^{\delta}\subseteq G^{\delta^{\prime}}$. Since
$\iota(t+\delta,t+\delta^{\prime})$ is induced by the inclusion vertex map, we
get the following commutative diagrams of digraph maps

${G^{t}}$${G\cup G^{t}}$${H^{t+\delta}}$${H^{t+\delta^{\prime}}}$${H\cup
H^{t+\delta}}$${H\cup
H^{t+\delta^{\prime}}}$$\scriptstyle{f}$$\scriptstyle{f}$$\scriptstyle{f}$$\scriptstyle{f}$$\scriptstyle{\iota(t+\delta,t+\delta^{\prime})}$$\scriptstyle{\iota(t+\delta,t+\delta^{\prime})}$

Applying the functor $C$ to these diagrams yields two commutative diagrams in
$\bm{\mathrm{Ch}}$. The diagonal maps are components of
${\mathcal{S}(f,\delta^{\prime})}_{\\#}$, the vertical maps are components of
${\mathcal{S}(f,\delta)}_{\\#}$ and the horizontal maps are components of
${\prescript{g}{}{\iota(t+\delta,t+\delta^{\prime})}}_{\\#}$. Hence we have a
commutative diagram

${\prescript{g}{}{C}_{\bullet}(G,t)}$${\prescript{g}{}{C}_{\bullet}(H,t+\delta)}$${\prescript{g}{}{C}_{\bullet}(H,t+\delta^{\prime})}$$\scriptstyle{{\mathcal{S}(f,\delta)}_{\\#}}$$\scriptstyle{{\mathcal{S}(f,\delta^{\prime})}_{\\#}}$$\scriptstyle{{\prescript{g}{}{\iota(t+\delta,t+\delta^{\prime})}}_{\\#}}$

as required. ∎

###  5.2 Weight perturbation

The classical stability theorem of persistent homology (first shown in [13])
is that for two continuous tame function $f,g:X\to\mathbb{R}$ of a trianguable
topological space $X$, denoting the persistence barcode of their sub-level set
filtration by $\mathcal{B}{}_{f}$ and $\mathcal{B}{}_{g}$ respectively,

$d_{B}(\mathcal{B}{}_{f},\mathcal{B}{}_{g})\leq|\\!|f-g|\\!|_{\infty}.$ (5.5)

In our setting, the closet analogy to changing the function is changing the
weighting, as well as the corresponding effect that has on the shortest-path
quasimetric. We find that GrPPH is stable to perturbations of the edge
weights. Moreover, the stability is local since it depends only of the weights
of the perturbed edges.

######  Definition 5.5.

Given a weighted digraph $G=(V,E,w)$ and a new weight function
$w^{\prime}:E(G)\to\mathbb{R}_{>0}$, we define
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathbb{O}^{p}_{w^{\prime}}{G}}:=(V,E,w^{\prime})$.

######  Theorem 5.6.

Given a weighted digraph $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and a new weighting
function $w^{\prime}:E(G)\to\mathbb{R}_{>0}$, let $d$ and $d^{\prime}$ denote
the shortest-path quasimetric on $G$ and $\mathbb{O}^{p}_{w^{\prime}}{G}$
respectively. Then

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{p}_{w^{\prime}}{G})}\big{)}\leq\max_{i,j\in
V}\left|d(i,j)-d^{\prime}(i,j)\right|\leq\sum_{e\in
E}\left|w(e)-w^{\prime}(e)\right|.$ (5.6)

###### Proof.

For brevity, denote $G^{\prime}:=\mathbb{O}^{p}_{w^{\prime}}{G}$ and
$\delta:=\max_{i,j\in V}\left|d(i,j)-d^{\prime}(i,j)\right|$. First note that
for any $(i,j)$ and any path $p\in\mathcal{P}({i}\to{j})$

$\left|\sum_{e\in p}w(e)-\sum_{e\in p}w^{\prime}(e)\right|\leq\sum_{e\in
p}\left|w(e)-w^{\prime}(e)\right|\leq\sum_{e\in
E}\left|w(e)-w^{\prime}(e)\right|=:W_{1}.$ (5.7)

So the cost of $p$ differs by at most $W_{1}$. Minimising over
$\mathcal{P}({i}\to{j})$, we see $\left|d(i,j)-d^{\prime}(i,j)\right|\leq
W_{1}$.

Since $V(G)=V(G^{\prime})$, there are identity vertex maps $i_{1}:V(G)\to
V(G^{\prime})$ and $i_{2}:V(G^{\prime})\to V(G)$. Now $i_{1}$ defines a
digraph map $G\to G^{\prime}$ since $G=G^{\prime}$ as digraphs. Moreover,
given $(i,j)\in E(G^{t})$, then $d(i,j)\leq t$ so $d^{\prime}(i,j)\leq
t+\delta$ and hence $(i,j)\in E((G^{\prime})^{t+\delta})$. This shows $i_{1}$
defines a digraph map $G^{t}\to(G^{\prime})^{t+\delta}$ for all $t\geq 0$.
Therefore $i_{1}$ (and likewise $i_{2}$) is a $\delta$-shifting vertex map.
Hence, we obtain morphisms

${\mathcal{S}(i_{1},\delta)}_{\\#}:\prescript{g}{}{C}(G)\to\prescript{g}{}{C}(G^{\prime})[\delta]\quad\text{
and
}\quad{\mathcal{S}(i_{2},\delta)}_{\\#}:\prescript{g}{}{C}(G^{\prime})\to\prescript{g}{}{C}(G)[\delta].$
(5.8)

Moreover, since composing $i_{1}$ and $i_{2}$ in either ordered yields the
identity vertex map, these morphisms constitute a $\delta$-interleaving. The
first inequality then follows by the isometry theorem. ∎

######  Remark 5.7.

Continuing the analogy to the classical stability theorem, note that the
sharper bound obtained by Theorem 5.6 is $|\\!|d-d^{\prime}|\\!|_{\infty}$
while the weaker bound is $|\\!|w-w^{\prime}|\\!|_{1}$.

###  5.3 Edge subdivision

Weighted digraphs arising in applications are subject not only to numerical
noise (i.e. weight perturbation) but also _structural noise_. For the
remainder of this section, we investigate the effects of various structural
perturbations.

First, we consider edge subdivision, in which one or mare parent edge is split
into multiple daughter edges with the weight distributed amongst them. Since
we are interpreting edge weights as corresponding to a length, it is natural
to require that the sum of the weights of the daughter edges equals the weight
of the parent edge. In order to formalise how the weight of an edge is
subdivided amongst its daughters, we use maps into the standard $d$-simplex,
where $d$ is the number of daughter edges.

######  Definition 5.8.

Given a weighted digraph $G=(V,E,w)$

  1. (a)

A  subdivision $S$ of $G$ is a choice of edges $F\subseteq E$, along with a
map $S:F\to\sqcup_{d\in\mathbb{N}}\Delta^{d}$ from edges in $F$ to the formal
disjoint union of all standard $d$-simplices.

Intuitively, a subdivision gives us a recipe for subdividing the edges of $F$
where $S(e)_{i}$ describes the fraction of $w(e)$ which the $i^{th}$ daughter
edge of $e$ should receive.

######  Notation 5.9.

Given a subdivision $S:F\to\sqcup_{d\in\mathbb{N}}\Delta^{d}$,

  1. (a)

Let
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}d(e)}$
denote the simplex dimension such that $S(e)\in\Delta^{d(e)}$.

  2. (b)

Let
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}CS(e)}$
denote the $d(e)$-tuple of cumulative sums, i.e.
$CS(e)_{i}:=\sum_{j=1}^{i}S(e)_{j}$.

######  Definition 5.10.

Given a subdivision $S:F\to\sqcup_{d\in\mathbb{N}}\Delta^{d}$, define

$\displaystyle V_{S}$ $\displaystyle:=V_{old}\sqcup
V_{new}:=V\sqcup\bigsqcup_{e\in F}\\{v_{e,1},\dots,v_{e,d(e)-1}\\}$
$\displaystyle E_{S}$ $\displaystyle:=E_{old}\sqcup E_{new}:=(E\setminus
F)\sqcup\bigsqcup_{e\in F}\\{\tau_{e,1},\dots,\tau_{e,d(e)}\\}$ $\displaystyle
w_{S}(\tau)$ $\displaystyle:=\begin{cases}w(\tau)&\text{if }\tau\in E_{old}\\\
S(e)_{i}\cdot w(e)&\text{if }\tau=\tau_{e,i}\end{cases}$

where $\tau_{e,i}=(v_{e,i-1},v_{e,i})$ and we denote
$v_{e,0}:=\operatorname*{st}(e)$ and $v_{e,d(e)}:=\operatorname*{fn}(e)$. We
then define
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\mathbb{O}^{s}_{S}{G}}:=(V_{S},E_{S},w_{S})$.

We show that the descriptor is stable to arbitrary subdivisions of arbitrary
subsets of edges. Moreover, this stability is local since the bound depends
only on the weight of subdivided edges.

######  Theorem 5.11.

Given a weighted digraph $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and any subdivision
$S:F\to\sqcup_{d\in\mathbb{N}}\Delta^{d}$,

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{s}_{S}{G})}\big{)}\leq\max_{e\in
F}w(e).$ (5.9)

###### Proof.

First, we setup some notation. Denote
$G_{S}:=\mathbb{O}^{s}_{S}{G}=(V_{old}\sqcup V_{new},E_{old}\sqcup
E_{new},w_{S})$. We let $d$ and $d_{S}$ denote the shortest-path quasimetric
on $G$ and $G_{S}$ respectively. Finally, let $W:=\max_{e\in F}w(G)(e)$.

Our strategy is to employ the isometry theorem (Theorem 2.38) Define the
following vertex maps

$\displaystyle f:V(G)\to V(G_{S})\quad$ $\displaystyle v\mapsto v;$ (5.10)
$\displaystyle g:V(G_{S})\to V(G)\quad$ $\displaystyle
v\mapsto\begin{cases}v&\text{if }v\in V_{old},\\\
\operatorname*{st}(e)&\text{if }v_{e,i}\in V_{new}\text{ and
}CS(e)_{i}<1/2,\\\ \operatorname*{fn}(e)&\text{if }v_{e,i}\in V_{new}\text{
and }CS(e)_{i}\geq 1/2,\end{cases}$ (5.11)

which are visualized in Figure 10.

$a$$b$$a$$v_{e,1}$$v_{e,2}$$v_{e,3}$$b$fg$G:$$G_{S}:$ Figure 10: Visualising
the vertex maps $f$ and $g$ under the subdivision $S(e)=(1/4,1/4,1/4,1/4)$
where $e=(a,b)$.

######  Claim 5.11.1.

For vertices $i,j\in V_{old}$, there is a path $i\leadsto j$ in $G$ of length
$t$ if and only if there is one in $G_{S}$.

###### Proof of Claim.

This is clear to see, since the weight of an edge is shared amongst its
daughter edges in the subdivision. ∎

######  Claim 5.11.2.

For any $t\geq 0$, $f$ defines a digraph map $G^{t}\to G_{S}^{t+W}$ and $G\cup
G^{t}\to G_{S}\cup G_{S}^{t+W}$.

###### Proof of Claim.

Since $f$ is just the inclusion vertex map, Claim 5.11.1 shows that $f$
defines a digraph map $G^{t}\to G_{S}^{t}$ and so certainly $G^{t}\to
G_{S}^{t+W}$. For the second map, pick an edge $e\in E$ and note $f(e)=e$. If
$e\not\in F$ then it is undivided and $e\in E(G_{s})$. Otherwise $e\in F$ and
$e\not\in E(G_{s})$, however we note
$d_{S}(\operatorname*{st}(e),\operatorname*{fn}(e))\leq w(e)\leq W$.
Therefore, for any $t\geq 0$, $e\in G_{s}^{t}+W$ and hence $f$ defines a
digraph map $G\cup G^{t}\to G_{S}\cup G_{S}^{t+W}$. ∎

######  Claim 5.11.3.

For any $t\geq 0$, $g$ defines a digraph map $G_{S}^{t}\to G^{t+W}$ and
$G_{S}\cup G_{S}^{t}\to G\cup G^{t+W}$.

###### Proof of Claim.

Given an edge $\tau=(a,b)\in E(G_{S}^{t})$ there is a path $p:a\leadsto b$ in
$G_{S}$ of length at most $t$. We may assume that $g(a)\neq g(b)$, else there
is nothing to check for this edge. If $a=v_{e,i}$ is a new vertex from
subdividing an edge $e\in F$ then $g(a)$ is either $\operatorname*{st}(e)$ or
$\operatorname*{fn}(e)$. Either by adding or removing relevant daughter edges
of $e$ to/from the start of $p$, we obtain a new path $g(a)\leadsto b$ in
$G_{S}$. By construction this, will add at most $w(e)/2\leq W/2$ to the length
of $p$. Likewise we can alter the end of $p$ to obtain a path $g(a)\leadsto
g(b)$ in $G_{S}$ of length at most $t+W$. By Claim 5.11.1, we see $g(\tau)\in
E(G^{t+W})$.

Finally, given an edge $\tau\in G_{s}$ there are two cases. If $\tau\in
E_{old}$ then the edge is preserved under $g$. Else $\tau=\tau_{e,i}\in
E_{new}$ in which case either $\tau$ is collapsed to one of the endpoints of
$e$, or it is mapped to $e$. Hence $g$ is digraph map $G_{S}\to G$ and the
final requirement follows. ∎

Therefore, $f$ and $g$ are $W$-shifting vertex maps and induce morphisms

${\mathcal{S}(f,W)}_{\\#}:\prescript{g}{}{C}(G)\to\prescript{g}{}{C}(G_{S})[W]\quad\text{
and
}\quad{\mathcal{S}(g,W)}_{\\#}:\prescript{g}{}{C}(G_{S})\to\prescript{g}{}{C}(G)[W].$
(5.12)

Now note that, as vertex maps $g\circ f=\mathrm{id}_{V(G)}$. Therefore, at the
level of homology we have
${\mathcal{S}(g,W)}_{\ast}\circ{\mathcal{S}(f,W)}_{\ast}=\mathcal{T}(\prescript{g}{}{\mathcal{H}}_{1}(G),2W).$

Composing vertex maps in the opposite order, we do not obtain the identity.
Moreover,
${\mathcal{S}(f,W)}_{\\#}\circ{\mathcal{S}(g,W)}_{\\#}\neq\mathcal{T}(\prescript{g}{}{C}(G_{s}),2W)$.
However, we will show that, at every $t\geq 0$, the chain maps on either side
of this inequality differ by a boundary. First, choose a basis
$\\{c_{1},\dots,c_{k}\\}$ of simple undirected circuits for
$\prescript{g}{}{Z}_{1}(G_{S},0)$. By Lemma 4.2, it suffices to prove that for
each $c_{i}$,

${\mathcal{S}(f,W)}_{\\#}{\mathcal{S}(g,W)}_{\\#}{\prescript{g}{}{\iota(0,t)}}_{\\#}c_{i}={\prescript{g}{}{\iota(0,t+2W)}}_{\\#}c_{i}\pmod{B}$
(5.13)

where $B:=\prescript{g}{}{B}_{1}(G_{S},t+2W)$. Since simple undirected
circuits are non-backtracking and the vertices
$\\{v_{e,1},\dots,v_{e,d(e)-1}\\}$ have in-degree $1$ and out-degree $1$, we
can write

$c_{i}=\sum_{e\in F}\alpha_{e}(\tau_{e,1}+\dots+\tau_{e,d(e)})+\sum_{e\in
E\setminus F}\alpha_{e}e$ (5.14)

for some $\alpha_{e}\in\\{0,\pm 1\\}$. Therefore, it suffices to prove the
following two claims.

######  Claim 5.11.4.

For each $e\in F$,
${\mathcal{S}(f,W)}_{\\#}{\mathcal{S}(g,W)}_{\\#}(\tau_{e,1}+\dots+\tau_{e,d(e)})=e$
and for each $e\in E\setminus F$,
${\mathcal{S}(f,W)}_{\\#}{\mathcal{S}(g,W)}_{\\#}e=e$.

###### Proof of Claim.

First note that $f$ fixes the endpoints of every edge $e\in E$ and hence
${\mathcal{S}(f,W)}_{\\#}e=e$. Now, choose arbitrary $e\in F$. There exists
some $M$ such that $g(v_{e,i})=\operatorname*{st}(e)$ for all $i<M$ and
$g(v_{e,i})=\operatorname*{fn}(e)$ for all $i\geq M$. Hence
${\mathcal{S}(g,W)}_{\\#}\tau_{e,i}=0$ for all $i<M$ and all $i>M$ but
${\mathcal{S}(g,W)}_{\\#}\tau_{e,M}=e$. Hence

${\mathcal{S}(f,W)}_{\\#}{\mathcal{S}(g,W)}_{\\#}(\tau_{e,1}+\dots+\tau_{e,d(e)})={\mathcal{S}(f,W)}_{\\#}e=e.$
(5.15)

Finally for $e\in E\setminus F$, $g$ fixes the endpoints of $e$ and hence
${\mathcal{S}(g,W)}_{\\#}e=e$. ∎

######  Claim 5.11.5.

For each $e\in F$, $\tau_{e,1}+\dots+\tau_{e,d(e)}=e\pmod{B}$.

###### Proof of Claim.

Choose any $e\in F$. The path $(\tau_{e,1},\dots,\tau_{e,d(e)})$ is a path of
length $W$ in $G_{S}$, between the endpoints of $e$. The claim now follows by
Lemma 4.1. ∎

Hence
${\mathcal{S}(f,W)}_{\\#}{\mathcal{S}(g,W)}_{\\#}{\prescript{g}{}{\iota(0,t)}}_{\\#}c_{i}={\prescript{g}{}{\iota(0,t+2W)}}_{\\#}c_{i}\pmod{B}$
for each $c_{i}$ and each $t\geq 0$, so, at the level of homology,
${\mathcal{S}(f,W)}_{\ast}\circ{\mathcal{S}(g,W)}_{\ast}=\mathcal{T}(\prescript{g}{}{\mathcal{H}}_{1}(G_{S}),2W)$.
Therefore ${\mathcal{S}(f,W)}_{\ast}$ and ${\mathcal{S}(g,W)}_{\ast}$
constitute a $W$-interleaving and the bound on bottleneck distance follows by
the isometry theorem. ∎

######  Remark 5.12.

Since subdividing an edge does not effect circuit rank of $\mathcal{U}(G)$,
the number of features does not change upon subdivision (by Corollary 4.3).

######  Definition 5.13.

Fix a weighted digraph $G=(V,E,w)\in\bm{\mathrm{WDgr}}$.

  1. (a)

The  medial subdivision,
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}S_{med}(G)}:E(G)\to\Delta^{2}$,
is given by $S(e)=(1/2,1/2)$ for every $e\in E(G)$.

  2. (b)

The  $n^{th}$ iterated medial subdivision of $G$,  $\mathrm{IMS}_{n}(G)$, is
defined iteratively as follows. Firstly, $\mathrm{IMS}_{0}(G):=G$ then for
each $n$, we define
$\mathrm{IMS}_{n}(G):=\mathbb{O}^{s}_{S}{\mathrm{IMS}_{n-1}(G)}$ where
$S=S_{med}(\mathrm{IMS}_{n-1}(G))$.

######  Corollary 5.14.

Given a weighted digraph $G\in\bm{\mathrm{WDgr}}$, the sequence of barcodes
$(\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathrm{IMS}_{n}(G))})_{n\in\mathbb{N}}$
converges under the bottleneck distance.

###### Proof.

We first note that

$\max_{e\in E(\mathrm{IMS}_{n}(G))}w(e)=\frac{1}{2^{n}}\max_{e\in E(G)}w(e).$
(5.16)

Hence Theorem 5.11 implies that the sequence of barcodes is Cauchy. The space
of persistence diagrams with the bottleneck distance is complete [11] and
hence the sequence of barcodes converges. ∎

While we have bottleneck stability, we do _not_ have $1$-Wasserstein
stability.

######  Proposition 5.15.

There exists no function $f:\bm{\mathrm{WDgr}}\to\mathbb{R}$ such that for any
weighted digraph $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and any subdivision
$S:F\to\Delta^{d}$ we have

$d_{W_{1}}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{s}_{S}{G})},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}\big{)}\leq
f\big{(}\operatorname*{\mathcal{N\\!G}}(F;G)\big{)}.$ (5.17)

###### Proof.

Suppose such $f$ exists and consider the following sequence of digraphs in
which each edge has unit weight.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$G_{1}$$G_{2}$$G_{3}$
Figure 11:  A sequence of weighted digraphs $G_{n}$, in which all edges have
unit weight and $\\#\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{n})}=n$.

Intuitively, $G_{n}$ is constructed by gluing $n$ disjoint copies of $G_{1}$
along the path $(v_{0},v_{1},v_{2},v_{3})$. Note that each copy of $G_{1}$
introduces a feature which dies at $t=3$ so

$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{n})}=\left\\{\\!\\!\left\\{[0,3)\text{
with multiplicity }n\right\\}\\!\\!\right\\}.$ (5.18)

Upon subdividing the edge $e=(v_{1},v_{2})$ via $S(e)=(1/2,1/2)$, each feature
changes to $[0,2.5)$. Hence