betaFeedback

WorksMathematics

Efficient and Practical Clustering of Variables in Causal Graphs

Abstract

Clustering variables in a graph may improve visual clarity and simplify causal inference. Harnessing the full potential of clustering requires an automated method to detect useful clusters in a graph. We introduce a novel class of clusters called conduits, and present a sound, complete and efficient algorithm for detecting all conduits in the graph. In addition to algorithmic detectability, conduits appear naturally in causal graphs stemming from real-world applications, enabling substantial size reduction. Furthermore, the structure of conduits enables the application of known identifiability results regarding clustering. We demonstrate these properties in a simulation study with real-world graphs.

Introduction

Directed acyclic graphs (DAGs) and their extensions are often used to visualize causal mechanisms. However, large graphs may render a causal model unsuitable for practical work due to the complexity of the graphical representation. In such graphs, many of the variables may describe parts of a single mechanism, such as financial indicators of a company or items of a health questionnaire. Merging such variables into a single vertex, i.e., clustering them, makes the graph easier to read and can simplify causal effect identification [15, 7]. Selecting the clusters by hand from large graphs is tedious and error-prone: the number of candidate vertex sets grows exponentially with the size of the graph while arbitrary clustering can change which causal effects are identifiable—that is, an effect may be identifiable in the original graph but not in the clustered graph. Clustering has been approached from various viewpoints, including already clustered graphs [e.g. 1, 4] and clustering in causal discovery [e.g. 6, 5].

In this work, we consider the setting where the causal graph is known, and the task is to find clusters within it. Zeng et al. [17] presented a method to cluster a causal graph with the aim of preserving the dd-separations of the original graph through a heuristic algorithm. Tikka et al. [15] defined transit clusters and developed an algorithm with polynomial delay for finding all transit clusters of a graph. Tikka et al. [15] and Tabell et al. [13] showed that under additional assumptions clustering a transit cluster is an identification invariant operation: a set of causal effects is identifiable in the clustered graph if and only if it is identifiable in the original graph. Ny­känen et al. [7] considered identification invariance for a broader class of coherent clusters, which includes transit clusters, and gave sufficient conditions under which clustering a coherent cluster preserves identifiability of causal effects.

©2026 Otto Tabell, Jani Nykänen, Santtu Tikka and Juha Karvanen.

License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/.

However, none of the previous work provides a class of clusters which simultaneously preserve identification invariance, are efficiently discoverable, and occur broadly in real-world causal graphs. The clusterings of Zeng et al. (2025) are not guaranteed to preserve the identifiability of causal effects. Although the algorithm of Tikka et al. (2023) has polynomial delay, a graph can have exponentially many transit clusters, so finding all of them takes exponential time. Moreover, the definition of transit clusters is somewhat restrictive, which may limit their applicability in real-world causal graphs. Finally, the results of Nykanen et al. (2026) apply to any coherent cluster, but the authors did not consider how such clusters could be found.

The aforementioned limitations motivate us to define conduits, a class of coherent clusters designed with the following properties in mind. First, the identification invariance results of Nykanen et al. (2026) can be applied to conduits because they are coherent. Second, all conduits of a graph can be found in polynomial time. Third, conduits occur naturally in causal graphs from real-world applications, which makes them broadly applicable. We present a sound and complete polynomial-time algorithm for finding all conduits of a graph. In a simulation study on causal graphs from real-world applications with added latent confounders, we compare our algorithm with the algorithm of Tikka et al. (2023), and we illustrate the use of conduits with a model of insurance claim costs.

An implementation of the algorithm and codes for the practical examples in the R language [8 version 4.6.1] are available in https://github.com/ottotabell/conduit.

Notation and Definitions

We use the convention that an upper case letter with a bold typeface denotes a set, for instance V\mathbf{V}, and an upper case letter without bolding denotes elements of the corresponding set, e.g., V∈VV \in\mathbf{V}. When VV is considered a variable, then a lower case letter vv is used in value assignments, e.g., V=vV = v. Similarly, assigning a value to a vector of variables V\mathbf{V} is denoted by V=v\mathbf{V} = \mathbf{v}.

A directed acyclic graph (DAG) is a pair G=(V,E)\mathcal{G} = (\mathbf{V}, \mathbf{E}), where V\mathbf{V} is the set of vertices and E\mathbf{E} is the set of directed edges, denoted by arrows Vi→VjV_i \to V_j, such that there are no directed cycles in G\mathcal{G}. For sets A,B⊆V\mathbf{A}, \mathbf{B} \subseteq\mathbf{V} in a DAG G=(V,E)\mathcal{G} = (\mathbf{V}, \mathbf{E}), we denote by Pa⁡G(A)\operatorname{Pa}_{\mathcal{G}}(\mathbf{A}), Ch⁡G(A)\operatorname{Ch}_{\mathcal{G}}(\mathbf{A}), An⁡G(A)\operatorname{An}_{\mathcal{G}}(\mathbf{A}) and De⁡G(A)\operatorname{De}_{\mathcal{G}}(\mathbf{A}) the parents, children, ancestors and descendants of the vertices of A\mathbf{A} (including A\mathbf{A} itself) in G\mathcal{G}, respectively. If the set A\mathbf{A} is excluded from the respective sets, then an asterisk ∗^{*} is included (e.g., Pa⁡G∗(A)=Pa⁡G(A)∖A\operatorname{Pa}_{\mathcal{G}}^{*}(\mathbf{A}) = \operatorname{Pa}_{\mathcal{G}}(\mathbf{A}) \setminus\mathbf{A}). In the case of a singleton set, that is, A={A}\mathbf{A} = \{A\}, we omit the curly brackets (e.g., Ch⁡G∗(A)=Ch⁡G∗({A})\operatorname{Ch}_{\mathcal{G}}^{*}(A) = \operatorname{Ch}_{\mathcal{G}}^{*}(\{A\})).

We are interested in DAGs induced by structural causal models.

Definition 1 (Structural causal model). A structural causal model (SCM) is a tuple M=(V,U~,F,p)\mathcal{M} = (\mathbf{V}, \widetilde{\mathbf{U}}, \mathbf{F}, p) consisting of the following objects:

  • A vector of observed random variables V\mathbf{V}, and a vector of unobserved random variables U~\widetilde{\mathbf{U}}.

  • A family of functions F=(fV)V∈V\mathbf{F} = (f_V)_{V \in\mathbf{V}} such that each fV∈Ff_V \in\mathbf{F} is a map from the state space of Pa⁡(V)\operatorname{Pa}(\mathbf{V}) to the state space of V\mathbf{V}, where Pa⁡(V)⊆(V∪U~)∖{V}\operatorname{Pa}(\mathbf{V}) \subseteq(\mathbf{V} \cup\widetilde{\mathbf{U}}) \setminus\{V\}, such that F\mathbf{F} forms a map from the state space of U~\widetilde{\mathbf{U}} to the state space of V\mathbf{V}. Accordingly, each random variable V∈VV \in\mathbf{V} is defined by the corresponding structural equation V=fV(Pa⁡(V))V = f_V(\operatorname{Pa}(V)).

  • A joint probability distribution pp of the unobserved variables U~\widetilde{\mathbf{U}}.

We only consider recursive SCMs, i.e., models where the unique solution of F\mathbf{F} in terms of U~\widetilde{\mathbf{U}} is obtained by recursively substituting each W∈Pa⁡(V)∩VW \in\operatorname{Pa}(V) \cap V in every function fV∈Ff_V \in\mathbf{F} with their corresponding functional representation with respect to fW∈Ff_W \in\mathbf{F}. Moreover, we restrict our attention to SCMs that are semi-Markovian, that is, models whose unobserved variables U~\widetilde{\mathbf{U}} admit a partition U~=U‾∪U\widetilde{\mathbf{U}} = \overline{\mathbf{U}} \cup\mathbf{U}, where U‾\overline{\mathbf{U}} is the set of dedicated error terms (i.e., U∈U‾U \in\overline{\mathbf{U}} if and only if UU is present in exactly one structural equation), and U\mathbf{U} consists of those unobserved variables that are present in exactly two structural equations. A motivation for this restriction is described below.

An SCM M\mathcal{M} induces a causal graph, that is, a DAG G=G(M)=(V∪U,E)\mathcal{G} = \mathcal{G}(\mathcal{M}) = (V \cup\mathbf{U}, \mathbf{E}), where the vertices represent the variables V∪UV \cup\mathbf{U} in M\mathcal{M}, and the directed edges in E\mathbf{E} point from the members of Pa⁡(V)\operatorname{Pa}(V) to VV. The dedicated error terms are omitted from the causal graphs, i.e., all members of U\mathbf{U} have exactly two children in G\mathcal{G}. In general we make no distinction between the variables of the model and their corresponding vertices in the induced causal graph.

Vertices of VV and U\mathbf{U} are called observed and unobserved vertices (of G\mathcal{G}), respectively. Unobserved vertices are presented in figures using bidirected (dashed) edges without specifying the unobserved vertex itself (i.e., a fork Vi←U→VjV_i \leftarrow U \rightarrow V_j, where U∈UU \in\mathbf{U}, is represented as Vi↔VjV_i \leftrightarrow V_j). Given a set W⊆V∪UW \subseteq V \cup\mathbf{U}, we denote by W+W^+ the set WW augmented with all unobserved vertices whose both children are in WW, that is, W+=W∪{U∈U:Ch⁡G∗(U)⊆W}W^+ = W \cup\{U \in\mathbf{U} : \operatorname{Ch}_{\mathcal{G}}^*(U) \subseteq W\}.

The induced DAG of a general causal model can have unobserved vertices with more than two children, in which case the latent projection [16] can be applied to project the induced DAG into a DAG where each unobserved vertex has exactly two children. This operation preserves all conditional independence relations implied by the DAG. An alternative way to formulate semi-Markovian causal models is to use acyclic directed mixed graphs (ADMGs, Richardson, 2003; Richardson et al., 2023), which explicitly allow bidirected edges in graphs.

Next we recall the definition of identifiability of causal effects.

Definition 2 (Identifiability). Given a causal graph G=(V∪U,E)\mathcal{G} = (V \cup\mathbf{U}, \mathbf{E}) and disjoint vertex sets X,Y⊆VX, Y \subseteq V, the causal effect p(y∣do⁡(x))p(\mathbf{y} \mid\operatorname{do}(\mathbf{x})) is identifiable from p(v)p(\mathbf{v}) in G\mathcal{G} if p1(y∣do⁡(x))=p2(y∣do⁡(x))p_1(\mathbf{y} \mid\operatorname{do}(\mathbf{x})) = p_2(\mathbf{y} \mid\operatorname{do}(\mathbf{x})) for every pair of distributions p1,p2p_1, p_2 induced by SCMs compatible with G\mathcal{G} such that p1(v)=p2(v)p_1(\mathbf{v}) = p_2(\mathbf{v}) for all valid value assignments V=vV = v.

To ensure that all causal effects and identifying functionals are well-defined, we restrict ourselves to study identifiability from distributions that satisfy p(v)>0p(\mathbf{v}) > 0 for all value assignments V=vV = v.

We are interested in reducing the size of a DAG by replacing a vertex set (i.e., a cluster) by a single vertex—an operation which we call clustering. A formal definition of this graph operation is described below.

Definition 3 (Clustering). Let G=(V∪U,E)\mathcal{G} = (V \cup\mathbf{U}, \mathbf{E}) be a causal graph. Clustering a vertex set T⊆V\mathbf{T} \subseteq V induces a directed graph G′=(V′∪U′,E′)\mathcal{G}' = (V' \cup\mathbf{U}', \mathbf{E}') such that:

  • V′=(V∖T)∪{T}V' = (V \setminus\mathbf{T}) \cup\{\mathbf{T}\}, where the vertex T\mathbf{T} represents the clustered set T\mathbf{T}, and U′=U∖{U∈U∣Ch⁡G∗(U)⊂T}\mathbf{U}' = \mathbf{U} \setminus\{U \in\mathbf{U} \mid\operatorname{Ch}_{\mathcal{G}}^*(U) \subset\mathbf{T}\}, that is, all unobserved vertices whose both children are in the set T\mathbf{T} are excluded from U′\mathbf{U}'.

  • The set of edges E′∗isobtainedfrom∗\mathbf{E}' *is obtained from*\mathbf{E}$ by removing all edges connected to T\mathbf{T} (including the edges Ti→TjT_i \to T_j, where Ti,Tj∈TT_i, T_j \in\mathbf{T}), and adding new edges connecting T\mathbf{T} to (V′∪U′)∖{T}(V' \cup\mathbf{U}') \setminus\{\mathbf{T}\} such that the edge Wi→TW_i \to\mathbf{T} or T→Wi\mathbf{T} \to W_i is in E′\mathbf{E}' if and only if there is a vertex Tj∈TT_j \in\mathbf{T} and an edge Wi→TjW_i \to T_j or Tj→WiT_j \to W_i in E\mathbf{E}, respectively.

We only consider clustering operations that induce a DAG, in which case G′\mathcal{G}' is a causal graph. Without this restriction, clustering can create a directed cycle in the clustered graph, such as in Figure 1a.

Examples demonstrating clustering and conduits

