$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{)}=0.5n$
(5.19)

which eventually exceeds the constant
$f(\operatorname*{\mathcal{N\\!G}}(e;G))$. ∎

###  5.4 Edge collapse

Another potential structural perturbation is that of edge collapses, in which
the two end points of an edge are identified and the edge deleted. In
applications, this may happen particularly to low-weight edges, which cannot
be discerned by the imaging method and hence collapsed to a vertex instead.
Since we interpret edge-weights as corresponding to distance, we add half the
weight of the collapsed edge to each of its neighbours so that the length of
paths through the collapsed edge are not changed.

######  Definition 5.16.

Given a weighted digraph $G=(V,E,w)$ and an edge $e=(a,b)\in E$, define

$\displaystyle V_{e}$
$\displaystyle:={\mathchoice{\raisebox{3.41666pt}{$\displaystyle{V}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.47221pt}{$\displaystyle{a\sim
b}$}}{\raisebox{3.41666pt}{$\textstyle{V}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-3.47221pt}{$\textstyle{a\sim
b}$}}{\raisebox{2.39166pt}{$\scriptstyle{V}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-2.43054pt}{$\scriptstyle{a\sim
b}$}}{\raisebox{1.70833pt}{$\scriptscriptstyle{V}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-1.7361pt}{$\scriptscriptstyle{a\sim
b}$}}}$ (5.20) $\displaystyle E_{e}$
$\displaystyle:={\mathchoice{\raisebox{3.75pt}{$\displaystyle{(E\setminus\\{e\\})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-4.0754pt}{$\displaystyle{(i,j)\sim(i^{\prime},j^{\prime})\iff
i\sim i^{\prime},j\sim
j^{\prime}}$}}{\raisebox{3.75pt}{$\textstyle{(E\setminus\\{e\\})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-4.0754pt}{$\textstyle{(i,j)\sim(i^{\prime},j^{\prime})\iff
i\sim i^{\prime},j\sim
j^{\prime}}$}}{\raisebox{3.75pt}{$\scriptstyle{(E\setminus\\{e\\})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-2.86389pt}{$\scriptstyle{(i,j)\sim(i^{\prime},j^{\prime})\iff
i\sim i^{\prime},j\sim
j^{\prime}}$}}{\raisebox{3.75pt}{$\scriptscriptstyle{(E\setminus\\{e\\})}$}\mkern-5.0mu\diagup\mkern-4.0mu\raisebox{-2.20436pt}{$\scriptscriptstyle{(i,j)\sim(i^{\prime},j^{\prime})\iff
i\sim i^{\prime},j\sim j^{\prime}}$}}}$ (5.21) $\displaystyle w_{e}(\sigma)$
$\displaystyle:=\min_{\tau\in\sigma}\left(w(\tau)+\frac{w(e)}{2}\cdot\mathds{1}_{\tau\in\mathcal{N}(e)}\right)$
(5.22)

where $\mathds{1}_{\tau\in\mathcal{N}(e)}=1\iff\tau\in\mathcal{N}(e)$, else
$\mathds{1}_{\tau\in\mathcal{N}(e)}=0$. 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}^{c}_{e}{G}}:=(V_{e},E_{e},w_{e})$.

Some edge collapses do not drastically alter the topological structure of the
graph or the shortest-path quasimetric. Therefore, we can get a local
stability bound on a subset of such operations.

######  Theorem 5.17.

Given a weighted digraph, $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and an edge
$e=(a,b)\in E$. Suppose $e$ is the only outgoing edge from $a$ and the only
incoming edge to $b$ (as in Figure 12), then

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{c}_{e}{G})}\big{)}\leq
w(e)+\min\left(\max_{v\in\mathcal{N}_{in}(a)}w(v,a),\max_{v\in\mathcal{N}_{out}(b)}w(b,v)\right)=:\delta.$
(5.23)

$a$$b$$v_{e}$$G$$\mathbb{O}^{c}_{e}{G}$ Figure 12: Schematic of
$\operatorname*{\mathcal{N\\!G}}(e)\subseteq G$ and
$\operatorname*{\mathcal{N\\!G}}(v_{e})\subseteq\mathbb{O}^{c}_{e}{G}$, under
the assumptions of Theorem 5.17.

###### Proof.

Denote $G_{e}:=\mathbb{O}^{c}_{e}{G}=(V_{e},E_{e},w_{e})$. First note that the
condition ensures that $\\{a,b\\}$ are the only vertices which get identified.
Moreover, no edges are identified, although $e$ is collapsed and the weights
on neighbours of $e$ may change. To ease notation we drop all equivalence
class notation for the vertices and edges of $G_{e}$ and refer to the new
vertex as $v_{e}:=\\{a,b\\}$.

We define two vertex maps. Firstly $f:V\to V_{e}$ is given by $v\mapsto v$ for
$v\neq a,b$ and $a,b\mapsto v_{e}$. Secondly, we define $g:V_{e}\to V$ as
follows. For most elements of $V_{e}$ we choose the only representative of the
equivalence class $v\mapsto v$. The only class containing more than one
element is $v_{e}=\\{a,b\\}$. For this class, we choose $g(v_{e})=a$ if

$\max_{v\in\mathcal{N}_{in}(a)}w(v,a)\geq\max_{v\in\mathcal{N}_{out}(b)}w(b,v),$
(5.24)

else we choose $g(v_{e})=b$. Let us assume that $g(v_{e})=a$; the other case
admits a similar proof. We show that $f$ and $g$ define $\delta$-shifting
vertex maps.

######  Claim 5.17.1.

$f$ defines a digraph map $G\to G_{e}$.

###### Proof of Claim.

All edges of $G$ are mapped to edges of $G_{e}$, with the exception of
$e=(a,b)$. The two endpoints of $e$ are mapped to the same point, $v_{e}$.
Therefore, $f$ define a digraph map as required. ∎

######  Claim 5.17.2.

$f$ defines a digraph map $G^{t}\to G_{e}^{t+\delta}$ for all $t\geq 0$.

###### Proof of Claim.

If $(i,j)\in E(G^{t})$, then there is a path $p$ joining $i\leadsto j$ of
length at most $t$ in $G$. Thanks to the previous claim, $f(p)$ is a path
$f(i)\leadsto f(j)$ in $G_{e}$. Thanks to the assumption on $e$, $p$ passes
through at most one incoming edge to $a$ and at most one outgoing edge from
$b$. Since these are the only edges whose weights are increased and each of
these is increased by $w(e)/2$, we see $f(p)$ is of length at most $t+w(e)$.
Therefore $(i,j)\in E(G_{e}^{t+\delta})$. ∎

######  Claim 5.17.3.

$g$ defines a digraph map $G_{e}^{t}\to G^{t+\delta}$.

###### Proof of Claim.

Suppose $(i,j)\in E(G_{e}^{t})$, then there is a path $p:i\leadsto j$ in
$G_{e}$ of length at most $t$. Suppose $p$ does not traverse $v_{e}$, then it
also doesn’t traverse any edge incident to $v_{e}$. Therefore $p$ also exists
in $G$ and is of length at most $t$. Hence, $(i,j)\in G^{t+\delta}$.

Conversely, suppose $p$ does traverse $v_{e}$ and write

$p=(v_{0}=i,v_{1},\dots,v_{k-1},v_{e},v_{k+1},\dots,v_{l}=j).$ (5.25)

Note that $v_{k-1}\in\mathcal{N}_{in}(a)$ and
$v_{k+1}\in\mathcal{N}_{out}(a)$. Replacing $v_{e}$ with the sequence $(a,b)$
we obtain a new path

$p^{\prime}=(v_{0}=i,v_{1},\dots,v_{k-1},a,b,v_{k+1},\dots,v_{l}=j).$ (5.26)

which exists in $G$. We now split into cases.
Case 1: If $i\neq v_{e}$ and $j\neq v_{e}$ then $g(i)=i$ and $g(j)=j$ and
$p^{\prime}$ is a path $g(i)=i\leadsto j=g(j)$.
Case 2: If $i=v_{e}$ then $j\neq v_{e}$ so $g(i)=a$ and $g(j)=j$ and
$p^{\prime}$ is a path $g(i)=a\leadsto j=g(j)$.
Case 3: If $j=v_{e}$ then $i\neq v_{e}$ so $g(i)=i$ and $g(j)=a$ but
$p^{\prime}$ is a path $g(i)=i\leadsto b$ which ends $(a,e,b)$; removing the
last edge yields a path $g(i)=i\leadsto a=g(j)$.

Note that edge-weights may decrease moving from $G_{e}$ to $G$ however we may
add one additional edge, namely $e$. Therefore, the length of $p^{\prime}$ is
at most $t+w(e)$ and hence $(i,j)\in G_{e}^{t+\delta}$. ∎

######  Claim 5.17.4.

$g$ defines a digraph map $G_{e}\cup G_{e}^{t}\to G\cup G^{t+\delta}$.

###### Proof of Claim.

Thanks to the previous claim, we only need to check edges $(i,j)\in E(G_{e})$.
Any edge $(i,j)\in E(G_{e})$ which is not incident to $v_{e}$ is mapped by $g$
to itself $(i,j)\in E(G)$. By the assumption on $e$, if $j=v_{e}$, then
$i\in\mathcal{N}_{in}(a)$ and hence $(g(i),g(v_{e}))=(i,a)\in E(G)$. Else,
suppose $i=v_{e}$, then $j\in\mathcal{N}_{out}(b)$. Note that the path
$(a,b,j)$ in $G$ is of length $w(e)+w(b,j)\leq\delta$. Therefore
$(g(v_{e}),g(j))=(a,j)\in E(G^{t+\delta})$ for all $t\geq 0$. ∎

