{'fraction_non_alphanumeric': 0.06313677811550152, 'fraction_numerical': 0.015586626139817629, 'mean_word_length': 3.516307928838129, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 62, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Grounded persistent path homology: a stable, topological descriptor for weighted digraphs

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.


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 I : WDgr → 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 I is well understood we may be able to explain why the weighted digraphs differ. In order to determine desirable characteristics of such an I, consider the examples shown in Figure 1, in which edge weights correspond to length as drawn. 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(I (G 1 ), 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 arXiv:2210.11274v1 [math.AT] 20 Oct 2022 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(I (G 1 ), I(G 4 )) should be small and the difference between I(G 1 ) and 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 I is continuous (or better yet Lipschitz), with respect to a choice of metric on 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(I (G), (I(OG)), over a range of graph operations, O : WDgr → WDgr.
Finally, in many applications (particularly in biology), it is important that any invariant 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 (a) distinguishes graphs with different flow profiles due to directionality; (b) can detect and describe features (i.e. loops) across a range of scales; (c) is stable to reasonable perturbations and converges under iterated subdivision; and (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 Chowdhury and Mémoli [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).

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 ContWDgr 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 g H 1 : ContWDgr → PersVec (1.1) where 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 g H 1 (G); the following theorem summarises our findings. Theorem 1.1. Given a weighted digraph G ∈ WDgr, denote the underlying undirected graph by U (G).
(a) All features in g H 1 (G) are born at t = 0; (b) g H 1 (G) at time t = 0 is the (real) cycle space of U (G); and moreover (c) there is a choice of circuits in U (G) whose homology classes generate g 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 g H 1 (G) to assign a 'scale' to any circuit in 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 ∈ WDgr, if G decomposes as a wedge decomposition G = G 1 ∨v G 2 or a disjoint union G = G 1 G 2 then g H 1 (G) ∼ = g H 1 (G 1 ) ⊕ g H 1 (G 2 ). (1.2) In Section 5 we investigate the stability of g 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.

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 Chowdhury and Mémoli [12]; a more efficient algorithm for computing PPH in degree 1 was later proposed by

Directed graphs
Definition 2.7. (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 × V \ ∆ V where We call elements of ∆ V self-loops. (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 , . . . , v n } such that (v i , v j ) ∈ E =⇒ i < j. (c) An oriented graph is a simple digraph G = (V, E) with no double edges, i.e. (i, j) ∈ E =⇒ (j, i) ∈ E. (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 → R >0 is a positively-valued function on the edges. (e) An undirected graph is a tuple G = (V, E) where E is a multiset of 2-element subsets of V.
For an edge e = (i, j) ∈ E, we write st(e) := i and fn(e) := j, and say that i and j are incident to e. (c) For an edge e = (i, j) ∈ E, we write w(i, j) := w(e). (d) We write i → j to mean there is an edge (i, j) ∈ E. (2.8) and the neighbourhood graph, NG(v; G), is the induced subgraph on N (v). Where G is clear from context, we omit it from notation.
that τ, e are incident to a common vertex} (2.9) and the neighbourhood graph, NG(F; G), is the induced subgraph on N (F; G). Where G is clear from context, we omit it from notation.
(e) For two vertices a, b ∈ V, a (directed) trail from a to b is an alternating sequence of vertices, v i ∈ V, and forward edges, e i ∈ E, such that e i = (v i−1 , v i ). We write that p is a trail a b. In a simple digraph, the e i uniquely determine the v i (and vice versa) so we occasionally omit one from the notation. (f) A trail which does not repeat vertices is a path. (g) An undirected circuit is an alternating sequence of vertices, v i ∈ V, and edges, e i ∈ E, Given an undirected circuit p, as above, if v 0 , . . . , v k−1 are all distinct then we say p is simple.
(a) Given a trail p, the length of p is defined as We denote the set of all paths i j by P (i, j).
Definition 2.11. For a weighted digraph G, the shortest-path quasimetric d : There is a notion of morphisms between (weighted) digraphs.
Given a vertex map f : V(G) → V(H) satisfying condition (2.14), we say f induces a digraph map G → H.
where d G and d H are the shortest-path quasimetrics on G and H respectively.
Given a path p = (v 0 , e 1 , . . . , e k , v k ) and a digraph map f : G → H, the image of p is the path, f (p), obtained from Remark 2.14. Suppose f : G → H is a weighted digraph such that w(H)( f (e)) ≤ w(G)(e) for every edge e ∈ E(G) with f (e) ∈ ∆ V(H) . Then for any path p : i j in G, f (p) is a path f (i) f (j) in H and len( f (p)) ≤ len(p). Hence, f is certainly a contraction. However, this is not a necessary contraction since the shortest path joining f (i) f (j) need not be the image of the shortest path joining i j.
Given these ways of mapping between (weighted) digraphs, a number of categories naturally arise.

Path homology
Path homology is a homology theory for directed graph, which was first introduced by Grigor'yan et al. [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 vertexweighted 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: (a) An elementary p-path is any sequence v 0 . . . v p of (p Definition 2.17. We freely generate R-modules from these sequences of vertices, for each p ≥ 0.
Definition 2.18. Given p ≥ 0, the non-regular boundary map ∂ N p : Λ p → Λ p−1 is given on the standard basis by Definition 2.19. Since R p ⊆ Λ p , let π : Λ p → R p denote the projection map onto R p . The regular boundary map ∂ p : R p → R p−1 is given by This boundary operator does not pass down to a boundary operator between the A p so we must define the following sub-modules.
Definition 2.20. The space of ∂-invariant p-paths is The homology of the regular path complex is the regular path homology of G, the k th homology group is The k th Betti number is β k := rank H k .
given on the standard basis by Hence Ω is a functor Dgr → 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. ([23, § 3.3]). For any simple digraph G = (V, E), Ω 0 (G) is isomorphic to the R-module freely generated by the vertices and Ω 1 (G) is isomorphic to the R-module freely generated by the edges, i.e.

Proposition 2.25
Notation 2.26. Note that an edge e = (a, b) ∈ E gives rise to an allowed 1-path ab ∈ A 1 (G). Moreover, ab ∈ Ω 1 (G). For ease of notation, given an edge e ∈ E, we will also use e = ab ∈ Ω 1 (G) to refer to the generator in Ω 1 (G).
Since Ω 1 is generated by edges in G, any trail p has a representative.
Notation 2.27. Given a directed trail p = (e 1 , . . . , e k ) in a digraph G, the representative of p is Likewise, there is a representative for any undirected circuit.
Notation 2.28. Given an undirected circuit p = (v 0 = a, e 1 , v 1 , . . . , e k , v k = a) in a digraph G, the representative of p is Remark 2.29. The representative of a circuit p, does not depend on the starting point, but if p traverses the circuit in the opposite direction then R(p ) = −R(p).  . Let G be a finite, simple digraph and R = R or Z. Any ω ∈ Ω 2 (G; R) can be written as a linear combination of ∂-invariant 2-paths of the following three types: First note that all of the elements identified in Proposition 2.30 are elements of Ω 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 2d, we see (2.29) Removing some long squares to account for these linear relations, we can obtain a basis of Ω 2 (G; R).

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. (ii) there are finitely many t ∈ R such that there is no > 0 such that M(t − ≤ t + ) is an isomorphism.
(e) For an interval I ⊆ R, we define the corresponding interval, P(I) ∈ PersVec, in which the vector spaces are and P(I)(s ≤ t) is the identity if s, t ∈ I and the trivial map otherwise. (f) Given M, N ∈ PersVec, their direct sum M ⊕ N ∈ PersVec is given pointwise by (2.32) whenever s ≤ t. We say φ is an isomorphism if each φ t is an isomorphism of vector spaces.
If an isomorphism M → N exists, we write M ∼ = 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. 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. ([17]). Given two multisets D 1 , D 2 ⊆ R 2 , the bottleneck distance is
for each s ≤ 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. Finally, when a persistent vector space is tame, there are finitely many critical values t 0 < · · · < t k such that if t i−1 < s ≤ t < t i then M(s ≤ t) is an isomorphism [10]. Hence, all information of the persistent vector space is contained within the maps M(t i−1 ≤ t i ) for i = 1, . . . , k. In particular, any interval in the barcode must have its endpoints at one of the critical values (or ±∞). In these scenarios, it suffices to consider M as a functor [k] → Vec, where [k] is the sub-poset of R consisting of the integers 0, . . . , k [31].

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.

Standard pipeline
A typical TDA pipeline for weighted digraphs consists of three ingredients: 1. a map F : Obj(WDgr) → Obj([R, Dgr]), which assigns a filtration of digraphs to every weighted digraph; 2. a chain complex functor C : Dgr → Ch which maps each digraph to a chain complex and induces chain map for every digraph map; and finally 3. a choice of homology functor H k : Ch → Vec in some degree k. These components can then be combined into the following pipeline.   Mor(WDgr Proof. Given f ∈ Mor WDgr F (G, H), since f is F-compatible, the underlying vertex map induces digraph maps f : F t G → F t H for every t ∈ R. Given s ≤ t, both F(G)(s ≤ t) and F(H)(s ≤ t) are digraph maps induced by the inclusion vertex map. Hence the following square of morphisms in Dgr commutes.
Hence f induces a natural transformation between F(G) and F(H). Moreover, since each f : F t G → F t H is fully determined by the underlying vertex map V(G) → 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 WDgr F → [R, Dgr] and hence H k is a functor WDgr F → [R, Vec], 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.
and d is the shortest-path quasimetric on G. For s ≤ t, the digraph map G s → G t is induced by the identity vertex map id V . Example 3.6. Choosing F = F d as above and C to be the regular path complex, we obtain a functor H k : WDgr F → [R, Vec]. 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 This example highlights three key issues with this pipeline: (a) the number of features in the barcode changes upon subdivision; (b) loops bounded by triangles or long squares are 'killed' as soon as they are born; and (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.

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 ∈ R. The main distinction is that we do not factor through a filtration functor F. Instead, we use F and C ∈ [Dgr, Ch] to construct a new functor g C F : In order to define the map on objects, we only need a weaker condition on C.
Definition 3.7. Given a filtration functor F : WDgr F → [R, Dgr], a functor C : InclDgr → Ch, G ∈ WDgr and t ∈ R, the chain complex g C • (G, t; F) is the top row of the following diagram.
We denote the chain groups as g C k (G, t; F) and the boundary maps as g ∂ t k . When F and t are clear from context, we omit them from notation We use the prescript g 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.
and hence C • (G, t; F) defines a chain complex. Lemma 3.9. Given a filtration functor F : WDgr F → [R, Dgr] and a functor C : Proof. For each s ≤ t we require chain maps g ι(s, t) # : g C • (G, s) → g C • (G, t) which satisfy the usual functorial axioms in t. First note that ι(s, t) : F s G → F t G is induced by the inclusion vertex map, which is a restriction of the identity vertex map V(G) → V(G). Hence this identity vertex map also yields a digraph map G ∪ F s G → G ∪ F t G, which we also denote ι(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.
Squares A and B and D commute because all vertical maps are components of the same chain map -either ι(s, t) # : . Then, in the following diagram, all vertex maps are induced by an inclusion vertex map so the square of morphisms commute.
Applying the functor C to this diagram and restricting to degree 1, we obtain square C which must, therefore, commute. Hence, we obtain a chain map, as required.
and the morphism g C F (G)(s ≤ t) is as constructed in the proof of Lemma 3.9.
Notation 3.11. (a) We denote the induced map on chain complexes by g ι(s, t) # := g C F (G)(s ≤ t).
(b) In each homology degree k, we denote the induced map on homology by g ι(s, t) * := Thanks to Lemma 3.9, g C F gives us a map Obj(WDgr) → Obj([R, Ch]), 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 g C F becomes a functor. Theorem 3.12. Given a filtration functor F : WDgr F → [R, Dgr] and a functor C : Proof. Given f ∈ Mor WDgr F (G, H) and t ∈ R, we need a chain map g f # : . Moreover, f must satisfy the usual functorial axioms, as well as commute with g ι(s, t) # , i.e. for any s ≤ t we need Note that f is given by a vertex map f : Applying the functor C to these digraph maps, we obtain two chain maps, which can be joined as shown in the following diagram.
Squares A , B and D all commute because all vertical maps are parts of the same chain maps -either f # : Since the inclusion digraph map ι : G → G ∪ F t G is induced by an inclusion vertex map, it certainly commutes with f and hence square 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 ι(s, t) is always an inclusion vertex map, f must commutes with each ι(s, t). Hence, the two morphisms commute past each other as required by equation (3.5).

Notation 3.13.
Given a morphism f ∈ Mor(WDgr F ), we denote the induced map on chain complexes, constructed above, by g f # := g C F ( f ) and the induced map on homology in degree k by g f * := [R, H k ]( g f # ).

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 Dgr → 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, Since F is fixed, we will largely remove it from notation. We also use C instead of Ω.
Lemma 3.14. The F d -compatible category of weighted digraphs is the contraction category of weighted digraphs (see Definition 2.15), Now that we understand the category WDgr F d , applying Theorem 3.12 yields a functor g C : ContWDgr → [R, Ch]. Taking the first homology yields a persistent vector space in a functorial way; this functor is our proposed invariant for weighted digraphs.  (3.10) the (degree k) grounded homology by Remark 3.17. Note that for any t ∈ R, Therefore, the only new homology occurs in degree k = 1, since it compares 1-cycles in G ∪ F t G with 1-boundaries from G t . This justifies our focus on degree 1 homology in Definition/Theorem 3.15. 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 g 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 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 ∪ 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).

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 g H 1 (G, 0) is in fact the real cycle space of U (G).
Proof. Fix arbitrary t ≥ len(p) and denote the vertices of the path as a = v 0 , . . . , v m = b. Whenever i < j we can truncate p to obtain a path v i v j of length at most t and so . Therefore, inductively we can write as required.
has a basis of simple undirected circuits; and (c) # Dgm( g 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, g C • (G, 0) at the start of the filtration. Since G 0 has no edges, the chain complex is simply Since G is an orientation of U (G), the first homology of this chain complex is precisely the real cycle space of U (G). Fix an arbitrary spanning forest T of U (G), and label the remaining edges e 1 , . . . , e k . Note k is the circuit rank of U (G). Let p i denote the simple undirected circuit in G which traverses e i and then returns to st(e i ) through the unique path in T. Then {R(p 1 ), . . . , R(p k )} is a basis for g H 1 (G, 0).

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 ∈ g Z 1 (G, 0), as the first time v becomes null-homologous.
Remark 4.5. Let p be an undirected circuit in G and p the same circuit, traversed in the opposite direction so that R(p ) = −R(p). Since g ι(0, t) * is linear, D(R(p)) = D(R(p )). Also, since R(p) does not depend on the starting vertex of p, neither does D(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) ∈ WDgr and two directed paths p 1 , p 2 : a b between distinct vertices a, b ∈ V, let p c denote the undirected circuit which traverses p 1 forwards and then p 2 in reverse.
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 which concludes the proof. 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 D(R(p c )) = 2. To see this is the correct death time, first note that 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 eb f − ec f , whose boundary is not 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 ∈ C 2 (G, 2) and

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
We call elements of a persistence basis representatives. Lemma 4.9. Given any G ∈ WDgr, a persistence basis for g H 1 (G) always exists.
Proof. This follows from the structure theorem (Theorem 2.32) and Corollary 4.3.
Obtaining a persistence basis B ⊆ 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 B g H 1 (G) = {{I 1 , . . . , I m }} then there is an ordering on the cycles This mapping gives an isomorphism because In this sense, the representatives in B generate g H 1 (G).
Representatives live in g Z 1 (G, 0) so they are just 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.  : Two weighted digraphs with the same underlying digraph but different persistence bases, illustrating that not every circuit basis of g H 1 (G, 0) yields a persistence basis for g H 1 (G).
Example 4.11. First, we note that it does not suffice to chose any basis of undirected circuits for 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 The GRPPH of these two weighted digraphs is Instead, a persistence basis for g H 1 (G 2 ) is {γ 2 2 , γ 2 3 }. This illustrates that an arbitrary choice of undirected circuit basis for g H 1 (G, 0) may not yield a persistence basis of g H 1 (G). Moreover, a correct choice of basis does not depend only on U (G); we must incorporate information about how cycles in 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, . . . , t m where the chain complex g C • (G, t) changes. Therefore, it suffices to study the following finite persistent chain complex instead.
To the right of the chain complex we show the induced maps on homology g ι(t i−1 , t i ) * . 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 g ι(0, t m ) * . 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 g H 1 (G, 0) and show that we obtain a persistence basis.
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 ∪ G t ) and C 2 (G t ). Our approach is to decompose g ι(r, s) # into a sequence of chain maps. In the first, all the new generators of C 1 (G ∪ 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 ∪ 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 g ι(r, s) * . 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 ∪ G s ) \ E(G ∪ G r ). Given an edge e = (a, b) ∈ E new , there is some directed path p : a 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 ∈ G. Choose arbitrary such v e ∈ 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 which were not present in C 2 (G r ) and are linearly independent. Define W 0 := U new and let Q 0 denote the degree 1 homology of the chain complex which is a subcomplex of g C • (G, s).
Proof of Claim. We define a chain map c # in the opposite direction and a homotopy P : Hence, on degree 1 homology, c # induces an inverse to q 0 . The chain map in degrees k = 1 is given by and c 1 is defined on the basis of C 1 (G ∪ G s ) by The homotopy is given on the basis of C 1 (G ∪ G s ) by where w (a,b) ∈ U new . A standard check of the two cases verifies that c # is a chain map and the relations c 1 • q 0 1 = id and q 0 1 • c 1 − id = g ∂ 2 • P hold. Intuitively, c # collapses a new edge e = (a, b) ∈ E new onto the sum of edges av e + v e b in G ∪ G r . The homotopy P shows the two elements are homologous thanks to the presence of the directed triangle w e ∈ U new . of Claim.
By Proposition 2.30, there exists u 1 , . . . , u n ∈ C 2 (G s ) such that where each u i is amongst the generators identified in Proposition 2.30. Define W i := W 0 ⊕ u 1 , . . . , u i . This gives a sequence of inclusion chain maps where each rows is a subcomplex of g C • (G, s). We denote the degree 1 homology groups by Q i , with Q n := g H 1 (G, S), and the induced homology maps by q i : Q i−1 → Q i . Together these chain maps decompose g ι(r, s) # and hence the q i decompose g ι(r, s) * , as show in the following diagram.
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.
Then for each i ∈ J, the map on homology q i has nullity 1 and a basis for ker they must be linearly independent in Q 0 . Moreover, the nullity of q n • · · · • q 1 is #J so {[b i ] | i ∈ J} gives a basis for ker(q n • · · · • q 1 ). Hence (q 0 ) −1 [b i ] i ∈ J forms a basis for ker g ι(r, s) * . It now remains to prove that each (q 0 ) −1 [b i ] has a undirected circuit representative. Proof of Claim. First we recall that b i = g ∂ 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 We can write b i = 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 ) = R( p) for some undirected circuit p through G r . Using Lemma 4.1, for each edge τ ∈ E( p) in this circuit there is a directed path T τ through G of length at most r such that τ = R(T τ ) (mod g B 1 (G, r)). Concatenating the T τ we obtain an undirected circuit p i through G such that R(p) = R(p i ) (mod g B 1 (G, r)).
of Claim.
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.
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 To find a basis for ker g ι(2, 3) * we must compute c 1 ( g ∂ 2 u 1 ).
Then the chain map c 1 maps each of the blue edges to a sum of edges in G 2 . In fact c 1 ( g ∂ 2 u 1 ) = γ which is the representative of the sole simple undirected circuit in G.
The following Lemma follows by a standard linear algebra argument, since each g ι(t i−1 , t i ) * is surjective.
Certainly a basis of undirected circuits for 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 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 , . . . , p l such that {R(p 1 ), . . . , R(p l )} forms a basis for ker g ι(0, t m ) * . Using Lemma 4.16, we extend this to a basis {R(p 1 ), . . . , R(p l ), R(p l+1 ), . . . , R(p N )} for g H 1 (G, 0). This is a persistence basis for g 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 g H 1 (G 2 ) are γ 2 1 , γ 2 3 and γ 2 2 , γ 2 3 . 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 ∈ E new , and a choice of order on the remaining u i .

Decomposition
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 Grounded persistent path homology: a stable, topological descriptor for weighted digraphŝ v G 1 G 2 G 1 ∨v G 2 decomposition is a disjoint union; as one might expect, the descriptor decomposes as a direct sum.
Theorem 4.18. Suppose G ∈ WDgr decomposes as a disjoint union, G = G 1 G 2 , then Proof. Note that for each t ≥ 0, The boundary operator respects this split, mapping g C k (G i , t) → g C k−1 (G i , t) and the maps g ι(s, t) # also respect this split, mapping g C(G i , s) → g C(G i , t). Taking homology in degree 1 maintains this direct sum decomposition.

Definition 4.19. (a) Given a weighted digraph G = (V, E, w), a wedge vertex is a vertex
v ∈ V such that there is a decomposition Given a wedge vertex,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 G = G 1 ∨v G 2 . (c) Given a wedge decomposition as above, a pair of vertices a, b ∈ V are called separated if they do not lie in a common V i .

Remark 4.20. Given a wedge decomposition
In the case of a wedge decomposition G = G 1 ∨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 = G t 1 ∨v G t 2 , since there may be paths between separated vertices, throughv. However, using a chain homotopy, we can show that these edges do not affect the homology.
Proof. There are natural inclusion digraph maps j i : G i → G which are also contractions. Less obviously, there are contraction digraph maps f i : Since these are all morphisms in ContWDgr, we obtain induced morphisms g j i # and g f i # . We combine these morphisms to get two morphisms as follows J : g C(G 1 ) ⊕ g C(G 2 ) → g C(G), J(γ 1 , γ 2 ) := g j 1 # γ 1 + g j 2 # γ 2 ; (4.26) F : g C(G) → g C(G 1 ) ⊕ g C(G 2 ), F(γ) := ( g f 1 # γ, g f 2 # γ).  In degree 1, F • J = id is the identity map on g C(G 1 ) ⊕ g C(G 2 ).
Proof of Claim. First note that, f i • j i is the identity digraph map id i : G i → G i . However, f 3−i • j i is the constant digraph map c i : G i → G 3−i which maps all of G i to the vertexv. Hence, in matrix form, we can write F • J as Since the constant maps c i send all vertices to a single vertex, g c i # maps every edge to 0. Hence, in degree 1, g c i # is the zero map. Whereas, in degree 1, g id i # is the identity map on g C 1 (G i , t) at each t. Therefore, on degree 1, F • J is the identity map on g C(G 1 ) ⊕ g C(G 2 ). of Claim.
Composing with homology in degree 1, we see F * • J * = id is the identity map on g H 1 (G 1 ) ⊕ g H 1 (G 2 ). Proof of Claim. First, we compute J • F in degree 1. Recall that g C 1 (G, t) is freely generated by the edges in G ∪ G t . Given an edge e = (a, b) ∈ E(G ∪ G t ), if the vertices a, b lie in a common V i then (J • F)(e) = e. However, if a, b are separated then (J • F)(e) = av +vb. So we see, at the level of chains, J • F does not compose to the identity.
If e = (a, b) ∈ E(G ∪ G t ) but the endpoints are separated then we must have e ∈ E(G t ). Hence, there is a path p : a b in G of length at most t. Moreover, this path must traverse the vertexv. Hence, p decomposes into two paths a v andv b, each of length at most t. Therefore, the directed triangle avb is present in G t and is a generator of g C 2 (G, t). Note that the boundary of avb is ∂ 2 (avb) = av +vb − (ab) = (J • F)(e) − e. (4.29) This discussion show that we can define a map P : g C 1 (G, t) → g C 2 (G, t) by Then, J • F − id = ∂ 2 P as maps on g C 1 (G). Composing with homology, we see J * • F * = id is the identity on g H 1 (G). of Claim.
Since J * and F * are mutually inverse, they induce isomorphisms of persistent vector spaces.

Stability analysis of GrPPH
It is important that GRPPH is stable with respect to a reasonable noise model. Typically this is shown by proving that g H 1 is Lipschitz with respect to reasonable metrics on WDgr and the bottleneck distance on 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 O T θ : Obj(WDgr) → Obj(WDgr) for editing weighted digraphs, where T is the type of operation θ is the parameter of the operation. For each type T, we derive bounds of the form 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 θ. If we can show that no such local f exists (for general G and θ) 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 g H 1 (G) ∼ = g H 1 (O T θ 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.

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.
Remark 5.2. By Lemma 3.14, a 0-shifting vertex map is precisely a contraction digraph map. Given another -shifting vertex map g : Proof. Fix t ≥ 0. Since f is a δ-shifting vertex map, the functor C induces chain maps f # : . These chain maps fit together into the following commutative diagram.
and D commute because they are parts of the same chain map. The inclusion digraph maps G t → G ∪ G t and H t+δ → H ∪ H t+δ are induced by the identity vertex maps. Therefore f trivially commutes with these inclusions and hence square C commutes. Hence we get a chain map which we denote S( f , δ) # : g C • (G, t) → g C • (H, t + δ). Note, in the case δ = 0, this is precisely the same construction as g f # , given in the proof of Theorem 3.12.
It remains to show that these chain maps (for each t ≥ 0) constitute a morphism g C(G) → g C(H)[δ]. Given s ≤ t, the chain map g ι(s, t) # : g C • (G, s) → g C • (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 ι(s, t) # . Therefore, S( f , δ) # commutes with g ι(s, t) # . Simple composition of digraph maps confirms that g • f is a δ g + δ f -shifting vertex map. Note that in each degree the chain map is constructed via the functor C • . Therefore, in each degree, we have (g • f ) # = g # • f # which yields equation (5.3).

Lemma 5.4. A δ-shifting vertex map is a δ -shifting vertex map for any δ ≥ δ and
Proof. Clearly a δ-shifting vertex map is a δ -shifting vertex map since G δ ⊆ G δ . Since ι(t + δ, t + δ ) is induced by the inclusion vertex map, we get the following commutative diagrams of digraph maps Applying the functor C to these diagrams yields two commutative diagrams in Ch. The diagonal maps are components of S( f , δ ) # , the vertical maps are components of S( f , δ) # and the horizontal maps are components of g ι(t + δ, t + δ ) # . Hence we have a commutative diagram as required.

Weight perturbation
The classical stability theorem of persistent homology (first shown in [13]) is that for two continuous tame function f , g : X → R of a trianguable topological space X, denoting the persistence barcode of their sub-level set filtration by B f and B g respectively, 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.  So the cost of p differs by at most W 1 . Minimising over P (i → j), we see |d(i, j) − d (i, j)| ≤ W 1 .
Since V(G) = V(G ), there are identity vertex maps i 1 : V(G) → V(G ) and i 2 : V(G ) → V(G). Now i 1 defines a digraph map G → G since G = G as digraphs. Moreover, given (i, j) ∈ E(G t ), then d(i, j) ≤ t so d (i, j) ≤ t + δ and hence (i, j) ∈ E((G ) t+δ ). This shows i 1 defines a digraph map G t → (G ) t+δ for all t ≥ 0. Therefore i 1 (and likewise i 2 ) is a δ-shifting vertex map. Hence, we obtain morphisms Moreover, since composing i 1 and i 2 in either ordered yields the identity vertex map, these morphisms constitute a δ-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 || ∞ while the weaker bound is ||w − w || 1 .

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.
where τ e,i = (v e,i−1 , v e,i ) and we denote v e,0 := st(e) and v e,d(e) := fn(e). We then define 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) ∈ WDgr and any subdivision S : Proof. First, we setup some notation. Denote G S := O s S G = (V old V new , E old 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∈F w(G)(e).
Our strategy is to employ the isometry theorem (Theorem 2.38) Define the following vertex maps if v e,i ∈ V new and CS(e) i < 1/2, fn(e) if v e,i ∈ V new and CS(e) i ≥ 1/2, (5.11) which are visualized in Figure 10.  Proof of Claim. Since f is just the inclusion vertex map, Claim 5.11.1 shows that f defines a digraph map G t → G t S and so certainly G t → G t+W S . For the second map, pick an edge e ∈ E and note f (e) = e. If e ∈ F then it is undivided and e ∈ E(G s ). Otherwise e ∈ F and e ∈ E(G s ), however we note d S (st(e), fn(e)) ≤ w(e) ≤ W. Therefore, for any t ≥ 0, e ∈ G t s + W and hence of Claim.
Claim 5.11.3. For any t ≥ 0, g defines a digraph map G t S → G t+W and G S ∪ G t S → G ∪ G t+W . Proof of Claim. Given an edge τ = (a, b) ∈ E(G t S ) there is a path p : a b in G S of length at most t. We may assume that g(a) = 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 ∈ F then g(a) is either st(e) or 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) b in G S . By construction this, will add at most w(e)/2 ≤ W/2 to the length of p. Likewise we can alter the end of p to obtain a path g(a) g(b) in G S of length at most t + W. By Claim 5.11.1, we see g(τ) ∈ E(G t+W ).
Finally, given an edge τ ∈ G s there are two cases. If τ ∈ E old then the edge is preserved under g. Else τ = τ e,i ∈ E new in which case either τ is collapsed to one of the endpoints of e, or it is mapped to e. Hence g is digraph map G S → G and the final requirement follows.
of Claim.
Grounded persistent path homology: a stable, topological descriptor for weighted digraphs Therefore, f and g are W-shifting vertex maps and induce morphisms S( f , W) # : g C(G) → g C(G S )[W] and S(g, W) # : g C(G S ) → g C(G) [W]. (5.12) Now note that, as vertex maps g • f = id V(G) . Therefore, at the level of homology we have S(g, W) * • S( f , W) * = T ( g H 1 (G), 2W). Composing vertex maps in the opposite order, we do not obtain the identity. Moreover, S( f , W) # • S(g, W) # = T ( g C(G s ), 2W). However, we will show that, at every t ≥ 0, the chain maps on either side of this inequality differ by a boundary . First, choose a basis {c 1 , . . . , c k } of simple undirected circuits for g Z 1 (G S , 0). By Lemma 4.2, it suffices to prove that for each c i , where B := g B 1 (G S , t + 2W). Since simple undirected circuits are non-backtracking and the vertices {v e,1 , . . . , v e,d(e)−1 } have in-degree 1 and out-degree 1, we can write e∈F α e (τ e,1 + · · · + τ e,d(e) ) + ∑ e∈E\F α e e (5.14) for some α e ∈ {0, ±1}. Therefore, it suffices to prove the following two claims. Finally for e ∈ E \ F, g fixes the endpoints of e and hence S(g, W) # e = e. of Claim.
Proof of Claim. Choose any e ∈ F. The path (τ e,1 , . . . , τ 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. of Claim.
for each c i and each t ≥ 0, so, at the level of homology, S( f , W) * • S(g, W) * = T ( g H 1 (G S ), 2W). Therefore S( f , W) * and S(g, W) * constitute a W-interleaving and the bound on bottleneck distance follows by the isometry theorem.  (a) The medial subdivision, S med (G) : E(G) → ∆ 2 , is given by S(e) = (1/2, 1/2) for every e ∈ E(G). (b) The n th iterated medial subdivision of G, IMS n (G), is defined iteratively as follows.
Firstly, IMS 0 (G) := G then for each n, we define IMS n (G) := O s S IMS n−1 (G) where S = S med (IMS n−1 (G)). Corollary 5.14. Given a weighted digraph G ∈ WDgr, the sequence of barcodes (B g H 1 (IMS n (G))) n∈N converges under the bottleneck distance.
Proof. We first note that max e∈E(IMS n (G)) w(e) = 1 2 n max e∈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 : WDgr → R such that for any weighted digraph G = (V, E, w) ∈ WDgr and any subdivision S : F → ∆ d we have Proof. Suppose such f exists and consider the following sequence of digraphs in which each edge has unit weight. Figure 11: A sequence of weighted digraphs G n , in which all edges have unit weight and #B g 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 Hence which eventually exceeds the constant f (NG(e; G)).

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.  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) ∈ WDgr and an edge e = (a, b) ∈ E. Suppose e is the only outgoing edge from a and the only incoming edge to b (as in Figure 12), then Proof of Claim. If (i, j) ∈ E(G t ), then there is a path p joining i j of length at most t in G. Thanks to the previous claim, f (p) is a path f (i) 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) ∈ E(G t+δ e ). of Claim.
Claim 5.17.3. g defines a digraph map G t e → G t+δ .
Proof of Claim. Suppose (i, j) ∈ E(G t e ), then there is a path p : i 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) ∈ G t+δ . Conversely, suppose p does traverse v e and write p = (v 0 = i, v 1 , . . . , v k−1 , v e , v k+1 , . . . , v l = j). (5.25) Note that v k−1 ∈ N in (a) and v k+1 ∈ N out (a).
Replacing v e with the sequence (a, b) we obtain a new path a, b, v k+1 , . . . , v l = j). (5.26) which exists in G. We now split into cases. Case 1: If i = v e and j = v e then g(i) = i and g(j) = j and p is a path g(i) = i j = g(j). Case 2: If i = v e then j = v e so g(i) = a and g(j) = j and p is a path g(i) = a j = g(j). Case 3: If j = v e then i = v e so g(i) = i and g(j) = a but p is a path g(i) = i b which ends (a, e, b); removing the last edge yields a path g(i) = i 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 is at most t + w(e) and hence (i, j) ∈ G t+δ e . of Claim.
Claim 5.17.4. g defines a digraph map G e ∪ G t e → G ∪ G t+δ .
Proof of Claim. Thanks to the previous claim, we only need to check edges (i, j) ∈ E(G e ). Any edge (i, j) ∈ E(G e ) which is not incident to v e is mapped by g to itself (i, j) ∈ E(G). By the assumption on e, if j = v e , then i ∈ N in (a) and hence (g(i), g(v e )) = (i, a) ∈ E(G). Else, suppose i = v e , then j ∈ N out (b). Note that the path (a, b, j) in G is of length w(e) + w(b, j) ≤ δ. Therefore (g(v e ), g(j)) = (a, j) ∈ E(G t+δ ) for all t ≥ 0. of Claim.
As vertex maps f • g = id V e and hence S( f , δ) * S(g, δ) * = T ( g C(G e ), 2δ). However, it is not the case that 2δ). 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. for some v 1 ∈ N in (a), v 2 ∈ N out (b) and α e , α τ ∈ {0, ±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. of Claim.
Proof of Claim. For the first equality, note that a, v 1 and v 2 are fixed by For the second, any edge τ ∈ E(G) \ N (e), τ = e does not have b as one of its endpoints and hence both endpoints of τ are fixed by g • f . of Claim.
Finally it remains to show that for any v 1 ∈ N in (a) and v 2 ∈ N out (b), v 1 a + ab + bv 2 = v 1 a + av 2 (mod g B 1 (G, t + δ)) (5.28) for all t ≥ 0. Note that (a, b, v 2 ) is a path a v 2 of length at most δ and hence the directed triangle (a, b, v 2 ) is in the digraph G t+δ for all t ≥ 0. The claim then follows since g ∂ 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 #B g H 1 (G) = #B g H 1 (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 : WDgr → R such that for any weighted digraph G = (V, E, w) ∈ WDgr and any edge e ∈ E therein we have Proof. Suppose such f exists then consider the following weighted digraph G, where e := (v 0 , v 5 ) and W := 2 f (NG(e; G)) Figure 13: An example weighted digraph which illustrates that g 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 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 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 (NG(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 v 3 was via the costly red edge but in 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.

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. 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.
To see this, note that for arbitrary i, j ∈ V we have d e (i, j) ≥ d(i, j) since there are strictly fewer paths i j in G e than in G. Moreover, there is path p e : a b in G e of length at most δ. Then, given a path p : i 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 j in G e of length at most t + (δ − w(e)) ≤ t + δ. Therefore, We claim that id V constitutes a d e (a, b)-shifting vertex map G → G e and G e → 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 id V defines a digraph map G t → G t+δ e and G t e → G t+δ for all t ≥ 0.
Then E e ⊆ E, so id V certainly defines a digraph map G e → G and thus G e ∪ G t e → G ∪ G t+δ for all t ≥ 0. In the other direction, E \ E e = {e} so id V does not define a digraph map G → G e However e ∈ E(G t+δ e ) for all t ≥ 0 and hence id V does define a digraph map G ∪ G t → G e ∪ G t+δ e for all t ≥ 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) ∈ E such that there exists a vertex v ∈ V such that a → v → b then Next, we consider the scenario where an edge e is subdivided and then one of the daughter edges τ := τ e,i is deleted (as shown in Figure 14). In the resulting weighted digraph O d τ G, there is no alternative path between the endpoints of τ so the bound from Theorem 5.22 would be infinite. However, we can bound the effect of such an operation. Proof. We first note that upon deleting τ 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 g H 1 (O d τ G S ) ∼ = g H 1 (G e ). Hence, it remains to prove The proof continues as an amalgamation of the proofs of Theorem 5.11 and Theorem 5.22. Define the following vertex maps if v e,i ∈ V new and CS(e) i < 1/2, fn(e) if v e,i ∈ V new and CS(e) i ≥ 1/2.
We note that f induces a contraction digraph map G e → G S Hence, by Lemma 5.4, it is a δ-shifting vertex map and moreover, S( f , δ) # = T ( g C(G s ), δ) • g f # .
Claim 5.24.1. g induces a digraph map G t S → G t+δ e , for every t ≥ 0.
Proof of Claim. Given (i, j) ∈ E(G t S ), there is a path p : i j in G s of length at most t. Since d e (a, b) ≤ δ there is a path p e : a b in G e of length at most δ. We construct a new trail p in G e as follows.
If the entire sequence of daughter edges (τ e,1 , . . . , τ e,d(e) ) appears in p then we replace that sequence with p e . If i ∈ V new and g(i) = a then we replace the initial sequence of daughter edges with p e . If i ∈ V new and g(i) = b then we simply remove the initial sequence of daughter edges. Likewise, if j ∈ V new and g(j) = b then we replace the final sequence of daughter edges with p e . If j ∈ V new and g(j) = a then we simply remove the final sequence of daughter edges. This yields a trail p : g(i) g(j) Since p cannot repeat edges, this construction inserts p e at most once and hence the length of p is at most t + δ. Therefore (i, j) ∈ E(G t+δ e ). of Claim.
Claim 5.24.2. g induces a digraph map G S ∪ G t S → G e ∪ G t+δ e , for every t ≥ 0.
Proof of Claim. It remains to check the image of edge e ∈ (G S ) Any un-subdivided edge e ∈ E old is preserved under g. Given an edge τ e,i = (x, y) ∈ E new then τ = (v e,i−1 , v e,i ) for some i and there are three cases (g(v e,i−1 ), g(v e,i )) = (st(e), st(e)) or (st(e), fn(e)) or (fn(e), 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 t+δ e for all t ≥ 0. Therefore g defines a digraph map as required. of Claim.
is identical to the corresponding section in the proof of Theorem 5.11. Note that we require 2δ ≥ w(e) so that we can apply Lemma 4.1 to show τ e,1 + · · · + τ e,d(e) = e (mod g B 1 (G, t + 2δ)), (5.38) for all t ≥ 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.  Figure 15: An example weighted digraph which illustrates that g 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 O d e G has no features. Therefore, the bottleneck distance is W/2 > f (NG(e; G)).

Separating edges
Since all features are born at t = 0 and 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. Then a wedge decomposition of G is G = (G 1 ∨ a G 2 ) ∨ b G 3 and a disjoint union decomposition of O d e G is O d e G = G 1 G 3 . Note that G 2 is just a single edge connecting two vertices so g H 1 (G 2 ) is the trivial persistent vector space. Using Theorem 4.18 and Theorem 4.21, we see as required.

Interpretation
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 j, not involving the edge e := (i, j), of length δ, then removing e changes the barcode by at most δ 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.

Vertex deletion
Definition 5.29. Given a weighted digraph G = (V, E, w) and a vertex v Since a single vertex graph has trivial GRPPH the disjoint union decomposition theorem (Theorem 4.18) allows us to delete isolated vertices.
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 : WDgr → R such that for any digraph G = (V, E, w) and any vertex v ∈ V therein we have

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.
Proposition 6.1. Suppose G ∈ WDag is the union two directed paths p 1 , p 2 from a source to a sink, with lengths l 1 ≥ l 2 respectively. Recall the definition of iterated medial subdivision (Definition 5.13). Then Proof. For brevity we denote G n := IMS n (G). By Corollary 4.3, the barcode B g H 1 (G n ) has exactly one feature. Let p where v 1 is along p 1 and v 2 is along p 2 (as drawn in red) dashed lines).
p (n) 2 in reverse. Clearly {R(c (n) )} is a persistence basis for g H 1 (G n ). Therefore, it suffices to show D(R(c (n) )) → 1 2 l 1 as n → ∞. Fix some natural n. Using Lemma 4.6 we see D(R(c (n) )) ≤ max(h 2 ) → 1 2 l 1 as n → ∞. Next, we wish to show D(R(c (n) )) ≥ 1 2 l 1 . Choose arbitrary t 2 < 1 2 l 1 , then it suffices to show that dim g H 1 (G n , t 2 ) = 0. In order to do so, we claim the inclusion chain map induces an isomorphism on homology in degree 1. It then follows that dim 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) ∈ C 1 (G n ∪ G t 2 n ), if (i, j) = (a, b) then let p i,j := p 2 , otherwise let p i,j denote the unique path i j in G n Then q 1 is given by q 1 (ij) := R(p i,j ). This is a chain map because there is no 2-path avb where v is somewhere along It is certainly the case that, at the level of chain maps, q 1 j 1 = id. Choose arbitrary (i, j) ∈ C 1 (G n ∪ G t 2 n ) and note that Then, by construction, we see j 1 q 1 − id = g ∂ 2 P. Hence, j and q are mutually inverse on homology in degree 1.
To conclude, we have shown for each n, Taking the limit n → ∞ 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 ∈ WDgr, let H 1 denote the 'standard pipeline' with C = Ω and F = F d , as used in Example 3.6. Then Proof. For brevity, we denote G n := IMS n (G). Fix > 0 and choose N sufficiently large that for any n ≥ N we have w(e) < for all e ∈ E(G n ). For any t ≥ 0, define 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 ∂ 2 = g ∂ 2 i 2 and hence i 1 induces a map on homology i * : H 1 (G t n ) → g H 1 (G n , t + ). Similarly, for any t ≥ 0 define 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 ∈ E(G n ), we know d(st(e), fn(e)) < and hence e ∈ E(G t+ n ). Again j 1 g ∂ 2 = ∂ 2 j 2 and hence j 1 induces a map on homology j * : g H 1 (G, t) → H 1 (G t+ ). Clearly i * • j * = g ι(t, t + 2 ) * and j * • i * = ι(t, t + 2 ) * . Therefore, by the algebraic stability theorem, we see for all n ≥ N.