Figure 1. (a) Clustering the set T1={T1,T2}T_1 = \{T_1,T_2\} creates a directed cycle in the clustered graph. (b) Clustering the set T2={T1,T2}T_2 = \{T_1,T_2\} creates a new path from V1V_1 to V2V_2, which also renders the causal effect p(v2∣do⁡(v1))p(v_2 \mid\operatorname{do}(v_1)) nonidentifiable. (c) The cluster T3={T1,T2,T3,T4,T5,T6}T_3 = \{T_1,T_2,T_3,T_4,T_5,T_6\} is a conduit. (d) T4={T1,T2}T_4 = \{T_1,T_2\} fulfills all conditions of a conduit except for (A). Figure 1: Examples demonstrating why stronger conditions than Definition 3 are desirable with clustering (top row), and the nature of the conditions of a conduit (bottom row, Definition 6).

Given an SCM M\mathcal{M} that induces a causal graph G\mathcal{G}, there exists a causal model M′\mathcal{M}' which induces the clustered graph G′\mathcal{G}' such that M′\mathcal{M}' can be constructed from M\mathcal{M} by replacing the set of variables T\mathbf{T} with a single vector-valued variable TT that has members of T\mathbf{T} as its components, and modifying the structural equations of TT and its children (i.e., those variables whose structural equations contain variables in T\mathbf{T}) accordingly. The causal model M′\mathcal{M}' is necessarily semi-Markovian if M\mathcal{M} is semi-Markovian because U′⊆U\mathbf{U}' \subseteq\mathbf{U}.

If there exists U∈UU \in\mathbf{U} whose both children are in the set T\mathbf{T}, then after clustering the vertex UU has only one child, namely the vertex TT, and by convention we omit unobserved vertices with only one child (i.e., the dedicated error terms) in causal graphs, which is the reason why such unobserved vertices are not included in U′\mathbf{U}'.

We disallow clustering unobserved vertices (i.e., T∩U=∅\mathbf{T} \cap\mathbf{U} = \varnothing) to avoid ambiguity regarding whether the vertex TT representing the cluster T\mathbf{T} should be considered observed or unobserved. Moreover, as stated above, unobserved vertices whose both children are in the cluster are implicitly clustered together with their children. Finally, this way we can represent unobserved vertices using bidirected edges in figures for visual clarity.

Conduits

While Definition 3 describes how a clustering operation is carried out, the definition itself is too general for practical considerations. Our aim is to define a clustering operation with the following properties:

  1. Identification invariance: The clusters should carry properties that enable the application of theoretical results related to identification invariance (Appendix § 7).

  1. Efficient detection: A set of potential clustering operations can be discovered efficiently algorithmically.

  1. Broad practical applicability: The set of possible clustering operations is broad enough to permit diverse applicability in real-world settings.

A researcher typically clusters a causal graph in order to answer one or several questions about causal effects using the simpler clustered graph. If the clustering operation is not identification invariant, the clustered graph may not allow inference on all of these causal effects: an effect may be identifiable in the original graph but not in the clustered graph, as demonstrated in Figure 1b. The researcher would then have to return to the original graph, defeating the purpose of clustering. The first property guarantees that this can be ruled out.

In many cases, the need for clustering increases as the size of the graph increases. For instance, a graph with a hundred vertices may be too convoluted to be presented visually. However, a brute-force approach to find all “desirable” clusterings can be highly inefficient, particularly in the case of larger graphs. For this reason, violating the second desired property, i.e., not being able to find potential clusters efficiently, is not ideal from a practical viewpoint. Finally, it is straightforward to find special cases that satisfy the first two conditions. However, an overly restrictive definition can easily hinder the applicability of the results in real-world settings, thus violating the final desired property.

In recent work, Nykänen et al. [7] studied the identification invariance of clustering operations (Definition 9 in Appendix § 7), by presenting several graphical conditions under which (non)-identifiability of a causal effect in the clustered graph implies (non)-identifiability of the corresponding causal effect in the original graph. Each of these conditions requires the cluster to be coherent (Definition 10 in Appendix § 7), that is, for each parent and child of the cluster, there must be a directed path from the parent to the child whose intermediate vertices all belong to the cluster. Coherence is therefore a natural requirement for our target class of clusters, as one of our aims is identification invariance. However, coherence alone provides very little structure for a cluster, making it difficult to develop an efficient algorithm for detecting every coherent cluster in a graph without any additional assumptions.

In another closely related line of work, Tikka et al. [15] introduced a coherent class of clusters called transit clusters (see Appendix § 8 for the definition) and provided an algorithm (FINDTRCLUST) to find all transit clusters in a causal graph. However, as a drawback, the said algorithm does not run in polynomial time. In addition, the restrictive definition of transit clusters means that transit clusters may not always be present in practical settings (see, e.g., Table 1).

GraphBidirected edgesAlgorithmAll clustersInvariant clustersReduction
PATHFINDER<br>∣V∣=109\lvert V\rvert= 109<br>∣R∣=28\lvert R\rvert= 28noneFINDCONDUITS60 (42, 88)60 (42, 88)12 (11, 14)
PATHFINDER<br>∣V∣=109\lvert V\rvert= 109<br>∣R∣=28\lvert R\rvert= 28noneFINDTRCLUST2 (1, 2)2 (1, 2)2 (1, 2)
PATHFINDER<br>∣V∣=109\lvert V\rvert= 109<br>∣R∣=28\lvert R\rvert= 28fewFINDCONDUITS42 (34, 59)42 (34, 58)11 (10, 12)
PATHFINDER<br>∣V∣=109\lvert V\rvert= 109<br>∣R∣=28\lvert R\rvert= 28fewFINDTRCLUST1 (1, 2)1 (1, 2)1 (1, 2)
PATHFINDER<br>∣V∣=109\lvert V\rvert= 109<br>∣R∣=28\lvert R\rvert= 28moderateFINDCONDUITS35 (28, 44)34 (27, 43)10 (9, 11)
PATHFINDER<br>∣V∣=109\lvert V\rvert= 109<br>∣R∣=28\lvert R\rvert= 28moderateFINDTRCLUST1 (1, 2)1 (1, 2)1 (1, 2)
ARTH150<br>∣V∣=107\lvert V\rvert= 107<br>∣R∣=36\lvert R\rvert= 36noneFINDCONDUITS52 (44, 59)52 (44, 59)19 (18, 21)
ARTH150<br>∣V∣=107\lvert V\rvert= 107<br>∣R∣=36\lvert R\rvert= 36noneFINDTRCLUST4 (2, 4)4 (2, 4)3 (2, 3)
ARTH150<br>∣V∣=107\lvert V\rvert= 107<br>∣R∣=36\lvert R\rvert= 36fewFINDCONDUITS42 (36, 51)39 (31, 48)17 (15, 18)
ARTH150<br>∣V∣=107\lvert V\rvert= 107<br>∣R∣=36\lvert R\rvert= 36fewFINDTRCLUST3 (2, 4)3 (2, 4)2 (2, 3)
ARTH150<br>∣V∣=107\lvert V\rvert= 107<br>∣R∣=36\lvert R\rvert= 36moderateFINDCONDUITS37 (30, 43)31 (24, 39)15 (13, 17)
ARTH150<br>∣V∣=107\lvert V\rvert= 107<br>∣R∣=36\lvert R\rvert= 36moderateFINDTRCLUST2 (1, 4)2 (1, 4)2 (1, 3)
WIN95PTS<br>∣V∣=76\lvert V\rvert= 76<br>∣R∣=57\lvert R\rvert= 57noneFINDCONDUITS107 (99, 114)107 (99, 114)33 (30, 35)
WIN95PTS<br>∣V∣=76\lvert V\rvert= 76<br>∣R∣=57\lvert R\rvert= 57noneFINDTRCLUST2 (1, 2)2 (1, 2)4 (2, 4)
WIN95PTS<br>∣V∣=76\lvert V\rvert= 76<br>∣R∣=57\lvert R\rvert= 57fewFINDCONDUITS94 (87, 101)80 (69, 90)28 (26, 31)
WIN95PTS<br>∣V∣=76\lvert V\rvert= 76<br>∣R∣=57\lvert R\rvert= 57fewFINDTRCLUST2 (1, 2)1 (1, 2)2 (2, 4)
WIN95PTS<br>∣V∣=76\lvert V\rvert= 76<br>∣R∣=57\lvert R\rvert= 57moderateFINDCONDUITS88 (81, 94)61 (50, 73)25 (23, 28)
WIN95PTS<br>∣V∣=76\lvert V\rvert= 76<br>∣R∣=57\lvert R\rvert= 57moderateFINDTRCLUST1 (1, 2)1 (1, 2)2 (2, 4)
HEPAR2<br>∣V∣=70\lvert V\rvert= 70<br>∣R∣=26\lvert R\rvert= 26noneFINDCONDUITS43 (34, 49)43 (34, 49)16 (14, 17)
HEPAR2<br>∣V∣=70\lvert V\rvert= 70<br>∣R∣=26\lvert R\rvert= 26noneFINDTRCLUST1 (1, 2)1 (1, 2)4 (1, 5)
HEPAR2<br>∣V∣=70\lvert V\rvert= 70<br>∣R∣=26\lvert R\rvert= 26fewFINDCONDUITS39 (30, 45)32 (25, 41)13 (12, 15)
HEPAR2<br>∣V∣=70\lvert V\rvert= 70<br>∣R∣=26\lvert R\rvert= 26fewFINDTRCLUST1 (1, 1)1 (1, 1)1 (1, 4)
HEPAR2<br>∣V∣=70\lvert V\rvert= 70<br>∣R∣=26\lvert R\rvert= 26moderateFINDCONDUITS35 (27, 42)24 (18, 32)11 (10, 13)
HEPAR2<br>∣V∣=70\lvert V\rvert= 70<br>∣R∣=26\lvert R\rvert= 26moderateFINDTRCLUST1 (0, 1)1 (0, 1)1 (0, 1)
MAGIC-IRRI<br>∣V∣=64\lvert V\rvert= 64<br>∣R∣=56\lvert R\rvert= 56noneFINDCONDUITS99 (85, 109)99 (85, 109)29 (27, 31)
MAGIC-IRRI<br>∣V∣=64\lvert V\rvert= 64<br>∣R∣=56\lvert R\rvert= 56noneFINDTRCLUST1 (1, 1)1 (1, 1)1 (1, 1)
MAGIC-IRRI<br>∣V∣=64\lvert V\rvert= 64<br>∣R∣=56\lvert R\rvert= 56fewFINDCONDUITS84 (71, 95)70 (57, 88)25 (21, 27)
MAGIC-IRRI<br>∣V∣=64\lvert V\rvert= 64<br>∣R∣=56\lvert R\rvert= 56fewFINDTRCLUST1 (0, 1)1 (0, 1)1 (0, 1)
MAGIC-IRRI<br>∣V∣=64\lvert V\rvert= 64<br>∣R∣=56\lvert R\rvert= 56moderateFINDCONDUITS75 (64, 86)54 (43, 70)21 (18, 24)
MAGIC-IRRI<br>∣V∣=64\lvert V\rvert= 64<br>∣R∣=56\lvert R\rvert= 56moderateFINDTRCLUST1 (0, 1)1 (0, 1)1 (0, 1)

Table 1. Comparison of FINDCONDUITS and FINDTRCLUST in the 5 largest graphs with different numbers of bidirected edges (none, few or moderate relative to the graph size; see Appendix E for details). Each graph was studied in 1000 instances for each number of edges, and each graph name is followed by the number of observed vertices ∣V∣\lvert V\rvert and the number of vertices in the restriction set ∣R∣\lvert R\rvert. The table reports the median number of all clusters found, the median number of clusters among them that are universally identification invariant according to Nykanen et al. [7], and the median reduction in the number of observed vertices obtained by clustering the invariant clusters. Interquartile ranges (Q1, Q3) are shown in parentheses.

For all the aforementioned reasons, our quest is to find a class of clusters that would be able to address all three desired properties in a satisfactory manner. As a result, we define a coherent class of clusters called conduits. We then provide an algorithm that enumerates all conduits in polynomial time for a given causal graph.

Definition

When considering efficient algorithmic discoverability of clusters, it is beneficial if the clusters can be formed in a straightforward way. We construct the conduits using iterative parental and filial sibling sets (IPS and IFS, respectively); we later show that by this construction there always exist a polynomial number of conduits, and that conduits can be discovered efficiently. IPS and IFS are defined as follows.

Definition 4 (Iterative parental siblings). Let G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}) be a causal graph. The set of kk-th iterative parental siblings of Z∈V∪UZ \in\mathbf{V} \cup\mathbf{U} is IPS⁡Gk(Z)=Zk\operatorname{IPS}_{\mathcal{G}}^{k}(Z) = \mathbf{Z}_{k}, where the sets (Zi)i=1k(\mathbf{Z}_{i})_{i=1}^{k} are defined recursively by letting Z1={Z}\mathbf{Z}_{1} = \{Z\} and Zi=Zi−1∪Ch⁡G∗(Pa⁡G∗(Zi−1))\mathbf{Z}_{i} = \mathbf{Z}_{i-1} \cup\operatorname{Ch}_{\mathcal{G}}^{*}(\operatorname{Pa}_{\mathcal{G}}^{*}(\mathbf{Z}_{i-1})) for i>1i > 1.

In the first iteration of IPS, we select some Z∈V∪UZ \in\mathbf{V} \cup\mathbf{U}. In each subsequent iteration, we augment the existing candidate set by the children of the parents of the previous set. IFS are defined analogously but through the parents of the children of the existing sets.

