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 -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. Nykä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 , and an upper case letter without bolding denotes elements of the corresponding set, e.g., . When is considered a variable, then a lower case letter is used in value assignments, e.g., . Similarly, assigning a value to a vector of variables is denoted by .
A directed acyclic graph (DAG) is a pair , where is the set of vertices and is the set of directed edges, denoted by arrows , such that there are no directed cycles in . For sets in a DAG , we denote by , , and the parents, children, ancestors and descendants of the vertices of (including itself) in , respectively. If the set is excluded from the respective sets, then an asterisk is included (e.g., ). In the case of a singleton set, that is, , we omit the curly brackets (e.g., ).
We are interested in DAGs induced by structural causal models.
Definition 1 (Structural causal model). A structural causal model (SCM) is a tuple consisting of the following objects:
A vector of observed random variables , and a vector of unobserved random variables .
A family of functions such that each is a map from the state space of to the state space of , where , such that forms a map from the state space of to the state space of . Accordingly, each random variable is defined by the corresponding structural equation .
A joint probability distribution of the unobserved variables .
We only consider recursive SCMs, i.e., models where the unique solution of in terms of is obtained by recursively substituting each in every function with their corresponding functional representation with respect to . Moreover, we restrict our attention to SCMs that are semi-Markovian, that is, models whose unobserved variables admit a partition , where is the set of dedicated error terms (i.e., if and only if is present in exactly one structural equation), and consists of those unobserved variables that are present in exactly two structural equations. A motivation for this restriction is described below.
An SCM induces a causal graph, that is, a DAG , where the vertices represent the variables in , and the directed edges in point from the members of to . The dedicated error terms are omitted from the causal graphs, i.e., all members of have exactly two children in . In general we make no distinction between the variables of the model and their corresponding vertices in the induced causal graph.
Vertices of and are called observed and unobserved vertices (of ), respectively. Unobserved vertices are presented in figures using bidirected (dashed) edges without specifying the unobserved vertex itself (i.e., a fork , where , is represented as ). Given a set , we denote by the set augmented with all unobserved vertices whose both children are in , that is, .
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 and disjoint vertex sets , the causal effect is identifiable from in if for every pair of distributions induced by SCMs compatible with such that for all valid value assignments .
To ensure that all causal effects and identifying functionals are well-defined, we restrict ourselves to study identifiability from distributions that satisfy for all value assignments .
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 be a causal graph. Clustering a vertex set induces a directed graph such that:
, where the vertex represents the clustered set , and , that is, all unobserved vertices whose both children are in the set are excluded from .
The set of edges \mathbf{E}$ by removing all edges connected to (including the edges , where ), and adding new edges connecting to such that the edge or is in if and only if there is a vertex and an edge or in , respectively.
We only consider clustering operations that induce a DAG, in which case is a causal graph. Without this restriction, clustering can create a directed cycle in the clustered graph, such as in Figure 1a.

