Access the full text.
Sign up today, get DeepDyve free for 14 days.
We introduce a persistent Hochschild homology framework for directed graphs. Hochschild homology groups of (path algebras of) directed graphs vanish in degree i ≥ 2. To extend them to higher degrees, we introduce the notion of connectivity digraphs, and analyse two main examples; the ﬁrst, arising from Atkin’s q-connectivity, and the second, here called n-path digraphs, generalising the classical notion of line graph. Based on a categorical setting for persistent homology, we propose a stable pipeline for computing persistent Hochschild homology groups. This pipeline is also amenable to other homology theories; for this reason, we complement our work with a survey on homology theories of directed graphs. Keywords Graph homology · Persistent homology · Hochschild homology · Connectivity graphs · n-Path digraphs · q-Connectivity Mathematics Subject Classiﬁcation 05C20 · 05C90 · 55N31 · 18G85 · 13D03 Introduction Directed graphs, or shortly digraphs, organise a multitude of mathematical objects and physical phenomena; in particular, where an inherent directionality plays a con- siderable rôle. Prominent examples motivating this paper come from structural brain networks, i.e., (directed) networks modelling the synaptic connectivity in the brain; here the pre- and post-synaptic signal propagation induces directions between neurons. Henri Riihimäki henrir@kth.se Luigi Caputi luigi.caputi@unito.it Dipartimento di Matematica “Giuseppe Peano”, Universitá di Torino, 10124 Torino, Italy Department of Mathematics, KTH, Stockholm, Sweden 123 L. Caputi, H. Riihimäki This type of application in neuroscience has particularly ignited the interest in applied topology and topological data analysis (TDA), together with the subsequent develop- ment of computational tools (Lütgehetmann et al. 2020; Reimann et al. 2017). For an application in classifying network (brain) dynamics, see the recent work (Conceição et al. 2022). One of the main techniques adopted in TDA is persistent homology (PH), which has been employed not just in neuroscience and neuroimaging (Caputi et al. 2021b; Chung et al. 2014; Khalid et al. 2014; Kuang et al. 2019; Lee et al. 2011), but also in ﬁelds like ﬁnance (Gidea 2017), ﬁngerprint classiﬁcation (Giansiracusa et al. 2019), and image classiﬁcation (Dey et al. 2017), to name a few. In applications, the classical persistent homology pipeline takes as input a ﬁltered family of undirected graphs. Having in mind the aforementioned examples involv- ing families of digraphs instead, we are interested in persistent homology pipelines for directed graphs; however, in order to extend the classical pipeline to directed frameworks, one needs suitable (co)homology theories of directed graphs. The main goal of this paper is to go beyond structural limitations of existing (undirected) approaches. To do so, we introduce new connectivity frameworks, aiming to capture more combinatorial and homotopical invariants of digraphs, as we now shall describe. In a primal approach, the persistent homology pipeline for directed graphs would be the following: one starts by constructing suitable simplicial complexes (the directed ﬂag complexes Masulli and Villa 2016; Reimann et al. 2017) associated to the digraphs, computes (most often, homological) features of the simplicial complexes, and ﬁnally uses these, or derived features, for subsequent network analysis. Implementations are usually possible, thanks to existing software and algorithms allowing homological computations; e.g., Flagser (Lütgehetmann et al. 2020) has a persistence implementa- tion with directed ﬂag complexes. Even if the simplices in directed ﬂag complexes are constructed using the coherently oriented cliques in the digraphs, the calculation of the associated homology groups reduces to simplicial homology. This has the effect that the associated topological invariants forget some information carried in the direction- ality of the edges. Besides the directed ﬂag complex approach, many other homology theories of digraphs have been recently used in applications. With the hope that the interested reader might ﬁnd useful a recollection of some prominent homology theories of digraphs, in Sect. 2 we provide a review of recent advancements. Among others, we give an overview of the recently developed path homology (Grigor’yan et al. 2020)— see Sect. 2.2, and also Chaplin (2022) for a comparison with the directed ﬂag complex of random graphs. A third approach uses Hochschild homology (HH), a homology theory of associative algebras introduced by Hochschild (1945)—cf. Sect. 2.3. There is a standard and coherent way of associating to a directed graph an associative algebra, called the path algebra. Then, application of Hochschild homology to path algebras of digraphs provides additional homological invariants. We refer to Sect. 2.4 for an exposition of other related homological constructions. In Sect. 3.2, we show that all the described homological approaches cannot tell apart simple examples of non-isomorphic digraphs. This then begs the question about what an appropriate homology theory for digraphs should be, and how to incorporate the directed combinatorics in the theory and applications. Hochschild homology of path algebras is able to capture part of the combinatorial information. Path algebras, in fact, naturally arise from the combinatorics of the directed paths in the digraphs, and 123 Hochschild homology, and a persistent approach via… Hochschild homology is able to coherently capture such information. If the digraph has an oriented cycle, the path algebra is automatically inﬁnite-dimensional. In the case of acyclic digraphs instead, the dimensions of the Hochschild homology groups, seen as vector spaces over a base ﬁeld, can be laid down in a simple combinatorial formula. However, also the Hochschild homology of digraphs has some shortcomings. First, the digraph is assumed to be acyclic, which rarely is the case in real networks. Second, the Hochschild homology groups vanish beyond degree 1, and one retrieves no information beyond dimension 1 of the digraph itself. To remedy the issues raised above, we propose in this paper the following approach: a persistent homology framework applied to a ﬁltered family of digraphs taking into account higher orders of intrinsic connectivities. The main points of the paper follow the scheme below: From digraphs to connectivity digraphs With the twofold aim of providing and extending persistent homology pipelines to higher degrees, and of capturing combina- torial information intrinsic in the directed structure of directed graphs, we introduce the notion of a connectivity digraph—cf. Deﬁnition 3.2. For a digraph G, a connectivity graph associated to G is a graph, possibly directed, constructed by using the combina- torics of G. For example, connectivity graphs can be described by edges, paths, sets of edges, or by cliques, together with their incidence relations. In Sect. 3 we present two new connectivity structures for simplices. The directed q-analysis extended from the work of Atkin (1972) connects simplices σ and τ , both of dimension ≥ q, if there is a q-dimensional face α such that d (σ ) ←α → d (τ ), where d is an extended i j i face map (see Deﬁnition 3.12). The n-path digraph connects n-simplices σ and τ if there is an (n − 1)-simplex α such that d (σ ) = α = d (τ ) with i < j, where d is the i j i standard face map. Both the above connectivity relations deﬁne connectivity digraphs. Hochschild homology for acyclic graphs Application of homologies (simplicial homology, path homology, Hochschild homology) to connectivity digraphs extends the family of homological invariants of digraphs to each n ∈ N. In particular, apply- ing Hochschild homology on connectivity digraphs enables us to admit Hochschild homology groups from degree 1 to n, where n now refers to the dimension of simplices appearing in our connectivity digraphs. A convenient computation of the dimension of Hochschild homology only applies when restricting to acyclic digraphs. In gen- eral, this fails to be true, also for our connectivity digraphs. To be able to compute Hochschild-related invariants for general digraphs, we deﬁne the Hochschild charac- teristic (Deﬁnition 2.29) which adds to the acyclic formula the component coming from the vector space generated by the simple cycles in the digraph. Stable persistent Hochschild homology In the case of acyclic digraphs the transfor- mation from the category of digraphs, through connectivity structures, into ﬁnite vector spaces via Hochschild homology is functorial. Then, for a given ﬁltration of digraphs, one can apply the usual pipeline to get persistent Hochschild homology groups of digraphs. The categorical framework developed by Bergomi and Vertechi (2020)pro- vides immediately the needed abstract stability theorems. For a ﬁltration F in the category Digraph of digraphs without oriented cycles, the persistent Hochschild 123 L. Caputi, H. Riihimäki pipeline can be illustrated as the following composition of functors: F C K− HH (R, ≤) − → Digraph − → Digraph − − → K-Alg −−→ FinVect 0 0 where C is any functorial construction of connectivity digraphs—cf. Sect. 4.1 and 4.2. In Sect. 4.3, we apply this procedure to a real network, namely the neural network of the C. elegans. Computational H H and K -theory into applied topology toolbox As far as the authors know, this work is the ﬁrst in bringing invariants from Hochschild homol- ogy into the realm of TDA, to be used as featurisations of common data objects. Our implementation of the above pipeline and computations on the C. elegans indeed demonstrate the applicability of our approach to real-world directed networks. Nat- ural extensions would be using cyclic homology theories and K -theoretic methods. Previous work has focused on computing the K -theory of the category of zig-zag persistence modules (Grady and Schenﬁsch 2021). In a subsequent work we plan to investigate the extension in the K -theoretic directions as well. We hope with this work to raise the interest of current developments in applied topology and persistence to focus more on trying to bring unexplored tools from theoretical algebraic topology and K -theory into the applied setting. Based on our work, we believe that a following recipe is useful. First, a fruitful combination of data and invariants needs to be found. For us, this is the combinatorics of (connectivity) digraphs and the path algebras they generate. Standard simplicial persistence is made for ﬁnite metric spaces, which we feel is not a natural pairing for digraphs as com- binatorial objects without any regard on metric issues. Second, the invariant needs to be computable. In our case, this comes from the known combinatorial formula for the dimensions of Hochschild homologies. Going further, one needs to focus algebraic derivations on proving similar results when these are not yet existing. Third, the main lesson from persistence theory are the stability results. Any new tool in the applied topology toolbox should take into account that small variations in the input data need to be bounded at the level of algebraic invariants and featurisations. As mentioned, our pipeline satisﬁes certain stability guarantees. We ﬁnish with some perspective on the apparent simplicity of digraphs. Even though graphs and digraphs are simple objects to describe and many concepts in graph theory are rather easy and intuitive to handle, it is the immense possibilities of putting together vertices and edges that gives rise to the actual complexity of graphs/digraphs. One then needs to ﬁnd an appropriate balance between the objects described and complexity and information content of the invariants attached to them. As a fourth point in the recipe of the previous paragraph, in applications some level of interpretability of the invariants is desired. In standard persistence it is easy to give a geometric meaning to the generators of a barcode. In the case of Hochschild homology it is still maintainable to understand how the information of directed paths is captured. The question of interpretability is of course conditioned on the application domain. For example, in medical applications the outcomes of TDA analyses should have some meaning to, say, prognosis and diagnosis. In machine learning applications topological/algebraic invariants can be accepted more as black box featurisations. 123 Hochschild homology, and a persistent approach via… Conventions Calligraphic font, as G, is used to denote ﬁnite graphs (both directed and undirected). All base rings are assumed to be unital and commutative, and algebras are assumed to be unital and associative. Unless otherwise stated, R denotes a ring, K is an alge- braically closed ﬁeld, A is a unital associative R-algebra, V is a vector space over K, and all tensor products ⊗ are assumed to be over the base ring R or base ﬁeld K. General references for graph theory, category theory, and algebraic topology are West (2005), MacLane (1971), and Hatcher (2000), respectively. 1 Graphs and complexes In this section we review and ﬁx some basic notions related to graphs and simplicial complexes, needed in the follow-up. 1.1 The category of digraphs A graph is pair G = (V , E ) consisting of a set of vertices V and a relation E ⊆[V ] . The relation E is the set of edges between vertices and we denote the edges by pairs {v, w}. We are interested in graphs with oriented edges: Deﬁnition 1.1 A directed graph,ora digraph, is pair G = (V , E ) consisting of a set of vertices V and a subset E ⊆ (V × V )/ , where ={(v, v) | v ∈ V }.The V V subset E is the set of directed edges and we denote edges by ordered pairs (v, w). In this work, unless otherwise speciﬁed, graphs and digraphs will always be ﬁnite, hence the sets V and E are ﬁnite. Note that the deﬁnition above deﬁnes simple (di)graphs without loops: there are no edges of the form {v, v} nor (v, v) and there is only one edge between any pair of vertices. In the case of digraphs, edges are unique ordered pairs (v, w), and we allow reciprocal edges (v, w) and (w, v) in E.Weuse the same symbol G for denoting both an (undirected) graph and a digraph. In the rest of the paper we will mainly deal with digraphs, and we will always make clear whether we are referring to a graph or a directed graph. Deﬁnition 1.2 A graph is complete if for every pair of vertices v and w there is an edge {v, w}. A digraph is complete if for every pair of vertices v and w there are both edges (v, w) and (w, v).A k-clique of G is a complete subgraph of G on k vertices. Directed graphs come equipped with source and target maps s, t : E → V . For an edge e = (v, w), the function s maps e to its source, s(e) = v, and t to its target, t (e) = w. Sometimes, when we want to specify the source and target maps, we denote a digraph as G = (V , E , s, t ). Graphs and digraphs have natural notions of morphisms between them; we spell it out in the case of digraphs. 123 L. Caputi, H. Riihimäki Deﬁnition 1.3 A morphism of digraphs from G = (V , E ) to G = (V , E ) is a 1 1 1 2 2 2 function φ : V → V 1 2 on the vertices such that (φ (v), φ (w)) ∈ E for every (v, w) belonging to E . 2 1 Observe that, by Deﬁnition 1.3, a morphism of digraphs sends directed edges to directed edges and it does not allow to collapse them. One can also consider func- tions φ : V → V on the vertices such that either φ(v) = φ(w) or (φ (v), φ (w)) ∈ E ; 1 2 2 we refer to these maps as maps of digraphs. Finite digraphs and edge preserving mor- phisms of digraphs form a category that we denote by Digraph.By Digraph we denote the category of ﬁnite digraphs with possible self-loops on vertices, and maps of digraphs. Remark 1.4 A morphism of digraphs from G to G sends complete subgraphs of G 1 2 1 to complete subgraphs of G , hence cliques to cliques. Indeed, otherwise a morphism would collapse at least one of the edges in the clique, which is not allowed. One can consider also more restrictive morphisms, namely morphisms of digraphs that are also injective (as functions of vertices). We will refer to these morphisms as regular morphims of digraphs and denote the resulting category of digraphs (possibly with loops) and regular morphisms by RegDigraph. Remark 1.5 Both the categories Digraph and RegDigraph have an initial object ∅, the empty digraph. Note that this is not a terminal object. An oriented cycle in a directed graph G is an embedding into G of the coherently oriented cyclic digraph C on n vertices—cf. Fig. 1. In the follow-up, we might need to work with categories of digraphs without oriented cycles; we use the following notation: Notation 1.6 We denote by Digraph the subcategory of Digraph consisting of ﬁnite directed graphs without oriented cycles. A standard construction in graph theory is the so called edge graph,or line graph, L(G) of a graph G. This is deﬁned as the graph consisting of all the edges of G as vertices, with connections described by the incidence relations. The construction generalizes to the case of digraphs—see, for instance, Harary and Norman (1960): Deﬁnition 1.7 The line digraph of a directed graph G = (V , E , s, t ) is the directed graph L(G) whose vertices are the edges of G and two vertices p and q in L(G) corresponding to the edges e = (s(e ), t (e )) and e = (s(e ), t (e )) in G are p p p q q q connected by a directed edge (p, q) ∈ E (L(G)) if t (e ) = s(e ). p q Associating a line (di)graph to a (di)graph is coherent with respect to morphisms: An initial object in a category C is an object I such that, for each object C of C, there is a unique morphism I → C. 123 Hochschild homology, and a persistent approach via… Fig. 1 The coherently oriented cyclic digraph C Remark 1.8 There is a functor L : Digraph → Digraph which sends a digraph G to its line digraph L(G). First, note that the line digraph L(G) of a digraph G is the empty digraph ∅ if, and only if, G has no edges. As by Remark 1.5, ∅ is an initial but not a terminal object in the category Digraph, the functoriality may fail for morphisms φ : G → G , where G has no edges. On the other hand, a morphism 1 2 2 of digraphs sends edges to edges and collapsing is not allowed; therefore, either both G and G have no edges—hence, the induced morphism between the associated line 1 2 digraphs is the trivial morphism ∅ → ∅—or φ induces a morphism of digraphs L(φ) : L(G ) → L(G ) between the associated (non-empty) line digraphs. It is now 1 2 straightforward to check that compositions and identities are preserved; hence, L is a functor. We will use a standard procedure for obtaining directed acyclic graph out of a digraph. Deﬁnition 1.9 A strongly connected component inadigraph G is an induced subgraph G such that for any two vertices x and y in G there are paths x → y and y → x in G . The strongly connected components are the equivalence classes of the relation of being strongly connected on the vertices of G, i.e. having directed paths between any ordered pair of vertices. The ensuing partition then enables to construct the quotient graph without directed cycles. Deﬁnition 1.10 The condensation c(G) of digraph G has as its vertices the strongly connected components of G. Two vertices X and Y have a directed edge (X , Y ) in c(G) if there is an edge (x , y) in G for some x ∈ X and y ∈ Y . 123 L. Caputi, H. Riihimäki Remark 1.11 The condensation c(G) of a digraph G does not have oriented cycles. In particular, if G has the structure of a preorder, i.e. a reﬂexive and transitive relation, the condensation is a canonical way of obtaining its underlying partial order (Schröder 2016, Proposition 8.13). Observe that taking the condensation of a digraph is not functorial; in fact, it may lead to maps G →∗, where ∗ is the one-point graph. However, in the theory of Alexandroff and ﬁnite topological spaces preorders and partial orders are in bijection with topological spaces and spaces with T separation, respectively. In this context, the condensation is a homotopy equivalence (Barmak 2011). 1.2 Simplicial complexes and homology theories We recall here the deﬁnition of simplicial complexes; Deﬁnition 1.12 An (abstract) simplicial complex on a vertex set V is a collection K of non-empty ﬁnite subsets σ ⊆ V that is closed under taking non-empty subsets: if σ ∈ K and τ ⊆ σ is non-empty then τ ∈ K . The subsets are called simplices of K . The following list records notations related to simplices and simplicial complexes used in this paper. Notation Deﬁnition σ ∈ K σ is a simplex in a simplicial complex K . K the set of simplices of K with dimension greater than or equal to q. Vert(K ) or V (K ),Vert(σ ) The sets of vertices of K and σ , respectively. dim(σ ) |Vert(σ )|− 1, dimension of σ . If equal to k,then σ is a k-simplex. dim(K ) The dimension of K , the dimension of its highest dimensional simplex. τ ⊆ σ , τ→ σ Face of σ . Faces are simplices. We use the convention that every simplex is a face of itself. Proper face has dimension strictly less than the dimension of the simplex. Analogously to morphisms of graphs, we can deﬁne morphisms of simplicial complexes: Deﬁnition 1.13 A simplicial map f : K → K between simplicial complexes K 1 2 1 and K is a function on the vertices f : V (K ) → V (K ) such that f (σ ) ∈ K is a 2 1 2 2 simplex for every simplex σ of K . 123 Hochschild homology, and a persistent approach via… (Abstract) simplicial complexes and simplicial maps form the category of simplicial complexes, that we denote by SCpx. In this work we focus on homological invariants of directed graphs, and more precisely, on homology groups of digraphs. Homology groups are topological invariants of simplicial complexes. We assume that the reader is familiar with homology theories and we refer to Hatcher (2000), Munkres (1984) for comprehensive introductions. For setting the notations we brieﬂy sketch here the main deﬁnition. We ﬁx a commutative ring R. Deﬁnition 1.14 A chain complex (C,∂) is a sequence C = (C ) of R-modules n n∈N with a boundary operator ∂ consisting of linear maps ∂ = (∂ : C → C ) such n n+1 n that ∂ ◦ ∂ = 0 for all n. n n+1 A morphism of chain complexes f : (C,∂) → (C ,∂ ) is a sequence of linear maps f : C → C with the commutation relations f ◦ ∂ = ∂ ◦ f . Chain complexes n n n n n+1 n n and morphisms of chain complexes over R form a category Ch(R), or more concisely Ch. For a simplicial complex K and a commutative ring R, there is a standard way to construct a chain complex (C,∂) by considering, for each n ∈ N, the free R- module generated by the n-simplices of K . The construction gives a functor from the category SCpx of simpicial complexes to the category Ch. Furthermore, for a chain complex (C,∂),the degree n homology H (C ) of (C,∂) is deﬁned as the quotient H (C ) := ker(∂ )/im(∂ ), n n n+1 which is well-deﬁned as im(∂ ) is contained in ker(∂ ) by the identity ∂ ◦∂ = 0. n+1 n n n+1 If we want to indicate the coefﬁcients R over which we are computing homology we write H (C ; R). The construction gives functors from the category of chain com- plexes Ch to the category Mod of R-modules; hence, by composition, funtors from the category SCpx to Mod . In the next section we brieﬂy recall how to construct, start- ing with a digraph, suitable simplicial complexes (ﬂag complexes or path complexes) and homology groups of digraphs. 2 Homology theories of digraphs In this section we survey some of the most prominent homology theories of directed graphs. We start in Sect. 2.1 by recalling the deﬁnition of ﬂag complexes and asso- ciated simplicial homology, then in Sect. 2.2 we review the path complexes and path homology, as introduced by Grigor’yan et al. (2020). In Sect. 2.3, we provide a more detailed account on the Hochschild homology of a digraph, as of more relevance to us. Finally, in Sect. 2.4, we sketch some variations to these constructions, as has appeared in the literature. 2.1 Homology of flag complexes Homology groups of undirected graphs can be deﬁned as the simplicial homology groups of their underlying topological spaces; in fact, graphs can be seen as 1- dimensional simplicial complexes, and one can directly apply the approach of Sect. 1.2. 123 L. Caputi, H. Riihimäki We ﬁrst start with describing this naive approach, and then we see how to generalize it by means of the so-called ﬂag complexes. For a digraph G = (E , V ) and a ﬁxed commutative ring R, consider the chain complex 0 0 ∂ 0 ··· − → 0 − → E −→ V − →0(1) R R where E is the free R-module generated by the edges E and V is the free R- R R module generated by the vertices V of G. The boundary maps ∂ are all 0, except for ∂ ; this acts on the basis edges in E as 1 R ∂ (v, w) := w − v, and is extended to the whole R-module E by R-linearity. The homology groups of a digraph deﬁned this way are usually referred to as the ordinary homology groups of graphs. Remark 2.1 The ordinary homology groups of graphs are trivial in every degree i ≥ 2. The 0-th homology group of G describes the set of connected components. The 1-st homology group is isomorphic to the kernel of the only non-trivial map ∂ , and counts the cycles of G; its rank can be entirely described in terms of numbers of vertices, edges and connected components of the digraph G—see for instance (Diestel 2010, Theorem 1.9.6). A prominent approach to generate higher dimensional homology groups is to construct, out of a graph G, the so-called ﬂag (also known as clique) complexes (Aharoni et al. 2005; Chen et al. 2001; Ivashchenko 1994); these provide natural invariants of graphs and have been generalized to digraphs (Masulli and Villa 2016; Reimann et al. 2017), as we now recall. We ﬁrst need to introduce the ordered simplicial complexes. A set S, endowed with a linear order of its elements, will be called an ordered set. Deﬁnition 2.2 An ordered simplicial complex on a vertex set V is a non-empty family of ﬁnite ordered subsets σ ⊆ V with the property that, if σ belongs to then every ordered subset τ of σ (ordered with the natural order induced by σ ) belongs to When dealing with directed graphs, we need ordered cliques (as opposed to unordered cliques—cf. Deﬁnition 1.2. Deﬁnition 2.3 An ordered k-clique of a directed graph G is a totally ordered k-tuple (v , ..., v ) of vertices of G with the property that, for every i < j, the pair (v ,v ) is 1 k i j an ordered edge of G. We can now extend the construction of ﬂag complexes to directed graphs. Deﬁnition 2.4 Let G = (V , E ) be a directed graph. The directed ﬂag complex of G is the ordered simplicial complex dFl(G) on V whose k-simplices are all the ordered (k + 1)-cliques of G. 123 Hochschild homology, and a persistent approach via… We can again construct a chain complex. Let C (dFl(G); R) be the R-module freely generated by all the n-simplices of dFl(G). There are well-deﬁned face maps d : C (dFl(G); R) → C (dFl(G); R) (2) j n n−1 for j = 0,..., n.The j-th face map d , as an operator applied to the simplex (v ,...,v ) in C (dFl(G); R) is deﬁned by cancelling the j-th vertex: 0 n n d (v ,...,v ) := (v ,..., v ,...,v ). j 0 n 0 j n Face maps uniquely identify the faces of a simplex. In fact, let σ = (v ,...,v ) be 0 n an n-simplex of the ﬂag complex dFl(G); then, the faces d (v ,...,v ) are (n − 1)- j 0 n simplices of dFl(G). Each face map d uniquely identiﬁes the j-th (n − 1)-face of σ as the face opposite to the vertex v . For example, if (v ,v ,v ) is an ordered 3-clique j 0 1 2 inadigraph G, represented below as an ordered simplex σ of the associated directed ﬂag complex dFl(G), d (σ ) d (σ ) 2 0 v v 0 2 d (σ ) then we have d (σ ) = (v ,v ), d (σ ) = (v ,v ) and d (σ ) = (v ,v ). 0 1 2 1 0 2 2 0 1 Remark 2.5 The construction of ﬂag complexes can be promoted to a functor from directed graphs to ordered simplicial complexes. Namely, if φ : G → G is a mor- 1 2 phism of digraphs, then it sends ordered cliques of G to ordered cliques of G .This 1 2 induces a simplicial morphism f : dFl(G ) → dFl(G ) between the ﬂag complexes, φ 1 2 sending a simplex σ ∈ dFl(G ), hence an ordered clique (v ,...,v ) of G ,tothe 1 0 k 1 simplex f (σ ) = (φ (v ),...,φ(v )). φ 0 k The (simplicial) homology groups with coefﬁcients in R of a directed graph G are deﬁned as the homology groups of the associated directed ﬂag complex, and for each n ∈ N it can be seen as a composition of functors Ch◦dFl H (−;R) Digraph − −−− → Ch − −−−− → Mod , (3) where Mod is the category of R-modules. Example 2.6 Fix as base ring the ring of integers Z. Consider the square-shaped digraph G on the vertices 0, 1, 2, 3 and set of edges described as in the following picture: 1 3 G = ⇒ dFl(G) = 0 2 123 L. Caputi, H. Riihimäki Fig. 2 Two possible directed conﬁgurations for the pentagon graph As we only have ordered 2-cliques, the associated ﬂag complex is the square itself, i.e. an ordered simplicial complex with four vertices and four edges. It has homology groups ∼ ∼ (dFl(G); Z) Z H (dFl(G); Z). H = = 0 1 By adding to G also the edge (0, 3), we get the ordered 3-cliques (0, 1, 3) and (0, 2, 3); the corresponding ﬂag complex is then the full square: 1 3 G = ⇒ dFl(G) = 0 2 The ﬁrst homology group H (dFl(G); Z) is now 0, whereas the 0-th homology group describing the number of connected components is again isomorphic to Z. Remark 2.7 From Example 2.6 we see that some information from the orientations of the edges is lost. In fact, even though the simplices are constructed from the ordered cliques, the homology groups are deﬁned as the homology groups of the (geometric realization of the) directed ﬂag complex, which forgets some information about the directionalities. As an additional illustrative example, consider the digraphs in Fig. 2 . They have isomorphic ordinary homology groups, as well as isomorphic homology groups of the associated directed ﬂag complexes. Therefore, for constructing homology theories of digraphs more sensitive to the directionalities, one might need to incorporate the directed combinatorics in the deﬁ- nition of the homology groups. This is partially achieved with the homology theories recalled in the next subsections. 2.2 Path homology Path homology can be considered as a homology theory of directed graphs, explicitly constructed from the edges of the digraphs. It was introduced in Grigor’yan et al. (2013), Grigor’yan et al. (2020), and it has nowadays many developments. We recall its deﬁnition, following the ﬁrst works on the subject. 123 Hochschild homology, and a persistent approach via… Deﬁnition 2.8 Let V be a ﬁnite set. For p ∈ N,an elementary p-path on V is an ordered sequence i ... i of p + 1 elements of V . 0 p Let K be a ﬁeld (this assumption may be relaxed, but for the sake of reference, we use here the same assumptions as in Grigor’yan et al. (2013)). The vector space over K consisting of formal linear combinations of elementary p-paths is denoted by (V ),orsimplyby . The basis element of (V ) corresponding to the elementary p p p p-path i ... i is denoted by e and the elements of (V ) are called paths. 0 p i ...i p 0 p The linear maps ∂(e ) := (−1) e deﬁne the boundary operator i ...i 0 p q=0 i ...i ...i 0 q p ∂ : → , hence a chain complex (Grigor’yan et al. 2020, Lemma 2.1). p p−1 Deﬁnition 2.9 (Grigor’yan et al. 2020, Deﬁnition 3.1) A path complex over V is a non-empty collection P of elementary paths on V with the property that if i ... i 0 p belongs to P, then also i ... i and i ... i belong to P. The paths in P are called 0 p−1 1 p allowed. For a path complex P on a set V , the vector space A (P) spanned by all the allowed p-paths from P is a subspace of . Deﬁne the subspace (P) of A (P) as p p p (P) := v ∈ A (P) | ∂v ∈ A (P) . p p p−1 The elements of (P) are called the ∂-invariant paths of P. Then the boundary operator ∂ restricts to a boundary operator on (P) (Grigor’yan et al. 2020, Sect. 3.2), and provides a chain complex ( (P), ∂). Deﬁnition 2.10 The path homology groups PH (P) of the path complex P are the homology groups of the chain complex ( (P), ∂). To every directed graph there is an associated path complex (Grigor’yan et al. 2020, Ex. 3.3). If G = (V , E ) is a digraph, an elementary p-path i ... i is allowed 0 p if (i , i ) ∈ E for all k = 1,..., p. The set of allowed p-paths on G is denoted by k−1 k P (G); note that P (G) = V , and P (G) = E. Then, the union P(G) := P (G) is p 0 1 n a path complex. In particular, if G is a digraph, then the path homology of G is deﬁned as the path homology of the path complex P(G), after restricting to the ∂-invariant paths. Remark 2.11 It has been shown that path homology satisﬁes nice functorial properties: for a morphism of digraphs f : G → G one gets a homomorphism f : PH (G ) → 1 2 ∗ ∗ 1 PH (G ) between the associated path homology groups (Grigor’yan et al. 2014, ∗ 1 Theorem 2.10). Furthermore, it has been shown that path homology satisﬁes Kün- neth formulas (Grigor’yan et al. 2017) and analogous properties to the classical Eilenberg-Steenrod axioms (Grigorian et al. 2018). The following example illustrates a computation of the path homology groups of the same digraph as in Example 2.6. Example 2.12 We return to the the square-shaped digraph G = (V , E ) on the vertices 0, 1, 2, 3 introduced in Example 2.6. The path complex P(G) associated to G is the complex with elementary allowed paths as depicted below: 123 L. Caputi, H. Riihimäki P ={0, 1, 2, 3}= V 1 3 P ={01, 02, 13, 23}= E P ={013, 023} 0 2 2 All the other P are empty. As the edge (0, 3) does not belong to G, the paths e and n 013 e are not ∂-invariant. However, the linear combination e − e would be, as 023 013 023 ∂(e − e ) = e − e + e − e + e − e = e + e − e − e . 013 023 13 03 01 23 03 02 13 01 23 02 Therefore, if K is a ﬁeld, then = e , e , e , e , = e , e , e , e and 0 0 1 2 3 1 01 02 13 23 = e − e . The associated path homology of G is then PH (P(G)) K 2 013 023 0 and it is 0 in higher dimensions. This can be shown by direct computation from the chain complex ( (P), ∂), or by using the fact that the square digraph is contractible (Grigor’yan et al. 2014, Example 3.13). Observe that if we add the edge (0, 3) to G the spaces and become = e , e , e , e , e and = e , e , 1 2 1 01 02 13 23 03 2 013 023 but the path homology groups do not change. We conclude this subsection with a note on the computability of path homology. Despite the apparent computational complexity, path homology is amenable to com- putations; for example, in dimension 2, for digraphs with 4000 vertices and ca. 25K edges (Grigor’yan 2022). The interested reader can ﬁnd the description and applica- tions of an algorithm computing path homology in higher degrees in Chowdhury et al. (2022) (and in the related references). 2.3 Hochschild homology of path algebras Hochschild (co-)homology, introduced by Hochschild (1945), is a natural invariant of associative, not necessarily commutative, unital algebras. An investigation of this homology theory is beyond the purposes of this work, and we refer to Loday (1998) for a general and comprehensive overview on the subject. To each digraph G,we associate an algebra RG, called the path algebra—see Deﬁnition 2.20. The path algebra is associative and, for ﬁnite digraphs, also unital. Therefore, Hochschild homology groups of RG give (algebraic) invariants of digraphs. Goal of this section is to review some properties of Hochschild (co-)homology, and to introduce a new characteristic of digraphs (Deﬁnition 2.29). 2.3.1 Hochschild homology We ﬁrst recall the deﬁnition of Hochschild homology, following (Loday 1998, Sect. 1.1). For a commutative ring R,let A be an associative unital R-algebra; for example, A can be a polynomial algebra over R. For a bimodule M over A,let A bimodule over the algebra A is an R-module endowed with an action of A both on the left and on the right, such that (am)a = a(ma ) for all a, a ∈ A,and m ∈ M. The actions are compatible, and if A is unital, the unit acts as the identity. 123 Hochschild homology, and a persistent approach via… C (A, M ) be the R-module ⊗n C (A, M ) := M ⊗ A deﬁned as the tensor product of M and n copies of A (all the tensor products being over R). The boundary operator, classically denoted by b,isthe R-linear map b : C (A, M ) → C (A, M ) deﬁned as follows: n n−1 n−1 b(m, a ,..., a ) = (ma , a ,..., a ) + (−1) (m, a ,..., a a ,..., a ) 1 n 1 2 n 1 i i +1 n i =1 +(−1) (a m, a ,..., a ) n 1 n−1 In the formula, for simplicity of notation, we have dropped the tensor products. The map b is a boundary operator (Loday 1998, Lemma 1.1.2) and the pair (C (A, M ), b) is a chain complex, called the Hochschild complex. Deﬁnition 2.13 The Hochschild homology groups HH (A, M ) of an associative unital algebra A with coefﬁcients in a bimodule M are the homology groups of the Hochschild complex. When M is the algebra A itself, we use a simpler notation: Notation 2.14 The Hochschild homology groups of an associative unital algebra A with coefﬁcients in A are denoted by HH (A). For illustration, we provide some elementary computations; for further details see Loday (1998). Example 2.15 Let M = A = R be a commutative ring. Then, we have R, if ∗= 0 HH (R) = . 0, otherwise In fact, as tensor products are computed over R and R ⊗ R = R, the chain complex C (R, R) is a copy of R in each degree, and the boundary operator b is either the identity or the zero map, depending on the parity of n. The computation follows. Example 2.16 Let M = A be an associative algebra. Then, HH (A) = A/[A, A] where [A, A] denotes the commutator submodule generated by all the [a, a ]= aa − a a. In fact, for a ⊗ a ∈ C (A, A),wehave b(a ⊗ a ) = aa − a a. In particular, if A is commutative, then we obtain HH (A) A, and for A non-commutative HH (A) 0 0 coincides with its center. 123 L. Caputi, H. Riihimäki We recall that if A is unital and commutative, then the module of Kähler differen- tials (A) is the A-module generated by all the formal differentials da, with a ∈ A, which are R-linear, i.e., d(λa + μb) = λda + μdb for all a, b ∈ A and λ, μ ∈ R, and satisfy the additional product condition d(ab) = adb + bda for all a, b ∈ A. Then the ﬁrst Hochschild homology group of A is isomorphic to (A) over the ring R (Loday 1998, Deﬁnition 1.1.9 and Proposition 1.1.10). Analogously, in higher degrees, the n-th Hochschild homology HH (A) of A is related to the module of n-forms (Loday 1998, Sect. 1.3). Example 2.17 Let A = K[X ] be the polynomial algebra over a ﬁeld K.As A is a commutative algebra, then HH (A) A. The ﬁrst Hochschild homology group is isomorphic to the ideal (X ) of A. In fact, by Loday (1998, Proposition 1.1.10) it is isomorphic to the module of Kähler differentials (A), and this latter is generated by X. All its higher Hochschild homology groups are zero. Remark 2.18 Note that the Hochschild homology groups HH (A, M ) depend on the choice of the ground ring. Non-isomorphic ground rings can lead to different computations—see for example Loday (1998, Sect. 1.1.18). A dual cohomological theory can be easily derived. In fact, the Hochschild coho- mology groups HH (A, M ) of an associative algebra A with coefﬁcients in M can be deﬁned as the homology groups of the cochain complex Hom (C (A, M )) = R n ⊗n Hom (A , M )—cf. Happel (1989), Loday (1998). Remark 2.19 The Hochschild homology construction is functorial in both the bimod- ule M and the algebra A, and for M = A, Hochschild homology is a covariant functor from the category of associative R-algebras to the category of R-modules (Loday 1998, Sect. 1.1.4). More precisely, a bimodule homomorphism f : M → M induces amap f : HH (A, M ) → HH (A, M ) ∗ ∗ ∗ in Hochschild homology by sending the element (m, a ,..., a ) ∈ C (A, M ) to 1 n n the element ( f (m), a ,..., a ) ∈ C (A, M ); the differential b clearly commutes 1 n n with it and induces the required homomorphism of homology groups. Similarly, if M = A and g : A → A is an R-algebra homomorphism, then g extends to the tensor products giving a map (a ,..., a ) → (g(a ),..., g(a )) and providing a morphism 0 n 0 n of chain complexes C (A, A) → C (A , A ); hence, a homomorphism of Hochschild ∗ ∗ homology groups. We note here that the functoriality with respect to R-algebra homomorphisms does not extend to Hochschild cohomology—see, for instance, Loday (1998, Sect. 1.5.5). This lack of functoriality is the reason why we will focus on Hochschild homology, rather than cohomology. 2.3.2 Hochschild homology of path algebras In this subsection we apply Hochschild homology to certain algebras associated to digraphs. All results and proofs provided here are classical, and we claim no originality. 123 Hochschild homology, and a persistent approach via… For computational purposes, we also restrict to the case in which the base ring R is an (algebraically closed) ﬁeld K; we can think of K as the ﬁeld of complex numbers. Let G = (V , E , s, t ) be a (ﬁnite) directed graph. By a path in G we mean a sequence γ = (e ,..., e ) of composable edges e in G such that s(e ) = t (e ). The number 1 n i i +1 i n is the length of the path. For any vertex v of G, we also consider the trivial path e of length 0 at the vertex v. Deﬁnition 2.20 The path algebra KG associated to the digraph G is the K-vector space with a basis consisting of all possible paths in G, and the multiplication being deﬁned on two basis paths γ = (e ,..., e ), γ = (e ,..., e ) by the formula 1 n 1 p (e ,..., e , e ,..., e ), if s(e ) = t (e ) 1 n n 1 1 γγ = . 0, otherwise The following lemma is easily derived from the deﬁnition: Lemma 2.21 The path algebra KG associated to a digraph G is an associative algebra over K, and has a unit if the digraph is ﬁnite. Proof Let γ, γ ,γ be paths in G. Then, by deﬁnition of product of paths, both (γ γ )γ and γ(γ γ ) are given as concatenation of paths if they are all compatible, and are both 0 otherwise (by bilinearity). Since the algebra KG is deﬁned as a vector space generated by the possible paths in G, this is enough to show its associativity. If the digraph G is ﬁnite, then the element e = e v∈V (G) is a unit. In fact, if γ = (e ,..., e ) is a path of G, then e γ = γ and γ e = γ , 1 n s(e ) t (e ) 1 n where e and e are the constant paths at s(e ) and t (e ), respectively. All the s(e ) t (e ) 1 n 1 n other products with paths of type e ,for v avertexof G, are zero; hence we have eγ = e γ = γ , and γ e = γ e = γ . s(e ) te 1 n The path algebra KG is generated (as an algebra over K) by all the paths of length at most 1, and the unit is the sum of all trivial paths. More precisely, it has the structure of a graded vector space with grading induced by the length of paths (Brion 2012). Observe that all trivial paths e , with v ∈ V (G), are idempotents of KG,as (e ) = e e = e . v v v v v Furthermore, if v and w are distinct vertices of G, then e e = 0. v w We will be interested in digraphs without oriented cycles. In fact, we have the following: Proposition 2.22 The path algebra KG is of ﬁnite dimension, if and only if G is ﬁnite, connected, and has no oriented cycles. here as a K-vector space. 123 L. Caputi, H. Riihimäki Fig. 3 The linear n-graph I Proof The path algebra KG is generated by the paths of length at most one, this number being bounded by the number of all vertices and edges of G. To prove the statement, it is enough to show that the number of paths of G is ﬁnite if and only if G is ﬁnite and has no oriented cycles. Assume ﬁrst that G is ﬁnite without oriented cycles. Then the number of paths of length l in G is bounded by |E (G)| .If the number of paths of G is inﬁnite, then there is a path of arbitrary large length. In particular, there exists a path γ with length greater than the number of vertices of G. This leads to a contradiction, because there exists a vertex v of G encountered twice by γ , hence an oriented cycle. Conversely, any inﬁnite connected graph has inﬁnitely many paths; if the graph G is ﬁnite, but it contains at least an oriented cycle γ , then we can generate inﬁnitely many paths by iterative compositions of such γ with itself. We proceed with some elementary examples of path algebras: Example 2.23 The simplest graphs to consider are given by the graph G with a single vertex v, the directed graph G with a vertex v and a loop e at v, and the digraph G with 1 2 two vertices v ,v and a directed edge e = (v ,v ) between them. The associated 0 1 1 0 1 path algebras are given by the base ﬁeld K, the polynomial ring K[X ], and by the ring of upper triangular (2 × 2)-matrices. More generally, if I is the graph illustrated in Fig. 3, then the path algebra KI is isomorphic to the ring of upper triangular (n × n)- matrices. An isomorphism can be described by sending the trivial path e to the entry (i , i ), and edge (v ,v ) to the entry (i , i + 1). i i +1 Observe that the map assigning to a digraph its path algebra is functorial: Remark 2.24 The assignment G → KG associating the path algebra KG to a digraph G extends to a functor from the category of directed graphs to the category K-Alg of associative K-algebras. To see this, observe that a morphism of digraphs sends paths to paths, thus induces a K-linear map between the vector spaces, and preserves the composition of paths. As a consequence, the induced map between the associated path algebras uniquely extends by linearity to a K-algebra homomorphism. Hochschild homology of associative path algebras is functorial—see Remark 2.19. Then, the composition K− HH Digraph − − → K-Alg −−→ Vect (4) describes the Hochschild homology of the path algebra of a (ﬁnite) digraph as a functor on the category Digraph with values in the category Vect of vector spaces over K. Computations of Hochschild (co-)homology groups may be difﬁcult for arbitrary associative algebras, but when A is the path algebra KG of a directed graph, compu- tations are easier and reﬂect the combinatorial properties of the digraph G.First,itis a standard fact that the path algebra associated to a digraph is a hereditary algebra, 123 Hochschild homology, and a persistent approach via… i.e., all submodules of its projective modules are projective. In fact, modules over a path algebra have a standard resolution of length 1 (Brion 2012, Proposition 1.4.1), and as a consequence the Hochschild homology groups HH (A) of the path algebra A vanish in degree ≥ 2. In degrees 0 and 1, the computation is due to Happel (1989) (see also Redondo 2001, Proposition 4.4): Theorem 2.25 If G = (V (G), E (G), s, t ) is a connected directed graph without oriented cycles and K is an algebraically closed ﬁeld, then ⎪ 1, if i = 0 dim HH (A) = dim HH (A) = 0, if i > 1 K K i 1 − n + dim e Ae , if i = 1 K t (e) s(e) e∈E (G) where A = KG is the path algebra of G,n =|V (G)| is the number of vertices of G and e Ae is the subspace of A generated by all the possible paths from s(e) to t (e) s(e) t (e) in G. In general, for inﬁnite digraphs, or digraphs admitting cycles, this computation can not be used and the ﬁrst Hochschild homology group is of inﬁnite rank. Example 2.26 Let G be the digraph with a vertex v and the single directed edge (a loop) (v, v). The path algebra KG is isomorphic to the polynomial algebra K[X ].This is a commutative algebra over K, hence by Example 2.17, we get K[X ], if i = 0 HH (KG) = (X ), if i = 1 0, if i > 1, which is not ﬁnite over K. In concrete applications, one avoids the case of digraphs with paths of inﬁnite length by restricting to some special classes of acyclic directed subgraphs. In such restricted context, we observe that Hochschild homology can be seen as a functor with values in the category of (graded) vector spaces of ﬁnite dimension: Remark 2.27 Theorem 2.25 implies that, when restricting to digraphs without oriented cycles, the associated Hochschild (co-)homology groups are vector spaces of ﬁnite dimension. Let Digraph be the subcategory of Digraph consisting of ﬁnite digraphs without oriented cycles and induced morphisms of digraphs. Then, the composition in Eq. (4) induces the composition of functors K− HH Digraph − − → K-Alg −−→ FinVect where now the target category FinVect is the category of ﬁnite-dimensional vector spaces over K. We give a concrete example: 123 L. Caputi, H. Riihimäki Fig. 4 Regular morphism of digraphs φ(v ) = w i i Example 2.28 Let φ : G → G be the regular morphism of digraphs illustrated in Fig. 4 1 2 , and deﬁned by sending v to the vertex w ,for i = 0, 1, 2. The morphism φ sends paths i i of G to paths of G of the same length, thus inducing by K-linearity an homomorphism 1 2 of vector spaces φ : KG → KG . In terms of basis elements, the trivial path e is ∗ 1 2 v sent to the trivial path e , whereas the basis elements corresponding to the 1-paths (v ,v ), (v ,v ), and (v ,v ) are sent to those of KG corresponding to (w ,w ), 0 1 0 2 1 2 2 0 1 (w ,w ), and (w ,w ). The tensor product operations are clearly compatible. As in 0 2 1 2 Remark 2.27, we get morphisms φ : C (KG , KG ) = KG ⊗ ··· ⊗ KG −→ KG ⊗ ··· ⊗ KG = C (KG , KG ), n n 1 1 1 1 2 2 n 2 2 hence induced maps between the Hochschild (co-)chain complexes. By applying the functors Hom(−, KG ) to the minimal projective resolutions of KG and KG ,we − 1 2 get a diagram of short exact sequences (for such a computation, see Happel 1989) 3 |V (G )| 4 ∼ 1 0 KK K K 0 φ φ Id ∗ ∗ 4 |V (G )| 8 ∼ 2 0 KK = K K 0 where the maps are induced by identiﬁcation of paths of length 0 (central map) and of the paths (v ,v ), (v ,v ), (v ,v ), and (v ,v ,v ) with the respective ones in G 0 1 0 2 1 2 0 1 2 2 (rightmost map). Focusing on the ﬁrst Hochschild homology groups HH (KG ) K and 1 1 HH (KG ) K , this roughly describes the functoriality of Hochschild homology 1 2 by means of the paths in the digraphs; the ﬁrst Hochschild homology groups being obtained as alternating sums of the vector spaces appearing in the horizontal diagrams of the short exact sequences. In general, descriptions of the Hochschild homology groups are not easy. In this work, we use the computation of Theorem 2.25 as handleable—considering in the summation only simple paths. In order not to loose the information captured by the number of cycles, we will also consider the following characteristic measure: 123 Hochschild homology, and a persistent approach via… Deﬁnition 2.29 Let G = (V (G), E (G), s, t ) be a digraph, and A = KG the path algebra of G over a ﬁeld K.The Hochschild characteristic of G is deﬁned as ⎛ ⎞ ⎝ ⎠ X (G) = dim HH (A) − 1 − n + dim e Ae + C (G) HH k 0 k t (e) s(e) e∈E (G) where n =|V (G)|, the sum over e ∈ E (G) only counts simple paths, and C (G) is the number of simple oriented cycles in G, i.e. cycles with only the ﬁrst and last vertices being equal. Note that the Hochschild characteristic agrees with the Euler characteristic of the Hochschild chain complex associated to the path algebra KG,if G has no ori- ented cycles and K is algebraically closed. The deﬁnition of Hochschild characteristic extends then to any ﬁeld. We conclude with some illustrative examples. Example 2.30 Consider the coherently oriented cyclic graph C ,for n ≥ 2, and the lin- ear n-graph I —see Figs. 1 and 3, respectively. Then, we get X (C ) = X (I ) = n HH n HH n 1. From the point of view of the Hochschild characteristic, linear graphs and cycles are not distinguishable. More generally, observe that a connected digraph whose underlying graph is iso- morphic to a linear graph has always Hochschild characteristic 1. Likewise, if the digraph is a polygon, or it differs from a polygon only for one edge (such edge having the opposite orientation). All other digraphs whose underlying unoriented graph is iso- morphic to a cyclic graph have Hochschild characteristic 0. Therefore, the following holds: Proposition 2.31 Let G be a (simple) connected digraph. Then, • if its underlying unoriented graph is isomorphic to a linear graph, then its Hochschild characteristic is 1; • if its underlying unoriented graph is isomorphic to a polygonal graph, then its Hochschild characteristic is either 0 or 1. Example 2.32 We apply the Hochschild homology computation of Theorem 2.25 to the square digraph G of Examples 2.6 and 2.12. The Hochschild homology group in degree 0 is isomorphic to K, whereas the dimension of HH (KG) is 1. The computation in degree 1 changes if we add to G the edge (0, 3), giving dim HH (KG) = 4. As a K 1 consequence, the Hochschild characteristics of the two graphs are 0 and −3. Observe that if we consider the cycle with a diagonal (rather than the square with a diagonal) we get Hochschild characteristics equal to 0 (with the edge (v ,v ) decreasing it). 0 2 We remark here that the computation of the Hochschild characteristics requires counting all simple cycles in the digraph. This is exponential, and, consequently, computations for large digraphs are rather demanding. 123 L. Caputi, H. Riihimäki 2.4 A view towards other approaches We conclude this survey section by reviewing some generalizations and other approaches to (co-)homology theories of digraphs; the literature on the subject is very rich, and this survey is far from being exhaustive. • A generalization of the homology of directed graphs as the homology of the asso- ciated ﬂag complex (see Sect. 2.1) is given by the homology of the so-called ﬂag tournaplex (Govc et al. 2021). In fact, when a directed graph has no recipro- cal edges the associated ﬂag tournaplex is isomorphic to the ﬂag complex of the underlying undirected graph. The ﬂag tournaplex of a digraph has been employed as a classiﬁer in Govc et al. (2021), combined with directionality invariants and persistent homology methods. • The theory of path homology for digraphs, as developed in Grigor’yan et al. (2020), has been further extended to multigraphs and quivers (Grigor’yan et al. 2018)or to more general path algebras, e.g., to the realm of differential algebras (Ren and Wang 2021). It has also a cohomological counterpart (Grigorian et al. 2015). This has also been extended to a persistent path homology approach—see for instance Dey et al. (2022). • Hochschild homology can be endowed with an additional differential of degree 1, usually denoted by B, turning it into a mixed complex (Kassel 1987). The additional differential B leads to the construction of the so-called cyclic homology, and to its variations negative cyclic homology and periodic cyclic homology of algebras— see also Loday (1998). Therefore, application of such homology theories to the path algebra of a digraph may lead to other invariants, extending the approach surveyed in Sect. 2.3.2. • Ordinary homology groups of digraphs, and the Hochschild homology groups of the associated path algebras, have natural generalizations to the categorical framework. One way to do so is by replacing the path algebra of Deﬁnition 2.20 with a suitable (freely generated) category Path(G), called the path category— see also the discussion below. In a similar fashion, instead of constructing the path algebra or the path category, one can associate to a directed graph other mathematical objects, for example the so-called path posets P(G). First introduced by Turner and Wagner (2012), the path poset has been recently used to deﬁne new combinatorial cohomologies of digraphs (Caputi et al. 2021a, 2022c), and that can be generalized to arbitrary monotone properties of graphs (Caputi et al. 2022b). This approach seems to be related to other topological/combinatorial invariants of simplicial complexes (Caputi et al. 2022a). • Among other approaches, sheaf homology has been used with some applications to the Max-Flow Min-Cut theorem (Krishnan 2014), as well as a directed approach to algebraic topology built upon cohomology of small categories with coefﬁcients in natural systems as in Baues and Wirsching (1985) and Dubut et al. (2015) and in the references therein. 123 Hochschild homology, and a persistent approach via… We can illustrate these various approaches in the following (non-commutative) diagram Cat Free Poset P H SCpx dFl Homologies of digraphs DiGraph Ab HH K− K-Alg where we synthetically show the construction of homology theories of digraphs as representations of the category DiGraph. Note that path homology does not appear in the picture because it is not yet known if it factors through simplicial complexes/algebras/posets/categories. We wish to spend a few more words on the path category and related homology theories, as these are close to the Hochschild homology of path algebras. The path category Path(G) associated to a directed graph G is the category freely generated by the paths of G. There is a forgetful functor from the category Cat of small categories and functors to the category of quivers (thought of as directed graphs with loops and multiple edges). Such forgetful functor has a left adjoint, the functor sending a quiver to the free category on that quiver (see e.g., MacLane 1971, Sect. II.7). As each directed graph is, in particular, also a quiver, one gets a functor Free : DiGraph → Cat (5) from the category of digraphs to the category of small categories. It is easy to see that Free(G) is in fact the path category Path(G). Then, the functor in (5) allows one to use homology theories of categories for obtaining new invariants of digraphs. The naive idea of directly computing the homology groups of the category Path(G) (with constant coefﬁcients), would not give new information due to the following (see Citterio 2001, Ex. 4.3): Proposition 2.33 The classifying space |N (Path(G))| of the path category of a directed graph G has the homotopy type of the geometric realization |G| of the digraph G. However, more interesting homology theories arise when considering the homology of categories with coefﬁcients in functors (Gabriel and Zisman 1967, App. 2). In this framework, one considers the homology groups of Path(G) with twisted coefﬁcients in the same spirit as in usual homology of topological spaces but with local coefﬁcients (see also Quillen 1973, Sect. 1). Remarkably, this point of view has been used in node embedding and community detection problems (Kaul and Tamaki 2020). 123 L. Caputi, H. Riihimäki 3 Connectivity structures and digraphs As outlined in Sect. 2, homology theories of digraphs are ﬂexible and versatile tools, able to capture various topological information from the input graphs. However, as we will show with examples in Sect. 3.2, these homology theories might miss some combinatorial information inherent in the digraph structure. Therefore, with the aim of capturing both the topology and combinatorics of digraphs, in this section we will study some special cases of connectivity digraphs, i.e., digraphs constructed by using some combinatorial information of G. For example, connectivity digraphs can be described by edges, paths, sets of edges, or cliques, together with their incidence relations. We will focus on two closely related simplicial connectivity approaches and show that they capture the combinatorial information described by edges and ordered cliques in a digraph. The ﬁrst one, developed by the second author in Riihimäki (2023) and brieﬂy recalled in Sect. 3.3, generalizes the classical q-connectivity analysis (Atkin 1972, 1974) to the context of ordered simplicial complexes. This construction is based on ordered cliques sharing q-faces respecting a chosen directionality condition. The connectivity digraphs constructed have the additional structure of a preordered set (Deﬁnition 3.13). Then in Sect. 3.4, we investigate the particular case of connec- tivity digraphs built with ordered cliques and codimension 1 incidence relations. The connectivity digraph structure is induced from a total order of simplicial face maps. This choice is shown to generalize the notion of line digraphs (going from the combi- natorics of edges to the combinatorics of higher simplices), giving what we call here the n-path digraphs—cf. Deﬁnition 3.20. 3.1 Connectivity digraphs Goal of this subsection is to introduce the concept of connectivity digraphs. For a digraph G, a connectivity digraph associated to G is meant to encapsulate some com- binatorial information of G. In order to make it formal, we start with the notion of a connectivity structure. Deﬁnition 3.1 A connectivity structure is a triple (G, F, A) consisting of a digraph G, and a non-empty family F of subgraphs of G together with a {0, 1}-valued function A : F × F →{0, 1}. Note that there are no additional requirements on the map A; roughly, a connectivity structure is a way to encode the connectivity properties of families of subsets of G,all at once. For a given connectivity structure (G, F, A) there is an associated well-deﬁned digraph E G (possibly with self-loops) constructed as follows: the set of vertices of E G is the family F, and for H , H in F, there is a directed edge (H , H ) in E G F 1 2 1 2 F if and only if A(H , H ) = 1. We can now give the formal deﬁnition of connectivity 1 2 digraphs. Deﬁnition 3.2 A connectivity digraph is the directed graph E G associated to a con- nectivity structure (G, F, A).A morphism of connectivity structures (G, F, A) → (G , F , A ) is a morphism of digraphs : G → G inducing a function φ : F → F such that A(H , H ) = 1 implies A (φ (H ), φ (H )) = 1. 1 2 1 2 123 Hochschild homology, and a persistent approach via… Before proceeding further, we provide some examples of connectivity structures and associated connectivity digraphs. Example 3.3 Let G be a digraph and let F ={G} be the family consisting of the graph G itself. Then, depending on A, E G can either be the graph with a single vertex and no edges, or the digraph with a vertex and a single self-loop. On the other hand, if F = V (G) consists of the vertices of G, and we set A(v, w) = 1 if and only if (v, w) ∈ E (G), then E G = G. Example 3.4 Let G be a digraph and let F = E (G) be the family consisting of all the edges of G. Set A(e, f ) = 1 if and only if t (e) = s( f ). Then, E G = LG and the associated connectivity digraph is isomorphic to the line digraph. We will investigate this example in detail in the next subsections. On the contrary, if we set A(e, f ) = 1if and only if t (e) = s( f ), then the associated connectivity digraph is sometimes called the complement of LG. Example 3.5 Let G be a digraph and let F = S(G) be the family consisting of all the strongly connected components of G. Set A(S, T ) = 1 if and only if there exists an edge e of G such that s(e) ∈ S and t (e) ∈ T (e). Then, E G CG yields nothing but the condensation of G. Example 3.6 Let G be a digraph and let F ={all the subgraphs of G}. Set A(s, t ) = 1 if and only if s is strictly contained in t. Then, the connectivity digraph E G yields, up to orientation, the Hasse diagram of G. Connectivity structures and morphisms of connectivity structures form a category where compositions are induced by compositions of morphisms of digraphs. It is also easy to see that the map which associates to a connectivity structure (G, F, A) the connectivity digraph E G is functorial with respect to morphisms of connectivity structures. The context of connectivity structures is quite general. Different connectivity struc- tures can encode various combinatorial information of digraphs. Our main motivation for introducing connectivity structures is that the associated connectivity digraphs pro- vide domains for the homology theories described in Sect. 2, and then one can extend the class of digraph invariants. We remark here that a deﬁnition similar to Deﬁnition 3.2 has previously appeared in Grigor’yanet al. (2018, Sect. 6) in the form of a connectivity multigraph of a CW- complex, and meant to extend Atkin’s connectivity graphs (see Sect. 3.3): the vertices of the multigraph are the n-cells and two vertices are adjacent if the corresponding cells share a face. This graph is given the structure of a directed graph by ﬁrst numbering all the cells, and then using this enumeration for describing the directions of the edges. Our construction of connectivity digraphs, and our two main examples of simplicial connectivities provided in Sects. 3.3 and 3.4, do not require a predetermined enumera- tion of the vertices, making the deﬁnition of connectivity digraphs more intrinsic. We also give a more immediate recipe for connectivity digraphs; in fact, Deﬁnition 3.1 essentially provides the adjacency matrices. 123 L. Caputi, H. Riihimäki 3.2 Motivating examples We start by motivating our combinatorial constructions, provided in Sects. 3.3 and 3.4, with some examples. Speciﬁcally we construct non-isomorphic digraphs, such that all the homology theories introduced in Sect. 2 fail to distinguish them. Then, we will see that the same homology theories, applied to the connectivity digraphs, are able to distinguish them—see Examples 3.15, 3.34, and 3.35, proving that encoding the combinatorics is quite helpful. Example 3.7 Consider the following directed graphs: 1 3 1 3 G = and G = 1 2 0 2 4 0 2 4 The two digraphs are not isomorphic. For example, the total degree of the vertex 2 in G is 4 with out-degree 1, but there are no vertices of out-degree 1 and total degree 4 in G . First, observe that the directed ﬂag complexes associated to G and G are both 2 1 2 contractible. Hence, the associated simplicial homology groups are isomorphic. Following Sect. 2.2, we ﬁnd the ∂-invariant paths for G and G : (G ) = 1 2 2 1 {e , e , e } and (G ) = ∅, and (G ) ={e , e , e , e − e } and 012 312 324 3 1 2 2 012 123 243 013 023 (G ) ={e }, and all the other , with n ≥ 3, are empty. The and are 3 2 0123 n 1 0 always spanned by the edges and vertices, respectively. Therefore, we get the chain complexes: ( (G ), ∂) = 0 → (G ) → (G ) → (G ) ∗ 1 2 1 1 1 0 1 ( (G ), ∂) = 0 → (G ) → (G ) → (G ) → (G ). ∗ 2 3 2 2 2 1 2 0 2 The homology groups of these chain complexes are both trivial and concentrated ∼ ∼ in degree 0, with the only non-trivial path homology groups PH (P(G )) K = = 0 1 PH (P(G )). 0 2 In the case of the Hochschild homology of the path algebras, as both graphs are acyclic, we can use Theorem 2.25. This gives us isomorphic K-vector spaces in all degrees (with both dim HH (KG ) and dim HH (KG ) equal to 7). K 1 1 K 1 2 Remarkably, the same homology theories can distinguish the associated line digraphs—the line digraphs having 2 and 1 connected components, respectively; as shown in the following illustration of the associated line digraphs: 123 Hochschild homology, and a persistent approach via… 31 34 32 13 23 43 LG = and LG = 1 2 12 24 02 01 02 01 12 24 This suggests that the directed combinatorics plays an important role. We give another example: Example 3.8 Consider the following digraphs with reciprocal edges: 0 0 S =12 S =12 1 2 3 3 The associated directed ﬂag complexes in both cases are topologically 2-spheres, hence their homology groups are isomorphic. A computation similar to the one in the previous example shows that the associated path homologies are also isomorphic. The Hochschild homology groups of the path algebras associated to the graphs S and S 1 2 are also isomorphic (in degree 1 of inﬁnite dimension over K, both digraphs having oriented cycle). Here follow the associated line digraphs: 13 21 02 02 21 32 LS = and LS = 1 2 01 12 23 01 12 31 Motivated by these examples, we proceed with investigating two examples of (simplicial) connectivity digraphs. 3.3 q-connectivity Our ﬁrst connectivity structure is an extension of Atkin’s Q-analysis (Atkin 1972) as developed in Riihimäki (2023). We brieﬂy summarise this theory as needed for the purposes of this paper, and guide the reader to the previous references for more in-depth expositions. The essential idea in Atkin’s work is the generalisation of edge path connectivity of a simplicial complex to sequences of connected simplices through sharing of faces of certain dimension. Atkin was particularly motivated by the classic 123 L. Caputi, H. Riihimäki work of Dowker (1952): to any relation one can associate two simplicial complexes, nowadays known as Dowker complexes, but the homology groups of these complexes are isomorphic. Atkin’s insight was to associate to a simplicial complex his Q-analysis, which turns out to differentiate between the two Dowker complexes of a relation. Deﬁnition 3.9 Let K be a simplicial complex. Two simplices σ and τ of K are q- near, if they share a q-face. Two simplices σ and τ of K are q-connected, if there is a sequence of simplices in K , σ = α ,α ,α ,...,α ,α = τ, 0 1 2 n n+1 such that any two consecutive ones are q-near. The sequence of simplices is called a q-connection between σ and τ . Similarly to the property of being path connected, we say that the complex K is q-connected if any two simplices in K of dimension greater than or equal to q are q-connected. The notion of q-connectivity is an equivalence relation on the set K of simplices of dimension q and higher, for 0 ≤ q ≤ dim(K ). The aim of Q-analysis is to associate a simplicial complex with its q-connectivity equivalence classes, or its q-connected components. Note that if a simplex σ is max- imal in K with respect to inclusion and dim(σ ) = q, then σ is q-connected only to itself; hence every maximal q-simplex generates its own equivalence class. For each q the equivalence classes encode the connectivity information of the q-upper skele- ton of K . A related notion was introduced in Palla et al. (2005) to study community structures in networks. Deﬁnition 3.10 Let G be a graph and n ≥ 2 a natural number. Two n-cliques in G are connected if there is a sequence of n-cliques of G such that any two consecutive cliques share n − 1 vertices. A n-clique community of G is a maximal set of pairwise connected n-cliques. The n-cliques of a graph are in correspondence with the (n − 1)-simplices in the associated ﬂag complex. The n-clique communities are obtained from the Q-analytical information of the ﬂag complex. Note that we can put the n-cliques as vertices of a graph with edges between vertices if the associated cliques share n − 1 vertices. This leads us to deﬁne our ﬁrst connectivity graph. Deﬁnition 3.11 The q-graph of a simplicial complex K has as its vertices the simplices in K and edges between pairs of q-near simplices. Standard Q-analysis as outlined above fails to take into account directionality in the case of digraphs and directed ﬂag complexes. Consider the cycle and star digraphs in the ﬁgure below. As undirected graphs, or 1-dimensional simplicial complexes, they are indistinguishable by q-connectivity information: both contain one component so they are 0-connected, and the maximal 1-simplices each form their own 1-connected components in both cases. 123 Hochschild homology, and a persistent approach via… 0 d 12 b We therefore introduce a reﬁned version of Q-analysis that is sensitive to the direc- tionality of simplices, or directed cliques in directed graphs. We do this by imposing directions through face maps. Deﬁnition 3.12 Let σ be an n-simplex. We denote by d the face map (v ,..., v ,...,v ), if i < n, 0 i n d (σ ) = (v ,...,v , v ), if i ≥ n. 0 n−1 n The face map d now makes sense in any dimension since it always removes the vertex at position min{i , dim(v)}. The reason to modify the standard face map in this fashion is due to the fact that q-connectivity looks at all the simplices of dimension q and higher. Deﬁnition 3.13 For an ordered simplicial complex K,let (σ, τ ) be an ordered pair of simplices σ ∈ K and τ ∈ K , where s, t ≥ q.Let (d , d ) be an ordered pair of s t i j the i- and j-face maps. Then (σ, τ ) is q-near along (d , d ) if either of the following i j conditions is true: 1. σ→ τ, 2. d (σ ) ←α → d (τ ), for some q-simplex α ∈ K . i j The ordered pair (σ, τ ) of simplices of K is q-connected along (d , d ) if there is a i j sequence of simplices in K , σ = α ,α ,α ,...,α ,α = τ, 0 1 2 n n+1 such that any two consecutive ones are q-near along (d , d ). The sequence of sim- i j plices is called a q-connection along (d , d ) between σ and τ . We simply write this i j connection as (σ α α ...α τ). 1 2 n We will call the above connection (q, d , d )-connection, when the choices of q i j and directions d and d are made, and similarly we say (q, d , d )-near. i j i j The directed (q, d , d )-connectivity is a preorder on the set of directed cliques i j K . By the classical Alexandroff correspondence, preorders and topological spaces are in bijection (Barmak 2011). The (q, d , d )-preorders thus endow a directed graph i j with a collection of new topological spaces. Up to homotopy it is enough to study partial orders obtained by condensing the preorders (Deﬁnition 1.10 and the discussion after). The homotopy types of partial orders can then be studied through their order complexes, i.e. taking the nerve. As our main connectivity digraph stemming from q-connectivity we take the (q, d , d )-nearness digraph in Digraph of the (q, d , d )-connectivity preorder. i j i j 123 L. Caputi, H. Riihimäki For visualisation purposes we use the Hasse diagram form, i.e. we do not draw the self-loops on vertices. Deﬁnition 3.14 For an ordered simplicial complex K the vertices in the (q, d , d )- i j digraph,orsimply q-digraph, are the simplices in K , and for two vertices σ and τ there is a directed edge (σ, τ ) when the pair (σ, τ ) is (q, d , d )-near. i j As an illustrative example we see that our new connectivity digraph can be used to distinguish prior Example 3.8; we refer the reader to Riihimäki (2023) for a more detailed investigations of these connectivity digraphs. Example 3.15 The full (1, d , d )-digraphs of the 2-spheres in Example 3.8 are shown 1 2 below. We use simpliﬁed notation where a simplex (v ,v ,...,v ) is denoted by 0 1 n (v v ··· v ). 0 1 n (01) (01) (02) (02) (012) (021) (012) (021) (12) (21) (12) (21) (123) (213) (312) (321) (13) (31) (23) (32) The connectivity digraphs are different between the spheres. Passing to condensations and order complexes of the associated (1, d , d )-preorders, the homotopy type of the 1 2 1 1 1 left sphere is a wedge of circles S ∨ S , while that of the right sphere is S .The q-connectivity therefore assigns the underlying digraphs with new homotopy types that distinguish them. In the next section we study our second example of a connectivity digraph, and show that it extends to an endofunctor on acyclic digraphs. The next example shows that the (q, d , d )-digraph construction can not induce an endofunctor on acyclic digraphs, i j as it might yield digraphs with oriented cycles and self-loops. Example 3.16 Consider the digraphs below and the morphism φ : G → G deﬁned 1 2 on vertices as 0 → 0 ,1 → 1 ,2 → 2 , and 3 → 0 . 2 2’ G = = G 03 0’ 1 2 1 1’ Morphisms of digraphs send simplices to simplices, in this case both (012) and (312) map to (0’1’2’). The induced morphism φ between the (1, d , d )-digraphs, 0 0 123 Hochschild homology, and a persistent approach via… as illustrated below, then acts on vertices as (012) → (0 1 2 ), (312) → (0 1 2 ), (01) → (0 1 ), (02) → (0 2 ), (12) → (1 2 ), (31) → (0 1 ), and (32) → (0 2 ). (01) (31) (0’1’) (02) (012) (312) (32) (0’2’) (0’1’2’) (12) (1’2’) Note that the edges ((012), (312)) and ((312), (012)) are both sent to the self-loop on (0’1’2’); this is allowed in Digraph and also consistent with the fact that (q, d , d )- i j digraphs inherently arise from the (q, d , d )-connectivity preorders which have all i j the reﬂexive relations. The example suggests the framework for studying the functoriality of (q, d , d )- i j digraphs, as we now shall show. In particular, we do not get an endofunctor on Digraph or Digraph , but take the target category to be Digraph . 0 + Theorem 3.17 The (q, d , d )-digraph construction induces a functor from Digraph i j to Digraph . Proof We write (q, d , d ) for the (q, d , d )-digraph of a digraph G.Let φ : G → G i j G i j 1 2 be a morphism of digraphs. Simplices, i.e. ordered cliques, are mapped to sim- plices; recall Remarks 1.4 and 2.5. Hence, two simplices σ = (v ,...,v ) and τ = 0 n (w ,...,w ) of dmension ≥ q are mapped to simplices φ(σ ) = (φ (v ), . . . , φ (v )) 0 k 0 n and φ(τ ) = (φ (w ), . . . , φ (w )) of dimension ≥ q. The edges in (q, d , d ) coming 0 k i j G from the face inclusions σ→ τ are then trivially sent to edges in (q, d , d ) . i j G Assume the nearness relation d (σ ) ←α → d (τ ) so an edge (σ, τ ) in i j (q, d , d ) .The q-simplex α is mapped to a q-simplex φ(α) in G . Note that i j G 2 there is an order-preserving bijection between the vertices (v ,...,v ) of σ and 0 n (φ (v ),...,φ(v )), and similarly for τ and φ(τ ), due to φ being a morphism of 0 n digraphs. The face maps d and d then act the same way on σ and φ(σ ), and i j τ and φ(τ ), respectively, with respect to the orderings. Therefore, α has to be a selection of vertices (v ,...,v ) from (v ,..., v ,...,v ) with the inherited i i 0 i n 0 q ordering, and (φ (v ), . . . , φ (v )) is a q-simplex in d (φ (v ), . . . , φ (v )). Simi- i i i 0 n 0 q larly the vertices (v ,...,v ) constitute a q-simplex in (w ,..., w ,...,w ), and i i 0 j n 0 q (φ (v ),...,φ(v )) is a q-simplex in d (φ (w ), . . . , φ (w )). This amount to the i i j 0 n 0 q nearness relation d (φ (σ )) ←φ(α)→ d (φ (τ )) and an edge (φ (σ ), φ (τ )) in i j (q, d , d ) . i j G A composition of morphisms of digraphs G → G → G still maps simplices 1 2 3 to simplices, while keeping the dimensions ≥ q and preserving the relative order- ings of vertices. The argument above then induces a composition of morphisms (q, d , d ) → (q, d , d ) → (q, d , d ) . The identity morphism on a digraph i j G i j G i j G 1 2 3 G obviously maps to the identity on (q, d , d ) . i j G 123 L. Caputi, H. Riihimäki 3.4 The n-path digraph Our second example of connectivity digraphs is given by the n-path digraphs (n) {PG } . These are deﬁned as the digraphs with the ordered (n + 1)-cliques of n∈N G as vertices, and with directed edges given by their incidence relations (see Deﬁni- tion 3.20). The construction is a generalization of the line digraph of Deﬁnition 1.7; furthermore, we will show that this construction can be promoted to an endofunctor on the category of digraphs Digraph—cf. Theorem 3.28. Let n be a positive natural number and let G be a directed graph. We start by rephrasing the concept of q-graph of Deﬁnition 3.11, in the speciﬁc case in which the simplicial complex K is the directed ﬂag complex of a digraph G, the simplices have all the same ﬁxed dimension, and the relation is the 1-codimensional q-nearness. Deﬁnition 3.18 Let G be a digraph and let dFl(G) be its associated directed ﬂag com- (n) plex. The n-path graph G associated to G is the graph whose vertices are the n-simplices of dFl(G), and such that two vertices σ and τ are connected by an edge whenever σ and τ share a common (n − 1)-face. Remark 3.19 Note that Deﬁnition 3.18 gives the underlying graph for the n-clique communities (Deﬁnition 3.10). The name n-path graph is then justiﬁed by the fact (n) that simple paths in G correspond to ordered (n + 1)-cliques of G, consecutively (1) connected by common ordered n-cliques. If G is a digraph, then the 1-path graph G associated to G is nothing but the line graph L(G) of the underlying undirected graph associated to G—cf. Deﬁnition 1.7. Let G be a digraph, n be a natural number and dFl(G) be the associated directed ﬂag complex. Based on Deﬁnition 3.18, we now deﬁne the n-path digraphs as the con- nectivity digraphs on the set of ordered (n + 1)-cliques with their incidence relations. The digraph structure is induced from the total order on {0,..., n} which induces a total order on the associated face maps. (n) Deﬁnition 3.20 For n ≥ 1, the n-path digraph PG associated to G is the directed graph with the n-simplices of dFl(G) as vertices. For vertices σ and τ , there is a directed edge (σ, τ ) if and only if there is an (n − 1)-simplex α of dFl(G) and some i , j ∈{0,..., n} such that d (σ ) = α = d (τ ), with i < j . i j (0) When n = 0, we set the 0-th path digraph PG to be the digraph G. Note that the difference of n-path digraph from q-digraph (Deﬁnition 3.14) is that the vertices are only the n-simplices, and the edges are determined by the natural order on face maps; in the case of q-digraphs there is a choice of the (q, d , d ) involved. i j These two methods then yield different connectivity structures as shown in the next example—compare it with Example 3.15. 123 Hochschild homology, and a persistent approach via… Example 3.21 Consider the digraphs S and S of Example 3.8. The associated 2-path 1 2 (2) digraph PS is the following: (012) (021) (123) (213) (2) The digraph PS , instead, is a disconnected digraph with two connected compo- nents: (012) (021) (312) (321) We investigate some properties of the n-path digraphs; ﬁrst, note that these path digraphs generalize the notion of line digraphs: (1) Proposition 3.22 When n = 1,the 1-path digraph PG is isomorphic to the line digraph L(G) of G. (1) Proof When n = 1, the vertices of PG are the edges of G. The face map d applied to an edge e of G, gives the source of e: d (e) = s(e). Analogously, we have the (1) relation d (e) = t (e). Consequently, two edges e and f of G are connected in PG by a directed edge (e, f ) if, and only if, they share a common vertex d (e) = d ( f ) 0 1 in G. Then the two constructions in Deﬁnitions 1.7 and 3.20 are equivalent. For a digraph G, denote by Cone(G) the cone digraph obtained from G by adding a new vertex v and, for each vertex v in G, a new directed edge (v, v ); see Fig. 5 for P P an illustration. Proposition 3.23 Let C be the coherently oriented cyclic digraph on n vertices, with n ≥ 3. Then the the 2-path digraph of the cone Cone(C ) is isomorphic to C . n n Proof For n ≥ 3, if C is the cyclic digraph on n vertices with all the edges coher- ently oriented, then the cone Cone(C ) has 2-simplices based at the edges of C . n n For each edge (v ,v ) in C , the edge (v ,v ) of Cone(C ) can be written as i i +1 n i P n d (v ,v ,v ) = d (v ,v ,v ) (where the indices i are taken modulo n). Then, 1 i i +1 P 0 i −1 i P it is easy to check that the associated 2-path digraph is isomorphic to C . The result generalizes by induction to every m: let Cone (G) denote the m-th iterated cone of G, i.e. Cone := Cone ◦ ··· ◦ Cone, m times. Then, we have the following: 123 L. Caputi, H. Riihimäki Fig. 5 The cone Cone(C ) of the coherently oriented cyclic digraph C Proposition 3.24 Let C be the coherently oriented cyclic digraph on n vertices, with n ≥ 3. Then, (m) m P Cone (C ) = C , n n the m-path digraph of the m-th cone Cone (C ) of C is isomorphic (as a directed n n graph) to C . We have seen that, for every m,the m-path digraph can be an oriented cycle. Cycles of ordered n-cliques have a rigid structure, as each subsequent element in the sequence is determined by the preceding one, and by the face maps: Remark 3.25 Let σ and σ be two n-simplices of dFl(G), and assume d (σ ) = d (σ ) i j for i < j, and n > 0. If σ = (v ,...,v ), denote by σ [h] the h-entry v of σ . Then 0 n h we have σ [h] for h < i , h > j σ [h]= σ [h + 1] for i ≤ h < j and σ [ j ] is the vertex in which σ and σ differ. For example, assume σ = (0, 1, 2, 3) and σ = (1, 4, 2, 3); then d (σ ) = d (σ ) and here the face maps correspond to the 0 1 indices i = 0, and j = 1. When h = i = 0, we have σ [0]= σ [1], and σ [h]= σ [h] for h = 2, 3; on the other hand, when h = j (case h = j = 1), we have σ [h]= 4, the vertex in which σ and σ differ. Such rigidity implies that taking n-path digraphs preserves acyclicity: (n) Proposition 3.26 The n-path digraph PG of a digraph G without oriented cycles does not have oriented cycles. 123 Hochschild homology, and a persistent approach via… (n) Proof We proceed by contradiction. Assume PG has an oriented cycle γ given by n-simplices σ → σ → ··· → σ → σ (6) 0 1 k−1 k of dFl(G). All the discussion below is given modulo k. The oriented cycle in Eq. (6) corresponds to a closed path of ordered (n +1)-cliques of G, and for each σ → σ there are indices i and j such that d (σ ) = d (σ ), h h+1 h h i h j h+1 h h with i < j . Without loss of generality assume that i = 0for some h—otherwise h h h let i = min{i | h = 0,..., k} and replace in the discussion below the index 0 with such minimal index i. Starting with the cycle γ , it is now possible to construct oriented closed paths in G as follows. First, as i = 0for some h, then we have σ [1]= σ [0] by Remark 3.25. h h h+1 Furthermore, as the simplex σ represents an ordered clique of G, this means that there is a directed edge e between the 0-th and 1-st entry of σ , i.e. e := (σ [0],σ [1]), h h h h h and we can see e as an edge between the vertices σ [0] and σ [0]. The idea is h h h+1 now to use these edges e to construct a cycle γ in G. To this goal, consider only h 0 the indices h in {0,..., k} for which i = 0, say h ,..., h . For all other indices r, h 0 s we have σ [0]= σ [0], where h := min {h < r }. Then, starting with r h +1 r h ,...,h j r 0 s v := σ [0]= σ [0], we have the sequence of edges 0 0 h e e h h e 0 1 s v = σ [0] − − → σ [0]= σ [0] − − → σ [0]− → ... −→ σ [0]= σ [0]= v 0 h h +1 h h +1 h +1 h 0 0 0 1 1 s 0 terminating again in v ,as γ was a cycle of simplices. But, this is not possible because G has no oriented cycles, leading to a contradiction. In the next example we show that the directed structure inherited by the path digraphs is more informative than the undirected one. We apply the constructions of Deﬁnitions 3.18 and 3.20 to the digraphs shown in Example 3.7: (2) Example 3.27 Let G and G be the graphs of Example 3.7. The 2-path graphs G 1 2 (2) and G have three vertices, corresponding to the three 2-simplices, and two edges, corresponding to the two edges in common; the obtained path graphs are isomorphic. (2) (2) On the other hand, the associated 2-path digraphs PG and PG are not isomorphic. 1 1 In fact, we have the digraph structures (2) PG = ••• (2) PG ••• showing that the extension from 2-path graphs to 2-path digraphs provides additional non-trivial information. We ﬁnish by establishing our main result concerning n-path digraphs, which is their functoriality. 123 L. Caputi, H. Riihimäki Theorem 3.28 For each n in N, (n) (n) P : DiGraph → DiGraph, G → PG is an endofunctor of the category of directed graphs. (n) Proof First, note that if n = 0, then P is the identity functor by deﬁnition; if (n) n = 1, then, by Proposition 3.22, P coincides with the line digraph functor (see Remark 1.8). Let now n ≥ 2. We ﬁrst observe that, if a digraph G has no ordered (n + 1)-cliques, then the associated n-path digraph is the empty digraph. By Remark 1.4, a morphism of digraphs φ : G → G induces a function between the sets of (n + 1)-cliques. As 1 2 a consequence, if G and G are two digraphs and the set of (n + 1)-cliques of G is 1 2 2 empty, then the set Hom (G , G ) of morphisms of digraphs between G and G Digraph 1 2 1 2 is also empty. By Remark 2.5 we also have an induced function between the sets of ordered (n + 1)-cliques of G and G , that preserves the relative order of the faces. 1 2 This function may not be surjective (there might be cliques that are not images of any clique in G ) nor injective (as it may send different cliques to the same one). (n) For a morphism of digraphs φ : G → G , we have got a function P (φ) between 1 2 the sets of vertices of the associated n-path digraphs. We now want to promote it to a morphism of n-path digraphs. To this end, let c, c be two ordered (n + 1)-cliques of G , and let σ and σ be the associated n-simplices in dFl(G ). It may happen that 1 c c 1 (n) P (φ) sends both σ and σ to the same simplex of dFl(G ). However, observe that c c 2 if σ and σ share an (n − 1)-face τ , and are sent to the same n-simplex of dFl(G ), c c 2 then the ordered (n + 1)-cliques c, c share the face τ such that there exists an index i with d (σ ) = d (σ ) = τ (as the linear ordering should be preserved). Therefore, i c i c (n) if σ and σ are collapsed to the same vertex of PG , then σ and σ represent c c c c (n) two non-adjacent vertices of PG . Furthermore, the relative incidence relations are (n) preserved, and the morphism of digraphs φ : G → G induces a function P (φ) such 1 2 (n) (n) (n) (n) that (P (φ)(σ ), P (φ)(σ )) ∈ PG for every (σ ,σ ) belonging to PG , i.e. c c c c 2 1 (n) P (φ) is a morphism of digraphs. (n) To conclude, it is now easy to see that P of the identity is the identity and that, (n) (n) (n) if φ and φ are morphisms of digraphs, then P (φ ◦ φ ) = P (φ ) ◦ P (φ ). 1 2 1 2 1 2 (n) This shows that P is an endofunctor of the category Digraph. By Proposition 3.26, we get also the functoriality when restricting to acyclic digraphs: (n) Proposition 3.29 The funtor P restricts to a functor DiGraph → DiGraph on 0 0 the category of ﬁnite digraphs without oriented cycles. Remark 3.30 The idea behind Deﬁnition 3.20 corresponds to the intuition that ﬂows in a directed graph follow the direction of the edges, from the source to the target. As we have remarked in Lemma 3.22, the source and target of a directed edge are given by the face maps d and d , respectively. The condition i < j in the construction of 1 0 the path digraph follows and generalizes this principle to the higher simplices as well. 123 Hochschild homology, and a persistent approach via… This condition can be relaxed to i ≤ j, which has the effect that the path digraphs might have reciprocal edges, and therefore oriented cycles. As described in Sect. 2.1, one of the possible approaches to a homology theory of digraphs is given by the ordinary homology of the associated directed ﬂag complexes; recall that this is constructed by using the set of ordered cliques in a digraph. When applied to 1-path digraphs, we have the following consequence: Remark 3.31 Let G be a digraph without oriented cycles. Then, the directed ﬂag com- (1) plex dFl(PG (G)) = dFl(L(G)) of the 1-path digraph has simplices of dimension at most 1. The above remark is not true for n-path digraphs. For example, it is easy to see that the 2-path digraphs may contain 3-cliques, and as a consequence the associated directed ﬂag complexes can possibly be of dimension at least 2: Example 3.32 Consider the digraph G on ﬁve vertices with directed edges as follows: 1 3 0 2 Then G contains three ordered cliques, corresponding to the simplices (0, 1, 2), (1, 2, 3) and (1, 4, 2). The boundary relations show that the associated 2-path digraph is the ordered clique on three vertices, and the associated directed ﬂag complex is a 2-simplex. In the case of q-connectivity the homotopy types of the connectivity digraphs can be studied through the order complex construction, recall Example 3.15. Analogously, it is then natural to ask what is the dimension of the directed ﬂag complex of an n-path digraph, and what is its homotopy type: Question 3.33 For a given digraph G, what is the homotopy type of the directed ﬂag (n) complex associated to PG ,ortothe relaxed n-path digraph of Remark 3.30? What are the distributions of the associated Betti numbers like? A partial answer to this is given in Riihimäki (2023) when G is the 1-skeleton of so called pseudomanifold; for example, the Cone(C )inFig. 5 is an example of a directed 2-pseudomanifold. In this case the directed ﬂag complexes of the connectivity digraphs we have considered are 1-dimensional. The digraph in Example 3.32 does not have the structure of a 2-pseudomanifold: there is a "singular" edge (1, 2) to which three different 2-simplices are attached. We conclude this section with examples showing that the digraphs of Examples 3.7 and 3.8 can now be distinguished by using the homology groups associated to the 2-path digraphs: 123 L. Caputi, H. Riihimäki Example 3.34 Consider the digraphs G and G illustrated in Example 3.7. The asso- 1 2 (2) ciated 2-path digraph PG —cf. Example 3.27—has two connected components, (2) whereas the 2-path digraph PG has one connected component. Then all the homology theories described in Sect. 2 can now distinguish the two digraphs. Example 3.35 For the digraphs S and S of Example 3.8 the associated 2-path 1 2 (2) (2) digraphs PS and PS have one and two connected components, respectively. 1 2 Again, all the homology theories described in Sect. 2 can distinguish these two digraphs representing 2-spheres. 4 Persistent Hochschild homology of digraphs The goal of this section is to introduce a persistent homology framework for Hochschild homology of directed graphs, using connectivity digraphs as an intermediate step. One of the disadvantages of Hochschild homology for digraphs is that it is trivial in degrees i ≥ 2. The use of connectivity digraphs is meant to solve this issue. We ﬁrst show that the n-path digraphs introduced in Sect. 3.4 allow us to construct a persistent homology functorially in the case of acyclic digraphs. We then extend the persistence pipeline to general digraphs; we lose functoriality but we obtain a new persistence descriptor for digraphs. 4.1 Persistent Hochschild homology of acyclic digraphs In this subsection we mainly follow Bergomi and Vertechi (2020), where an abstract categorical framework in which to develop persistent homology theories has been introduced. In this framework, one replaces ﬁltrations of topological spaces with ﬁl- trations in an arbitrary category (for us, the category of directed graphs) and the homology functors with any functor with values in a regular ranked category (for us, Hochschild homology over a ﬁeld K), compare with Bergomi and Vertechi (2020, Table 1). To accomplish our aims we could have also used the generalised persistence of Patel (2018); we think, however, that the theory in Bergomi and Vertechi (2020) provides a more straightforward passage to our aims. We start by considering the poset (R, ≤) of real numbers with the induced natural partial order ≤. The poset (R, ≤) can be seen as a category in a standard way, as every poset can be seen as a category: the category P associated to a poset P = (S, ≤) has the set S as a collection of objects and a (unique) morphism x → y for any x ≤ y.A morphism of posets is then a functor between them, equivalently an order-preserving map of posets. In persistent homology applications, one usually considers diagrams of spaces indexed by the natural numbers, or more generally by the real numbers. These diagrams are referred to as ﬁltrations: Deﬁnition 4.1 A (real-indexed) ﬁltration in a category C is a functor F : (R, ≤) → C. Remark 4.2 Following Bergomi and Vertechi (2020) we will always consider tame ﬁltrations. Essentially, a ﬁltration F is tame if there is a ﬁnite sequence {t } such i i ∈N 123 Hochschild homology, and a persistent approach via… that F (a) → F (b) may fail to be an isomorphism only if a < t ≤ b for some i.The concept of tameness extends to subposets of (R, ≤). Example 4.3 Let {G } be a family of digraphs, with G → G a morphism of n n∈N n n+1 digraphs for each n ∈ N. Then, the family {G } yields a ﬁltration (N, ≤) → n n∈N Digraph; if we assume G to be without oriented cycles, the ﬁltration takes values in Digraph . Observe that if {G } is a family of subgraphs of a given directed graph n n∈N G, then by Remark 4.2 the resulting ﬁltration is tame. Let F be a ﬁltration in Digraph . In the following discussion, we restrict to the (n) (n) n-path digraph functor PG , but everything is the same by replacing PG with any functorial construction of connectivity digraphs. By Theorem 3.28, composition with (n) the n-path digraph functor PG induces, for each n in N, a ﬁltration in Digraph ; by Proposition 3.26,the n-path digraph of a digraph without oriented cycles does not have oriented cycles. We then get the following composition of functors: (n) F P (R, ≤) − → Digraph −−→ Digraph . 0 0 Let FinVect be the category of ﬁnite dimensional vector spaces over an algebraically closed ﬁeld K. By Remark 2.27, the Hochschild homology groups yield functors with values in FinVect. Remark 4.4 The category FinVect, equipped with the dimension function assigning to a vector space its dimension, is a ranked category—cf. Bergomi and Vertechi (2020, Deﬁnition 2.1). Before putting all together, we need the deﬁnition of a persistence function, generalizing persistent Betti numbers from classical persistent homology: Deﬁnition 4.5 (Bergomi and Vertechi 2020, Deﬁnition 3.2) Let C be a category. An integer-valued lower-bounded function p on the morphisms of C is a categorical persistence function if, for all u → u → v → v the following hold: 1 2 1 2 1. p(u → v ) ≤ p(u → v ) and p(u → v ) ≤ p(u → v ); 1 1 2 1 2 2 2 1 2. p(u → v ) − p(u → v ) ≥ p(u → v ) − p(u → v ). 2 1 1 1 2 2 1 2 Let F : (R, ≤) → Digraph be a ﬁltration, and consider the following composition of functors: (n) F P K− HH (R, ≤) − → Digraph −−→ Digraph − − → K-Alg −−→ FinVect (7) 0 0 By Bergomi and Vertech (2020, Proposition 3.6), any functor C → FinVect yields a categorical persistence function. In order to get an analogue of persistent Betti numbers usually associated to pairs of real numbers, it is then sufﬁcient to have a ﬁltration and a categorical persistence function (Bergomi and Vertechi 2020, Remark 3.8). In our context, F : (R, ≤) → Digraph is a ﬁltration, and the composition of functors in (7) 123 L. Caputi, H. Riihimäki yields the categorical persistence function. Furthermore, for each pair of real numbers u ≤ v, Hochschild homology gives the linear maps (n) (n) (n) (n) HH (KPG ) → HH (KPG ) and HH (KPG ) → HH (KPG ) 0 0 1 1 u v u v of ﬁnite dimensional vector spaces. By taking the images of these maps, we get the desired persistent Betti numbers: Deﬁnition 4.6 The (n, 1)-persistent Betti number of a ﬁltration in Digraph is the (n) (n) persistent Betti number induced by HH (KPG ) → HH (KPG ), in dimension 1 1 1. The (n, 0)-persistent Betti number for dimension 0 is deﬁned analogously. Remark 4.7 Note that degrees of Hochschild homology are only 0 and 1. The higher "homological" degrees n, and the n-th Betti numbers, are deﬁned by the connectivity digraphs of n-simplices. This is in our view the lifting of Hochschild homology beyond degree 1. In this functorial framework, given a categorical persistence function p and a (tame) ﬁltration F, it is possible to deﬁne a persistence diagram DF as well (Bergomi and Vertechi 2020). In the case of real-indexed ﬁltrations, the morphisms u ≤ v ∈ R are + 2 in bijection with the positive half-plane ={(u,v) ∈ R | u ≤ v}. We therefore get an induced persistence function p : → Z given by (u,v) → p(F (u ≤ v)). For u <v we deﬁne the multiplicity μ(u,v) as min{ p (sup(I ), inf(I )) − p (inf(I ), inf(I )) − p (sup(I ), sup(I )) u v u v u v F F F I ,I u v +p (inf(I ), sup(I ))}, u v where I and I range over disjoint connected neighborhoods of u and v. The persis- u v tence diagram DF associated to p is then deﬁned by those points (u,v) such that μ(u,v) > 0, together with the diagonal {(u, u) | u ∈[0, ∞)} (Bergomi and Vertechi 2020, Deﬁnition 6). Note that for small enough neighborhoods I and I we have u v inf(I ) → sup(I ) → inf(I ) → sup(I ), and the above minimized expression is u u v v exactly that of condition 2. in Deﬁnition 4.5 with strict inequality. We get an immediate stability theorem, in fact an isometry theorem, between our Hochschild homology valued ﬁltrations and their persistence diagrams. Let d (F , G) be the interleaving distance between two ﬁltrations F , G : (R, ≤) → FinVect FinVect and let d(DF , DG) be the bottleneck distance between the associated persistence diagrams. Theorem 4.8 Let F , G : (R, ≤) → Digraph be two ﬁltrations of digraphs. Then, (n) (n) d (HH ◦ KP ◦ F , HH ◦ KP ◦ G) = d(DF , DG) FinVect 1 1 where DF and DG represent the persistence diagrams associated to F and G. Proof The proof follows directly from Bergomi and Vertech (2020, Theorem 3.27 and 3.29). 123 Hochschild homology, and a persistent approach via… The theorem says that the persistent Hochschild homology groups associated to a ﬁltration of digraphs are stable, one of the main required properties in persistent homology applications. We refer to this as persistent Hochschild homology (PHH). Note that, in the terminology of Bubenik et al. (2015), we have introduced a generalised persistence along with a hard stability theorem: the map from persistence modules to discrete invariants is 1-Lipschitz. This still leaves open the (very hard) problem of proving a stable persistent Hochschild homology pipeline starting from the space of (acyclic) digraphs. The main obstacle here lies in the difﬁculty of having an appropriate metric for digraphs that behaves well with ﬁltrations. Note that persistent Hochschild homology does not behave as the usual persistent homology; in fact, we have the following: Remark 4.9 Consider an edge weighted directed graph G, and consider the ﬁltration induced by sorting the weights in an increasing order—the ﬁrst digraph in the sequence being the spanning subgraph on the vertices of G. Then, generators in persistent Hochschild homology applied to such ﬁltration always persist until ∞. Therefore we cannot talk about births and deaths as is usually done in the context of barcodes. Similarly, as for Hochschild homology, we can consider compositions (n) F P Ch◦dFl H (R, ≤) − → Digraph −−→ Digraph − −−− → Ch − → Ab 0 0 involving the homology of directed ﬂag complexes, or the path homology functors. For n = 0, these compositions yield the usual persistent homology in the ﬁrst case, and the persistent path homology introduced in Chowdhury and Mémoli (2018), in the second. Henceforth, composition with the higher connectivity digraphs allows us to extend the usual classical pipelines. As the homology functors—of the directed ﬂag complex dFl and of the path complex P associated to ﬁnite digraphs, when considering coefﬁcients in a ﬁeld—take values in ﬁnite dimensional vector spaces, the same discussion of the section repeats verbatim, yielding the following: Theorem 4.10 Let F , G : (R, ≤) → Digraph be two ﬁltrations of digraphs. Then, for each i ∈ N we get: (n) (n) d (H ◦ dFL ◦ P ◦ F , H ◦ dFL ◦ P ◦ G) = d(DF , DG) FinVect i i and (n) (n) d (H ◦ P ◦ P ◦ F , H ◦ P ◦ P ◦ G) = d(DF , DG) FinVect i i where DF and DG represent the persistence diagrams associated to F and G. The connectivity digraphs could be substantiated much more, for example, by trying to understand their homotopy types and how those might relate to the underlying digraphs, see the discussion around Question 3.33; this is an ongoing work of the authors. From persistence point of view the ﬁltrations of digraphs could be produced from some derived ﬁltrations, in the same vein as in standard persistence of ﬁnite 123 L. Caputi, H. Riihimäki metric spaces one might employ eccentricity or curvature ﬁltrations. For digraphs one interesting example comes from the discrete Forman-Ricci curvature extended to directed networks (Saucan et al. 2019). We believe this connection of structurally interesting ﬁltrations and connectivity digraphs might be of interest and would lead to new avenues in analysing the structure of digraphs. 4.2 A persistent Hochschild homology pipeline for directed graphs As seen in the previous section, Hochschild homology gives rise to a persistence function when considering directed graphs without oriented cycles; however, this approach fails with graphs having oriented cycles, due to Proposition 2.22.Wenow introduce a persistence-like framework for Hochschild homology that extends our set-up to the whole category Digraph. Our pipeline proceeds as follows: 1. We start with a ﬁltration F : (R, ≤) → Digraph. 2. At each ﬁltration step t we obtain a connectivity digraph E F by applying the (n) n-path digraph P for some n,orthe q-digraph for some (q, d , d ), or any other i j connectivity digraph construction (possibly non-functorial). 3. The resulting digraphs E F can in general have oriented cycles. We therefore consider the condensation c(E F ) (Deﬁnition 1.10). 4. By Remark 1.11, c(E F ) does not have oriented cycles. Hence, we compute the Hochschild characteristic X (c(E F )) = dim HH (A) − dim HH (A), HH t k 0 k 1 where A is the associated path algebra. Note that dim HH (A) agrees with the k 0 number of connected components and dim HH (A) with the formula 1 − n + k 1 dim e Ae of Theorem 2.25. As the digraph c(E F ) does not have k t (e) s(e) t e∈E (G) oriented cycles, this is exactly the characteristic introduced in Deﬁnition 2.29. Diagrammatically, we have: F E c k− X HH (R, ≤) − → Digraph − → Digraph − → Digraph −→ k-Alg −−→ FinVect. (8) Note that the process lands in the category of ﬁnite vector spaces. Even though E might be functorial, as we have introduced two examples in this paper, the composition is not functorial anymore due to condensation c; we refer to the discussion after Remark 1.11. Remark 4.11 Observe that taking the condensation of a digraph and the connectivity digraphs do not commute. In particular, killing the cycles in the condensation process may kill also ordered cliques; this is the reason why we ﬁrst apply E and then the condensation c. We demonstrate our persistent Hochschild homology pipeline, by applying it to the ﬁltrations of the following digraphs: • Random Erdös-Rényi (ER) digraph with probability 0.5 for directed edges between any pair of vertices. We make it randomly edge weighted by replacing each non- zero entry of the adjacency matrix with a value sampled uniformly from [0, 1). 123 Hochschild homology, and a persistent approach via… Fig. 6 The necklace digraph Fig. 7 Persistent Hochschild characteristics. Left: condensed digraph and condensed 1-path digraph of a random Erdös–Rényi. Right: condensed digraph and condensed 1-path digraph of a random necklace digraph. Both digraphs had 20 vertices Fig. 8 Persistent Hochschild characteristics. Left: condensed q-digraphs of a random Erdös–Rényi. Right: condensed q-digraph of a random necklace digraph. The choices for (q, i , j ) are shown in the ﬁgures. Both digraphs had 20 vertices • Random necklace digraph, as represented in Fig. 6. Similarly, to make it random we ﬁrst construct the associated adjacency matrix, which has ones on the ﬁrst upper and lower diagonals, and we then replace these with a value sampled uniformly from [0, 1). In both examples, we take the digraph ﬁltration induced by the random entries of the associated adjacency matrices: at a ﬁltration value t we take the digraph induced by keeping only edges whose weight is ≤ t. The digraphs we used had 20 vertices, so were represented by 20 × 20 adjacency matrices. Figure 7shows the persistent Hochschild characteristics for the random Erdös-Rényi and necklace digraphs, and for their associated 1-path digraphs. Figure 8 shows the results for q-digraphs with (q, d , d ) equal to (q, d , d ) for q ∈{1, 2, 3, 4} for i j 0 q+1 the random Erdös-Rényi, and (0, d , d ) for the necklace digraph; for ease of notation 0 1 we write (q, d , d ) as (q, i , j ) in the remainder of the paper. i j 123 L. Caputi, H. Riihimäki As observed in Remark 4.9, generators in persistent Hochschild homology always persist until ∞, and therefore the associated Betti curves yield monotone func- tions. Experiments involving the persistent Hochschild characteristics of random ER digraphs, and more structured necklace digraphs—cf. Fig. 7—show instead that the associated curves are not monotone. This is caused by the condensation step in the pipeline introduced in this section. Condensation also has the effect of reducing the number of edges and paths in the graph, a number that is correlated to the ﬁrst Hochschild homology group—cf. Theorem 2.25. The effect of condensation is seen in the plots as zig-zagging; particularly large positive jumps correspond to large cyclic components being killed. Note that a common feature in all plots is that the early parts of the ﬁltrations are dominated by the connected components. This occurs until a certain saturation point in which more structured graphs appear and the number of edges, paths, and of oriented cycles, is more prominent. It is interesting to note that this saturation point is reached very soon when dealing with random digraphs and much later for the necklace digraphs. Essentially this is observed in the plots when the value of X drops to negative. The plots for ER q-digraphs also begin slightly positive before HH more paths begin to dominate dropping the values very negatively. Exception is the ER (4,0,5)-digraph: due to the required high-dimensional connecting faces the digraphs are predominantly rather empty of edges and dominated by connected components. When oriented cycles are more likely to be created with long paths, the variations in X are stronger. Compare this effect on the persistent Hochschild characteris- HH tics of random ER digraphs and of necklace digraphs in Fig. 7. Necklace digraphs, perturbed with addition of white noise, present small cycles, so that the persistent Hochschild characteristics is changing almost linearly. Changing the associated con- nectivity digraph may change completely the behaviour of X . Note the change in HH the persistent Hochschild characteristics associated to the line digraphs of the same random and necklace digraphs. Finally, we remark that the X of the q-digraphs in Fig. 8 show drastically larger HH values compared to Fig. 7. Recall that these digraphs have as vertices all the simplices of dimension ≥ q. The simplicial face inclusions are also always near resulting in edges (Deﬁnition 3.13). Therefore the q-digraphs are larger and more dominated by paths along the ﬁltration. This is particularly visible in the plot for ER (2,0,3)-digraph. As already mentioned, the pipeline we have introduced uses the condensation of a digraph to kill the oriented cycles. By producing acyclic digraphs, this also has an effect in the computational efﬁciency since many graph algorithms, for example ﬁnding paths, have lower complexity; this was taken advantage of in Riihimäki (2023) for computing q-connected pathways of simplices. Other approaches are possible, for example in Kaul and Tamaki (2020, Algorithm 1) a Berger and Shor algorithm (Berger and Shor 1990) has been used for the same task. Using condensation leads to our pipeline not being functorial, and we do not know if the persistent Hochschild characteristic deﬁned this way is stable in the sense of Theorem 4.8; this leaves open the following question: Question 4.12 Is it possible to modify the composition of Eq. (8) in a functorial way? Is the composition of Eq. (8) stable in the sense of Theorem 4.8? 123 Hochschild homology, and a persistent approach via… Fig. 9 Persistent Hochschild homology of the synaptic ﬁltration of the C. elegans digraph. Left: n-path digraphs. Right: (q, i , j )-digraphs 4.3 Persistent Hochschild homology of the C. elegans network As an application of the pipeline (8) to real-world data, we analysed the neuronal network of the C. elegans organism (Varshney et al. 2011); in this network vertices are neurons and directed edges represent pre-post-synaptic connections. The synaptic connectivity is obtainable from Altun et al. (2023) and we used the steps in Govc (2020) to construct the directed graph, which has 279 vertices and 2194 edges. The computations demonstrate that our proposed pipeline can be taken as the ﬁrst steps in computational (persistent) Hochschild homology, and the analysis below is meant to provide insight into how one might use this approach in concrete network analysis. The network data contains the synaptic strengths, i.e. each edge has an integer weight in the interval [1, 37]; note that not every value appears as an edge weight. These weights allow to deﬁne a natural synaptic ﬁltration of the full digraph G:for t ∈[1, 37] we take G ⊆ G to be the subgraph induced by all edges with weight ≤ t. Figure 9shows the persistent Hochschild characteristics over the synaptic ﬁltration, for various n-path digraphs and q-digraphs. The choice of the triple (q, i , j ) is only exemplary, and was selected to be different from the examples in the previous section. For more about the Q-analysis of C. elegans see Riihimäki (2023). To gain more insight into the behaviour of X we also show in Fig. 10 the numbers of vertices, HH connected components, and strongly connected components in the n-path digraphs and (q, i , j )-digraphs over the synaptic ﬁltration. In all the plots we see a ﬂattening of the curves around synaptic weight 17. This indicates that addition of new simplices along with higher weight edges happens so sparsely within the network, that it does not change the structure of n-path or q-digraphs in any meaningful way. Recall that the Hochschild characteristic X for (not necessarily connected) HH acyclic digraphs is computed as #components − 1 + #vertices − #{s(e) − edges e t (e)-paths}. This quantity is computed after condensation. For the 2-path digraph we see that in the early parts of the ﬁltration the numbers of components and strong com- ponents rise sharply. Particularly strong components are nearly half of the number of vertices indicating that there are many reciprocally connected pairs of simplices. While the 2-path digraph becomes more connected along the ﬁltration, as seen by the sharp decline in the number of components, the number of strong components stays rather constant. The value of X , however, is very negative along the full ﬁltration. HH 123 L. Caputi, H. Riihimäki Fig. 10 Numbers of vertices, connected components, and strongly connected components of the synaptic ﬁltration of the C. elegans digraph. Left: n-path digraphs. Right: (q, i , j )-digraphs These observations seem to indicate that, even after condensing the strong compo- nents, the 2-path digraph is dominated by paths of 2-simplices connected through shared 1-faces. This interpretation is in fact consistent with the known structure of the C. elegans digraph: there is an over-representation of 2- and 3-cliques with reciprocal edges (Varshney et al. 2011). The behaviour of 3-, 4- and 5-path digraphs seems to follow that of 2-path digraph; the sharp rise of X at ﬁltration values 2–5 is most HH likely the effect of condensing away many edges. The q-digraphs exhibit very large negative values of X . This is largely dominated HH by the contribution of edges: recall that each simplicial face inclusion is q-near, hence contributing an edge. Predominantly due to this, in contrast to 2- and 3-path digraphs, the X of (2,0,2)- and (3,0,3)-digraphs steadily decreases to more negative values HH along the synaptic ﬁltration when more simplices appear. The numbers of strongly connected components in these digraphs is a large fraction of the numbers of vertices, 123 Hochschild homology, and a persistent approach via… possibly indicating that the strong components are rather small, i.e there are only few reciprocally connected simplices. Condensation then only destroys relatively few edges, leaving a larger negative factor in X . From the known over-representation HH of reciprocally connected 2- and 3-cliques in the C. elegans network one might expect that many pairs of simplices with exactly the same vertices would be connected in both ways in the (q, i , j )-digraphs; the particular choice of i and j here might not be sensitive to this. The sharp increase in the (4,0,4)-digraph around ﬁltration values 12– 13 seems to be due to condensation: at the same time there is a drop in the number of components, so more simplices become connected, and a steep increase in the number of strong components, with the overall effect being that many edges are condensed away. It is interesting that this happens at the particular synaptic weights, and the same phenomena occurs in all the n-path digraphs, albeit to a less degree; this seems to indicate that there is, simplicially, something interesting happening in the C. elegans network at the synaptic weight range 10–15. Further investigating this is left for future work. For (5,0,5)-digraph we see that the slightly positive value of X until ﬁltration HH value 12 is dominated by vertices and components with very little connections; this is reasonable as simplices of dimension ≥ 5 are sparse within the network. As more simplices appear we see a decline in X with the increase of connecting edges. Note HH that the numbers of vertices and strong components seem to agree throughout the ﬁltration, indicating that there are nearly zero reciprocal connections and condensation therefore has no effect. Acknowledgements The authors wish to thank Ran Levi for his support and useful discussions. The authors would also like to thank the anonymous referees, whose feedback greatly improved the paper. Funding Open access funding provided by Royal Institute of Technology. The authors acknowledge support from the École Polytechnique Fédérale de Lausanne via a collaboration agreement with the University of Aberdeen. Henri Riihimäki acknowledges support from the KTH Royal Institute of Technology in Stockholm, and from the Dbrain project within Digital Futures consortium in Stockholm. Declarations Conﬂict of interest The authors declare that they have no conﬂict of interest. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Aharoni, R., Berger, E., Meshulam, R.: Eigenvalues and homology of ﬂag complexes and vector representations of graphs. Geom. Funct. Anal. 15, 555–566 (2005) 123 L. Caputi, H. Riihimäki Altun, Z., Herndon, L., Wolkow, C., Crocker, C., Lints, R., Hall, D.: Wormatlas. (2023). https://wormatlas. org Atkin, R.: From cohomology in physics to q-connectivity in social science. Int. J. Man Mach. Stud. 4, 139–167 (1972) Atkin, R.: Mathematical Structure in Human Affairs. Heinemann, London (1974) Barmak, J.: Algebraic Topology of Finite Topological Spaces and Applications. Springer, Berlin (2011) Baues, H.-J., Wirsching, G.: Cohomology of small categories. J. Pure Appl. Algebra 38(2), 187–211 (1985) Berger, B., Shor, P.W.: Approximation alogorithms for the maximum acyclic subgraph problem. In: Proceed- ings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’90, pp. 236–243. Society for Industrial and Applied Mathematics (1990) Bergomi, M.G., Vertechi, P.: Rank-based persistence. Theory Appl. Categ. 35, 228–260 (2020) Brion, M.: Representations of quivers. In: Geometric methods in representation theory. vol. 24, pp. 103–144. Soc. Math. France, Paris (2012). https://www-fourier.ujf-grenoble.fr/~mbrion/notes_quivers_rev.pdf Bubenik, P., de Silva, V., Scott, J.: Metrics for generalized persistence modules. Found. Comput. Math. 15, 1501–1531 (2015) Caputi, L., Collari, C., Di Trani, S.: Multipath cohomology of directed graphs (2021a). arXiv:2108.02690 Caputi, L., Pidnebesna, A., Hlinka, J.: Promises and pitfalls of topological data analysis for brain connectivity analysis. Neuroimage 238, 118245 (2021b) Caputi, L., Celoria, D., Collari, C.: Categorifying connected domination via graph überhomology (2022a). arXiv:2201.00721 Caputi, L., Celoria, D.,Collari, C.: Monotone cohomologies and oriented matchings (2022b). arXiv:2203.03476 Caputi, L., Collari, C., Di Trani, S.: Combinatorial and topological aspects of path posets, and multipath cohomology. J. Algebr. Combin. (2022c). https://doi.org/10.1007/s10801-022-01180-9 Chaplin, T.: First Betti number of the path homology of random directed graphs. J. Appl. Comput. Topol. (2022). https://doi.org/10.1007/s41468-022-00108-3 Chen, B., Yau, S.-T., Yeh, Y.-N.: Graph homotopy and graham homotopy. Discrete Math. 241(1), 153–170 (2001). (Selected Papers in honor of Helge Tverberg) Chowdhury, S., Huntsman, S., Yutin, M.: Path homologies of motifs and temporal network representations. Appl. Netw. Sci. 7(1), 4 (2022) Chowdhury, S., Mémoli, F.: Persistent path homology of directed networks. In: Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1152–1169 (2018) Chung, M.K., Hanson, J.L., Ye, J., Davidson, R.J., Pollak, S.D.: Persistent homology in sparse regression and its application to brain morphometry. IEEE Trans. Med. Imaging 34, 1928–1939 (2014) Citterio, M.G.: Classifying spaces of categories and term rewriting. Theory Appl. Categ. 9(5), 92–105 (2001) Conceição, P., Govc, D., Lazovskis, J., Levi, R., Riihimäki, H., Smith, J.: An application of neighbourhoods in digraphs to the classiﬁcation of binary dynamics. Netw. Neurosci. 6(2), 528–551 (2022) Dey, T.K., Mandal, S., Varcho, W.: Improved Image Classiﬁcation using Topological Persistence. In: Hullin, M., Klein, R., Schultz, T., Yao, A. (eds.) Vision, Modeling and Visualization. The Eurographics Association (2017) Dey, T.K., Li, T., Wang, Y.: An efﬁcient algorithm for 1-dimensional (persistent) path homology. Discrete Comput. Geom. (2022). https://doi.org/10.1007/s00454-022-00430-8 Diestel, R.: Graph Theory. Springer, Heidelberg (2010) Dowker, C.H.: Homology groups of relations. Ann. Math. 56, 84–95 (1952) Dubut, J., Goubault, É., Goubault-Larrecq, J.: Natural homology. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Automata, Languages, and Programming, pp. 171–183. Springer, Berlin (2015) Gabriel, P., Zisman, M.: Calculus of Fractions and Homotopy Theory. Springer, Berlin (1967) Giansiracusa, N., Giansiracusa, R., Moon, C.: Persistent homology machine learning for ﬁngerprint clas- siﬁcation. In: 18th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 1219–1226 (2019) Gidea, M.: Topology data analysis of critical transitions in ﬁnancial networks. SSRN Electron. J. 01 (2017) Govc, D.: Computing homotopy types of directed ﬂag complexes (2020). arXiv:2006.05333 Govc, D., Levi, R., Smith, J.P.: Complexes of tournaments, directionality ﬁltrations and persistent homology. J. Appl. Comput. Topol. 5, 313–337 (2021) Grady, R., Schenﬁsch, A.: Zig-zag modules: cosheaves and K-theory (2021). arXiv:2110.04591 123 Hochschild homology, and a persistent approach via… Grigorian, A., Lin, Y., Muranov, Y., Yau, S.-T.: Cohomology of digraphs and (undirected) graphs. Asian J. Math. 19, 887–932, 11 (2015) Grigorian, A., Jimenez, R., Muranov, Y., Yau, S.-T.: On the path homology theory of digraphs and Eilenberg– Steenrod axioms. Homol. Homot. Appl. 20, 179–205, 01 (2018) Grigor’yan, A.: Overview of path homology theory of digraphs. BIMSA-YMSC seminar (2022). https:// www.math.uni-bielefeld.de/~grigor/dslides5.pdf Grigor’yan, A., Lin, Y., Muranov, Y., Yau, S.-T.: Homologies of path complexes and digraphs (2013). arXiv:1207.2834 Grigor’yan, A., Lin, Y., Muranov, Y., Yau, S.-T.: Homotopy theory for digraphs. Pure Appl. Math. Q. 10(4), 619–674 (2014) Grigor’yan, A., Muranov, Y., Yau, S.-T.: Homologies of digraphs and künneth formulas. Commun. Anal. Geom. 25(5), 969–1018 (2017) Grigor’yan, A., Muranov, Y., Vershinin, V., Yau, S.-T.: Path homology theory of multigraphs and quivers. Forum Math. 30(5), 1319–1337 (2018) Grigor’yan, A., Lin, Yong, Muranov, Y., Yau, S.-T.: Path complexes and their homologies. J. Math. Sci. 248, 564–599 (2020) Happel, D.: Hochschild cohomology of ﬁnite-dimensional algebras. Lect Notes Math 1404, 108–126 (1989) Harary, F., Norman, R.Z.: Some properties of line digraphs. R Circ Mat Palermo 9, 161–168 (1960) Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2000) Hochschild, G.: On the cohomology groups of an associative algebra. Ann. Math. 46, 58–67 (1945) Ivashchenko, A.V.: Contractible transformations do not change the homology groups of graphs. Discrete Math. 126(1), 159–170 (1994) Kassel, C.: Cyclic homology, comodules, and mixed complexes. J. Algebra 107(1), 195–216 (1987) Kaul, M., Tamaki, D.: A weighted quiver kernel using functor homology (2020). arXiv:2009.12928 Khalid, A., Kim, B.S., Chung, M.K., Ye, J.C., Jeon, D.: Tracing the evolution of multi-scale functional networks in a mouse model of depression using persistent brain network homology. NeuroImage 101 (2014) Krishnan, S.: Flow-cut dualities for sheaves on graphs (2014). arXiv:1409.6712 Kuang, L., Zhao, D., Xing, J., Chen, Z., Xiong, F., Han, X.: Metabolic brain network analysis of FDG-PET in Alzheimer’s disease using kernel-based persistent features. Molecules 24, 2301 (2019) Lee, H., Chung, M.K., Kang, H., Kim, B.-N., Lee, D.S.: Discriminative persistent homology of brain networks. In: Proceedings—International Symposium on Biomedical Imaging, pp. 841–844 (2011) Loday, J.-L.: Cyclic Homology. Springer, Berlin (1998) Lütgehetmann, D., Govc, D., Smith, J.P., Levi, R.: Computing persistent homology of directed ﬂag complexes. Algorithms 13(1), 19 (2020) MacLane, S.: Categories for the Working Mathematician. Springer, Berlin (1971) Masulli, P., Villa, A.E.P.: The topology of the directed clique complex as a network invariant. SpringerPlus 5(388), 1–12 (2016) Munkres, J.R.: Elements of Algebraic Topology. Addison Wesley, Boston (1984) Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005) Patel, A.: Generalized persistence diagrams. J. Appl. Comput. Topol. 1, 397–419 (2018) Quillen, D.: Higher algebraic K-theory: I. In: Bass, H. (ed.) Higher K-Theories, pp. 85–147. Springer, Berlin (1973) Redondo, J.: Hochschild cohomology: some methods for computations. Resenhas Inst. Mat. Estat. Univ. São Paulo 2, 113–137 (2001) Reimann, M.W., Nolte, M., Scolamiero, M., Turner, K., Perin, R., Chindemi, G., Dłotko, P., Levi, R., Hess, K., Markram, H.: Cliques of neurons bound into cavities provide a missing link between structure and function. Front. Comput. Neurosci. 11, 48 (2017) Ren, S., Wang, C.: Differential algebras on digraphs and generalized path homology (2021). arXiv:2103.15870 Riihimäki, H.: Simplicial q-connectivity of directed graphs with applications to network analysis. SIAM. J. Math. Data Sci. (2023) (to appear) Saucan, E., Sreejith, R.P., Vivek-Ananth, R.P., Jost, J., Samal, A.: Discrete RICCI curvatures for directed networks. Chaos Solitons Fract. 118, 347–360 (2019) Schröder, B.: Ordered Sets, 2nd edn. Birkhäuser, Basel (2016) 123 L. Caputi, H. Riihimäki Turner, P., Wagner, E.: The homology of digraphs as a generalisation of Hochschild homology. J. Algebra Appl. 11, 1250031 (2012) Varshney, L., Chen, B., Paniagua, E., Hall, D., Chklovskii, D.: Structural properties of the Caenorhabditis elegans neuronal network. PLoS Comput. Biol. 7, e1001066 (2011) West, D.B.: Introduction to Graph Theory. Prentice-Hall, Hoboken (2005) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional afﬁliations.
Journal of Applied and Computational Topology – Springer Journals
Published: Mar 14, 2023
Keywords: Graph homology; Persistent homology; Hochschild homology; Connectivity graphs; n-Path digraphs; q-Connectivity; 05C20; 05C90; 55N31; 18G85; 13D03
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.