As vertex maps $f\circ g=\mathrm{id}_{V_{e}}$ and hence
${\mathcal{S}(f,\delta)}_{\ast}{\mathcal{S}(g,\delta)}_{\ast}=\mathcal{T}(\prescript{g}{}{C}(G_{e}),2\delta)$.
However, it is not the case that $g\circ f=\mathrm{id}_{V}$ nor
${\mathcal{S}(g,\delta)}_{\\#}{\mathcal{S}(f,\delta)}_{\\#}=\mathcal{T}(\prescript{g}{}{C}(G),2\delta)$.
However, these two chain maps do agree at the level of homology, as we now
show. We follow a similar approach to the proof of Theorem 5.11.

######  Claim 5.17.5.

Given a simple undirected circuit $c\in\prescript{g}{}{Z}_{1}(G,0)$, we can
write

$c=\alpha_{e}\big{(}v_{1}a+ab+bv_{2}\big{)}+\sum_{\begin{subarray}{c}\tau\in
E(G)\\\ \tau\neq e,\tau\not\in\mathcal{N}(e)\end{subarray}}\alpha_{\tau}\tau$
(5.27)

for some $v_{1}\in\mathcal{N}_{in}(a)$, $v_{2}\in\mathcal{N}_{out}(b)$ and
$\alpha_{e},\alpha_{\tau}\in\\{0,\pm 1\\}$.

###### Proof of Claim.

This is a direct consequence of the requirement that $e$ is the only outgoing
edge from $a$ and the only incoming edge to $b$. ∎

######  Claim 5.17.6.

For $v_{1}\in\mathcal{N}_{in}(a)$ and $v_{2}\in\mathcal{N}_{out}(b)$, we have
${\mathcal{S}(g,\delta)}_{\\#}{\mathcal{S}(f,\delta)}_{\\#}(v_{1}a+ab+bv_{2})=v_{1}a+av_{2}$
and for $\tau\in E(G)\setminus\mathcal{N}(e),\tau\neq e$ we have
${\mathcal{S}(g,\delta)}_{\\#}{\mathcal{S}(f,\delta)}_{\\#}\tau=\tau$.

###### Proof of Claim.

For the first equality, note that $a$, $v_{1}$ and $v_{2}$ are fixed by
$g\circ f$ whereas $(g\circ f)(b)=a$. For the second, any edge $\tau\in
E(G)\setminus\mathcal{N}(e)$, $\tau\neq e$ does not have $b$ as one of its
endpoints and hence both endpoints of $\tau$ are fixed by $g\circ f$. ∎

Finally it remains to show that for any $v_{1}\in\mathcal{N}_{in}(a)$ and
$v_{2}\in\mathcal{N}_{out}(b)$,

$v_{1}a+ab+bv_{2}=v_{1}a+av_{2}\pmod{\prescript{g}{}{B}_{1}(G,t+\delta)}$
(5.28)

for all $t\geq 0$. Note that $(a,b,v_{2})$ is a path $a\leadsto v_{2}$ of
length at most $\delta$ and hence the directed triangle $(a,b,v_{2})$ is in
the digraph $G^{t+\delta}$ for all $t\geq 0$. The claim then follows since
$\prescript{g}{}{\partial}_{2}(abv_{2})=ab+bv_{2}-av_{2}$. ∎

######  Remark 5.18.

If $G$ is a DAG and an edge $e=(a,b)$ satisfies the condition of Theorem 5.17,
then there is a topological ordering of $G$ with $a$ and $b$ adjacent.
However, note that this is _not_ a sufficient condition for local stability to
edge collapse.

######  Remark 5.19.

Collapses of the sort described in Theorem 5.17 remove exactly one vertex and
one edge and do not change the number of weakly connected components. Hence,
by Corollary 4.3 we have
$\\#\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}=\\#\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{c}_{e}{G})}.$

While some edge collapses are relatively minor, in general they can
drastically alter the topology of the digraph. As such, we cannot expect local
stability to arbitrary edge collapses.

######  Theorem 5.20.

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 edge $e\in E$
therein we have

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{c}_{e}{G})}\big{)}\leq
f\big{(}\operatorname*{\mathcal{N\\!G}}(e;G)\big{)}.$ (5.29)

###### Proof.

Suppose such $f$ exists then consider the following weighted digraph $G$,
where $e:=(v_{0},v_{5})$ and $W:=2f(\operatorname*{\mathcal{N\\!G}}(e;G))+4$.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{e}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$W$$W$$1.5$$1.5$$1.5$$1.5$$G$$\mathbb{O}^{c}_{e}{G}$
Figure 13: An example weighted digraph which illustrates that
$\prescript{g}{}{\mathcal{H}}_{1}$ is locally unstable to arbitrary edge
collapses. Unlabelled edges have weight $1$.

Note, $G$ has 3 features, which die at $2$, $2$ and $W$, while
$\mathbb{O}^{d}_{e}{G}$ has 3 features, which die at $2.5$, $2.5$ and $3$. The
longer feature, supported on the red edge $(v_{2},v_{3})$, has a reduced
death-time in $\mathbb{O}^{d}_{e}{G}$ because there is a shortcut
$(v_{2},v_{e},v_{3})$, of length $3$. Any bijection between these features
(and the diagonals) must have bottleneck cost at least
$\min(W/2,W-3)>f(\operatorname*{\mathcal{N\\!G}}(e;G))$. ∎

While this seems like a serious problem for our descriptor, note that the
collapse in Figure 13 makes significant changes to the topology of the
underlying digraph. Originally, $G$ was a DAG with source $v_{0}$ and sink
$v_{5}$; the edge collapse identified these two nodes and introduced directed
cycles. Moreover, in $G$ the only path $v_{2}\leadsto v_{3}$ was via the
costly red edge but in $\mathbb{O}^{d}_{e}{G}$ there is a shortcut via
$v_{e}$. Therefore, since the profile of paths has changed drastically, it is
arguably desirable that our descriptor changes too.

###  5.5 Edge deletion

####  5.5.1 General case

Another important class of structural perturbations is edge deletion.
Intuitively, as with edge collapse, some edge deletions can have drastic
impact on the descriptor whereas some deletions are minor events.

######  Definition 5.21.

Given a weighted digraph $G=(V,E,w)$ and an edge $e\in E$, 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}^{d}_{e}{G}}:=(V,E\setminus\\{e\\},w_{e})$
where $w_{e}$ is obtained by restricting $w$ to $E\setminus\\{e\\}$.

We find that our descriptor is stable to deletions but the bound depends on
the minimum length of a possible diversion. In general, this diversion cost
may be infinite.

######  Theorem 5.22.

Given a weighted digraph $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and an edge
$e=(a,b)\in E$, let $d$ and $d_{e}$ denote the shortest-path quasimetric for
$G$ and $\mathbb{O}^{d}_{e}{G}$ respectively. Assume that $d_{e}(a,b)$ is
finite, then

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{e}{G})}\big{)}\leq
d_{e}(a,b).$ (5.30)

###### Proof.

Denote $G_{e}:=\mathbb{O}^{d}_{e}{G}=(V_{e},E_{e},w_{e})$ and
$\delta:=d_{e}(a,b)$. We first note that

$\max_{i,j\in
V}\left|d_{e}(i,j)-d(i,j)\right|\leq\left|d_{e}(a,b)-d(a,b)\right|\leq
d_{e}(a,b)=\delta.$ (5.31)

To see this, note that for arbitrary $i,j\in V$ we have $d_{e}(i,j)\geq
d(i,j)$ since there are strictly fewer paths $i\leadsto j$ in $G_{e}$ than in
$G$. Moreover, there is path $p_{e}:a\leadsto b$ in $G_{e}$ of length at most
$\delta$. Then, given a path $p:i\leadsto j$ in $G$ of length $t$, the path
contains $e$ at most once. We can replace $e$ with $p_{e}$ to obtain a new
path $i\leadsto j$ in $G_{e}$ of length at most $t+(\delta-w(e))\leq
t+\delta$. Therefore, $d_{e}(i,j)\leq d(i,j)+\delta$.

We claim that $\mathrm{id}_{V}$ constitutes a $d_{e}(a,b)$-shifting vertex map
$G\to G_{e}$ and $G_{e}\to G$. Then, by a similar argument to that of Theorem
5.6, we obtain the result via the isometry theorem. The inequalities of (5.31)
automatically imply that $\mathrm{id}_{V}$ defines a digraph map $G^{t}\to
G_{e}^{t+\delta}$ and $G_{e}^{t}\to G^{t+\delta}$ for all $t\geq 0$.

Then $E_{e}\subseteq E$, so $\mathrm{id}_{V}$ certainly defines a digraph map
$G_{e}\to G$ and thus $G_{e}\cup G_{e}^{t}\to G\cup G^{t+\delta}$ for all
$t\geq 0$. In the other direction, $E\setminus E_{e}=\\{e\\}$ so
$\mathrm{id}_{V}$ does _not_ define a digraph map $G\to G_{e}$ However $e\in
E(G_{e}^{t+\delta})$ for all $t\geq 0$ and hence $\mathrm{id}_{V}$ _does_
define a digraph map $G\cup G^{t}\to G_{e}\cup G_{e}^{t+\delta}$ for all
$t\geq 0$. ∎

In general, Theorem 5.22 is a non-local bound, but if an edge has an
alternative route in its local neighbourhood then the bound becomes local.

######  Corollary 5.23.

Given a weighted digraph $G=(V,E,w)$ and an edge $e=(a,b)\in E$ such that
there exists a vertex $v\in V$ such that $a\to v\to b$ then

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{e}{G})}\big{)}\leq
w(a,v)+w(v,b).$ (5.32)