Definition 5 (Iterative filial siblings). Let G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}) be a causal graph. The set of ℓ\ell-th iterative filial siblings of W∈V∪UW \in\mathbf{V} \cup\mathbf{U} is IFS⁡Gℓ(W)=Wℓ\operatorname{IFS}_{\mathcal{G}}^{\ell}(W) = \mathbf{W}_{\ell}, where the sets (Wj)j=1ℓ(\mathbf{W}_{j})_{j=1}^{\ell} are defined recursively by letting W1={W}\mathbf{W}_{1} = \{W\} and Wj=Wj−1∪(Pa⁡G∗(Ch⁡G∗(Wj−1)))\mathbf{W}_{j} = \mathbf{W}_{j-1} \cup(\operatorname{Pa}_{\mathcal{G}}^{*}(\operatorname{Ch}_{\mathcal{G}}^{*}(\mathbf{W}_{j-1}))) for j>1j > 1.

We define a conduit as the intersection of the descendants of the iterative parental siblings of some Z∈V∪UZ \in\mathbf{V} \cup\mathbf{U} and k∈Nk \in\mathbb{N} and the ancestors of the iterative filial siblings of some W∈V∪UW \in\mathbf{V} \cup\mathbf{U} and ℓ∈N\ell\in\mathbb{N} (provided that these sets are non-empty). Furthermore, we require a conduit to be coherent, so that the identification invariance results of Nykkänen et al. (2026) apply. Formally, conduits are defined as follows.

Definition 6 (Conduit). A non-empty set T⊆V\mathbf{T} \subseteq\mathbf{V} in a causal graph G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}) is a conduit if

(A) For each P∈Pa⁡G∗(T+)P \in\operatorname{Pa}_{\mathcal{G}}^{*}(\mathbf{T}^{+}) and C∈Ch⁡G∗(T)C \in\operatorname{Ch}_{\mathcal{G}}^{*}(\mathbf{T}) there is a directed path P→T1→⋯→Tm→CP \to T_{1} \to\cdots\to T_{m} \to C such that T1,…,Tm∈TT_{1}, \ldots, T_{m} \in\mathbf{T} and m≥1m \ge1.

(B) There exist Z,W∈V∪UZ, W \in\mathbf{V} \cup\mathbf{U} and k,ℓ∈Nk, \ell\in\mathbb{N} for which at least one of the following conditions is satisfied:

(B1) T=(De⁡G(Z)∩An⁡G(W))∩V\mathbf{T} = (\operatorname{De}_{\mathcal{G}}(Z) \cap\operatorname{An}_{\mathcal{G}}(W)) \cap\mathbf{V} for Z=IPS⁡Gk(Z)Z = \operatorname{IPS}_{\mathcal{G}}^{k}(Z) and W=IFS⁡Gℓ(W)W = \operatorname{IFS}_{\mathcal{G}}^{\ell}(W).

(B2) T=An⁡G(W)∩V\mathbf{T} = \operatorname{An}_{\mathcal{G}}(W) \cap\mathbf{V} for W=IFS⁡Gℓ(W)W = \operatorname{IFS}_{\mathcal{G}}^{\ell}(W).

(B3) T=De⁡G(Z)∩V\mathbf{T} = \operatorname{De}_{\mathcal{G}}(Z) \cap\mathbf{V} for Z=IPS⁡Gk(Z)Z = \operatorname{IPS}_{\mathcal{G}}^{k}(Z).

The set of conduits in G\mathcal{G} is denoted by ΓG\Gamma_{\mathcal{G}}.

Condition (A) corresponds to the definition of coherence (Definition 10 in Appendix § 7). Coherence ensures that the clustered graph is a DAG and that clustering does not form new directed connections between the vertices outside the cluster ((Nykkänen et al., 2026, Lemma 15)).

Conditions (B1)–(B3) specify how the cluster is determined by the descendants and ancestors of IPS and IFS, respectively. These conditions are crucial when developing an efficient algorithm to discover all conduits in a graph. First, the construction of a candidate conduit is streamlined: the algorithm does not require any further iterations to form the candidate cluster once the descendants and ancestors of IPS and IFS are known. Second, there exist a polynomial number of IPS and IFS sets, from which we can further construct all conduits in polynomial time, as proven in Appendix D. These statements are further revisited in § 3.2 where we provide a polynomial-time algorithm for detecting conduits.

The nature of the conditions is illustrated in Figure 1c and Figure 1d:

  • In fig:1c there is a conduit T3={T1,T2,T3,T4,T5,T6}\mathrm{T}_3 = \{\mathrm{T}_1,\mathrm{T}_2,\mathrm{T}_3,\mathrm{T}_4,\mathrm{T}_5,\mathrm{T}_6\}, whose iterative sibling sets appearing are W=IFSG2(T5)={T4,T5,T6}\mathrm{W} = \mathrm{IFS}_{\mathcal{G}}^{2}(\mathrm{T}_5) = \{\mathrm{T}_4,\mathrm{T}_5,\mathrm{T}_6\} and either Z=IPSG1(T1)={T1}\mathrm{Z} = \mathrm{IPS}_{\mathcal{G}}^{1}(\mathrm{T}_1) = \{\mathrm{T}_1\}, Z=IPSG2(T1)={T1,T2}\mathrm{Z} = \mathrm{IPS}_{\mathcal{G}}^{2}(\mathrm{T}_1) = \{\mathrm{T}_1,\mathrm{T}_2\} or Z=IPSG3(T1)={T1,T2,T3}\mathrm{Z} = \mathrm{IPS}_{\mathcal{G}}^{3}(\mathrm{T}_1) = \{\mathrm{T}_1,\mathrm{T}_2,\mathrm{T}_3\}, which shows that the sibling sets that generate a conduit are not always unique.

  • In fig:1d the cluster T4={T1,T2}\mathrm{T}_4 = \{\mathrm{T}_1,\mathrm{T}_2\} satisfies condition (B), but not condition (A). Consequently, clustering T4\mathrm{T}_4 creates a directed path from V1\mathrm{V}_1 to V4\mathrm{V}_4, even though there is no directed path between V1\mathrm{V}_1 and V4\mathrm{V}_4 in the original graph.

In practical applications, we may be interested in finding conduits for a subset R⊆V\mathbf{R} \subseteq\mathbf{V}. This can be beneficial, for instance, if we want to prohibit the response and treatment variables from being clustered, or if there exists a particular target group of vertices we want to cluster. Restricted conduits are defined as follows.

Definition 7 (Restricted conduit). Given a set R⊆V\mathbf{R} \subseteq\mathbf{V} in a causal graph G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}), a vertex set T⊆V\mathbf{T} \subseteq\mathbf{V} is a restricted conduit with respect to R\mathbf{R}, if T⊆R\mathbf{T} \subseteq\mathbf{R} and T\mathbf{T} is a conduit in G\mathcal{G}. The set of conduits restricted to R\mathbf{R} is denoted by ΓG∣R\Gamma_{\mathcal{G}|\mathbf{R}}.

Algorithm for Detecting Conduits

We proceed to develop an algorithm that detects all (restricted) conduits in a given causal graph. Our approach starts with constructing the set of iterative parental and filial siblings for all vertices in the graph. The definition of a conduit (Definition 6) allows us to directly construct the candidate conduit based on IPS and IFS. This approach is reminiscent of FINDTRCLUST ([15]), where the aim is to construct transit clusters through all emitters and receivers—two vertex sets that uniquely characterize transit clusters. The algorithm for detecting all conduits, which we call FINDCONDUITS, is presented in Algorithm 1.

The outline of Algorithm 1 is the following. On line 2, we initialize the set of valid conduits A\mathcal{A}. Line 3 computes the maximum number of iterations needed to construct all IPS and IFS sets (see Lemma 14 in Appendix C). The IPS and IFS sets are constructed on lines 4 and 5, respectively. Empty sets are explicitly included in both sets. We loop through all possible pairs of the IPS and IFS sets on lines 6 and 7, and then construct the candidate set AC\mathcal{A}_{C} according to conditions (B1)–(B3) on lines 9–11. Line 12 rejects candidates that do not entirely belong to the restriction set R\mathbf{R} or that do not meet the minimum size requirement of λ\lambda. Condition (A) is then validated on line 13. Upon successful validation, we add AC\mathcal{A}_{C} to the list of valid conduits on line 14.

The following theorem states that FINDCONDUITS is sound and complete, and operates in polynomial time. The number of candidate sets processed by FINDCONDUITS is assessed in Appendix C.

Theorem 8. FINDCONDUITS is sound and complete for any valid parameters (G,R,λ)(\mathcal{G}, \mathbf{R}, \lambda) and outputs all (restricted) conduits in G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}) in O(n5~m)O(n^{\tilde{5}}m) time with respect to R⊆V\mathbf{R} \subseteq\mathbf{V} and λ∈N\lambda\in\mathbb{N}, where n=∣V∪U∣n = |\mathbf{V} \cup\mathbf{U}| and m=∣E∣m = |\mathbf{E}|.

Algorithm 1 An algorithm for finding every (restricted) conduit in a given causal graph. The inputs are a causal graph G=(V∪U,E)\mathcal{G} = (\mathrm{V} \cup\mathrm{U}, \mathrm{E}), a non-empty restriction set R⊆V\mathrm{R} \subseteq\mathrm{V} whose members are the only vertices that are allowed to belong to any conduit, and the minimum size of the conduits λ∈N\lambda\in\mathbb{N}. Returns the set of all restricted conduits of G\mathcal{G} that are at least of size λ\lambda.

1: function FINDCONDUITS(𝒢, R, λ)
2:     𝒜 ← ∅
3:     q ← ⌈|V ∪ U|/2⌉
4:     𝒵 ← {∅} ∪ ⋃_{Z∈V∪U} ⋃_{k=1}^{q} IPS^k_𝒢(Z)
5:     𝒲 ← {∅} ∪ ⋃_{W∈V∪U} ⋃_{ℓ=1}^{q} IFS^ℓ_𝒢(W)
6:     for all Z ∈ 𝒵 do
7:         for all W ∈ 𝒲 do
8:             if (Z = ∅) ∧ (W = ∅) then continue
9:             if Z = ∅ then A_C ← An_𝒢(W) ∩ V
10:            if W = ∅ then A_C ← De_𝒢(Z) ∩ V
11:            if (Z ≠ ∅) ∧ (W ≠ ∅) then A_C ← (De_𝒢(Z) ∩ An_𝒢(W)) ∩ V
12:            if (|A_C| ≥ λ) ∧ (A_C ⊆ R) then
13:                if A_C satisfies condition (A) of Definition 6 in 𝒢 then
14:                    𝒜 ← 𝒜 ∪ {A_C}
15:    return 𝒜

The proof of Theorem 8 is provided in Appendix D. The practical performance is illustrated in the next section.

Demonstrations

In this section, we demonstrate the performance and the practical use of the results of this paper. We first study the efficiency of FINDCONDUITS in a simulation study by generating random causal graphs. We then focus on the practical side by selecting DAGs from the Bayesian Network Repository ([2, 11]), and conduct a new simulation study where we attempt to find universally identification invariant clusters using both FINDCONDUITS and FINDTRCLUST. We compare the number of clusters found, the number of vertices reduced via clustering, and the running time. Finally, we focus more explicitly on one of the graphs of the repository which models insurance claim costs.

While the Bayesian networks in question are not necessarily causal, we treat them as benchmark causal DAGs for illustrative purposes in our examples. We omit singleton sets in clustering as clustering them does not reduce the size of the graph.

Practical Performance of FINDCONDUITS

We begin by generating random connected DAGs from 25 to 150 vertices. We initially generate graphs with two different probabilities for directed edges: 2/∣V∣2/|\mathrm{V}| for sparse graphs and 0.4 for dense graphs. If the graph is not connected, we generate additional random edges between each unconnected component, such that the acyclicity remains, until the graph is connected. We then run FINDCONDUITS for each graph and record its running time. This process is repeated 1 000 times for each graph size and density. The results are presented in Figure 2.

Figure 2. Median running times (left) and the median number of conduits (right) by FINDCONDUITS for graphs with 25–150 vertices for sparse and dense graphs. Interquartile ranges are shown in the bands.

The algorithm runs consistently faster for sparse graphs than for dense graphs, which is in line with the complexity being dependent on the number of edges. For the densest graphs with 150 vertices, the median running time was about 154 seconds while for the sparse graphs with 150 vertices it was about 7 seconds. The maximum running time was 231 seconds.

Empirical Evaluation of the Clustering Algorithms

In this section, we study how FINDCONDUITS and FINDTRCLUST perform under various causal graphs, originating from real-world applications. We select all 17 DAGs from Bayesian Network Repository whose sizes range from 10 vertices to 110 vertices.

We perform a simulation study in which each instance proceeds as follows. Without unobserved confounders universal identification invariance is immediate, so in addition to the base graphs, we also consider graphs where we add bidirected edges at random. We then select all leaf vertices LL, that is, vertices that do not have any children, and randomly select between two and four vertices from the ancestors of the leaf set, i.e., A⊂An∗(L)A \subset An^{*}(L). We are interested in all causal effects where interventions are performed on a subset of AA and a subset of LL forms the responses, and therefore exclude L∪AL \cup A from clustering. In other words, the restriction set RR consists of all observed vertices except for LL and AA. Next, we find all restricted conduits and transit clusters and check which of them are universally identification invariant according to Theorems 19, 21 and 23 by Nykanen et al. [7]. Finally, we select pairwise disjoint invariant clusters, from the largest to the smallest, discarding any cluster that intersects one already selected, cluster them, and record how much the graph is reduced. The generation of each simulation instance is explained in more detail in Appendix E.

While this procedure does not necessarily yield maximal size reduction (for instance, if the largest cluster overlaps with other large clusters), it is an adequate method to demonstrate the differences in performance between the algorithms FINDCONDUITS and FINDTRCLUST. Furthermore, finding an optimal clustering sequence (with respect to size reduction) can be computationally cumbersome, because in the worst case, it might be necessary to iterate through all possible permutations of the cluster list.

