Characterization and Learning of Causal Graphs from Hard Interventions
Authors: Zihan Zhou
Muhammad Qasim Elahi
Murat Kocaoglu
Venue: NeurIPS 2025 poster ()
Keywords: Markov Equivalence Class
Bayesian Network
Causal Discovery
Primary area: probabilistic_methods
TL;DR: We introduce a graphical representation to characterize I-Markov Equivalence Class and propose a learning algorithm to integrate multiple datasets from hard interventions.

Abstract: A fundamental challenge in the empirical sciences involves uncovering causal structure through observation and experimentation. Causal discovery entails linking the conditional independence (CI) invariances in observational data to their corresponding graphical constraints via d-separation. In this paper, we consider a general setting where we have access to data from multiple experimental distributions resulting from hard interventions, as well as potentially from an observational distribution. By comparing different interventional distributions, we propose a set of graphical constraints that are fundamentally linked to Pearl's do-calculus within the framework of hard interventions. These graphical constraints associate each graphical structure with a set of interventional distributions that are consistent with the rules of do-calculus. We characterize the interventional equivalence class of causal graphs with latent variables and introduce a graphical representation that can be used to determine whether two causal graphs are interventionally equivalent, i.e., whether they are associated with the same family of hard interventional distributions, where the elements of the family are indistinguishable using the invariances from do-calculus. We also propose a learning algorithm to integrate multiple datasets from hard interventions, introducing new orientation rules. The learning objective is a tuple of augmented graphs which entails a set of causal graphs. We also prove the soundness of the proposed algorithm.