Next, we consider the scenario where an edge $e$ is subdivided and then one of
the daughter edges $\tau:=\tau_{e,i}$ is deleted (as shown in Figure 14). In
the resulting weighted digraph $\mathbb{O}^{d}_{\tau}{G}$, there is no
alternative path between the endpoints of $\tau$ so the bound from Theorem
5.22 would be infinite. However, we can bound the effect of such an operation.

$\tau$$e$$G_{S}$$\mathbb{O}^{d}_{\tau}{G_{S}}$$G$$G_{e}$ Figure 14: Schematic
of the four weighted digraphs in Theorem 5.24, where $e$ is the curved bottom
edge and $\tau$ is as labelled.

######  Theorem 5.24.

Given a weighted digraph $G=(V,E,w)\in\bm{\mathrm{WDgr}}$, an edge $e=(a,b)\in
E$ and a subdivision $S:\\{e\\}\to\Delta^{d}$, denote
$G_{S}:=\mathbb{O}^{s}_{S}{G}$ and $G_{e}:=\mathbb{O}^{d}_{e}{G}$. Let $d_{e}$
denote the shortest-path quasimetric in $G_{e}$. Choose any of the daughter
edges $\tau:=\tau_{e,i}\in E(G_{S})$, then

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{S})},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{\tau}{G_{S}})}\big{)}\leq\max\left(d_{e}(a,b),\frac{w(e)}{2}\right)=:\delta.$
(5.33)

###### Proof.

We first note that upon deleting $\tau$ from $G_{S}$, the remaining daughter
edges and daughter vertices from the subdivision can be deleted, using
Corollary 5.28 and Corollary 5.30. The remaining graph is precisely $G_{e}$
and so
$\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{\tau}{G_{S}})\cong\prescript{g}{}{\mathcal{H}}_{1}(G_{e}).$
Hence, it remains to prove

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{S})},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{e})}\big{)}\leq\delta.$
(5.34)

The proof continues as an amalgamation of the proofs of Theorem 5.11 and
Theorem 5.22. Define the following vertex maps

$\displaystyle f:V(G_{e})\to V(G_{S})\quad$ $\displaystyle v\mapsto v;$ (5.35)
$\displaystyle g:V(G_{S})\to V(G_{e})\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.36)

We note that $f$ induces a contraction digraph map $G_{e}\to G_{S}$ Hence, by
Lemma 5.4, it is a $\delta$-shifting vertex map and moreover,
${\mathcal{S}(f,\delta)}_{\\#}=\mathcal{T}(\prescript{g}{}{C}(G_{s}),\delta)\circ{\prescript{g}{}{f}}_{\\#}$.

######  Claim 5.24.1.

$g$ induces a digraph map $G_{S}^{t}\to G_{e}^{t+\delta}$, for every $t\geq
0$.

###### Proof of Claim.

Given $(i,j)\in E(G_{S}^{t})$, there is a path $p:i\leadsto j$ in $G_{s}$ of
length at most $t$. Since $d_{e}(a,b)\leq\delta$ there is a path
$p_{e}:a\leadsto b$ in $G_{e}$ of length at most $\delta$. We construct a new
trail $p^{\prime}$ in $G_{e}$ as follows.

If the entire sequence of daughter edges $(\tau_{e,1},\dots,\tau_{e,d(e)})$
appears in $p$ then we replace that sequence with $p_{e}$. If $i\in V_{new}$
and $g(i)=a$ then we replace the initial sequence of daughter edges with
$p_{e}$. If $i\in V_{new}$ and $g(i)=b$ then we simply remove the initial
sequence of daughter edges. Likewise, if $j\in V_{new}$ and $g(j)=b$ then we
replace the final sequence of daughter edges with $p_{e}$. If $j\in V_{new}$
and $g(j)=a$ then we simply remove the final sequence of daughter edges. This
yields a trail $p^{\prime}:g(i)\leadsto g(j)$ Since $p$ cannot repeat edges,
this construction inserts $p_{e}$ at most once and hence the length of
$p^{\prime}$ is at most $t+\delta$. Therefore $(i,j)\in E(G_{e}^{t+\delta})$.
∎

######  Claim 5.24.2.

$g$ induces a digraph map $G_{S}\cup G_{S}^{t}\to G_{e}\cup G_{e}^{t+\delta}$,
for every $t\geq 0$.

###### Proof of Claim.

It remains to check the image of edge $e\in(G_{S})$ Any un-subdivided edge
$e\in E_{old}$ is preserved under $g$. Given an edge $\tau_{e,i}=(x,y)\in
E_{new}$ then $\tau=(v_{e,i-1},v_{e,i})$ for some $i$ and there are three
cases

$(g(v_{e,i-1}),g(v_{e,i}))=(\operatorname*{st}(e),\operatorname*{st}(e))\text{
or }(\operatorname*{st}(e),\operatorname*{fn}(e))\text{ or
}(\operatorname*{fn}(e),\operatorname*{fn}(e)).$ (5.37)

Hence either $g(x)=g(y)$ or $(g(x),g(y))=e$. The edge $e$ does not appear in
$G_{e}$ but it does appear in $G_{e}^{t+\delta}$ for all $t\geq 0$. Therefore
$g$ defines a digraph map as required. ∎

Again, we see $g\circ f=\mathrm{id}_{V(G)}$ and hence
${\mathcal{S}(g,\delta)}_{\ast}\circ{\mathcal{S}(f,\delta)}_{\ast}=\mathcal{T}(\prescript{g}{}{\mathcal{H}}_{1}(G_{e}),2\delta)$.
The proof that
${\mathcal{S}(f,\delta)}_{\ast}\circ{\mathcal{S}(g,\delta)}_{\ast}=\mathcal{T}(\prescript{g}{}{\mathcal{H}}_{1}(G_{S}),2\delta)$
is identical to the corresponding section in the proof of Theorem 5.11. Note
that we require $2\delta\geq w(e)$ so that we can apply Lemma 4.1 to show

$\tau_{e,1}+\dots+\tau_{e,d(e)}=e\pmod{\prescript{g}{}{B}_{1}(G,t+2\delta)},$
(5.38)

for all $t\geq 0$. ∎

In general, the shortest-path distance between the endpoints of an edge, upon
its deletion, can depend on _all_ remaining edges in the graph. Therefore, the
bound of Theorem 5.22 is non-local and indeed no generic, local stability
theorem is possible.

######  Theorem 5.25.

There exists no function $f:\bm{\mathrm{WDgr}}\to\mathbb{R}$ such that for any
digraph $G=(V,E,w)\in\bm{\mathrm{WDgr}}$ and any edge $e\in E$ therein we have

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{e}{G})}\big{)}\leq
f\big{(}\operatorname*{\mathcal{N\\!G}}(e;G)\big{)}.$ (5.39)

###### Proof.

Suppose such $f$ exists then consider the following weighted digraph $G$,
where $e:=(v_{1},v_{3})$ and $W:=2f(\operatorname*{\mathcal{N\\!G}}(e;G))+2$.

$v_{0}$$v_{1}$$v_{3}$$v_{2}$$v_{0}$$v_{1}$$v_{3}$$v_{2}$$W$$W$$G$$\mathbb{O}^{d}_{e}{G}$
Figure 15: An example weighted digraph which illustrates that
$\prescript{g}{}{\mathcal{H}}_{1}$ is locally unstable to arbitrary edge
deletions. Unlabelled edges have weight $1$.

Note, $G$ has a single feature which dies at time $W$, whereas
$\mathbb{O}^{d}_{e}{G}$ has no features. Therefore, the bottleneck distance is
$W/2>f(\operatorname*{\mathcal{N\\!G}}(e;G))$. ∎

####  5.5.2 Separating edges

Since all features are born at $t=0$ and $\prescript{g}{}{Z}_{1}(G,0)$ has a
basis of simple undirected circuits, one might expect that edges never
involved in such circuits can be safely deleted without changing the
descriptor. Indeed, this is the case and is a direct consequence of the wedge
decomposition theorem.

######  Definition 5.26.

In a weighted digraph $G=(V,E,w)$, an edge $e=(a,b)\in E$ is called a
separating edge if $a$ and $b$ are weakly disconnected in
$\mathbb{O}^{d}_{e}{G}$.

######  Remark 5.27.

An edge is separating if and only if there are no simple undirected circuits
containing it.

######  Corollary 5.28.

Given a weighted digraph $G=(V,E,w)$ and a separating edge $e=(a,b)\in E$,

$\prescript{g}{}{\mathcal{H}}_{1}(G)\cong\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{e}{G}).$
(5.40)

###### Proof.

First note that $a$ and $b$ are both wedge vertices. Let $V_{1}$ denote the
vertices in the weak connected component of $a$ in $\mathbb{O}^{d}_{e}{G}$.
Define $V_{2}:=\\{a,b\\}$. Finally, define $V_{3}:=(V(G)\setminus V_{1})$. Let
$G_{1}$, $G_{2}$ and $G_{3}$ denote the induced subgraph of $G$ on $V_{1}$,
$V_{2}$ and $V_{3}$ respectively.

Then a wedge decomposition of $G$ is $G=(G_{1}\vee_{a}G_{2})\vee_{b}G_{3}$ and
a disjoint union decomposition of $\mathbb{O}^{d}_{e}{G}$ is
$\mathbb{O}^{d}_{e}{G}=G_{1}\sqcup G_{3}$. Note that $G_{2}$ is just a single
edge connecting two vertices so $\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$ is
the trivial persistent vector space. Using Theorem 4.18 and Theorem 4.21, we
see