Table 1 summarizes the results for the five largest graphs; the results for all graphs are given in Appendix E. Without latent confounders, every cluster found is universally identification invariant, as coherent clusters are then plain. In this setting, the median reduction in the graph size by clustering the identification invariant conduits ranged from 12 to 33 vertices. The largest median reduction relative to the number of observed vertices in the restriction set was in the graph HEPAR2, where the median reduction was 62%. Transit clusters, in contrast, reduced the graphs by at most four vertices, since only one to four transit clusters were found in each of these graphs.

Latent confounders affect conduits in two ways. First, in general, fewer conduits are found, because condition (A) also requires directed paths from the unobserved parents of the cluster to its children. Second, not every conduit found is universally identification invariant, and consequently, the reduction decreases as the number of bidirected edges grows. Nonetheless, losing some conduits still leaves viable clusterings available: for the largest number of bidirected edges, the median reduction was 36–44% of ∣R∣|\mathbf{R}|, i.e., of all observed variables apart from the leaf vertices and the random ancestors.

In every graph and for any number of bidirected edges, the median reduction was larger with FINDCONDUITS than with FINDTRCLUST, and the interquartile ranges of the two algorithms did not overlap; this holds for all 17 graphs (Appendix E). In five graphs (INSURANCE, MAGIC-NIAB, MEHRA, SANGIOVESE and WATER), no invariant transit cluster was found in at least three quarters of the instances. Running times are also reported in Appendix E; both algorithms finished within seconds in most graphs, with FINDTRCLUST typically faster on the larger graphs due to the small number of transit clusters. The maximum running time was 147 seconds with FINDCONDUITS.

Clustering via Conduits in an Insurance Claim Costs Model

In this application, we focus on the INSURANCE graph ([3]) which is one of the graphs examined in the simulation study of § 4.2. This graph has been used to estimate the expected claim costs for a car insurance policyholder and we consider its subgraph that consists of 19 vertices. The graph is displayed in Figure 3a and the documentation of the variables is provided in the R package bnlearn ([11]).

Original and clustered graphs of the insurance claim model

Figure 3. A subgraph of the insurance claim model by Binder et al. [3], augmented by two bidirected edges, and a graph induced by clustering a conduit.

First, we run FINDCONDUITS for the entire graph without restricting to any vertex set to find all non-singleton clusters. This results in 90 clusters, with sizes ranging from 2 to 18 vertices. The median cluster size in the set is 4 vertices.

Suppose that we are interested in causal effects of risk aversion and/or socioeconomic status on the costs of cars involved in insurance claims (This Car Cost and/or Other Car Cost). Our task is now to find conduits that are identification invariant with respect to the entire family of causal effects we are interested in. We therefore run FINDCONDUITS with the restriction set R\mathbf{R} consisting of all other observed vertices. One of the conduits found, T\mathbf{T}, consists of the 13 vertices that mediate these effects, that is, all vertices except Age, Mileage and the four variables of interest. As no bidirected edge has exactly one endpoint in T\mathbf{T}, cluster T\mathbf{T} is plain, and clustering it is universally identification invariant ([7]). The clustered graph, shown in Figure 3b, has only seven vertices.

Consequently, the identifiability of every effect in the family of causal effects (i.e., where risk aversion and socioeconomic status serve as interventional variables and the car costs as response variables) can be decided in the clustered graph instead of the original graph of 19 vertices. In the clustered graph, the effects of risk aversion on the claim costs are identifiable. In contrast, the effects of socioeconomic status alone on the claim costs are not identifiable because of the bidirected edges between socioeconomic status, risk aversion and the cost of the policyholder’s car, and hence they are not identifiable in the original graph either. The joint effect of risk aversion and socioeconomic status is again identifiable.

Conclusion

We defined a class of clusters called conduits, with the following essential properties in mind: identification invariance, efficient algorithmic detectability and broad applicability. We presented a sound and complete algorithm (FINDCONDUITS) that detects all conduits in a given graph in polynomial time. The algorithmic cluster detection offers possibilities to integrate clustering into existing causal inference software.

We illustrated the practical benefits of conduits in a simulation study on well-known causal graphs from real-world applications. To study identification invariance, random latent confounders were added to the graphs. Efficiency was measured by the running time of the algorithm, and applicability was measured by the number of identification invariant clusters found and the reduction in graph size obtained by clustering them. In most cases, clustering led to a considerable reduction in the size of the graph within moderate computation times on the evaluated graphs.

Acknowledgments and Disclosure of Funding

Otto Tabell was supported by the Finnish Doctoral Program Network in Artificial Intelligence (AI-DOC, Decision VN/3137/2024-OKM-6). Jani Nykanen and Juha Karvanen were supported by the Research Council of Finland (grant no. 368935 to JK). The authors acknowledge CSC – IT Center for Science, Finland, for computational resources. Claude Fable 5.2 (Anthropic) was used to generate the proofs for the number of candidate sets in Algorithm 1. Claude Opus 5.5 (Anthropic) was used to perform extensive checks regarding the validity of our arguments and results, and to check the spelling. The model was also used to debug the R code and to assist in the implementation of the simulation study and its analysis. The authors reviewed and verified all output and take full responsibility for the content.

Universal Identification Invariance

In arbitrary clustering there lies a danger: a causal effect may be nonidentifiable in the clustered graph even though it is identifiable in the original graph, which may lead to mistaken conclusions regarding the identifiability should we only use the clustered graph as the basis. Clustering operations that retain the same identifiability properties of a family of causal effects are called identification invariant ([13, 7]). A formal definition is provided below.

Definition 9 (Identification invariance). Suppose a clustering operation ΩT\Omega_{\mathbf{T}} that maps a causal graph G\mathcal{G} to a causal graph G′=ΩT(G)\mathcal{G}'=\Omega_{\mathbf{T}}(\mathcal{G}) obtained by clustering T⊂V\mathbf{T}\subset\mathbf{V} in G\mathcal{G}. Then:

  • ΩT\Omega_{\mathbf{T}} is identification invariant for a family of causal effects C=(p(yi∣do⁡(xi)))i=1m\mathcal{C}=(p(y_i\mid\operatorname{do}(x_i)))_{i=1}^{m} if each causal effect is either identifiable in G\mathcal{G} and G′\mathcal{G}' or nonidentifiable in G\mathcal{G} and G′\mathcal{G}'.

  • ΩT\Omega_{\mathbf{T}} is universally identification invariant if the operation is identification invariant for the maximal family of causal effects not involving the variables of T\mathbf{T}, that is, the set of causal effects p(y∣do⁡(x))p(\mathbf{y}\mid\operatorname{do}(\mathbf{x})) such that X∩Y=∅\mathbf{X}\cap\mathbf{Y}=\varnothing and X,Y⊂V∖T\mathbf{X},\mathbf{Y}\subset\mathbf{V}\setminus\mathbf{T}.

It was proven by Anand et al. [1] that in a clustering operation that does not create directed cycles, each causal effect that is identifiable in the clustered graph is also identifiable in the original graph, but without stronger assumptions clustering operations can render identifiable causal effects nonidentifiable, an example of which is provided in Figure 4.

Figure 4. A graph where T={T1,T2}\mathbf{T}=\{T_1,T_2\} forms a conduit, and the causal effect p(v2∣do⁡(v1))p(v_2 \mid\operatorname{do}(v_1)) is identifiable in the original graph but not after clustering T\mathbf{T}.

Nykanen et al. [7] established several identification invariance results for coherent clustering operations based on c-components of the graph ([14, 12]). Transit clusters and conduits are examples of coherent clusters. Coherence is defined as follows:

Definition 10 (Coherence). A set of vertices T⊆V\mathbf{T} \subseteq\mathbf{V} in a causal graph G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}) is coherent provided that for all P∈Pa⁡G∗(T+)P \in\operatorname{Pa}^{*}_{\mathcal{G}}(\mathbf{T}^{+}) and C∈Ch⁡G∗(T)C \in\operatorname{Ch}^{*}_{\mathcal{G}}(\mathbf{T}) there exists a directed path P→T1→⋯→Tm→CP \to T_{1} \to\cdots\to T_{m} \to C such that T1,…,Tm∈TT_{1}, \ldots, T_{m} \in\mathbf{T} and m≥1m \ge1. A clustering operation is coherent if the clustered set satisfies the coherence property.

Nykanen et al. [7] introduced three different graphical conditions, which we list below, to assess universal identification invariance. The definitions and theorems in the following refer to those in Nykanen et al. [7].

  • Plainness: Pa⁡G∗(T+)⊂V\operatorname{Pa}^{*}_{\mathcal{G}}(\mathbf{T}^{+}) \subset\mathbf{V}, that is, T\mathbf{T} does not have any unobserved parents that have one child in the cluster and one child outside the cluster. (Definition 18, Theorem 19)

  • c-coherence: There exists a vertex T∗∈TT^{*} \in\mathbf{T} such that Pa⁡G∗(T∗)∖T+=Pa⁡G∗(T+)\operatorname{Pa}^{*}_{\mathcal{G}}(T^{*}) \setminus\mathbf{T}^{+} = \operatorname{Pa}^{*}_{\mathcal{G}}(\mathbf{T}^{+}), and for each C∈Ch⁡G∗(T)C \in\operatorname{Ch}^{*}_{\mathcal{G}}(\mathbf{T}), either T∗∈Pa⁡G∗(C)T^{*} \in\operatorname{Pa}^{*}_{\mathcal{G}}(C), or there exists a directed path T∗→T1→⋯→Tm→CT^{*} \to T_{1} \to\cdots\to T_{m} \to C in G\mathcal{G} such that T1,…,Tm∈TT_{1}, \ldots, T_{m} \in\mathbf{T} and the graph G[P+]\mathcal{G}[\mathbf{P}^{+}] induced by the vertex set P={T∗,T1,…,Tm}\mathbf{P} = \{T^{*}, T_{1}, \ldots, T_{m}\} is a c-component. (Definition 20, Theorem 21)

  • c-isolation: There exists a vertex T∗∈TT^{*} \in\mathbf{T} such that Pa⁡G∗(T∗)∖T+=Pa⁡G∗(T+)\operatorname{Pa}^{*}_{\mathcal{G}}(T^{*}) \setminus\mathbf{T}^{+} = \operatorname{Pa}^{*}_{\mathcal{G}}(\mathbf{T}^{+}), and for each c-component D=(V∗∪U∗,E∗)\mathcal{D} = (\mathbf{V}^{*} \cup\mathbf{U}^{*}, \mathbf{E}^{*}) in G\mathcal{G} it either holds V∗∩T=∅\mathbf{V}^{*} \cap\mathbf{T} = \varnothing or V∗∩De⁡G∗(T)=∅\mathbf{V}^{*} \cap\operatorname{De}^{*}_{\mathcal{G}}(\mathbf{T}) = \varnothing, that is, there is no bidirected path from T\mathbf{T} to De⁡G∗(T)\operatorname{De}^{*}_{\mathcal{G}}(\mathbf{T}). (Definition 22, Theorem 23)

Recall that a bidirected path is a path consisting solely of bidirected edges, that is, a path of the type V1←U1→V2←⋯←Uk→VkV_{1} \leftarrow U_{1} \to V_{2} \leftarrow\cdots\leftarrow U_{k} \to V_{k}, where V1,…,Vk∈VV_{1}, \ldots, V_{k} \in\mathbf{V} and U1,…,Uk∈UU_{1}, \ldots, U_{k} \in\mathbf{U}.

Transit Clusters

A transit cluster ([15]) is a special type of coherent cluster (Definition 10) that is uniquely determined by its receivers and emitters, which we define below.

Definition 11 (Receiver). For a set of vertices T⊂V∪U\mathbf{T} \subset\mathbf{V} \cup\mathbf{U} in a causal graph G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}), the set of receivers is the set

Re⁡G(T)={R∈T∣Pa⁡G∗(R)∖T≠∅},\operatorname{Re}_{\mathcal{G}}(\mathbf{T}) = \{R \in\mathbf{T} \mid\operatorname{Pa}^{*}_{\mathcal{G}}(R) \setminus\mathbf{T} \ne\varnothing\},

that is, the set of all vertices of T\mathbf{T} that have parents outside the vertex set T\mathbf{T}.

Definition 12 (Emitter). For a set of vertices T⊂V∪U\mathbf{T} \subset\mathbf{V} \cup\mathbf{U} in a causal graph G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}), the set of emitters is the set

Em⁡G(T)={E∈T∣Ch⁡G∗(E)∖T≠∅},\operatorname{Em}_{\mathcal{G}}(\mathbf{T}) = \{E \in\mathbf{T} \mid\operatorname{Ch}^{*}_{\mathcal{G}}(E) \setminus\mathbf{T} \ne\varnothing\},

that is, the set of all vertices of T\mathbf{T} that have children outside the vertex set T\mathbf{T}.

In the following, we use the notation G[A]\mathcal{G}[A] for the induced subgraph (A,F)(A, \mathbf{F}) of G\mathcal{G}, where A⊂V∪UA \subset\mathbf{V} \cup\mathbf{U} and F\mathbf{F} contains those edges of E\mathbf{E} that have both endpoints in AA. A transit cluster is defined as follows:

Definition 13 (Transit cluster). A set of vertices T⊂V∪U\mathbf{T} \subset\mathbf{V} \cup\mathbf{U} in a causal graph G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, \mathbf{E}) is a transit cluster if the following conditions hold:

(T1) For all pairs of receivers R1,R2∈Re⁡G(T)R_{1}, R_{2} \in\operatorname{Re}_{\mathcal{G}}(\mathbf{T}) it holds Pa⁡G(R1)∖T=Pa⁡G(R2)∖T\operatorname{Pa}_{\mathcal{G}}(R_{1}) \setminus\mathbf{T} = \operatorname{Pa}_{\mathcal{G}}(R_{2}) \setminus\mathbf{T} (i.e., all receivers have the same parents).

(T2) For all pairs of emitters E1,E2∈EmG(T)\mathrm{E}_1,\mathrm{E}_2 \in\mathrm{Em}_{G}(\mathbf{T}) it holds ChG(E1)∖T=ChG(E2)∖T\mathrm{Ch}_{G}(\mathrm{E}_1) \setminus\mathbf{T} = \mathrm{Ch}_{G}(\mathrm{E}_2) \setminus\mathbf{T} (i.e., all emitters have the same children).

(T3) For all vertices Ti∈T\mathrm{T}_i \in\mathbf{T} there exists a receiver R∈ReG(T)\mathrm{R} \in\mathrm{Re}_{G}(\mathbf{T}) or an emitter E∈EmG(T)\mathrm{E} \in\mathrm{Em}_{G}(\mathbf{T}) such that Ti\mathrm{T}_i and R\mathrm{R} or Ti\mathrm{T}_i and E\mathrm{E} are connected via an undirected path in the subgraph G[T=]G[\mathbf{T}^{=}], which is obtained from G[T]G[\mathbf{T}] by removing all incoming edges to ReG(T)\mathrm{Re}_{G}(\mathbf{T}) and all outgoing edges from EmG(T)\mathrm{Em}_{G}(\mathbf{T}).

(T4) If EmG(T)≠∅\mathrm{Em}_{G}(\mathbf{T}) \ne\varnothing, then for all R∈ReG(T)\mathrm{R} \in\mathrm{Re}_{G}(\mathbf{T}) there exists an emitter E∈EmG(T)\mathrm{E} \in\mathrm{Em}_{G}(\mathbf{T}) such that E∈DeG(R)\mathrm{E} \in\mathrm{De}_{G}(\mathrm{R}).

(T5) If ReG(T)≠∅\mathrm{Re}_{G}(\mathbf{T}) \ne\varnothing, then for all E∈EmG(T)\mathrm{E} \in\mathrm{Em}_{G}(\mathbf{T}) there exists a receiver R∈ReG(T)\mathrm{R} \in\mathrm{Re}_{G}(\mathbf{T}) such that R∈AnG(E)\mathrm{R} \in\mathrm{An}_{G}(\mathrm{E}).

If T\mathbf{T} is connected in G[T]G[\mathbf{T}], then T\mathbf{T} is called a transit component.

In Definition 3 we only permit clustering of observed vertices. However, to keep the definition of a transit cluster consistent with the original definition in Tikka et al. [15], transit clusters are allowed to include unobserved vertices. When considering identification invariance, one requires an additional assumption that EmG(T)∩U=∅\mathrm{Em}_{G}(\mathbf{T}) \cap\mathbf{U} = \varnothing.

While transit clusters and conduits share similar properties, transit clusters are not necessarily conduits, and conversely not every conduit is a transit cluster, as demonstrated by Figure 5:

Examples of transit clusters and conduits

Figure 5. (a) T1={T2,T3}\mathbf{T}_1=\{\mathbf{T}_2,\mathbf{T}_3\} is a transit cluster, but not a conduit, because it does not satisfy (B). (b) T2={T1,T2,T3,T4}\mathbf{T}_2=\{\mathbf{T}_1,\mathbf{T}_2,\mathbf{T}_3,\mathbf{T}_4\} is both a transit cluster and a conduit. Examples illustrating similarities and differences between conduits (Definition 6) and transit clusters.

  • The transit cluster T1\mathbf{T}_1 in Figure 5a is not a conduit due to the violation of condition (B): There does not exist an IPS-IFS pair that would allow the formation of T={T2,T3}\mathbf{T}=\{\mathbf{T}_2,\mathbf{T}_3\} because any IPS or IFS set that contains both T2\mathbf{T}_2 and T3\mathbf{T}_3 must also contain V3\mathbf{V}_3.

  • The cluster T2\mathbf{T}_2 in Figure 5b is both a transit cluster and a conduit, showing that these two classes of clusters do overlap. However, if either the edge V1→T3\mathbf{V}_1 \to\mathbf{T}_3 or T4→V3\mathbf{T}_4 \to\mathbf{V}_3 (or both) is removed, then T2\mathbf{T}_2 is a conduit, but not a transit cluster.

In essence, transit clusters impose stronger conditions on edges connected to the cluster, but allow less restricted internal structure, whereas conduits require fewer edges between the vertices outside the cluster and the cluster itself, but at the cost of disallowing vertices not in the intersection specified by (B1).

Number of Candidate Sets in Algorithm 1

Lemma 14 (Length of sibling chains). Let G=(V∪U,E)\mathcal{G}=(\mathcal{V}\cup\mathcal{U},\mathbf{E}) be a causal graph with n=∣V∪U∣n=|\mathcal{V}\cup\mathcal{U}| vertices, let Z∈V∪UZ\in\mathcal{V}\cup\mathcal{U}, and let Zk=IPS⁡Gk(Z)Z_k=\operatorname{IPS}_{\mathcal{G}}^k(Z) for k≥1k\ge1. Then