Square motifs
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 ab + bd − cd − ac; ab − db + dc − ac; ab + be − ce − ac , db + be − ce − dc; ab − eb + ec − ac , db − eb + ec − dc.  Figure 19: A weighted digraph with many paths (of 2 edges each) from source to sink for which we can compute B g H 1 (G).
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, ∞).
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, ∞).
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.

Multiple paths
Example 6.4. Consider Figure 19, in which there is a single source and a single sink but multiple paths between. Define α i := max(a i , b i ) and assume that α 1 ≤ α 2 ≤ . . . α n−1 ≤ α n . Then, the barcode is  Figure 20: Two weighted digraphs with identical shortest-path quasimetric network but differing GRPPH which can be explained by the difference in circuit rank.

Identical quasimetric
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 g H 1 (G 1 ) = g H 1 (G 2 ). Moreover, B g 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, A persistence basis for g H 1 (G 1 ) } Note that at t = 1 the two triangular cycles becomes homologous in g H 1 (G 2 ) but are still non-trivial, until they die at t = 2.

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 . . . v n such that i < j =⇒ v i → v j .
Definition A.2. The directed flag complex, dFl(G), of a digraph G ∈ Dgr is the chain complex · · · dFl 2 (G) where dFl k (G) is the R-vector space freely generated by the (k + 1)-cliques in G. The boundary map ∂ k is defined on the basis of cliques by where v 0 . . .v i . . . v k is the k-clique obtained from v 0 . . . v k by removing the vertex v i . The directed flag complex is an alternative chain complex for digraphs, dFl : Obj(Dgr) → Obj(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 and C = dFl . (A.2) Recalling that morphisms in Dgr can collapse edges, we show that dFl cannot constitute a functor Dgr → Ch. However, we do find a smaller category TricolDgr ⊆ Dgr, containing all digraphs, upon which 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), g Á H 1 : Obj(WDgr) → Obj(PersVec). For the remainder of the appendix, we review the results obtained for GRPPH, in the main text and check which results apply to g Á 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 TricolDgr. We summarise the known stability results for the directed flag complex in Table 2.
Moreover, we find that the failure in functoriality Dgr → 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, B g Á H 1 (G). This behaviour is not present in GRPPH; we argue this is an instability which complicates the interpretation of B g Á H 1 (G). Proof. Suppose such a functor exists. Consider the three digraphs illustrated in Figure 22.