$\prescript{g}{}{\mathcal{H}}_{1}(G)\cong\prescript{g}{}{\mathcal{H}}_{1}(G_{1})\oplus\prescript{g}{}{\mathcal{H}}_{1}(G_{2})\oplus\prescript{g}{}{\mathcal{H}}_{1}(G_{3})\cong\prescript{g}{}{\mathcal{H}}_{1}(G_{1})\oplus\prescript{g}{}{\mathcal{H}}_{1}(G_{3})\cong\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{e}{G})$
(5.41)

as required. ∎

####  5.5.3 Interpretation

$v_{0}$$v_{2}$$v_{3}$$v_{1}$$5$$w_{0}$$w_{1}$$w_{2}$$w_{3}$$10$$2$$2$$2$$2$$2$$G_{1}$$G_{2}$
Figure 16: Some example weighted digraphs, used to interpret the consequences
of the stability theorems obtained in Section 5.5. Unlabelled edges have
weight $1$.

Theorem 5.22 tells us that we are stable to deleting edges which have fast
diversions. That is, if there is a path $p:i\leadsto j$, not involving the
edge $e:=(i,j)$, of length $\delta$, then removing $e$ changes the barcode by
at most $\delta$ in bottleneck distance. Note, this bound is independent of
the weight of the deleted edge $w(e)$.

To illustrate this point, consider $G_{1}$ in Figure 16. Removing
$(v_{2},v_{3})$ incurs a bottleneck cost of at most $2$, since there is a
diversion of length $2$. Likewise, despite being a highly-weighted edge, we
can also remove $(v_{0},v_{1})$ for a bottleneck cost of at most $2$.

On the other hand, consider now $G_{2}$ in Figure 16. The edge $(w_{0},w_{1})$
has a high weight and the only diversion is via the black edges, of length
$10$. Deleting the edge $(w_{0},w_{1})$ incurs a bottleneck cost of $5$ since
it removes the sole feature. Moreover, deleting one of the smaller edges (for
example $(w_{2},w_{3})$) also incurs a bottleneck cost of $5$ since it deletes
the same feature.

###  5.6 Vertex deletion

######  Definition 5.29.

Given a weighted digraph $G=(V,E,w)$ and a vertex $v\in V$, 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}^{d}_{v}{G}}:=(V\setminus\\{v\\},E_{v},w_{v})$
where $E_{v}:=E\cap(V\setminus\\{v\\})\times(V\setminus\\{v\\})$ and $w_{v}$
is obtained by restricting $w$ to $E_{v}$.

Since a single vertex graph has trivial GrPPH the disjoint union decomposition
theorem (Theorem 4.18) allows us to delete isolated vertices.

######  Corollary 5.30.

Given a weighted digraph $G=(V,E,w)$ and an isolated vertex $v_{i}\in V$ (i.e.
$\mathcal{N}(v)=\emptyset$), then

$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}\cong\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{v_{i}}{G})}.$
(5.42)

However, in general, deleting a vertex from a digraph can drastically change
its topology. This follows immediately from Theorem 5.11 and Theorem 5.25
since a local vertex deletion stability theorem would imply a local edge
deletion stability theorem.

######  Corollary 5.31.

There exists no function $f:\bm{\mathrm{WDgr}}\to\mathbb{R}$ such that for any
digraph $G=(V,E,w)$ and any vertex $v\in V$ therein we have

$d_{B}\big{(}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)},\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{v}{G})}\big{)}\leq
f\big{(}\operatorname*{\mathcal{N\\!G}}(v;G)\big{)}.$ (5.43)

##  6 Examples

###  6.1 Iterated medial subdivision

In order to develop intuition for how the descriptor behaves under iterative
subdivision, we explicitly derive the limiting diagram for a DAG with exactly
one loop (shown in Figure 17). Certainly, the diagram contains exactly one
feature which is born at $t=0$. Intuitively, the death time corresponds to the
earliest time that a long square can appear between the source and sink nodes,
filling in the central hole.

$a$$b$$l_{1}$$l_{2}$ Figure 17: Illustration of the weighted digraph $G$,
considered in Proposition 6.1. The top path $p_{1}$ has length $l_{1}$ and the
bottom path $p_{2}$ has length $l_{2}$. The limiting death time of the sole
feature corresponds to the limiting value of the earliest time that a long
square appears of the form $av_{1}b-av_{2}b$ where $v_{1}$ is along $p_{1}$
and $v_{2}$ is along $p_{2}$ (as drawn in red) dashed lines).

######  Proposition 6.1.

Suppose $G\in\bm{\mathrm{WDag}}$ is the union two directed paths $p_{1},p_{2}$
from a source to a sink, with lengths $l_{1}\geq l_{2}$ respectively. Recall
the definition of iterated medial subdivision (Definition 5.13). Then

$\lim_{n\to\infty}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathrm{IMS}_{n}(G))}=\left\\{\\!\\!\left\\{\left[0,\frac{1}{2}l_{1}\right)\right\\}\\!\\!\right\\}$
(6.1)

###### Proof.

For brevity we denote $G_{n}:=\mathrm{IMS}_{n}(G)$. By Corollary 4.3, the
barcode $\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{n})}$ has exactly one
feature. Let $p_{i}^{(n)}$ denote the path $a\leadsto b$ in $G_{n}$ arising
from subdividing the edges of $p_{i}$. For each $n$, let $c^{(n)}$ denote the
simple undirected circuit in $G_{n}$ which follows $p_{1}^{(n)}$ and then
$p_{2}^{(n)}$ in reverse. Clearly $\\{\mathfrak{R}({c^{(n)}})\\}$ is a
persistence basis for $\prescript{g}{}{\mathcal{H}}_{1}(G_{n})$. Therefore, it
suffices to show
$\operatorname*{\mathcal{D}}(\mathfrak{R}({c^{(n)}}))\to\frac{1}{2}l_{1}$ as
$n\to\infty$. Fix some natural $n$.

Using Lemma 4.6 we see
$\operatorname*{\mathcal{D}}(\mathfrak{R}({c^{(n)}}))\leq\max(h_{1}^{(n)},h_{2}^{(n)})$
where

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

Note that $h_{1}^{(n)}\to\frac{1}{2}l_{1}$ and
$h_{2}^{(n)}\to\frac{1}{2}l_{2}$ and hence
$\max(h_{1}^{(n)},h_{2}^{(n)})\to\frac{1}{2}l_{1}$ as $n\to\infty$.

Next, we wish to show
$\operatorname*{\mathcal{D}}(\mathfrak{R}({c^{(n)}}))\geq\frac{1}{2}l_{1}$.
Choose arbitrary $t_{2}<\frac{1}{2}l_{1}$, then it suffices to show that
$\dim\prescript{g}{}{H}_{1}(G_{n},t_{2})\neq 0$. In order to do so, we claim
the inclusion chain map

${0}$${C_{1}(G_{n})}$${C_{0}(G_{n})}$${C_{2}(G_{n}^{t_{2}})}$${C_{1}(G_{n}\cup
G_{n}^{t_{2}})}$${C_{0}(G_{n}\cup
G_{n}^{t_{2}})}$$\scriptstyle{j_{2}}$$\scriptstyle{\prescript{g}{}{\partial}_{1}}$$\scriptstyle{j_{1}}$$\scriptstyle{j_{0}}$$\scriptstyle{\prescript{g}{}{\partial}_{2}}$$\scriptstyle{\prescript{g}{}{\partial}_{1}}$

induces an isomorphism on homology in degree $1$. It then follows that
$\dim\prescript{g}{}{H}_{1}(G_{n},t_{2})=1$ because the first homology of top
row is the real cycle space of $G_{n}$.

We define a chain map ${q}_{\\#}$ in the opposite direction to $q$. In degree
$2$, $q_{2}$ is the zero map and in degree $0$, $q_{0}$ is the identity map.
Finally in degree $1$, given $(i,j)\in C_{1}(G_{n}\cup G_{n}^{t_{2}})$, if
$(i,j)=(a,b)$ then let $p_{i,j}:=p_{2}$, otherwise let $p_{i,j}$ denote the
unique path $i\leadsto j$ in $G_{n}$ Then $q_{1}$ is given by
$q_{1}(ij):=\mathfrak{R}({p_{i,j}})$. This is a chain map because there is no
$2$-path $avb$ where $v$ is somewhere along $p_{1}^{(n)}$.

It is certainly the case that, at the level of chain maps,
$q_{1}j_{1}=\mathrm{id}$. Choose arbitrary $(i,j)\in C_{1}(G_{n}\cup
G_{n}^{t_{2}})$ and note that
$j_{1}q_{1}(ij)-(ij)=\mathfrak{R}({p_{i,j}})-ij$. By Lemma 4.1, there is some
$u_{i,j}\in C_{2}(G_{n}^{t_{2}})$ such that
$\prescript{g}{}{\partial}_{2}u_{i,j}=\mathfrak{R}({p_{i,j}})-ij$. Define
$P:C_{1}(G_{n}\cup G_{n}^{t_{2}})\to C_{2}(G_{n}^{t_{2}})$ by $ij\mapsto
u_{i,j}$. Then, by construction, we see
$j_{1}q_{1}-\mathrm{id}=\prescript{g}{}{\partial}_{2}P$. Hence, $j$ and $q$
are mutually inverse on homology in degree $1$.

To conclude, we have shown for each $n$,

$\frac{1}{2}l_{1}\leq\operatorname*{\mathcal{D}}(\mathfrak{R}({c^{(n)}}))\leq\max(h_{1}^{(n)},h_{2}^{(n)}).$
(6.3)

Taking the limit $n\to\infty$ finishes the proof. ∎

Note that description of Proposition 6.1 is not unique to this descriptor,
indeed the same result holds for the standard pipeline. As discussed in
Section 3.1, for the standard pipeline, as the weighted digraph is subdivided,
the birth times of all features tend to $0$. When the digraph is sufficiently
subdivided, all edges enter the filtration very early on and the effect of
adding the edges from $G$ at $t=0$ has negligible effect. Hence, in the
subdivision limit, the diagrams obtained from the two pipelines coincide.

######  Theorem 6.2.

Given $G\in\bm{\mathrm{WDgr}}$, let $\mathcal{H}_{1}$ denote the ‘standard
pipeline’ with $C=\Omega$ and $F=F_{d}$, as used in Example 3.6. Then

$\lim_{n\to\infty}\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(\mathrm{IMS}_{n}(G))}=\lim_{n\to\infty}\mathcal{B}{(}\mathcal{H}_{1}(\mathrm{IMS}_{n}(G))).$
(6.4)