(i) Zk⊆Zk+1Z_k\subseteq Z_{k+1} for all k≥1k\ge1, and if Zk+1=ZkZ_{k+1}=Z_k for some kk, then Zk′=ZkZ_{k'}=Z_k for all k′≥kk'\ge k;

(ii) the sequence (Zk)k≥1(Z_k)_{k\ge1} contains at most ⌈n/2⌉\lceil n/2\rceil distinct sets, and Zk=Z⌈n/2⌉Z_k=Z_{\lceil n/2\rceil} for all k≥⌈n/2⌉k\ge\lceil n/2\rceil;

(iii) if ZZ has no parents, then Zk={Z}Z_k=\{Z\} for all k≥1k\ge1.

The same statements hold for the iterative filial siblings Wℓ=IFS⁡Gℓ(W)\mathbf{W}_\ell=\operatorname{IFS}_{\mathcal{G}}^\ell(W) of a vertex W∈V∪UW\in\mathcal{V}\cup\mathcal{U}, where in (iii) the vertex WW is assumed to have no children.

Proof. Write Pk=Pa⁡G∗(Zk)P_k=\operatorname{Pa}_{\mathcal{G}}^*(Z_k), so that Zk+1=Zk∪Ch⁡G∗(Pk)Z_{k+1}=Z_k\cup\operatorname{Ch}_{\mathcal{G}}^*(P_k) by Definition 4. The inclusion in (i) is immediate, and the second claim of (i) holds because Zk+1Z_{k+1} is a function of ZkZ_k alone. Claim (iii) follows from P1=∅P_1=\varnothing. For (ii) we use three observations, valid for all k≥1k\ge1:

(a) Zk+1∩Pk=∅Z_{k+1}\cap P_k=\varnothing. Indeed, Zk∩Pk=∅Z_k\cap P_k=\varnothing and Ch⁡G∗(Pk)∩Pk=∅\operatorname{Ch}_{\mathcal{G}}^*(P_k)\cap P_k=\varnothing by the definition of Ch⁡G∗(⋅)\operatorname{Ch}_{\mathcal{G}}^*(\cdot).

(b) Pk⊆Pk+1P_k\subseteq P_{k+1}. Each P∈PkP\in P_k is a parent of some vertex of Zk⊆Zk+1Z_k\subseteq Z_{k+1}, and P∉Zk+1P\notin Z_{k+1} by (a).

(c) If Pk+1=PkP_{k+1}=P_k, then Zk+2=Zk+1Z_{k+2}=Z_{k+1}. Indeed, Zk+2=Zk+1∪Ch⁡G∗(Pk)=Zk+1Z_{k+2}=Z_{k+1}\cup\operatorname{Ch}_{\mathcal{G}}^*(P_k)=Z_{k+1}, because Ch⁡G∗(Pk)⊆Zk+1\operatorname{Ch}_{\mathcal{G}}^*(P_k)\subseteq Z_{k+1}.

Let tt be the number of distinct sets in the sequence. By (i), Z1⊊Z2⊊⋯⊊ZtZ_1\subsetneq Z_2\subsetneq\cdots\subsetneq Z_t and Zk=ZtZ_k=Z_t for all k≥tk\ge t; in particular ∣Zt∣≥t|Z_t|\ge t. If t=1t=1 there is nothing to prove, so let t≥2t\ge2. Then Z2≠Z1Z_2\ne Z_1 implies P1≠∅P_1\ne\varnothing, and for 1≤k≤t−21\le k\le t-2 the relation Zk+2≠Zk+1Z_{k+2}\ne Z_{k+1} together with (b) and (c) implies Pk⊊Pk+1P_k\subsetneq P_{k+1}. Hence ∣Pt−1∣≥t−1|P_{t-1}|\ge t-1. Since ZtZ_t and Pt−1P_{t-1} are disjoint by (a), we obtain t+(t−1)≤nt+(t-1)\le n, that is, t≤⌊(n+1)/2⌋=⌈n/2⌉t\le\lfloor(n+1)/2\rfloor=\lceil n/2\rceil.

The argument uses no property of G\mathcal{G} other than it being a directed graph. Applying it to the graph obtained from G\mathcal{G} by reversing all edges, which exchanges the roles of parents and children and therefore those of Definition 4 and Definition 5, gives the statements for (Wℓ)ℓ≥1(\mathbf{W}_\ell)_{\ell\ge1}.

Corollary 15 (Number of candidate pairs). Let G=(V∪U,E)\mathcal{G}=(\mathcal{V}\cup\mathcal{U},\mathbf{E}) be a causal graph with n=∣V∪U∣n=|\mathcal{V}\cup\mathcal{U}| vertices, and let Z\mathcal{Z} and W\mathcal{W} be the sets constructed on lines 4 and 5 of Algorithm 1. Then

∣Z∖{∅}∣≤1+(n−1)⌈n2⌉≤n2+12,∣W∖{∅}∣≤1+(n−1)⌈n2⌉≤n2+12.(1)|\mathcal{Z}\setminus\{\varnothing\}|\le1+(n-1)\left\lceil\frac{n}{2}\right\rceil\le\frac{n^2+1}{2},\qquad|\mathcal{W}\setminus\{\varnothing\}|\le1+(n-1)\left\lceil\frac{n}{2}\right\rceil\le\frac{n^2+1}{2}. \tag*{(1)}

Consequently, line 11 of Algorithm 1 is executed for at most

(1+(n−1)⌈n2⌉)2≤(n2+1)24(2)\left(1+(n-1)\left\lceil\frac{n}{2}\right\rceil\right)^2\le\frac{(n^2+1)^2}{4} \tag*{(2)}

pairs (Z,W)∈Z×W(Z,W)\in\mathcal{Z}\times\mathcal{W}, and in particular at most this many non-empty candidate sets AC\mathbf{A}_C are constructed on line 11.

Proof. As GG is a DAG, it has at least one vertex without parents, which contributes only its singleton to Z\mathcal{Z} by Lemma 14(iii). Each of the remaining n−1n-1 vertices contributes at most ⌈n/2⌉\lceil n/2\rceil sets by Lemma 14(ii). This gives the first inequality of (1). For the second, note that 1+(n−1)⌈n/2⌉1+(n-1)\lceil n/2\rceil equals (n2+1)/2(n^2+1)/2 when nn is odd and (n2−n+2)/2(n^2-n+2)/2 when nn is even. The bound for W\mathcal{W} is obtained in the same way from a vertex without children. Finally, line 11 is reached only if Z≠∅\mathcal{Z}\ne\varnothing and W≠∅\mathcal{W}\ne\varnothing, so (2) follows from (1).

Proposition 16 (Worst-case number of candidate sets). For every even n≥6n\ge6 there exists a causal graph G=(V∪U,E)G=(V\cup U,E) with ∣V∣=n|V|=n and U=∅U=\varnothing such that the candidate set AC\mathcal{A}_{\mathcal{C}} constructed on line 11 of Algorithm 1 is non-empty for at least

(n−3)2(n−4)24\frac{(n-3)^2(n-4)^2}{4}

pairs (Z,W)∈Z×W(Z,W)\in\mathcal{Z}\times\mathcal{W}. Consequently, the maximum number N(n)N(n) of such pairs over all causal graphs with nn vertices satisfies N(n)=n4/4+O(n3)N(n)=n^4/4+O(n^3).

Proof. Let q=n/2≥3q=n/2\ge3 and let Gq\mathcal{G}_q be the graph with vertices V={X1,…,Xq,Y1,…,Yq}V=\{X_1,\ldots,X_q,Y_1,\ldots,Y_q\}, U=∅U=\varnothing, and the edges

Xj→YjandXj→Yj+1for j=1,…,q, where Yq+1=Y1,X_j\to Y_j \quad\text{and}\quad X_j\to Y_{j+1}\qquad\text{for }j=1,\ldots,q,\text{ where }Y_{q+1}=Y_1,
Yj→Yj+1andXj+1→Xjfor j=1,…,q−1;Y_j\to Y_{j+1}\quad\text{and}\quad X_{j+1}\to X_j\qquad\text{for }j=1,\ldots,q-1;

see Figure 6 for q=4q=4. The ordering Xq,…,X1,Y1,…,YqX_q,\ldots,X_1,Y_1,\ldots,Y_q is topological, so Gq\mathcal{G}_q is a DAG. Throughout the proof, the indices of XX and YY are read modulo qq, and for an integer aa and 1≤r≤q1\le r\le q we denote the cyclic arcs

Figure 6. The graph Gq\mathcal{G}_q of Proposition 16 for q=4q=4 (n=8n=8). The edge Yj−1→YjY_{j-1} \to Y_j places Yj−1Y_{j-1} among the parents of YjY_j, so the iterative parental siblings of YjY_j grow in one direction only along the cycle Y1,…,YqY_1,\ldots,Y_q. The edge Xj→Xj−1X_j \to X_{j-1} places Xj−1X_{j-1} among the children of XjX_j and plays the same role for the iterative filial siblings of XjX_j.

X[a,r]={Xa,Xa+1,…,Xa+r−1},Y[a,r]={Ya,Ya+1,…,Ya+r−1}.X[a,r]=\{X_a,X_{a+1},\ldots,X_{a+r-1}\},\qquad Y[a,r]=\{Y_a,Y_{a+1},\ldots,Y_{a+r-1}\}.

We omit the subscript Gq\mathcal{G}_q from Pa⁡\operatorname{Pa}, Ch⁡\operatorname{Ch}, An⁡\operatorname{An}, De⁡\operatorname{De}, IPS⁡\operatorname{IPS} and IFS⁡\operatorname{IFS} for clarity. The parents and children of single vertices are

Pa⁡∗(Xj)={Xj+1} (j<q),Pa⁡∗(Yj)={Xj−1,Xj,Yj−1} (j≥2),Pa⁡∗(Y1)={Xq,X1},\operatorname{Pa}^{*}(X_j)=\{X_{j+1}\}\ (j<q),\qquad\operatorname{Pa}^{*}(Y_j)=\{X_{j-1},X_j,Y_{j-1}\}\ (j\ge2),\qquad\operatorname{Pa}^{*}(Y_1)=\{X_q,X_1\},
Ch⁡∗(Yj)={Yj+1} (j<q),Ch⁡∗(Xj)={Yj,Yj+1,Xj−1} (j≥2),Ch⁡∗(X1)={Y1,Y2},\operatorname{Ch}^{*}(Y_j)=\{Y_{j+1}\}\ (j<q),\qquad\operatorname{Ch}^{*}(X_j)=\{Y_j,Y_{j+1},X_{j-1}\}\ (j\ge2),\qquad\operatorname{Ch}^{*}(X_1)=\{Y_1,Y_2\},

and Pa⁡∗(Xq)=Ch⁡∗(Yq)=∅\operatorname{Pa}^{*}(X_q)=\operatorname{Ch}^{*}(Y_q)=\varnothing. We claim that for all 2≤k≤q−12\le k\le q-1: (I1) IPS⁡k(Xj)={Xj}∪Y[j+1,k]\operatorname{IPS}^{k}(X_j)=\{X_j\}\cup Y[j+1,k] for 1≤j≤q−11\le j\le q-1;

(I2) IPS⁡k(Yj)={Xj−2}∪Y[j,k]\operatorname{IPS}^{k}(Y_j)=\{X_{j-2}\}\cup Y[j,k] for 3≤j≤q3\le j\le q;

(F1) IFS⁡k(Xj)={Yj−1}∪X[j,k]\operatorname{IFS}^{k}(X_j)=\{Y_{j-1}\}\cup X[j,k] for 2≤j≤q2\le j\le q;

(F2) IFS⁡k(Yj)={Yj}∪X[j,k]\operatorname{IFS}^{k}(Y_j)=\{Y_j\}\cup X[j,k] for 2≤j≤q−12\le j\le q-1.

Proof of (I1). Let 1≤j≤q−11\le j\le q-1 and Zk=IPS⁡k(Xj)Z_k=\operatorname{IPS}^{k}(X_j). We have Pa⁡∗(Z1)={Xj+1}\operatorname{Pa}^{*}(Z_1)=\{X_{j+1}\} and Ch⁡∗(Xj+1)={Yj+1,Yj+2,Xj}\operatorname{Ch}^{*}(X_{j+1})=\{Y_{j+1},Y_{j+2},X_j\}, so Z2={Xj}∪Y[j+1,2]Z_2=\{X_j\}\cup Y[j+1,2]. Suppose that Zk={Xj}∪Y[j+1,k]Z_k=\{X_j\}\cup Y[j+1,k] for some 2≤k≤q−22\le k\le q-2. The parents of the vertices of Y[j+1,k]Y[j+1,k] among X1,…,XqX_1,\ldots,X_q are Xj,Xj+1,…,Xj+kX_j,X_{j+1},\ldots,X_{j+k}. Their only parent among Y1,…,YqY_1,\ldots,Y_q outside Y[j+1,k]Y[j+1,k] is YjY_j, the parent of Yj+1Y_{j+1}. Together with Pa⁡∗(Xj)={Xj+1}\operatorname{Pa}^{*}(X_j)=\{X_{j+1}\} this gives

Pa⁡∗(Zk)={Yj}∪X[j+1,k].\operatorname{Pa}^{*}(Z_k)=\{Y_j\}\cup X[j+1,k].

The only child of YjY_j is Yj+1∈ZkY_{j+1}\in Z_k. The children of the vertices of X[j+1,k]X[j+1,k] are the vertices of Y[j+1,k+1]Y[j+1,k+1] and vertices of X[j,k]X[j,k], all of which belong to Zk∪Pa⁡∗(Zk)Z_k\cup\operatorname{Pa}^{*}(Z_k) except for Yj+k+1Y_{j+k+1}. Because k+1≤q−1k+1\le q-1, we have Yj+k+1≠YjY_{j+k+1}\ne Y_j, so Yj+k+1∉Pa⁡∗(Zk)Y_{j+k+1}\notin\operatorname{Pa}^{*}(Z_k) and therefore Zk+1=Zk∪{Yj+k+1}={Xj}∪Y[j+1,k+1]Z_{k+1}=Z_k\cup\{Y_{j+k+1}\}=\{X_j\}\cup Y[j+1,k+1].

Proof of (I2), (F1) and (F2). These follow by the same computation, and we only record the first step and the set that drives the induction. In each case the step from kk to k+1k+1 is valid for 2≤k≤q−22\le k\le q-2 and adds exactly one vertex.

  • (I2): Pa⁡∗(Yj)={Xj−1,Xj,Yj−1}\operatorname{Pa}^{*}(Y_j)=\{X_{j-1},X_j,Y_{j-1}\} gives IPS⁡2(Yj)={Xj−2,Yj,Yj+1}\operatorname{IPS}^{2}(Y_j)=\{X_{j-2},Y_j,Y_{j+1}\}. If Zk={Xj−2}∪Y[j,k]Z_k=\{X_{j-2}\}\cup Y[j,k], then Pa⁡∗(Zk)={Yj−1}∪X[j−1,k+1]\operatorname{Pa}^{*}(Z_k)=\{Y_{j-1}\}\cup X[j-1,k+1], whose only child outside Zk∪Pa⁡∗(Zk)Z_k\cup\operatorname{Pa}^{*}(Z_k) is Yj+kY_{j+k}.

  • (F1): Ch⁡∗(Xj)={Yj,Yj+1,Xj−1}\operatorname{Ch}^{*}(X_j)=\{Y_j,Y_{j+1},X_{j-1}\} gives IFS⁡2(Xj)={Yj−1,Xj,Xj+1}\operatorname{IFS}^{2}(X_j)=\{Y_{j-1},X_j,X_{j+1}\}. If Wk={Yj−1}∪X[j,k]W_k=\{Y_{j-1}\}\cup X[j,k], then Ch⁡∗(Wk)={Xj−1}∪Y[j,k+1]\operatorname{Ch}^{*}(W_k)=\{X_{j-1}\}\cup Y[j,k+1], whose only parent outside Wk∪Ch⁡∗(Wk)W_k\cup\operatorname{Ch}^{*}(W_k) is Xj+kX_{j+k}.

  • (F2): Ch⁡∗(Yj)={Yj+1}\operatorname{Ch}^{*}(Y_j)=\{Y_{j+1}\} gives IFS⁡2(Yj)={Yj,Xj,Xj+1}\operatorname{IFS}^{2}(Y_j)=\{Y_j,X_j,X_{j+1}\}. If Wk={Yj}∪X[j,k]W_k=\{Y_j\}\cup X[j,k], then Ch⁡∗(Wk)={Xj−1}∪Y[j+1,k]\operatorname{Ch}^{*}(W_k)=\{X_{j-1}\}\cup Y[j+1,k], whose only parent outside Wk∪Ch⁡∗(Wk)W_k\cup\operatorname{Ch}^{*}(W_k) is Xj+kX_{j+k}.

Counting. Let Z0⊆ZZ_0\subseteq Z be the family of the sets in (I1) and (I2), and W0⊆WW_0\subseteq W the family of the sets in (F1) and (F2). Every set in Z0Z_0 contains exactly one of the vertices X1,…,XqX_1,\ldots,X_q, say XiX_i. Within (I1) and within (I2), the set is determined by XiX_i and its size. A set from (I1) contains Yi+1Y_{i+1}, whereas a set from (I2) is of the form {Xi}∪Y[i+2,k]\{X_i\}\cup Y[i+2,k] with k≤q−1k\le q-1 and does not contain Yi+1Y_{i+1}. Hence all sets in Z0Z_0 are distinct and

∣Z0∣=(q−1)(q−2)+(q−2)2=(q−2)(2q−3).|Z_0|=(q-1)(q-2)+(q-2)^2=(q-2)(2q-3).

Similarly, every set in W0W_0 contains exactly one of the vertices Y1,…,YqY_1,\ldots,Y_q, say YiY_i; a set from (F2) contains XiX_i, whereas a set from (F1) is of the form {Yi}∪X[i+1,k]\{Y_i\}\cup X[i+1,k] with k≤q−1k\le q-1 and does not. Hence ∣W0∣=(q−1)(q−2)+(q−2)2=(q−2)(2q−3)|W_0|=(q-1)(q-2)+(q-2)^2=(q-2)(2q-3).

Non-emptiness. Let Z∈Z0Z\in Z_0 and W∈W0W\in W_0, and let Xi∈ZX_i\in Z and Yh∈WY_h\in W. The directed path Xi→Xi−1→⋯→X1→Y1→Y2→⋯→YhX_i\to X_{i-1}\to\cdots\to X_1\to Y_1\to Y_2\to\cdots\to Y_h shows that Yh∈De⁡(Z)∩An⁡(W)∩VY_h\in\operatorname{De}(Z)\cap\operatorname{An}(W)\cap V, so the candidate set constructed on line 11 is non-empty. The number of such pairs is

∣Z0∣∣W0∣=(q−2)2(2q−3)2=(n−3)2(n−4)24.|Z_0||W_0|=(q-2)^2(2q-3)^2=\frac{(n-3)^2(n-4)^2}{4}.

Asymptotics. For even nn the lower bound above and the upper bound (2) give (n−3)2(n−4)2/4≤N(n)≤(n2+1)2/4(n-3)^2(n-4)^2/4 \le N(n) \le(n^2+1)^2/4. For odd n≥7n \ge7, adding one isolated observed vertex to G(n−1)/2G_{(n-1)/2} changes neither the sets above nor their descendants and ancestors, so N(n)≥(n−4)2(n−5)2/4N(n) \ge(n-4)^2(n-5)^2/4. In both cases N(n)=n4/4+O(n3)N(n) = n^4/4 + O(n^3). ■\blacksquare

Proof of Theorem 8

Definition 8. FINDCONDUITS is sound and complete for any valid parameters (G,R,λ)(\mathcal{G}, \mathbf{R}, \lambda) and outputs all (restricted) conduits in G=(V∪U,E)\mathcal{G} = (\mathbf{V} \cup\mathbf{U}, E) in O(n5m)O(n^{5}m) time with respect to R⊆V\mathbf{R} \subseteq\mathbf{V} and λ∈N\lambda\in\mathbb{N}, where n=∣V∪U∣n = |\mathbf{V} \cup\mathbf{U}| and m=∣E∣m = |E|.

Proof In the following, we denote A=FINDCONDUITS⁡(G,R,λ)\mathcal{A} = \operatorname{FINDCONDUITS}(\mathcal{G}, \mathbf{R}, \lambda).

Soundness: We need to verify that if the set AC\mathbf{A}_{C} is added to A\mathcal{A} in line 14 in Algorithm 1, then AC\mathbf{A}_{C} satisfies the conditions of Definition 6 and it is at least of size λ\lambda. For simplicity we assume that R=V\mathbf{R} = \mathbf{V}; the general case is proven similarly.

Lines 4 and 5 initialize the set of iterative parental and filial siblings per their definitions. This ensures that when proceeding to lines 9–11 to construct the candidate AC\mathbf{A}_{C}, the candidate is constructed by IPS and IFS. We notice that the construction of AC\mathbf{A}_{C} follows precisely conditions (B1)–(B3), using the IPS and IFS. Line 12 verifies that the candidate is at least of size λ\lambda and that it belongs entirely in the restriction set R\mathbf{R}. Line 13 verifies that condition (A) applies for the candidate AC\mathbf{A}_{C}. If this is the case, the candidate AC\mathbf{A}_{C} is added to A\mathcal{A}. Thus all conditions of Definition 6 are satisfied.

Completeness: Let T∈ΓG\mathbf{T} \in\Gamma_{\mathcal{G}} be a conduit such that ∣T∣≥λ|\mathbf{T}| \ge\lambda. We aim to show that T∈A=FINDCONDUITS⁡(G,R,λ)\mathbf{T} \in\mathcal{A} = \operatorname{FINDCONDUITS}(\mathcal{G}, \mathbf{R}, \lambda). We can assume without loss of generality that R=V\mathbf{R} = \mathbf{V}.

We begin by observing the lines 4 and 5 that initialize the set of iterative parental and filial siblings. These procedures ensure that Z\mathcal{Z} and W\mathcal{W} contain all possible IPS and IFS candidates, as shown by Lemma 14 in Appendix C.

By condition (B), T\mathbf{T} must be constructed by the iterative parental and/or filial sibling sets, denoted by Z\mathcal{Z} and W\mathcal{W}. The fact that Z\mathcal{Z} and W\mathcal{W} contain all possible IPS and IFS candidates ensures Z∈Z\mathcal{Z} \in\mathcal{Z} and/or W∈W\mathcal{W} \in\mathcal{W}.

Analyzing lines 9–11, we note that they construct the cluster candidate AC\mathbf{A}_{C} precisely as defined by the conditions (B1)–(B3), using Z\mathcal{Z} and W\mathcal{W}, so that T=AC\mathbf{T} = \mathbf{A}_{C}. In addition, at this point, the size of the candidate is not restricted, so it is possible that the candidate is of size λ\lambda. Because T\mathbf{T} is a conduit, condition on line 13 (which corresponds to (A)) is satisfied. Consequently, the set AC\mathbf{A}_{C} is added to the list of valid conduits in line 14.

Polynomial-time complexity: Let n=∣V∪U∣n = |\mathbf{V} \cup\mathbf{U}| and m=∣E∣m = |E|. In the worst case, no restriction is made and conduits of any size can be found, so we assume R=V\mathbf{R} = \mathbf{V} and λ=1\lambda= 1. Suppose that ancestral relationships between the variables have been assessed as a preprocessing step. This can be computed in O(n(n+m))O(n(n + m)) time. As a result, these sets are accessed in constant time. We then proceed to form the set of candidate iterative parental siblings in line 4. This set is formed iteratively by first assessing some Z∈V∪U\mathcal{Z} \in\mathbf{V} \cup\mathbf{U}, and then expanding this set by assessing the children of its parents. By Lemma 14, the expansion changes the set at most ⌈n/2⌉−1\lceil n/2 \rceil- 1 times, after which it can be stopped. Additionally, at worst, we are required to assess the parents and children of nn vertices in one iteration. Combining the results above, we can claim that, at worst, the candidate IPS set is acquired in O(n3)O(n^{3}) time. By Corollary 15, the set Z\mathcal{Z} contains at most (n2+1)/2(n^{2} + 1)/2 non-empty sets. Analogous results apply for IFS and the set W\mathcal{W}.

In lines 6–7, we then loop through each IPS-IFS pair. Counting also the empty sets included in Z\mathcal{Z} and W\mathcal{W}, this leads to at most ((n2+3)/2)2=O(n4)((n^{2} + 3)/2)^{2} = O(n^{4}) iterations, of which at most (n2+1)2/4(n^{2} + 1)^{2}/4 reach line 11. Proposition 16 in Appendix C shows that the leading term n4/4n^{4}/4 is attained, so the number of iterations cannot be reduced below order n4n^{4} in general. The operations to construct the candidate conduit AC\mathbf{A}_{C} in lines 9–11 are performed in O(n)O(n) time, enabled by the preprocessing step. Similarly, the minimum size and restriction set check on line 12 can be performed in O(n)O(n) time. Line 13 checks whether ACA_C is coherent. This requires assessing whether there exists a directed path from each parent of ACA_C to each child of ACA_C that passes directly through the cluster. This can be computed, e.g., by traversing from the parents of ACA_C in topological order through ACA_C and tracking which vertices of ACA_C can be reached from each parent, eventually finishing with the children of ACA_C (if they can be reached). The topological ordering can be obtained as a preprocessing step in O(n+m)O(n+m) time and an upper bound for the traversal is O(nm)O(nm).

Combining these results, we obtain

O(n(n+m)+(n+m)+2n3+n4(nm))=O(n5m),O\bigl(n(n+m)+(n+m)+2n^3+n^4(nm)\bigr)=O(n^5m),

which concludes the proof.

Additional Details Regarding the Simulation Study

The generation of a simulation instance follows the procedure below:

  1. Let G∗=(V,E∗)\mathcal{G}^*=(\mathrm{V},\mathrm{E}^*) be a DAG, and let U=∅\mathrm{U}=\varnothing and E=E∗\mathrm{E}=\mathrm{E}^*. For each unordered pair of distinct vertices Vi,Vj∈VV_i,V_j\in\mathrm{V}, with probability s/∣V∣s/|\mathrm{V}|, where s∈{0,0.1,0.2}s\in\{0,0.1,0.2\}, add a new unobserved vertex UkU_k to U\mathrm{U} and the edges Vi←Uk→VjV_i\leftarrow U_k\rightarrow V_j to E\mathrm{E}. Let G=(V∪U,E)\mathcal{G}=(\mathrm{V}\cup\mathrm{U},\mathrm{E}).

  1. Let L\mathrm{L} be the set of vertices of G\mathcal{G} that have no children, and let k=min⁡{4,max⁡{2,⌊∣V∣/25⌉}}k=\min\{4,\max\{2,\lfloor|\mathrm{V}|/25\rceil\}\}.

  1. Draw kk vertices at random from An⁡G∗(L)\operatorname{An}_{\mathcal{G}^*}(\mathrm{L}), and let D\mathrm{D} consist of these vertices and L\mathrm{L}.

  1. Let R=(V∪U)∖D\mathrm{R}=(\mathrm{V}\cup\mathrm{U})\setminus\mathrm{D}. Find the restricted conduits of size at least 2 with FINDCONDUITS(G,R,2)(\mathcal{G},\mathrm{R},2) and the restricted transit clusters with FINDTRCLUST(G,R)(\mathcal{G},\mathrm{R}) (such that all singletons are discarded), and record the time each algorithm takes. An algorithm that does not finish within 30 minutes is stopped, and its results for the repetition are recorded as missing.

  1. For each cluster found, check whether it is plain, c-isolated or c-coherent ([7]). Clusters that satisfy none of these conditions are discarded.

  1. Go through the remaining clusters from the largest to the smallest, and cluster each one that is disjoint from all previously clustered sets by replacing it with a single vertex (Definition 3). Universal identification invariance is preserved in iterative clustering (Nykänen et al., 2026, Corollary 26). Let G′\mathcal{G}' be the resulting graph. Record the numbers of found and certified clusters, the number of clusterings, and the numbers of observed vertices in G′\mathcal{G}'.

In Table 2–Table 4, we present the complete simulation results for no, few and moderate numbers of bidirected edges, respectively.

GraphAlgorithmAll clustersInvariant clustersReductionTime (s)
ALARMFindConduits28 (25, 32)28 (25, 32)14 (13, 16)1.4 (1.0, 1.9)
|V| = 37, |R| = 24FindTrClust4 (2, 4)4 (2, 4)4 (3, 4)2.5 (1.7, 3.0)
ARTH150FindConduits52 (44, 59)52 (44, 59)19 (18, 21)8.7 (6.2, 11.3)
|V| = 107, |R| = 36FindTrClust4 (2, 4)4 (2, 4)3 (2, 3)5.2 (3.7, 6.5)
BARLEYFindConduits84 (77, 91)84 (77, 91)25 (23, 26)2.6 (1.6, 3.4)
|V| = 48, |R| = 38FindTrClust5 (3, 5)5 (3, 5)6 (4, 6)6.7 (4.2, 8.3)
CHILDFindConduits30 (19, 37)30 (19, 37)5 (5, 6)0.2 (0.1, 0.3)
|V| = 20, |R| = 11FindTrClust1 (0, 1)1 (0, 1)1 (0, 1)0.4 (0.3, 0.6)
ECOLI70FindConduits28 (19, 35)28 (19, 35)12 (11, 14)2.5 (1.5, 3.3)
|V| = 46, |R| = 20FindTrClust2 (1, 2)2 (1, 2)2 (1, 2)2.1 (1.3, 2.8)
HAILFINDERFindConduits145 (125, 158)145 (125, 158)28 (27, 31)1.8 (1.3, 2.3)
|V| = 56, |R| = 41FindTrClust8 (6, 8)8 (6, 8)14 (12, 16)4.9 (3.5, 6.1)
HEPAR2FindConduits43 (34, 49)43 (34, 49)16 (14, 17)3.8 (2.7, 4.7)
|V| = 70, |R| = 26FindTrClust1 (1, 2)1 (1, 2)4 (1, 5)5.7 (4.2, 7.1)
INSURANCEFindConduits52 (35, 64)52 (35, 64)11 (10, 14)0.5 (0.4, 0.7)
|V| = 27, |R| = 19FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)1.0 (0.7, 1.3)
MAGIC-IRRIFindConduits99 (85, 109)99 (85, 109)29 (27, 31)4.4 (3.3, 5.5)
|V| = 64, |R| = 56FindTrClust1 (1, 1)1 (1, 1)1 (1, 1)2.8 (2.1, 3.3)
MAGIC-NIABFindConduits40 (36, 45)40 (36, 45)20 (17, 22)2.1 (1.4, 2.6)
|V| = 44, |R| = 37FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)1.1 (0.8, 1.4)
MEHRAFindConduits27 (21, 33)27 (21, 33)11 (9, 13)0.5 (0.3, 0.6)
|V| = 24, |R| = 19FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.7 (0.5, 1.0)
MILDEWFindConduits80 (69, 92)80 (69, 92)20 (18, 25)0.7 (0.5, 1.0)
|V| = 35, |R| = 32FindTrClust2 (1, 2)2 (1, 2)4 (3, 4)2.5 (1.8, 3.3)
PATHFINDERFindConduits60 (42, 88)60 (42, 88)12 (11, 14)7.7 (5.9, 9.4)
|V| = 109, |R| = 28FindTrClust2 (1, 2)2 (1, 2)2 (1, 2)4.0 (3.1, 4.8)
SACHSFindConduits3 (2, 4)3 (2, 4)2 (2, 3)0.1 (0.0, 0.1)
|V| = 11, |R| = 5FindTrClust1 (1, 1)1 (1, 1)1 (1, 1)0.2 (0.1, 0.2)
SANGIOVESEFindConduits27 (22, 40)27 (22, 40)9 (8, 10)0.4 (0.3, 0.5)
|V| = 15, |R| = 12FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)1.5 (1.1, 1.9)
WATERFindConduits17 (12, 23)17 (12, 23)12 (10, 14)0.8 (0.6, 1.0)
|V| = 32, |R| = 22FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)1.9 (1.4, 2.4)
WIN95PTSFindConduits107 (99, 114)107 (99, 114)33 (30, 35)5.5 (3.9, 6.9)
|V| = 76, |R| = 57FindTrClust2 (1, 2)2 (1, 2)4 (2, 4)5.0 (3.6, 6.1)

