Causal discovery from observational and interventional data across multiple environments
Authors: Adam Li
Amin Jaber
Elias Bareinboim
Venue: NeurIPS 2023 poster (2023)
Keywords: causal inference
causal discovery
transportability
multi-domain learning
TL;DR: A causal discovery algorithm for learning from a mixture of observational and interventional data collected across multiple domains.

Abstract: A fundamental problem in many sciences is the learning of causal structure underlying a system, typically through observation and experimentation. Commonly, one even collects data across multiple domains, such as gene sequencing from different labs, or neural recordings from different species. Although there exist methods for learning the equivalence class of causal diagrams from observational and experimental data, they are meant to operate in a single domain. In this paper, we develop a fundamental approach to structure learning in non-Markovian systems (i.e. when there exist latent confounders) leveraging observational and interventional data collected from multiple domains. Specifically, we start by showing that learning from observational data in multiple domains is equivalent to learning from interventional data with unknown targets in a single domain. But there are also subtleties when considering observational and experimental data. Using causal invariances derived from do-calculus, we define a property called S-Markov that connects interventional distributions from multiple-domains to graphical criteria on a selection diagram. Leveraging the S-Markov property, we introduce a new constraint-based causal discovery algorithm, S-FCI, that can learn from observational and interventional data from different domains. We prove that the algorithm is sound and subsumes existing constraint-based causal discovery algorithms.

Causal discovery from observational and interventional data across multiple environments
Adam Li
Department of Computer Science, Columbia University adam. li@columbia.c edu
Amin Jaber
Synlico Inc.
amin. jaa..jaaberssslicooccom
Elias Bareinboim
Department of Computer Science, Columbia University ebêcs. www.mbia.......ooooooooo........ edu
Abstract
A fundamental problem in many sciences is the learning of causal structure under- lying system, typically through observation and experimentation. Commonly, one even collects data across multiple domains, such as gene sequencing from different labs, neural recordings from different species. Although there exist methods for learning the equivalence class of causal diagrams from observational and experimental data, they are meant to operate in a single domain. In this paper, we develop fundamental approach to structure learning in non-Markon non-Markovian systems (i.e. when there exist latent confounders) leveraging observational and interven- tional data collected from multiple domains. Specifically, we start by showing that learning from observational data in multiple domains is equivalent learning from interventional data with unknown targets in single domain. But there are also subtleties when considering observational and experimental data. Using causal invariances derived from do-calculus, define a property called S S-Markov that connects interventional distributions from multiple-domaing to graphical criteria selection diagram. Leveraging the S-Markov property, constraint- based causal discovery algorithm, S-FCI, that can learn from observa- tional and interventional data from different domains. We prove that the algorithm is sound and subsumes existing constraint-base causal discovery algorithms.
introduce new
Introduction
Causal discovery is the process of learning cause-and-effect relationships between variables in given system, which is many times the final goal of the data scientist or a necessary step towards more refined causal analysis [1. 2]. The learning process typically leverages constraints from data to infer the corresponding causal diagram. However, it is common that the data constraints do not uniquely identify the full diagram. Therefore, the target of analysis is often an equivalence class (EC) of causal diagrams that encodes constraints found in the data (implied by the underlying unknown causal system).
An EC encodes invariances in the form of graphical constraints, and thus used to represent all causal diagrams that encode those constraints and invariances. Formal characterizations of ECs
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