###### Proof.

For brevity, we denote $G_{n}:=\mathrm{IMS}_{n}(G)$. Fix $\epsilon>0$ and
choose $N$ sufficiently large that for any $n\geq N$ we have $w(e)<\epsilon$
for all $e\in E(G_{n})$. For any $t\geq 0$, define

$\displaystyle i_{1}$ $\displaystyle:C_{1}(G_{n}^{t})\to C_{1}(G_{n}\cup
G_{n}^{t+\epsilon})$ $\displaystyle i_{2}$ $\displaystyle:C_{2}(G_{n}^{t})\to
C_{2}(G_{n}^{t+\epsilon})$

where each $i_{k}$ is taken from the chain map induced by the relevant
inclusion of digraphs. It can be easily checked that
$i_{1}\partial_{2}=\prescript{g}{}{\partial}_{2}i_{2}$ and hence $i_{1}$
induces a map on homology
$i_{\ast}:H_{1}(G_{n}^{t})\to\prescript{g}{}{H}_{1}(G_{n},{t+\epsilon})$.
Similarly, for any $t\geq 0$ define

$\displaystyle j_{1}$ $\displaystyle:C_{1}(G_{n}\cup G_{n}^{t})\to
C_{1}(G_{n}^{t+\epsilon})$ $\displaystyle j_{2}$
$\displaystyle:C_{2}(G_{n}^{t})\to C_{2}(G_{n}^{t+\epsilon})$

where each $j_{k}$ is likewise taken from the chain map induced by the
relevant inclusion of digraphs. Note, in particular, given an edge $e\in
E(G_{n})$, we know $d(\operatorname*{st}(e),\operatorname*{fn}(e))<\epsilon$
and hence $e\in E(G_{n}^{t+\epsilon})$. Again
$j_{1}\prescript{g}{}{\partial}_{2}=\partial_{2}j_{2}$ and hence $j_{1}$
induces a map on homology $j_{\ast}:\prescript{g}{}{H}_{1}(G,t)\to
H_{1}(G^{t+\epsilon})$.

Clearly $i_{\ast}\circ
j_{\ast}={\prescript{g}{}{\iota(t,t+2\epsilon)}}_{\ast}$ and $j_{\ast}\circ
i_{\ast}={\iota(t,t+2\epsilon)}_{\ast}$. Therefore, by the algebraic stability
theorem, we see

$d_{B}\left(\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{n})},\operatorname{Dgm}(\mathcal{H}_{1}(G_{n}))\right)\leq\epsilon$
(6.5)

for all $n\geq N$. ∎

###  6.2 Square motifs

$a$$b$$c$$d$$a$$b$$c$$d$$a$$b$$c$$d$$e$$a$$b$$c$$d$$e$$G_{1}$$G_{2}$$G_{3}$$G_{4}$$\left\\{\\!\\!\left\\{[0,1)\right\\}\\!\\!\right\\}$$\left\\{\\!\\!\left\\{[0,\infty)\right\\}\\!\\!\right\\}$$\left\\{\\!\\!\left\\{[0,1),[0,1)\right\\}\\!\\!\right\\}$$\left\\{\\!\\!\left\\{[0,\infty),[0,\infty)\right\\}\\!\\!\right\\}$
Figure 18: Interpreting $\prescript{g}{}{\mathcal{H}}_{1}(G)$ via differences
between directed paths in square motifs. Top row: name of weighted digraph;
middle row: diagram where all weights are $1$; bottom row: barcode of GrPPH.

######  Example 6.3.

Further to the interpretation developed in Proposition 6.1, consider the four
weighted digraphs in Figure 18. All edges are given unit weight and the
barcodes are indicated under each digraph. Homology representatives for each
of the features are given by

$\displaystyle ab+bd-cd-ac;$ $\displaystyle ab-db+dc-ac;$ $\displaystyle
ab+be-ce-ac\quad,\quad db+be-ce-dc;$ $\displaystyle ab-eb+ec-ac\quad,\quad db-
eb+ec-dc.$

In $G_{1}$, note that the flow starting at $a$ recombines at $d$ after flowing
for $t=2$ seconds. In contrast, the flow in $G_{2}$ splits from the sources
and then never recombines. This is reflected in the lifetime of the feature
changing from $[0,1)$ to $[0,\infty)$.

If we add additional edges to $G_{2}$ to recombine the flow at a new vertex
(as in $G_{3}$), we add an additional feature but all features now have finite
lifetime. Finally, reversing these additional edges (as in $G_{4}$) prevents
the flow from recombining again and the features return to lifetime
$[0,\infty)$.

This further emphasises the interpretation that features arise when flow is
split between two paths and the lifetime of the feature is related to the time
it takes for the flow to recombine.

###  6.3 Multiple paths

$a$$b$$v_{1}$$v_{2}$$v_{n-1}$$v_{n}$$a_{1}$$a_{2}$$a_{n-1}$$a_{n}$$b_{1}$$b_{2}$$b_{n-1}$$b_{n}$$\vdots$
Figure 19: A weighted digraph with many paths (of 2 edges each) from source to
sink for which we can compute
$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}$.

######  Example 6.4.

Consider Figure 19, in which there is a single source and a single sink but
multiple paths between. Define $\alpha_{i}:=\max(a_{i},b_{i})$ and assume that
$\alpha_{1}\leq\alpha_{2}\leq\dots\alpha_{n-1}\leq\alpha_{n}.$ Then, the
barcode is

$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}=\left\\{\\!\\!\left\\{[0,\alpha_{2}),[0,\alpha_{3}),\dots,[0,\alpha_{n-1}),[0,\alpha_{n})\right\\}\\!\\!\right\\}.$
(6.6)

A persistence basis for $\prescript{g}{}{\mathcal{H}}_{1}(G)$ is
$\\{c_{2},\dots,c_{n}\\}$ where $c_{i}:={av_{1}}+{v_{1}b}-{v_{i}b}-{av_{i}}$
and $\operatorname*{\mathcal{D}}(c_{i})=\alpha_{i}$.

###  6.4 Identical quasimetric

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$1$$1$$1$$1$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$1$$1$$1$$1$$2$$G_{1}$$G_{2}$
Figure 20: Two weighted digraphs with identical shortest-path quasimetric
network but differing GrPPH which can be explained by the difference in
circuit rank.

######  Example 6.5.

Finally, consider the two weighted digraphs illustrated in Figure 20. Since
they both have the same shortest-path quasimetric, they yield the same barcode
under the standard pipeline. More formally, $F_{d}(G_{1})=F_{d}(G_{2})$ and
hence
$\prescript{g}{}{\mathcal{H}}_{1}(G_{1})=\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$.
Moreover, $\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G_{1})}$ is empty
because the circuit $(v_{0},v_{1},v_{3},v_{2})$ is filled-in with a long
square as soon as it appears in the filtration. In contrast,

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

A persistence basis for $\prescript{g}{}{\mathcal{H}}_{1}(G_{1})$ is
$\\{v_{0}v_{1}+v_{1}v_{3}-(v_{0}v_{2}+v_{2}v_{3})\\}$ while a persistence
basis for $\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$ is
$\\{v_{0}v_{1}+v_{1}v_{3}-(v_{0}v_{2}+v_{2}v_{3})\quad,\quad
v_{0}v_{1}+v_{1}v_{3}-v_{0}v_{3}.\\}$ Note that at $t=1$ the two triangular
cycles becomes homologous in $\prescript{g}{}{\mathcal{H}}_{1}(G_{2})$ but are
still non-trivial, until they die at $t=2$.

##  Appendix A Grounded pipeline with the directed flag complex

We will now consider the pipeline developed in Section 3.2, changing the
choice of chain complex, $C$, to the directed flag complex.

######  Definition A.1.

Given a digraph $G=(V,E)$, a  directed $n$-clique is a $(n+1)$-tuple of
distinct vertices $v_{0}\dots v_{n}$ such that $i<j\implies v_{i}\to v_{j}$.

######  Definition A.2.

The  directed flag complex, $\operatorname{\mathrm{dFl}}(G)$, of a digraph
$G\in\bm{\mathrm{Dgr}}$ is the chain complex

${\cdots}$${\operatorname{\mathrm{dFl}}_{2}(G)}$${\operatorname{\mathrm{dFl}}_{1}(G)}$${\operatorname{\mathrm{dFl}}_{0}(G)}$${R}$${0}$$\scriptstyle{\partial_{3}}$$\scriptstyle{\partial_{2}}$$\scriptstyle{\partial_{1}}$$\scriptstyle{\partial_{0}}$