Table 2. Comparison of FindConduits and FindTrClust in all graphs with no bidirected edges (s=0s = 0). Each graph was studied in 1000 instances (i.e., repetitions of the simulation), and each graph name is followed by the number of observed vertices ∣V∣\lvert V\rvert and the number of vertices in the restriction set ∣R∣\lvert R\rvert. The table reports the median number of all clusters found, the median number of clusters among them that are universally identification invariant according to Nykänen et al. [7], the median reduction in the number of observed vertices obtained by clustering the invariant clusters, and the median running time of the algorithm. Interquartile ranges (Q1, Q3) are shown in parentheses.

GraphAlgorithmAll clustersInvariant clustersReductionTime (s)
ALARMFindConduits25 (22, 28)18 (14, 23)11 (9, 12)0.3 (0.3, 0.5)
ALARMFindTrClust2 (1, 3)2 (1, 3)2 (1, 3)0.4 (0.3, 0.4)
∣V∣=37|\mathbf{V}| = 37, ∣R∣=24|\mathbf{R}| = 24
ARTH150FindConduits37 (30, 43)31 (24, 39)15 (13, 17)9.4 (6.7, 12.7)
ARTH150FindTrClust2 (1, 4)2 (1, 4)2 (1, 3)2.4 (1.6, 2.8)
∣V∣=107|\mathbf{V}| = 107, ∣R∣=36|\mathbf{R}| = 36
BARLEYFindConduits69 (63, 76)46 (37, 57)18 (16, 20)0.8 (0.6, 1.2)
BARLEYFindTrClust2 (1, 4)2 (1, 3)3 (1, 5)1.0 (0.9, 1.1)
∣V∣=48|\mathbf{V}| = 48, ∣R∣=38|\mathbf{R}| = 38
CHILDFindConduits20 (13, 30)16 (9, 26)4 (3, 5)0.1 (0.1, 0.1)
CHILDFindTrClust1 (0, 1)1 (0, 1)1 (0, 1)0.2 (0.2, 0.3)
∣V∣=20|\mathbf{V}| = 20, ∣R∣=11|\mathbf{R}| = 11
ECOLI70FindConduits16 (14, 21)15 (11, 20)9 (8, 11)1.6 (1.1, 2.1)
ECOLI70FindTrClust1 (1, 2)1 (1, 2)1 (1, 2)0.9 (0.6, 1.2)
∣V∣=46|\mathbf{V}| = 46, ∣R∣=20|\mathbf{R}| = 20
HAILFINDERFindConduits148 (121, 164)71 (56, 91)23 (21, 26)0.9 (0.7, 1.2)
HAILFINDERFindTrClust4 (3, 6)4 (3, 5)8 (5, 10)1.5 (1.1, 1.7)
∣V∣=56|\mathbf{V}| = 56, ∣R∣=41|\mathbf{R}| = 41
HEPAR2FindConduits35 (27, 42)24 (18, 32)11 (10, 13)1.1 (0.9, 1.5)
HEPAR2FindTrClust1 (0, 1)1 (0, 1)1 (0, 1)0.9 (0.7, 1.2)
∣V∣=70|\mathbf{V}| = 70, ∣R∣=26|\mathbf{R}| = 26
INSURANCEFindConduits33 (25, 45)25 (16, 38)9 (7, 10)0.3 (0.3, 0.5)
INSURANCEFindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.5 (0.4, 0.6)
∣V∣=27|\mathbf{V}| = 27, ∣R∣=19|\mathbf{R}| = 19
MAGIC-IRRIFindConduits75 (64, 86)54 (43, 70)21 (18, 24)1.5 (1.2, 1.9)
MAGIC-IRRIFindTrClust1 (0, 1)1 (0, 1)1 (0, 1)0.7 (0.6, 0.7)
∣V∣=64|\mathbf{V}| = 64, ∣R∣=56|\mathbf{R}| = 56
MAGIC-NIABFindConduits33 (30, 37)26 (22, 30)13 (12, 17)0.8 (0.7, 1.0)
MAGIC-NIABFindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.4 (0.3, 0.4)
∣V∣=44|\mathbf{V}| = 44, ∣R∣=37|\mathbf{R}| = 37
MEHRAFindConduits24 (19, 31)15 (11, 20)8 (7, 10)0.3 (0.3, 0.4)
MEHRAFindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.5 (0.4, 0.6)
∣V∣=24|\mathbf{V}| = 24, ∣R∣=19|\mathbf{R}| = 19
MILDEWFindConduits72 (59, 90)37 (27, 51)17 (14, 19)0.4 (0.3, 0.5)
MILDEWFindTrClust1 (1, 2)1 (1, 2)1 (1, 4)1.1 (0.9, 1.3)
∣V∣=35|\mathbf{V}| = 35, ∣R∣=32|\mathbf{R}| = 32
PATHFINDERFindConduits35 (28, 44)34 (27, 43)10 (9, 11)2.9 (2.2, 3.7)
PATHFINDERFindTrClust1 (1, 2)1 (1, 2)1 (1, 2)1.3 (1.0, 1.6)
∣V∣=109|\mathbf{V}| = 109, ∣R∣=28|\mathbf{R}| = 28
SACHSFindConduits3 (2, 4)2 (2, 4)2 (2, 3)0.1 (0.0, 0.1)
SACHSFindTrClust1 (0, 1)1 (0, 1)1 (0, 1)0.1 (0.1, 0.1)
∣V∣=11|\mathbf{V}| = 11, ∣R∣=5|\mathbf{R}| = 5
SANGIOVESEFindConduits24 (17, 33)15 (9, 23)8 (6, 9)0.2 (0.1, 0.2)
SANGIOVESEFindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.6 (0.5, 0.8)
∣V∣=15|\mathbf{V}| = 15, ∣R∣=12|\mathbf{R}| = 12
WATERFindConduits8 (6, 12)8 (5, 12)7 (5, 10)0.5 (0.4, 0.6)
WATERFindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.8 (0.7, 1.0)
∣V∣=32|\mathbf{V}| = 32, ∣R∣=22|\mathbf{R}| = 22
WIN95PTSFindConduits88 (81, 94)61 (50, 73)25 (23, 28)2.3 (1.7, 3.3)
WIN95PTSFindTrClust1 (1, 2)1 (1, 2)2 (2, 4)1.1 (0.9, 1.4)
∣V∣=76|\mathbf{V}| = 76, ∣R∣=57|\mathbf{R}| = 57

