Clustering and Structural Robustness in Causal Diagrams

This is a self-archived version of an original article. This version may differ from the original in pagination and typographic details. Author(s): Title: Year: Version: Copyright: Rights: Rights url: Please cite the original version: CC BY 4.0 https://creativecommons.org/licenses/by/4.0/ Clustering and Structural Robustness in Causal Diagrams ©2023 Santtu Tikka, Jouni Helske, Juha Karvanen Published version Tikka, Santtu; Helske, Jouni; Karvanen, Juha Tikka, S., Helske, J., & Karvanen, J. (2023). Clustering and Structural Robustness in Causal Diagrams. Journal of Machine Learning Research, 24, Article 195. https://jmlr.org/papers/v24/21-1322.html 2023 Journal of Machine Learning Research 24 (2023) 1-32 Submitted 11/21; Revised 6/23; Published 7/23 Clustering and Structural Robustness in Causal Diagrams Santtu Tikka [email protected] Jouni Helske [email protected] Juha Karvanen juha.t.karv[email protected] Department of Mathematics and Statistics P.O.Box 35 (MaD) FI-40014 University of Jyvaskyla, Finland Editor: Francis Bach Abstract Graphs are commonly used to represent and visualize causal relations. For a small number of variables, this approach provides a succinct and clear view of the scenario at hand. As the number of variables under study increases, the graphical approach may become impractical, and the clarity of the representation is lost. Clustering of variables is a natural way to reduce the size of the causal diagram, but it may erroneously change the essential properties of the causal relations if implemented arbitrarily. We define a specific type of cluster, called transit cluster, that is guaranteed to preserve the identifiability properties of causal effects under certain conditions. We provide a sound and complete algorithm for finding all transit clusters in a given graph and demonstrate how clustering can simplify the identification of causal effects. We also study the inverse problem, where one starts with a clustered graph and looks for extended graphs where the identifiability properties of causal effects remain unchanged. We show that this kind of structural robustness is closely related to transit clusters. Keywords: causal inference, graph theory, algorithm, identifiability, directed acyclic graph 1. Introduction Directed acyclic graphs (DAGs) and their extensions are commonly used to describe causal relations between variables in epidemiology and other fields (Pearl, 1995; Greenland et al., 1999; Tennant et al., 2021). The power of graphs lies in their ability to visualize the assumed structure, and at the same time, to serve as well-defined inputs for algorithms such as those that solve the nonparametric identifiability of causal effects (Shpitser and Pearl, 2006; Lee et al., 2019; Lee and Shpitser, 2020; Tikka et al., 2021). The graphical approach has been criticized by proponents of potential outcome framework (Rubin, 1974) for its impracticality when a large number of variables is considered (Imbens, 2020). This criticism is partially justified: the visual clarity of a graph is easily lost when the number of vertices is more than a few, especially in the case of several crossing edges (Purchase, 1997). Moreover, in some settings the identifiability of causal effects is an NP-hard problem (Tikka et al., 2019), which makes it impractical to consider large graphs. A possible remedy for these difficulties is to cluster the variables to reduce the size of the graph. A question then arises whether the clustered graph and the original graph are equivalent with respect to the identifiability properties of causal effects. The idea of clustering is natural and has been used in causal inference explicitly and implicitly. The back-door criterion (Pearl, 1993), the front-door criterion (Pearl, 1995), and ignorability assumptions in the potential outcome framework (Rosenbaum and Rubin, 1983) impose conditions upon a set (i.e., a cluster) of variables and the structure inside the set is not important. Explicitly, clusters have been constructed starting from structural equations (Skorstad, 1990) or multivariate data (Entner and Hoyer, 2012; Parviainen and Kaski, 2017; Nisimov et al., 2021). Outside causal inference, many clustering methods for directed graphs have been proposed under varying premises (Malliaros and Vazirgiannis, 2013). ©2023 Santtu Tikka, Jouni Helske, Juha Karvanen. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v24/21-1322.html. Tikka, Helske and Karvanen Clustering can be also viewed from a different starting point as a way to construct causal models where the causal relationships between clusters of variables are specified instead of the relationships between the variables themselves. For instance, a recent review (Tennant et al., 2021) found that many DAGs in applied health research included so-called ”super-nodes” (Kornaropoulos and Tollis, 2013) which represent multiple variables with the implicit assumption of strong connectivity of the corresponding vertices. This viewpoint emphasizes the uncertainty of structural assumptions and the fact that we may not possess sufficient knowledge about the domain under study to fully specify individual relationships between variables. The goal in this type of clustering is structural robustness; inferences made with the clustered graph can be safely applied in any graph that is compatible with the clustering, but not necessarily vice versa. This approach was considered in a formal setting by Anand et al. (2021). Clustering is different from latent projection (Verma, 1993) that also can be used to simplify the structure of DAG in causal inference (Tikka and Karvanen, 2018). Figure 1 demonstrates that a cluster of vertices is not always equivalent to a latent projection in terms of identification. We consider the identifiability of a query p(xb|do(xa)) from observations p(xa, xb, xc1, xc2). In this task, we may apply clustering C={c1, c2}and obtain an identifying formula similar to the original solution. However, if we use a latent projection to consider either c1or c2as unobserved in graph G1, a bidirected edge between aand bappears, and the query is not identifiable anymore. In the graph G2, the query is not identifiable if a latent projection is used to consider both c1and c2as unobserved, although projecting only either c1or c2retains the identifiability. On the other hand, arbitrary clustering of variables in a DAG does not necessarily retain the identifiability either. ab c1 c2 (a) Original graph G1. ab c2 (b) Graph obtained from G1via latent projection of c1. ab c (c) Graph obtained from G1by clustering c1and c2as c. ab c1 c2 (d) Original graph G2. ab (e) Graph obtained from G2via latent projection of c1and c2. ab c (f) Graph obtained from G2by clustering c1and c2as c. Figure 1: Two examples on clustering of vertices. As the first contribution, we introduce a specific type of cluster, called transit cluster, and present conditions for the equivalence of causal effect identifiability between the original and the clustered graph. We consider clustering as an operation that transforms a DAG into a new DAG where the cluster is represented by a single vertex. Our approach toward clustering builds on the intuitive idea that information flows through a cluster and the detailed structure inside the cluster is often irrelevant. We assume that the DAG being clustered is fully specified. As the second contribution, we provide a sound and complete algorithm for finding all transit clusters in a given graph and demonstrate how clustering can simplify the identification of causal 2 Clustering and Structural Robustness effects. While polynomial-time algorithms exist for many important causal identification problems, the resulting identifying functional can be complicated (Tikka and Karvanen, 2017b). Clustering vertices in the graph can reduce the computational burden and lead to identifying functionals with a simpler structure. As the third contribution, we study the inverse problem, where one starts with a clustered graph and looks for extended graphs where the identifiability properties of causal effects remain unchanged. This problem is related to the top-down causal modeling where one starts by creating the DAG with concepts, such as “work history”, “socio-economic background” or “genetic factors”, and only later divides these concepts into actual variables. Here a transit cluster represents this kind of concept. We present an iterative procedure that can be used to extend a single vertex to an arbitrary transit cluster. We show that transit clusters are structurally robust in the sense that under certain conditions the structure inside the cluster is irrelevant for identification. A schematic illustration of contributions of the paper is presented in Figure 2. Causal inference with large graphs Large unclustered graph Clustering (Algorithms 1 and 2) All transit clusters Transit cluster Clustered graph Transit cluster Clustered graph . . . Transit cluster Clustered graph Top-down causal modeling Clustered graph Peripheral extension (Definition 12, Theorems 13 and 14) Extended graph Unclustered graph Figure 2: A schematic illustration of the contributions of the paper. In causal inference with large graphs (left), the application of the proposed clustering algorithm to a large graph results in a collection of all transit clusters, each of which corresponds to a clustered graph. In top-down causal modeling (right), we start with a clustered graph and iteratively apply peripheral extension to obtain an unclustered graph that shares the key properties with the clustered graph. The rest of the paper is organized as follows. In Section 2, we define the transit cluster and prove its key properties. In Section 3, we present an algorithm for finding all transit clusters of a DAG and prove that it is sound and complete. After considering clustering from a purely graphical point of view in Sections 2 and 3, we then proceed to consider clustering in causal diagrams in Section 4, where we provide results on the identifiability of causal effects for specific transit clusters. In Section 5, we consider structural robustness and its connection to transit clusters. Illustrative examples on the clustering and structural robustness are given Section 6. Section 7 concludes the paper. Code for the clustering algorithms and examples are available in a GitHub repository: https://github.com/santikka/transit_cluster. 3 Tikka, Helske and Karvanen 2. Clustering Vertices in DAGs We begin by introducing the notation used for directed graphs. A DAG G= (V, E) is an ordered pair of two sets where Vis a set of indices (vertices), i.e., V={1, . . . ,n}, and Eis a set of ordered pairs (directed edges) E⊆ {(i, j)|i, j ∈V}. Vertices and edges are denoted with small letters. In a DAG G= (V, E), PaG(A), ChG(A), AnG(A) and DeG(A) denote the parents, children, ancestors and descendants of vertex set A⊆Vincluding A, respectively. The neighbors of a vertex set Aincluding Ais denoted by NeG(A)≡ChG(A)∪PaG(A). Vertices connected to Aincluding Ais denoted by CoG(A). The corresponding sets of the previous that exclude Aare denoted by Pa∗ G(A), Ch∗ G(A), An∗ G(A), De∗ G(A), Ne∗ G(A), and Co∗ G(A). If there is only one relevant graph Gin a given context, we will sometimes omit the subscript from these sets for clarity, and simply write Pa(A) or Pa∗(A), for example. We use the notation G[W] to denote an induced subgraph (W, F) of G= (V, E), where W⊆V and Fcontains those edges of Ewith both endpoints in W. Similarly, G[A, B] denotes an induced edge subgraph obtained from Gby removing incoming edges to A⊆Vand outgoing edges of B⊆V. The collection of vertex sets that induce the components of Gis denoted by C(G). By a cluster we mean a subset of vertices of a DAG. Note that there are different definitions of “clustering” and “cluster graph” in other contexts. The motivation for the name “cluster” becomes evident when we consider a graph that represents the cluster as a single vertex: Definition 1 (Clustering) Clustering of a set of vertices T⊂Vin a DAG G= (V, E)induces a graph G′= (V′, E′)obtained from Gby removing vertices Tand adding a new vertex tthat has parents Pa∗ G(T)and children Ch∗ G(T). In addition, sets W⊂Vand W′⊂V′are clustering equivalent if W\T=W′\ {t}and T⊂Wif and only if t∈W′. Definition 1 captures the intuitive idea of clustering where the incoming and outgoing edges of the cluster are the same as the incoming and outgoing edges of its representative in the induced graph. However, without any constraints on the set Tbeing clustered, this definition is too general in the sense that the properties of the induced graph may be drastically different from the original graph. For example, the induced graph is not necessarily a DAG or it may contain paths that were not present in the original graph. Next, we will present conditions for the clustered vertices Tthat guarantee the usefulness of the clustering. Our approach is based on the intuitive notion that the effects flow through the cluster and the edges between the clustered vertices do not matter. Only those edges that connect to vertices outside the cluster are relevant. For this purpose, we define two special sets of vertices. Definition 2 (Receiver) For a set of vertices Tin a DAG G= (V, E), the set of receivers is the set ReG(T)≡ {v∈T|PaG(v)∩(V\T)=∅}. The set of receivers for a set of vertices T⊂Vare those members of Tthat have parents outside of Tin G. To complement the receivers, we also define the following. Definition 3 (Emitter) For a set of vertices Tin a DAG G= (V, E), the set of emitters is the set EmG(T)≡ {v∈T|ChG(v)∩(V\T)=∅}. We will use shortcut notation G[T=] to denote a subgraph induced by Tsuch that the incoming edges to receivers of Tand outgoing edges from emitters of Tare removed. We are now ready to define a cluster that preserves the fundamental structure of the graph. Definition 4 (Transit cluster) A non-empty set T⊂Vis a transit cluster in a connected DAG G= (V, E)if the following conditions hold 4 Clustering and Structural Robustness 1. Pa(ri)\T=Pa(rj)\Tfor all pairs ri, rj∈Re(T), 2. Ch(ei)\T=Ch(ej)\Tfor all pairs ei, ej∈Em(T), 3. For all vertices ti∈T, there exists a receiver ror an emitter esuch that tiand ror tiand e are connected via an undirected path in G[T=]. 4. If Em(T)=∅then for all r∈Re(T)there exists e∈Em(T)such that e∈De(r), 5. If Re(T)=∅then for all e∈Em(T)there exists r∈Re(T)such that r∈An(e). In other words, a transit cluster is a set of vertices such that any member of its receivers has the same parents outside of the set, and any member of its emitters has the same children outside of the set. Additionally, we disallow those vertices from belonging to the cluster that are disconnected from the receivers or emitters when incoming edges of receivers and outgoing edges of emitters have been removed. Finally, for any receiver, there is always a directed path connecting that receiver to an emitter, and conversely, for any emitter, there is always a directed path connecting a receiver to that emitter. Together, these features endow the grouped set of vertices with several desirable properties. The set of all transit clusters of Gis denoted by ΥG. The purpose behind the first two conditions in Definition 4 is to ensure that no new paths from the parents of the receivers to the children of emitters are created by performing the clustering. The third condition ensures that a transit cluster is characterized by its receivers and emitters, as we will show later. The last two conditions enforce the idea of information flow through the cluster. Examples of transit clusters are presented in Figure 3. Definitions 1–4 allow us to characterize the graph induced by a transit cluster as follows: Corollary 5 The induced graph G′of transit cluster Tis constructed from Gby replacing Twith a single vertex tsuch that Pa∗ G′(t) = Pa∗ G(ReG(T)) \Tand Ch∗ G′(t) = Ch∗ G(EmG(T)) \T. We consider some desirable basic properties of transit clusters. We delegate the proofs of all results to Appendix A. First, we must ensure that the graph induced by a transit cluster does not contain cycles. Lemma 6 Graph G′induced by a transit cluster Tin a DAG Gis a DAG. Next, we note that transit clusters are uniquely defined by their receivers and emitters. Lemma 7 Let Tand Sbe transit clusters in a DAG G= (V, E). If Re(T) = Re(S)and Em(T) = Em(S), then T=S. Intuitively, if clustering is carried out for multiple vertex sets in sequence, the order in which the clustering is carried out should not matter in terms of the graph obtained after the last set has been clustered. This notion is captured by the next two theorems. The first one states that a transit cluster remains a transit cluster even if a disjoint transit cluster is clustered. Theorem 8 (Invariance of transit clusters) Let Tbe a transit cluster in G= (V, E)and let G′ be the induced graph where Tis replaced by a single vertex t. The set S⊂V\Tis a transit cluster in Gif and only if it is a transit cluster in G′. A complementary result to the previous theorem guarantees that a transit cluster will still be a transit cluster even if its subset is clustered. Theorem 9 (Modularity of transit clusters) Let Tbe a transit cluster in graph G= (V, E)and G′the induced graph where Tis replaced by a single vertex t. Let S⊂V\T. The set {t} ∪ Sis a transit cluster in G′if and only if T∪Sis a transit cluster in G. 5 Tikka, Helske and Karvanen x r1 r2 r3 e1 e2y (a) Transit cluster {r1, r2, r3, e1, e2}. x r1 e1 r2 e2 rk−1 ek−1 rk ek y . . . (b) Transit cluster {r1, r2,...,rk, e1, e2,...,ek}. x1r1z1e1y1 x2 z3z4 z5 r2 z2 e2y2 (c) Transit cluster {r1, r2, e1, e2, z1, z2, z3, z4, z5}. Figure 3: Examples of transit clusters. In addition to presented transit clusters, there are other transit clusters, for instance transit cluster {r1, e1}in panel (a). Theorem 9 helps us to characterize the conditions for valid unions of transit clusters. The following corollary plays a key role in the algorithmic approach to finding transit clusters in Section 3. Corollary 10 (Union of transit clusters) Let disjoint sets Sand Tbe transit clusters in G. S∪Tis a transit cluster in Gif Pa∗(Re(S)) = Pa∗(Re(T)) and Ch∗(Em(S)) = Ch∗(Em(T)). While other types of unions of transit clusters can result in valid transit clusters, it turns out that the particular union specified by Corollary 10 is the only one we actually need. In a practical setting, there may be vertices that we cannot or do not want to include in the same cluster with other vertices. Thus the set of possible clusters may be restricted. Definition 11 (Restricted transit cluster) Let G= (V, E)be a DAG and R⊆V. A restricted transit cluster T⊂Vwith respect to Rin Gis a transit cluster in Gsuch that T⊆R. We denote the set of all restricted transit clusters with respect to Rby ΥG|R≡ {T|T∈ΥG, T ⊆R}. The next definition specifies the operations that can be applied to a DAG so that a transit cluster remains a transit cluster. 6 Clustering and Structural Robustness Definition 12 (Peripheral extension) Let T={t1, . . . , tk}be a transit cluster in a DAG G. Let G+be a DAG obtained from Gby one of the following operations: 1. Add an edge ti→tjwhere ti, tj∈Tand the edge does not create a cycle, 2. Replace the edge ti→tjby the path ti→tk+1 →tjwhere tk+1 is a new vertex, 3. Divide vertex tias follows: add a new vertex tk+1 such that Ch∗ G+(tk+1) = Ch∗ G(ti), remove all outgoing edges of tiand add edge ti→tk+1. 4. Add a new vertex tk+1 and the edge tk+1 →tiand where ti∈T\Re(T), 5. Add a new vertex tk+1 and the edge ti→tk+1 where ti∈T\Em(T). Adding a receiver or an emitter when Re(T)=∅and Em(T)=∅: 6. Add a new vertex tk+1 (a new receiver) such that Pa∗ G+(tk+1) = Pa∗ G(Re(T)), and add an edge tk+1 →tjwhere tj∈Tis on a path from a receiver to an emitter in G. 7. Add a new vertex tk+1 (a new emitter) such that Ch∗ G+(tk+1) = Ch∗ G(Em(T)), and add an edge tj→tk+1 where tj∈Tis on a path from a receiver to an emitter in G. 8. Add two new vertices tk+1 (a new receiver) and tk+2 (a new emitter) such that Pa∗ G+(tk+1) = Pa∗ G(Re(T)) and Ch∗ G+(tk+2) = Ch∗ G(Em(T)), and add the edge tk+1 →tk+2. Adding a receiver when Re(T)=∅and Em(T) = ∅: 9. Add a new vertex tk+1 (a new receiver) such that Pa∗ G+(tk+1) = Pa∗ G(Re(T)). Adding an emitter when Re(T) = ∅and Em(T)=∅: 10. Add a new vertex tk+1 (a new emitter) such that Ch∗ G+(tk+1) = Ch∗ G(Em(T)). Now define T+=Tif operation 1 was applied, T+=T∪{tk+1}if operation 2, 3, 4, 5, 6, 7, 9 or 10 was applied, and T+=T∪ {tk+1, tk+2}if operation 8 was applied. In all cases, T+is a peripheral extension of T, and G+is the corresponding peripheral extension graph. Operations 1–5 modify the internal structure of the transit cluster. New vertices and edges can be added but new parents for receivers or new children for emitters cannot be added with these operations. Operations 6–10 add new receivers and emitters. Here the allowed operations differ for transit clusters that have only receivers, only emitters and both receivers and emitters. Special conditions are needed to make sure that T+fulfills the conditions of Definition 4. The following theorem shows that a peripheral extension always results in a transit cluster. Theorem 13 Let T+be a peripheral extension of a transit cluster Tin a DAG G= (V, E)and let G′be the induced graph where Tis replaced by a single vertex. Then T+is a transit cluster in the corresponding peripheral extension graph G+and G′is the induced graph of T+. A complementary result shows that any transit cluster can be constructed iteratively with operations of Definition 12. Theorem 14 Let G′be the induced graph of a transit cluster constructed from Gby replacing set Tby a single vertex t. Then Gand Tcan be constructed by iteratively applying operations of Definition 12 to transit cluster {t}in G′. So far, our focus has been on transit clusters in general. It turns out that transit clusters can always be constructed from smaller “building blocks” which we call transit components. Furthermore, it is much easier to find transit components in a given DAG than transit clusters. 7 Tikka, Helske and Karvanen Definition 15 (Transit component) A transit cluster Tin a DAG Gis a transit component if Tis connected in G[T]. We extend the notion of restriction to transit components: the set of all restricted transit components of a DAG Gwith respect to the set Ris denoted by TG|R, and when R=V, i.e., when the aforementioned set corresponds to components without restriction, we simply write TG. The intuitive idea behind the purpose of transit components is encapsulated in the following theorem. Theorem 16 (Transit cluster decomposition) Let Tbe a transit cluster in a DAG G= (V, E). If Tis not a transit component, then there exists a transit cluster Sand a transit component Rsuch that T=S∪Rand S∩R=∅. In simpler terms, any transit cluster can always be constructed iteratively from disjoint transit components. The transit cluster decomposition plays a key role in finding transit clusters. 3. Clustering Algorithms To find valid vertex clusters, we can always apply a naive approach and enumerate every vertex subset of a DAG Gand determine whether the conditions of Definition 4 hold. However, this approach quickly becomes infeasible with larger graphs. In light of Theorem 16, we can instead start by constructing the set of all transit components, and then obtain the set of all transit clusters by applying Corollary 10 to the components. We begin by presenting a sound and complete algorithm for finding transit components that exploit the structure of the graph by enumerating a set of candidate receiver and emitter sets. Algorithm 1 (FindTrComp) starts by constructing the candidate sets for potential receivers and emitters, VCh and VPa, respectively on lines 3 and 4. Lemma 7 shows that we only need to consider the receivers and emitters to uniquely specify a transit component. Next, we iterate over all pairs of the candidates on lines 5 and 6. Lines 7–9 restrict the candidates into mutually ancestral sets Zand W, and further exclude those candidates that cannot satisfy the properties of a transit cluster. If at least one of the obtained candidate sets Zand Wis nonempty on line 11, we move on to construct a candidate transit component Aon line 12. If Aobeys the restriction defined by R on line 13, we move on to the iteration over the components of Ain the induced subgraph G[A] on line 14. Lines 15 and 16 define those members of the current candidates Zand Wthat belong to the current component Akas Zkand Wkrespectively. Finally, we determine whether the members of Zkhave the same parents, and whether members of Wkhave the same children during lines 17–19. If this is the case, a new transit component of Ghas been found, and it is added to the set Aof components found so far. Finally, this set is returned on line 21 after the outermost iterations have been completed. We proceed to show that FindTrComp always terminates. Lemma 17 FindTrComp always terminates for valid inputs Gand R. Lemma 17 allows us to consider the output of FindTrComp. To show soundness of the algorithm, me must show that the output set only contains restricted transit components. Theorem 18 (Soundness of FindTrComp) Let G= (V, E)be a DAG, R⊆Vand A=FindTrComp(G, R), then A⊆TG|R. Conversely for completeness of FindTrComp, we must show that any restricted transit component of a DAG will be found by the algorithm. Theorem 19 (Completeness of FindTrComp) Let G= (V, E)be a DAG, R⊆V, and A= FindTrComp(G, R)then TG|R⊆ A. 8 Clustering and Structural Robustness On the contrary, the application of the ID-algorithm to the clustered graph of Figure 5 leads to identifying functional of form p(xa|do(xb)) = X xt p(xt|xb) X x′ b p(xa|x′ b, xt)p(x′ b) ,(2) i.e. front-door adjustment. This enables us to model p(xt|xb) in an arbitrary, but consistent manner without making specific claims about the internal structure of T. 6.3 Speeding up identification algorithms Identifying functionals obtained from the application of ID-algorithm or general do-calculus are often unnecessarily complex and could be further simplified (Tikka and Karvanen, 2017b). This can allow easier interpretation of the identifying functional and more efficient estimation of the causal effect. The R (R Core Team, 2022) package causaleffect (Tikka and Karvanen, 2017a) implements an automatic simplification algorithm for this task, however, the algorithm can be slow in case of large graphs. Alternatively if we can first simplify the graph by clustering, we can reduce the computational burden of both the identification algorithm as well as subsequent simplification algorithm. For example, in case of the Sangiovese graph, the causaleffect package returns (1) in 0.1 seconds with simplification option disabled and 132 seconds with simplification enabled (which in this case does not lead to simpler equation) on a standard laptop. On the other hand, running the clustering algorithm and subsequent identification (which returns (2)) takes only 0.5 seconds. Importantly, the simplification algorithm of Tikka and Karvanen (2017b) is NP-hard, and thus it may be possible to obtain simpler identifying functionals using transit clusters in scenarios where direct simplification is infeasible. The code for this benchmark is also available in the GitHub repository. 6.4 Top-down causal modeling As an example of peripheral extension and the robustness of the estimation strategies, consider a causal graph shown in Figure 6, studied earlier by Helske et al. (2021), where the interest is in the causal effect of the education level Xeon income Xi. Variable Xsmeasures general language skills on Illinois Test of Psycholinguistic Abilities (ITPA), which is a composite of 12 subtests. Thus instead of vertex srepresenting a single composite variable Xsin Figure 6, we can by the peripheral extension (12) treat it as a transit cluster T={s1, . . . , s12}(with sicorresponding to the subtest i) without affecting the identifiability of the causal effect p(xi|do(xe)). While the causal effect estimates can depend on whether we use Xsor XTin the modelling, the obtained estimator is robust to these changes in a sense that the methodology of Helske et al. (2021) can be used to estimate the effect in both cases. As another example of peripheral extension, we consider an epidemiological application studied earlier by Karvanen et al. (2020). The question of interest is the causal effect of salt-adding behavior on the salt intake. The high salt intake is one of the causes of hypertension (He et al., 2013). The example is based on the National Health and Nutrition Examination Survey (NHANES, https://wwwn.cdc.gov/nchs/nhanes/) 2015–2016 that is an observational study on the health and nutritional status of adults and children in the United States. The NHANES variables are already divided into categories by their content and the type of the data. In the top-down modeling, these categories may correspond to transit clusters in the causal diagram. An example of a causal diagram constructed by this approach is shown in Figure 7. The peripheral extension (Definition 12) can be used to extend the clusters. For instance, the cluster represented by the vertex a, “Salt-adding behavior”, may consists of the following variables measured in NHANES: 1. How often do you add ordinary salt to your food at the table? (Rarely 0, Occasionally 1, Very often 2) 15 Tikka, Helske and Karvanen g s i ezw u1 u2 u3 Figure 6: Causal diagram representing the effect of education level Xeon income Xi. Other variables represented in graph are gender Xg, score on Illinois Test of Psycholinguistic Abilities (ITPA) Xs, socioeconomic status of the parents Xw, and the grade point average Xzat the end of primary school. Variables Xu1, Xu2, Xu3are unobserved. 2. Did you add any salt to your food at the table yesterday? (No 0, Yes 1), and 3. How often is ordinary salt or seasoned salt added in cooking or preparing foods in your household? (Never 0, Rarely 1, Occasionally 2, Very often 3). and the variables of the cluster represented by vertex b, “Diet behavior”, may include 1. Are you on low salt/low sodium diet? 2. Are you on other special diet? (several options) 3. Number of meals not home prepared during the past 7 days 4. Number of meals from fast food or pizza place during the past 7 days The use of transit clusters provides a formal justification for the top-down modeling. Especially, Theorem 33 states sufficient conditions for the validity of conclusions made with the clustered graph. 7. Discussion We have considered clustering from two starting points. First, we started with an unclustered DAG that may have a large number of vertices and proposed algorithms for finding transit components and transit clusters, allowing us to simplify the representation of the DAG and the obtained identifying functional. Furthermore, we provided sufficient conditions for non-identifiability in a clustered DAG to imply non-identifiability in the original DAG. Second, we started with a clustered DAG where a single vertex represents a group of variables and presented the peripheral extension, a procedure for constructing all transit clusters that are compatible with the clustered DAG. We showed that an identifying functional for a causal effect in the clustered DAG remains valid in DAGs obtained via peripheral extension. A transit cluster was deliberately defined for a DAG without any reference to a causal model. This allows us to cluster vertices even before it is known which data will be available. The division into observed and unobserved variables is however hard-coded into the definition of a structural 16 Clustering and Structural Robustness o d i a b s u1 u2 Figure 7: Causal model for the salt intake example. The vertices represent the following transit clusters of variables: Salt-adding behavior Xa(represented by a single vertex a), salt intake Xs, diet behavior Xb, demographic variables Xd, occupation Xo, and income Xi. causal model where an unobserved variable cannot have parents. This restriction is taken into account in Theorems 32 and 33. The DAG-based definition of a transit cluster makes it possible to apply a workflow where Algorithm 1 is first run for the whole graph in order to find all transit components. Restrictions may then be applied to these transit components before transit clusters are constructed by Algorithm 2. The same transit components can be re-used when the causal effect in the focus is changed to a new one that implies different restrictions for the transit clusters. The examples presented in Section 6 illustrate the use of transit clusters in reducing the size of a causal diagram, simplifying identifying functionals, and speeding up identification algorithms. The identifying functional defined using the representative vertex in place of transit cluster allows a researcher to focus on the overall structure of the functional when choosing suitable estimation methods for the causal effect. Transit clusters also provide a justification for the top-down causal modeling. In addition to the use cases considered, clustering could be beneficial also in causal discovery (Spirtes et al., 2000, 2001). If a set of variables can be assumed to form a transit cluster, we may, at least theoretically, use any single variable of the set as representative of the whole cluster when considering whether the cluster and a variable outside the cluster are d-separated. In general, causal discovery methods can construct the underlying DAG only up to an equivalence class and additional challenges with finite samples may occur due to a variety of reasons, such as measurement error (Zhang et al., 2017), selection bias (Zhang et al., 2016), or missing data (Tu et al., 2019). The assumption on a transit cluster could in some cases provide the information needed to reduce these ambiguities. In future work, we would like to extend the results of Sections 4 and 5 to more general identifiability problems with multiple data sources consisting of a mix of observational and interventional distributions. We hypothesize, that at least plain transit clusters can be used to retain identifiability in more complex settings. It may also be possible to extend the definition of transit clusters to graphs where the direction of some edges is unknown. Acknowledgments 17 Tikka, Helske and Karvanen This work was supported by Academy of Finland grant numbers 311877 and 331817. Appendix A. Proofs We restate and prove all results of the paper. Lemma 6 Graph G′induced by a transit cluster Tin a DAG Gis a DAG. Proof Let tbe the single vertex in G′that corresponds to Tin G. We show that if there exists a directed path from v1to v2in G′, there cannot also exist a directed path from v2to v1. Assume first that both directed paths exist and neither of them contains t. This is a contradiction because then both paths would exist in a DAG Gas well. Next, assume without loss of generality that the directed path from v1to v2contains t. It follows that Ghas a directed path v1→. . . →r→ . . . →e→. . . →v2, where the existence of vertices r∈Re(T) and e∈Em(T) is guaranteed by the definition of transit cluster. Similarly, if the directed path from v2to v1contains t, there would a directed path from v2to v1, which together with directed path from v1to v2would create a cycle in G. If the directed path from v2to v1does not contain t, it will exist also in Gand form a cycle in G. We conclude that G′cannot have cycles and is thus a DAG. Lemma 7 Let Tand Sbe transit clusters in a DAG G= (V, E). If Re(T) = Re(S)and Em(T) = Em(S), then T=S. Proof Suppose instead that there exists t∈Tsuch that t∈ Sand that t∈ Re(T)∪Em(T). By condition 3, tis connected to a receiver or an emitter in G[T=]. Assume first that tis connected to receiver rin G[T=]. As Re(T) = Re(S), ris also a receiver for S. Follow the path from rto tand let sbe the last vertex that belongs Sand qthe next vertex that does not belong to S. If there is an edge s→q,sis an emitter for Sand if there is an edge q→s,sis a receiver for S. As Re(T) = Re(S) and Em(T) = Em(S), sis also a receiver or an emitter for T. This leads to a contradiction because by definition the edges incoming to receivers and outgoing from emitters are cut in G[T=] and the path between tand rcannot exist. The case where tis connected to an emitter in G[T=] proceeds analogously. Theorem 8 (Invariance of transit clusters) Let Tbe a transit cluster in G= (V, E)and let G′ be the induced graph where Tis replaced by a single vertex t. The set S⊂V\Tis a transit cluster in Gif and only if it is a transit cluster in G′. Proof As Sand Tare disjoint, the vertices of Sas well as the edges between vertices of Sare unaffected by the clustering of T. It follows that S′=S, where S′is the clustering equivalent set of S. We will show that ReG′(S′) = ReG(S), EmG′(S′) = EmG(S), and S′fulfills the conditions of Definition 4 both in Gand G′. As the edges between Sand V\(S∪T) are unaffected by the clustering, it suffices to consider only edges between Sand T. If a parent of ReG(S) belongs to T, condition 1 applied to Sin Gguarantees that vertex twill be a parent of all vertices in ReG(S) in G′. If tis a parent of ReG′(S′), condition 1 applied to S′in G′guarantees that any member of T that is a parent of a receiver in Gwill be a parent of all vertices in ReG(S) in G. Similarly, if a child of EmG(S) belongs to T, vertex twill be a children of all vertices in EmG(S) in G′and if tis a child of EmG′(S′), any member of Tthat is a child of an emitter in Gwill be a child of all vertices in EmG(S) in G. It follows that ReG′(S′) = ReG(S), EmG′(S′) = EmG(S) and conditions 1 and 2 are fulfilled for S′=Sboth in Gand G′. Conditions 3, 4 and 5 are fulfilled as well as they consider only paths inside S′. 18 Clustering and Structural Robustness Theorem 9 (Modularity of transit clusters) Let Tbe a transit cluster in graph G= (V, E)and G′the induced graph where Tis replaced by a single vertex t. Let S⊂V\T. The set {t} ∪ Sis a transit cluster in G′if and only if T∪Sis a transit cluster in G. Proof Denote Q=T∪Sand Q′={t} ∪ S. First, we assume that {t} ∪ Sis transit cluster in G′and show that T∪Sis transit cluster in G. Condition 1: We will show for all r∈ReG(Q) that PaG(r)\Q= PaG′(ReG′(Q′)) \Q′. First let v /∈Qto be a parent of receiver rin G. It follows that in G′, vertex vis a parent of rif r∈Sor a parent of tif r∈Tbecause v /∈Qin G. It follows that ror tis a receiver in G′and v∈PaG′(ReG′(Q′)) \Q′. Now let v∈PaG′(ReG′(Q′)) \Q′and consider two cases: a) If vis a parent of tin G′then tis a receiver in G′. Further, vis a parent of some ti∈Tin Gbecause tis a single vertex corresponding to transit cluster Tin G. It holds ti∈ReG(Q) because v /∈Q. Condition 1 of transit cluster guarantees that vis also a parent of r. b) If vis a parent of si∈Sin G′then vis a parent of si∈Salso in G because v /∈Q′in G′. Thus siis a receiver in Gand v∈Pa(Re(Q)G)G\Q. Condition 2: The proof is analogous to condition 1. Condition 3: Consider qi∈Q. Assume first that qi∈T. There exist in G′vertex vthat is a receiver for Q′or an emitter for Q′and is connected to t. Applying conditions 1, 2, 4 and 5 for transit cluster Tguarantees that there a path between qiand vin G. If v∈S, it is the required receiver or emitter for Q. If v=t, applying conditions 1, 2, 4 and 5 to transit cluster Tguarantees that set Thas the required receiver or emitter. Assume next that qi∈S. There exist in G′vertex vthat is a receiver for Q′or an emitter for Q′and is connected to qi. If v∈S, it satisfies the condition 3 for Qbecause applying conditions 4 and 5 to transit cluster Tguarantees that tcan be replaced by a path consisting of vertices in T. If v=t, applying conditions 1, 2, 4 and 5 for transit cluster Tguarantees that set Thas the required receiver or emitter. Condition 4: Assume EmG(Q)=∅and let r∈ReG(Q). a) If r∈Tthen tis a receiver in G′by the proof of condition 1. It follows that there exists e′∈EmG′(Q′) such that e′∈DeG′(t). If e′=t, it directly fulfills condition 4. If e′=t, there exists e∈EmG(T) such that e∈DeG(r), which fulfills condition 4. b) If r∈Sthen r∈ReG′(Q′) and there exists e∈EmG′(Q′) such that e∈DeG′(r). If e∈S, it fulfills condition 4 because Q′is a transit cluster. If e=t, there exists an emitter in Tthat fulfills condition 4 because Tis a transit cluster. Condition 5: The proof is analogous to condition 4. Next, we assume that T∪Sis transit cluster in Gand show that {t} ∪ Sis transit cluster in G′. Conditions 1 and 2 are already covered above when we showed that Pa(Re(Q)G)G\Q= PaG′(ReG′(Q′)) \Q′and Ch(Em(Q)G)G\Q= ChG′(EmG′(Q′)) \Q′. Condition 3: Consider qi∈Q′. Assume first that qi=t. For any ti∈Tthere exist some vertex vthat is the required receiver or emitter in G. By the definition of clustering, tand vare connected in G′. Assume next that qi∈S. There exist in Gvertex vthat is a receiver for Qor an emitter for Qand is connected to qi. If v∈S, it satisfies the condition 3. If v∈T, vertex tis the required receiver or emitter for qiin G′. Condition 4: Assume EmG′(Q)=∅and let r∈ReG′(Q′). a) If r=t, set ReG(Q)∩Tis non-empty and all members of this set fulfill condition 4 in G. Let there be a path from ri∈ReG(Q)∩Tto e∈EmG(Q) in G. It follows that either e∈Tand tis the requested emitter in G′or e∈Sand there is a path from tto ein G′and eis the requested emitter. Condition 5: The proof is analogous to condition 4. Corollary 10 (Union of transit clusters) Let disjoint sets Sand Tbe transit clusters in G. S∪Tis a transit cluster in Gif Pa∗(Re(S)) = Pa∗(Re(T)) and Ch∗(Em(S)) = Ch∗(Em(T)). 19 Tikka, Helske and Karvanen Proof Consider graph G′where the transit cluster Sis replaced by vertex sand graph G′′ where transit clusters Sand Tare replaced by vertices sand t, respectively. It is easy to check that set {s, t} is a transit cluster in G′′ under the assumption that Pa∗(Re(S)) = Pa∗(Re(T)) and Ch∗(Em(S)) = Ch∗(Em(T)). By applying Theorem 9 to G′′ we conclude that {s} ∪ Tis a transit cluster in G′. By applying Theorem 9 then to G′, we conclude that S∪Tis a transit cluster in G. Theorem 13 Let T+be a peripheral extension of a transit cluster Tin a DAG G= (V, E)and let G′be the induced graph where Tis replaced by a single vertex. Then T+is a transit cluster in the corresponding peripheral extension graph G+and G′is the induced graph of T+. Proof Let G+be the peripheral extension graph of T+. A new receiver is created by operations 6, 8 and 9. A new emitter is created by operations 7, 8 and 10. A new emitter can be created also by operation 3. Operations 6, 7, 8, 9 and 10 explicitly copy parents and children so that the conditions 1 and 2 of transit cluster hold for T+. If tiis an emitter in operation 3, it will not be an emitter in G+. Copying the children to new vertex tk+1 ensures that condition 2 is fulfilled for tk+1. Before an operation, condition 3 hold for all existing vertices in T. Condition 3 holds also in G+for all existing vertices because the operations do not change the existence of the current paths. Condition 3 holds for the new vertex tk+1 added by operations 3, 4 and 5 because condition 3 holds for ti, and tk+1 is connected to ti. Condition 3 directly holds for a receiver or an emitter added by operation 6, 7, 8, 9 or 10. We also conclude that if there exist a path in Gfrom r∈ReG(T) to e∈EmG(T), there also exist a path from rto ein G+because operation 1 does not remove edges or vertices, operations 2 and 3 preserve directed paths, operations 4 and 5 do not affect receivers and emitters, operations 6, 7 and 8 explicitly add an edge to create the required directed path, and operations 9 and 10 do not apply to cases where Thas both receivers and emitters. It follows that the conditions 4 and 5 of transit cluster hold for T+. Graph G′is the induced graph of G+because PaG∗(ReG∗(T∗)) \T∗= PaG(ReG(T)) \T and ChG+(EmG+(T+)) \T+= ChG(EmG(T)) \T. Theorem 14 Let G′be the induced graph of a transit cluster constructed from Gby replacing set Tby a single vertex t. Then Gand Tcan be constructed by iteratively applying operations of Definition 12 to transit cluster {t}in G′. Proof At the beginning, all vertices in Tare unmarked, i.e., they are not yet included in the graph to be constructed. Assume first Re(T)=∅and Em(T)=∅. Apply operation 3 to tto create set A0 that has exactly one receiver rand one emitter e. Choose rto be an arbitrary member of Re(T) to rand choose eto be an arbitrary member of Em(T) that is a descendant of r. Apply operation 2 iteratively to construct a path corresponding to the path from rto ein T. Now all vertices of T that belong to this path are marked. Form a set A2of such receiver-emitter pairs in Tthat there is a directed path from the receiver to the emitter. While there are unprocessed pairs in A2, do the following operations: If both the receiver and the emitter are unmarked, apply operation 8 to create the receiver-emitter pair and apply operation 2 to create the directed path between them. If the receiver is unmarked and the emitter is marked, apply operation 6 to connect the receiver to a vertex that is on the receiver-emitter path and is an ancestor of all marked vertices on this path. Then apply operation 2 iteratively to create all vertices of the receiver-emitter path. If the receiver is marked and the emitter is unmarked, apply operation 7 to connect the emitter to a vertex that is on the receiver-emitter path and is a descendant of all marked vertices on this path. Then apply operation 2 iteratively to create all vertices of the receiver-emitter path. If both the receiver and the emitter are marked, apply first operation 1 and then iteratively operation 2 to create the directed path between them. 20 Clustering and Structural Robustness Next process all vertices of Tthat have not been marked yet. Apply operations 4 and 5 to connect them to a vertex that is their child or parent. Repeat this until there are no vertices left. Finally, process all edges of Tand use operation 1 to add the missing edges. Next assume Re(T) = ∅and Em(T)=∅. Apply operation 9 to add all receivers. Then process all vertices of Tthat have not been marked yet similar way as above. Finally process all edges of Tand use operation 1 to add the missing edges. The case Re(T) = ∅and Em(T)=∅proceed analogously. Theorem 16 (Transit cluster decomposition) Let Tbe a transit cluster in a DAG G= (V, E). If Tis not a transit component, then there exists a transit cluster Sand a transit component Rsuch that T=S∪Rand S∩R=∅. Proof Because Tis not a transit component, there exists a set R⊂Tsuch that G[R] is connected and such that Ris not connected to S=T\Rin G[T]. Note that such a set necessarily exists, because at least one vertex tin Tis not connected to T\ {t}in G[T] due to Tnot being a transit component. Next, we show that Sand Rare transit clusters. If Thas receivers, then the receivers of Sand Rmust have the same parents as the receivers of Tbecause Sand Rare disconnected in G[T], and because Tis a transit cluster, thus satisfying condition 1. Analogously, if Thas emitters then the children of the emitters of Sand Rmust be the same, satisfying condition 2. Conditions 3 through 5 are satisfied for Sand Rbecause any path from an emitter to a receiver in Texists either entirely in Sor Rbecause Sor Rare disconnected in G[T]. Thus Sand Rare disjoint transit clusters such that T=S∪Rand Ris a transit component because it is connected in G[R]. Lemma 17 FindTrComp always terminates for valid inputs Gand R. Proof The sets VCh and VPa are finite, and for any set Aconstructed on line 12, there is only a finite number of possible components C(G[A]) in the innermost for-loop. Thus, there is finite number of iterations in total across all for-loops, and all other operations are well-defined and nonrecursive. Theorem 18 (Soundness of FindTrComp) Let G= (V, E)be a DAG, R⊆Vand A=FindTrComp(G, R), then A⊆TG|R. Proof We show that if FindTrComp(G, R) reaches line 20, then the set being added to Ais a transit component in G. Because TG|R⊆ TGfor all R⊂V, we can assume that R=V. Let Vi, Vj be a pair defined on lines 5 and 6 such that line 20 is triggered in the same iteration. Let Zand W be defined as dictated by lines 7 and 8, respectively. The condition on line 9 must not have been fulfilled, which means that if Zis non-empty, all of its members have parents, and if Wis non-empty, all of its members have children. Because the condition on line 11 is fulfilled, we know that at least one of the sets Zand Wis non-empty. We summarize the construction of Aon line 12. The set contains all vertices connected to Z∪W when incoming edges of Zand outgoing edges of Whave been removed in G. The intuition is to construct a set Asuch that Zwould be equal to Re(A) and Wwould be equal to emi(A). The construction together with lines 7 and 8 ensures that there will be a path from any member of Zto some member of Wand vice versa, which is required to satisfy conditions 4 and 5 of Definition 4. The line 12 directly enforces condition 3. However, this construction alone does not guarantee that Zand Wwill be the set of receivers and emitters of A, respectively, because Zmight not have the same parents outside of A, or Wmight not have the same children outside of A. It might also be the case that Ais not connected in G[A]. 21 Tikka, Helske and Karvanen Next, we break Ainto its components in G[A] and iterate over them on line 14. Conditions 3, 4 and 5 remain valid for each component. Because line 20 is reached, there must be at least one component Akfor which line 19 evaluates to true. This means that for such a set Ak, the sets Zkand Wkhave the same set of parents and children outside of Akas any of their members, respectively. This means that the remaining conditions 1 and 2 of Definition 4 are satisfied by Ak, making Aka transit component. Theorem 19 (Completeness of FindTrComp) Let G= (V, E)be a DAG, R⊆V, and A= FindTrComp(G, R)then TG|R⊆ A. Proof We show that if T⊂Vis a transit component in G, then it will be a member of the set Areturned by FindTrComp. Because TG|R⊆ TGfor all R⊂V, we can assume that R=V. Definition 4 implies that there exists a pair of vertices vi, vj∈Vsuch that Re(T)⊆Ch∗(vi) and Em(T)⊆Pa∗(vj) by conditions 1 and 2. Denote Vi= Ch∗(vi) and Vj= Pa∗(vj) with respect to the definitions on lines 5 and 6, respectively. Conditions 4 and 5 further imply that Re(T)⊆An(Em(T)) and Em(T)⊆De(Re(T)). Therefore Re(T)⊆Vi∩An(Vj) and Em(T)⊆Vj∩De(Vi). At this point, we make an important choice; if there exist multiple vi, vjpairs that satisfy these conditions, we choose one that minimizes the corresponding intersections Vi∩An(Vj) and Vj∩De(Vi). More precisely, we assume that for our choice vi, vjthere does not exist v′ i, v′ jsuch that V′ i∩An(V′ j)⊂ Vi∩An(Vj) and V′ j∩De(V′ i)⊂Vj∩De(Vi). We call this the minimal representative choice in the context of this proof and illustrate the meaning of this choice with an example. It is easy to verify that B={r1, e1}is a transit cluster in the graph of Figure 3(a). Suppose that we had chosen vi=xand vj=yresulting in Vi= Ch∗(x) = {r1, r2, r3}and Vj= Pa∗(y) = {e1, e2}. This is a valid choice because Re(B)⊆Vi,Em(B)⊆Vj, and for the intersections we have that Vi∩An(Vj) = Vi, Vj∩De(Vi) = Vj. However, x, y is not the pair that minimizes these intersections. Choosing instead V′ i= Ch∗(r2) = {r1}and V′ j= Pa∗(e2) = {e1}we have that Re(B) = V′ i,Em(B) = Vjand for the intersections it holds V′ i∩An(V′ j) = V′ i,V′ j∩De(V′ i) = V′ j. Now V′ i⊂Viand V′ j⊂Vjwhich shows that our initial choice x, y was not minimal, and r2, e2is actually the minimizing pair. Let Z=Vi∩An(Vj) and W=Vj∩De(Vi) as defined on lines 7 and 8, respectively. Because Tis a transit component, it must have either receivers or emitters, which by definition have parents and children outside of T. This means that at least one of the sets Zand Wis non-empty and Zhas parents in Gor Whas children in G. Thus, the for-loop does not continue on line 9, and we move on to line 11, which is satisfied for the same reason. Next, we construct the set Aon line 12. Importantly, we must show that T⊆A. Suppose instead that there exists t∈Tsuch that t∈ Aand tis not a receiver or emitter of T. Because Tis a transit component, then tmust be connected to Re(T)∪Em(T) when incoming edges of Re(T) and outgoing edges of Em(T) have been removed. Due to the construction of A, this leaves the only option that tis connected to Re(T)∪Em(T) only via paths that intersect Z\Re(T) or W\Em(T) and is no longer connected to Re(T)∪Em(T) when incoming edges of Zand outgoing edges of Ware removed. Let Z′and W′denote those subsets of Zand Wthat only contain vertices that intersect such paths, respectively. This means that it must also be the case that Z′⊂Tand W′⊂Tbecause Tis connected in G[T] and thus entire connecting path is in T. Suppose that the path has an incoming edge to Z′\Re(T) and let tz∈Z′\Re(T) be a vertex on this path. Because tz∈Talso, we have a contradiction, because tzis not a receiver of Tbut Z′is not empty which means that tzmust have parents that are not members of T. The case for the path intersecting W′\Re(T) is analogous. Thus we affirm that T⊆A. Next, we must show that Tis a component of G[A]. Because T⊆A, there must be a component Akof G[A] such that T⊆Ak. Let Zkand Wkbe defined according to lines 15 and 16, and suppose instead that there exists a∈Ak\Tsuch that ais connected to Tin G[Ak]. Let a′be a vertex 22 Clustering and Structural Robustness in Ak\Ton the path from ato Tin G[Ak] such that it is either parent or a child of T. As T and Akare both connected, it follows from the construction of Athat if a′is a parent of T, then a′∈Zk\Re(T) or if a′is a child of T, then a′∈Wk\Em(T). Suppose that a′∈Zk\Re(T). Now, because a′is a parent of T, it must a parent of all of its receivers. Furthermore, ChG[A](a′)⊂Zk, i.e., a′necessarily has at least one fewer child than the representative vi(mainly, a′itself). Then ChG[A](a′)∩AnG[A](Vj)⊂Vi∩AnG[A](Vj), which contradicts the minimal representative choice. The case for a′∈Wk\Em(T) is analogous. Hence, Tis a component of G[A]. We can now deduce that Zk∩T= ReG(T) and Wk∩T= EmG(T). If there existed z∈Zk∩T that is not a receiver of T, we would have a contradiction, because Tis a transit component, and zk∈Ch∗ G(vi) meaning that Twould be connected to Pa∗(T) via a vertex that is not its receiver. The case for Wkis once again analogous. The sets ZPa and WCh constructed on lines 17 and 18 are simply the common parents of ReG(T) and common children EmG(T), and because Tis a transit component, the check of line 19 evaluates to true as all receivers have the same parents and all emitters have the same children in G. Finally, FindTrComp adds Tto the set Aon line 20. Theorem 20 FindTrComp outputs all restricted transit components of a DAG G= (V, E)with respect to R⊆Vin O(|V|4+|V|3|E|)time. Proof Let n=|V|and m=|E|. Any restrictions on the vertices that are allowed to be members of transit clusters will only lead to a decrease in runtime, so we assume that R=V. Because the algorithm repeatedly accesses sets of parents, children, ancestors, and descendants of the vertex sets in the input graph G, we assume that these are derived as a preprocessing step, which evaluates each vertex and edge once in the worst case, thus taking O(n+m) time to construct the sets (for example, via a depth-first search). Thus any future access to these sets can be carried out in constant time. The maximum number of unique parent and child sets in the collections VPa and VPa occurs when the parents and children of each vertex are unique. Thus there are at most niterations in both of the two outermost for-loops on lines 5 and 6, leading to n2iterations in total. Each of the constructions and verifications on lines 7–11 can be evaluated in O(n) time with help of the preprocessing step. The construction of the candidate set Aand its components C(G[A])) on lines 12 and 14 takes O(n+m) time in the worst case, when the entire graph has to be traversed (again, for example by a single depth-first search for both tasks simultaneously, when the search reaches a vertex vthrough an incoming edge to Zor an outgoing edge from W, it simply immediately returns to the previous vertex without discovering v.). There are at most ncomponents of G[A], which leads to at most n iterations in the innermost for-loop on line 14. During lines 15–20, each operation can be carried out in O(n) time, once again taking advantage of the preprocessing step. Combining all of the previous observations gives us O(n+m) + n2(n+ (n+m) + n2)=O(n4+n3m) = O(|V|4+|V|3|E|). Lemma 21 Let Tbe a transit component of a DAG G= (V, E)and let G′= (V′, E′)be the induced graph of the clustering with trepresenting the set T. If there does not exist a transit component S of Gsuch that T∩S=∅and T\S=∅, then |TG|=|TG′|+|TG[T]|. Proof From the assumptions it follows that for any transit component Sof G, we have that either T⊂Sor T∩S=∅. Thus, by Theorem 8, there must be an equal number of transit components that do not contain Tin Gand those that do not contain tin G′. Similarly by Theorem 9 there must be an equal number of transit components that contain Tfor Gand those contain tfor G′. In this 23 Tikka, Helske and Karvanen case we apply the theorem to S′=S\Tand Tto make the previous observation. This means that the only difference in the number of transit components of Gand G′is that in G, the set Tinduces |TG[T]|transit components, whereas in G′the set {t}induces a single transit component. However, the difference is offset by one because Tis not a transit component in G[T]. Theorem 22 Let G= (V, E)be a DAG. Then |TG| ≤ |V|(|V|+1) 2−1. Proof Because FindTrComp is sound and complete, we take advantage of the algorithm, and consider pairs of sets Viand Vjdefined on lines 6 and 5, and the corresponding sets Zand W. We consider cases: 1) each pair (Vi, Vj) produces at most one transit component, 2) at least one pair (Vi, Vj) produces more than one transit component, and in addition 3) show that the equality |TG|=|V|(|V|+ 1)/2−1 is attainable. 1. In the first case, the maximum number of pairs (Vi, Vj) such that Vi∩An(Vj)=∅and Vj∩ De(Vi)=∅is clearly |V|(|V|+1) 2−1, because Gis a DAG. Assuming that each pair where at least one of the aforementioned intersections is nonempty produces a distinct transit component, the claim follows. 2. In the second case, we must consider the repercussions of multiple transit components being induced by the same pair (Vi, Vj). Also, we will associate each transit component Twith a unique representative pair (Vi, Vj) as follows: if it occurs that a transit component Tis induced by two distinct pairs (Vi, Vj) and (V′ i, V ′ j), we choose the pair that induces the smallest number of transit components. In the case that there are still multiple such pairs, the choice is arbitrary. Next, we must consider two separate scenarios: a) the sets Zand Wcorresponding to the pair (Vi, Vj) defined on lines 7 and 8 are both nonempty, and b) one of the sets Zand Wis empty. a) Suppose that the pair (Z, W) induces ktransit components, A1, . . . , Ak, defined according to line 4 which are the components of A, defined according to line 12. Let n=|V|,ni=|Ai| for each i= 1, . . . , k, and n0=|V|−|A|. Suppose that for some Aj, there exists a transit component Tof Gsuch that Aj∩T=∅and Aj\T=∅. Because Tis a transit component and thus connected, it must contain at least one child of an emitter of Ajor a parent of a receiver of Aj. Without loss of generality, assume that a child cof an emitter of Ajis a member of T. However, this also makes ca child of an emitter eof at least one other transit component Ai,i=j. It cannot be the case that there would exist a child of an emitter of Ajsuch that it is not a child of an emitter of Ai=Ajbecause we have assumed that the current pair (Vi, Vj) produces the smallest number of transit components. Now, if e∈ T, we have a contradiction, because Aj\T=∅, there must a path from Ajto a receiver of T, but there cannot be a path from eto the same receiver, because Aiand Aj are not connected in G[A]. If e∈T, it follows that Ai⊂Tusing the same argument with nodes along any path from a receiver of Aito ethat always exists due to the definition of a transit cluster. Now, because Zis not empty, there is a parent pof a receiver of Aj that is also a parent of a receiver of Ai. If p∈ Twe have a contradiction, because there is a receiver of Tin Aiwhich has different parents than a receiver of Tin Aj. If p∈T, this makes pan emitter of Tand we have again a contradiction, because there would be a cycle in the induced graph of T, as there is a directed path from an emitter to a receiver in T. We conclude that no such transit component Tcan exist. The case where Tcontains instead a parent of a receiver of Ajis analogous. We can now apply Lemma 21 repeatedly to each set A1, . . . , Ak. Let G′denote the graph obtained after clustering each Ai,k= 1, . . . , k. We have that |TG|=|TG′|+ k X i=1 |TG[Ai]|. 24 Clustering and Structural Robustness S. Greenland, J. Pearl, and J. Robins. Causal diagrams for epidemiologic research. Epidemiology, 10(1):37–48, 1999. F. J. He, J. Li, and G. A. MacGregor. Effect of longer term modest salt reduction on blood pressure: Cochrane systematic review and meta-analysis of randomised trials. BMJ, 346:f1325, 2013. J. Helske, S. Tikka, and J. Karvanen. Estimation of causal effects with small data in the presence of trapdoor variables. Journal of the Royal Statistical Society: Series A (Statistics in Society), 184 (3):1030–1051, 2021. G. W. Imbens. Potential outcome and directed acyclic graph approaches to causality: Relevance for empirical practice in economics. Journal of Economic Literature, 58(4):1129–1179, 2020. J. Karvanen, S. Tikka, and A. Hyttinen. Do-search: A tool for causal inference and study design with multiple data sources. Epidemiology, 32(1):111–119, 2020. E. M. Kornaropoulos and I. G. Tollis. DAGView: An approach for visualizing large graphs. In W. Didimo and M. Patrignani, editors, Graph Drawing, pages 499–510, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. J. J. R. Lee and I. Shpitser. Identification methods with arbitrary interventional distributions as inputs. arXiv preprint arXiv:2004.01157, 2020. S. Lee, J. Correa, and E. Bareinboim. General identifiability with arbitrary surrogate experiments. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence, 2019. A. Magrini, S. D. Blasi, and F. M. Stefanini. A conditional linear Gaussian network to assess the impact of several agronomic settings on the quality of Tuscan Sangiovese grapes. Biometrical Letters, 54(1):25–42, 2017. F. D. Malliaros and M. Vazirgiannis. Clustering and community detection in directed networks: A survey. Physics reports, 533(4):95–142, 2013. S. Nisimov, Y. Gurwicz, R. Y. Rohekar, and G. Novik. Improving efficiency and accuracy of causal discovery using a hierarchical wrapper. In The 37th Conference on Uncertainty in Artificial Intelligence, Workshop on Tractable Probabilistic Modeling, 2021. P. Parviainen and S. Kaski. Learning structures of Bayesian networks for variable groups. International Journal of Approximate Reasoning, 88:110–127, 2017. J. Pearl. Comment: graphical models, causality and intervention. Statistical Science, 8(3):266–269, 1993. J. Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669–688, 1995. J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2nd edition, 2009. H. Purchase. Which aesthetic has the greatest effect on human understanding? In G. DiBattista, editor, Graph Drawing, pages 248–261, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg. R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2022. URL https://www.R-project.org/. P. R. Rosenbaum and D. B. Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41–55, 1983. 31 Tikka, Helske and Karvanen D. Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of Educational Psychology, 66:688–701, 1974. I. Shpitser and J. Pearl. Identification of joint interventional distributions in recursive semiMarkovian causal models. In Proceedings of the 21st National Conference on Artificial Intelligence, volume 2, pages 1219–1226. AAAI Press, 2006. G. Skorstad. Clustered causal ordering. In Proceedings of 4th International Workshop on Qualitative Physics, pages 290–299, 1990. P. Spirtes, C. Glymour, and R. Scheines. Constructing Bayesian networks models of gene expression networks from microarray data. In Proceedings of the Atlantic Symposium on Computational Biology, 2000. P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT Press, 2nd edition, 2001. P. W. G. Tennant, E. J. Murray, K. F. Arnold, L. Berrie, M. P. Fox, S. C. Gadd, W. J. Harrison, C. Keeble, L. R. Ranker, J. Textor, G. D. Tomova, M. S. Gilthorpe, and G. T. H. Ellison. Use of directed acyclic graphs (DAGs) to identify confounders in applied health research: review and recommendations. International Journal of Epidemiology, 50(2):620–632, 4 2021. S. Tikka and J. Karvanen. Identifying causal effects with the R package causaleffect. Journal of Statistical Software, Articles, 76(12):1–30, 2017a. S. Tikka and J. Karvanen. Simplifying probabilistic expressions in causal inference. The Journal of Machine Learning Research, 18(1):1203–1232, 2017b. S. Tikka and J. Karvanen. Enhancing identification of causal effects by pruning. The Journal of Machine Learning Research, 18(194):1–23, 2018. S. Tikka, A. Hyttinen, and J. Karvanen. Identifying causal effects via context-specific independence relations. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch´e-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. S. Tikka, A. Hyttinen, and J. Karvanen. Causal effect identification from multiple incomplete data sources: A general search-based approach. Journal of Statistical Software, 99(5), 2021. R. Tu, C. Zhang, P. Ackermann, K. Mohan, H. Kjellstr¨om, C. Glymour, and K. Zhang. Causal discovery in the presence of missing data. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019. T. Verma. Graphical aspects of causal models. Technical Report R-191, UCLA, 1993. K. Zhang, J. Zhang, B. Huang, B. Sch¨olkopf, and C. Glymour. On the identifiability and estimation of functional causal models in the presence of outcome-dependent selection. In Proceedings of the 32rd Conference on Uncertainty in Artificial Intelligence, 2016. K. Zhang, M. Gong, J. Ramsey, K. Batmanghelich, P. Spirtes, and C. Glymour. Causal discovery in the presence of measurement error: Identifiability conditions. In UAI 2017 Workshop on Causality: Learning, Inference, and Decision-Making, 2017. 32