where $\operatorname{\mathrm{dFl}}_{k}(G)$ is the $\mathbb{R}$-vector space
freely generated by the $(k+1)$-cliques in $G$. The boundary map
$\partial_{k}$ is defined on the basis of cliques by

$\partial_{k}(v_{0}\dots
v_{k}):=\sum_{i=0}^{k}(-1)^{i}v_{0}\dots\hat{v}_{i}\dots v_{k}$ (A.1)

where $v_{0}\dots\hat{v}_{i}\dots v_{k}$ is the $k$-clique obtained from
$v_{0}\dots v_{k}$ by removing the vertex $v_{i}$.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$ Figure 21: A directed $4$-clique, giving rise to
a generator $v_{0}v_{1}v_{2}v_{3}\in F_{3}$.

The directed flag complex is an alternative chain complex for digraphs,
$\operatorname{\mathrm{dFl}}:\mathrm{Obj}(\bm{\mathrm{Dgr}})\to\mathrm{Obj}(\bm{\mathrm{Ch}})$,
which has seen more use in applications than path homology (see e.g. [34,
28]). We now repeat the investigation conducted in the main body of the paper,
replacing path homology with the directed flag complex. Henceforth, for the
rest of the paper, we fix $F$ to be the shortest-path filtration (see
Definition 3.5) and $C$ to be the directed flag complex,

$F=F_{d}\quad\text{ and }\quad C=\operatorname{\mathrm{dFl}}.$ (A.2)

Recalling that morphisms in $\bm{\mathrm{Dgr}}$ can collapse edges, we show
that $\operatorname{\mathrm{dFl}}$ cannot constitute a functor
$\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$. However, we do find a smaller category
$\bm{\mathrm{Tricol}}\bm{\mathrm{Dgr}}\subseteq\bm{\mathrm{Dgr}}$, containing
all digraphs, upon which $\operatorname{\mathrm{dFl}}$ is functorial. This
smaller category contains inclusions and thus we can apply the machinery
developed in Section 3.2 to obtain grounded persistent directed flag complex
homology (GrPdFlH),
$\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\bm{\mathrm{PersVec}})$.

For the remainder of the appendix, we review the results obtained for GrPPH,
in the main text and check which results apply to
$\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}$. Reassuringly, the results
on undirected circuit representatives and weight perturbation stability hold
in this setting. However, some stability results fail, most notably edge
subdivision, since they rely on morphisms outside of
$\bm{\mathrm{Tricol}}\bm{\mathrm{Dgr}}$. We summarise the known stability
results for the directed flag complex in Table 2.

Moreover, we find that the failure in functoriality
$\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$ leads to a failure in the wedge
decomposition theorem (Theorem 4.21). In Example A.13, we exhibit an explicit
example wherein deleting a small appendage edge can dramatically alter the
barcode, $\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(G)}$.
This behaviour is not present in GrPPH; we argue this is an instability which
complicates the interpretation of
$\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(G)}$.

###  A.1 Functoriality of the directed flag complex

$v_{1}$$v_{2}$$G$$v_{1}$$v_{2}$$v_{0}$$H$$v_{1}$$v_{2}$$G$$\mathbb{Z}$$0$$\mathbb{Z}$${f}_{\ast}$${g}_{\ast}$$\mathrm{id}$$f$$g$$\mathrm{id}$$H_{1}\circ\operatorname{\mathrm{dFl}}$
Figure 22: A commuting diagram in $\bm{\mathrm{Dgr}}$ which illustrates why
$\operatorname{\mathrm{dFl}}$ cannot be made into a functor
$\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$. For definitions of the digraph maps,
see the proof of Theorem A.3

######  Theorem A.3.

The directed flag complex cannot be made into a functor
$\operatorname{\mathrm{dFl}}:\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$.

###### Proof.

Suppose such a functor exists. Consider the three digraphs illustrated in
Figure 22. The digraph map $f$ is given by the obvious inclusion, whilst $g$
maps $v_{1}$ and $v_{2}$ to themselves and $v_{0}\mapsto v_{1}$. Note that
$g\circ f$ composes to the identity and hence the triangle of digraph maps
commutes. Applying $H_{1}\circ\operatorname{\mathrm{dFl}}$ to this diagram we
find that ${g}_{\ast}\circ{f}_{\ast}$ is the identity on $\mathbb{Z}$.
However, $H_{1}(\operatorname{\mathrm{dFl}}(H))$ is the trivial vector space
because $H$ has two ordered $2$-simplices which fit together to form a hemi-
sphere. The identity cannot factor through $0$ and hence we have a
contradiction. ∎

In order to see why functoriality fails, consider the following obvious guess
at the induced map.

######  Definition A.4.

Given a digraph map $f:G\to H$, the _induced map_
${f}_{\\#}:\operatorname{\mathrm{dFl}}_{k}(G)\to\operatorname{\mathrm{dFl}}_{k}(H)$
is given on each directed $k$-clique $v_{0}\dots v_{k}$ in $G$ by

${f}_{\\#}(v_{0}\dots v_{k}):=\begin{cases}f(v_{0})\dots f(v_{k})&\text{if all
the }f(v_{i})\text{ are distinct},\\\ 0&\text{otherwise}.\end{cases}$ (A.3)

We extend linearly to obtain a linear map
${f}_{\\#}:\operatorname{\mathrm{dFl}}_{k}(G)\to\operatorname{\mathrm{dFl}}_{k}(H)$.

This does not necessarily constitute a chain map
$\operatorname{\mathrm{dFl}}(G)\to\operatorname{\mathrm{dFl}}(H)$. To see why,
consider the map $g$ defined in the proof of Theorem A.3 and illustrated in
Figure 22. The directed clique $(v_{0},v_{2},v_{1})$ is mapped to
$(v_{1},v_{2},v_{1})$ which is a double edge and not a clique; this leads to a
boundary being mapped to a non-trivial homological cycle. However, such
mappings (sending directed triangles to double edges) are the only obstruction
to functoriality.

######  Definition A.5.

  1. (a)

A digraph map $f:G\to H$ is called  triangle-collapsing if whenever $ijk$ is a
directed $2$-clique and $f(i)=f(k)$ then $f(j)=f(i)=f(k)$.

  2. (b)

We denote the category of all digraphs with triangle-collapsing digraph maps
as
${\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>
######  Proposition A.6.

The directed flag complex with induced maps as in formula (A.3) is a functor
$\operatorname{\mathrm{dFl}}:\bm{\mathrm{Tricol}}\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$.

###### Proof.

We first note that formula (A.3) certainly respects the composition and
identity axioms required for functoriality; it remains only to confirm that
${f}_{\\#}$ is a chain map
$\operatorname{\mathrm{dFl}}(G)\to\operatorname{\mathrm{dFl}}(H)$. That is, we
need to check ${f}_{\\#}$ commutes with the boundary map. We verify this on
the basis of $\operatorname{\mathrm{dFl}}_{k}(G)$.

Choose some directed $(k+1)$-clique $(v_{0},\dots,v_{k})$ in $G$. If all the
$f(v_{i})$ are distinct then clearly ${f}_{\\#}\partial_{n}(v_{0}\dots
v_{k})=\partial_{n}{f}_{\\#}(v_{0}\dots v_{k})$. Otherwise
$f(v_{i_{1}})=f(v_{i_{2}})$ for some $i_{1}<i_{2}$. Then

$\displaystyle\partial_{k}{f}_{\\#}(v_{0}\dots v_{k})$
$\displaystyle=\partial_{k}(0)=0$ (A.4)
$\displaystyle{f}_{\\#}\partial_{k}(v_{0}\dots v_{k})$
$\displaystyle=(-1)^{i_{1}}{f}_{\\#}\left[v_{0}\dots\hat{v}_{i_{1}}\dots
v_{k}\right]+(-1)^{i_{2}}{f}_{\\#}\left[v_{0}\dots\hat{v}_{i_{2}}\dots
v_{k}\right]$ (A.5)

If $i_{2}=i_{1}+1$ then the two terms of (A.5) are equal but opposite sign so
${f}_{\\#}\partial_{k}(v_{0}\dots v_{k})=0$. Else there is some $j$ such that
$i_{1}<j<i_{2}$. Since $v_{0}\dots v_{k}$ is a clique,
$v_{i_{1}}v_{j}v_{i_{2}}$ is also a clique. Then the triangle-collapsing
condition requires that $f(v_{j})=f(v_{i_{1}})=f(v_{i_{2}})$ and hence both
summands in (A.5) are $0$. ∎

######  Remark A.7.

If $f:G\to H$ is an inclusion map, injective as a vertex map or $H$ is an
oriented graph then $f$ is triangle-collapsing.

###  A.2 Grounded pipeline

An immediate corollary of Proposition A.6 is that
$\operatorname{\mathrm{dFl}}$ is a functor
$\bm{\mathrm{Incl}}\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$. This was the minimum
condition that we needed to define the grounded pipeline (see Lemma 3.9), and
so we get a map on objects

$\prescript{g}{}{C}_{F}:\mathrm{Obj}(\bm{\mathrm{WDgr}})\to\mathrm{Obj}(\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}).$
(A.6)

Recall that, since $F=F_{d}$ and $C=\operatorname{\mathrm{dFl}}$, at
$t\in\mathbb{R}$ the chain complex $\prescript{g}{}{C}_{F}(G,t)$ is

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

However since $\operatorname{\mathrm{dFl}}$ is not a functor
$\bm{\mathrm{Dgr}}\to\bm{\mathrm{Ch}}$, we cannot apply Theorem 3.12 to obtain
a functor
$\prescript{g}{}{C}_{F}:\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}$.
Instead, we must restrict the morphisms on $\bm{\mathrm{WDgr}}$ so that they
induce triangle-collapsing morphisms between the relevant digraphs at every
step of the persistent chain complex.

######  Definition A.8.

  1. (a)

Given two weighted digraphs $G,H$, a vertex map $f:V(G)\to V(H)$ is called
path-collapsing if whenever $f(i)=f(k)$ and there is some vertex $j$ with
paths $i\leadsto j\leadsto k$ then $f(i)=f(j)=f(k)$.

  2. (b)

We 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<EMAIL_ADDRESS>denote the category of weighted digraphs where morphisms are path-collapsing,
contracting digraph maps.

######  Remark A.9.

Both $\bm{\mathrm{Incl}}\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}$ and
$\bm{\mathrm{Cont}}\bm{\mathrm{WDag}}$ are subcategories of
$\bm{\mathrm{Pathcol}}\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}$.

One can check that if $f:G\to H$ is path-collapsing and contracting, then the
underlying vertex map induces triangle-collapsing digraph maps $G\to H$,
$G^{t}\to H^{t}$ and $G\cup G^{t}\to H\cup H^{t}$ for every $t$. Then, using
the functoriality established in Proposition A.6, the proof of Theorem 3.12
goes through to show the following.

######  Theorem A.10.

Fixing $F=F_{d}$ and $C=\operatorname{\mathrm{dFl}}$, $\prescript{g}{}{C}_{F}$
is a functor
$\prescript{g}{}{C}_{F}:\bm{\mathrm{Pathcol}}\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}\to\textbf{[}\bm{\mathrm{R}},\,\bm{\mathrm{Ch}}\textbf{]}$.

######  Definition/Theorem A.11.

Grounded persistent directed flag homology (GrPdFlH) 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}{}{\widetriangle{\mathcal{H}}}_{1}}:=\textbf{[}\bm{\mathrm{R}},\,H_{1}\textbf{]}\circ\prescript{g}{}{C}_{F}:\bm{\mathrm{Pathcol}}\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}\to\bm{\mathrm{PersVec}}.$
(A.7)

We reuse the notation of Definition 3.16, to denote the space of grounded
cycles, boundaries and homology in this directed flag complex setting.

###  A.3 Interpretation

Section 4.1 established some basic properties of the descriptor. In
particular, all features are born at $t=0$ and the number of features in the
barcode, $\\#\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(G)}$,
is the circuit rank of the underlying, undirected graph, $\mathcal{U}(G)$.
These results do not rely on the functoriality of $\prescript{g}{}{C}_{F}$.
Indeed, they only require that there are generators corresponding to directed
triangles in $C_{2}(G)$, which is certainly the case for
$C=\operatorname{\mathrm{dFl}}$. Therefore, all results of Section 4.1 apply
to the directed flag complex.

In contrast, Lemma 4.6, bounding the death-time of a given circuit, requires
the existence of generators corresponding to long squares. Therefore the proof
does not work in the directed flag setting. However, we can prove the
following, slightly weaker bound.

######  Lemma A.12.

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\\}.$ (A.8)

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