Table 4. Comparison of FindConduits and FindTrClust in all graphs with moderate bidirected edges (s=0.2s = 0.2). Each graph was studied in 1000 instances (i.e., repetitions of the simulation), and each graph name is followed by the number of observed vertices ∣V∣|\mathbf{V}| and the number of vertices in the restriction set ∣R∣|\mathbf{R}|. The table reports the median number of all clusters found, the median number of clusters among them that are universally identification invariant according to Nykanen et al. [7], the median reduction in the number of observed vertices obtained by clustering the invariant clusters, and the median running time of the algorithm. Interquartile ranges (Q1, Q3) are shown in parentheses.

GraphAlgorithmAll clustersInvariant clustersReductionTime (s)
ALARMFindConduits26 (23, 29)23 (18, 27)12 (11, 14)0.8 (0.6, 1.0)
∣V∣=37|\mathrm{V}| = 37, ∣R∣=24|\mathrm{R}| = 24FindTrClust3 (2, 4)2 (2, 4)3 (2, 4)1.1 (0.9, 1.3)
ARTH150FindConduits42 (36, 51)39 (31, 48)17 (15, 18)7.8 (5.8, 10.6)
∣V∣=107|\mathrm{V}| = 107, ∣R∣=36|\mathrm{R}| = 36FindTrClust3 (2, 4)3 (2, 4)2 (2, 3)2.8 (2.1, 3.2)
BARLEYFindConduits75 (68, 82)62 (50, 73)21 (19, 24)1.8 (1.3, 2.4)
∣V∣=48|\mathrm{V}| = 48, ∣R∣=38|\mathrm{R}| = 38FindTrClust3 (2, 5)3 (1, 5)5 (3, 6)3.3 (2.5, 3.9)
CHILDFindConduits23 (15, 33)20 (13, 31)5 (4, 6)0.2 (0.1, 0.3)
∣V∣=20|\mathrm{V}| = 20, ∣R∣=11|\mathrm{R}| = 11FindTrClust1 (0, 1)1 (0, 1)1 (0, 1)0.4 (0.3, 0.5)
ECOLI70FindConduits19 (16, 28)19 (15, 27)11 (9, 12)1.5 (1.1, 1.9)
∣V∣=46|\mathrm{V}| = 46, ∣R∣=20|\mathrm{R}| = 20FindTrClust2 (1, 2)2 (1, 2)2 (1, 2)1.0 (0.8, 1.2)
HAILFINDERFindConduits147 (122, 161)97 (79, 119)26 (24, 29)0.7 (0.6, 0.9)
∣V∣=56|\mathrm{V}| = 56, ∣R∣=41|\mathrm{R}| = 41FindTrClust5 (4, 7)5 (4, 7)10 (7, 13)1.5 (1.1, 1.7)
HEPAR2FindConduits39 (30, 45)32 (25, 41)13 (12, 15)0.8 (0.6, 2.4)
∣V∣=70|\mathrm{V}| = 70, ∣R∣=26|\mathrm{R}| = 26FindTrClust1 (1, 1)1 (1, 1)1 (1, 4)0.8 (0.6, 2.6)
INSURANCEFindConduits38 (29, 55)34 (22, 52)10 (8, 12)0.6 (0.4, 0.8)
∣V∣=27|\mathrm{V}| = 27, ∣R∣=19|\mathrm{R}| = 19FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.9 (0.7, 1.1)
MAGIC-IRRIFindConduits84 (71, 95)70 (57, 88)25 (21, 27)2.4 (1.9, 3.0)
∣V∣=64|\mathrm{V}| = 64, ∣R∣=56|\mathrm{R}| = 56FindTrClust1 (0, 1)1 (0, 1)1 (0, 1)1.3 (1.0, 1.6)
MAGIC-NIABFindConduits35 (31, 39)31 (26, 36)16 (13, 20)1.4 (1.1, 1.7)
∣V∣=44|\mathrm{V}| = 44, ∣R∣=37|\mathrm{R}| = 37FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.7 (0.6, 0.8)
MEHRAFindConduits25 (20, 32)20 (15, 27)10 (8, 11)0.5 (0.4, 0.6)
∣V∣=24|\mathrm{V}| = 24, ∣R∣=19|\mathrm{R}| = 19FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.8 (0.6, 1.0)
MILDEWFindConduits76 (63, 91)54 (41, 71)18 (17, 22)0.6 (0.5, 0.8)
∣V∣=35|\mathrm{V}| = 35, ∣R∣=32|\mathrm{R}| = 32FindTrClust1 (1, 2)1 (1, 2)3 (1, 4)1.8 (1.5, 2.4)
PATHFINDERFindConduits42 (34, 59)42 (34, 58)11 (10, 12)2.6 (2.1, 3.4)
∣V∣=109|\mathrm{V}| = 109, ∣R∣=28|\mathrm{R}| = 28FindTrClust1 (1, 2)1 (1, 2)1 (1, 2)1.2 (1.0, 1.6)
SACHSFindConduits3 (2, 4)3 (2, 4)2 (2, 3)0.0 (0.0, 0.1)
∣V∣=11|\mathrm{V}| = 11, ∣R∣=5|\mathrm{R}| = 5FindTrClust1 (0, 1)1 (0, 1)1 (0, 1)0.1 (0.1, 0.1)
SANGIOVESEFindConduits25 (20, 35)21 (14, 28)9 (7, 10)0.2 (0.2, 0.3)
∣V∣=15|\mathrm{V}| = 15, ∣R∣=12|\mathrm{R}| = 12FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)0.8 (0.6, 1.1)
WATERFindConduits11 (8, 17)11 (7, 17)9 (7, 12)0.6 (0.4, 0.8)
∣V∣=32|\mathrm{V}| = 32, ∣R∣=22|\mathrm{R}| = 22FindTrClust0 (0, 0)0 (0, 0)0 (0, 0)1.3 (1.0, 1.6)
WIN95PTSFindConduits94 (87, 101)80 (69, 90)28 (26, 31)2.1 (1.6, 2.9)
∣V∣=76|\mathrm{V}| = 76, ∣R∣=57|\mathrm{R}| = 57FindTrClust2 (1, 2)1 (1, 2)2 (2, 4)1.4 (1.1, 1.8)

Table 3. Comparison of FindConduits and FindTrClust in all graphs with few bidirected edges (s=0.1s = 0.1). Each graph was studied in 1000 instances (i.e., repetitions of the simulation), and each graph name is followed by the number of observed vertices ∣V∣|\mathrm{V}| and the number of vertices in the restriction set ∣R∣|\mathrm{R}|. The table reports the median number of all clusters found, the median number of clusters among them that are universally identification invariant according to Nykänen et al. [7], the median reduction in the number of observed vertices obtained by clustering the invariant clusters, and the median running time of the algorithm. Interquartile ranges (Q1, Q3) are shown in parentheses.

References

  1. [1]T. V. Anand, A. H. Ribeiro, J. Tian, and E. Bareinboim. Causal effect identification in cluster DAGs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10):12172–12179, 2023. doi: 10.1609/aaai.v37i10.26435.DOI
  2. [2]Bayesian Network Repository. Bayesian network repository. https://www.bnlearn.com/bnrepository/, 2026. Accessed May 18, 2026.
  3. [3]J. Binder, D. Koller, S. Russell, and K. Kanazawa. Adaptive probabilistic networks with hidden variables. Machine Learning, 29(2-3):213–244, 1997.DOI
  4. [4]S. Ferreira and C. K. Assaad. Identifying macro causal effects in a C-DMG over ADMGs. Transactions on Machine Learning Research, July 2025.arxiv.org/abs/2504.01551
  5. [5]F. Madaleno, P. Misra, and A. Markham. Coarsening causal DAG models. arXiv preprint arXiv:2601.10531, 2026.arxiv.org/abs/2601.10531
  6. [6]U. Ninad, J. Wahl, A. Gerhardus, and J. Runge. Causal discovery on vector-valued variables and consistency-guided aggregation. arXiv preprint arXiv:2505.10476, 2025.arxiv.org/abs/2505.10476
  7. [7]J. Nykänen, O. Tabell, S. Tikka, and J. Karvanen. Invariance of clustering operations in causal effect identification, 2026. URL https://arxiv.org/abs/2610.03101.
  8. [8]R Core Team. R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. https://www.R-project.org/, 2026.
  9. [11]M. Scutari. Learning Bayesian networks with the bnlearn R package. Journal of Statistical Software, 35(3):1–22, 2010.arxiv.org/abs/0908.3817
  10. [12]I. Shpitser and J. Pearl. Identification of joint interventional distributions in recursive semi-Markovian causal models. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI), pages 1219–1226, 2006.
  11. [13]O. Tabell, S. Tikka, and J. Karvanen. Clustering and pruning in causal data fusion. Journal of Machine Learning Research, 27(175):1–56, 2026. URL http://jmlr.org/papers/v27/25-1140.html.arxiv.org/abs/2505.15215
  12. [14]J. Tian and J. Pearl. A general identification condition for causal effects. In Eighteenth National Conference on Artificial Intelligence, pages 567–573. American Association for Artificial Intelligence, 2002.DOI
  13. [15]S. Tikka, J. Helske, and J. Karvanen. Clustering and structural robustness in causal diagrams. Journal of Machine Learning Research, 24(195):1–32, 2023.
  14. [16]T. S. Verma. Graphical aspects of causal models. Technical report, Department of Computer Science, University of California, Los Angeles, 1993. R-191.
  15. [17]A. Zeng, M. Cafarella, B. Kenig, M. Markakis, B. Youngmann, and B. Salimi. Causal DAG summarization. Proceedings of the VLDB Endowment, 18(6):1933–1947, 2025.DOI

Paper details

vlnc:W_t3qpjywf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Fable 5.2, Claude Opus 5.5

View statement
Looking for related papers…
Contents