Characterization and Learning of Causal Graphs from Hard Interventions
Zihan Zhou'
Muhammad Qasim Elahi"
Department of Computer Science
School of Electrical and Computer Engineering Purdue University
Johns Hopkins University edu edu
elahi0@ purdue.edu
Murat Kocaoglu
Department of Computer Science Johns Hopkins University
mkocaoglu@jhu. edu
Abstract
A fundamental challenge in the empirical sciences involves uncovering causal structure through observation and experimentation. Causal discovery entails link- ing the conditional independence (CI) invariances in observational data to their corresponding graphical constraints via d-separation. In this paper, we consider a general setting where we have access to data from multiple experimental distribu- tions resulting from hard interventions, as well as potentially from an observational distribution. By comparing different interventional distributions, propose set of graphical constraints that are fundamentally linked to Pearl's do-calculus within the framework of hard interventions. These graphical constraints associate each graphical structure with set of interventional distributions that are consistent with the rules of do-calculus. We characterize the interventional equivalence class of causal graphs with latent variables and introduce a graphical representation that can be used to determine whether two causal graphs interventionally equiva- lent, i..., whether they are associated with the same family of hard interventional distributions, where the elements of the family are indistinguishable using the invariances from do-calculus. We also propose a learning algorithm to integrate multiple datasets from hard interventions, introducing learning objective is a tuple augmented graphs which entails a set of causal graphs. We also prove the soundness of the proposed algorithm.
orientation rules. The
Introduction
Understanding the behavior complex systems through their causal relationships is a fundamental problem in science. Researchers collect data and perform experiments to analyze how specific phenomena arise or to investigate the structure and function of underlying systems, whether social, biological, economic [Hünermund and Bareinboim 2023 Petersen al. 2024 Sanchez et al. 2022]. Causal discovery focuses on identifying causal re relationships from both observational and interventional data [Pearl] 1995 Spirtes et al. [000] Peters al.) 2017). A widely used approach for causal discovery models the underlying system as causal graph, represented by directed acyclic graph (DAG), where nodes denote random variables and directed edges between nodes (A - B)
signify causal relations [Pear| 2009
Spirtes et al. 2001].
Equal Contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Causal discovery involves deriving constraints from data to infer the underlying causal graph. How- ever, in practice, these constraints are rarely enough to identify the exact causal graph. Instead, they typically define set of graphs consistent with the data, collectively referred to as an equivalence class (EC) [Ali et al. 2012 Meek] 2013a]. Conditional independence (CI) relations are the primary markers of the underlying causal structure and are used to define an equivalence class. These fundamental probabilistic invariances have been widely explored within the framework of graphical models [Pearl 1995 Peters et al., 2017]. Conditional independencies (CIs) are a powerful tool and serve as the foundation for many causal discovery algorithms, e.g., PC and FCI [Spirtes et al. 2001].
When only observational data is available, the Markov equivalence class (MEC) comprises all causal graphs that exhibit the same set of conditional independences (CIs) among the measured variables. as defined by the d-separation criterion [Verma and Pearl 1992]. The availability of interventional (experimental) data allows us to reduce the size of the equivalence class, potentially facilitating the recovery of the causal graph [Hauser and Bühlmann] 2012 Kocaoglu et al., 2017). Hard and soft interventions are two methods for manipulating variables. A hard intervention directly sets a variable to a fixed value, removing natural dependencies, while soft intervention alters the mechanism through which the parents of a variable influence the target variable. While soft interventions are more common in biology as, e.g., in gene knockout experiments [Meinshausen al., 2016 since we do not have precise control of mechanisms, in computer systems hard interventions are feasible and have been used for learning causal relations, e.g., in microservice architectures (Wang et al., 2023).
Although a hard intervention can be seen as a special case of soft one, it can be more informative in the presence of latent variables in many cases. For instance, consider the causal graph D2 = {X + Z > Y, Z ++ Y}. We use the bidirected edge to represent latent confounder between two nodes. A hard intervention on Z breaks the inducing path (X, Z, Y), which implies that after a hard intervention on Z, the variables and Y are no longer dependent. In contrast, in the case of a soft intervention, the incoming edges to Z are not removed, so soft intervention will not break the inducing path. It is also worth noting that hard interventions may change d-separation statements non-locally, as seen here between X, Y after do(z), which the existing representations of interventional Markov equivalence classes cannot encode. Now consider another graph D2 = {X - Z + Y, Z +> Y.X + Y.. which is the same Dj with the additional edge X + Y. With access to hard intervention on Z, we can distinguish these graphs; however, with a soft intervention, one cannot differentiate between them. This example demonstrates that hard interventions can be more informative in the presence of latent variables and narrow down the search space more effectively than soft ones. We conducted empirical experiments in Appendix Fo to compare hard and soft interventions in learning the causal graph with latents. The results verify this observation. A fundamental question how can we extract as much causal knowledge as possible from a collection of hard interventional datasets. To the best of our knowledge, this problem has been open before this work.
Motivated by this, our paper considers general setting where multiple experimental distributions resulting from hard interventions are available alongside (optionally) observational distributions. Prior work has focused on characterizing the Z-Markov equivalence class through distributional invariances both within and across a set of observational and interventional distributions [Hauser and Bühlmann 2012 Yang et al. 2018). The closest work ours is Kocaoglu et al.) [2019]. However, they deal with soft interventions, whereas we consider a setting where experimental data comes from hard interventions. This can lead to more invariances that can be inferred from the experimental data compared to the soft intervention case, which can potentially further reduce the size of Z-Markov equivalence class. However, the existing work cannot utilize these additional invariances.
We propose using do-constraints with hard interventions, a concept that emerges from comparing observational and experimental distributions, extending Pearl's 's do-caleulus to uncover new structural insights in causal graphs Kocaoglu et al., 2019 Jaber et al., 20200. They emerge as the converse of the causal calculus developed by Pearl| 1195). These constraints, distinct from traditional conditional independence (CI) relations, are derived by contrasting distributions such as (()| and P(y|do through a do-see test. When differences are detected, they reveal open backdoor paths in the graph, aiding structure learning. We leverage F-nodes, introduced by Pearl, to explicitly encode intervention effects in augmented graphs (Pearl [993]. These nodes make the effects of interventions visible within the graph, enabling the application of do-calculus tests and capturing key structural knowledge
IIduucin paths are paths between non- adjacent variables that cannot be blocked by conditioning on any subset of observed variables. They only exist in the presence of unobserved confounders.

---

such as the existence of a backdoor path from X to Y when Fx is not d-separated from Y given X. Such augmented representations, widely used in inference and identification, highlight the utility of do-constraints alongside CI relations for learning causal structures Yang et al.. 2018, Kocaoglu et al. 2019 Mooij et al. 2020
We say that a set of interventional distributions satisfies the I-Markov property with respect to a graph if these distributions adhere the invariance constraints imposed by the causal calculus rules of that graph. We first extend the causal calculus rules to operate between arbitrary sets of hard interventions. We say that two causal graphs, D1 and D2. are Z I-Markov equivalent if the set of distributions that are Z-Markov to both D1 and D2 is the same. Using the augmented graph, we identify graphical condition that is both necessary and sufficient for two Causal Bayesian Networks (CBNs) with latents to be Z-Markov equivalent under the framework of hard interventions. Finally, we propose a sound algorithm for causal discovery from hard-interventional datasets. Our main contributions can be summarized as follows:
We propose a characterization of Z-Markov equivalence between two causal graphs with latent variables for a given intervention set Z, based on generalization of do-calculus under hard interventions.
We provide graphical characterization of I M-rkko equivalence for causal graphs with latent variables under the framework of hard interventions.
We introduce learning algorithm for inferring the graphical structure using a combination of different interventional data, while utilizing the corresponding new constraints. This procedure includes a new set of orientation rules, and we formally prove its soundness.
We conducted experiments (Appendix F to compare the size of T-Marko equivalence class under hard and soft interventions to show that hard interventions on average provide more information about the causal graph.
2 Background and Related Works
In this section, we briefly describe related background knowledge and notations in this paper. Throughout this paper, we use upper case letters to denote variables, lower case letters to denote realizations, and bold letters for sets.
Causal Bayesian Network (CBN): Given set of variables V. P(v) represents the joint distribution for V = v. A hard intervention do(X = x) refers to setting a subset X C V to constants x. It breaks the causal relationship between the intervened variables and their parents. The interventional distribution is Px(v) (v). Let P denote the tuple of all interventional distributions for all X C V. Then, a directed acyclic graph (DAG) D = (V, E) is said to be a causal Bayesian network compatible with P if and only if, for all X S V Px() II (xV) P(u; ((u,) for all v consistent with x, and where pa, the set of parents of V; in D. D is said to be causal if it satisfies this condition. V[D) and F denote the set of all nodes and all edges of graph D respectively. Causal graphs entail specific conditional independence (CI) relationships among observable variables via d- d-separation statements. The d-separation serves as a criterion to determine whether a set of variables X is independent of another set Y, given Z.
If a causal graph has latent variables, it is denoted as D = (VUL, E) where V represents observable variables, L represents latent variables, and E denotes the edges. latent variable L is a common cause of two observable variables, we use a curved bidirected edge between the two children variables. Such a causal graph called Acyclic Directed Mixed Graph (ADMG). However, unlike causal graphs with sufficiency, the observed distribution is obtained by marginalizing L out as the Markovian condition does not hold in this case: P(v) = ΣL [ ((t.)pa.). Two causal graphs are called Markov equivalent if they encode the same set of CI statements over V.
Ancestral graphs: Ancestral graphs are a graphical representation for a class of Markov equivalent causal graphs with latent variables. In ADMG, X is an ancestor of Y if there is directed path from X to Y X is a spouse of Y if X ++ Y is present. An inducing path relative to Z is path on which every non-endpoint vertex T & Z collider on the path and every collider is an
We follow the convention that node ancestor of itself.
3

---

ancestor of one of the endpoints. A directed path is cycle if it starts and ends at the same node. An almost directed cycle can be constructed by changing an arrowtail an arrowhead in a cycle. An ADMG is ancestral if it does not contain any almost directed cycle. It is maximal if there is no inducing path (relative to the empty set) between any pair of non-adjacent vertices. It is called a Maximal Ancestral Graph (MAG) if it is both maximal and ancestral [Richardson and Spirtes 2002]. In Zhang [2008a], the authors show how to uniquely construct a MAG for causal graph with latents L, E), such that all the (conditional) independence statements and ancestral relationships over V are preserved. Such CI statements are called m-separation statements in ADMGs.
D
In graph D, triple (X, Y, Z) is unshielded if X, Y are adjacent and Y, Z are adjacent while X, Z are not adjacent. If both edges are into Y. then it is an unshielded collider. A path between X and Y. p (X, ...., W. Z, Y), is discriminating path for Z if (1) p includes at least three edges; (2) Z is non-endpoint node on p. and is adjacent to Y on P: and (3) X is not adjacent to Y, and every node between X and Z is collider on and is parent of Y. Two MAGs are Markov equivalent if and only if (1) they have the same skeleton; (2) they have the same unshielded colliders; and (3) if path p is discriminating path for Z in both MAGG, then Z. is a collider on the path in one graph if and only if it is a collider on the path in the other. A partial ancestral graph (PAG) represents a Markov equivalence class of MAGs. It can be learned from CI statements over the observable variables under faithfulness. When observational data is provided, FCI algorithm is commonly used algorithm to recover the PAG and is proved to be sound and complete Zhang [0088b]
Related works: There are many works in the literature [Chickering, 2002 Hyttinen et al., 2013 Eberhardi 2007, Shanmugam al., 2015 Kocaoglu et al.) 2017] related to learning the causal structure from a combination of observational and interventional data. Under the assumption of sufficiency. Hauser and Bühlmann (2012] 2014) introduced the Markov equivalence characterization. Yang et al.] [018] further showed that the same characterization can be used for both hard and soft interventions. More works aimed at the cases where latents are present in the graph. If only observational data is available, Zhang [2008b] showed the property and proposed the sound and complete FCI algorithm to learn PAG. Spirtes et al. [200T], Colombo
Colombo et al. (2012). Spirtes et al.) [1991]. Colombo et al. (2014). Ghassami et al. [2018]. Kocaoglu et al. [017]] proposed FCI Farivariant
algorithms under different settings. Kocaoglu et al. [2019] introduced a characterization for I- Markov equivalence class for soft interventions using augmented graphs with F node and proposed
an FCI-variant algorithm learn it. Following this, Jaber et al. [2020] characterized the 3M-MEC for unknown soft interventions and proposed a learning algorithm. [L et al. [2023) introduced the S-Markov property and learning algorithm when data from multiple domains are provided.
For disjoint sets of variables X, Y, Z, a CI statement 'X is independent of Y conditioning on Z' is represented by X IL Y Z. Similarly, in causal graph D, the d-separation statement 'X is independent of Y conditioning on Z in graph DD is denoted as (X ILI Y/Z).. A set of interventions is I 2V where 2V the power set of For two interventions I.J I, the symmetric difference is IAJ = (I) J) U (J \ I). Dz/Dx is the graph obtained by removing all the edges into/out of X from D. For Px xx) (Z)) is the subset of Y that are not ancestors of Z in the graph Px. In a PAG, a circle mark in an edge Xo- Y can be either an arrowtail or an arrowhead which is not determined. A star mark in edge X Y is used wildcard which can be circle, arrowhead, or arrowtail. We assume that there is no selection bias.
Notations:
3 Combining Experimental Distributions under Do-Calculus
One of the most renowned contributions to causal inference is the development of do-calculus (also known as causal calculus) [Pear] 1995 2009]. Do-calculus is set of three inference rules that enable the transformation of distributions associated with causal graph. It leverages the graphical structure to determine when and how interventions can be adjusted or "removed" from expressions. In the context of hard interventions, the theorem is stated as f3l
Theorem 3.1. (Theorem 3 in Pearl (1995)). )). Let D = (V U.L E) be causal graph. Then the following statements hold for any distribution that is consistent with D
Rule 1 (see-see): For any X C V and disjoint Y. Z, W VV
'Here we put condition on = for Rule 2. While this is redundant, we aim to show its clear connection with the corresponding F' node d- d-separations in the augmented graphs (see Section 4. which requires conditioning.

---

Px(y|w,z) Px(vlw), If TT ZJW, X in Dx
Rule 2 (do-see): For any disjoint X, Y. Z C V and W C V
(ZUU) (ZUY)
Px,xyy/,,2 w, ( (tyl,,z)) 2), Y Z W, X X
Rule 3 (do-do): For any disjoint X, Y, Z S V and W W (ZUY)
[/) (x(r/w), Y 1 WW X in D XZ(W)
where Z(W) C Z are non-ancestors of W in Dx
Similar to the observations in Kocaoglu et al. [019 that the converse of the rules can be utilized to derive insights of the graph structures, here we also need a set of statements for hard interventions. With soft intervention, the interventional graph remains the same as causal relationship is broken by soft interventions. However, hard interventions induce changes to the causal graph, making it potentially more informative in learning the graph structure. The intuition is that with hard interventions, the causal graph becomes more sparse and thus more do-invariance statements can be found to constrain the graph. Accordingly, we show the following Proposition that characterizes the graph conditions from the invariance of two arbitrary intervention sets. Throughout the paper, for pair of targets I, J and conditioning set W, define the following useful sets: K IAJ, K₁ K KJ = K K, KWW, Ky K
W. R₁ = R. K1, RJ RoK,,
Proposition 3.2. (Generalized do-calculus for hard interventions). Let D = (VUL, , E) be causal graph with latents. Then, the sollowing holds for any tuple of hund-inieeventiinnal distributions (Pi)Iez consistent with D, where I 2
Rule 1 (conditional independence); For any I IST V and disjoint Y,Z, W (V)
Pr(y/w, z) Pi(y[w) if Y Z|W; I in DI Rule 2 (do-see): For any I, S V and disjoint Y, W VEVVV K. where == IAJ
Pr(y/w, k) (y w, k) Pa(y/w,k) k), if (Y IL K, W. Dr.K A(Y IL Ki W J) DJKS
Rule 3 (do-do): For any I C V and disjoint Y, W.W CVV K, where IAJ Pr(ylw) = Pr. = Pı(ylw). if (Y IL K, W, 1 DTTKYWW A TL K, G.W.J. J.KT(WT
Rule 4 (mixed do-see/do-do): For any I, S V and disjoint Y, W C V, where K == IAJ
Pi(y/w) (y/
Py(l)w), if (Y IL R,/W, D.D.NYWI (Y T
W, W. 1) D AY 1 R1 W J.J. A (Y TL Wi/W,J)D
Note that Rule 2 and are special cases of Rule 4. We present them to make the connection to standard causal calculus rules more explicit. In the following sections, we will show how the generalized rules can be crucial in characterizing and learning the Z-Markov Equivalence Class (I-MEC).
4 Z-Markov Equivalence Class
In this section, we will characterize the graphical conditions for interventional Markov equivalence class. First of all, we start by introducing the definition of interventional Markov equivalence based on the new do-constraint rules.
Definition 4.1. Consider the tuples of absolutely continuous probability distributions (Pr)rez over set of variables V. A tuple (ft)Ie satisfies the Z-Markov property with respect to a causal graph D (VU L, E) if the following holds for disjoint Y, Z, W C V:
1. For I E I: Pı(vlw.z) = Pi(v(w) if Y IL in Dj
2. For IJJ I: Pi(ylw) Py(ylw) if (Y IL
R, W. I I) Dirngwss (Y TT
WJ W A (Y TL R, J.W A (Y TL Wi/W. J)D,
The set of all tuples that satisfy the I-Markov property with respect D are denoted by Pz(D, V).
5

---

The two conditions of M-Markov property correspond to the first Rule in Theorem 3.1 and Rule 4 in Proposition 3.2 respectively. When I i.e. we only have access to observational distribution, this definition aligns with the well-known definition of Markov equivalence. It only implies the first condition on the observational distribution P(V). Accordingly, two causal graphs are said to be I-Markov equivalent if they induce the same constraints to the interventional distribution tuple which we formalize as follows:
Definition 4.2. Given two causal graphs D1= (V U L1, E1) and D2 = UV E2), and a set of intervention targets I _ 2", D and D2 are Z-Markov equivalent if PI(1,, V) PP(22, V).
The challenge of checking the Z-Markov property in Definition 4.1 involves checking multiple graph conditions in different graph mutilations of DD. In order to construct a more compact representation of D that captures all the graph conditions, we construct the augmented pair graph defined as follows
Definition 4.3 (Augmented Pair Graph). Given causal graph D (V L, E) and set of intervention targets I _ 2V, for a pair of interventions I.J E I, the augmented pair graph of D, denoted as (1 (D), is constructed as: Aug = where (=IJ is auxiliary node with the superscript representing the pair of intervention targets it refers to, E T) E(D,) E E'Dy], E = ((F(T.)) (5) with S as singleton.
E (UUUE)
In words, for each pair interventions I, J. we create the augmented pair graph by creating two copies of vertices V v(J) and adding the edges between the vertices with those in the corresponding interventional graphs Dr Dy. and then connecting the auxiliary node F' to all the nodes in the symmetric difference of I, J. We will omit the subscript for the graph and superscript for F node when the pair of interventions is clear from the context. This kind of construction has been proposed and used in the causality literature before [Eberhardt and Scheines) [007] Hauser and Bühlmann, 2012, Pearl 2009 Dawid 2002). The constructed augmented pairs allow us to test the m-separation statements as listed in Definition 4.1 without looking into mutilations of the original graph D. This is illustrated by the following Proposition.
Proposition 4.4. Given a causal graph D = (VUL, E) and a set of intervention targets I C 2V, for each pair of interventions I,J E I. K IAJ, and the corresponding augmented pair graph (1) (D) = (V(D) (V U (F(IJ)), ( U ( U.),E = {(F(I.), (LF()))))))s (S)tse we have the following equivalence statements:
For disjoint Y, R.WCT W.V.
(Y IL Z = (Y 11 ZWW, I, (()))) Aug
(I)
For disjoint Y, Z, W CV:
(Y TL RJ /, DD D WRT
(Y TL W W, D..
(F(LJ) I Y w Auga.a) (F(IJ) IL YJJ) J(d, w AuRa (D)
(Y IL J)
(Y TT WI/W W1. J)D
While the augmented pair graphs encode the same CI statements as the original graph, we know that different graphs may entail the same CI statements. To characterize the I-Markov equivalence, utilize the structure of Maximal Ancestral Graphs (MAGs). MAGG represent the Markov equivalence class of the original graph, making possible to compare and analyze equivalence classes without needing the full graph with latent variables. We introduce the following definition to construct a graph structure that captures the Z-Markov equivalence.
Definition 4.5. (Twin Augmented MAG). Given a causal graph D = (V U L, L, and a set of interventions C 2V, for each pair of intervention targets I, E I. K IAJ, and the corre- sponding augmented pair graph Aug(L,,) (D) = (V() U V(J) U (PUJ)) E U E U U = ((F(L.)), S)} SEK construct the MAGS of the augmented pair graph and denote it as
'Throughout this paper, 'We use the conventional steps to construct the MAG from an ADMG: For each pair of nodes X, Y. if X is Y's s ancestorldscenddansspour and there is an inducing path between them, we orient X + Y/X < Y/X ++
the superseript for (a set of) nodes to denote the interventional domain.
Y between them, otherwise they not adjacent.

---

MAG(Auu((.)) (D)). The twin augmented MAG, denoted as (w,n is constructed by adding edges (F,S() and (F, 1()) MAG(AugTT.n(D)) if for the singleton E S()) or s(J) is adjacent to F in (AG(A
Lemma 4.6. Twin augmented MAGs are valid MAGs.
The motivation of adding extra edges to F nodes comes from the fact that a query Y Y E E itself is not testable by comparing the invariances using PI, P3. It requires access to PL.J which is not necessarily given. Therefore, when the invariance does not hold, we cannot distinguish if F non-separable to Y in only one domain or in both domains. Next, we give graphical characterization of I-Markov equivalence between causal graphs using Definition 4.5
Theorem 4.7. Given two causal graphs D = (VUL, E1) and D2 = (V U L2, E2), and a set of intervention targets I _ 2V, DD and D2 are I-rarkov equivalent with respect to I if and only if for each pair of interventions I,J E I, Mi = (Di), M2 Twin
1. M1 and M2 have the same skeleton;
2. Mi and M2 have the same unshielded colliders;
3. Ifa path is discriminating path for node Y in both Mi and M2. then Y is collider on the path if and only if it is a collider on the path in the other.
To illustrate how we construct twin augmented MAGs step by step and compare I-Markov equivalence for two causal graphs, we construct the examples in Figure 2 in Appendix D
5 Z-Augmented MAG
We have demonstrated that the characterization of T-Markov equivalence between two causal graphs can be effectively captured using the proposed twin augmented MAGs. However, for an intervention target set of size k; we will have inspect all (5) such structures. This undesirable, as there exists only one underlying causal graph, and a more compact graph representation is preferred. Additionally. each twin augmented MAG encodes information for only a single pair of distributions, whereas we aim for an objective that encapsulates as much information as possible. To address these challenges, we propose new graphical structure defined as follows:
Definition 5.1 (I-augmented MAG). Given a causal graph (V, E) and a set of intervention targets I, construct all twin augmented MAGs Twin( for all J E I [I}. For each I I I, the Z-augmented MAG related to I is defined as ADgr(D,I) F= (F(LJ) ( (1) E {(F(I.), ("))))))))))))))))) (rata ( (D)) JEZA) In other words, it the graph union of each twin augmented MAG's induced subgraph on v u (F The Z-augmented MAG tuple is tuple of all Z-augmented MAGS (Z (Augr (D,T))
(V U F, E(T)) U E) where
Remark: The Z-augmented MAG Aug, (D, I) preserves all the m-separation statements in the domain of dI from the twin augmented MAGs with I in the intervention pair, Twin (D), [I)). The structure of (T) F within each twin augmented MAG is preserved in the Z-augmented MAG and is not affected by the other domains.
The constructed Z-augmented MAG tuple consists of only k: graphs, each of which encapsulates more information on the domain than twin augmented MAG. Specifically, the of ADMGs consistent with a twin augmented MAG in one domain is a superset of those consistent with an T-augmented MAG, as the Z-augmented MAG imposes stricter constraints of separations across other domains on the causal graph. Furthermore, the graphical conditions for two causal graphs to be Z-Markov equivalent, as stated in Theorem 4.7 remain valid when using the Z-augmented MAG. Hence, the Z-augmented MAG serves as the unified and compact graphical representation. Below, we illustrate the steps of how construct an I Z-augmented MAG.
In Figure| [] we demonstrate the construction of T-auumented MAGs with respect to three datasets: observational data and interventions on X and Z, i.e., I = (I, = 0, 12 = (X), = {2)). for the graph D, = XX Y + Z, Y Z]. For simplicity, we relabel the observational domain and the interventional domains for X and Z as 1, and 3, respectively, in the T-augmented MAGs shown in Figure [ Figure la Figure lb and Figure Ic are the twin augmented MAGs given
=
7

---

(0, (X.)), (0. (2)), and ((X), (2)) respectively, Based on the twin augmented MAGs, we construct the Z-augmented MAGs as shown in Figure Id Figure Ie and Figure If for the domains 0, {X} and {Z) respectively. Each Z-augmented MAG has the domain-speciff skeleton in the center with the F nodes around it indicating the invariances from other domains. The T-augmented MAGs entail the same information about the causal graph as the twin augmented MAGG, but they have much more compact representation. Proposition 5.2 5.2
shows the equivalence between the two representations.
X(I + 7(1) 3 y())
X
7(1)
(
X(2)
2
(
(7(12)
F(1.3)
F(2,3)
X22 Z22) - (())
X
Z
(
X
Z y
(a)
(win
(b) Twin(o,(2))D)) (Di)
(c) (win(x)),22))() (Di)
F(1.2)
F(1.3)
F(12)
F22,3)
F(1,3)
F(2,3)
X(I) 2 3 y())
(
((2)
V(2)
X
2 Y(3)
(d) Auga (DI,I)
(e) Aug(x) (Di,I)
( (ug (Di,
Figure 1: Illustration of the construction of T- augmented MAGs from twin augmented MAGs.
Figure Zalis the ground truth graph. The intervention targets are I [ = 0. = [x),13 {2}}.
(a), (b), and (c) are the twin augmented MAGs. (d), (c), and (f) are the Z- Z-augmented MAGs.
E2) and a set of intervention targets I C 2V, construct the T-augmented MAGs following the steps in Definition 5.1 of D1, D2. DD and D2 are I-Markov equivalent with respect to I if and only if for each I E I. Aug, I) and Aug, ID2 satisfy the 3 conditions in Theorem 4.7
Proposition 5.2. Given two causal graphs D = (VUL, -.
6 Learning by Combining Experiments
In this section, we develop an algorithm to learn the causal structure from given datasets. We do not assume that observational data given. Like any learning algorithm, faithfulness assumption is necessary to infer graphical properties from the distributional constraints. Accordingly, we assume that the provided interventional distributions
h-faithful the causal graph D, defined below.
Definition 6.1 (h-faithful). For a causal graph D = (V U L, E), tuple of distributions (Pi)eez E P(D, V) is called h-faithful to D if the converse for each of the conditions in Definition holds.
6.1 Learning Objective
Similar to the case when only observational data is available, it is hard to recover the whole graph in general. Therefore, the objective of the algorithm is learn graphical representation that demonstrates a set of I-Markov equivalent graphs. However, although the MAG of the augmented pair graphs proposed in Definition 4.5 denotes the ground truth, it is not always a fundamentally learnable structure from the distributions. To witness, let us consider the example in Figure 2c The edge (F, ((2) is not in MAG (ug (z)))) (D))). While we can learn only that from the distributions, Pone (vi w) स Pz Pz(y//) for some W C [X The inequality tells us that there is an inducing path from F to (1) or (2) which we cannot distinguish. Therefore, we proposed the twin augmented MAG to be able to capture the characterization for I-Markov equivalent graphs. Based on that, we construct the I-augmented MAG which is a more compact graphical structure and we use it as the learning objective. Accordingly, we define the I-augmented graph as follows.
Definition 6.2 (I-augmented Graph). Given a causal graph DD and set of intervention targets T, for each I E I, let M = Aug ( and let [M] be the set of Z-augmented MAGs corresponding to all the causal graphs that are I-Markov equivalent to D given I. For any I E I. the Z-augmented graph, denoted as (D, I), is a graph such that:
1. Gr has the same adjacencies as M, and any member of [M] does; and
8

---

2. every non-circle mark in (I) is an invariant mark in [M].
The Z-augmented graph tuple CT(D) is a tuple of all Z-augmented graphs (T (Gr(D,I) 1),,, We will omit the graph 'D or the intervention targets I when it is clear from the context for simplicity,
6.2 The Learning Algorithm
Algorithm 1 Main Causal Discovery Algorithm
Input: Intervention targets I, interventional distributions (Pt)tez, observable variables V Initialize L7 as an empty tuple, SepSet as an empty set;
Phase I: Initialize with Complete Graphs;
for I in I do
Duplicate V to create V run Algorithm on I, to get Fi as F nodes;
Put a circle edge (a-o) between every pair of X E v(I) and Y E V U.F
Phase II: Learning the Skeleton and Separating Sets;
for I in I do
E(Gr) + 0. V(G)) + yOUF
for in I do
Run Algorithm 3 on J, (Pt)Tez, V Fi to get & SepSela;
F((9)) <- ( JETTUE Ee, SepSet + SepSet U SepSely;
LI + + U Gr;
Phase III: Apply Orientation Rules to each 91, I E I;
Rule 0: For every unshielded triple (X y z in 9r. I E I, orient it as X00 x- y(
770 if Y & ( Z).
First apply Rule 0, then apply 7 FCI rules in Zhang 20088 together with the following 4 additional
rules to each Gr until none applies.
Rule 8: For any edge adjacent to F' node, orient the edge out of the F' node.
Rule 9: For any I E I, if X E I, x() (T) are adjacent in 91, then orient X o ( as
( + y1)
Rule 10: If (1) + ( in GI for some I I, replace the circle mark at (J) between (3) and
y(J) in GJ with arrowhead for any J E I (I).
Rule 11: In 91, I,J I, if IU (x), F(I.)) is adjacent to y Y &f J, then orient (1) * (1) as (1) + (!)
Output: T-augmented graph tuple Lr
We propose Algorithm [ to learn the Z-augmented graph tuple from the given experiments. The algorithm is inspired by the FCI algorithm. It learns the Z-augmented graph tuple Ly by iteratively recovering 91 for each I E I. In Phase I, it initializes the T-augmented graph 91 for each I E I. It puts circle edge between each pair of nodes X, Y E V. This constructs the domain-specific skeleton (1) under target I. After that, we attach the F nodes to the T-augmented graph using Algorithm[]an then put circle edge between any F node and any X V. In Phase II, we learn the skeleton for each Z-augmented graph G,. For each I E I, we retrieve the Z-augmented graph GI with all circle edges. Algorithm 3 tests if there separating set between any pair of nodes X, Y in Gr. If both nodes are non-F nodes, this can be tested by checking whether Pi w, ..) and (1 w). If one of them is an F node, this can be tested by checking the equality between Pi w) and PJ (y w) for Y E V. W.WCC V. Two F nodes are separated by default. If there is no such set W, we preserve the circle edge between X and Y. Otherwise, we remove the circle edge from GT. In Phase III, we apply orientation rules to learn more edges in the constructed T-augmented graphs. Notice that the skeleton G() in GI is a PAG; thus, the FCI rules are still applicable here We first use Rule 0 to orient all the unshielded triples by checking if the node in the center of the triple in the separating set of the two end nodes. After that, Algorithm | will repeatedly apply the FCI rules (Rules 5 to 7 are not included here as they are related to selection bias nodes) together with 4 new rules until none apply. Here we briefly describe the intuition of Rule 9, 10, and 11 (Rule 8 is sound by construction).
Rule 9 (Intervened nodes): The intuition of this rule is that since X is intervened, all the non- descendants of X become separable from X in Dj. Thus, Y has to be a descendant of X in Dj. Rule 10 (Consistency of Skeletons): The intuition of this rule stems from the fact that each skeleton is obtained from the same causal graph D. The ancestral relationship between any pair of nodes

---

cannot be reversed by hard interventions.
Rule 11 (Inducing Path): The intuition is that the nodes cannot be separated from Y & K. meaning there is an inducing path to y or y through x x If X intervened, the inducing path cannot go through X
To illustrate how each step in Algorithmmi Serriithm@oorrse works, we show an example in Appendix We establish the soundness of the proposed algorithm.
Theorem 6.3. Consider a set of interventional distributions (Pr)tez that are h-faithful to causal graph D (V L,, E), where I is a set of intervention targets. Algorithm 7 is sound, i.e., every adjacency and arrowheadhail orientation in the returned I I-augmented graph (1 I) is common for all L-augmented MAGs of D', 9I(D', I) for any D' which I-Markov equivalent to
7 Experiments
In this experiment, we compare the Z-MEC size under hard and soft interventions. For
Table I: Comparison of Z-MEC size under hard and soft interventions
n
Mean of Hard
Mean of Soft
Graph
Ratio
a given number of
2
2.03 + 0.15
2.93 = 0.29
Random
0.69 + 0.05
observable nodes n, we create an arbitrary ADMG by first con- structing a DAG and then adding bidirected edges to it. Then, we enumerate all ADMGs of the same size and check if the ADMG is in the I-MEC. For hard inter- ventions, construct the I-augmented MAGs according to the steps in Definition 5.1 and then check if Theorem 4.7 holds. For soft interventions, we refer to the construction in Definition 4 and criteria in Theorem 2 in Kocaoglu et al. [019]. We count the number of ADMGs that are in the I-MEC and take average over 50 random ADMGs and compute the standard error. The results are shown in Table [ 'Complete' means the DAG is complete while 'Random' means the DAG has density of 0.5. is obvious that on average, the size of I-MEC is smaller under hard interventions and the ratio tends to decrease while increases, meaning hard interventions become more powerful for larger graphs. We can only enumerate the ADMGs for small graphs as the total number grows super-exponentially with n. For the experiment details and additional experiments, see Appendix
2,37 + 0.12
3.67 + 0.22
Complete
0.65 0.05
3
19.50 +
30.57 + 4.36
Random
0.64 + 0.11
3
14.03 + 2.69
24.70 + 4.12
Complete
0.57 + 0.05
4
677.13
227.72
1218.83 + 361.83 .83
Random
0.56 + 0.18
4
721.37
1 276.36
1529.57 1 368.68
Complete
0.47 0.07
8 Conclusion
We address the challenge of learning the causal structure underlying a phenomenon of interest using combination of several experimental data. Different from Kocaoglu al.) [2019]. we study the problem under hard interventions. The motivation comes from the observation that hard interventions provide more information about the causal graph than soft ones. We verify the observation through empirical experiments that compare the Z-MEC size under hard and soft interventions (Appendix F). Our approach builds on generalization of the converse of Pearl's do-calculus, which introduces new tests that can be applied to data. These tests translate into structural constraints. We define Z-MEC based on these criteria (Definition 1 and provide a graphical characterization for the equivalence of two causal graphs (Theorem 4.7) using the proposed twin augmented MAG structure (Definition 4.5). To construct unified graphical representation that is closer to the ground truth ADMG, we combine the twin augmented MAGs into an Z-augmented MAG (Definition 5.1) and show the equivalence of the two representations (Proposition (.2). Finally, we propose an algorithm (Algorithm T to learn the interventional equivalence class represented by the T-augmented graphs (Definition 6.2)) from data, incorporating novel orientation rules. We also prove the soundness of the proposed learning algorithm (Theorem 6.3) The proofs can be found in Appendix B
Acknowledgement
This research has been supported in part by NSF CAREER 2239375, IIS 2348717, Amazon Research Award, Adobe Research and Intuit.
10

---

References
Jayadev Acharya, Amnb Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy. Learn- ing and testing causal models with interventions. Advances in Neural Information Processing Systems, 31, 2018.
Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Intervention efficient algorithms for approximate learning of causal graphs. In Algorithmic Learning Theory, pages 151-184. PMLR, 2021.
Ayesha R Ali, Thomas S Richardson, Peter L Spirtes, and Jiji Zhang. Towards characterizing markov equivalence classes for directed acyelic graphs with latent variables. arXiv preprint vrXiv:/207.1365, 2012.
Anastasiya Belyaeva, Chandler Squires, and Caroline Uhler. Dei: learning causal differences between gene regulatory networks. Bioinformatics, 37(18):3077-3669 2021.
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33:21865-21877 2020.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554 2002.
Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high- dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages 294-321, 2012.
Diego Colombo, Marloes H Maathuis, et al. Order-independent constraint-based causal structure learning. J. Mach. Learn. Res., 15(1):3741-3782, 2014.
A Philip Dawid. Influence diagrams for causal modelling and inference. International Statistical Review, 10(2):161-189 2002.
Frederick Eberhardt. Causation and intervention. Unpublished doctoral dissertation, Carnegie Mellon University, 93, 2007.
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of science, 74(5):981-995, 2007.
Juan Gamella. gies: Python implementation of the greedy interventional equivalence search algo- rithm. https: //ggt/u//tttt com wwl.gaaaaallaggiiiie.. 2025. GitHub repository; commit e13f9a7; accessed 2025-10-23.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Kun Zhang. Learning causal structures using regression invariance. Advances in Neural Information Processing Systems, 30, 2017.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In International Conference Machine Learning, pages 1733. PMLR, 2018.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyelic graphs. The Journal of Machine Learning Research, 13(1): 1409-24644 2012.
Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926-939, 2014.
Christina Heinze-Demi Jonas Peters, and Nicolai Meinshausen. Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2):20170016, 2018.
Miguel A Hernán and James Robins. Using big data to emulate target trial when randomized trial is not available. American journal of epidemiology, 183(8):758-764 2016.
11

---

Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from heierogenooushoossatoonnyy data, Journal of Machine Learning Research, (19))) 1-53, 2020.
Paul Hünermund and Elias Bareinboim. Causal inference and data fusion in econometrics. The Econometrics Journal, page utad008, 2023.
Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Experiment selection for causal discovery. The Journal of Machine Learning Research, 14(1):04413077, 2013.
Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in neural information processing systems, 199555 2020.
Yiho Jiang and Bryon Aragam. Learning nonparametric latent causal graphs with unknown interven- tions. Advances in Neural Information Processing Systems, 11160468-601155 2023.
Saravanan Kandasamy, Amab Bhattacharyya, and Vasant Honavar. Minimum intervention cover of a causal graph. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2876-28855 2019.
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf. Michael C Mozer, Chris Pal, and Yoshua Bengio. Learning neural causal models from unknown interventions. arXiv preprint arXiv: 1910010705 2019.
Yaroslav Kivva, Ehsan Mokhtarian, Jalal Etesami, and Negar Kiyavash. Revisiting the general identifiability problem. In Uncertainty Artificial Intelligence, pages 1022-1030. PMLR, 2022.
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. Advances in Neurul Information Processing Systems, 30, 2017.
Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. Advances in Neural Information Processing Systems, 32, 2019.
David S Lee. Randomized experiments from non-random selection in us house elections. Journal of Econometrics, (2((2):75-697, 2008.
Adam Li, Amin Jaber, and Elias Bareinboim. Causal discovery from observational and interventional data across multiple environments. Advances in Neural Information Processing Systems, 36: 16942-16956, 2023.
Romain Lopez, Chr-shiistian Hütter, Jonathan Pritchard, and Aviv Regev. Large-scale differentiable causal discovery of factor graphs. Advances in Neural Information Processing Systems, 35: 19290-19303, 2022.
Alessandro Mascaro and Federico Castelletti. Bayesian causal discovery from unknown general interventions. arXiv preprint arXiv:2312.00509, 2023.
Christopher Meek. Causal inference and causal explanation with background knowledge. arXiv preprint arXiv:1302.4972 2013a.
Christopher Meek. Strong completeness and faithfulness in bayesian networks. arXiv preprint 102.4:130..4973, 2013b.
Nicolai Meinshausen, Alain Hauser, Joris M Mooij, Jonas Peters, Philip Versteeg, and Peter Bühlmann. Methods for causal inference from gene perturbation experiments and validation. Proceedings of the National Academy of Sciences, 113((7):7361-73368 2016.
Joris M Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of machine learning research, 21999);1-108, 2020.
J Pearl. Aspects of graphical models connected with causality. Proceedings of the 49th Session of the international Statistical Institute, Italy, pages 399-401, 1993.
12

---

Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669-66) 688, 1995.
Judea Pearl. Causality. Cambridge university press, 2009.
Ronan Perry, Julius Von Kügelgen, and Bernhard Schölkopf. Causal discovery in heterogeneous environments under the sparse mechanism shift hypothesis. Advances in Neural Information Processing Systems, 35:10004-10917 2022.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society Series B: Statistical Methodology, 78(5):947-1012, 2016.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Anne Helby Petersen, Claus Thom Ekstrøm, Peter Spirtes, and Merete Osler. Causal discovery and epidemiology: A potential for synergy. American Journal of Epidemiology, page kwae 101, 2024.
Thomas Richardson and Peter Spirtes. Ancestral graph markov models. The Annals of Statistics, 30 (4):962-1030, 2002.
2002.
James M Robins, Richard Scheines, Peter Spirtes, and Larry Wasserman. Uniform consistency in causal inference. Biometrika, 90(3):491-515, 2003.
Karen Sachs, Omar Perez, Dana Pe' er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721)) (::522))::23359 2005.
Pedro Sanchez, Jeremy Voisey, Tian Xia, Hannah Watson, Alison Q O'Neil, and Sotirios Tsaftaris. Causal machine learning for healthcare and precision medicine. Royal Society Open Science, 9(8):220638, 2022.
Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.
Atul Sharma, Pranjal Jain, Ashraf Mahgoub, Zihan Zhou, Kanak Mahadik, and Somali Chaterji. Lerna: transformer architectures for configuring error correction tools for short-and long-read genome sequencing. BMC bioinformatics, 23(1):25, 2022.
Peter Spirtes, Clark Glymour, and Richard Scheines. From probability to causality. Philosophical Studies: An International Journal for Philosophy in the Analytic Tradition, 64(1):1-36, 1991.
Peter Spirtes, Clark Glymour, and Richard Scheines. Cousation, prediction, and search. MIT press, 2001.
Peter L Spirtes, Christopher Meek, and Thomas S Richardson. Causal inference in the presence of latent variables and selection bias. arXiv preprint arXiv: 1302.4983, 2013.
Chandler Squires. causaldag: creation, manipulation, and learning of causal models, 2018. URL httpp:://ithhut com/ ahlerlabbcausaddar Version: <replace with PyPI ver or commit>, accessed 2025-10-23,
Sarah I. Taubman, Heidi I. Allen, Bill Wright, Katherine Baicker, and Amy N Finkelstein. Medicaid increases emergency-departmne use: evidence from oregon's health insurance experiment. Science, 343(61 (1826666))26332220 2688 2014.
Jin Tian and Judea Pearl. Causal discovery from changes. In Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence, pages 512-521, 2001.
Panagiotis Tigas, Yashas Annadani, Andrew Jesson, Bernhard Schölkopf, Yarin Gal, and Stefan Bauer. Interventions, where and how? experimental design for causal models at scale, Advances in neural information processing systems, 35:24130-24143, 2022.
13

---

Thomas Verma and Judea Pearl. An algorithu for deciding if a set of observed independencies has causal explanation. In Uncertainty artificial intelligence, pages 923-330. Elsevier, 1992.
Qing Wang. Jesus Rios, Saurabh Jha, Karthikeyan Shanmugam, Frank Bagehorn, Xi Yang, Robert Filepp. Naoki Abe, and Larisa Shwartz. Fault injection based interventional causal learning for distributed applications. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages
2023.
Yuhao Wang, Liam Solus, Karren Yang, and Caroline Uhler. Fermutation-basee causal inference algorithms with interventions. Advances in Neural Information Processing Systems, 30, 2017.
Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Polynomial-time algorithms for counting and sampling markov equivalent dags. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12198 12206, 2021.
Karren Yang, Abigail Katcoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal dags under interventions. International Conference on Machine Learning, pages 5541-5550. PMLR, 2018.
Jiji Zhang, Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9(7), 2008a.
Jiji Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17):8833-1888 2008b.
Zihan Zhou, Zijia Du, and Somali Chaterji. Kratos: Context-aware cell type classification and interpretation using joint dimensionality reduction and clustering, In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pages 2616-2633 2022.
Zihan Zhou, Muhammad Qasim Elahi, and Murat Kocaoglu. Sample efficient bayesian learning of causal graphs from interventions. Advances in Neural Information Processing Systems, 37: 9178-9206 2024.
14

---

Appendix Contents
Detailed Related Works
16
Proofs
16
B.1
Proof for Proposition 3.2
16
B.2
Proof for Proposition
19
3
Proof for Lemma
21
4
Proof for Theorem 4.7
21
B.5
Proof for Proposition
25
B.6
Proof for Theorem 6.3
25
Algorithms
28
Algorithm for Creating Nodes
28
Algorithm for Finding Separating Sets
28
Complexity Analysis
28
An example of the Construction of Twin Augmented MAGs
29
An Example of the Learning Process
30
Experiment Details
31
Enumerate All ADMGS
31
F2
Sample ADMGS
32
Comparison of Learning Objectives with Other Interventional Causal Discovery
Algorithms
33
Further Discussion
G.1
Assumptions
33
G.I.I
Positivity
33
1.2 Faithfulness
33
G.2
Comparison between Hard Interventions and Soft Interventions
34
G.3
Incompleteness of the Learning Algorithm
35
Limitations, Future Work, and Broader Impact
36
15

---

A Detailed Related Works
The learning process uses data constraints infer the causal diagram. However, these constraints often cannot uniquely identify the complete diagram. As a result, the analysis typically focuses on an equivalence class (EC) of causal diagrams that captures the constraints implied by the underlying causal system. When only observational data is available, such EC is called MEC. It characterizes causal graphs with the same set of d-separation statements over observable variables [Spirtes et al. 2001, Verma and Pearl 1992 SSpirtes et al.) 2013 Meek, 201 Under causal sufficiency, Hauser and Bühlmann| (2012 Yang et al. 20188 characterizes the Z-MEC. TTian and Pearl [200T] first considers the equivalence class under local changes. When there are latents under soft intervention with known targets. Kocaoglu et al. 2019] characterize the I-MEC while
Equivalence Class:
with unknown targets, it is called MMMEC [Jaber et al. 2020 When there is access to multiple domains, Li ct al. [2023) propose S-MEC.
Learning from Combined Datasets: There are plenty of works in the literature on learning the causal structure from experiments (or across domains). However, most of them provide empirical
approaches without theoretical analysis. Approaches like Peery et al. 2022]. Peters et al. (2016). Ghassami et al.] [2017]. Heinzee Deml al. (2018). Huang al. [2020] often assume Markovianity or
specific functional models (e.g., linearity), or combinations of observational and interventional data with both known and unknown targets. contrast, JCI combines all data into single dataset and
performs learning on the pooled data (Mooij et al. 2020]. Ke et al. [2019]. [Brouillrd et al. [2020) introduces geural-network-basee frameworks that leverages observational and interventional data to identify causal structures, even when intervention targets are unknown, demonstrating superior performance in structure recovery tasks but there is no soundness analysis. Acharya et al. (0188 demonstrates that with Oloo n.) interventions and O(n/c²) samples per intervention, one can effectively distinguish whether an unknown CBN matches a given model or differs by more than in total variation distance. Jiang and Aragam [2023] offers the first results to characterize conditions under which causal representations are identifiable without parametric assumptions, even in settings with unknown interventions and without assuming faithfulness. Addanki et al. [2021] aims to determine the directions of all causal or ancestral relations in G using a minimum-cost set of interventions. GIES [Hauser and Bühlmann, 2012] and IGSP (Wang al. 2017] are score-based and aim at learning a single DAG under known targets; there is no soundness or equivalence class analysis either. Lopez et al. (2022) developed a differentiable causal discovery for large and high- dimensional data. Tigas el al. [2022] proposed an experiment design algorithm to adaptively choose the intervention targets. [hhou et al. [0244, Mascaro and Castelletti [023) proposes Bayesian causal
discovery algorithms under causal sufficiency.
B
Proofs
B.1
Proof for Proposition 3.2
In this section, we extend the do-calculus rules to enable their application across two arbitrary interventions. This extension is crucial for characterizing our equivalence class when arbitrary sets of interventional distributions are provided.
Proof. Rule 1: The results follow from rule 1 of Theorem 3.1
Rule 2: From (Y 1L K2|W, DII,, we can derive from rule of Theorem 3.1 that Pi w, 2) (y/,,)) Similarly, given (Y Ki/W,J)2y we have Ps (y (r z). To- gether, we have Pr(y) w, z) Py w)... Here, we use Pt,J as the intermediate distribution to show the equality and use rule 2 in Theorem [.1 twice. This is necessary, as for any S c IUJ, D3 would be a denser graph that contains fewer m-separation statements than Dr,. Next, we show that it is also sufficient.
Lemma B.1. If3S C W (TUJ), s. (Y 1L K, DrKK, A (Y 11 K, JJDI, then (Y IL KG/W,DD,ss A (Y L K₁ W, W)J),,,K
Proof. Suppose otherwise (Y P K, D)), " then there is an m m-connecting path p from
Y to U K3 in Di,K, Given (Y JL K, S 1) D) D we have (Y IL K,/W, I) 1)P Pr.s
16

---

Comparing (Y + K,/W, DT,,K and (Y TT K,W,DDoy ky.s' the only difference between the two statements is the edges outgoing from S. Removing the edges creates p. Consider the case that S S is in p. For p to be m-connecting, S can only be collider. However, such m- connecting path indicates that there also a m-connecting path from Y to S which contradicts the given conditions. Thus, S cannot be in p. Then, there has to be a collider in p activated by some S E in Di,K, Consider a collider C' that is closest to Y in p. C is an ancestor of S. Then the path created by concatenating the subpath from Y to C and C' to S is an m-connecting path which is also in I. This is a contradiction. Following the same process we can also show that
(Y L Kr J)
(y w, z) are sufficient to use another interventional distribution Pt. as the intermediate distribution to show the equality.
Lemma B.1 shows that the graphical conditions for Pı(y/w,z) = (y w. 2)
Rule 3: From (Y II. Kj/W, DID (kyawy we can tell using rule 3 of Theorem 3.1 that Pr w) PiJ From (Y T1 K2(,,J)r J) we have (v)) = (y/ww) Together, we have Pi(y ()) PJ (y/w), Similarly, we apply the do-do rule twice and use PL,J as an intermediate distribution to show the equality. Likewise, any distribution that corresponds to denser graph indicates the conditions. Next, we show the sufficiency the conditions.
(WW.) Lemma B.2. IS C VVUUIJU W). such that (Y TL KJ.S|W II DAIK,W A (Y TT
Kr, Kr,S|W.J. (.WJ)).. D.K. then (Y IL KJ/ KJ/W, DD.,,, PIKK A (Y TL KT/W, J)D J.K
Proof. Suppose otherwise (Y M.. K₁ KWWWI I) DD.)D.DKK, (w)) then there is an m-connecting path p from Y E Y to E ()(W) in (WK. Given (Y TL S/, D..SSW.IInnipp DrKKYW,,SWY we Comparing (Y TL K, W,I) F.K, and (Y T K3 (WW,,)rI,jIO DIIKAWY the only difference in the graph is the edges into S(W). Consider the case that there is some S E S(W) in p. Consider S that is closest to Y. S cannot be a collider on p since it is not ancestor of any W W, and thus p will be blocked. Let consider the 2 cases:
have (Y IL KIIW.I)Dg FK,
If S has an outgoing edge towards Y on p. then there a directed path from S to Y because otherwise there has to be collider C E W in between Y and S, and S will be an ancestor of C. However, the subpath from to S in would then be m-connecting D (W).SW) which a contradiction.
If has an incoming edge from Y on p, then there is directed path S to U on p. Otherwise, there has to be collider C' in the subpath between S and U p. Such C' that is closest to S makes S an ancestor of C E W, a contradiction. Nevertheless, if there is a directed path from S to U, S is an ancestor of U. If U is ancestor of any W E W, S will also be ancestor of W, contradiction. Thus U cannot be an ancestor of any W E W, and the edges into U will be removed in D (W) which contradicts the assumption that is an m-connecting path.
Therefore, S cannot be p. While S has to be an ancestor of some W E W to activate p if it not on p, this contradicts the assumption that S S(W). To conclude, we show that (Y IL K, W. I) PrKKiwyy Following the same process,
also show that (Y IL K₁ W J.. J)Dy,
Lemma B.2 shows that the graphical conditions for Pr(y w) Pta(y w) (y /w) are sufficient use another interventional distribution Pt,J, the intermediate distribution to show the equality by using rule 3 of Theorem 3.1
twice.
Rule 4: We begin by introducing useful lemma.
Lemma B.3. For disjoint X, Y. W C V,S V (XUY),
SN Sn W #0,5 W, then Pxly (w) ( w) if: (SR II. Y/W, X) )).eR A (Sw IL Y W Sw: X Dx.sw where Sw = S n
W.SR S W.
DX x. ^ (Sw TL Y/W Sw. X) as C1. We first show that, by applying nule 3 and rule 2 in Theorem 3.1 sequentially, we can trans-
Proof. Denote the statement (SR TL Y
form from Px to Px.- Specifically, Px(y|w) = Px.a (y/w) if (S Il Y X) px.eww>
17

---

and Px.sn (y (w) = Px. (y))) if (Sw TT Y \ Sw, XR P By definition, Px. (y|w)= = (x))()/))
Denote the statement (SR TL Y X) Px.sn A (Sw TT Y|W Sw X, SR)DXxX Sw C2. Next, we show that C₁ and C2 are equivalent. Notice that they share the same statement, and we just need show that the other one holds true.
(C1 + C2): Suppose otherwise, (Sw M Y SWW X, SR (R..SRRPxxspp (x.s Sw then there is an m-connecting path from E Y to U Sw D Dx SS Comparing (Sw V. Y/W Sw, X, SR) S..S)x,,,, S Sw and (Sw IL Y/W (),,X)Dxxssp the difference is the SR in the conditioning set and the edges into SR. Consider the case that there is some S E SR in p. Since the edges into S are removed, S can only have outgoing edges, but conditioning on S will then block p. Thus, cannot be in p. S is not in since the edges into S are removed, conditioning S will not activate any path. Thus the supposition cannot hold.
(C2 = Cj): Suppose otherwise, (Sw +L Y/W Sw, X)Dx Sw Then there is an m-connecting path from Y E Y to U E Sw in Dx Comparing (Sw Y(W Sw: X, Sx..s. Sw and (Sw 1A Y/W SS.X))xxsst sw"" the difference is the SR in the conditioning set and the edges into SR. Consider the case that there is some S SR that closest in p.
is a colliser on p. then is an ancestor of some E W. There is a m-connecting path from S to Y in D (W) A contradiction.
If S has an outgoing edge towards Y in p. there has to be collider C & W between S and Y in Otherwise, the subpath between S and Y will be m mn-conecting in D (WS which contradicts the supposition. Since p is m-connecting, C' has to be ancestor of some W W in Px.sw' To block in Sw there has to be some S" e S that in between and W. This will create an m-connecting path from S' Y in D (W)) which is contradiction.
If S has an outgoing edge towards Sw in p. then S has to be an ancestor of some W W in D (wyy which is a contradiction.
Therefore, S is not in p. There has to be collider C E W in p. Consider such C' closest to Y. There directed path from C and directed path from be m-connecting. However, this makes S an ancestor of W in D (Wjj and the path created by concatenating the directed path from C to S and the subpath from C' to Y in p would be d-connecting in D (W)) A contradiction. The supposition does not hold.
some W W in Dx,sw for p to
This concludes the proof this lemma.
By applying Lemma B.3 twice, we can derive the graphical condition for Pi(llw) = Pi, (y (y for two arbitrary interventions I.J. The following lemma shows that this is sufficient condition.
Lemma B.4. If EE c V (TU JJ. RJ. Sn|W, I) DTKK, A (Y 11 Ww W \ (Sw U Wa), I) Drw, then (Y 11
S SwSw -S W, such that (Y
RJ W.D). Dr A (Y IL WJ W WJ.
Proof. We first consider (Y IL W. D) DT,,, (.j Suppose otherwise (Y J.. R,, J,]W, I) ( then there is an m-connecting path p from Y E Y U E RJ in D [R).(W]. From the given condition, The only difference is the edges into SR (W) in Dr- there is any S E SR in p. then it has only outgoing edges. Since p is m-connecting, the subpath from S to Y on p is also m-connecting in D (.Ro(W),SSe (WT)- which is contradiction. Thus SR cannot be on p. To block p D (RR,
know that (Y IL R2 W, I) PKKK),W)
there collider C' in p that is an ancestor of some W E W. C is activated in p in D, D (W) but not activated in D (W). This requires some S SR (W) to be ancestor of W, which is impossible. Therefore, the supposition does not hold.
18

---

Next, we consider (Y TT WJ W W.. W..ID Suppose otherwise, (Y T WJ W W., D. Pr.w'' then there is an m-connecting path p from Y E to U WJ in D P,, P is blocked in D1, S. Comparing (Y TT W \ WJ,I)D,, and (Y TT Wa/W (Sw U WJ), 1) Dww, "w. the only difference is the edges outgoing from Sw. If there is some S E Sw in then S has to be collider. Consider such S closest to Y. Since p m-connecting, then the subpath from
Y is also m-connecting in D iw which is contradiction. Thus, S cannot be in p. For S to block p in Sww while not p. it has to be an ancestor of some W E W and a descendant of some collider in p. However, since S E W, it can still activate the collider in p in Piw..Sw Therefore, the supposition does not hold.
By applying Lemma B.4 twice, we can show that it is sufficient to transfer through Pr.-- This concludes the proof of this theorem.
B.2 Proof for Proposition 4.4
We show the graphical conditions on the augmented pair graphs are equivalent to those given in the generalized causal calculus rules.
Proposition B.5. Consider a CBN (D = (VUL,E) , P) with latent variables L and its augmented pair graph (, (D) = (VOUVOU E DEE with respect to pair of interventions
I.J E I. Let S IAJ be set of nodes, F is adjacent to S(D), We have the following equivalence relations:
Suppose disjoint Y, Z, W C V. We have
(Y 11 Z D), = (Y 2 I F) (ug
(3)
Suppose Y, W are disjoint subsets of V S. We have
(Y W W., DD..
(F IL YOO 10)) (
-1
(4)
(Y IL Wr/W WI, J)
(F Y(J) ((J) ADg
(Y IL RJ W. D)D
(F 11 ( w CMATEB
(Y W.W.J. / D.RR(WT
FR
(F 11 Y(J) w (irr
(5)
For disjoint Y, Z, W C V, where KI KYJ,K, = - - KnW,R
K\ W, Rr R. KI, RJ ROKJ
(Y RJ W. D)PYnGTT
(Y 11 WJ W W..
{
{ (F Y ) (F ((J) w(J)) Aug
(6)
(Y W,JJ) D. (W)
(Y IL W1 W
WI.J)
For the right statement, conditioning on F is equivalent to removing it and the subgraph induced by (JJ from Aug (D). Then the statements on the two sides are equivalent.
Proof. Consider Equation 3
Consider Equation
We need to show that (Y TT W WJ, Do,DDrww + (F T
Y(I/W0) I()) AuR
(+) Suppose otherwise (F J. (() ( then there is an m-connecting path from F to ()) E ( in Aug/r.J) (D). Since W is conditioned on, cannot be a frontdoor path. Also, edges into I()) are removed, thus p cannot be backdoor path through Wr. However, given
(Y II W W,, I)D,, w,,," there is no backdoor path through W,, The supposition does not hold.
(+)) Suppose otherwise (Y M. Wa|W Wa. I Dr then there is an m-connecting path from (D) ())) U WJ. It has to be backdoor path from U. However, (F 1
19

---

T Y (y0,,0) ( ( will not hold, if there is backdoor path from U to Y. Thus the supposition does not hold.
For the same reason, we can show that (Y TT Wr/W WI, + (F 1
/ J(J) (D)
Consider Equation 5 We need to show that (Y II Ra/W, 1) Lng(W
Y W() (D)
(=) Suppose otherwise (F V. YO W() (u then there is m-connecting path p from F to y E Y in Ju (D). Since [ is conditioned on and the edges into ( are removed, p cannot be through ( If F has a frontdoor path to y through RJ (1) then Y to RJ will also be m-connecting D (W)) Else if it is backdoor path, can only go through some
( R (W); it contradicts (Y IL RJ W. D)D DDrraywy Thus the supposition does not hold.
(+) Suppose otherwise (Y KL RJ W I)DLRR then there is an m-connecting path p from Y Y to U E R, in D (IR..W]- If has an outgoing from U, then F would have frontdoor path through ( to ( that is m-connecting. This contradicts (F TL (()p) w()) W()) Aug (D)) Thus p can only be backdoor path from U. If U is not an ancestor of any W E W in Dj. the edges into U are removed and p do not exist in this case. Else if U is ancestor of some W W, the same backdoor path would also be activated in A (D). Therefore, the supposition does not hold.
For the same reason, we
can show that (Y
R, J) P.RRWw
(F
Y(J
Consider Equation We need to show that (Y 11 R,/W, I) PLRJ A TT W
I)
W,, Dr + (F IL Y w Augg,,,)
(+) Suppose otherwise (F 4. ( )( then there is an m-connecting path from F to (I)) E Y in (ug If a frontdoor path through s since ( W are conditioned on, only R could be in p. However, the path from R, to Y would be m-comnecting in D (R) which is a contradiction. If p is a backdoor path from to U E ( to y()) E y since the edges into [ removed, U only be from R or W If w then it contradicts (Y 1. W W \ WJ,
U E R U could be either an ancestor of some W E W or
non-ancestor of any (1() E W For the case that U is not ancestor of any ( E w p is blocked by U as inactivated collider. If U is an ancestor of some W(T) E W then the subpath from U to (T) would indicate an m-connecting path from R, to Y in Dr,w, which contradicts
(Y L Ry W, I) D)DLR Thus, the supposition does not hold.
(+-) Suppose otherwise, there are two cases to consider, either (Y L. Ra R3/W, WWWI)) D..IIWy or (Y T
W, W W,,I)
If (Y K WJ W WJ,D),,,, there is m-connecting path p from Y E Y to E WJ in Di Di,w w. P cannot be a frontdoor path at U, since all edges outgoing from Wa are removed. While a valid backdoor path at U indicates that there is also a valid path from F to (I) through ( in Aug Thus, this case impossible.
If (Y LL W W., D), there is an m-connecting path from Y Y to E R, in D P. cannot be a frontdoor path at U, because otherwise the path constructed by adding F > U to in (..) (D) will be m-connecting. Thus, can only be a backdoor path at U. is not an ancestor of any W D, the edges into are removed and such p do not exist. Else if U is an ancestor of some W E W in Dr. W(I) will activate the path constructed by adding
20

---

F-U0 to p in Aug(,,) (D), which contradicts (F TT Y(D w Aug (D), Therefore, the supposition does not hold.
For the same reason, can show that (Y TT R1 JJ Danniwy M(Y 1 Wi/W WI. DJ
(F Y ( )( AuRr,,
Proof of Proposition 4.4; The follows from Proposition B.5
B.3 Proof for Lemma 4.6
Proof. The extra cycles contain F, while F has only outgoing edges. Thus, the twin augmented
MAGs are ancestral. Suppose there is inducing path (F, XI, Xx,...xx)), F and Xx are not adjacent. Then X has a directed edge to X₁ MAG(Aug(D)) while MAG(Aug(D) is a MAG by definition. Thus, contradiction arises, and the supposition does not hold. The twin augmented MAGs are maximal
B.4 Proof for Theorem 4.7
Proof. (If) Suppose that the twin augmented MAGs TwinngJy(Diy Twing.,) (D2) for all I, I satisfy the 3 conditions. Then they induce the same m-separations and vice versa. Then by Proposition 4.4 that D1 and D: impose the same constraints over the distribution tuples. Thus P2(D1, V) Pz(D2.V)
(Only if) Suppose for pair of interventions I,J E M, = (Pi) Twi (D2) do not fully satisfy the 3 conditions. Then they must induce at least one different m-separation statement. We need to show that all the differences in m-separation statements induced by different M structures can be captured by some m-separation statements that are testable by the distribution tuples, and therefore, the difference in m-separation would be inducing different constraints on PI,D,, V) and PD,D2, V). Thus the condition that Pz(Di, V) = Pr(D2, V) will no longer hold, which is contradiction.
We start by showing all testable m-separation statements. For an arbitrary twin augmented MAG M (VO) U VVJ) U (F), E E(J) UE), the testable m-separation statements are as follows:
v, v, T T= TL ( ( 1 F)M X, Y
(XUY)JU
((X()) IL ( J( FMM:: & (XUY))
{(F I 2 M A ( TL Y z()) YCV,ZCV\Y;
Next, we show that M, and M2 should have the same skeleton.
First, we show that they have the same skeleton on V Suppose otherwise, Mi, ( and ( are adjacent but they are non-adjacent in M2. Then it implies that (Xx(1) 11 (1) (Z() F)M, (X(I) T (T) T F),, for some C V. Then we can further condition on 7() while preserving the se-ppraatiooss since edges into (T) are removed and thus conditioning on will not activate any extra path. Therefore, we have (X J.f ( (Z)) I F),, A (X II y!)) ( I(U, F),, which a pair of different testable statements in T. Similarly, Mi and M2 also have the same skeleton in v(J. What remains to be demonstrated that the nodes share the same adjacencies in both graphs.
By the construction of twin augmented MAGs, F is adjacent to (1), (J) in both Mj and M2. We need to show that F' has the same adjacencies X & K in both graphs. Suppose otherwise, F is adjacent to (I) in M1, but non-adjacent to (T) in M2. According in Mi but non-adjacent them in M2. We introduce the following
construction of M1,M2.
F is adjacent to (1) lemma which shows that in this case, we can still find a pair of different testable m-separation statements which reflect this structural difference.
Lemma B.6. Consider a causal graph D (V L. E) given a set of intervention targets I S 2V. Construct its twin augmented MAG M (VO) (VO (V)), E (E() UE), for I,J E I. lherr exists minimal W,, W2 C V, such that (F IL ( TP A (F IL (()) w w )M.. then (F 11 X (1)) W (F 11 (J), w(J) where W W,U
(J)
21

---

Proof. Suppose otherwise (F II ).) MM meaning that conditioning on W activates extra paths from F' to ( in M. Obviously, ( can neither be on the paths nor activate a collider on the paths. Consider a m-connecting path p(l) from F to X (1) given w in M. Then there is collider c on (()) which is activated by some w w!"". Let the subgraph of M induced by V(J) U F be G5. F and X are blocked by W2 meaning that the corresponding path p(o) in G5 is either blocked by inactivated colliders or does not exist due to removed edges into J. In both cases, p(d) is blocked by 0. However, due to the minimality of W2, it has to block some path other than p!d). Consider Wa E 22 which is closest to X and is a descendant of a collider ci on p(J), Denote the path created by concatenating direct paths from cP to W and c(J) to X as p> (J) Suppose there is a path pi from F to XJ) that is blocked by W Since (J) is blocked
by w:"") w:!") cannot be a collider on p If there is an edge into W from F's side, then the (J) will be m-conneccingg The subpath from F to W= has to be blocked by inactivated colliders or conditioning on a non-collider. In either case, Wr is not necessary for blocking pi") Conversely, there has to be an outgoing edge from w! towards F. Consequently, on p F has an outgoing edge towards W while W has an outgoing edge towards F. Thus there has to be collider in between F and W Consider such a collider C²2 E ww(") that is closest to F. Nevertheless, according to the minimality of W2, c has to block another path. If we repeat this process for |V] times, we show that W22 > n, which is impossible. Thus the supposition that (F WL X (1)) w()) does not hold. Similarly, can show that (F IL x (())) w()) which concludes the proof.
subpath of pa:
Therefore, according to Lemma B.6, the structural difference implies that we can find some W E W \ {X} such that (F V X W ) V (F N x(J] w while (F IL T() W A (F IL ( w(J) which is a pair of different testable m-separation statements. To conclude, M2 have the same skeleton.
Next, we show that Mi and M2 have the same unshielded colliders. We start by showing that they have the same unshielded colliders in the vertex induced subgraph on ( and V Suppose otherwise, (X (X(1), y 2 is an unshielded collider in Mj but not in M2. Since ( is not a collider in M2. has to be conditioned on to make X and 2 m-separable. Then we have (X 1 1 70 r W()) M, A (X J 2 [ra) W y@)M, and (X II z I(), W()) Ma A (X() 11 T(U, w y() Mz M,2 for some W S V (Y), which contains pair of different testable statements.
Then we need to show that unshielded colliders which include F nodes are also the same in both graphs. Due to the construction, F can only have outgoing edges, thus it can only be an end node in the collider. Suppose (F, ( 2 is an unshielded collider Mi but not in M2. More specifically, F Y ++ in M₁ and F y + 2 in M2 There are 2 cases: Y E K or Y & K.
First, consider Y E K. Y has to be in J \ I. then in the induced subgraph of V(J, we cannot have Y(J) (+)(() in Mi or M2. Thus we can find some W C V (Y), such that (F H IO Wa, yd) V (F 1 (()) W(J, y(J) while (F 1 I" W(T), YY))) A (F y Z(I W()), ( which is a pair of different testable m-separation statements.
Second, consider the case that Y K, but adjacent to F in both Mi and M2. Then there an inducing path from F to (L) or yJ) in the augmented pair graphs According to our construction of twin augmented MAGs, F is adjacent to both y()) and (J) in both Mi and M2. Since F is not adjacent to (1) (J) in M2, we know according to Lemma B.6 that there exists W C V such that (F 1L ( w JMz A (F Il (()) w))) MM W has to contain Y, otherwise F' is m-connecting to 2 or (J) in M2 through y or Y(J), We need
to further show that there cannot be (J) (J)(J) in M2. Suppose otherwise, if (J) + (J)
in M2. then there is a cycle in Dz. Else if y() + Z(J) in M2. then there is a latent common ancestor of Y, Z in Dz2. This will create an inducing path (F, (T), z(T) in M2 which contradicts the condition that F and (I) are non-adjacent. In M1, since there is + Y +*Z, we have
22

---

(F Z I WO)M A (F x J(d) W which contains a pair of different testable statements in T. Therefore, M, and M2 have the same unshielded colliders.
Suppose (U, W1, W2,..,,W WR, Y, Z) is a discriminating path in both Mi and M2, Y is a collider in Mi but non-collider in M2. By our construction, F can only be U or Y in the path. There are cases.
First, if F is not in the path. Then all the nodes in the path are in V v(J), Suppose the path is in V(D, Then in M2, there exists some W S V, such that (U T1 z [ F. (.W))) W;, Y e W,i E [k.] While in MI, we have (TT)) y. I0, F. W MM, since conditioning on y would activate the path. Thus there a pair of testable m-separation statements.
Next, if F is Y in the path, this case is not valid, since F' can only have outgoing edges. Therefore, if F is Y in the path, it should have the same collider status in Mi and MM2.
Lastly, F is U in the path. All of the other nodes in the path have to be all in either V or V Suppose that all other nodes are in V Since F' is non-adjacent to Z(1) in Mi and M2, we know that F is also adj-anjacent to Z(J) according to Lemma B.6 Thus in M2, there exists W S V. such that (F IL Z ( W() Mm, A (F IL 2(0) ) W,, Y E W.ie E [b]. We, Y are in W because otherwise F' is m-connecting with g through the path. However, in MI we have (F TL I(0) W()),, (F TT Z JJ), W because conditioning on w:("), y will activate every collider in the path from F to z(0, Therefore, there is a pair of different testable statements in T. To conclude, for each discriminating path in Mi and M2, F is a collider in Mi and only if it is collider in M2. Up to now, we showed that if MM and M2 do not satisfy the three graphical conditions in the theorem, then there exists a testable m-separation statement that holds in one graph but not the other.
When there exists a pair of intervention targets I.J E I such that M1
Twin (D)) and M2 = (wii do not satisfy either of the three conditions mentioned in the theorem statement, this implies that Dj and DD2 are not I-Markov equivalent. This is because there is m-separation statement that appears as a condition in the definition of Z-Markov equivalence that is different in the two graphs M, and M22- There is a m-separating path in M1 that is m-connecting in M2. We now show that Pz(D2, V) contains tuples of distributions that are not in PD V). We leverage a key result from Meek, demonstrating that the set of unfaithful distributions has Lebesgue measure zero. Building on this, we construct jointly Gaussian structural causal model that incorporates latent variables.
Lemma B.7. Meek (2013b) Consider causal DAG D (V,E), where (A f1 B C) Let De = (V E.) be the subgraph that contains all the nodes in the m- nn-oonecting path that induces (A B C)D. Then any distribution P over V where every adjacent pair of variables is dependent
satisfies (A A B
C)p
The proof of Lemma B.7 uses weak transitivity and an inductive argument and can be found in
Meek 2013b]. Suppose that X, Y, Z C V such that (X TL Y Z, F. Aug,,,,,)) (P.)) and (X A. Y 1 Augaa,,, Suppose that both X, Y are observed variables. In this case, any tuple of interventional distribution obtained from an observational distribution that is faithful to the causal graph with latent variables constitutes a valid example. Suppose X- = F for some and Y E V. Therefore, an F-node is m-connected to an observed node in (ug (D2) but not in Aug (Di).
Consider the causal graph D: (V JULL U. E) with latent variables. Focus on the subgraph of DD2 that includes all variables contributing to the m-connecting path of (X fl1 Y Z, F) (D2). An example can be found in Meek [2013b). Let us call this subgraph Dyutt (Vpuutt, Fpuat). Consider a jointly Gaussian distribution on V puch that is faithful to Dpath- Such distribution exists by construction in Meek (Theorem 7, [Meek] 2013b)). Denote this distribution by Ppath. We will focus on P Prah and later expand by adding the remamnnng variables in Druff as jointly independent and independent of the variables in D Danth Now, consider two intervention targets I and J on the CBN (Dpah, Prath), where IAJ- K. This implies that the distributions P1 and P3 account for the graphical separation of Fj. For this proof, we treat F1 as regime variable indicating when we switch between P1 and Pj. This treatment is valid because we add only this single F' node, without introducing others. Define the distribution P* as follows:
(' | 0) Pt()), P' = P)(-)
23

---

and let Fy follow a uniform distribution. We need to show that the invariances implied by the graph separation in the generalized causal calculus rules fail for Pt and P,. This equivalent to demonstrating that F, is dependent on Y given Z in the distribution P To construct the interventional distributions, we use SCM that implies the given CBN. Let x represent the vector of all variables in the graph, including latent ones. Consider the SCM given as follows:
x
Ax +
where A a lower triangular matrix describing the graph structure and parent-child relationships in D paah: and e is the vector of exogenous Gaussian noise terms, |x] n.
Let PI represent the distribution obtained by introducing the noise vector e, into the system. The vector e, is non-zero only in the rows i where x; E I. Furthermore, the matrix A is modified to a new matrix Ai, i. which is identical to A except that all entries in the rows corresponding to i (Vr; E I) are set to zero. This modification effectively removes the influence of the parents of the variables in the intervention set I, as required by the definition of hard intervention. Consequently, Pt qualifies as a valid hard interventional distribution. Similarly, let e, denote the noise vector introduced for an intervention on J. The matrix A is similarly replaced with Ag, where all entries in the rows corresponding to j (Vx, E J) are set to zero, achieving the same effect for the variables in J. We show that in the combined distribution p* using these Pt, PJ every adjacent variable is dependent. Clearly, when C₁ and cj are different, F variable is dependent with the variables in K := IAJ, since PK(K F 0) + P K F ), which implies ( K A F p-. Therefore, we focus on establishing that every pair of variables that are adjacent are correlated except for the F variable. The correlation of the variables in Paah is calculated as follows:
x = A₁x e = (I, A1)x - es = >x= x= xI, -I, A1) (e
- e₁)
x = A2x +2x+c+ox = (In -
= x
(I, A2) (e ee)
Where I, is the identity matrix of size n by n. Let = e es and 62 = e + e,. The correlation matrix between the observed variables, with respect to the distribution P after marginalizing out the binary regime variable, is computed as follows:
E xxx O., A1) [ele]]] (In, A1) +.5(LI, A2) [ (Ln A2)-1"
Let D1 E [c and D2 E [c2c]]] represent the diagonal covariance matrices for the noise introduced by the hard interventions. Additionally, assume that all the noise variables, including er, and e,,, follow zero-mean Gaussian distributions. Consider two adjacent variables, 24 and Ty, within 2 path We observe that the matrices I, Ai and I, A2 are full-rank, as A is strictly lower triangular matrix, and the same holds for A and A2. As a result, the matrix inverses in these equations exist and are unique.
We now treat D and D2 as variables in this system. When performing a hard intervention, we can freely select the variance of each added noise term. Our objective is to demonstrate that there always exist hard interventions, represented by D2 and D2, such that x; and zy become dependent. Since both I; and 2, are jointly Gaussian, they are dependent if and only if they are correlated. Therefore, we need to show that E [æ,æ,] # for any adjacent pair zy; Ty. we set D₁ = D2 O, we return to the observational system. By the assumption that the original distribution is faithful to the graph Dpat: any adjacent variables are dependent. This implies that the corresponding system of linear equations is not trivially zero. Hence, by randomly choosing the variances of the noise terms, we can ensure that, with probability 1, any adjacent pair of variables will be dependent (by applying a union bound).
Thus, we have shown that, in the graph D Ppah along with the F variable, every pair of adjacent variables is dependent. Next, we can extend this distribution to include the variables outside D puth- To do this, we select the remaining variables to be jointly independent and independent from those in Dpan. The interventional distributions can then be constructed by applying similar hard intervention, where extra noise terms are added to the variables being intervened upon and replacing the matrix A. The resulting set of interventional distributions will belong to Pr (D2, V), but not to Pr (D,, V). This is because m-separation should imply invariance across the interventional distributions, but we have constructed them in such way that this condition does not hold. This concludes the proof. L
24

---

B.5 Proof for Proposition 5.2
Proof. We have shown in Theorem 4.7 that two causal graphs are I-Markov equivalent if and only if their twin augmented MAGs satisfy the 3 conditions. Here we just need to show that the twin augmented MAGs follow the conditions if and only the Z-augmented MAGs follow the conditions.
(If:) Notice that each twin augmented MAG T (D) can be constructed by taking the graph union of Augr( (D, I) and Aug, (D.I) and removing irrelevant F nodes. Therefore. if Augr (D1. and Aug, (D2. I) have the same skeleton for any I E I. T and T will also have the same skeleton. Furthermore, T (D) and Augı (D,I) have the same unshielded colliders within ( U { because they have the same subgraph V U (F())))) Since twin augmented MAGs do not have other F nodes, T and Twinr,J (D2) have the same unshielded colliders. Similarly, any discriminating path in Augı (D, I) will also be preserved in J (D) while there cannot be discriminating paths that pass through the F node in Twin (D). Therefore, T and Twinr, (D2) have the same collider status discriminating paths.
(Only if:) Now we show that if Twinr, (D,) and Twing,J (D2) satisfy the 3 conditions for any I.J E I, then Augi(D,, (D1, I) and Augı (D2, I) also satisfy the 3 conditions for any I E I. Since ADgr(Di,I) is the graph union of Twin (D, on V U (F(L.)), all the adjacencies are kept and the same for Aug, ADg I). Thus, they have the same adjacencies. For unshielded triples, if both ends are F nodes, then they have to be unshielded colliders in both Augr (D1, and Augi (D2, I) given F nodes have only outgoing edges by construction, If most one endpoint of the unshielded triple is an F node, then the same structure can be retrieved from the relevant twin augmented MAG. Therefore, Augr(22 (D1, I) and AugT(D) (D2, I) have the same unshielded colliders. Finally, we need to show that if p = (U, W2, WR. Y, Z) is discriminating path in both A (Di,I) and Augı( Augr(D2, I). then p has the same collider status. If p is in V then p is also in Twinr. (D) and Twinr.J (D2) for any E I and thus it shows the same collider status both Z-augmented MAGs. If FI.J) is an endpoint of p. then the path is also in T (D1) and T (D2) with the same collider status. By the construction of I-augmented MAGs, an F node can only be Y in if it is not the starting node. Since F nodes only have outgoing edges, p will have the same collider status in both Augr (D,, I) and
B.6 Proof for Theorem 6.3
The algorithm is learning the causal graph through finding the separating sets between each pair of nodes using the distributional invariance tests. The invariance tests are tied to the m-separation statements in the causal graph according to the h-faithfulness assumption, and the properties in Defini- tion 4.1 are mapped to the m-separation statements in the twin augmented MAGs by Proposition 4.4 We show that twin augmented MAGS are combined to construct Z-augmented MAGS which preserve the m-separation statements in Proposition 5.2 Ideally, our algorithm would learn a structure that is close to the T-augmented MAGs. Therefore, to show the soundness of Algorithm T define the I-essential graph as follows:
we need to first
Definition B.8 (I-essential graph). Given a causal graph D (V V.L, E) and set of intervention targets I C 2V, the T-essential graph of D related to I, denoted as (D, I) is the union graph of the Z-augmented MAGs of D' for all D' that are ADMGs I-Markov equivalent to D.
Definition B.9 (Union Graph of k ADMGs). Let G1, G....., ...,., G& be k ADMGs, where each graph G, = (V.,E.)
The union graph of l ADMGs, denoted as Gu = (Vu, Eu), where Vu = U V., for each pair of vertices (X,Y) the edge set of Gu is determined by:
X Y,
iX + Y) appears in all G., X, Y E V
X + Y, Xo Y, Xo_oY,
if (X + Y) appears in all G., X, Y E V..
&
if (X + Y) appears in some G. (X + Y) appears in some X, E.V. V
if ( + Y) appears in some Go (X +
Yaappears in some G, X, E V,,,,
25

---

The Z-essential graphs denote the structure that is ultimately learnable by any causal discovery algorithm. Based on this definition, to demonstrate the soundness of our algorithm, it suffices to address the following two questions:
(a) Do all the Z-augmented graphs returned by Algorithm | have the same adjacencies as the T-essential graphs?
(b) Are the orientation rules sound, i.e. any arrowhead/arrowtail learned by the algorithm is also present in the Z-essential graph?
We first address (a). Consider an Z-augmented graph Gr. the edges either contain a F node or not. There are no edges between any two F nodes by our construction of 91 and Augr (D, I]. Consider the edge (FU(.)) Y() in Gr. is recovered because there does not exist W C V, such that Pr(y) w) = (v w) under h-faithfulness. According to Definition 4.1 and Proposition 4.4 it implies that F (L.)) and y y(J) are also adjacent in Twin (I.) (D') for any D'' that is I-Markov equivalent D. Thus F(IJ)) and (J)) are also adjacent in Aug, (D', I). Consequently, they also adjacent in the Z-essential graph. For the same reason, if F(I.)) and ( are not adjacent in G1, can derive that they are also not adjacent in (D,
Next, consider the edges that do not contain F nodes. There are no edges between two nodes in different domains both 91 and Augr(D, I) by our construction, We call the vertex induced subgraph on V J E I domain. We just need to show that they have the same adjacencies within each domain. According to our algorithm, within each domain, all the edges are connected by applying the FCI algorithm, which is proved to be sound by Zhang 2008b]. Thus, 9r will have the same adjacencies as (ug ()V(") E I for all D' that are I-Markov equivalent to D.
Finally, we address the soundness of orientation rules. In phase I of the learning algorithm, FCI rules within each domain to learn the skeletons. Zhang] (2008b) showed that FCI is sound and complete. Thus, the orientations in the skeleton learned in this phase for all D' that is I-Markov equivalent to D. In phase II, F nodes are introduced and adjacent to the symmetric difference of the targets, and the nodes that are not separable from F. All the edges induced to F nodes are oriented outgoing from F nodes by Rule 8. This is also true in A Aug, (D', .I) for all D' that is I-Markov equivalent to D. Thus, so far, all the orientations learned sound. What remains to be shown is the soundness of the extra orientation rules.
use
shared across all Aug, (D'),
In Algorithm 3 for the interventional domains, return the separating set that includes the interventional target of the domain. This inclusion is required by the do-calculus rules. However, in practice when running Algorithm T we can remove the targets from the separating sets save memory since removing them will not impose any modification on the orientation rules. To witness, the only rules with use separating sets are Rule 0 and Rule 4. Both are deciding the node of interest is a collider. Since the targets are intervened, they have no incoming edges and thus removing them from the conditioning sets will not drop off any possible colliders. Therefore, one has the flexibility to include the targets in the separating set or not.
Remark:
Soundness of Rule O: If both end nodes are in V, then the soundness is guaranteed by the soundness of FCI. Suppose (F, (x)) (1) is an unshielded collider identified by the learning algorithm, i.c., there is some W C V \ I, such that, F IT (1) ( ( while X & W UI Suppose otherwise, (F, (1), y()) is not unshielded collider, then it can only be F - ( + yf), Since F, (I) are non-adjacent, the soundness of the skeleton indicates that there is set of nodes that separates F from (f), However, in this case, to separate from y()) (²) has to be in the condition set; otherwise, the path F + (1) + (f) would be d-connecting.
Soundness of Rule 9: To address the soundness of Rule 9, we need to show that if (1), (I) are adjacent, and X E I, then Y can only be descendant of X in the interventional causal graph Dj. Suppose otherwise, then Y is an ancestor of X or they have at least one common ancestor in Dj. However, since X is intervened, there will be no ancestor of X in Dr. which is a contradiction.
Soundness of Rule 10: We need to show that if we recover X + Y in the domain G there cannot be (J) +- (J) in another domain of J. Suppose otherwise, it indicates that there is a directed path from Y to X in Dy. However, there is also a directed path from X to in Dz. Dj and Dj are subgraphs of D, thus there is at least I cycle in D which is a contradiction.
26

---

collider in the path. Consequently, we can infer that the inducing Soundness of Rule 11: F(...) is adjacent to Y y while Y & I shows that there does not exist any W C V such that Pr(y) w) Pa (y)ww. This means that there no separating set that separates both F(IJ), y and F(IJ), y This indicates that there is an inducing path from F(I.)) y or from F(.J) y(J) relative to the latent variables in the augmented pair graph. Due the definition of the inducing path, it has to go through X or ( K {X}. However, in G since X is intervened, X cannot serve path has to go through ( to y ( Furthermore, ( has to be parent of one of the end nodes of the path. Given that F nodes are source nodes, we can orient X + y
27

---

C Algorithms
C.1 Algorithm for Creating Nodes
Algorithm 2 Algorithm for Creating F Nodes
Input: Intervention set Z, intervention I Initialize FF <- 0; for J in I \ {I) do
F t FU (F(L)))
Output: The set of F nodes
C.2 Algorithm for Finding Separating Sets
Algorithm 3 Algorithm for Finding Separating Set
Input: Target I and J, interventional distributions (ft)rez, observable variables V, F nodes F Initialize & 6; I = J then for X,Y Y in V do
SepFlag &- False;
for W C if Pr(y/w (,lww, x) (r(y) w) then SepPlag +- True SepSet(X()) = UFU
if SepFlag- False then
EU Y();
else
for Y in V do SepFlag &- False; if Y in IAJ then Pass;
else
for W C do
if Piy w) (g/ then
SepFlag + True;
SepSet(I, y +
SepSet(F, ( + (J] w());
if SepFlag = False then E E (F(I))) y
Output: Circle edges E, separating sets SepSet
C.3
Complexity Analysis
Since our algorithm is also constraint-based--ine FCI and PC-the bulk of the computational cost comes from invariance tests, which can be F-node. In the worst case, each pair of nodes may require an exponential number of tests to identify separating set. However, practice, many implementations (including FCI and PC) limit the size of the conditioning set (c.g., to a constant such as 3), which reduces the worst-case complexity to polynomial bound of O(n²) (see, e.g., Spirtes al. (2001)).
conditional independence tests involving the
For the new orientation rules we introduce: Rules 8, 9, and 11 operate in O(1) time since they only check the adjacencies of fixed number of nodes. Rules 10 and 11 have complexity of (nn2) as they potentially examine all pairs of nodes. In comparison, the FCI orientation rules can take up to O(n") in the worst-case.
Thus, for each Z-augmented MAG, our learning algorithm has similar worst-case complexity as the FCI algorithm, namely O(n²). If there are k targets, the total complexity becomes O(kn)).
28

---

D An example of the Construction of Twin Augmented MAGs
Graph Dj in Figure Za is the original graph with a confounder between Z, Assume that the intervention set is I = I = 0, _ = {2}} Here we use the index of the targets in the superseripts of the variables for simplicity. Figure 2b shows how we build the augmented pair graph by adding the F node and pointing it to both Zs in the two interventional subgraphs. In Figure 2c] we show the MAG of (2)) The edge of (F, (") is added because there is an inducing path (F, 2",Y(i) in Aug(o,12) (D1), which means that F is not m-separable from Y(1) and F is an ancestor of yr()) Now that (F, (()) is presented in MAG(Aug(0,(2))())
but not (F, (2)).
according to Definition 4.5 we also add the edge of (F, Y (2)) finally construct the twin augmented MAG of D1, which is [w)) (2z) as illustrated in Figure 2d
Next, we repeat the same process for D2 as illustrated in Figure 2e 21 2g
Comparing Twin (, (Di)
and T Twinga, (Dz) (Figure 2h), we see that they do not satisty the three conditions from Theo- rem 4.7 since they have different skeletons. Hence, we conclude that Dj and D2 are not Z-Markov equivalent with respect to This example also highlights that hard interventions can be more informative than soft interventions because, under soft intervention the two graphs, and they will be Z-Markov equivalent using the results from Kocaoglu et al. [0199] However, with hard intervention, can distinguish the two graphs Dj and D2 from one another.
Z, one cannot distinguish
X(I) - 7(1)
Y(I)
X - 7(1) (())
T
X(1) - 2(2)
Y())
F
t
+
F
+
X(2)
- (
X Y
(
Z
- ((2)
X(2)
2 (
(a) Graph D
(b) Aug (
MAG (D))
(d) Twin
X(I)
2() Y())
X(1) 7(1)
y
X(I) 2 y
t
F
F
+
- (2) x(()
2 + ((2)
(2)
2
(
7(2)
(
(g) MAG (D2)) (h) ("ii
(e) Graph D2
(1) ou (D2)
Figure 2: Illustration of the construction of twin augmented MAGs where D1 and D2 are not I- I-Markov equivalent. (a) and (e) are two causal graphs, Dj and D2 respectively, given intervention targets I = {I = 9, I2 respectively. (c) and (g) are the MAG of the augmented pair graphs for D3 and D2 respectively. (d) and (h) are the twin augmented MAGs for D, and D2 respectively. F - (1) in (AG(AAgg0,())) and MAG(Aug()42)) (D2)) because there an inducing path (P, 2 (()) in both augmented pair graphs. In the twin augmented graphs, we further add F + (2) to make the adjacencies around the node symmetric.
{Z}}. (b) and (f) are the augmented pair graphs for D1 and D2
29

---

E
An Example of the Learning Process
(h oz y
x x oz y
x
oz (2
x x oz (2)
(a) Initialize (o(Di)
(b) Initialize Go (D2)
(c) Initialize 9(2) (D1)
(d) Initialize 9[2) (D2)
X
lb
(1))
X(
2 (
X
( (1)
x
z
p
f
F
F
(
88
Z (
(2)
Z
(2) (2)
(
Z
9 (2)
(c) (D)) and (2z) (Dz)(t) (D.)) and g1z) (D2) After Phase Il
(g) go ) and (1z) (D))(h)
(h) Gy (D2) and G(z) After Rule 0
After Phase II
After Rule 0
X > z (
X 2(1) y
zl1b
(1)
X
((1)
y
F
F
F
F
(2)
2 (
F
(2)
222) (2)
(2)
z
(2)
(2)
(
y (2)
(i Go (D) and ((2) (Di) (i) Go (D)) and (D2)(D)) After Rule 8
After Rule 8
(k) (D,) and G(z) (D)) (D())) and Giz) (D2)
Figure 3: An example of the learning process of Algorithm
Here we show an example of the learning process of Algorithm I in Figure 3 Consider the two causal graphs D1, D2 as shown in Figure 2a and Figure [e respectively. Assume that we have access to (Pots: Pz). ). i.e. I == [I, 0. L }- In Phase I, we initialize the T-augmented graphs under each interventional target for both graphs by constructing complete graphs with only circle edges within the observable nodes. After that, we create the F nodes between each pair of intervention targets using Algorithm 2 and connect each F node to all observable nodes. The initialized Z-augmented graphs are shown in Figure 3a Figure 3b Figure 3c, and Figure 3d Here we omit the superscript for F nodes since there are only two domains. Then in Phase II. we learn skeletons by using Algorithm 3 to check the invariance statements. Specifically, for each pair of X, Y E V. if there exists some W C V that separates X, Y in any domain, we remove the circle edge between X, Y accordingly. Similarly, if F is separable from vertex in V given condition set W C V. i.e. Po(y) w) = P(zy (y/w), then we remove the circle edge between F, Y in both domains. Thus construct the skeletons of I-augmented graphs for D, and D2 shown in FigureB3eJand Figure 3rr respeciivyy The upper graphs are for the observational domain while the lower graphs for the domain of Pz. Next, in Phase III, we apply the orientation rules. We start by finding all the unshielded colliders using Rule O. In Gn (D1). we notice that conditioning
Z(1,
F is dependent on (1), Similarly, conditioning on (1) FF is dependent on (1), We can then orient X (1)) (1) (1)) Fo-oZ(L), and Fo-oY(1
X (1) (1), x0) Z(1) Fo- (11), and Fo- (1) respectively. The same structure appears in Go (D2). However, in Go (D2). we can identify the unshielded triplets (X(2), (()) 7(2)) and (2(2) (2), F') which help us orient the colliders accordingly. The resulting graphs plotted in Figure 3g and Figure 3h Using Rule 8.
30

---

we orient all edges incident to F out of F. The Z-augmented graphs after Rule 8 are presented in Figure Bi and Figure 3i Since only Z is intervened but not Y, we can orient the edge Z(2) + Y in both ((z) (D)) and ((z) (D2) using Rule 9. While Rule 10 helps us to orient o 0-> Y Rule
11 implies that we can orient 2 + y(L) since F points to ( ((2) in both (Di) and 9o (D)) as Y is not intervened. Thus, there has to be an inducing path from F to y y that goes through z(1) or Z(2) in both augmented pair graphs for D1 and D2. Notice that these edges cannot be oriented by the FCI rules. At this stage, none of the rules apply anymore; therefore, (p(D)), ( (Di) and (D2), (D2) are returndd as the learned Z-augmented graphs of Algorithm [ The final results are shown in Figure 3k and Figure 31 Notice that the learned Z-augmented graphs of the two causal graphs have different adjacencies and unshielded colliders. Therefore, they can be distinguished by the conditions listed in Theorem
F Experiment Details
E1 Enumerate All ADMGS
In this experiment, we aim to demonstrate that the I-MEC size under hard interventions is smaller than that under soft interventions in general. Here how we set up the experiments. Given the number of observable variables n, we iterate through all possible ADMGs structures with n nodes. The number of such ADMGs can be found as follows. We first generate all possible DAGs (not necessarily connected) with n nodes. Then, for each pair of nodes in a DAG, there can be bidirected edge or not. Thus, the number of ADMGs under consideration is 2( multiplied by the number of all DAGG. Each time, randomly pick ADMG G' as the ground truth graph. Assuming that the size of the intervention targets is 2, we construct the twin augmented MAG M2 of G following Definition ( [2019). We then enumerate all possible ADMGs, and for each candidate ADMG G', we construct its corresponding Mii and My, and compare MI, following Theorem 4.7 M2, following Theorem 2 in Kocaoglu et al. [2019]. For each nt, we repeat the experiment 30 times and calculate the average size of Z-MEC size together with standard errors. We consider two types of sampling ADMGs, random and complete. 'Random' means the ADMG is constructed by randomly adding directed and bidirected edges with a probability of 0.5 between each pair of nodes while not creating any cycle. 'Complete' means we first construct a random complete DAG and then randomly add bidirected edges with a probability of 0.5 between each pair. For intervention targets, we assume they are either atomic or an empty set. We only show the results for small n, as the number of with n. All the experiments are run on an NVIDIA GeForce RTX 3090 graphics card. The numerical results are shown in Table 2 We notice that the number of ADMGs grows very fast with n. The results have a high standard error. This is due to the differences between the sampled graphs. Nevertheless, under hard interventions, the I-MEC size tends to shrink the Z-MEC size more efficiently than with soft interventions on average, showing the power of hard interventions. Furthermore, grows, the ratio of hard I-MEC divided by the soft I-MEC decreases, meaning that hard interventions extract more information on the causal graphs.
and the Augmented MAG M2 of G following Definition 4 in Kocaooll et al.
ADMGs grows super-exponentiin
n
Mean under Hard
Mean under Soft
Graph
Ratio
Number of ADMGs
2
2.03 + 0.15
2.93 + 0.29
Random
0.69 = 0.05
6
2.37 = 0.12
3.67 : 0.22
Complete
0.65 = 0.05
6
3
19.50 = 3.41
30.57 + 4.36
Random
0.64 = 0.11
200
14.03 + 2.69
24.70 + 4.12
Complete
0.57 = 0.05
200
677.13 = 227.72
1218.83 + 361.83
Random
0.56 - 0.18
34,752
4
721.37 + 276.36
1529.57 + 368.68
Complete
0.47 = 0.07
34,752
Table 2: Estimation of I-MEC size by enumerating all ADMGs of the same size. We consider
random ADMGs and ADMGs by adding bidirected edges to random complete DAGs. For each setting we sample 30 ground truth ADMGs and calculate the mean and standard error of T-MEC size and the ratio.
31

---

F22 Sample ADMGs
When n 5, the total number of valid ADMGs is 29,983,744, which is intractable to enumerate. Instead, we can sample ADMGs estimate the expectation of the probability of randomly sampled ADMG to be Z-Markov equivalent to given ADMG using Hoeffding's ss Inequality. To do this, given n, we randomly sample a DAG that is complete graph using the uniform CPDAG sampler by Wienöbst et al. [222T. Then, for each sampled complete DAG, we add bidirected edges uniformly to each pair nodes to construct a ground truth ADMG. To compare with the ADMG, we randomly pick two intervention targets that are either an empty set atomic, and then randomly sample ADMGs following the same process and construct the augmented graphs. Suppose for each ground truth ADMG, we draw M such random samples. For the i-th sample, S, = 1, if it is Z-Markov equivalent the true graph and S; 0 otherwise. We define S i=1 S, which shows the number of Z-Markov equivalent ADMGs. We denote EE as the expectation we are approximating. Thus, according to Hoeffding's Inequality, we have:
Mf
S P( M
Es 2 S exx(p22Me
We choose c = 0.01 and cxp(- 2M = 0.01 for M with M = 23025. For each setting, we randomly sample 50 ground truth ADMGs and then take the average. The results are shown in Table 3 Table 4 and T We can see that the estimated IEgard is significantly lower than Egof meaning hard interventons can more efficiently learn the causal structure. Notice that as n becomes larger, the number of ADMGs grows fast and thus the expectations get close to Consequently, much smaller e would be necessary to approximate the expectations, leading to much larger number of samples M.
n
Estimated Ehard
Estimated Eaft
Ratio
2
0.417 + 0.010
0.584 + 0.010
0.715 + 0.011
3
0.143 + 0.012
0.235 + 0.016
0.607 0.022
4
0.058 + 0.011
0.112 0.015
0.514 + 0.024
5
0.028 + 0.011
0.061 = 0.013
0.459 0.028
6
0.015 + 0.010
0.036 = 0.012
0.420 + 0.030
Table 3: Estimation of Z-MEC size on complete DAGs with different sizes and 0.5 density of bidirected edges.
n
Estimated Egard
Estimated =0y?
Ratio
3
0.151 + 0.011
0.264 0.015
0.571 + 0.017
4
0.067 + 0.010
0.149 0.013
0.451 + 0.017
5
1.034 0.010
0.091 = 0.013
0.373 + 0.017
6
0.019 + 0.010
0.059 + 0.012
0.317 + 0.017
Table 4: Estimation of T-MEC size with different n and fixed 0.45n - 1) bidirected edges
(approximately 0.9 in density).
P
Estimated ghard
Estimated E
Ratio
0.1
0.020 = 0.011
0.024 1.024:0.00 0.011
0.804 0.018
0.3
0.022 + 0.011
0.040 + 0.012
0.566 0.030
0.5
0.028 0.011
0.061 + 0.013
0.459 + 0.028
0.7
0.031 + 0.011
0.081 + 0.013
0.395 0.021
0.9
0.034 1:84+0000 0.010
0.093 + 0.011
0.365 + 0.015
Table 5: Estimation of Z-MBC size on completed DAGS with nodes and different densities of bidirected edges. It shows that when the density of bidirected edges goes up, hard interventions shrink the I-MEC size more efficiently than soft interventions.
32

---

F33 Comparison of Learning Objectives with Other Interventional Causal Discovery Algorithms
Most existing interventional causal discovery algorithms aim to learn a single causal graph. However, the goal of our learning algorithm is learn tuple of Z-aummented graphs that entails (a superset of) Z-Markov equivalent ADMGs. None of the previous approaches outputs the same object.
Concretely, Z-FCI [Kocaoglu et al. 2019 (known targets)/t--CI [Jaber al. 2020] (unknown targets) assume soft interventions and cannot exploit the additional invariance constraints incurred by hard interventions. They use single augmented MAG as the learning objective. JCI [Mooij et al.) 2020] claims it works for any interventions but it is overly simplistic and the learned PAG is less informative (in Jaber et al. [2020] App. shows that v/-FCI can learn more than JCI), GIES Haassr and Bühlmann 2012 and IGSP Wang al. 2017] are score-based and aim at learning a single DAG under known targets. They neither guarantee inclusion minimality nor provide equivalence- certificates. Nevertheless, score-based methods usually impose parametric assumptions like linear function or additive Gaussian noise to the causal models. Such methods are not robust when the underlying mechanism deviates from those assumptions. Additionally, GIES and IGSP assume latents and therefore their outputs are less informative. Because the outputs are of different types, a direct performance metric is unavailable to measure the performance of the methods. The previous sections have shown that empirically how much smaller the Z-MEC is vs, the soft Z-MEC produced by 3-FCI Here we compare with GIES and IGSP with a simple example.
mnclusion-minimaliy
Consider the graph [X -, Z - Y + - Y] where L is a latent variable. We generate a Bayesian network with binary variables according to the graph. We take 100k samples from the observational distribution and 100k samples from Pz. We choose 100k as it is more than enough to return correct CI tests. GIES returns YY' + Z - X] which has the wrong causal order and does not belong to the same observational MEC. IGSP returns [X + 7 + Y, X -> Y] which is the observational MAG of the true graph, but it cannot tell anything to judge if there is a latent confounder between Z, Y. Under the same setting, when the simulated dataset is from a linear Gaussian structural causal model, both GIES and IGSP output [X + Z -> Y] which catches the right causal order but does not belong to the observational MEC. In both settings, our algorithm is able to learn the graphs illustrated in Figure 3k which preserve information from both domains. We use the Python implementation of GIES by Olga Kolotuhina and Juan L. Gamella [aaeella 2025)
The IGSP
implementation from the causaldag package (Squires 2018
G
Further Discussion
G.1 Assumptions
G.1.1 Positivity
In theory, dddess not require strict global positivity assumption. All results rely solely on h-faithfulness. "Strictl positive distribution" is added some works on discovery as a convenience. This is because within the space of strictly positive parameterizations, the subset that violates faithfulness sits on algebraic varieties of lower dimension, hence has Lebesgue measure 0 (see Robins al. (2003 and many follow-ups). In practice, with finite data, zero near-zero cell makes Test statistics undefined or unstable, so implementations often impose minimum-count rules even when the theory would allow the zero.
The positivity assumption is required for identifiability (for example, Kivva et al. 20022) Kandasamy et al. [2019]). This is because that the manipulation of numerical expression explicitly require the denominator to be strictly positive. By contrast, structural discovery uses only qualitative independence relations. As long as evaluate test where, no global support assumption is required.
G.1.2 Faithfulness
There are weaker faithfulness assumptions. However, the soundness of Algorithm I requires h- faithfulness. The I-MEC we defined is based on the generalized do-calculus rules and so as the learning algorithm and hence h-faithfulness is minimal for the algorithm to be sound.
'The algorithm was proposed in Kocaoglu et al. 2019 and later named I-FCI by Li al. 2023
33

---

Like classic faithfulness, the set of parameterizations that violate h-faithfulness has Lebesgue measure zero for standard SEM families with continuous noise if we consider linear models; i.e., holds generically (it also holds for many other models, see follow-ups of Robins et al. (003]) D. It is therefore no stronger a thesere- sense than ordinary faithfulness, but is stronger logically: rules out a few additional, finely-tuned parameter combinations that would create the extra cancellations specific to our Rules 1-4-those cancellations correspond exactly to our new orientation rules, so dropping h- h-faithfulness would break thesoundness. From the high level, imagine a causal graph under faithfulness assumption. could be the case that for certain conditioning values Z = 2, two variables X and Y that are d-connected are independent. While faithfulness covers the case that X is dependent with Y given (when the dependency metric is averaged over all 2), h-faithfulness is similar to saying X, Y are dependent given every Z = This analogy is exact if the intervened node is a source node, but we believe it gives some insight on the leap from observational faithfulness to h-faithfulness
G.2 Comparison between Hard Interventions and Soft Interventions
One may expect that hard interventions can always extract more information about the causal graph than soft interventions when there are latents. Here, we show an example in Figure 4 where this not true. Consider the ground truth ADMG 'D in Figure 4a with intervention targets I {[
{X1, X2), 1g (Y,, }. The Z-augmented MAGs under hard interventions are shown in Figure 4b and Figure 4c respectively. The augmented MAG under soft interventions is shown in Figure 4d We suppress the superscript of /' nodes since they are the same. We notice that under hard interventions, the skeletons in both domains are empty graphs because the hard interventions remove all the bidirected edges in D. However, under soft interventions, the skeleton of D is preserved since soft interventions do not modify the graphical structures. As a result, any graph that has only bidirected edges between X1 and i. E {1,2] is Z-Markov to D given 1 12 hard interventions while this not true for soft interventions with the same targets. For example, consider the two graphs D1, D2 plotted in Figure 44 and Figure 41 Given I, their domain-specinf skeletons will all be empty graphs as 'D when I is hard, thus they are I-Markov equivalent to D. However, with soft interventions, their skeletons can be preserved and thus not Z-Markov equivalent D when I is soft. Therefore, for this kind of graphs and intervention targets, soft interventions may end up with smaller Z-Markov equivalence class than hard interventions.
F
F
X1 + + 12
x
y(1)
(1)
2
(1)
x(2
y (2)
2
(2)
(a) Example graph D
(b) Augi, (D,I)
(c) Augi, (D,I)
X1 K1
Y2
X1 X
x
X2 Y2
(d) Augmented MAG of D under soft interventions
(e) Example graph D1
(f) Example graph Dz
Figure 4: An example that soft interventions lead to smaller Z-Markov equivalence class than hard interventions. (a) is the ground truth causal graph D with intervention targets I = {[X1,Xg] {, Y1, }: : (b) and (c) are the two I-augmented MAGs under hard interventions; (d) shows the augmented MAG under soft interventions; (e) and (f) are two examples graphs that are I-Markov equivalent to D when I is hard but not I-Markov equivalent to D when I is soft.
If the observational distribution is provided, the skeleton is preserved for both hard and soft in- terventions. However, the following example in Figure 5isowss that even given the observational distribution, there still exist causal graphs which can be distinguished by soft interventions but not so with hard interventions. Consider the causal graphs 2, and D2 as shown in Figure 5a and Figure 55) with intervention targets I = 0, 12 (Y), and I, = (X,Y). Here we use the index of the targets for superscripts and subscripts for simplicity. The augmented MAGs of Dj and D2
34

---

under soft interventions are shown in Figure 5c and Figure 5d respectively.. We can see that the triple (F(2.3) .X.Y) ,x Y) forms an unshielded collider in the augmented MAG of D2 but it is a non-collider in the augmented MAG of D22 Therefore, they do not satisfy the 3 conditions, meaning that they are not Z-Markov equivalent when I is soft. The Z-augmented MAGs for D1 and D2 are shown in respectively. We can see that all the pairs of corresponding Z-augmented MAGs satisfy the conditions. Therefore, D1 and D2 are I-Markov equivalent under hard interventions although the observational distribution is given. If an additional intervention target 1 {X] is given, D1. D2 will be non-Z-Markov equivalent with a different collider status of the triple (F(1.), ( y(d) in Augı, (D1, 2) and Augı, (D2, 2). We conclude that although hard interventions are stronger than soft interventions, they not always lead to a smaller Z-Markov equivalence class than soft interventions. It may also imply that using mixture of hard and soft interventions may be more efficient in causal discovery than using either of them alone.
Figure 5e
ST 5g and Figure 5h Si Dij
X
X - Y
(a) Example graph Dr (b) Example graph D2
F(2.3)
F(1.3) F
F(2.)) F(13) F(1.))
X
(C) Augmented MAG of(d) Augmented MAG of D1 under soft interven-D2 under soft interven- tions
tions
F(L3)
F(1.2) F(2.3)
p(12) p(,3) p(.3
X + (1)
X
(
X(I Y
(e) Augi, (Pi,I)
(1 Augi, (D1,I) I]
(g) Augi, (Dı,I)
F(1,3)
F(1,2)
F(2.3)
F(12) ((23)) F(1.))
((I) Y())
Y())
X(I y())
(h) Augz, (D2.I)
(i) Augi, (D2.
( Aug,, (D2.I)
Figure 5: An example that given the observational distribution, soft interventions can distinguish the given two causal graphs while hard interventions cannot. (a), (b) are the ground truth causal graph D1, D2 respectively with intervention targets I {0, {Y), }, [X, Y }:: (c), (d) are the augmented MAGS under soft interventions for Dj and D2 respectively; (e), (f), (g) are the Z-augmented MAGs under hard interventions for Di; (h), (i), (i) are the Z-augmented MAGs under hard interventions for D:2. Notice that Dj and D: are not I-Markov equivalent when is soft because (F. Y) have different unshielded collider status in the corresponding augmented MAGs. However, they are I-Markov equivalent when is hard because their Z-augmented MAGs corresponding to the same domains all satisfy the 3 conditions.
G.3 Incompleteness of the Learning Algorithm
In this section, we will present an example in Figure to show that Algorithm is not complete, i.e., for some causal graphs and intervention targets I. there exist circles marks in the Z-augmented graph returned by Algorithm] T that can be an arrowhead in the Z-augmented MAG of a causal graph that is Z-Markov equivalent, and arrowtail in another I-augmented MAG. Let consider the causal graph DD as shown in Figure 6a with intervention targets I = [I, = { {X2) ). In = {. Here we use the domain index as the superscripts for simplicity. The Z-augmented MAGs Augr, (D, I) and Augr, (D, (D, I) are shown in Figure 6b and Figure 66 respectively. The I Z-augmented graphs G1, (D, and 91, (D, () learned by Algorithm are shown Figure 6d and Figure respectiivl.. x((1)
(1) and x(2) + xx(2)
oriented by the inducing path rule. However, our algorithm cannot orient
35

---

x x and x² x Without loss of generality, let's consider X 0- X3 in 91, (D). Suppose that there exists graph D' such that there is X + X3 in 91 (D', Since we have x²2) x3² in 91, (D', II) this indicates that there is inducing path and directed path from X, to X3 in D'x and thus in D' as D' is a subgraph of 'D' The bidirected edge between x(") and x3" in 9r, (D',I) II) indicates that the directed path from X4 to X3 is broken in X= This can only happen when X2 is in the directed path between X, and X3 in D' and thus D'x as removing the edges into X4 does not affect its descendants. Therefore, X₃ has child other than X3 and is an ancestor of X2- Nevertheless, X(2) has only one possible child x²²) in 91, (D, Thus, the supposition does not hold. For the same reason, we can orient the circle mark in X a-> x in 9r, (D. These circle marks can only be oriented by comparing the graphical structures across domains. We need extra orientation rules to catch them.
X1
X4 Xs
(a) Example graph D
F
F
x
_
+ [
(1) x
x
X (2)
X (2)
(
x!
(b) Augr, (D,I)
(c) Augr, (D,I)
F
x
x + (1) - (1) (1)
x x
x1
X
x
x!
(d) 91 (D,I)
(e) (D,I)
Figure 6: An example to show that Algorithm| I is not complete. (a) is the ground truth causal graph D with intervention targets
{(x2) {Xa]]: (b) and (c) are the Z-augmented MAG under I and In respectively; (d) and (c) are the domain-speciff Z-augmented graphs learned by Algorithm ] under I and 12 respectively. The proposed Algorithm [ cannot recover the circle marks XX, and X4, but there does not exist causal graph that has an arrowhead at the same places in their I-augmented MAGS.
G.4 Limitations, Future Work, and Broader Impact
Limitations: While our work provides general characterization of Z-Markov equivalence classes, the resulting representation is a tuple of augmented graphs, rather than single unified graph. This makes the characterization less straightforward interpret. In addition, although our proposed algorithm is sound, it is not complete. We just illustrate this limitation with a concrete example provided in Appendix G.3
This work opens several promising directions for future research. First, our empirical results suggest that hard interventions tend to be more informative than soft interventions. It would be valuable to formally analyze this observation and establish theoretical conditions under which this holds. Additionally, while we have proven the soundness of our learning algorithm, extending with additional orientation rules to achieve completeness remains an open challenge. Finally, our current framework assumes full access to interventional distributions. Developing methods that can learn causal graphs from limited interventional samples is an important direction for making these approaches more practical in real-world settings.
Future Work:
This work contributes to advancing the theoretical and algorithmic foundations of causal discovery, with the potential to improve pecision-making/causall inference in critical domains
Broader Impact:
such as healthcare, economics, genomics, and social sciences [Sharma al.) 2022 Zhou al.
2022 Hernán and Robins 2016 Sachs et al. 2005 Taubman et al. 2014
Lee 2008 Belyaeva et al.
36

---

2021]. By combining observational and interventional data, the proposed methods can reduce reliance on sarge-scale experimentation, making causal analysis more accessible data-scarce or resource- limited settings. This could empower practitioners to build more reliable models for understanding complex systems, ultimately benefiting scientific discovery and evidence-based policy-making.
However, the use of causal discovery methods also carries risks. Incorrect or biased causal infer- ences-whether due data limitations, modeling assumptions, or algorithmic shortcomings-coull lead to misguided conclusions, especially in sensitive applications like healthcare or policy-making. Furthermore, there risk of misuse if these methods are deployed without adequate validation or oversight, potentially reinforcing harmful biases or supporting flawed decision- making processes.
To mitigate these risks, it is crucial to promote transparency, reproducibility, and the inclusion of domain expertise when applying these methods. Future work should also explore techniques to quantify uncertainty in causal conclusions, improve model interpretabilltyy and develop guidelines safeguards for responsible deployment.
37

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We discuss this in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss this in Appendix G.4
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
38

---

Justification:
We discuss this in Section 3 Section
Section
5
Section 6
The proofs are in
the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We discuss this in Appendix F
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
39

---

Answer: [Yes]
Justification:
We discuss this in Appendix F The instructions are provided in the Readme
file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/ppp ctt.ccccppuul ctc/public/gguudee /eeggudddsseCeebbbinninna ssiliiiiccyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We discuss this in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We discuss this in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
40

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We discuss this in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss this in Appendix G.4
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
41

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not use any dataset or model that has this concern.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the assets and mention the license explicitly in the paper and Readme of the code.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets.papersstt package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
42

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the descriptions in the Readme file.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/cooe/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
43

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM is merely used for editing purposes in this work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
44


Reviews:
[{"review_id": "13vXlnaKkd", "reviewer": "Reviewer_HFqZ", "summary": "The paper considers interventional equivalence class to the setting where hard interventions are available, in the presence of unobservables.  The core contributions of the paper are:\n\n1) generalized do-calculus that relates pair of interventional distributions\n2) Twin-Augmented MAG (TAM) that embeds a pair of intervention graphs with F-nodes\n3) A graphical characterization of I-Markov equivalence class via TAM \n4) Compression of k TAMs which preserves do-calculus constraints\n5) An FCI-like discovery algorithm with new orientation rules", "questions": "“Revisiting the General Identifiability Problem” (Kivva et al., 2022) and “Minimum Intervention Cover of a Causal Graph” (Kandasamy et al., 2019) are examples of papers that derive constraints across multiple interventions using do-calculus (where the graph is given). It is unclear whether the TAM invariances introduce new algebraic equalities or re-express known identifiability constraints graphically. I understand the problem statements are different (they are inverse problems in some sense), but very closely related.\n\nSince the paper deals with invariances of do-calculus across interventional distributions, besides the h-faithfulness requirement does the algorithm also needs positivity requirement?\n\nNumerous inconsistencies suggest the manuscript was rushed.  Some core concepts are used before being defined.  I request the authors to proof-read the manuscript thoroughly.\n\nLine 49: The bidrected edge is used before defining it.\n\nLine 129: Inducing path is used before definition.  Does ancestor include the vertex?  I assume it is inclusive but it should be clear.\n\nLine 131: What is \"almost directed cycle\"? -- please define it in the main paper or point out to the right section in Appendix.\n\nLine 179:  In Rule 2, conditioning on z is not necessary after intervention on z.  It is redundant as z is already in intervention.\n\nLine 197/199:  A minor suggestion:  Equate them to $P_{ \\mathbf{I} \\cup \\mathbf{J}} (\\mathbf{y} | \\mathbf{w})$ / $\\mathbf{P}_{ \\mathbf{I} \\cap \\mathbf{J}} (\\mathbf{y} | \\mathbf{w})$.  I feel the proof maybe easy to derive with this addition.\n\nLine 217: R_I, R_J, K_I, K_J first appear inside Proposition 3.2 yet is reused later. Move them to a global definition.\n\nLine 229: \"We introduce the augmented pair\". -- It appears a new concept is being introduced, though is rightly pointed out that the notion of augmented pair and F-nodes is known in the literature.\n\nLine 232: Superscripts (I) (J) are used without explanation.\n\nLine 235: K should be in bold.\n\nLine 258: Please add a short explanation regarding how to construct the MAG.  This would improve the flow.\n\nLine 259:  MAG and Twin are in math mode.  Please use \\mathrm or appropriate styling for all such text/abbrevation inside math mode.\n\nLine 260:  The definition of S is confusing.  I understand S is defined inside Augmented pair definition but S is undefined here.\n\nLine 263:  In $Y^{(\\mathbf{I})}$ what is Y?", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper provides the first I-Markov equivalence characterization for hard interventions in the presence of unobservables.  The paper is well-structured starting with a modified version of do-calculus, to equivalence characterization, to compression of I-MAG, and finishing with a learning algorithm.  Proofs are detailed and appear sound.  Although the experiments are small-scale and synthetic (which is probably unavoidable), they quantify a clear reduction in equivalence-class size when moving from soft to hard interventions, illustrating noticeable benefit.\n\nWeaknesses:\nThe contribution feels incremental: apart from the twin-augmented MAG, most machinery (augmented graphs, orientation rules, do-calculus derivations) already exists in the literature.  The hard intervention with latents is an important problem but the conceptual leap in my opinion is modest when viewed against two decades of equivalence class research.", "was_revised": true, "final_justification": "The rebuttal and discussions clarified some of my technical concerns, and I considered upgrading my score. However, I still found the manuscript difficult to read and believe it requires substantial revisions. Therefore, I will maintain my original score.", "rebuttal": "Thank you for the thoughtful assessment and the detailed style notes.\n\n**Novelty based on existing machineries**\n\nPrior augmented-graph formalisms ([1], [2], [6], [7]) cover **soft** interventions only or assume no latents.  Hard interventions add the *surgical* constraint “no incoming edges”, which induces **new cross-environment distributional invariances** (Proposition 3.2) that cannot be captured by those graphs. Nevertheless, the presence of latents would create non-local dependencies and can be affected by hard interventions on remote nodes. Our twin augmented MAG (TAM) embeds these additional constraints via the $F$ node edges and is thus more expressive than prior augmented graphs. This extension is what allows us to prove the first graphical characterisation of an $\\mathcal{I}$-MEC under hard interventions with latents —- a result that did not exist.\n\n**Additional related works**\n\nBoth papers assume the *graph is known* and derive algebraic constraints to decide the identifiability of *parameters (if interventional distributions can be computed from the observational distribution)* (Kivva [4]) or a minimum intervention *cover* (Kandasamy [5]). Our setting is like the **inverse** problem: our Twin-Augmented MAG translates cross-environment distributional invariance statements into d-separations without assuming the graph. These invariances are then used to (i) characterise the $\\mathcal{I}$-MEC (Thm 4.7) with a compact graphical representation and (ii) drive Algorithm 1 for structure learning based on the graphical constraints corresponding to the invariances. Thus the two lines of work are complementary: one answers ‘Which causal effects are computable if the graph is known?’; the other answers ‘Which graphs are compatible with the data across multiple hard-intervention settings?’ We will include these additional related works and add this contrast at the end of Section 2.\n\n**Positivity assumption for the learning algorithm**\n\nIn theory, Algorithm 1 does not require a strict global positivity assumption. All results rely solely on h-faithfulness. We are aware that  “strictly positive distribution” is added in some works on discovery as a convenience. This is because *within the space of strictly positive parameterisations* the subset that violates Faithfulness sits on algebraic varieties of lower dimension—hence has Lebesgue measure 0 (see [3] and many follow-ups). In practice, with finite data, a zero or near-zero cell makes test statistics undefined or unstable, so implementations often impose minimum-count rules even when the theory would allow the zero.\n\nWe notice that the positivity assumption is required for identifiability (For example, [4], [5]). This is because that the manipulation of numerical expression explicitly require the denominator to be strictly positive. By contrast, structural discovery uses only qualitative independence relations. As long as we can evaluate a test where $P(S)>0$, no global support assumption is required.\n\n**Style/Notation issues**\n\nWe will systematic­ally reorder definitions so every concept precedes first use for bidirected edge, inducing path, ancestor, and almost directed cycle. We will also fix any typos in the revision.\n\nFor the conditioning set in Rule 2, Line 179, we add $Z$ explicitly due to its clear connection with the corresponding $F$ node d-separation statements, which require conditioning although it is not necessary. We will add a clarifying comment in the revised manuscript.\n\nIn line 197/199, we will take the suggestion to add $P_{ \\mathbf{I} \\cup \\mathbf{J} }(\\mathbf{y}|\\mathbf{w})$ to the equations to make it easier to understand. In the proof, we also show that using $P_{ \\mathbf{I} \\cup \\mathbf{J} }$ as the intermediate distribution is both necessary and sufficient to derive the graphical constraint.\n\nWe will make ${\\mathbf{R}_{\\mathbf{I}}}$ and so on a global definition to avoid repeated definitions. \n\nWe will use `\\mathrm` for notation of MAGs and twin augmented graphs.\n\nFor the definition of Augmented pair graph, we will add a sentence to indicate that $F^{(\\mathbf{I}, \\mathbf{J} )}$ is an auxiliary node for a pair of targets $\\mathbf{I}, \\mathbf{J}$. The superscript shows the targets. We omit the superscript when it is clear from the context which pair of targets we are looking at.\n\nFor the definition of twin augmented MAG, we will add a short sentence in Section 2 where we describe maximal ancestral graphs, on how to construct a MAG over an ADMG. In Line 260, we will replace $S$ with $V\\in \\mathbf{V}$ as a node such that $V^{(\\mathbf{I})}$ or $V^{(\\mathbf{J})}$ is adjacent to $F^{(\\mathbf{I}, \\mathbf{J} )}$ in $\\mathrm{MAG}(Aug_{ (\\mathbf{I}, \\mathbf{J}) }(\\mathcal{D}))$. \n\nIn Line 263, $Y$ is any node in $\\mathbf{V}$. We intended to clarify that any separation statement like $F \\mathrel{\\perp\\mspace{-10mu}\\perp} Y^{(\\mathbf{I})}$ for $Y \\in \\mathbf{V}$ is not directly testable from comparing the CIs using just $P_{\\mathbf{I}}, P_{\\mathbf{J}}$. We can only decide this separation to be true when both $F \\mathrel{\\perp\\mspace{-10mu}\\perp} Y^{(\\mathbf{I})}$ and $F \\mathrel{\\perp\\mspace{-10mu}\\perp} Y^{(\\mathbf{J})}$ hold and that motivates our construction of Twin augmented MAGs by adding extra edges to the $F$ node.\n\n**MAG construction example**\n\nSection 4 will gain an example (figure now in App. D) showing how we construct twin augmented MAGs starting from an ADMG.\nSection 5 will gain an example (figure now in App. E) showing how we compress twin augmented MAGs to an $\\mathcal{I}$-augmented MAG. We believe this, together with the reordered definitions, will substantially improve readability.\n\n**We appreciate the constructive feedback. We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.**\n\nReferences:\n\n[1] Eaton, Daniel, and Kevin Murphy. \"Belief net structure learning from uncertain interventions.\" *Journal of Machine Learning Research* 1 (2007): 1-48.\n\n[2] Pearl, Judea. \"Models, reasoning and inference.\" Cambridge, UK: CambridgeUniversityPress 19, no. 2 (2000): 3.\n\n[3] Robins, James M., Richard Scheines, Peter Spirtes, and Larry Wasserman. \"Uniform consistency in causal inference.\" *Biometrika* 90, no. 3 (2003): 491-515.\n\n[4] Kivva, Yaroslav, Ehsan Mokhtarian, Jalal Etesami, and Negar Kiyavash. \"Revisiting the general identifiability problem.\" In Uncertainty in Artificial Intelligence, pp. 1022-1030. PMLR, 2022.\n\n[5] Kandasamy, Saravanan, Arnab Bhattacharyya, and Vasant G. Honavar. \"Minimum intervention cover of a causal graph.\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, pp. 2876-2885. 2019.\n\n[6] Yang, Karren, Abigail Katcoff, and Caroline Uhler. \"Characterizing and learning equivalence classes of causal dags under interventions.\" In International Conference on Machine Learning, pp. 5541-5550. PMLR, 2018.\n\n[7] Kocaoglu, Murat, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. \"Characterization and learning of causal graphs with latent variables from soft interventions.\" Advances in neural information processing systems 32 (2019)."}, {"review_id": "8Gd3fk2vpH", "reviewer": "Reviewer_4BQV", "summary": "The paper discusses the problem of learning a causal graph from interventional data. In particular, the authors consider the scenario where multiple datasets — each produced by a different hard intervention — are available to practitioners. The authors claim to generalize do-calculus and propose a novel causal discovery algorithm, of which they prove the soundness.", "questions": "- In Proposition 3.2, what do you mean by \"tuple of hard-interventional distributions\"? Is it a set of different interventions or is it a unique intervention $\\mathbf{I}\\in\\mathcal{I}$ as it seems from your notation? If it is a unique intervention, how does it differ from Theorem 3.1? Otherwise, if it is a set of interventions, does the rule hold on all interventional distributions or are you considering the distribution where all interventions are performed?\n- Why has the method not been compared with other existing interventional causal discovery frameworks? For instance, I-FCI, psi-FCI, JCI, GIES, IGSP. It would help my evaluation if the authors could expand on this.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- To the best of my knowledge, the introduced algorithm is novel, as it builds on a novel and more general characterization of do-calculus introduced by the authors in this work.\n\nWeaknesses:\n- I had problems understanding the core points of the paper. Theoretical results in Sections 3, 4, and 5 lack an intuitive discussion or examples. For instance, a graphical representation of the concepts of augmented pair graphs and twin augmented MAGs could have clarified a quite heavy-to-read notation. To be entirely honest, do-calculus is not one of the core aspects of my expertise, and I am consequently adjusting my confidence with a low score.\n- Related works reference several existing techniques for interventional and observational causal discovery. However, the authors only discuss the relation between their proposed method and FCI. The experimental section does not compare their method with any existing method.", "was_revised": true, "final_justification": "The authors acknowledged the significant presentation problems in the paper. Already in the rebuttal, they improved the discussion of their theoretical results. Together with the aspects mentioned in the rebuttal of reviewer QBQf, the next revision of the paper should be sufficiently readable. The rebuttal convinced me of the novelty of their work.", "rebuttal": "**We thank the reviewer for the helpful comments and apologize for the parts that were hard to follow.**\n\n**Clarification of the main paper**\n\nWe agree the exposition can be improved. Due to the page limitation, we had to move some figures that illustrate the concepts to the appendix which made the main text less readable. In the revision we will: 1) move Figure 1 in App. D to Section 4 to illustrate the  construction of **twin-augmented MAG** and highlighting the extra edge that captures the hard-intervention constraints; 2) move Figure 2 to Section 5 to show how we construct $\\mathcal{I}$-augmented MAGs by combining twin-augmented MAGs. A short narrative paragraph will precede each theorem to walk the reader through the intuition before the formal statement. We conclude the main idea of this paper below.\n\n **Background and our contribution:**\n\nLearning a causal graph from **multiple hard-intervention distributions** has two pillars:\n\n(i) *do-calculus*, which maps cross-environment invariance statements to graphical separations;\n\n(ii) *equivalence-class characterizations*, which say **exactly** what can be learned from those invariances.\n\nFor observational data this yields the well-known **Markov Equivalence Class (MEC)**.\n\nFor interventional data, Hauser & Bühlmann [1] extended the idea to the **I-MEC**, but only for *observed* DAGs with no latents; later work (Yang et al. [2]) unified hard/soft interventions in the same fully-observed setting, and Kocaoglu ’19 [3] handled **soft** interventions with latent variables via an *augmented MAG*.\n\nOur paper closes the remaining gap: **hard interventions *with* latents**.\n\nBecause a hard cut severs every parent of the target, its effect can be *global* (the dependencies between non-adjacent nodes can be affected) when hidden confounders exist (see example in Line 48). Such surgical property provides us with more testable conditional independence statements and which therefore, the augmented MAG structure in [3] fails in our setting. \n\nWe therefore:\n\n1. **Generalize do-calculus (Rules 1–4)** under hard interventions (Prop. 3.2) and define h-faithfulness (Def. 6.1) accordingly as the assumption for the learning algorithm. The generalized do-calculus rules map the testable invariances between hard-interventional distributions to the graphical constraints on the (mutilated) graphs.\n\n2. Build the **augmented pair graph** (Def. 4.3) and further, the **twin-augmented MAG (TAM)** (Def. 4.5) (Figure 1 in App. D shows a detailed example of how we construct TAMs from the original ADMGs through augmented pair graphs), which preserves *all testable* invariances without mutilating the original ADMG.\n\n3. Prove **Thm 4.7**: a complete graphical characterisation of the **$\\mathcal{I}$-MEC** based on the graphical structures of the TAMs—the first such result for hard interventions under latents.\n\n4. Compress the TAMs that contain the same interventional domain into a single, lean **$\\mathcal{I}$-augmented MAG** (Def 5.1) (Figure 2 in App. E shows a detailed example of how we construct the $\\mathcal{I}$-augmented MAGs). The $\\mathcal{I}$-augmented MAGs are more compact and preserve all the testable separation statements. The union graph of all the $\\mathcal{I}$-Markov equivalent $\\mathcal{I}$-augmented MAGs forms the $\\mathcal{I}$-essential graphs (Def. B.8) which become the ultimate target of our discovery procedure.\n\n5. Derive **Algorithm 1**, an FCI-style learner that outputs a tuple of $\\mathcal{I}$-augmented graphs (which represents a set of valid ADMGs) using FCI orientation rules together with additional, sound orientation rules (example walk-through in App. F, Figure 3).\n\nTogether, these steps establish what is fundamentally learnable under hard interventions and provide a learning algorithm to achieve it. We will improve the main text, especially introduction and related works accordingly, to improve readability.\n\n**No comparison with other interventional methods**\n\nUnlike most causal discovery algorithms, the goal of our algorithm is *not* to return a single causal graph but a tuple of $\\mathcal{I}$-augmented graphs that entail **$\\mathcal{I}$-Markov equivalent graphs**; none of the listed algorithms outputs that object.  Concretely, **I-FCI [3] (known targets)/$\\psi$-FCI [4] (unknown targets)** assume soft interventions and cannot exploit the additional invariance constraints; applying them to our setting recovers a *larger* MEC (App. G). They use a single augmented MAG as the learning objective. **JCI** claims it works for any interventions but it's overly simplistic; the learned PAG is less informative (in [4] App. D shows that $\\psi$-FCI can learn more than JCI). **GIES, IGSP** are score-based and aim at learning a *single* DAG under known targets; they neither guarantee inclusion-minimality nor provide equivalence-class certificates. Nevertheless, scores-based methods usually impose parametric assumptions like linear function or additive Gaussian noise to the causal models. Such methods are not robust when the underlying mechanism deviates from those assumptions. Additionally, GIES and IGSP assume no latents and therefore cannot return ADMGs. Because the outputs are of different types, a direct performance metric is unavailable to measure the performance of the methods; instead we reported a *size* comparison (Table 2) that quantifies empirically how much smaller the $\\mathcal{I}$-MEC is vs. the soft $\\mathcal{I}$-MEC produced by I-FCI/$\\psi$-FCI. To compare with GIES and IGSP, we use the graph $[X\\rightarrow Z \\rightarrow Y, Z\\leftarrow L \\rightarrow Y]$ where $L$ is a latent variable. We take 100k samples from observational distribution and 100k samples from $P_Z$. For the setting where $X, Y, Z$ are binary, we generate a random CPT based on the true graph and sample from it. GIES returns $[Y\\rightarrow Z \\rightarrow X]$ which is completely wrong. IGSP returns $[X\\rightarrow Z \\rightarrow Y, X\\rightarrow Y]$ which is the observational MAG of the true graph, but it cannot tell anything to judge if there is a latent confounder between $Z, Y$. Under the same setting, when the simulated dataset is from a linear Gaussian SEM, both GIES and IGSP outputs $[X\\rightarrow Z \\rightarrow Y]$ which catches the right causal ordering but still is wrong and does not belong to the MEC. In both settings, our algorithm is able to learn the graphs illustrated in Figure 3 (k) which preserve information from both domains. We use the python implementation of GIES by Olga Kolotuhina and Juan L. Gamella. The IGSP implementation is from the `causaldag` package.\n\nWe will make this distinction explicit in an extra sub section in App. G with the detailed experiment settings. We will also add the small scale experiments to compare the outputs of each method in the revision.\n\n**Meaning of “tuple of hard-interventional distributions”**\n\nLet $ \\mathcal{I} = \\lbrace \\mathbf{I}\\_1, \\ldots, \\mathbf{I}\\_m \\rbrace $ be the set of intervention targets. \nThe “tuple” is the collection $ (P^{(1)}, \\ldots, P^{(m)}) $\nwhere $P^{(j)}$ is the interventional distribution under the intervention target $\\mathbf{I}\\_j$. \nProposition 3.2 is a generalization of Theorem 3.1. More specifically, Theorem 3.1 tells under what graphical constraints one can adjust the intervention or conditioning set from a given distribution. Proposition 3.2 generalizes the rules to any pair of arbitrary interventional distributions ($P_{\\mathbf{I}}$ and $P_{\\mathbf{J}}$ in the main paper). It is saying that for any pair of interventional distributions, the invariance statements hold under the corresponding graphical constraints. The new set of rules make the comparisons of testable invariances explicit.\n\n**Once again, thank you for the detailed feedback. We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.**\n\nReferences:\n\n[1] Hauser, Alain, and Peter Bühlmann. \"Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs.\" *The Journal of Machine Learning Research* 13, no. 1 (2012): 2409-2464.\n\n[2] Yang, Karren, Abigail Katcoff, and Caroline Uhler. \"Characterizing and learning equivalence classes of causal dags under interventions.\" In International Conference on Machine Learning, pp. 5541-5550. PMLR, 2018.\n\n[3] Kocaoglu, Murat, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. \"Characterization and learning of causal graphs with latent variables from soft interventions.\" Advances in neural information processing systems 32 (2019).\n\n[4] Jaber, Amin, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. \"Causal discovery from soft interventions with unknown targets: Characterization and learning.\" Advances in neural information processing systems 33 (2020): 9551-9561."}, {"review_id": "nYRZ1QYPuZ", "reviewer": "Reviewer_QBQf", "summary": "The paper characterizes $\\cal I$ -Markov equivalence class for a given hard intervention set $\\cal I$, by generalizing do-calculus under hard interventions. Prior work established similar results for only soft interventions, and to my knowledge, the present work is the first paper to extend those results specifically to hard interventions, leveraging the additional conditional independence constraints imposed by the hard interventions. Specifically, two graph structures, twin augmented MAG and $\\cal I$-augmented MAGs, are proposed to capture $\\cal I$-Markov equivalence (for hard interventions) graphically. In addition, a sound learning algorithm is proposed for finding this equivalence class. It is empirically shown that the $\\cal I$-MEC under hard interventions is in general significantly smaller than the one under soft interventions, which validates the motivation of the paper to address the gap (for hard interventions) in the literature.", "questions": "### Questions\n* If I understand correctly, the proofs only require the surgical properties of a hard intervention, that is intervened node has no parents left. A hard intervention, as common in literature, is defined as the deterministic do intervention via setting the intervened variables to constants. I’d like to ask whether the results are still valid for “stochastic hard interventions”, sometimes called perfect interventions. A remark about this could be helpful.\n* Augmented pair graph. I’m curious, are you confident that the “augmented graph” construction in [19] is insufficient for developing the results in this paper? In other words, why is it truly necessary to extend that definition to “augmented pair graph”? This is not a criticism but rather an attempt to digest the results.\n* Experiments: Were you able to run experiments for actually learning the graphs, for small graphs perhaps? If I’m not mistaken, the experiments in the paper focus only on the size of I-MEC. \n* h-faithfulness: Do you have any comment on how strong this assumption is? I understand that some faithfulness assumption is required for CI-based causal discovery, I’m just curious if a milder form would still be sufficient (e.g., adjacency faithfulness is milder than standard faithfulness in classical causal discovery)\n\n**Minor points**\n- Given the use of “I-MEC” in prior work and the hard-intervention specific nature of this paper, I wonder whether a distinctive name, e.g., I-Hard-MEC, would have been more appropriate.\n\n- Line 185: A soft intervention, in general, leaves the interventional graph the same. However, as a special case, it can change the graph, e.g., cutting one parent while leaving the other parents intact.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### strengths\n* Characterizing the interventional MEC under hard interventions, which the paper shows to be significantly smaller than the one for soft interventions in most cases, is surprisingly a hitherto unknown problem, to my knowledge. For this reason alone, I think the paper has strong contributions to causal discovery literature. The learning algorithm is not perfect (see my comments below); yet, the characterization results and the well-thought-out limitations discussion (in the appendix) suggest that this paper might draw significant attention and serve as the groundwork for future follow-up papers in the causal discovery community.\n* The paper is mostly well-written. Due to the theoretical nature, some parts in the main body might be hard to grasp, though the appendix has plenty of explanations and examples to answer the majority of the possible questions of a reader.\n\n### weaknesses\n* Algorithm 1 is sound. However, i) it is not complete, ii) it requires intervention targets to be known, which is not always the case (e.g., off-target effects), iii) (minor) the runtime/complexity can be expensive, though it is approximately the same order as the standard FCI algorithm.  \n* This is a minor weakness of the paper and more of a comment since it mainly stems from the space limitation (but also from some design choices)---all graphical descriptions (of twin augmented MAGs and $\\cal I$-augmented MAGs) are deferred to the appendix. This makes it more difficult to follow the results for the non-expert reader, e.g., the discussion in line 322 about learnable structures requires Figure 1c in the appendix. I trust that some figures will be moved to the main body in the final version of the paper. The reason I also say it’s a design choice is that, in my opinion, figures would have been more useful to convey the constructions and ideas than brief experiment results in the main paper (which is important but can be just explained more briefly by referring to results in the appendix).", "was_revised": true, "final_justification": "I've had an initial positive review, with score 5 (please see my initial review).\n\nDuring the rebuttal process, I have also read the other reviews and authors’ responses. I think the “Background and our contribution” walk-through response to Reviewer 4BQV is a good summary for improving the exposition of the paper. I trust that with the promised changes—these explanations and adding some figures to the main text— the revised paper will be an easier read, and will showcase the importance and contributions better (which I already appreciate, as reflected in my positive view).\n\nThus, I maintain my positive score and recommend acceptance.", "rebuttal": "**We thank the reviewer for the encouraging assessment and the detailed, constructive questions.**\n\n**Limitation on the current algorithm**\n\nThe learning algorithm we proposed is incomplete and requires the knowledge of the intervention targets. We leave these problems as future extensions. The algorithm can be expensive in runtime when the graph is large. Some techniques to speed up FCI (for example [1]) transfer directly to our algorithm..\n\n**Lack of visualizations in the main text**\n\nDue to the page limitation, we have to move the figures of examples with detailed explanation to the appendix. We will put some of them in the main text for the revision to better convey the concepts. Specifically, we will move Figure 1 in App. D on a detailed example of how to construct the twin augmented MAGs from the ADMGs to Section 4. We will also move Figure 2 in App. E on a detailed example of how to construct an $\\mathcal{I}$-augmented MAG by combining the twin augmented MAGs and how it preserves the desired separations, to Section 5.\n\n**Clarification on hard interventions**\n\nThe results are still valid for stochastic hard interventions. In deterministic interventions there is no randomness left in $X$, so conditioning on $X$ is harmless. In stochastic interventions $X$ does carry randomness, and putting it in the conditioning set may open collider paths (or block active paths), changing the independence structure. Therefore, the intervention target being in the conditioning set in d-separation statements should not be done if it is stochastic. We do that because there is no randomness left in the node to establish dependencies.\n\n**Necessity of augmented pair graphs**\n\nWe start by introducing the generalized do-calculus rules under hard interventions. The rules map testable distributional invariances into graphical constraints which can be used for discovery. The augmented pair graph shows how these invariance statements are preserved when we are comparing two domains, especially for those statements across domains. Based on the augmented pair graphs, we further construct twin augmented MAGs and then put them together in a domain-centric $\\mathcal{I}$-augmented MAG as the ultimate graphical representation. The $\\mathcal{I}$-MAG in [3] integrates all domains into one graph. This is not applicable for soft interventions that does not modify the original causal graph. In our case, since hard interventions will modify the graphs, we have to use the domain-centric graphs to capture different graph skeletons in different domains. Therefore, while the $\\mathcal{I}$-augmented MAGs are the ultimate graphical representation we use to characterize the equivalence class, the augmented pair graph is the first step of the construction of $\\mathcal{I}$-augmented MAGs which differs from the case in [3] as the invariances statements under soft interventions can be preserved in one graph. This can also be seen from the set of do-calculus rules under soft interventions ([2]) which differs from the rules under hard interventions.\n\n**Experiments on learning small graphs**\n\nThe experiments are focusing on empirically compare the size of $\\mathcal{I}$-MEC under hard and soft interventions to show that hard interventions are, in general, more powerful than soft interventions in learning the causal graphs. The reason we did not **compare** with other methods that allows interventional data is that the output types vary and there is no unified global *accuracy* metrics that can measure the performance. For our learning algorithm, it returns a set of $\\mathcal{I}$-augmented graphs, which represents a set of ADMGs. To witness, given an ADMG, we can construct the twin augmented MAGs and further $\\mathcal{I}$-augmented MAGs following the steps in Def. 4.5 and Def 5.1. If the oriented arrowheads or arrowtails align with $\\mathcal{I}$-augmented MAGs, this ADMG is entailed by the algorithm's outputs. \n\nI-FCI [3] (this is named by some follow-ups) or $\\psi$-FCI [4] returns a single augmented graph called I-PAG. Our experiments in App. G implicitly shows that Algorithm 1 performs better than them given that Algorithm 1's outputs entail a smaller size of $\\mathcal{I}$-Markov equivalent ADMGs. Other interventional causal discovery methods aim at returning one single graph. Such methods (for example, [6], [7]) often impose parametric assumptions on the SEMs like linear causal model or additive Gaussian noise and so on. Such methods degrade sharply when the assumptions do not hold. Additionally, they are not compatible with latents. Their output graph is not guaranteed to fall into the $\\mathcal{I}$-MEC either. Due to the various output types, we did not **compare** the **performance** of Algorithm 1 with other methods. We will add some small scale experiments to show how our learning algorithm works in the revision.\n\n**Faithfulness assumption**\n\nWe recognize that there are weaker faithfulness assumptions. However, the soundness of Algorithm 1 requires h-faithfulness. The $\\mathcal{I}$-MEC we defined is based on the generalized do-calculus rules and so as the learning algorithm and hence h-faithfulness is minimal for the algorithm to be sound. \n\nLike classic faithfulness, the set of parameterizations that *violate* h-faithfulness has Lebesgue measure zero for standard SEM families with continuous noise if we consider linear models; i.e., it holds *generically* [5] (it also holds for many other models, see follow-ups of [5]).  It is therefore no stronger in a measure–theoretic sense than ordinary faithfulness, but it is stronger *logically*: it rules out a few additional, finely-tuned parameter combinations that would create the extra cancellations specific to our Rules 1-4—those cancellations correspond exactly to our new Rules 1–4, so dropping h-faithfulness would break soundness. We can also put it this way. Imagine a causal graph under faithfulness assumption. It could be the case that for certain conditioning values $Z=z$, two variables $X$ and $Y$ that are d-connected are independent. While faithfulness covers the case that $X$ is dependent with $Y$ given $Z$ (when the dependency metric is averaged over all $z$), h-faithfulness is similar to saying $X, Y$ are dependent given every $Z=z$. This analogy is exact if the intervened node is a source node, but we believe it gives some insight on the leap from observational faithfulness to h-faithfulness\n\n**Name of MEC**\n\nWe will adopt a clearer term like $\\mathcal{I}$**-Hard-MEC** and mention its relation to prior “MEC” work in the revision.\n\n**Soft intervention remark**\n\nWe will correct the sentence to: “A *typical* soft intervention leaves the graph unchanged, but special cases (e.g., edge deletion) are possible; our results do not rely on such deletions.”\n\n**Again, thank you for the positive evaluation and the helpful suggestions. We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.**\n\nReferences:\n\n[1] Colombo, Diego, Marloes H. Maathuis, Markus Kalisch, and Thomas S. Richardson. \"Learning high-dimensional directed acyclic graphs with latent and selection variables.\" The Annals of Statistics (2012): 294-321.\n\n[2] Correa, Juan, and Elias Bareinboim. \"A calculus for stochastic interventions: Causal effect identification and surrogate experiments.\" In Proceedings of the AAAI conference on artificial intelligence, vol. 34, no. 06, pp. 10093-10100. 2020.\n\n[3] Kocaoglu, Murat, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. \"Characterization and learning of causal graphs with latent variables from soft interventions.\" Advances in neural information processing systems 32 (2019).\n\n[4] Jaber, Amin, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. \"Causal discovery from soft interventions with unknown targets: Characterization and learning.\" Advances in neural information processing systems 33 (2020): 9551-9561.\n\n[5] Robins, James M., Richard Scheines, Peter Spirtes, and Larry Wasserman. \"Uniform consistency in causal inference.\" Biometrika 90, no. 3 (2003): 491-515.\n\n[6] Hauser, A. & Bühlmann, P. “Characterization and Greedy Learning of Interventional Markov Equivalence Classes of DAGs.” JMLR 13: 2409 – 2464, 2012.\n\n[7] Wang, Y., Solus, L., Yang, K. & Uhler, C. “Permutation-based Causal Inference Algorithms with Interventions.” NeurIPS 2017."}]

Author rebuttal:

Meta-review: This paper makes a notable contribution by characterizing interventional Markov equivalence under hard interventions with latent variables, a problem not previously resolved. The authors introduce the Twin-Augmented MAG (TAM) and I-augmented MAG, establish a complete graphical characterization of the I-MEC in this setting, and develop a sound discovery algorithm with new orientation rules. Empirical evidence further shows that hard interventions yield smaller equivalence classes than soft interventions. Together, these results fill an important gap and are technically novel, rigorous, and well-motivated.

The main weakness concerns clarity and accessibility of presentation. The manuscript is notation-heavy, introduces definitions after use, and lacks intuitive figures. In addition, as Reviewer HFqZ noted, the technical advances may appear incremental without a clearer exposition of the proof techniques and their distinction from prior work. I strongly encourage the authors to follow through on their promised revisions: moving key figures to the main text, reordering definitions, expanding the related work discussion to highlight novelty, and improving the overall exposition. Addressing these points will substantially enhance readability and better convey the significance of the contribution.
Decision: Accept (poster)