important to understand the output of a learning algorithm and how it relates to the underlying causal system the scientist aims explain.
ECs are defined with respect to distributional invariances which are implied by the structure of the graph. For example, conditional independences (CT) are implied by d-separations in the causal graph. Hence, it is desirable to formally characterize the EC in the general setting where we have interventional data from multiple domains. A complete graphical characterization would enable an efficient representation of the distributional invariances in the data and ii) the ability to translate these intaainvaaissees to graphical constraints (e.g. d-separation).
An early example of an EC when only observational data is available in a single domain is the Markov equivalence class (MEC). The MEC characterizes causal diagrams with the same set of d-separation statements over observed nodes [2-5]. Given interventional (i.e. experimental) data, one can reduce the size of the equivalence class [6, 7]. In the case of known intervention targets, the EC is known as the Z-MEC [7-9] and in the case of unknown targets, it is called the VM-MCC [6].
In prior research, domain-changer and interventions were treated similarly [10-14]. Nevertheless, various examples across scientific disciplines highlight their distinction (see Table 1). For instance, when extrapolating data-driven conclusions from bonobos to humans, consider Figure 1(b). Notably, the environment/domain, represented by the S-node pointing to X, illustrates differences in kidney function between the species. When applying CRISPR intervention a gene linked to kidney protein production (X), researchers investigate the impact of medication (Y) on fluid balance in the body (Z). This intervention is explicitly different from the sidney-function differences between bonobos and humans because the change-in-domain is there regardless of whether or not an intervention is made. This differentiation between interventions and domains holds significance, especially in causal discovery. By leveraging invariances across observational and interventional data from both bonobos and humans, one can learn additional causal relationships. Moreover, conflating these qualitatively distinct settings is generally invalid, as pointed out in transportability analysis [15]. Pearl and Bareinboim (2011) introduced clear semanties for S-nodes (environments), offering a unified representation in the form of a selection diagram.
In this paper, investigate structure learning when mixtures of observational and interventional data (known and unknown targets) across multiple domains are available. The multi-domain setting has been analyzed from the lens of selection diagrams, where selection nodes (or S-nodes) encode distributional changes in the mechanisms, or exogenous variables due to a change in domain [16-18]. We will show in this paper characterization of the EC for selection diagrams. Generalizing the structure learning setting to multiple domains requires a formal treatment because it is a common scenario in the sciences [19-31]: see Table for example of different settings and related literature). For example, in single-cell sequencing analysis, scientists are interested in analyzing the causal effects of proteins on one another. However, they may typically collect observational and/or experimental data from multiple labs (i.c. domains) and wish to combine them into one dataset. Also, scientists may collect observational and experimental data over multiple species in order learn more about one specific species, or the relationships among species [25, 27,32) 32].
The celebrated FCI algorithm and its variants learn a partial ancestral graph (PAG), an MEC of causal diagrams, given purely observational data [1, 2, 33]. The I-FCI (with known targets) and V-FCII (with unknown targets) generalize these results to interventional data, and further reduce the size of the EC to an I-PAG and V/PAG, respectively [6. 7J. However, these algorithms operate in a single domain, or environment and do not account for combining known/unknown target interventions.
Various approaches have been proposed throughout the literature for causal discovery from multiple domains. The works in [10, 13, 34-38] assume Markovianity, functional model (c.g. linearity) holds, and/or do not take into account arbitrary combinations of observational and interventional data with known and unknown targets. Alternatively, JCI pools data together and performs learning on the combined dataset [14]. Pooling data is an incomplete procedure when considering interventional data within a single domain let alone multiple domains [6][Appendix D.2].
In this paper, we take a principled approach to the multi-domain structure learning problem and formally characterize S-PAGs, the object of learning. This paper introduces the selection-diagrant FCI algorithm (S-FCI) that learns from a mixture of observational and interventional data from multiple domains to construct an EC of selection diagrams, an S-PAG. Specifically, contribute the following:
2

---

Interv.
Domain
Obs.
Property
FCI-variant
Related Lit.
K
u
x
x
Markov [39]
[3,33, 40-43]
[30, 31]
1
v
I-Markov [7,
[7. 8, 44]
[22,30)
1
v
x
v
V-Markov [6]
[6. 13, 45]
[22, 27, 46]
k
V M-Markov (Thm. 1)
[6] (Cor. 5)
[20, 21, 23, 24, 47, 48]
k
V S-Markov (Thm. 2) S-FCI (Thm. 3)
[20-25, 28-31, 46-50]
Table 1: Summary Markov property results, and related algorithms that learn the ancestral graph based on number of domains and types of interventional (interv.) data provided such as observational (obs.), and known (K) and unknown (4) targets. The last column indicates brief survey different fields in ecology, economics, genomics, neurosciences, neurology and medicine that attempt to answer questions each level. The rows highlighted in "red" are new concepts.
1. Generalization of standard Markov properties We introduce the S-Markov property. which extends and generalizes the normal Markov, I-Markov, and Vr-Markov properties to the setting of multiple domains with arbitrary mixtures of observational and interventional data with known and unknown targets.
2. Learning algorithm- We develop sound learning algorithm for learning an equivalence class of selection diagrams with observational and/or interventional data across different domains."
2 Preliminaries and Notation
Uppercase letters (X) represent random variables, lowercase letters (r) signify assignments, and bold
ones (X) indicate sets. The CI relation being independent of Y given Z is denoted as X .L Y|Z. The d-separation (or m-separation) of X from Y given Z in graph G' is expressed as (X T Y (Z)).. x depicts G with incoming edges to X removed, while Gx omits all edges outgoing from X. Conventionally, every variable is d-separated from the empty set, denoted as (X 1 ()). Superscripts and subscripts will be dropped where feasible to simplify notation.
Causal Bayesian Network (CBN): Let P(V) be a probability distribution over a set of variables V, and Px(V), denote the distribution resulting from the hard intervention do(X x). which sets X
C V to constants x. Let P denote the set of all interventional distributions PV(V), for all X V. including P(V). A directed acyclic graph (DAG) over V is said be causal Bayesian network compatible with P if and only if, for all X S V, Pv(v) = II [x). P(e:lpa,) for all v consistent with and where Pa; is the set of parents of V; [41, 51, pp. 24). Given that a subset of variables are unmeasured or latent, G(V UL E) will represent the causal graph where and L denote the measured and latent variables, respectively, and E denotes the edges. Following the convention in [41], for simplicity, a dashed bi-directed edge is used instead of the corresponding latent variables. CI relations can be read from the graph using graphical criterion known d d-separation.
Under this type of interventions, the original conditional distributions of the intervened variables X are replaced with new ones, without completely eliminating the causal effect of the parents. Accordingly, the interventional distribution Px (v) for X S V such that pt (X:)Pus) # PPX,) VX, E X, and factorizes as follows:
Soft Interventions:
Px(v) Σ II L ((X,e))
(*(xappa,
II P(ty/pa.) (XT
(1)
In this work, we assume no selection bias and solely consider soft interventions. In the presence of multiple domains, a selection diagram captures commonalities and differences between domains [16, 52, 53]. Represented as Gs UUUL,
Es), it extends causal diagram by incorporating S-nodes and their edges. (2) S-nodes, Si.j, indicate distribution changes across pairs among N
domains, by pointing to nodes in V whose mechanism is altered between domains and j. An example
is shown in Figure 1(a), where the S-node is pointing to X, indicating that the distribution of X
Our algorithm is implemented open-source MIT-Licensed https//gittbbbcm/yyywwyydootooot
3

---

changes, or that of the latent variable of X is different across the two domains." Similarly, "F-nodes" are auxiliary nodes used in [1. 7, 54] to represent invariances with respect to interventions within the same domain. F-nodes this paper when written as FX means it intervenes on X and compares distributions from domains and j. F'x means compares distributions within domain i. Unlike interventions, Hamain-shiffi potentially alter latent variable distributions or functional relationships and persist irrespective of whether or not external intervention occurs. Distinguishing these concepts enables S-node learning, vital for transportabilityy analysis on ancestral graphs. Appendix Section E,4 elaborates on our distinctions from previous work [11, 13, 36].
Let S 1 SNN..N } represent (2) S-nodes for distribution changes across domain pairs. When = S o, indicating there no S-node for single domain.
Multi-domain setup The following objects are utilized repeatedly, and introduced here. Our [6] and the transportability literature [55].
notation borrows from
1. Domains: II = , IT?
} denotes a set of N domains.
Intervention targets: y { 22 .... M) is an ordered tuple of sets of intervention targets, with different sets of intervention targets occurring within each of the N domains for a total of M intervention target sets. We will denote V as the intervention targets associated with domain i.
3. Distributions: I
P1 PN is an ordered tuple of probability distributions that are available to learn from. Denote Pt as the distributions associated with domain i. There is one-to-one correspondence between P and v, such that Pj is the distribution associated with targets 1 in domain
Known target indices: K. is a vector of I's and O's indicating which sets of interventions are - KC represents therefore an index vector selecting the distributions and interventions with unknown targets. Px and x denotes the set of distributions and intervention targets corresponding to the known target interventions.
snown-tarretss U ;= 1-
Causal diagram: = (V UL, E), is a shared diagram over the N domains.
6. Selection diagram: Gs (V VVULUS S, E Es), extends G with the corresponding S-nodes and their edges to represent each pair of domains. Let Vs denote the set of nodes that S-node $ points and Vs as the set of children for all S-nodes of Gg.
X denotes the ith domain set of variables X, and X, E X indicates the ith variable within X. When discussing intervention targets, x(((() refers to the jth variable with the kth mechanism change in domain For instance, X(((k), X:. represent two interventions with distinct mechanisms (k and I) on variable X in domain i. 0) E & explicitly denotes the observational distribution for domain and is by convention a "known-targ" ttarge", For concreteness, say (x(()) (X(0))1
{11,, 112, 11n) with
P = (Pt, P2. Pj, P v = (0' are three distributions available in domain 1: P1 is observational, P3 is known-target on X with specific mechanism change and P3 is unknown- target that intervenes on and Y simultancously. In domain 3, P is observational. There are distributions for domain 2.
YJ, (+), and = [1, 1,, 1]. In words, there
3
Multi-domain Markoy Equivalence Class
Before designing a learning algorithm, we must characterize what can be learned from the given selection diagram. This section explores ECs in multi-domain setting with arbitrary mixtures of observational and interventional data. The following assumptions are made throughout the paper.
Assumption 1 (Shared causal structure). We assume that each environment shares the same causal diagram. That the S-nodes do not change the underlying causal diagram.
This means that the S-nodes do not represent structural changes such as when Vú2 has different parent set across domains."
'In the original selection diagram, each S-node points single node. Our adaptation simplifies it to single S-node with multiple connections. Theoretical properties remain unaffected, shown in the appendix. 'The assumption that there are no structural changes between domains can be relaxed in the context of inference, specified in [16]. We do not explore this relaxation here in the context of structure learning.

---

Assumption 2 (Observational data is present across domains), We make the simplifying assumption that 0 E L Vi [N] that is observational data present all domains.
This is realistic assumption in many scientific applications highlighted in Table 1.* Another assumption we make is that all soft interventions across domains are distinct.
Assumption 3 (Distinct interventions across domains). We assume all the interventions across different domains have unique mechanisms. That is, if ((m) E y and X E W where + j. then m o n. In words, X has different mechanisms across the two distributions Pus.
This is a realistic assumption that precludes the possibility that any interventions that occur in different domains result in the same exact mechanism. For example, even if medication is given to humans and bonobos, it is unrealistic to expect the intervention has the same mechanism of action in each domain. Next, we define important operation when comparing two different intervention sets.
Definition 3.1 (Symmetrical Difference Operator A in Multiple Domains), For two domains j. (possibly = j), given two sets of intervention targets, V and Vr let 4 A denote the symmetrical difference set such that X E A'A if ( E V and (*k) T vice versa.
This operation identifies the set of variables with unique interventional mechanisms across two intervention targets and also tracks the domain ids. For example, given I (X*, Y. Z) and J' = {X², y) then I' AJ = {X, 2)1.2, An implication of the above definition and Assumption 3 that the symmetrical difference of two intervention target sets from two different domains the union of all the variables in both sets since the mechanisms would be unique. For more details and discussion on the assumptions, see the Appendix.
3.1 Multi-distributional invariances: interventions and change-of-domain
This section elaborates on exactly what type of distributional invariances we characterize in the so called S-Markov EC.
When given only observational data, the celebrated FCI algorithm uses invariances of the form P(Y W) P(Y X) within the same probability distribution P(V) to characterize the Markov EC [2]. These invariances, or CI statements can mapped to d-separation statements in the graphical model. The resulting learned object is the PAG, which represents the EC when only observational data given within a single domain.
The works in [6-8, 44] build upon the Markov EC to characterize the so called interventional Markov EC, which uses distributional invariances of the form Pw (Y|X) P'z (Y})). In words, these are conditional probabilities that remain invariant under different interventions. Importantly, this sort of invariance markedly different from that of the CI statements, where only observational data is present, because one is now comparing probabilities across different distributions. These distributional invariances can be characterized graphically by the d d-separation property when using an augmented graph with "F-nodes", which serve as graphical representations of the differences in distributions due to interventions. However, this body of work assumes that all the distributions, observational and interventional, are within the same domain.
In this work, we generalize this setting and consider an input set of distributions from (possibly) different domains to characterize the S-Markov EC. We consider distributional invariances of the form P (Y
P& (Y such that distributions could stem from different domains when i i j. Such an invariance implies that the conditional distribution of Y X remains the same across domains and j under interventions on W and K, respectively. Whenever = j. these invariances reduce to the ones considered in the interventional Markov EC. From this perspective, it is clear that multi-domain invariances generalize the invariances analyzed in observational and interventional data in single-domain.
3.2 S-Markov Property
Now, we are ready to generalize the previous Markov properties [2, 5-7, 41, 56] to the case when ob- servational, and known/unknown-targe interventional distributions in multiple domains are available.
'If one can collect experimental data in domain, it is reasonable that they can also collect observational data. We discuss this further in the Appendix.
5

---

81.2
$1.2
S1.2
S1.2
F12
F
F1.
Y
Y
(a)
(b)
(d)
by Figure 1: Example selection diagrams (a.b) and their respective augmented graphs (c,d). (c) corresponds to intervention set y (0', 22,000..00 (x3") and (d) corresponds to intervention set
V = (0H.0000 00, (
Definition 3.2 (S-Markov Property), Given the Multi-domain setup, P satisfies the S-Markov property with respect to the pair (Gs, V) if the following holds for disjoint Y, W, w,ZS V:
1. For Dj E D:
Pj Pj(r/w) if T Z/W,S)Gs
2. For Y m. V E V: (yl)) = P(((ww) if 1 K/ WK. S ( Has R(w)
where K = - AWAAWW)SS WK= = wkkKW K W and R(W) C R are non-ancestors of W in Gs.
Let (Gs, V denote the set of distribution tuples that satisfy the S-Markov property with respect (Gs, V where K. denotes the known intervention targets.
When there is only a single domain, II {II'), }. the first constraint reduces to standard d-separation on a causal diagram. The second condition is generalization of the y --Markov property characterization [6], extending conditional invariances to multiple domains. We illustrate the definition with the following two examples.
Example 1. Consider the selection diagram in Figure ((a) with domains II = (II IT.). Let (PI, Pl. P?) be the result of the interventions L = (0) [X} ()) S = (S (S } be the set of S-nodes, and K = [1. 0, 1]. First, we have (Y ( (1.2) )o..))Gs G.s so the first constraint of Def. 3.2 is not applicable for any distribution. Second, compare Pf (y/ar) and P3 where 51. convention and K {X}. We have (Y (YXX) and the invariance is not required. For P and (v(lx) we have (Y)S)X) Also, for P2 (v|æ) and Pf(W)), we have (YXIX,))) S))asy Hence, invariances required between those pairs of distributions. A similar argument can be made when comparing other probability terms across distributions. Therefore, P satisfies the S-Markov property with respect to (Gs, V
O
Example 2. Consider the setup from Ex. 1. We check if P satisfies the S-Markov property relative
to (Gs, Tt where T (f), (Y)' We compare P/ (X) and P)((X and have K (D*A(Y))) U (Y)2. The separation (X LL Y| holds true which implies the invariance (X) = P2 (X). but P2 was generated from an intervention on X so the invariance is not satisfied. Hence, does not satisfy the S-Markov property with respect (G's, V
Next, use Def. 3.2 to define S-Markov equivalence follows. In words, two pairs of selection diagrams and their corresponding sets of intervention targets (Gs, M and (G's, V/" are S-Markov equivalent if they can induce the same set of distribution tuples.
Definition 3.3 (S-Markov Equivalence). Let II and K. denote fixed sets of domains and indices of known intervention targets, respectively. Given selection diagrams Gs, G's defined over S and the corresponding intervention targets V. Ni, the pairs (Gs, V and (G's, Vi) are said to be S M-Markov equivalent if (Gss V S TT).
3.3 Multi-domain observational data
S-nodes introduced through the lens of selection diagrams are augmentations of the causal graph to
represent different domains and changes in distributions that may occur [7, 15, 54, 57]. As part of this augmented graph, S-nodes are graphically similar F-nodes, which have been successfully used to represent interventions [6, 7, 54]. F-nodes utility nodes where each one is parent to (cach element

---

in) symmetrical difference set, and they are used to represent invariances between interventional distributions. The significance of these F-nodes will be further emphasized Section 3.4; more specifically, by Definition 3.5 and Proposition 1. Despite the similarity between F-nodes and S-nodes, worthy to distinguish S-nodes since many causal inference tasks, such as in transportability, rely on knowing the S-node structure [15, 53]. Before deriving the graphical characterization for the S-Markov equivalence class, we first focus on the setting where there only observational data across different domains. We highlight that S-nodes can be exactly viewed as F-nodes constructed from interventions with unknown targets when there is only observational data to consider [6].
Definition 3.4 (Corresponding Intervention Set). Consider the Multi-domain setup. For selection diagram Gş over N domains. (v..)) (V Vis. .... V sM-1,,, ,Vi, o j E [N] is an ordered tuple of the children of each S-node. The corresponding intervention set for Vs s is ( IN) such that I' A'A
Sas for all + j.
The corresponding intervention set is set that simplifies our presentation of the following theorem.
Theorem 1 (Equivalence of V and $ Markov property given multi-domain observational distributions). Consider the Multi-domain setup. Let Gs be a selection diagram among N domains and G be the corresponding causal diagram without S-nodes. Let n = (0), ..., (7>) and K = [1, .,., 1]. such that for each of the N domains, there is only observational data. Let Ig be the corresponding
intervention set for Vs. Let pll an arbitrary set distributions generated by the corresponding interventions. I satisfies the S-Markov property with respect to (Gs, v if and only if it satisfies the --Markov property with respect to Is)
When given observations collected from multiple domains, it is equivalent to collecting distributions with unknown-targe -ttrgett interventions. This coincides with other works, which treat different domains and interventions as the same [10, 13]. In this setting, S-nodes have a correspondence to the augmented graph's 's F-nodes in [6]. In some sense, the -ononnn can be viewed as "nature's" intervention on the causal system. However, this simplification is not warranted when we consider interventions that occur in different domains.
3.4 Mixture of multi-domain observational and interventional data
Next, we analyze the general setting with multi-domain observational and interventional data. Def. 3.2 and 3.3 may be quite challenging evaluate in practice since it involves surgically altering the selection diagram. One can leverage graphical approach that encodes the symmetric differences of interventions using F-nodes [7].
Definition 3.5 (Augmented selection diagram). Consider the Multi-domain setup. Let the multiset I [K|
be defined as I ,K,, K2, KR} of Gss with respect to V is denoted as Augu (Gs) and constructed as follows: Augo(Gs) (V U LUSUF, EUEsUE), where F ( jAkeiNi [M] is the set of added F-node edges.
y met V E A v Av = Kj. The augmented graph
is the set of added F-nodes and E [(Pp ])k,
The F-nodes graphically encode the symmetrical difference sets between every pair of intervention targets in IIll (i.e. m AT) within and across the different domains in IT. F = F% denotes an F-node representing the kth symmetric difference of intervention targets within domain i and F denotes an F-node from comparing intervention targets between domains i and j. The result is an augmented selection diagram with the original causal structure augmented with S-nodes, F-nodes, and their additional edges. For example, Figure 1(c) shows the augmented diagram of the selection diagram in Figure ((a) with respect to iil (0 (X)+ (X)+, (2)). The significance of this construction follows from Proposition where separation statements in the S-Markov definition are tied (shown to be equivalent, formally speaking) to ones in the augmented selection diagram, with no need to perform any graphical manipulations.
Proposition 1 (Graphical S-Markov Property). Consider the Multi-domain setup. Let Auga (Gs) be the augmented graph of Gs with respect to V. Let K = K; U {Si.A be the union of the set of nodes adjacent to pi.k and the corresponding S-node Sü.k The following equivalence relations hold
'Due space constraints, all the proofs are provided in the Appendix.
7

---

for disjoint Y, Z, W S V, where W, = wn K and R = K, W,
(Y W) = (Y Z N.W.S.F).cm Augg((s) (ugg
(2)
(Y K. W.W (S Gss nawy
(Y (r..
(5 Augp (Gs)
(3)
L
The result in the above proposition is illustrated in the following example.
Example 3. Consider the selection diagram in Fig. 1(b) with intervention targets v = (0', [ (²).
By Prop. 1, can evaluate the S-Markov property in the corresponding augmented diagram in Fig. I(d) without manipulating it. For example, (Y 1. Z)Gsz can be tested in Fig. I(d)
by (Y - 1S F Augu(Gs) to determine if the invariance (Y) (2) should hold. In addition, we can test if across-domain distributional invariances should hold. We have (YX(F! S1. [[X, Z}. F!) Augu (Gs) then the invariance (2 2) (2 2) is not required.
Maximal Ancestral Graphs (MAGs) provide a compact and convenient representation capable of preserving all the tested constraints in augmented selection diagrams which are represented by d- separations [58]; see also [59, P. 6]. This formalized in Definition 3.6 and the construct referred as an S-MAG. The following example is provided for illustration.
Definition 3.6 (S-MAG). Given a selection diagram Gg and a set intervention targets V an S-MAG is the MAG constructed from Auga (Gs). That is MAG MAGgAug (Gs)).
Example 4. Consider the selection diagram in Figure ((a) and let T = (x)+, (12). The corre- sponding augmented selection diagram Augu (Gs) is shown in Fig. 1(c). Finally, the corresponding S-
MAG is M MAG(Augg (Gs)) = (X - F - Y, X + F1.2 Y,X + S1. Y. EX-Yp Y). L
Finally, putting these results together, we derive a graphical characterization for two selection diagrams with corresponding sets of intervention targets to S-Markov equivalent.
Theorem 2 (S-Markov Characterization). Let II and K. denote fixed sets of domains and indices of known intervention targets, respectively. Given selection diagrams Gs, G'g defined over S and the corresponding intervention targets V Vr' the pairs (Gs, V and (G's, VV) are S-Markov equivalent if and only if for M M MAG( (AAAggggGGs) and M' = MMMMAAGAuu (G's):
1. M and M' have the same skeleton;
2. M and M' have the same unshielded colliders; and,
3. If a path p is discriminating path for a node Y in both M and M', then Y is a collider on the path in one graph if and only it is collider on the path in the other.
Theorem states that the pairs (Gs, v and (G's, Y are S-Markov equivalent if their corresponding S-MAGs satisfy the corresponding three conditions, illustrated in the example below.
Example 5. Consider the tuples (Gs, Tll from Example and (Gs, T from Example 2. S-
MAGs M = (AGgAug (Gs)) is shown in Ex. 4 and M' = M MAG (Gs)) = (F) -
Y, F + Y. X + 51.2 + Y, + Y}. Therefore, Mj and M2 have differing skeletons and thus are not S M-Markov equivalent.
Next, we leverage this characterization to devise an algorithm to learn the corresponding equivalence class of true, underlying selection diagram.
4 Causal Discovery From Multiple Domains
We investigate in this section how learn an EC of selection diagrams from mixture of observational and interventional data that is generated from multiple domains. The graphical characterization of S-Markov equivalence in Theorem 2 and the significance of ancestral graphs (MAGs) deriving this result motivate the following definition of S-PAG.
WWe assume that the symmetrical difference sets are indexed for both diagrams in the same pattern such that the correspondence between F-nodes and S-nodes is the same in M and M

---

Sha
S12
W
W
(a) G3
Orienting Unshielded Colliders
(d)
Figure 2: Example of S-FCI applied with v (f)' {X) (P2) and AC [1, 1, 1]. The S-node representing domain-shift between domains and is the black square in (a).
Algorithm 1 S-FCI: Algorithm for Learning a S-PAG SepSet the separating sets, is the S-node set, Fill the F-node set, H maps each pair of known-targets symmetric diff's., and maps each pair of distributions a pair of domains.
Input: Tuple of distributions p = (PI ) vector of known intervention targets IC and yrll.
Output: S-PAG, P
f o, k 0, :N + N..
(S.F,H. e CreatcAugmenttedNooosspp""""""" V) (see Alg. E.2)
Phase I: Learn skeleton
for all pairs X,Y E VUFUS do
SepSet(X, Y), SepFlag GervallieDDDCCosttannsXXYYY..... Th K,, V) (see Alg. E.4)
if SepFlaa True then
Remove edge between X and Y
Phase ll: Orient unshielded colliders
For every unshielded triple (X, Y, Z) P orient as collider iff Z SepSet Y)
Phase Ilb: Apply logical orientation rules
R1-7: Apply FCI rules from [39] and following two rules until none apply.
Rule 8": For FRJ E Flll and for S S, orient adjacent edges out Ft and Sij.
Rule 9': For Ft.) E Fll with X H that is adjacent to node Y & H if [ = then
orient Y.
Definition 4.1 (S-PAG). Consider the Multi-domain setup. Let M M MM (Gs)) and let
[M] be the of S-MAGs corresponding all the tuples (G's, w that are S-Markov equivalent (Gs, ) The S-PAG for (Gs, I denoted P is graph such that:
1. P has the same adjacencies as and any member [M] does; and
every non-circle mark (tail or arrowhead) in P an invariant mark in [M] (i.e. present in all the S-MAGs in [M]).
S-PAGs generalize PAGs and 4-PAGs from the single-domain the multiple-domain setting(6, 42]. The S-nodes and F-nodes are not so much "random variables" as they are graphical instruments that encode differences across domains and among interventional distributions this equivalence class. Next, we introduce generalization of c-faithfulness [6] that enables causal discovery from multi-domain data.
Definition 4.2 (S-faithfulness). Consider selection diagram Gs over N domains. A tuple of distributions (PT) E (GG, = is called s-faithful to Gs if the converse of each of the S-Markov conditions (Definition 3.2) holds.
O
The new algorithm, called S-FCI is shown in Alg. Due to space constraints, we only include the high-level algorithm here. The algorithm proceeds by first constructing the augmented graph using Alg. E.2, by adding S-nodes and F-nodes to represent every pair of domains and interventions. Then it uses hypothesis testing to learn invariances in the skeleton (Alg. E.3) and finally applies orientation rules (Alg. E.5). S-FCI learns skeleton by mapping pairs of distributions pil to F-nodes, or S-nodes by testing for the distributional invariances discussed in Section 3.1. Def. 3.2 and Prop. 1 connect these invariances to graphical criterion, which allow us to reconstruct the skeleton of the causal diagram. Interventional distributions across domains used to learn F-node structure, and

---

S1.2
S/.
Fj
F
F
(a)
(b)
(c)
Figure 3: Causal graphs related to example 6 selection diagram with an intervention at Y, and S-node pointing to X (a), the graph after applying Z-FCI without considering domain-changee (b) and the S-PAG learned by S-FCI (c).
whereas observational distributions across domains are used to learn S-node structure. Besides the standard FCI rules that apply in the absence of selection bias, the algorithm also applies the following rules -9'.
Rule 8" (Augmented Node Edges) We orient edges out of F-nodes. Rule 9º (Identifiable Inducing Paths) If F E F is adjacent to a Y & H known-target node and we know that the intervention target is node X, one can orient X - because the Fij + Y is only present due inducing path between X and Y.
In Figure 2, the different stages of the S-FCI algorithm are shown. Next we prove the proposed S-FCI algorithm is sound.
Theorem 3 (S-FCI Soundness), Given KC, let P! be generated by some unknown tuple (Gs, L from domains II with corresponding selection diagram Gg and is s-faithful to the selection diagram Gs. S-FCI algorithm is sound (i.e. every adjacency and orientation in Ps. the S-PAG learned by S-FCT, is common for M AA(AAggg (Gs)))-
11
Next, we illustrate some subtleties between the S-FCI and related algorithms that say pool obser- vational and interventional distributions, ignoring the domain change. The example is motivated from biomedical sciences, where interventions are commonly performed in different domains and the goal is to leverage all datasets for learning. A group of scientists are trying to determine the causal structure of a set of proteins, but leverage data across the lab and hospital setting. Different experiments are run in each setting and combined into a single dataset [29]. We provide additional examples and commentary the S-FCI subtleties in the Appendix.
Example 6. Let Gg be a selection diagram as shown in Figure 3(a). Let II = (I2 be the set of domains representing the lab (II') and the hospital (11²). These are tuple of distributions P = (PI, P with intervention targets I (0' (Y)) (2)) and K.C = -,, 1]. where X represents some protein in the dataset.
In this example, let Gs be the true selection diagram as shown in Figure 3(a). Given the interven- tional and observational data, may be tempted use the I-FCI algorithm and simply pool the observational data, while ignoring the domain differences [7]. but this would learn the graph in Figure 3(b) with an incorrect orientation (shown as the red edge). This I-PAG only contains because there is only two distributions: i) the pooled observational data and ii) the data resulting from intervention Y. Applying R9 of the I-FCI algorithm incorrectly orients the edge X Y. Thus, R9 of the I-FCI algorithm is not sound when the domains are ignored [7, 44].
F-node
Figure 3(c) contains what S-FCI would recover. Intuitively, one should learn (c) instead of (b) because even though there a change in distribution among X and Y, one cannot ascertain whether there is an inducing path from F) to X, or a change in distribution due to the domain.
5 Conclusions
In this paper, we introduced generalized Markov property called S-Markov, which defines new equivalence class (EC), the S-PAG, representing the constraints found across observational and experimental distributions collected from multiple domains. Building on this new characterization, we develop a causal discovery algorithm called S-FCI, which subsumes FCI, I-FCI and V-FCI, and accepts as input mixture of observational and interventional data from multiple domains.
10

---

Acknowledgements
AL was supported by the NSF Computing Innovation Fellowship (#2127309). EB was supported in part by the NSF, ONR, AFOSR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation.
References
[1] Judea Pearl. Causality: Models, reasoning, and inference. 2nd. Cambridge University Press, 2009.
[2] P. Spirtes, C. Glymour, and R. Scheines. "Causation, Prediction, and Search." In: 81 (1993). Place: New York, NY Publisher: Springer New York.
[3] T. Verma and J. Pearl. An Algorithm for Deciding if Set of Observed Independencies Has a Causal Explanation. arXiv: 1303.5435
[es]. 2013.
[4] P. L. Spirtes, C. Meek, and T. S. Richardson. Causal Inference in the Presence of Latent Variables and Selection Bias, arXiv:1302.499 [cs]. 2013.
[5] C. Meek. Causal Inference and Causal Explanation with Background Knowledge. arXiv: TrXiv:1302.4991 302.4972 [cs]. 2013.
[6] Jaber, M. Kocaoglu, Shanmugam, and E. Bareinboim. "Causal Discovery from Soft Interventions with Unknown Targets: Characterizattin and Learning." In: Advances in Neural Information Processing Systems. Vol. 33. Curran Associates, Inc., 2020, pp. 9551-9561.
[7] M. Kocaoglu, A. Jaber, K. Shanmugam, and Bareinboim. "Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions." " In: Advances in Neural Information Processing Systems 32 (2019).
[8] A. Hauser and P. Bühlmann. Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs. arXiv: 104.2808 [cs, math, stat). 2012.
[9] A. Hauser and Bühlmann. "Two Optimal Strategies for Active Learning of Causal Models from Interventional Data." In: International Journal of Approximate Reasoning 55.4 (2014). arXiv: 2005 1474 [cs, stat], pp. 926-939.
[10] R. Perry, von Kügelgen, and B. Schölkopf. Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis. srXiv:2206.02011 [cs, stat]. 2022.
[11] B. Huang, K. Zhang, M. Gong, and C. Glymour. "Causal Discovery and Forecasting in Nonsta- tionary Environments with State-Space Models." en. In: Proceedings of the 36th International Conference on Machine Learning. ISSN: 2640-3498, PMLR, 2019, pp. 2901-2910.
[12] B. Huang, C. J. H. Low, F. Xie, C. Glymour, and K. Zhang. "Latent hierarchical causal structure discovery with rank constraints." In: arXiv preprint arXiv:2210.01 (2022).
[13] J. Peters, P. Bühlmann, and N. Meinshausen. Causal inference using invariant prediction:
identification and confidence intervals. arXiv:1501. 0.00..03322 [stat]. 2015.
[14] J. M. Mooij, S. Magliacane, and T. Claassen. "Joint causal inference from multiple contexts."
In: The Journal of Machine Learning Research 21.1 (2020). 99:9919-9::4026.
[15] J. Pearl and Bareinboim. "Transportability Causal and Statistical Relations: A Formal Approach." en. In: Proceedings of the AAAI Conference Artificial Intelligence 25.1 (2011). Number: pp. 247-254.
[16] E. Bareinboim and Pearl. "Transportability of Causal Effects: Completeness Results." In: Proceedings of the AAAI Conference on Artificial Intelligence 26.1 (2012), pp. 698-704.
[17] J. Pearl and E. Bareinboim. "Transportability across studies: A formal approach." In: (2018).
[18] J. D. Correa and E. Bareinboim. "From Statistical Transportability to Estimating the Effect of Stochastic Interventions." In: ().
[19] T. R. Frieden. "Evidence for Health Decision Making Beyond Randomized, Controlled Trials." " en. In: New England Journal of Medicine 377.5 (2017). Ed. by M. Drazen, D. P. Harrington, J. J. McMurray, J. H. Ware, and J. Woodcock, pp. 465-475.
[20] A. Li, S. Inati, K. Zaghloul, and S. Sarma. "Fragility in Epileptic Networks : the Epileptogenic Zone." " In: 2017, pp. 1-8.

---

[21] A. Li, C. Huynh, Z. Fitzgerald, I. Cajigas, D. Brusko, J. Jagid, A. O. Claudio, A. M. Kanner, J. Hopp. S. Chen, J. Haagensen, E. Johnson, W. Anderson, N. Crone, S. Inati, K. A. Zaghloul, J. Bulacio, J. Gonzalez-Martiner and S. V. Sarma. "Neural fragility as an EEG marker of the seizure onset zone." en. In: Nature Neuroscience 24.10 10 (2021). Number: 10 Publisher: Nature Publishing Group, pp. 1465-1474.
[22] K. Sachs, O. Perez, D. Pe' Pe'er, D. A. Lauffenburger, and G. P. Nolan. "Causal protein-signaling networks derived from multiparameter single-cell data." eng. In: Science (New York, N.Y.) 308.5721 (2005), pp. 523-529.
[23] J. M. Bernabei, A. Li, A. Y. Revell, R. J. Smith, K. M. Gunnarsdottir, I. Z. Ong, K. A. Davis, N. Sinha, S. Sarma, and B. Litt. "Quantitative approaches guide epilepsy surgery from intracranial EEG." " In: Brain (202)), awad007.
[24] A. Palepu, A. Li, Z. Fitzgerald. K. Hu, Costacurta, J. Bulacio, J. Martinez-Gonzaler and S. V. Sarma. "Evaluating Invasive EEG Implantations with Structural Imaging Data and Functional Scalp EEG Recordings from Epilepsy Patients." eng. In: Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual International Conference 2019 (2019), pp. 3866-3866 3869.
[25] S. Nolte and J. Call. "Targeted helping and cooperation in zoo-living chimpanzees and bonobos." eng. In: Royal Society Open Science 8.3 (2021), 201688.
[26] J. Kelly, A. Karthikesalingam, M. Suleyman, G. Corrado, and D. King. "Key challenges for delivering clinical impact with artificial intelligence." In: BMC Medicine 17.1 (2019), pp. 195-195.
[27] D. Stimpson, N. Barger, J. P. Taglialatela, A. Fintrarn-ii R. Hof, W. D. Hopkins, and C. C. Sherwood. "Differential serotonergic innervation of the amygdala in bonobos and chimpanzees." In: Social Cognitive and Affective Neuroscience 1 1.3 (2016), pp. 413-422.
[28] E. A. Petersen, T. G. Stauss, J. A. Scowcroft, E. S. Brooks, J. L. White, S. M. Sills, K. Amirdelfan, M. N. Guirguis, J. Xu, C. Yu, A. Nairizi, D. G. Patterson, K. C. Tsoulfas, M. J. Creamer, V. Galan, R. H. Bundschu, C. A. Paul, N. D. Mehta, H. Choi, D. Sayed, S. P. Lad, J. DiBenedeett K. A. Sethi, J. Goree, M. T. Bennett, N. Harrison, A. F. Israel, P. Chang, P. W. Wu, G. Gekht, C. E. Argoff, C. E. Nasr, R. S. Taylor, J. Subbaroyan, B. E. Gliner, D. L. Caraway, and N. A. Mekhail. "Effect of figghffreuency (10-kHz) Spinal Cord Stimulation in Patients With Painful Diabetic Neuropathy: A Randomized Clinical Trial." eng. In: JAMA neurology 78.6 (2021), pp. 687-698.
[29] P.-Y. Tung, J. D. Blischak, C. J. Hsiao, D. A. Knowles, J. E. Burnett, J. K. Pritchard, and Y. Gilad, "Batch effects and the effective design of single-cell gene expression studies." " en. In: Scientific Reports 7.1 (2017). Number: Publisher: Nature Publishing Group, p. 39921.
[30] T. R. Hughes, M. J. Marton, A. R. Jones, C. J. Roberts, R. Stoughton, C. D. Armour, H. A. Bennett, E. Coffey, H. Dai, Y. D. He, M. Kidd, A. M. King, M. R. Meyer, D. Slade, P.
Lum, S. B. Stepaniants, D. D. Shoemaker, D. Gachotte, K. Chakraburtty, J. Simon, M. Bard, and S. H. Friend. "Functional discovery via a compendium of expression profiles." eng. In:
Cell 102.1 (2000), pp. 109-126.
[31] X. Shen, S. Ma, P. Vemuri, and G. Simon. "Challenges and Opportunities with Causal Discov- ery Algorithms: Application Alzheimer's Pathophysiology." en. In: Scientific Reports 10.1 (2020). Number: Publisher: Nature Publishing Group, p. 2975.
[32] D. Ehrens, A. Li, F. Aeed, Y. Schiller, and S. V. Sarma. "Network Fragility for Seizure Genesis in an Acute in vivo Model of Epilepsy." eng. In: Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual International Conference 2020 (2020), pp. 3695-3698.
[33] D. Colombo, M. H. Maathuis, M. Kalisch, and T. S. Richardson. "Learning high-dimensional directed acyclic graphs with latent and selection variables."
In: Annals of Statistics 40.1 (2011),
pp. 294-321.
[34] A. Ghassami, S. bal,hkalcybar, N. Kiyavash, and K. Zhang, Learning Causal Structures Using Regression Invariance. arXiv:1705.cm 09644 [cs, stat). 2017.
[35] C. Heinze-Demll J. Peters, and N. Meinshausen. Invariant Causal Prediction for Nonlinear Models. arXiv:1706.08577 [stat]. 2018.
12

---

[36] B. Huang, K. Zhang, J. Zhang. J. Ramsey, R. Sanchez-Romen Romero. C. Glymour, and B. Schölkopf. Causal Discovery from Retenggeneos//oossattoonnny Data with Independent Changes. arXiv: 19X3:1903.01172 (es, stat]. 2020.
[37] A. Ghassami, N. Kiyavash, B. Huang, and K. Zhang. "Multi-domain Causal Structure Learning in Linear Systems." In: Advances in Neural Information Processing Systems. Vol. 31. Curran Associates, Inc., 2018.
[38] Y. Zeng, S. Shimizu, R. Cai, F. Xie, M. Yamamoto, and Z. Hao. "Causal Discovery with Multi-Domain LiNGAM for Latent Factors." In: Proceedings of The 2021 Causal Analysis Workshop Series. ISSN: 2640-3498. PMLR, 2021, pp. 1-4.
[39] J. Zhang. "On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias." In: Artificial Intelligence 172.16-17 (2008), Publisher: Elsevier, pp. 1873-1896.
[40] P. Spirtes, C. Glymour, and R. Scheines. "From probability to causality." " In: Philosophical Studies 64 (1991), pp. 1-36.
[41] J. Pearl and D. Mackenzie. The book of why the new science of cause and effect. Pages: 418.
2019.
[42] D. Colombo, M. H. Maathuis, M. Kalisch, and T. S. Richardson. "Learning high-dimensional directed acyclic graphs with latent and selection variables." " In: The Annals of Statistics 40.1 (2012). arXiv: 104.5617 [es, math, stat].
[43] D. Colombo and M. H. Maathuis. FOrder-Independer Constraint-Based Causal Structure Learning" " In: Journal of Machine Learning Research 15 (2014), pp- 3921-3962.
[44] K. D. Yang, A. Katcoff, and C. Uhler. Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions. arXiv: 802.06310 [math, stat). 2019.
[45] D. Eaton and K. Murphy. "Exact Bayesian structure learning from uncertain interventions." en. In: Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics. ISSN: 1938-7228, PMLR, 2007, pp. 107-114.
[46] J. Smith, M. Hays, G. Kamali, Coogan, N. Crone, Y. Kang, and S. Sarma. "Stimulating native seizures with neural resonance: new approach to localize the seizure onset zone." In: Brain 145.11 (2022), pp. 3886-3900.
[47] A. Li, Myers, N. Warsi, K. M. Gunnarsdottir, S. Kim, V. Jirsa, A. Ochi, H. Otusbo, G. M. Ibrahim, and S. V. Sarma. Neural Fragility of the Intracranial EEG Network Decreases after Surgical Resection of the Epileptogenic Zone. en. Pages: 2021.07 00021.07.0..30 07.007....198. 2022.
[48] K. M. Gunnarsdottir, A. Li, R. J. Smith, J.-Y. Kang, A. Korzeniewska, N. E. Crone, A. G. Rouse, J. J. Cheng, M. Kinsman, P. Landazuri, U. Uysal, C. M. Ulloa, N. Cameron, I. Cajigas,
J. Jagid, A. Kanner, T. Elarjani, M. M. Bicchi, S. Inati, K. A. Zaghloul, V. L. Boerwinkle,
S. Wyckoff, N. Barot, J. Gonzalez- and S. V. Sarma. "Source-sink connectivity: a novel interictal EEG marker for seizure localization." In: Brain 145.11 (2022), pp. 3901-3915.
[49] K. Jo Black and M. Richards. "Eeo""""Coooiiiee iico-gentrifiication and who benefits from urban green amenities: NYC's high Line." en. In: Landscape and Urban Planming 204 (2020), p. 103900.
[50] A. M. Lozano, N. Lipsman, H. Bergman, Brown, S. Chabardes, W. Chang, K. Matthews,
C. C. McIntyre, T. E. Schlaepfer, M. Schulder, Y. Temel, J. Volkmann, and J. K. Krauss. "Deep
brain stimulation: current challenges and future directions." " In: Nature reviews. Neurology 15.3 (2019), pp. 148-160.
[51] E. Bareinboim and J. Pearl. "Causal Inference by Surrogate Experiments: z-Identifiability." In: Uncertainty in Artificial Intelligence- Proceedings of the 28th Conference, UAI 2012 (2012), pp. 113-120.
[52] E. Barcinboim, J. D. Correa, D. lbeling, and T. Ieard. "On Pearl's s Hicrarchy and the Foun- dations of Causal Inference." In: Probabilistic and Causal Inference: The Works Judea Pearl. 1st ed. Vol. 36. New York, NY, USA: Association for Computing Machinery, 2022,
pp. 507-556.
[53] E. Bareinboim and J. Pearl. "Meta-Trrassortaabiii of Causal Effects: A Formal Approach." en. In: Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics. ISSN: 1938-7228, PMLR, 2013, pp. 135-143.
13

---

[54] P. Dawid. "Influence Diagrams for Causal Modelling and Inference." In: International Statis- tical Review / Revue Internationale de Statistique 70.2 (2002). Publisher: [Wiley, International Statistical Institute (ISI)), pp. 161-189.
[55] E. Bareinboim and J. Pearl. "Causal inference and the data-fusion problem." In: Proceedings of the National Academy of Sciences 113.27 (2016). Publisher: National Academy of Sciences, pp. 7345-7352.
[56] Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[57] J. D. Correa and E. Bareinboim. "General Transportability Soft Interventions: Completeness Results." In: O.
[58] T. Richardson and P. Spirtes. " "Ancestral graph Markov models." In: The Annals of Statistics
30.4 (2002). Publisher: Institute of Mathematical Statistics, pp. 962-1030.
[59] J. Zhang and G. F. Cooper. "Causal Reasoning with Ancestral Graphs." In: Journal of Machine Learning Research 9 (2008), pp. 1437-1474.
[60] S. L. Lauritzen, A. P. Dawid, B. N. Larsen, and H.-G. Leimer. "Indepen- dence properties of directed markov fields." en. In: Networks 20.5 (1990). _eprint: https://onlinelibraayy wwwpebrwwww..iwy.......... http://coo//oo////.......... wtt.10000ee..202000000
pp. 491-505.
[61] J. Zhang. A Characterization of Markov Equivalence Classes for Directed Acyclic Graphs with Latent Variables. weXiv:1206..00 5206228221/6 [cs, stat], 2012.
[62] C. Meek. Strong Completeness and Faithfulness in Bayesian Networks. arXiv:1302.499 [cs]. 2013.
[63] J. Correa and E. Bareinboim. "A Calculus for Stochastic Interventions:Causal Effect Identifi- cation and Surrogate Experiments." en. In: Proceedings of the AAAI Conference on Artificial Intelligence 34.06 (2020). Number: 06, pp. 10093-10100.
[64] J. Correa and E. Bareinboim. "General Transportability of Soft Interventions: Completeness Results." In: Advances in Neural Information Processing Systems. Vol. 33. Curran Associates, Inc., 2020, pp. 10902-10912.
[65] J. M. Robins, M. A. Hernán, and B. Brumback. "Marginal structural models and causal inference in epidemiology." eng. In: Epidemiology (Cambridge, Mass.) 11.5 (2000), pp. 550- 560.
[66] D. Geiger, I. Verma, and J. Pearl. "d-Separation: From Theorems to Algorithms." en. In: Machine Intelligence and Pattern Recognition. Ed. by M. Henrion, R. D. Shachter, L. N. Kanal, and Lemmer. Vol. 10. Uncertainty in Artificial Intelligence. North-Holland, 1990, pp. 139-148.
[67] A. Jaber, M. Kocaoglu, K. Shanmugam, and E. Bareinboim. "Causal Discovery from Soft Interventions with Unknown Targets: Characterization and Learning"" In: O.
[68] A. P. Dawid. "Conditional Independence in Statistical Theory." en. In: Journal of the Royal Statistical Society: Series B (Methodological)) 41.1 (1979). _eprint:
https://onlinelibaaryy http://rrrrriiillle.ooo///////da http://///11..111 10...11111 11j2517--161.1199..b000
pp. 1-15.
[69] J. Pearl. "Causal Diagrams for Empirical Research." " In: Biometrika 82.4 (1995). Publisher: [Oxford University Press, Biometrika Trust], pp. 669-688.
[70] A. A. Hagberg, D. A. Schult, and P. J. Swart. "Exploring Network Structure, Dynamics, and Function using NetworkX." " In: Proceedings of the 7th Python in Science Conference. Ed. by
G. Varoquaux, T. Vaught, and J. Millman. Pasadena, CA USA, 2008, pp. 11-15.
[71] Squires, Wang, and Uhler. Permutation- Causal Structure Learning with Unknown Intervention Targets. arXiv:1910.0900 [stat]. 2020.
[72] A. Li, J. Lee, F. Montagna, C. Trevino, and R. Ness. Dodiscover: Causal discovery algorithms in Python.
[73] A. Lii, J. Lee, and A. Roy. Prwhy-Grahss: Causal graphs that are networks-compliant for the py-why ecosystem.
[74] J. Park, U. Shalit, B. Schölkopf, and K. Muandet. Conditional Distributional Treulment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regression. arXiv:2102.088: (cs, stat]. 2021.
14

---

[75] J. M. Mooij and T. Claassen. "Constraint-Bade Based Causal Discovery using Partial Ancestral Graphs in the presence of Cycles." en. In: Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI). ISSN: 2640-3498. PMLR, 2020, pp. 1159-1168.
[76] R. Nagarajan, M. Scutari, and S. Lèbre. Bayesian Networks in R: with Applications in Systems Biology. New York, NY: Springer New York, 2013.
[77] A. Ankan and A. Panda. "pgmpy: Probabilistic graphical models using python." In: Proceed- ings of the 14th Python in Science Conference (SCIPY 2015). Citeseer, 2015.
[78] P. Hünermund and E. Bareinboim. Causal Inference and Data Fusion Econometrics. 1rXiv:1912.09111 [econ]. 2023.
[79] D. T. Campbell, J. C. Stanley, and N. L. Gage. Experimental and quasi-experimental designs for research. Experimental and quasi-experimental designs for research. Pages: ix, 84. Boston, MA, US: Houghton, Miftlin and Company, 1963.
[80] C. F. Manski. Identification for Prediction and Decision: Cambridge, MA: Harvard University Press, 2008.
[81] S. Wasserman. "Review of Statistical Methods for Meta-Analysis." In: Journal of Educational Statistics 13.1 (1988). Publisher: [Sage Publications, Inc., American Educational Research Association, American Statistical Association], pp. 75-78.
[82] W. R. Shadish, T. D. Cook. and D. T. Campbell. Experimental and Expai-Experimenntl Designs for Generalized Causal Inference. Cengage Learning, 2002.
[83] S. L. Morgan and C. Winship. Counterfactuals and Causal Inference: Methods and Princi- ples for Social Research. Analytical Methods for Social Research. Cambridge: Cambridge University Press, 2007.
15


Reviews:
[{"review_id": "PBDBcopVPw", "reviewer": "Reviewer_WVJw", "summary": "This paper analyzes the categorization and properties of Markov equivalence class from interventional data. The unique part is that this paper considers multiple environments (use env for short lately), where in each env, both observational and interventional data are accessed.", "questions": "The paper mentioned in introduction about the work of JCI [1], and argues that JCI pools data together and perform learning\non the combined dataset [35]. Pooling data is an incorrect procedure, ... may result in learning an invalid MEC (see Example 11).\nSo this paper argues that even under the standard setting (unknown interventional targets from observational and interventional data, under a single env), JCI is incorrect. I checked example 11, but it links to example 6 and other properties. So can you elaborate one such example to point to the mistakes made by JCI?\n\n[1] Mooij, J. M., Magliacane, S., & Claassen, T. (2020). Joint causal inference from multiple contexts. The Journal of Machine Learning Research, 21(1), 3919-4026.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. Causal discovery from interventional data is a promising direction, because genuine causal relations can be recovered by RCT, where RCT generates interventional data.\n2. The setting is general, which considers the existence of latent confounders, and also extend the previous setting to {obs, intv} across different envs.", "weaknesses": "1. The motivation is not convinced.\nfirst of all, the term \"env\" here is different from conventional usage. below [1][2][3] shows the conventional meaning of the term \"environment\", which means that an env just alters the observational distribution by known or unknown underlying mechanism. Based on my understanding, in the standard definition of \"causal discovery from interventional data\", each interventional data (a sample from the causal graph under known/unknown interventions) is viewed as collected from an env.\nI think the above setting is general enough to meet real needs, what is the motivation to build a second layer of \"env\" on top of that? If this is indeed the case, I believe it should be supported by solid empirical evaluations.\n[1] Huang, B., Zhang, K., Gong, M., & Glymour, C. (2019, May). Causal discovery and forecasting in nonstationary environments with state-space models. In International conference on machine learning (pp. 2901-2910). PMLR.\n[2] Peters, J., Buhlmann, P., & Meinshausen, N. (2015). Causal inference using invariant prediction: identification and confidence intervals. arXiv. Methodology.\n[3] Peters, J., Janzing, D., & Schölkopf, B. (2017). Elements of causal inference: foundations and learning algorithms (p. 288). The MIT Press. (Section 7.2.5)\n\n2. lacks solid empirical evaluations to support the claims\nthe second contribution of this paper is that \"Learning algorithm - We develop a sound learning algorithm for learning a Markov\nequivalence class of selection diagrams with observational and/or interventional data\", so I wonder \na) any empirical justification about the soundness?\nb) compared with existing work, what advantage of the setting, i.e., {obs, intv} across envs?\nc) any real-world usage to support the motivation, or to convince readers that the categorization and analysis in this paper are indeed needed.\nCurrently, there is no experiment part in main body, this is unacceptable from my opinion.\n\n3. The notation part is extremely hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> w - “1. The motivation is not convinced… the term \"env\" here is different from conventional usage… that an env just alters the observational distribution by known or unknown underlying mechanism…. what is the motivation to build a second layer of \"env\" on top of that?”\n\nThank you for the opportunity to elaborate on this important issue. The question entailed by your note is: How do interventions and environments differ in real-life scenarios? \n\nMany examples across scientific disciplines demonstrate that the notions of domain/environment and interventions are distinct. For example, when making inferences about humans based on data from bonobos, this distinction becomes clear. The difference between the two species is depicted as the environment/domain in this context. A scientist might perform an intervention on a bonobo's kidney (specifically, what we're representing as Z), and try to determine the effect of medication (X) on fluid equilibrium in the body (Y). Although we could intervene on Z in bonobos and observe its effect on X and Y, our ultimate goal might be to understand the effect of X on Y in humans. It's generally invalid to conflate these two qualitatively different indices, a point first noted by Bareinboim & Pearl in the context of transportability analysis around 2011. The distinct environments exist regardless of any intervention, such as medication. Also, an intervention on the kidney function is different across the two species. Bareinboim & Pearl (2011) formalized this setting, introducing clear semantics for the S-nodes (environments) that essentially offers a combined representation for both environments. We appreciate the references listed though and have added them to the introduction. With this foundation, we can now address the reverse problem of determining the equivalence class of selection diagrams from data.\n\nMoving to mathematics, neglecting these distinctions has significant implications for the structure learning problem. To witness, consider Figure 2 in the main text. It demonstrates, even in a simple 2-node scenario, why environments and experiments must be distinguished. We have a laboratory (domain 1) and a hospital setting (domain 2). In the lab, we can experimentally perturb proteins (Y) and simultaneously observe levels of biomarker (X). Let the true causal direction be $X \\rightarrow Y$.  In the hospital, observational data is collected, which includes sequencing data and biomarker values. Given a domain-shift (e.g. batch effects common in gene sequencing exps), it’s essential to account for the shift when comparing observational and interventional data. Otherwise, one might mistakenly infer that $Y \\rightarrow X$. While this orientation is valid if the data were collected in a single-domain setting and the same distributional invariances held, it isn’t accurate in this specific example due to the overlooked domain shift. In other words, a single indicator can’t describe the invariance in this setting, equating interventions and domain-shifts is erroneous.\n\nWe further demonstrate differences wrt JCI [Mooij 2020] and ICP [Peters 2015] in a few simple examples shown in Figure S4 and S5 (attached fig. PDF). \n\nThe framework of “nonstationary changes” [Huang 2019] also uses auxiliary random variables to capture mechanism changes as a result of time-series non-stationarity and thus can be seen as encompassed within the JCI framework. They allow changes in causal strengths and noise variances though, which may be interesting to explore in future work and how it can improve the characterizations and/or learning we propose here.\n\n> w: “2b) compared with existing work, what advantage of the setting, i.e., {obs, intv} across envs?”\n\nWe have shown in the Appendix “Section D.2 Comparisons with Other Works” (pg 25)  how the S-Markov property and the SFCI algorithm generalize the existing $\\Psi$-Markov and $\\Psi$-FCI algorithm. \n\n> w: “2a) any empirical justification about the soundness?”\n\nDue to space constraints, we put empirical exps. in the Appendix Section D.3 (pg 26). We ran SFCI on the Sachs dataset shown as Figure S5 in the submission.  We also added Figure S10 (attached fig. pdf), which demonstrates in a simulation how S-FCI compares with $\\Psi$-FCI and standard FCI algorithm.\n\n> w: “2c) any real-world usage to support the motivation,...\n\nAlong with the previous response, in Table 1 we highlight different bodies of scientific work that look at different domains with obs. and/or interventional data. Furthermore, we ran S-FCI on the Sachs dataset in Appendix Sec. D.3.1 (pg 27).\n\n> w: “3. The notation part is extremely hard to follow.”\n\nWe understand the notation is complex due to carrying around the domains, distributions and intervention targets. We have modified the paper and introduced objects and notation in a more organized format in the Preliminaries shown in the author rebuttal. We hope we have motivated the need for notation that distinguishes domains, interventions and distributions.\n\n> q: “The paper … argues that JCI pools data together and perform learning on the combined dataset. Pooling data is an incorrect procedure, ... may result in learning an invalid MEC (see Example 11)...”\n\nThank you for pointing this out!. Our choice of wording has been changed to **“Pooling data is an incomplete procedure… and moreover ignoring the presence of a domain-shift with interventional data can lead to learning an invalid MEC (see Example 11)”**. \n\n**Re incompleteness of the JCI procedure [2]:** In the Appendix of [Jaber et al. 2020], Section D.2 Prop. 6, shows that, if there are at least 3 distributions, the JCI procedure does not capture all the invariances across every pair of distributions required by the $\\Psi$-Markov property. The same reasoning applies here since the S-Markov property generalizes the $\\Psi$-Markov property.  The incompleteness of the pooling procedure is also shown in an example comparing JCI to SFCI in Figure S5 (fig. rebuttal).\n"}, {"review_id": "wo0Ay9u4H0", "reviewer": "Reviewer_KPtn", "summary": "This paper develops a structure learning algorithm that uses observational and experimental data across multiple domains while handling both known and unknown target interventions. The developed algorithm generalizes and subsumes pre-existing methods that only work for single domain settings. Some experiments are given in the appendix.", "questions": "Line 2:\nDo you mean \"Commonly, one even collects data across multiple domains...\" or \"Commonly, one collects data across even multiple domains...\"?\n\nLine 18; Theorem 3:\nThe proposed algorithm is sound. Is it also complete? Could there be cases where it fails? Please discuss.\n\nSuggestion to go along with Table 1:\nIt would be *very* helpful to include definitions of Markov, I-Markov and $\\Psi$-Markov in this section, and discuss/compare them. This will allow readers to more easily follow and appreciate the subsequent discussions.\n\nLine 36:\nIs L latent while X and Y are observed? It was not clear, but I assume so.\n\nLine 84:\nWhat happens if we use hard interventions? Do things break?\n\nLine 85:\nRepeated \"= $\\langle P^1, \\ldots, P^N \\rangle$\"\n\nDefinition 2.2:\nA picture would be helpful.\n\nKnown intervention indices $\\mathcal{K}$ in Definition 2.3:\n$\\mathcal{K}$ is defined on Line 159 and only appears later on Line 168, without appearing anywhere in the definition. Is there a purpose in explicitly mentioning it? What am I missing?\n\nLine 163:\n$X,Y,W$ are disjoint. What about $Z$ and $K$?\n\nLine 166:\nWhy is $\\Psi^j_\\ell \\in \\Psi^i$? Are you saying $i = j$? If so, why introduce $j$? Or do you mean $\\Psi^i_k, \\Psi^j_\\ell \\in \\Psi^\\pi$?\n\nSuggestion for Line 168:\nMaybe directly write $W \\setminus K$ and $K \\setminus W$? That way, you can avoid introducing extra notation such as $W_K$. Also, is there some formatting issue? Definitions of $W_k$, $R$ and $R(W)$ should be part of point 2, right?\n\nCondition 2 of Definition 2.3:\nFrom my understanding, the intuition of (ii) is that \"Y can only be affected by $S^{i,j}$ through $W$\". How should I intuitively explain (i) to someone else? What is the correct intuition to have in mind?\n\nExample 1 and Figure 1:\n- Where is $S^{1,2}_x$ in the picture?\n- Is there a reason why $F_{U_x}$ and $F_x$ are drawn differently?\n\nLine 177:\n\"Define ... be ...\" should be \"Let ... be ...\" or \"Define ... as ...\"\n\nLine 184:\nWhat do you mean by \"constraints of type 2 are not applicable\"?\n\nLine 185:\nWhat is $D_{\\underbar{X}}$?\n\nTypo on Line 212:\n\"... implies that ...\" refers to condition 1 right? In that case, shouldn't it be \"$P^i_j(Z \\mid Y, X) = P^i_k(Z \\mid Y)$\" instead?\n\nTypo on Line 223:\n\"$\\{Y\\}^1$\" should be \"$\\{X\\}^1$\", right?\n\nSuggestion for Line 228:\nAdd \"we have (\" after the first comma?\n\nLine 241:\nThere is no $S_x$ in Figure 1 though?\n\nLines 243 to 245:\nThis distinction should be emphasized earlier. In my head, I was treating mechanism shift and (soft) interventions as synonyms, and I was confused by Figure 1. I suggest to put this distinction note in the preliminaries, before Section 2.\n\nF-nodes:\nIf I am not mistaken, the first instance of F-nodes appear on Line 245 (and many times following that line). What are F-nodes? Section 1 only mentions S-nodes. F-nodes ned to be properly defined and discussed earlier before using them in this section.\n\nDefinition 2.4:\nA picture would be helpful.\n\nConfusion about notation of $F$ in Definition 2.4 and subsequent usage:\nOn Line 272, is $\\binom{(}{N},2$ supposed to be $\\binom{N}{2}$? Is the superscript of $F$ supposed to be single-valued and pair-valued? Subsequent discussion seem to toggle between them and also use $j \\in [N]$ instead of $j \\in \\binom{N}{2}$. I was very confused by this; my best guess is that $F^{i}$ is shorthand for $F^{i,i}$. Is that true? Please make this clear. Thanks!\n\nLine 273:\nThe symbol 'k' already means something in this context. Maybe use $\\ast$ or $z$ or some other symbol for the subscript?\n\nProposition 1:\n- Where is $F_{\\mathcal{E}}$ used in Proposition 1?\n- Line 285, Equation (1): What is $S_i$? Do you mean $S^i$? But I thought the superscripts of S-nodes are in pairs?\n- Line 285, Equation (1): What is $F_{[k]}$? Do you mean $F_1 \\cup \\ldots \\cup F_k$ or $F_{\\mathcal{E}}$ or something else?\n\nTypo on Line 291:\nMissing \"(\" between \"by\" and $X$. I also suggest adding a comma before \"and\".\n\nTypo on Line 311:\nMissing \")\" at the end of definitions of both $M_1$ and $M_2$.\n\nTypo on Line 314:\nExtra space: \"i s\".\n\nGrammar on Line 357:\n\"known-target node $Y$\" reads nicer than \"node $Y$ known-target\"\n\nLine 357:\nWhat is $H^{i,j}_k$? I see it appearing in Algorithm 1 but I don't think it has been properly defined.\n\nLine 613:\nMissing \")\" after \"given $Z$\"", "limitations": "Nil.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides many examples when introducing notation and concepts. There is also discussion contrasting the contributions of this paper against prior works in the appendix.\n", "weaknesses": "The notation is heavy and there are quite a few typos/inconsistent notation which made the initial reading confusing; but I believe these can be remedied. See \"Questions\" section.\n\nI did not check all the proofs in detail, but I do not see any glaring weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Line 2, 36, 85, 163, 166, 168, 177, 212, 223, 228, 243 to 245, 273, 291, 311, 314, 357, 613,\n\nThank you. We have fixed these typos, or added your suggestion into the text.\n\n> Line 18; Theorem 3: Is it also complete? …\n\nThe proposed algorithm generalizes IFCI for the orientation of inducing paths. However, it’s worth noting that IFCI R9 itself isn't complete in the known-targets setting. As an illustration, consider Figure S2(a) (attached figure PDF) with interventions: {}, ${X, Y}$ and $\\mathcal{K} = [1, 1]$, applying IFCI in single-domain yields PAG in S2(b). Still, we could infer $Y \\rightarrow Z$ due to an inducing path. The current orientation rule with known-targets is therefore sound but incomplete. We’ve included this example in the Appendix to motivate future work. \n\nAdditionally, it’s worth noting that it took over a decade to fully characterize FCI (1990s to Jiji Zhang’s 2008 work). Thus, we hope our initial characterization is a valuable step towards further investigation and understanding.\n\n> Suggestion to go along with Table 1…\n\nDue to space constraints, incorporating this into the main text would be challenging. Still, we do agree that a discussion and comparison would be useful, so we have added a section in the Appendix comparing the diff. markov properties. \n\n> Line 84: What happens if we use hard interventions?...\n\nNo characterization for a Markov equiv. class w.r.t. hard interventions exists. Each hard intervention modifies the graph, complicating the establishment of a consistent object for constraints collection. Proving an analogous Proposition 1 (Graphical S-Markov Property) in this context is highly non-trivial due to intervention-induced graph changes. As a result, the process of mapping invariances to the d-separation of an augmented graph is difficult. \n\nFor clarity, we highlight two points. First, we do not address the characterization of equivalence classes stemming from hard interventions, including those in ‘basic’ single-env. Second, our work seems to shed light on properties and nuances in hopes of paving the way for a more expansive characterization in the future.\n\n> Definition 2.2: A picture would be helpful.\n\nFigure S6 in the original submission contains a figure showing the depiction of this “joint selection diagram”. As this def. is not absolutely necessary, we moved this to the Appendix to conserve space for a better introduction of notation.\n\n> Known intervention indices $\\mathcal{K}$ in Definition 2.3 … Is there a purpose in explicitly mentioning it? What am I missing?\n\nIt is necessary because in the S-Markov Characterization (Thm 2; L306), for two tuples of $\\langle G, \\mathbf{\\Psi}, \\mathbf{S} \\rangle$ to be S-Markov equivalent, they must have the same known-targets by definition. It would not make sense to compare tuples where the known-targets become unknown and vice-versa. Indeed, this is not explicitly stated, so as part of the notation fix, we have added it explicitly to Thm 2 (pg 7). \n\n> Condition 2 of Definition 2.3: How should I intuitively explain (i) to someone else?...\n\nIn cond. 2, part i), it looks at whether or not the distribution of a variable y given some variable w is the same across different domains and intervention target sets. To determine this cross-distribution invariance, we look for d-separation in a surgically altered graph, where the alterations are made based on the intervened nodes. This entire def. then maps to a d-separation statement in the augmented graph in the case of structure-preserving soft-interventions in Proposition 1 (L280). \n\n> Example 1 and Figure 1: Where is $S^{1,2}_x$  in the picture?\n\n$S^{1,2}_x$ is not shown in the Figure. Example 1 (L176-180) specifies a setting using Figure 1 and adds a S-node, $S^{1,2}_x$. We have clarified this in the text.\n\n> Line 184: What do you mean by \"constraints of type 2 are not applicable\"?\n\nIn this ex., we mean that since there is no d-separation in the surgically altered graph, then the conditional invariance in the S-Markov property (L166-167) is not required.\n\n> Line 185: What is $D_{\\underline{X}}$?\n\nIn preliminaries L78-79, this mean “all edges outgoing from X are removed”.\n\n> Line 241: There is no $S_x$ in Figure 1 though?\n\n$S_x$ is meant to be a S-node that points to X in the figure (Preliminaries L124). We have adapted the text to describe this more clearly.\n\n> F-nodes: What are F-nodes? Section 1 only mentions S-nodes. F-nodes ned to be properly defined and discussed earlier before using them in this section.\n\nSee L238. F-nodes are auxiliary nodes representing invariances between different distributions introduced in [Pearl 1993, Dawid (2002), Jaber 2020]. These graphically encode the changes due to an intervention and enable the distributional invariances to be encoded via d-separation. We have added discussion about this to Section 1.\n\n> Definition 2.4: A picture would be helpful.\n\nFigure 2a in the main submission (pg 8) contains an example. We adjusted the text to elaborate on Def 2.4.\n\n> Is the superscript of F supposed to be single-valued and pair-valued?... \n\nYes, that is correct. L273-274 clarify this as $F_k^i$ represents pairs of distributions within domain i and $F_k^{i,j}$ as pairs between domain i and j. We will add this to Section 1 to improve clarity.\n\n> Line 285, Equation (1): What is $S_i$?...\n\nYes, thank you for catching this. Indeed, it should say $S^{i,j}$.\n\n> Where is $F_{\\epsilon}$ used in Proposition 1? Line 285, Equation (1): What is $F_{[k]}$? \n\nThanks for catching this! Indeed, $F_{[k]}$ should be $F_{\\epsilon}$, the set of all the F-nodes added in the augmented graph. These F-nodes capture the invariances when comparing every pair of distributions included across domains.\n\n> Line 357: What is $H_k^{i,j}$?...\n\nL344: $H_k^{i,j}$ is the set of known-intervention targets; it keeps track of the symmetric differences $\\mathbf{\\Psi}^i_k \\Delta \\mathbf{\\Psi}^j_l$. We have added this in the header of the Algorithm 1.\n"}, {"review_id": "VIkHaN8FUm", "reviewer": "Reviewer_9ikg", "summary": "This paper discusses the multi-domain scenario for causal discovery, instead of the classic single-domain scenario. It figures out the object to learn for this the muti-domain causal discovery task and proposes corresponding methods for optimizing S-PAGs. It extends existing Markov properties to the S-Markov property, which is more compatible to the multi-domain setting. An algorithm for learning MEC under this diagram is proposed, and the author claims it will be implemented as an open-source repo.", "questions": "i. What about the efficiency of the proposed algorithm?\nii. Are the assumptions on the multi-domain setting too strong? How could we relax them?", "limitations": "See weakness", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "i. This paper discusses a new setting, i.e., a mixture of observational and interventional data from multiple domains. This setting is meaningful, which can be used in many real-world applications.\nii. This paper proposes the definition of the multi-domain Markov equivalence class and provides the method of causal discovery from multiple domains.\niii. Many examples are provided in Section 2 to help with explanations.", "weaknesses": "i. The symbols are a bit disordered, which makes readers hard to understand and follow. A clearer definition in Section 1 is possibly needed.\nii. No relation works, which may increase the hardness for readers.\niii. The experiments are supposed to be placed in the main content, which is important for this paper. The structure of this paper may be re-considered.\niv. Many theorems and rules are proposed, but it seems that the proof is not mentioned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> weakness-“i. The symbols are a bit disordered, which makes readers hard to understand and follow.”\n\nWe’ve experimented with various notations but they tend to be somewhat heavy and we apologize. This complexity arises because the novel characterization and learning algorithm necessitate a formal distinction between distributions, domains, and interventions, which requires keeping track of distributions, intervention sets, domain IDs, known-targets, etc. \n\nIn light of your feedback, we’ve restructured the preliminary section and introduced symbols in a bullet-point format for easier comprehension of these concepts (shown in the general author rebuttal). We also dropped the subscript (set index) and superscript (domain index) in the rest of the paper where possible to make the reading simpler.\n\n>  w-“ii. No relation works, which may increase the hardness for readers.”\n\nWe respectfully disagree. In the original submission, we referenced various works in the introduction that present characterizations for ancestral graphs, including the I-Markov equivalence class (EC) and the $\\Psi$-Markov EC (lines 50-54). Specifically, we highlighted works that characterize the Markov EC in contexts like observational (obs) data alone and combined observational and interventional data. We also touched upon other works in the context of “multiple domains” (L55-61).\n\nA deeper comparison with other works is provided in Appendix Section “D.2 Comparisons with Other Works”. Additionally, Table 1 cites studies in the sciences that seek to answer causal discovery questions in the settings discussed. Having said that, if there are important references you believe we might have overlooked, we would be glad to include them. \n\n> w-“iii. The experiments are supposed to be placed in the main content, which is important for this paper.”\n\nGiven the pg. limit and the introduction of theoretical concepts in the main text, we opted to include relevant experiments in the Appendix, specifically in “Section D.3 Experimental Results - Simulations.” In the original submission, we presented an experiment in this section (L1133-1168) that demonstrated the incorrect orientation of edges when one fails to account for interventions occurring in different domains. This is illustrated with the result of S-FCI (Figure S5 in the original submission) on multi-distributional data, such as the Sachs dataset.\n\nFurthermore, we introduce a simulation in Figure S10 (see attached fig. PDF) comparing the graphs learned by FCI, $\\Psi$-FCI, and S-FCI algorithms. By recognizing data from different domains, the S-FCI algorithm can orient more true edges in alignment with the true graph than other FCI and $\\Psi$-FCI strategies using the same dataset. \n\nWe understand that the placement of experiments in a paper may vary according to authors' preferences, so we respectfully disagree with the notion that there's a universal standard for their placement in the main body. Having said that, we're very open to rearranging content if the reviewers agree that this is the most suitable option.\n\n> w-”iv. Many theorems and rules are proposed, but it seems that the proof is not mentioned.”\n\nWe list this after the first Lemma 1 statement: “Due to space constraints, all the proofs are provided in the Appendix” (line L207).\n\n> question-“i. What about the efficiency of the proposed algorithm?”\n\nOur paper’s goal is to i) develop a theoretical characterization of multi-domain Markov property, and ii) develop a sound learning algorithm that can discover the corresponding Markov EC from data. Before an efficient algorithm for learning can be developed, it’s vital to first provide a theoretical characterization of the ancestral graph and demonstrate an instance of the algorithm, confirming that such learning is realizable. A promising direction for future research would be to develop an even more efficient algorithm.\n\nAfter contextualizing our approach, we acknowledge that this is a practical concern. The runtime complexity of the proposed algorithm mirrors that of the standard FCI, but with the added complexity of comparing different distributions to learn the edge-structure of the augmented nodes. Various methods were proposed to alleviate this issue within the FCI framework. For instance, the RFCI algorithm [Colombo et al. 2012] attempts to construct a “possibly d-separating set” between every two nodes to select the conditioning set. In fact, this extension is discussed in the original submission’s Appendix **“Section D.1.6 Results improving efficiency of skeleton discovery phase”**. We showed that the RFCI strategy can be extended and also applies to improving S-FCI’s complexity. \n\n > q-“ii) Are the assumptions on the multi-domain setting too strong? How could we relax them?”\n\n**Re soft intervention assumption:** We assume that interventions are soft rather than hard. Currently, no characterization for a Markov EC exists in the context of hard interventions. Each hard intervention modifies the graph, complicating the establishment of a consistent object for constraints collection. Proving the analogous to Proposition 1 (Graphical S-Markov Property) in this context is highly non-trivial due to intervention-induced graph changes. \n\nFor clarity, we highlight two points.\n1. we do not address the characterization of equivalence classes stemming from hard interventions, including those in ‘basic’ single-env. \n2. our work sheds light on properties and nuances in hopes of paving the way for a more expansive characterization in the future.\n\n**Re shared causal structure assumption**: As noted above, managing a “changing structure” is already challenging even within a single domain. Once the skeleton starts changing arbitrarily across domains, the task of identifying a compact representation for the equivalence class becomes even more difficult. We consider this an intriguing direction and reserve its exploration for future work. "}]

Author rebuttal:
We thank the reviewers for their time and effort reading our paper and for your valuable feedback with this review. We have attempted to address each of your raised points and hope you can consider the paper in the light of the clarifications provided in your respective rebuttals.

Overall, we have included a better formatted section in the preliminaries to describe the notation, which provides a more structured introduction to the distinct, but necessary objects in our paper.

**[Notation]** Since, domains, interventions, and distributions are central distinctions throughout the whole paper, we added the following to “Section 1.1 Preliminaries and Notation” to simplify the introduction of this notation. 

 “

The following objects are utilized repeatedly, and introduced here. Our notation borrows from the transportability literature [Bareinboim & Pearl, 2012].

1. **Domains**: $\mathbf{\Pi} = \{ \Pi^1, \Pi^2, ..., \Pi^N\}$ denotes a set of N domains.
2. **Intervention targets**: $\mathbf{\Psi}^\Pi = \langle \Psi^1_1, \Psi^1_2, ..., \Psi^N_M \rangle$ is an ordered tuple of sets of intervention targets, with different sets of intervention targets occurring within each of the N domains for a total of M intervention target sets. We will denote $\mathbf{\Psi}^i$ as the intervention targets associated with domain i. 
3. **Distributions**: $\mathbf{P}^\Pi = \langle P^1_1, P^1_2 ..., P^N_M \rangle$ is an ordered tuple of probability distributions that are available to learn from. Denote $\mathbf{P}^i$ as the distributions associated with domain i. There is a one-to-one correspondence between $\mathbf{P}$ and $\mathbf{\Psi}$, such that $P^i_j$ is the distribution associated with targets $\mathbf{\Psi}^i_j$ in domain i.
4. **Known target indices**: $\mathcal{K}$ is a vector of 1’s and 0’s indicating, which sets of interventions are known-targets. $\mathcal{U} := 1 - \mathcal{K}$ represents therefore an index vector selecting the distributions and interventions with unknown targets. $\mathbf{P}\_{\mathcal{K}}$ and $\mathbf{\Psi}_{\mathcal{K}}$ denotes the set of distributions and intervention targets corresponding to the known target interventions.
5. **Causal diagram**: $G =  (\mathbf{V} \cup \mathbf{L}, \mathbf{E})$, is a shared diagram over the N domains.
6. **Selection diagram**: $G_S =  (\mathbf{V} \cup \mathbf{L} \cup \mathbf{S}, \mathbf{E} \cup \mathbf{E_S})$, extends G with the corresponding S-nodes and their edges to represent each pair of domains.

“

Meta-review: The three reviewers and the authors had a robust discussion with much back and forth.  Nevertheless, in the end the reviewers could not reach consensus.  After reading it in great details myself, I agree with many of the points of all the reviewers, and the authors are strongly encouraged to take all reviewer comments into account in the final version. But I actually found the notation clear and the writing extremely clear given the challenging nature of the topic, and I found the motivation solid.  Therefore I am recommending acceptance but strongly advising the authors to address especially the third reviewer's concerns about discussion of relationship to other work (in the supplement if it won't fit into the paper) and about experiments. I think the paper makes a concrete set of useful theoretical contributions to the causal discovery field.

Other items the authors should be sure to address in the final version are:

For such a well-written paper, I was surprised “soft intervention” was used repeatedly but never defined. And it’s central to the paper! For that reason, even though I know it’s common in the literature, it should be defined again in the paper too.

Line 109: SCMs is -> SCMs are

I wasn’t sure the multiple domains problem was that common or important, but the paper gives good examples, including the very common setting of: same biological mechanism but data from different labs

Because the supplement begins by repeating the full paper, the theorem numbers in the supplement (where the proofs are) don’t seem to align easily with the theorem numbers in the paper. So it takes more work than it should for the reader (for example) to go to the supplement and find the proof of Theorem 2. At least it did for this reader.
Decision: Accept (poster)