A.1 Functoriality of the directed flag complex
The digraph map f is given by the obvious inclusion, whilst g maps v 1 and v 2 to themselves and v 0 → v 1 . Note that g • f composes to the identity and hence the triangle of digraph maps commutes. Applying H 1 • dFl to this diagram we find that g * • f * is the identity on Z.
However, H 1 (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. We extend linearly to obtain a linear map f # : dFl k (G) → dFl k (H).
This does not necessarily constitute a chain map dFl(G) → 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. 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 dFl(G) → dFl(H). That is, we need to check f # commutes with the boundary map. We verify this on the basis of dFl k (G).

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, #B g Á H 1 (G), is the circuit rank of the underlying, undirected graph, U (G). These results do not rely on the functoriality of 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 = 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) ∈ WDgr and two directed paths p 1 , p 2 : a b between distinct vertices a, b ∈ 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 {t ≥ 0 | ∃v i ∈ V along p i such that d(a, v i ) ≤ t and d(v i , b) ≤ t} . (A.8) Then D(p c ) ≤ 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 g C 2 (G, T) and so certainly av 1 b − av 2 b ∈ 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 , . . . , 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 ∈ WDag then the proof goes through unchanged because ContWDag ⊆ PathcolContWDgr.
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.   Denotes a theorem which applies to the directed flag complex unrestricted. Denotes a theorem which applies to the directed flag complex after restricting to G ∈ WDag. 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.