###### Proof.

The proof is similar to that of Lemma 4.6. However, since there are no
generators corresponding to long squares, we need $T$ to be sufficiently large
that the edge $(a,b)$ appears in $G^{T}$. Therefore $av_{1}b$ and $av_{2}b$
are both generators of $\prescript{g}{}{C}_{2}(G,T)$ and so certainly
$av_{1}b-av_{2}b\in\prescript{g}{}{C}_{2}(G,T)$. ∎

Theorem 4.10, which guarantees the existence of a persistence basis of
undirected circuit, also applies to the directed flag complex. The proof is
unchanged except that each of the generators $u_{1},\dots,u_{n}$ must be
directed triangles since these are the generators of $C_{2}(G^{t})$.

Finally, the disjoint union decomposition theorem (Theorem 4.18) applies
unchanged to the directed flag complex. Unfortunately, the proof of wedge the
wedge decomposition theorem (Theorem 4.21) fails in the directed flag case,
because the contractions $f_{i}$ are not necessarily path-collapsing. However,
if we restrict to $G\in\bm{\mathrm{WDag}}$ then the proof goes through
unchanged because
$\bm{\mathrm{Cont}}\bm{\mathrm{WDag}}\subseteq\bm{\mathrm{Pathcol}}\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}$.

Moreover, it is not just the proof of Theorem 4.21 which fails but indeed the
statement itself. Note that, if Theorem 4.21 were to hold in the directed flag
case then Corollary 5.22 (on stability to separating edge deletion) would hold
automatically too.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{0}$$10$$10$$10$$10$$1$$G$ Figure 23:  An
example weighted digraph for which the wedge decomposition result fails, when
using the directed flag complex.

######  Example A.13.

Consider Figure 23 and denote $e:=(v_{0},v_{1})$. Note that $e$ is a
separating edge and hence, by Corollary 5.22,
$\prescript{g}{}{\mathcal{H}}_{1}(G)\cong\prescript{g}{}{\mathcal{H}}_{1}(\mathbb{O}^{d}_{e}{G})$
and we can compute
$\mathcal{B}{\prescript{g}{}{\mathcal{H}}_{1}(G)}=\left\\{\\!\\!\left\\{[0,20)\right\\}\\!\\!\right\\}$.
However, using the directed flag complex we observe

$\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(G)}=\left\\{\\!\\!\left\\{[0,21)\right\\}\\!\\!\right\\}\quad\text{
but
}\quad\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(\mathbb{O}^{d}_{e}{G})}=\left\\{\\!\\!\left\\{[0,30)\right\\}\\!\\!\right\\}.$
(A.9)

The sole cycle in $G$ dies at $t=21$ because

$\prescript{g}{}{\partial}_{2}(v_{1}v_{2}v_{3}+v_{3}v_{4}v_{1}+v_{0}v_{1}v_{3}+v_{0}v_{3}v_{1})=v_{1}v_{2}+v_{2}v_{3}+v_{3}v_{4}+v_{4}v_{1}$
(A.10)

and the corresponding directed triangles appear in $G^{21}$.

This example illustrates an instability of
$\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}$ which is not present in
$\prescript{g}{}{\mathcal{H}}_{1}$. Moreover, since $e$ is not involved in any
simple undirected circuits, we would not expect its presence to affect
$\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(G)$; this instability
complicates the interpretation of
$\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}$.

###  A.4 Stability analysis

The key results used in the proof of most stability theorems were Lemmas 5.3
and 5.4, in which a $\delta$-shifting vertex map $f:V(G)\to V(H)$ was used to
construct part of an interleaving. In order to repeat this construction in the
directed flag setting, we need to ensure that $f$ is path-collapsing.

######  Lemma A.14.

Any $\delta$-shifting, path-collapsing 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].$
(A.11)

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

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

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

######  Lemma A.15.

A $\delta$-shifting, path-collapsing vertex map is a
$\delta^{\prime}$-shifting, path-collapsing 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)}_{\\#}.$
(A.13)

With these lemmas, many theorems from Section 5 go through unchanged ether
because they only involve $\delta$-shifting maps which are inclusions or
because they use explicit counter-examples which have the same barcodes in
this new setting. For the other results, since
$\bm{\mathrm{Cont}}\bm{\mathrm{WDag}}\subseteq\bm{\mathrm{Pathcol}}\bm{\mathrm{Cont}}\bm{\mathrm{WDgr}}$,
the proofs work unchanged so long as we restrict to $G\in\bm{\mathrm{WDag}}$.
To summarise this, we present Table 2, which is a reproduction of Table 1 with
additional annotations. Of particular note, we emphasise that weight
perturbation stability holds unrestricted but edge subdivision stability (and
hence convergence under iterated medial subdivision) only holds if
$G\in\bm{\mathrm{WDag}}$.

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 2:  Stability and instability theorems for
$\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}$, under various digraph
operations. $\blacklozenge$ Denotes a theorem which only applies to a subset
of such operations. $\checkmark$ Denotes a theorem which applies to the
directed flag complex unrestricted. $\restriction$ Denotes a theorem which
applies to the directed flag complex after restricting to
$G\in\bm{\mathrm{WDag}}$.

###  A.5 Iterated medial subdivision

Recall Proposition 6.1, in which we found the limiting barcode of a simple
cycle graph, under iterated medial subdivision. This limiting value does not
hold in the directed flag setting.

$v_{0}$$v_{1}$$v_{2}$$v_{0}$$v_{1}$$v_{2}$$2$$2$$3$$5$$5$$2$$G$$H$ Figure 24:
Two weighted digraphs, of the form considered by Proposition 6.1, illustrating
that the behaviour of
$\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(G)}$ under
iterated subdivision is not as symmetric.

######  Example A.16.

Consider the two digraphs pictured in Figure 24. In $G$, the two paths have
lengths $l_{G,1}=4>3=l_{G,2}$, while in $H$ the two paths have lengths
$l_{H,1}=10>2=l_{H,2}$. When using directed flag complex,

$\displaystyle\lim_{n\to\infty}\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(G_{n})}$
$\displaystyle=\left\\{\\!\\!\left\\{[0,3)\right\\}\\!\\!\right\\}=\left\\{\\!\\!\left\\{[0,l_{G,2})\right\\}\\!\\!\right\\},$
(A.14)
$\displaystyle\lim_{n\to\infty}\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(H_{n})}$
$\displaystyle=\left\\{\\!\\!\left\\{[0,5)\right\\}\\!\\!\right\\}=\left\\{\\!\\!\left\\{[0,1/2\cdot
l_{H,1})\right\\}\\!\\!\right\\}.$ (A.15)

The reason this limiting value differs from path homology is because edge
$(v_{0},v_{2})$ must appear in $G^{t}$ before the sole feature can die.