Figure 1. (a) Clustering the set creates a directed cycle in the clustered graph. (b) Clustering the set creates a new path from to , which also renders the causal effect nonidentifiable. (c) The cluster is a conduit. (d) 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 that induces a causal graph , there exists a causal model which induces the clustered graph such that can be constructed from by replacing the set of variables with a single vector-valued variable that has members of as its components, and modifying the structural equations of and its children (i.e., those variables whose structural equations contain variables in ) accordingly. The causal model is necessarily semi-Markovian if is semi-Markovian because .
If there exists whose both children are in the set , then after clustering the vertex has only one child, namely the vertex , 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 .
We disallow clustering unobserved vertices (i.e., ) to avoid ambiguity regarding whether the vertex representing the cluster 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:
Identification invariance: The clusters should carry properties that enable the application of theoretical results related to identification invariance (Appendix § 7).
Efficient detection: A set of potential clustering operations can be discovered efficiently algorithmically.
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).
| Graph | Bidirected edges | Algorithm | All clusters | Invariant clusters | Reduction |
| PATHFINDER<br><br> | none | FINDCONDUITS | 60 (42, 88) | 60 (42, 88) | 12 (11, 14) |
| PATHFINDER<br><br> | none | FINDTRCLUST | 2 (1, 2) | 2 (1, 2) | 2 (1, 2) |
| PATHFINDER<br><br> | few | FINDCONDUITS | 42 (34, 59) | 42 (34, 58) | 11 (10, 12) |
| PATHFINDER<br><br> | few | FINDTRCLUST | 1 (1, 2) | 1 (1, 2) | 1 (1, 2) |
| PATHFINDER<br><br> | moderate | FINDCONDUITS | 35 (28, 44) | 34 (27, 43) | 10 (9, 11) |
| PATHFINDER<br><br> | moderate | FINDTRCLUST | 1 (1, 2) | 1 (1, 2) | 1 (1, 2) |
| ARTH150<br><br> | none | FINDCONDUITS | 52 (44, 59) | 52 (44, 59) | 19 (18, 21) |
| ARTH150<br><br> | none | FINDTRCLUST | 4 (2, 4) | 4 (2, 4) | 3 (2, 3) |
| ARTH150<br><br> | few | FINDCONDUITS | 42 (36, 51) | 39 (31, 48) | 17 (15, 18) |
| ARTH150<br><br> | few | FINDTRCLUST | 3 (2, 4) | 3 (2, 4) | 2 (2, 3) |
| ARTH150<br><br> | moderate | FINDCONDUITS | 37 (30, 43) | 31 (24, 39) | 15 (13, 17) |
| ARTH150<br><br> | moderate | FINDTRCLUST | 2 (1, 4) | 2 (1, 4) | 2 (1, 3) |
| WIN95PTS<br><br> | none | FINDCONDUITS | 107 (99, 114) | 107 (99, 114) | 33 (30, 35) |
| WIN95PTS<br><br> | none | FINDTRCLUST | 2 (1, 2) | 2 (1, 2) | 4 (2, 4) |
| WIN95PTS<br><br> | few | FINDCONDUITS | 94 (87, 101) | 80 (69, 90) | 28 (26, 31) |
| WIN95PTS<br><br> | few | FINDTRCLUST | 2 (1, 2) | 1 (1, 2) | 2 (2, 4) |
| WIN95PTS<br><br> | moderate | FINDCONDUITS | 88 (81, 94) | 61 (50, 73) | 25 (23, 28) |
| WIN95PTS<br><br> | moderate | FINDTRCLUST | 1 (1, 2) | 1 (1, 2) | 2 (2, 4) |
| HEPAR2<br><br> | none | FINDCONDUITS | 43 (34, 49) | 43 (34, 49) | 16 (14, 17) |
| HEPAR2<br><br> | none | FINDTRCLUST | 1 (1, 2) | 1 (1, 2) | 4 (1, 5) |
| HEPAR2<br><br> | few | FINDCONDUITS | 39 (30, 45) | 32 (25, 41) | 13 (12, 15) |
| HEPAR2<br><br> | few | FINDTRCLUST | 1 (1, 1) | 1 (1, 1) | 1 (1, 4) |
| HEPAR2<br><br> | moderate | FINDCONDUITS | 35 (27, 42) | 24 (18, 32) | 11 (10, 13) |
| HEPAR2<br><br> | moderate | FINDTRCLUST | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) |
| MAGIC-IRRI<br><br> | none | FINDCONDUITS | 99 (85, 109) | 99 (85, 109) | 29 (27, 31) |
| MAGIC-IRRI<br><br> | none | FINDTRCLUST | 1 (1, 1) | 1 (1, 1) | 1 (1, 1) |
| MAGIC-IRRI<br><br> | few | FINDCONDUITS | 84 (71, 95) | 70 (57, 88) | 25 (21, 27) |
| MAGIC-IRRI<br><br> | few | FINDTRCLUST | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) |
| MAGIC-IRRI<br><br> | moderate | FINDCONDUITS | 75 (64, 86) | 54 (43, 70) | 21 (18, 24) |
| MAGIC-IRRI<br><br> | moderate | FINDTRCLUST | 1 (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 and the number of vertices in the restriction set . 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 be a causal graph. The set of -th iterative parental siblings of is , where the sets are defined recursively by letting and for .
In the first iteration of IPS, we select some . 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 be a causal graph. The set of -th iterative filial siblings of is , where the sets are defined recursively by letting and for .
We define a conduit as the intersection of the descendants of the iterative parental siblings of some and and the ancestors of the iterative filial siblings of some and (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 in a causal graph is a conduit if
(A) For each and there is a directed path such that and .
(B) There exist and for which at least one of the following conditions is satisfied:
(B1) for and .
(B2) for .
(B3) for .
The set of conduits in is denoted by .
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 , whose iterative sibling sets appearing are and either , or , which shows that the sibling sets that generate a conduit are not always unique.
In fig:1d the cluster satisfies condition (B), but not condition (A). Consequently, clustering creates a directed path from to , even though there is no directed path between and in the original graph.
In practical applications, we may be interested in finding conduits for a subset . 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 in a causal graph , a vertex set is a restricted conduit with respect to , if and is a conduit in . The set of conduits restricted to is denoted by .
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 . 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 according to conditions (B1)–(B3) on lines 9–11. Line 12 rejects candidates that do not entirely belong to the restriction set or that do not meet the minimum size requirement of . Condition (A) is then validated on line 13. Upon successful validation, we add 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 and outputs all (restricted) conduits in in time with respect to and , where and .
Algorithm 1 An algorithm for finding every (restricted) conduit in a given causal graph. The inputs are a causal graph , a non-empty restriction set whose members are the only vertices that are allowed to belong to any conduit, and the minimum size of the conduits . Returns the set of all restricted conduits of that are at least of size .
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: 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 , 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., . We are interested in all causal effects where interventions are performed on a subset of and a subset of forms the responses, and therefore exclude from clustering. In other words, the restriction set consists of all observed vertices except for and . 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 , 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]).

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 consisting of all other observed vertices. One of the conduits found, , 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 , cluster 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 that maps a causal graph to a causal graph obtained by clustering in . Then:
is identification invariant for a family of causal effects if each causal effect is either identifiable in and or nonidentifiable in and .
is universally identification invariant if the operation is identification invariant for the maximal family of causal effects not involving the variables of , that is, the set of causal effects such that and .
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 forms a conduit, and the causal effect is identifiable in the original graph but not after clustering .
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 in a causal graph is coherent provided that for all and there exists a directed path such that and . 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: , that is, 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 such that , and for each , either , or there exists a directed path in such that and the graph induced by the vertex set is a c-component. (Definition 20, Theorem 21)
c-isolation: There exists a vertex such that , and for each c-component in it either holds or , that is, there is no bidirected path from to . (Definition 22, Theorem 23)
Recall that a bidirected path is a path consisting solely of bidirected edges, that is, a path of the type , where and .
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 in a causal graph , the set of receivers is the set
that is, the set of all vertices of that have parents outside the vertex set .
Definition 12 (Emitter). For a set of vertices in a causal graph , the set of emitters is the set
that is, the set of all vertices of that have children outside the vertex set .
In the following, we use the notation for the induced subgraph of , where and contains those edges of that have both endpoints in . A transit cluster is defined as follows:
Definition 13 (Transit cluster). A set of vertices in a causal graph is a transit cluster if the following conditions hold:
(T1) For all pairs of receivers it holds (i.e., all receivers have the same parents).
(T2) For all pairs of emitters it holds (i.e., all emitters have the same children).
(T3) For all vertices there exists a receiver or an emitter such that and or and are connected via an undirected path in the subgraph , which is obtained from by removing all incoming edges to and all outgoing edges from .
(T4) If , then for all there exists an emitter such that .
(T5) If , then for all there exists a receiver such that .
If is connected in , then 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 .
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:

Figure 5. (a) is a transit cluster, but not a conduit, because it does not satisfy (B). (b) is both a transit cluster and a conduit. Examples illustrating similarities and differences between conduits (Definition 6) and transit clusters.
The transit cluster 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 because any IPS or IFS set that contains both and must also contain .
The cluster 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 or (or both) is removed, then 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 be a causal graph with vertices, let , and let for . Then
(i) for all , and if for some , then for all ;
(ii) the sequence contains at most distinct sets, and for all ;
(iii) if has no parents, then for all .
The same statements hold for the iterative filial siblings of a vertex , where in (iii) the vertex is assumed to have no children.
Proof. Write , so that by Definition 4. The inclusion in (i) is immediate, and the second claim of (i) holds because is a function of alone. Claim (iii) follows from . For (ii) we use three observations, valid for all :
(a) . Indeed, and by the definition of .
(b) . Each is a parent of some vertex of , and by (a).
(c) If , then . Indeed, , because .
Let be the number of distinct sets in the sequence. By (i), and for all ; in particular . If there is nothing to prove, so let . Then implies , and for the relation together with (b) and (c) implies . Hence . Since and are disjoint by (a), we obtain , that is, .
The argument uses no property of other than it being a directed graph. Applying it to the graph obtained from 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 .
Corollary 15 (Number of candidate pairs). Let be a causal graph with vertices, and let and be the sets constructed on lines 4 and 5 of Algorithm 1. Then
Consequently, line 11 of Algorithm 1 is executed for at most
pairs , and in particular at most this many non-empty candidate sets are constructed on line 11.
Proof. As is a DAG, it has at least one vertex without parents, which contributes only its singleton to by Lemma 14(iii). Each of the remaining vertices contributes at most sets by Lemma 14(ii). This gives the first inequality of (1). For the second, note that equals when is odd and when is even. The bound for is obtained in the same way from a vertex without children. Finally, line 11 is reached only if and , so (2) follows from (1).
Proposition 16 (Worst-case number of candidate sets). For every even there exists a causal graph with and such that the candidate set constructed on line 11 of Algorithm 1 is non-empty for at least
pairs . Consequently, the maximum number of such pairs over all causal graphs with vertices satisfies .
Proof. Let and let be the graph with vertices , , and the edges
see Figure 6 for . The ordering is topological, so is a DAG. Throughout the proof, the indices of and are read modulo , and for an integer and we denote the cyclic arcs
Figure 6. The graph of Proposition 16 for (). The edge places among the parents of , so the iterative parental siblings of grow in one direction only along the cycle . The edge places among the children of and plays the same role for the iterative filial siblings of .
We omit the subscript from , , , , and for clarity. The parents and children of single vertices are
and . We claim that for all : (I1) for ;
(I2) for ;
(F1) for ;
(F2) for .
Proof of (I1). Let and . We have and , so . Suppose that for some . The parents of the vertices of among are . Their only parent among outside is , the parent of . Together with this gives
The only child of is . The children of the vertices of are the vertices of and vertices of , all of which belong to except for . Because , we have , so and therefore .
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 to is valid for and adds exactly one vertex.
(I2): gives . If , then , whose only child outside is .
(F1): gives . If , then , whose only parent outside is .
(F2): gives . If , then , whose only parent outside is .
Counting. Let be the family of the sets in (I1) and (I2), and the family of the sets in (F1) and (F2). Every set in contains exactly one of the vertices , say . Within (I1) and within (I2), the set is determined by and its size. A set from (I1) contains , whereas a set from (I2) is of the form with and does not contain . Hence all sets in are distinct and
Similarly, every set in contains exactly one of the vertices , say ; a set from (F2) contains , whereas a set from (F1) is of the form with and does not. Hence .
Non-emptiness. Let and , and let and . The directed path shows that , so the candidate set constructed on line 11 is non-empty. The number of such pairs is
Asymptotics. For even the lower bound above and the upper bound (2) give . For odd , adding one isolated observed vertex to changes neither the sets above nor their descendants and ancestors, so . In both cases .
Proof of Theorem 8
Definition 8. FINDCONDUITS is sound and complete for any valid parameters and outputs all (restricted) conduits in in time with respect to and , where and .
Proof In the following, we denote .
Soundness: We need to verify that if the set is added to in line 14 in Algorithm 1, then satisfies the conditions of Definition 6 and it is at least of size . For simplicity we assume that ; 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 , the candidate is constructed by IPS and IFS. We notice that the construction of follows precisely conditions (B1)–(B3), using the IPS and IFS. Line 12 verifies that the candidate is at least of size and that it belongs entirely in the restriction set . Line 13 verifies that condition (A) applies for the candidate . If this is the case, the candidate is added to . Thus all conditions of Definition 6 are satisfied.
Completeness: Let be a conduit such that . We aim to show that . We can assume without loss of generality that .
We begin by observing the lines 4 and 5 that initialize the set of iterative parental and filial siblings. These procedures ensure that and contain all possible IPS and IFS candidates, as shown by Lemma 14 in Appendix C.
By condition (B), must be constructed by the iterative parental and/or filial sibling sets, denoted by and . The fact that and contain all possible IPS and IFS candidates ensures and/or .
Analyzing lines 9–11, we note that they construct the cluster candidate precisely as defined by the conditions (B1)–(B3), using and , so that . In addition, at this point, the size of the candidate is not restricted, so it is possible that the candidate is of size . Because is a conduit, condition on line 13 (which corresponds to (A)) is satisfied. Consequently, the set is added to the list of valid conduits in line 14.
Polynomial-time complexity: Let and . In the worst case, no restriction is made and conduits of any size can be found, so we assume and . Suppose that ancestral relationships between the variables have been assessed as a preprocessing step. This can be computed in 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 , and then expanding this set by assessing the children of its parents. By Lemma 14, the expansion changes the set at most times, after which it can be stopped. Additionally, at worst, we are required to assess the parents and children of vertices in one iteration. Combining the results above, we can claim that, at worst, the candidate IPS set is acquired in time. By Corollary 15, the set contains at most non-empty sets. Analogous results apply for IFS and the set .
In lines 6–7, we then loop through each IPS-IFS pair. Counting also the empty sets included in and , this leads to at most iterations, of which at most reach line 11. Proposition 16 in Appendix C shows that the leading term is attained, so the number of iterations cannot be reduced below order in general. The operations to construct the candidate conduit in lines 9–11 are performed in time, enabled by the preprocessing step. Similarly, the minimum size and restriction set check on line 12 can be performed in time. Line 13 checks whether is coherent. This requires assessing whether there exists a directed path from each parent of to each child of that passes directly through the cluster. This can be computed, e.g., by traversing from the parents of in topological order through and tracking which vertices of can be reached from each parent, eventually finishing with the children of (if they can be reached). The topological ordering can be obtained as a preprocessing step in time and an upper bound for the traversal is .
Combining these results, we obtain
which concludes the proof.
Additional Details Regarding the Simulation Study
The generation of a simulation instance follows the procedure below:
Let be a DAG, and let and . For each unordered pair of distinct vertices , with probability , where , add a new unobserved vertex to and the edges to . Let .
Let be the set of vertices of that have no children, and let .
Draw vertices at random from , and let consist of these vertices and .
Let . Find the restricted conduits of size at least 2 with
FINDCONDUITSand the restricted transit clusters withFINDTRCLUST(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.
For each cluster found, check whether it is plain, c-isolated or c-coherent ([7]). Clusters that satisfy none of these conditions are discarded.
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 be the resulting graph. Record the numbers of found and certified clusters, the number of clusterings, and the numbers of observed vertices in .
In Table 2–Table 4, we present the complete simulation results for no, few and moderate numbers of bidirected edges, respectively.
| Graph | Algorithm | All clusters | Invariant clusters | Reduction | Time (s) |
| ALARM | FindConduits | 28 (25, 32) | 28 (25, 32) | 14 (13, 16) | 1.4 (1.0, 1.9) |
| |V| = 37, |R| = 24 | FindTrClust | 4 (2, 4) | 4 (2, 4) | 4 (3, 4) | 2.5 (1.7, 3.0) |
| ARTH150 | FindConduits | 52 (44, 59) | 52 (44, 59) | 19 (18, 21) | 8.7 (6.2, 11.3) |
| |V| = 107, |R| = 36 | FindTrClust | 4 (2, 4) | 4 (2, 4) | 3 (2, 3) | 5.2 (3.7, 6.5) |
| BARLEY | FindConduits | 84 (77, 91) | 84 (77, 91) | 25 (23, 26) | 2.6 (1.6, 3.4) |
| |V| = 48, |R| = 38 | FindTrClust | 5 (3, 5) | 5 (3, 5) | 6 (4, 6) | 6.7 (4.2, 8.3) |
| CHILD | FindConduits | 30 (19, 37) | 30 (19, 37) | 5 (5, 6) | 0.2 (0.1, 0.3) |
| |V| = 20, |R| = 11 | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 0.4 (0.3, 0.6) |
| ECOLI70 | FindConduits | 28 (19, 35) | 28 (19, 35) | 12 (11, 14) | 2.5 (1.5, 3.3) |
| |V| = 46, |R| = 20 | FindTrClust | 2 (1, 2) | 2 (1, 2) | 2 (1, 2) | 2.1 (1.3, 2.8) |
| HAILFINDER | FindConduits | 145 (125, 158) | 145 (125, 158) | 28 (27, 31) | 1.8 (1.3, 2.3) |
| |V| = 56, |R| = 41 | FindTrClust | 8 (6, 8) | 8 (6, 8) | 14 (12, 16) | 4.9 (3.5, 6.1) |
| HEPAR2 | FindConduits | 43 (34, 49) | 43 (34, 49) | 16 (14, 17) | 3.8 (2.7, 4.7) |
| |V| = 70, |R| = 26 | FindTrClust | 1 (1, 2) | 1 (1, 2) | 4 (1, 5) | 5.7 (4.2, 7.1) |
| INSURANCE | FindConduits | 52 (35, 64) | 52 (35, 64) | 11 (10, 14) | 0.5 (0.4, 0.7) |
| |V| = 27, |R| = 19 | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 1.0 (0.7, 1.3) |
| MAGIC-IRRI | FindConduits | 99 (85, 109) | 99 (85, 109) | 29 (27, 31) | 4.4 (3.3, 5.5) |
| |V| = 64, |R| = 56 | FindTrClust | 1 (1, 1) | 1 (1, 1) | 1 (1, 1) | 2.8 (2.1, 3.3) |
| MAGIC-NIAB | FindConduits | 40 (36, 45) | 40 (36, 45) | 20 (17, 22) | 2.1 (1.4, 2.6) |
| |V| = 44, |R| = 37 | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 1.1 (0.8, 1.4) |
| MEHRA | FindConduits | 27 (21, 33) | 27 (21, 33) | 11 (9, 13) | 0.5 (0.3, 0.6) |
| |V| = 24, |R| = 19 | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.7 (0.5, 1.0) |
| MILDEW | FindConduits | 80 (69, 92) | 80 (69, 92) | 20 (18, 25) | 0.7 (0.5, 1.0) |
| |V| = 35, |R| = 32 | FindTrClust | 2 (1, 2) | 2 (1, 2) | 4 (3, 4) | 2.5 (1.8, 3.3) |
| PATHFINDER | FindConduits | 60 (42, 88) | 60 (42, 88) | 12 (11, 14) | 7.7 (5.9, 9.4) |
| |V| = 109, |R| = 28 | FindTrClust | 2 (1, 2) | 2 (1, 2) | 2 (1, 2) | 4.0 (3.1, 4.8) |
| SACHS | FindConduits | 3 (2, 4) | 3 (2, 4) | 2 (2, 3) | 0.1 (0.0, 0.1) |
| |V| = 11, |R| = 5 | FindTrClust | 1 (1, 1) | 1 (1, 1) | 1 (1, 1) | 0.2 (0.1, 0.2) |
| SANGIOVESE | FindConduits | 27 (22, 40) | 27 (22, 40) | 9 (8, 10) | 0.4 (0.3, 0.5) |
| |V| = 15, |R| = 12 | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 1.5 (1.1, 1.9) |
| WATER | FindConduits | 17 (12, 23) | 17 (12, 23) | 12 (10, 14) | 0.8 (0.6, 1.0) |
| |V| = 32, |R| = 22 | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 1.9 (1.4, 2.4) |
| WIN95PTS | FindConduits | 107 (99, 114) | 107 (99, 114) | 33 (30, 35) | 5.5 (3.9, 6.9) |
| |V| = 76, |R| = 57 | FindTrClust | 2 (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 (). 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 and the number of vertices in the restriction set . 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.
| Graph | Algorithm | All clusters | Invariant clusters | Reduction | Time (s) |
| ALARM | FindConduits | 25 (22, 28) | 18 (14, 23) | 11 (9, 12) | 0.3 (0.3, 0.5) |
| ALARM | FindTrClust | 2 (1, 3) | 2 (1, 3) | 2 (1, 3) | 0.4 (0.3, 0.4) |
| , | |||||
| ARTH150 | FindConduits | 37 (30, 43) | 31 (24, 39) | 15 (13, 17) | 9.4 (6.7, 12.7) |
| ARTH150 | FindTrClust | 2 (1, 4) | 2 (1, 4) | 2 (1, 3) | 2.4 (1.6, 2.8) |
| , | |||||
| BARLEY | FindConduits | 69 (63, 76) | 46 (37, 57) | 18 (16, 20) | 0.8 (0.6, 1.2) |
| BARLEY | FindTrClust | 2 (1, 4) | 2 (1, 3) | 3 (1, 5) | 1.0 (0.9, 1.1) |
| , | |||||
| CHILD | FindConduits | 20 (13, 30) | 16 (9, 26) | 4 (3, 5) | 0.1 (0.1, 0.1) |
| CHILD | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 0.2 (0.2, 0.3) |
| , | |||||
| ECOLI70 | FindConduits | 16 (14, 21) | 15 (11, 20) | 9 (8, 11) | 1.6 (1.1, 2.1) |
| ECOLI70 | FindTrClust | 1 (1, 2) | 1 (1, 2) | 1 (1, 2) | 0.9 (0.6, 1.2) |
| , | |||||
| HAILFINDER | FindConduits | 148 (121, 164) | 71 (56, 91) | 23 (21, 26) | 0.9 (0.7, 1.2) |
| HAILFINDER | FindTrClust | 4 (3, 6) | 4 (3, 5) | 8 (5, 10) | 1.5 (1.1, 1.7) |
| , | |||||
| HEPAR2 | FindConduits | 35 (27, 42) | 24 (18, 32) | 11 (10, 13) | 1.1 (0.9, 1.5) |
| HEPAR2 | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 0.9 (0.7, 1.2) |
| , | |||||
| INSURANCE | FindConduits | 33 (25, 45) | 25 (16, 38) | 9 (7, 10) | 0.3 (0.3, 0.5) |
| INSURANCE | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.5 (0.4, 0.6) |
| , | |||||
| MAGIC-IRRI | FindConduits | 75 (64, 86) | 54 (43, 70) | 21 (18, 24) | 1.5 (1.2, 1.9) |
| MAGIC-IRRI | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 0.7 (0.6, 0.7) |
| , | |||||
| MAGIC-NIAB | FindConduits | 33 (30, 37) | 26 (22, 30) | 13 (12, 17) | 0.8 (0.7, 1.0) |
| MAGIC-NIAB | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.4 (0.3, 0.4) |
| , | |||||
| MEHRA | FindConduits | 24 (19, 31) | 15 (11, 20) | 8 (7, 10) | 0.3 (0.3, 0.4) |
| MEHRA | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.5 (0.4, 0.6) |
| , | |||||
| MILDEW | FindConduits | 72 (59, 90) | 37 (27, 51) | 17 (14, 19) | 0.4 (0.3, 0.5) |
| MILDEW | FindTrClust | 1 (1, 2) | 1 (1, 2) | 1 (1, 4) | 1.1 (0.9, 1.3) |
| , | |||||
| PATHFINDER | FindConduits | 35 (28, 44) | 34 (27, 43) | 10 (9, 11) | 2.9 (2.2, 3.7) |
| PATHFINDER | FindTrClust | 1 (1, 2) | 1 (1, 2) | 1 (1, 2) | 1.3 (1.0, 1.6) |
| , | |||||
| SACHS | FindConduits | 3 (2, 4) | 2 (2, 4) | 2 (2, 3) | 0.1 (0.0, 0.1) |
| SACHS | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 0.1 (0.1, 0.1) |
| , | |||||
| SANGIOVESE | FindConduits | 24 (17, 33) | 15 (9, 23) | 8 (6, 9) | 0.2 (0.1, 0.2) |
| SANGIOVESE | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.6 (0.5, 0.8) |
| , | |||||
| WATER | FindConduits | 8 (6, 12) | 8 (5, 12) | 7 (5, 10) | 0.5 (0.4, 0.6) |
| WATER | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.8 (0.7, 1.0) |
| , | |||||
| WIN95PTS | FindConduits | 88 (81, 94) | 61 (50, 73) | 25 (23, 28) | 2.3 (1.7, 3.3) |
| WIN95PTS | FindTrClust | 1 (1, 2) | 1 (1, 2) | 2 (2, 4) | 1.1 (0.9, 1.4) |
| , |
Table 4. Comparison of FindConduits and FindTrClust in all graphs with moderate bidirected edges (). 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 and the number of vertices in the restriction set . 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.
| Graph | Algorithm | All clusters | Invariant clusters | Reduction | Time (s) |
| ALARM | FindConduits | 26 (23, 29) | 23 (18, 27) | 12 (11, 14) | 0.8 (0.6, 1.0) |
| , | FindTrClust | 3 (2, 4) | 2 (2, 4) | 3 (2, 4) | 1.1 (0.9, 1.3) |
| ARTH150 | FindConduits | 42 (36, 51) | 39 (31, 48) | 17 (15, 18) | 7.8 (5.8, 10.6) |
| , | FindTrClust | 3 (2, 4) | 3 (2, 4) | 2 (2, 3) | 2.8 (2.1, 3.2) |
| BARLEY | FindConduits | 75 (68, 82) | 62 (50, 73) | 21 (19, 24) | 1.8 (1.3, 2.4) |
| , | FindTrClust | 3 (2, 5) | 3 (1, 5) | 5 (3, 6) | 3.3 (2.5, 3.9) |
| CHILD | FindConduits | 23 (15, 33) | 20 (13, 31) | 5 (4, 6) | 0.2 (0.1, 0.3) |
| , | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 0.4 (0.3, 0.5) |
| ECOLI70 | FindConduits | 19 (16, 28) | 19 (15, 27) | 11 (9, 12) | 1.5 (1.1, 1.9) |
| , | FindTrClust | 2 (1, 2) | 2 (1, 2) | 2 (1, 2) | 1.0 (0.8, 1.2) |
| HAILFINDER | FindConduits | 147 (122, 161) | 97 (79, 119) | 26 (24, 29) | 0.7 (0.6, 0.9) |
| , | FindTrClust | 5 (4, 7) | 5 (4, 7) | 10 (7, 13) | 1.5 (1.1, 1.7) |
| HEPAR2 | FindConduits | 39 (30, 45) | 32 (25, 41) | 13 (12, 15) | 0.8 (0.6, 2.4) |
| , | FindTrClust | 1 (1, 1) | 1 (1, 1) | 1 (1, 4) | 0.8 (0.6, 2.6) |
| INSURANCE | FindConduits | 38 (29, 55) | 34 (22, 52) | 10 (8, 12) | 0.6 (0.4, 0.8) |
| , | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.9 (0.7, 1.1) |
| MAGIC-IRRI | FindConduits | 84 (71, 95) | 70 (57, 88) | 25 (21, 27) | 2.4 (1.9, 3.0) |
| , | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 1.3 (1.0, 1.6) |
| MAGIC-NIAB | FindConduits | 35 (31, 39) | 31 (26, 36) | 16 (13, 20) | 1.4 (1.1, 1.7) |
| , | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.7 (0.6, 0.8) |
| MEHRA | FindConduits | 25 (20, 32) | 20 (15, 27) | 10 (8, 11) | 0.5 (0.4, 0.6) |
| , | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.8 (0.6, 1.0) |
| MILDEW | FindConduits | 76 (63, 91) | 54 (41, 71) | 18 (17, 22) | 0.6 (0.5, 0.8) |
| , | FindTrClust | 1 (1, 2) | 1 (1, 2) | 3 (1, 4) | 1.8 (1.5, 2.4) |
| PATHFINDER | FindConduits | 42 (34, 59) | 42 (34, 58) | 11 (10, 12) | 2.6 (2.1, 3.4) |
| , | FindTrClust | 1 (1, 2) | 1 (1, 2) | 1 (1, 2) | 1.2 (1.0, 1.6) |
| SACHS | FindConduits | 3 (2, 4) | 3 (2, 4) | 2 (2, 3) | 0.0 (0.0, 0.1) |
| , | FindTrClust | 1 (0, 1) | 1 (0, 1) | 1 (0, 1) | 0.1 (0.1, 0.1) |
| SANGIOVESE | FindConduits | 25 (20, 35) | 21 (14, 28) | 9 (7, 10) | 0.2 (0.2, 0.3) |
| , | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 0.8 (0.6, 1.1) |
| WATER | FindConduits | 11 (8, 17) | 11 (7, 17) | 9 (7, 12) | 0.6 (0.4, 0.8) |
| , | FindTrClust | 0 (0, 0) | 0 (0, 0) | 0 (0, 0) | 1.3 (1.0, 1.6) |
| WIN95PTS | FindConduits | 94 (87, 101) | 80 (69, 90) | 28 (26, 31) | 2.1 (1.6, 2.9) |
| , | FindTrClust | 2 (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 (). 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 and the number of vertices in the restriction set . 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]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]Bayesian Network Repository. Bayesian network repository. https://www.bnlearn.com/bnrepository/, 2026. Accessed May 18, 2026.
- [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]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]F. Madaleno, P. Misra, and A. Markham. Coarsening causal DAG models. arXiv preprint arXiv:2601.10531, 2026.arxiv.org/abs/2601.10531
- [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]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]R Core Team. R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. https://www.R-project.org/, 2026.
- [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
- [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.
- [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
- [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
- [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.
- [16]T. S. Verma. Graphical aspects of causal models. Technical report, Department of Computer Science, University of California, Los Angeles, 1993. R-191.
- [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