By a similar method to Proposition 6.1, one can show the following.

######  Proposition A.17.

Suppose $G\in\bm{\mathrm{WDag}}$ is the union two directed paths $p_{1},p_{2}$
from a source to a sink, with lengths $l_{1}\geq l_{2}$ respectively. Recall
the definition of iterated medial subdivision (Definition 5.13). Then

$\lim_{n\to\infty}\mathcal{B}{\prescript{g}{}{\widetriangle{\mathcal{H}}}_{1}(\mathrm{IMS}_{n}(G))}=\left\\{\\!\\!\left\\{\left[0,\max\left(\frac{1}{2}l_{1},l_{2}\right)\right)\right\\}\\!\\!\right\\}$
(A.16)

The asymmetry in this limiting descriptor arises from asymmetry in the path
lengths of the directed triangle motif, in contract to the long square motif.
In contrast, path homology yields a simpler interpretation; the size of the
limiting feature is directly proportional to the length of the longer path.

## References

  * [1] Ulrich Bauer and Michael Lesnick  “Induced matchings and the algebraic stability of persistence barcodes”  In _Journal of Computational Geometry_ 6.2, 2015, pp. 162–191  DOI: 10.20382/jocg.v6i2a9
  * [2] Katherine Benjamin et al.  “Homology of homologous knotted proteins”, 2022  arXiv:2201.07709 [math.AT]
  * [3] Alyson Bittner et al.  “Comparing directed and weighted road maps”  In _Research in Computational Topology_ Springer, 2018, pp. 57–70
  * [4] Emma L. Brown et al.  “Quantification of vascular networks in photoacoustic mesoscopy”  In _Photoacoustics_ 26, 2022, pp. 100357  DOI: 10.1016/j.pacs.2022.100357
  * [5] Peter Bubenik and Jonathan A. Scott  “Categorification of Persistent Homology”  In _Discrete & Computational Geometry_ 51.3, 2014, pp. 600–627  DOI: 10.1007/s00454-014-9573-x
  * [6] Luigi Caputi, Anna Pidnebesna and Jaroslav Hlinka  “Promises and pitfalls of topological data analysis for brain connectivity analysis”  In _NeuroImage_ 238, 2021, pp. 118245  DOI: 10.1016/j.neuroimage.2021.118245
  * [7] Luigi Caputi and Henri Riihimäki  “Hochschild homology, and a persistent approach via connectivity digraphs”, 2022  arXiv:2204.00462 [math.AT]
  * [8] Thomas Chaplin  “Flagser (fork) and GrPdFlH wrapper”, 2022  URL: https://github.com/tomchaplin/flagser
  * [9] Frédéric Chazal and Bertrand Michel  “An Introduction to Topological Data Analysis: Fundamental and Practical Aspects for Data Scientists”  In _Frontiers in Artificial Intelligence_ 4, 2021  URL: https://www.frontiersin.org/article/10.3389/frai.2021.667963
  * [10] Frédéric Chazal, Vin Silva, Marc Glisse and Steve Oudot  “The Structure and Stability of Persistence Modules”  Cham: Springer International Publishing, 2016  DOI: 10.1007/978-3-319-42545-0˙2
  * [11] Mauricio Che et al.  “Basic Metric Geometry of the Bottleneck Distance”, 2022  arXiv:2205.09718 [math.MG]
  * [12] Samir Chowdhury and Facundo Mémoli  “Persistent Path Homology of Directed Networks”  In _Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2018, pp. 1152–1169  DOI: 10.1137/1.9781611975031.75
  * [13] David Cohen-Steiner, Herbert Edelsbrunner and John Harer  “Stability of persistence diagrams”  In _Proceedings of the twenty-first annual symposium on Computational geometry_ , 2005, pp. 263–271
  * [14] David Cohen-Steiner, Herbert Edelsbrunner, John Harer and Yuriy Mileyko  “Lipschitz functions have Lp-stable persistence”  In _Foundations of computational mathematics_ 10.2 Springer, 2010, pp. 127–139
  * [15] William Crawley-Boevey  “Decomposition of pointwise finite-dimensional persistence modules”  In _Journal of Algebra and Its Applications_ 14.05, 2015, pp. 1550066  DOI: 10.1142/S0219498815500668
  * [16] Tamal K. Dey, Tianqi Li and Yusu Wang  “An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology”  In _36th International Symposium on Computational Geometry (SoCG 2020)_ 164, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 36:1–36:15  DOI: 10.4230/LIPIcs.SoCG.2020.36
  * [17] Herbert Edelsbrunner and John Harer  “Persistent homology-a survey”  In _Contemporary mathematics_ 453 Providence, RI: American Mathematical Society, 2008, pp. 257–282
  * [18] Xinbo Gao, Bing Xiao, Dacheng Tao and Xuelong Li  “A survey of graph edit distance”  In _Pattern Analysis and Applications_ 13.1, 2010, pp. 113–129  DOI: 10.1007/s10044-008-0141-y
  * [19] Barbara Giunti  “TDA-Applications” Accessed: 2022-09-07, https://www.zotero.org/groups/2425412/tda-applications
  * [20] Christian Goodbrake et al.  “Brain Chains as Topological Signatures for Alzheimer’s Disease”, 2022  arXiv:2208.12748 [q-bio.NC]
  * [21] Dejan Govc, Ran Levi and Jason P. Smith  “Complexes of tournaments, directionality filtrations and persistent homology”  In _Journal of Applied and Computational Topology_ 5.2, 2021, pp. 313–337  DOI: 10.1007/s41468-021-00068-0
  * [22] A.. Grigor’yan, Yong Lin, Yu.. Muranov and Shing-Tung Yau  “Path Complexes and their Homologies”  In _Journal of Mathematical Sciences_ 248.5, 2020, pp. 564–599  DOI: 10.1007/s10958-020-04897-9
  * [23] Alexander Grigor’yan, Yong Lin, Yuri Muranov and Shing-Tung Yau  “Homologies of path complexes and digraphs”, 2012  arXiv:1207.2834 [math.CO]
  * [24] Alexander Grigor’yan, Yong Lin, Yuri Muranov and Shing-Tung Yau  “Homotopy theory for digraphs”  In _Pure and Applied Mathematics Quarterly_ 10.4, 2015, pp. 619–674  DOI: 10.4310/PAMQ.2014.v10.n4.a2
  * [25] Mohd Sabri Ismail et al.  “Early warning signals of financial crises using persistent homology”  In _Physica A: Statistical Mechanics and its Applications_ 586, 2022, pp. 126459  DOI: 10.1016/j.physa.2021.126459
  * [26] Lu Li et al.  “Minimal Cycle Representatives in Persistent Homology using Linear Programming: an Empirical Study with User’s Guide”  In _Frontiers in artificial intelligence_ 4 Frontiers, 2021, pp. 73
  * [27] Yong Lin, Shiquan Ren, Chong Wang and Jie Wu  “Weighted Path homology of Weighted Digraphs and Persistence”, 2019  arXiv:1910.09891 [math.AT]
  * [28] Daniel Lütgehetmann, Dejan Govc, Jason P. Smith and Ran Levi  “Computing Persistent Homology of Directed Flag Complexes”  In _Algorithms_ 13.1, 2020  DOI: 10.3390/a13010019
  * [29] Paolo Masulli and Alessandro E.. Villa  “The topology of the directed clique complex as a network invariant”  In _SpringerPlus_ 5.1, 2016, pp. 388  DOI: 10.1186/s40064-016-2022-y
  * [30] John D. Medaglia  “Graph Theoretic Analysis of Resting State Functional MR Imaging.”  In _Neuroimaging clinics of North America_ 27, 2017, pp. 593–607
  * [31] Vidit Nanda  “Computational Algebraic Topology - Lecture Notes”  March, 2021  URL: https://people.maths.ox.ac.uk/nanda/cat/TDANotes.pdf
  * [32] John T. Nardini et al.  “Topological data analysis distinguishes parameter regimes in the Anderson-Chaplain model of angiogenesis”  In _PLOS Computational Biology_ 17.6 Public Library of Science, 2021, pp. 1–29  DOI: 10.1371/journal.pcbi.1009094
  * [33] Nina Otter et al.  “A roadmap for the computation of persistent homology.”  In _EPJ data science_ 6, 2017, pp. 17
  * [34] Michael W Reimann et al.  “Cliques of neurons bound into cavities provide a missing link between structure and function”  In _Frontiers in computational neuroscience_ 11 Frontiers, 2017, pp. 48  DOI: 10.3389/fncom.2017.00048
  * [35] Ann E. Sizemore et al.  “Cliques and cavities in the human connectome”  In _Journal of Computational Neuroscience_ 44.1, 2018, pp. 115–145  DOI: 10.1007/s10827-017-0672-6
  * [36] Bernadette J. Stolz et al.  “Multiscale topology characterizes dynamic tumor vascular networks”  In _Science Advances_ 8.23, 2022, pp. eabm2456  DOI: 10.1126/sciadv.abm2456
  * [37] Paul W. Sweeney, Angela d’Esposito, Simon Walker-Samuel and Rebecca J. Shipley  “Modelling the transport of fluid through heterogeneous, whole tumours in silico”  In _PLOS Computational Biology_ 15.6 Public Library of Science, 2019, pp. e1006751  DOI: 10.1371/journal.pcbi.1006751
  * [38] Jiacheng Xing, Jiaying Jia, Xin Wu and Liqun Kuang  “A Spatiotemporal Brain Network Analysis of Alzheimer’s Disease Based on Persistent Homology.”  In _Frontiers in aging neuroscience_ 14, 2022, pp. 788571