Scalable Intervention Target Estimation in Linear Models
Authors: Burak Varici
Karthikeyan Shanmugam
Prasanna Sattigeri
Ali Tajer
Venue: NeurIPS 2021 Poster (2021)
Keywords: linear SEMs
interventions
causal inference

Abstract: This paper considers the problem of estimating the unknown intervention targets in a causal directed acyclic graph from observational and interventional data. The focus is on soft interventions in linear structural equation models (SEMs). Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets even for linear SEMs. This severely limits their scalability and sample complexity. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The pivotal idea is to estimate the intervention sites from the difference between the precision matrices associated with the observational and interventional datasets. It involves repeatedly estimating such sites in different subsets of variables. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class. Consistency, Markov equivalency, and sample complexity are established analytically. Finally, simulation results on both real and synthetic data demonstrate the gains of the proposed approach for scalable causal structure recovery. Implementation of the algorithm and the code to reproduce the simulation results are available at \url{https://github.com/bvarici/intervention-estimation}.

Scalable Intervention Target Estimation in Linear Models
Burak VarieI Rensselaer Polytechnic Institute varicberpi. edu
Karthikeyan Shanmugam
IBM Research AI
karthikeyan. shanmugam2 iim. com
Prasanna Sattigeri
Ali Tajer
IBM Research AI
Rensselaer Polytechnic Institute
psattiglus ibm. com
tajerêecse. rpi.
Abstract
This paper considers the problem of estimating the unknown intervention targets in a causal directed acyclic graph from observational and interventional data. The focus is on soft interventions in linear structural equation models (SEMs). Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets even for linear SEMs. This severely limits their scalability and sample complexity. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The pivotal idea is estimate the intervention sites from the difference between the precision matrices associated with the observational and interventional datasets. It involves repeatedly estimating such sites in different subsets of variables. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class. Consistency, Markov equivalency, and sample complexity are established an- alytically. Finally, simulation results on both real and synthetic data demonstrate the gains of the proposed approach for scalable causal structure recovery. Implementa- of the algorithm and the code reproduce the simulation results are available at lht //iittt liggithhun huub. com/ wtw.:/iiiiinneeetnttmmmom -on-eeeettiieeeeeeeee est imat ion.
Introduction
Directed acyclic graphs (DAG) commonly used for encoding the cause-effect relationships among random variables. Extensive research has been dedicated to learning the structure of DAGs from their associated observational data. Strueture learning from the observational data relies uncovering conditional independence (CI) among the random variables. Since structurally distinct DAGs can encode the same set of CI relations, DAG is identifiable only up its Markov equivalence class (MEC) from the observational data. Subsequently, interventional data can be used to further refine the MEC obtained from the observational data and learn specific causal effects.
This paper is motivated by addressing two significant independent challenges in causal discovery. First, most of the existing approaches for learning with interventional datasets require the intervention target set to be known, which can be a strong assumption. For instance, gene-editing technologies are known to perform cleavage off-target genome sites (1] Therefore, identifying the intervened nodes alone is a critical problem in structure learning, and despite its significance, remains uninvestigated. Secondly, besides learning the structures of single DAGs. there exist application domains in which the goal is learning the structural changes between two related networks and their associated DAGs, learning the sites of interventions. For instance, structural differences between the gene regulatory
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

networks of different subtypes of cancers can help to identify the roles of specific genes (2]. In clectroencephalography analysis, the objective is to detect different brain regions that have different interactions when the subject is performing various tasks [3] 'hese brain regions correspond to intervened nodes in a causal graph representation. Another application area is fault detection in large-scale Internet of things and cloud applications [4). Faulty nodes in the system can be considered as intervened nodes, and they are localized through intervention target estimation.
In practice, fixing the target variable at a specific value or removing its causal dependencies is often difficult, while disturbing the distribution of target variable is easier (5). The type of interventions that do not remove the causal effects are commonly observed in the real world. For example, elements of an advertising system can be modified without removing the causal effects [6]. In another example, consider molecular biology, in which the effects of infused chemicals to the cell are not set to specific values nor are they known precisely 87 Therefore, we consider a soft intervention setting, in which we assume the conditional distributions of the target variables are changed, but no assumption is made on the causal effects. Finally, we assume that the topological ordering remains the same after the intervention procedure.
Under the soft intervention model, we propose an algorithm for estimating the intervention targets given the data from two linear SEMs associated with the observational and interventional data. Motivated by the fact that the difference of the precision matrices associated with these two models is sparse, we focus on estimating the sparse difference between precision matrices to avoid extensive conditional independence testing. This leads a significant improvement the computational com- plexity compared to those of the alternative methods. This facilitates scaling up to high-dimensional settings. Furthermore, we show that this algorithm can be used in conjunction with an observa- tional DAG learning procedure to refine the MEC to interventional-Mi -MEC (Z-MEC). Besides being consistent in the population setting, we provide the finite-sample guarantees for linear SEM with Gaussian noise when the soft interventional changes between the two models are sparse. Our main contributions are as follows:
We propose algorithm that identifies intervention targets under the intervention- faithfulness assumption. We show that our algorithm identifies I-MEC given the ob- servational MEC.
We provide the sample complexity of our algorithm under linear SEM with Gaussian noise.
We perform experiments both real biological and synthetic datasets to illustrate the ability to work in the high- sighh-dienssonal settings and the gains compared to the relevant methods.
2
Related work
Among the broad range of approaches to intervention recovery, there exist two methods that are closely related to the scope of this paper: (i) estimating the difference between two DAGs, and (ii) learning from a combination of observational and interventional datasets.
Direct estimation of differences: Direct estimation of differences in linear SEMS has been studied recently. The study in (9) proposes a PC-style algorithm for learning changes in the edge weights by testing invariances of regression coefficients and noise variances. Even though the differences can be sparse, individual models can be dense, and estimating these variables through regression can be inaccurate. Furthermore, the number of hypothesis tests is exponential in the number of nodes that are affected by the changes, which can be prohibitive even under sparse changes in the hub nodes. Esti- mating the difference of two precision matrices is a relatively easier task and has received attention re- cently [3). providing sinite-sample guarantees in the high- high-dimensional regime when such a differ- ence is sparse. An existing study closest the scope of our work is (14), which proposes re-estimating precision difference to progressively eliminate nodes and estimate the difference DAG. This approach critically hinges on the assumption that the noise variance is invariant, rendering limited applicability to intervention settings. In contrast, our algorithm builds on the changes in noise variances and esti- mates the intervention targets efficiently. We demonstrate the effect of this difference in Appendix [ B.
Learning interventional-MECC. There is a growing number of studies on causal structure learning from both observational and interventional data. Score-based greedy interventional equivalence search (GIES) [15) and hybrid interventional greedy sparsest permutation (IGSP) (16) algorithms proposed for settings in which there are no latent confounders. Both of these algorithms assume

---

that the intervention targets are known. However, knowing the intervention targets can be a strong assumption since even for controlled interventional experiments, off-target effects are common. For instance, noise variances of the off-target variables can change, resulting in the intervened nodes being unknown.
For causal structure learning without the knowledge of the intervention targets, an existing study includes the dynamic programming approach [8]. This approach has limited scalability due to its time complexity being exponential in the model size. Structural discovery from interventions proposed in [17) is neural network- -baed method that can learn from interventional data without target knowledge. Nevertheless, it requires discrete data and can have at most one intervened node in given setting, limiting its upplicability. The differential causal discovery from interventional data (DCDI) algorithm proposed in [18] extends the approach of (17) without making as strong assumptions, e.g., learning distribution over all potential interventional families via continuous optimization. While this method is shown to converge to the real intervention targets, its runtime becomes prohibiting even in models with as few as 100 nodes. The Unknown-target IGSP (UT- IGSP) algorithm proposed in [99 learns the intervention targets simultaneously while learning the causal structure. Even though interventions refine the search space, a greedy search of the sparsest permutation is still too slow in the high-dimensional regime, especially when using non-Gaussian CI tests. A graphical characterization of soft interventions with unknown targets is proposed in (7) for causally insufficient systems. This algorithm, however, relies CI tests and it is not scalable. We focus on causally sufficient systems in this paper.
Problem definition
Let G _ ([p]: E) be DAG with the node set [p] - {1,....p) and the edge set E S [p] x [p]. We denote the directed edge from i E [p] to E [p] by i + j. We associate random variable X, with i E [p]. and accordingly, define the random vector X (XI....,, We consider a linear SEM, according to which
B
where B E RPxP is the autoregressive matrix in which By * 0 if and only if - j in g. The random vector E Rax1 has zero-mean and covariance matrix Q & diag(o?...... o We denote the covariance matrix of X by Σ and its inverse (the precision matrix) by θ, which satisfies θ = (I B) B) For entries of O, we have
Bg
B
Bu of
+
Σ
Vi
(2)
0
o
kEch())nah(i)
and O₂ oi 2 +
Σ jEch(i)
of
B
Vi
where ch(i), pa(i), de(i), and an()) denote children, parents, descendants, and ancestors set of node i DAG G, respectively.
From the observational data, a DAG can be learned only up to its MEC [20). Interventions are used to increase the identifiability of DAG by removing all causes of the intervention target (perfect intervention) or modifying those relationships without removing them completely (imperfect intervention). We consider the following soft intervention setting, which does not remove causal effects (from direct parents) on intervention target nodes, and hence, is more practical.
Soft intervention model. In this model, interventions correspond disturbing the target nodes i E I by changing the variances of their noise variables, while the cause weights, i.e., the weights Bpa(t), A [By. E pa()), can vary freely. This intervention procedure on the initial DAG results in second DAG with new parameters.
Let (1) represent a linear SEM prior to intervention with parameters B(),e and ((2) be the linear SEM after the intervention, with parameters B(2), (2), The intervention target set that relates these two DAGs is
I {i: of
(1) + o
(2)
(4)
3

---

Accordingly, denote the covariance and precision matrices of these two models by ,()) e(1, and ((2), Accordingly, denote the differences between the two models by AB _ B() - B and Ae - (2) (2)) For a subset of nodes S S [p], denote the precision matrix of the random vector Xs - [X; i E $} by Os. We also denote the set of changed nodes by SA {k: (Ae)a, # 0} and denote its size by PA _ |Sa] According to 3). this set consists of all the intervened nodes and their parents.
In this paper, we estimate the intervention targets I given the data from two SEMs under the soft intervention model. Furthermore, we estimate the non-intervened parents of the targets, which update the given observational MEC into the I-MEC. Formally, we define 3 Σ x E + (i, pa
as the estimator that maps the covariance matrices of the observational and interventional data to an intervention target set estimate and their parents. We aim to maximize the probabilities of & recovers I and their parents. To this end, we define
P P
and
P(pa(I) = pa(f))
(5)
We will show that the algorithm proposed in Section exactly recovers I and the non-intervened parents of the members of I. Hence, given the observational MEC, we obtain the I-MEC.
4 Algorithm and main results
In this section, we provide our proposed algorithm and present the attendant performance guarantees. Our algorithm involves repeatedly estimating the difference of the precision matrices to find the intervention target set I, or equivalently, its complement I This algorithm consists of three key steps. In Step 1, instead of directly estimating I, we aim to discard the nodes that are strongly deemed not to belong to I. For this purpose, we start by identifying the non-intervened nodes that do not have intervened children. These nodes are not of interest and they are discarded from further consideration. We achieve this by estimating difference of precision matrices corresponding to the complete model with variables [p]. and we denote the changed nodes in the diagonal of this precision difference matrix with SA. We continue with only the nodes contained in SA for further scrutiny, naive approach to identifying the rest of the non-intervened nodes is computing Åe exhaustively for all the 2 subsets of SA. which for large Pa is computationally prohibitive. Alternatively, partition SA into two sets: the set of non-intervened source nodes and its complement. We feed these two partitions for further processing to Step 2. Since the distribution of a node relies only on its ancestors, reaching a topological ordering is critical to reduce the complexity. In Step 2, for each source node, we find the nodes that share a common ancestor with it. Subsequently, we decompose SA into equivalence classes according to these ancestral relationships with non-intervened source nodes. Decomposing SA allows us to order the equivalence classes according a topological ordering. In Step 3, we process these classes individually, and show that we only need to compute Ae for all the subsets of each class considered in Step 3. This results significant reduction in the computational complexity compared to the exhaustive search approach. Finally, we identify the non-intervened parents of from the earlier results. Since estimating the precision difference appears in our algorithm repeatedly, we describe it next and then continue with the details of the three steps.
Precision difference estimation (PDE). When the difference between two SEMs is sparse, esti- mating the difference of their precision matrices can be formulated as a Lasso-type problem and solved efficiently. Since it will be used repeatedly, it is important for this function recover the support of Ae and have feasible computational complexity. The study in (12) solves the follow- ing convex problem through the alternating direction method of multipliers (ADMM) to estimate Ag = (1) (
( Tr - (F - + 2
Å argmin
-
A1lAall1
(6)
where is tuning parameter. The computational complexity of this algorithm grows according to Opp²), which overcomes the limitation of the algorithm of [10] used in [14], which has complexity Op*)). Therefore,
this ADMM-based method as our PDE procedure.
Step 1: Finding the non-intervened source nodes. By leveraging the PDE procedure discussed, we first estimate Ag over all [p] nodes and obtain SA. Representation of θ,, in (3) implies that

---

(8) Next, we decompose the set SA \ Jo into equivalence classes where all the nodes in class have the same source ancestral set. We denote these equivalence classes by AI, and the source ancestral set corresponding to a class A, by Johe for E LL]. These classes are ordered according to a diagonal entry of Ae is non-zero if and only if either its corresponding node is in I or it has a child in I. Hence, the set [p] SS contains only non-intervened nodes and can be discarded from consideration. Furthermore, some non-intervened nodes in Sa, namely those that do not have intervened ancestors, do not observe a change in their statistics. Therefore, it is possible to identify them from covariance matrices 21(1 and 22) Subsequently, these nodes can serve as the starting points for distinguishing the rest of the Ie in Sa. Let us define them as the non enn-intereened source nodes, denoted by
Jo - {j= Ji:jeEss SA, j & I, anz(j) 0} 0)
The outputs of this step, Sn and Jo. are fed into the next steps of the algorithm.
Step 2: Forming equivalence classes from Jn- We will show that for any non-intervened node
j E Sa. there exists a minimal subset of Sa, which makes the corresponding diagonal entry of the precision matrix invariant, and it does not contain any descendant of j. Therefore, the non-intervened nodes that have the same ancestors are affected by the interventions similarly, and finding their ancestors is critical. We show that determining whether node k E Sa \ Jo has a common ancestor with node j E Jo is possible by applying PDE on (i, kj. Accordingly, we define the source ancestral set J for each node & SA \ Jo as
J - (i j E Jo, an(j) n an(k) + 0}, S
topological order such that for 1 S l < S L, Jo & Joh In other words, the class corresponding to the superset of any JØ should appear later than A in the sequence AI...., AL. Source ancestral sets and equivalence classes are fed into the next step.
Step 3: Processing equivalence classes. Given Step 1 and Step 2, we describe our exact search space of subsets for De estimates to declare whether a node is intervened. We process equivalence classes AI, ,I,...,AA individually, i.e., at stage f, consider the nodes in A,, Let us Ae
define M, - Jo U UUsske As. It suffices to estimate A only for each A C Ae to determine the intervention status of any node in Ar class. This key observation reduces the number of PDE steps needed. Specifically, for any non-intervened, j E Ace there exists a subset A C Ae such that the corresponding diagonal entry of AeMUAA will be zero, and there does not exist any such set for the intervened nodes in Ae. Formally, the process equivalence class returns
I = (i: i A
and Jj = (j: E
Finally, we identify the non-intervened parents of the intervened nodes without any new Ag estimates.
Computational complexity. Algorithm [ repeatedly performs PDE in each step. The number of required instances of PDE is (PA + 1) in Step I, O(p%) in Step 2, and Σes(y 2 in Step 3. Hence, it grows exponentially with max [1] [Aee,, which can be pa in the worst case in extreme examples. Nevertheless, in almost all practical scenarios it is usually considerably smaller. To provide some insights, we provide the next example and relegate more discussions to Appendix B.4
Example 1. Consider DAG with nodes (1, 2, 4,5) 5) and the edge set {1-33 +3,3 - 4,2 4,2 + 5,4 - 5) and let I = 5). Hence, we have 5A = f1,2, 5), = (1,2), Jo = =11, Jd f1. (1,2), J8 {1}. and
(1.2), and accordingly, A₁ = (3)
J6
Joh= = (1, Note that the largest A class has 2 nodes whereas SA has 5 nodes.
Restricted SEM. For a linear SEM & with (B,e) we denote the restricted SEM (see Lemma I for details) that characterizes the relationship among the random variables Xs for a set S by (g) As defined earlier, the corresponding precision matrix is denoted by Os. The entries of Bs and noise variances og are characterized by the original values of B, o, and e.
We remark that the invariance of the distributions for the noise term of a node and the value of the node are equivalent only for the non-intervened nodes that do not have an intervened ancestor. Therefore, only such nodes can be detected from the full linear SEM. The noise term of
Remark 1
5

---

Algorithm Causal Intervention Target Estimator (CITE)
Input: X,(1) and x
2: Output. I intervention set
3: Estimate Ae < precision difference(E(), (())
4: Form Sa - {k: k E [p], [A à + 0)
5: Form Jo using 7 and J6 for each & E Sa Jo using
6: Form equivalence classes Al...., AL.
7: for E [L] do
8: Take A, set and the corresponding Jot set
9:
B₁ + -/: C Jn 15b<()
10:
M Jo UUDEB, Ab
11:
Jr,Ie t process equivalence class( Me, Ao, E ((2))
12: end for
13:
I
UeEIL] It
pI( + parent finder(I, Ji Mr, E(2))
15: Return and pa(Z)
Algorithm 2 Functions for the main algorithm
Precision Difference Estimation (PDE) (E(), 22)
1: Using ADMM based algorithm of [12] method estimate Ae (E(1))-1 (I(2))-1
2: Symmetrize Ae: set Ae = (ōe A /
3: Threshold Åe: set [Aek.] = if L <.
4: Return Ae
Process Equivalence Class (M, (M,,E yX), )()
1: For each subset A S A, estimate AeMus precision difference (E,2))
2: for E A do
3:
if 33 C A, where & A, and [Aemualk, =0 then
4:
J Juk
5: else
6: + UUK
7: end if
8:
end for
9:
Return J,I
Parent Finder (I,J. Al.... Mr. Ar, _0) E12)
1: i do
2:
G G c; Ae
3:
for forj Me, do
4:
if if Ac, such that (Aom,ualis then
5:
Add j to pa(i)
6: end if
7: end for
8: end for
9: Return pa(i) for E
non-intervened node maintains its invariance in a restricted SEM which we keep its intervened ancestors and their parents. On the other hand, the noise term of an intervened node is always variant for any choice of restricted SEM.
In the following subsections, we will provide different analytical guarantees of Algorithm I Specifi- cally, we will comment on the consistency of recovery, the refinement MEC T-MEC, and the sample complexity.

---

4.1 Consistency of Z recovery
We provide the consistency of Algorithm D for estimating Z in this subsection. First, we need the following assumption ensure that interventions successful.
Assumption (I-faithfulness) For any choice if E S S [p], we have the following properties:
(2) 1. If of $ $o, (2) then o 0 + 3,6"
2. 1f S * to
01 3, + 10 (2) then [
3. If S,4 * S, and [B + in either model, then [0g + [o
(1) (2)
Next, we characterize the parameters of restricted SEM, and then formalize the observations stated in Remark D in the subsequent proposition.
Lemma
144]
Corresponding to a subset S S [p). denote the removed set nodes by U 2 [p]
and define U, - U Unnjj)) for E S. We have
S o (o) ( Bu,,s) ) Jes (BEs Oon())an (anc))lu,..)
(10)
[Bs]as
(11)
o
Proposition 1 Denote the ancestors of & I in I by an (j) Ifa set S contains anz(j) and their
parents pa pa(anz(i)), then S.. = Furthermore, for i E and any set S we have [A + O. Additionally, if [Bss, # 0 in either model, then we have [Deelis* # 0..
(1)
(2)
5.j"
Remark We repeatedly use the restricted SEM characterization Lemmal with various strategic choices of subsets S in Algorithm to eliminate the non oon-interveeed nodes from S. using the criterion of Proposition 7 Step 1, to identify Jo in ( we set S {j} for each j E Sa. Step to identify J (8) for each SA \ Jo. we S kj.k} for each j E Jo. In Step to process the nodes in Ag, we use subsets of the form Me U A for subsets A in As.
Theorem (Consistency) If Assumption hoolds and covariance estimates are perfect, then Algo- rithm 7 consistently estimates soft interventions with P = 11
4.2 Z-Markov equivalence
Interventions in DAG change the conditional distributions of the intervened variables, and hence, they reveal orientations of some edges that previously undirected in observational CPDAG, resulting in the interventional CPDAG (I-CPDAG). The DAGs that have the same I-CPDAG under soft intervention I form the Z-Markov equivalence class (I-MBC). This is shown and discussed next.
For DAG & and an intervention set Z, an additional Z-vertex Ç and corresponding I-edges {( -> hez added to form the interventional DAG (I-DAG), Note that vertex ( creates v-structure for any non-inter intervened j pa(i). However, if j is also in I. then Z-DAG also contains the v-structure that orient the edge i
< --i
- --i-j
< <+> edge, and there is
We call the edges in G that are not directed in the original CPDAG but are directed in I-CPDAG as Z-directed edges. In the parent finder step of Algorithm D we find the edge set {j - i jzzizzzz and subsequently, obtain the I-MEC. Therefore, we can use Algorithm [ in conjunction with an observational algorithm to perform causal structure learning, and establish the following theorem.
Theorem (I-MEC) If Assumption holds and covariance estimates are perfect, then Algorithm 7 consistently recovers non non-intervened parents of an i with = This result modifies the original MEC, which can be obtained via any observational structure learning algorithm, into the I-MEC.
7

---

1.
10
0.9
0.5
0.9
Precttin
0.8
0.0
0.7
0.7
0.7
10: peat
10 (e:8
0444
0.-
06-
pm30
06-
px330
p=300
p+-00
2000
2003
5002
10000
2000
2000
5005
10000
2000
2000
2402
20000
Samples
(a) Shift intervention
(b) Increased variance
(c) Randomized intervention
Figure 1: Average precision of estimating intervention targets. Algorithm reaches high precision with increasing number of samples even in large models for all settings.
4.3 Sample complexity
In this subsection, we provide the finite-sample counterparts of Theorem I and Theorem 2 Our choice of the PDE algorithm, the 1DMM-base method of (12), enjoys snite-sample results when noise E has Gaussian distribution. The following theorem establishes the sample complexity of Algorithm | for estimating I and the non-intervened parents of the nodes in I.
Theorem (Sample complexity) Let d denote the maximum degree of an intervened node and set & 5(2 & (() and a & 1 maXegsupp [T -.e.upppFuuppp.... sapp.suppl Accordingly, define M
|| }. My max [
|1 1,20
||
1,,00) Mr.rr &
max [II sl IIF ol where S is the support of (2(2)) 11. When a and Mr < +00, with n = 0 (oge) samples, Algorithm
1. identifies I with probability least 1 8;
2. identifies the non-intervened parents U jjezzezz with probability at least 2 1 6.
Note that we have assumed that the product My. rr is bounded. This necessary to avoid a linear scaling of the sample complexity in p. More discussion the necessity and implications of this assumption provided in the proof of Theorem 3 in Appendix[A
Empirical results
5.1 Synthetic data intervention recovery
We start by testing our algorithm for estimating intervention targets, i.c., the Set We generate 100 re- alizations of Erdōs-Rénn: Rényi (21) DAGs with expected neighborhood size 1.5, and [Z] 5. We sam- ple the entries of B, i.e., the edge weights, independently at random according to the uniform distribu- tion [-1, 0.25 U |0.25, 1]. The additive Gaussian noise terms have distribution (00 Ip). We se- lect the intervention set by randomly selecting nodes from [p]. We consider three different models to intervene the nodes in I: (i) shift intervention model in which mean of the noise e; is shifted from 0 to 1, (ii) variance increase model in which the variance of the noise is increased from to 2, and (iii) randomized intervention model, in which (B(2)) pa(()) 0 and the noise variance varies from to 1.5. All the simulations are run on a MacBook Pro with 2.7 GHz Dual-Core core and 8 GB RAM.
(B(2))p((t).
We first run algorithm by varying the graph size and the number of samples. Figure illustrates that our algorithm is able to recover the intervention targets with high precision under all three intervention models. Having high precision is especially important in high dimensions, since large false positive rate severely affects any downstream task such as structure learning. Recall rates are close to I and they omitted from the graph.
Next, we compare our results with that of the UT-IGSP algorithm 19 for the shift intervention model. We note that UT-IGSP performs greedy search to identify the sparsest permutation through CI tests, and returns intervention targets as by-product along with the learned causal structure. The computation time of UT-IGSP, hence, grows quickly with the size of the graph, reaching

---

average of 61.2 seconds for 100. Therefore, the complexity of structure learning and intervention target discovery the high-dimensional regime is prohibitive. In contrast, our algorithm has comparable performance to UT-IGSP when p 100, while requiring less than a second of runtime. Our algorithm's runtime scales gracefully when the dimension is in the hundreds.
Table I estimation in the shift intervention model 50 repetitions with 5000 samples density 1.5
UT-IGSP (19)
Algorithm
P Precision
Recall
Time(s)
Precision
Recall
Time(s)
0.99 (0.04)
0.99 (0.04)
0.8
0.96 (0.09)
0.94 (0.09)
0.1
60
0.95 (0.07)
0.99 (0.05)
5.2
0.97 (0.07)
0.95 (0.10)
0.2
0.96 (0.08)
0.99 (0.04)
17.8
0.96 (0.08)
0.96 (0.10)
0.3
100
0.93 (0.11)
1 (0)
61.2
0.94 (0.09)
0.98 (0.07)
0.3
5.2 Synthetic data- causal structure learning
In Section 4.2 have shown that Algorithm [ recovers the intervention targets. It can be further used to refine the observational MEC to an I-MEC. Accordingly, we take the correct CPDAG of G()), and then apply our algorithm's ' findings to obtain I-CPDAG. We report the accuracy of additional edge orientations and in particular recovery of parents (if possible) of intervention targets in Appendix B.2
5.3 Application to real data
We apply our algorithm to two real datasets with observational and interventional data to learn their causal structures. When there exist multiple interventional environments, we apply our algorithm to them individually to estimate the intervened nodes and their parents. Subsequently, we combine the results from all enviromments in order to form the final estimated structure. There is a large number of interventional settings in which finding the targets and their non-intervened parents by our algorithm yields a good estimate of the associated DAG, which we use for our evaluation.
We compare our results with those of the algorithms UT-IGSP, and UT-IGSP" in 19 where the former works with partially known intervention targets and the latter does not require any target input. We use both parametric (Gaussian) and non- con-paraettric (Hilbert-Schmidt independence criterion) CI tests for UT-IGSP methods. We note that the non-parametric tests have significant runtimes. We note that our algorithm uses PDE at several stages, which calls for different À regularization parameters. Namely, let us denote the parameters used for Step and Step 3 by X1 Step 2 by X2 and the parent finder of Step 3 by Ag. Similarly, UT-IGSP needs cut-off value for CI tests. We run the algorithms with different values of these parameters to obtain the receiver operating characteristic (ROC) curves.
Protein signaling data. We first consider the dataset in (22) for discovering the protein signaling network of 11 nodes. It consists of measurements of proteins and phospolipids under different interventional environments. In each environment, signaling nodes are inhibited or activated. Hence, these sites form intervention targets. The conventionally accepted ground truth has been updated over the years, and we compare with the recent version in [23), which consists of 16 edges. We follow the process of (19) and work with 1755 observational and 4091 interventional samples aggregated from 5 different interventional environments. In Fig. 2a we report the results of running Algorithm Tand
UT-IGSP with various parameters.
Perturb-seq gene expression data. We analyze the performance of our algorithm on the perturb-seq dataset by (24). The dataset consists of observational data and the interventional data from bone marrow-derived dendritic cells (BMDCss. A single gene has been targeted for deletion in each interventional environment. Similarly to (24), we have focused on 24 genes that are known to have regulatory effects, and we have followed [16] to select interventional data from 8 gene deletions along with observational samples. We take the Fig. 4D
24 as the ground truth, which has 34
'The code and preprocessed real data are taken from and CausalDAG package which is distributed under 3- 3-Clause BSD licence is used.
for fair comparison.

---

Unson-Goell UmosPaaSC
UnGSP-Seax
True positives
True positives
10
8
6-
False positives
False positives
Sachs
(2
dataset
(b) Dixit 24 dataset
(a) is more robust in smaller graphs; (b) handles larger graphs and multiple interventional settings successfully, and conforms to real datasets better than CI testers.
Figure 2: ROC curves for directed edge recovery. Algorithm
edges among 24 nodes. We use 23 interventional settings for the targeted 8 gene deletions. In Fig. 2b we plot the results of running Algorithm and UT-IGSP with various parameters.
In both real datasets, our algorithm achieves higher accuracy in recovering directed edges. The comparison with UT-IGSP more striking Fig. 2b and shows that our ability work with many interventional environments on a relatively larger graph. Furthermore, Fig. 2a shows that Algorithm T handles smaller graphs more robustly. These results illustrate that even though our algorithm designed for linear models, on real datasets, it performs better than the current state-of-the fi-th-eart art methods that rely on CI tests.
6 Conclusion
In this paper, we have considered the problem of estimating intervention targets in linear structural equation models (SEMs) under soft interventions. We have proposed algorithm that consistently identifies intervened nodes that can scale to larger graphs and have sample complexity guarantees in Gaussian linear SEMs. The algorithm can be used also to infer interventional Markov equivalence class (MEC) from the observational MEC. We have demonstrated comparable or better performance compared the existing methods in number of settings.
The limitation our method is that only applies to linear SEMs. The dataset in an application should be evaluated carefully confirm whether the assumptions satisfied. This avoids any adverse effects arising from wrong interpretations cause-effect relationships. Extending the similar ideas for scalable and efficient intervention target estimation the non-linear DAGs is open question that we aim to address in future work. Finally, the condition number of the optimization problem is assumed be bounded in the sample complexity results. We note that algorithm is independent of the specific precision difference estimation (PDE) algorithms and can be used in modular way. In this regard, can benefit from any potential relaxation on this limitation of PDE algorithms.
Acknowledgments and Disclosure of Funding
This work supported by the Rensselaer-IBM AI Research Collaboration (http://aire.rpi.edd) part of the IBM AI Horizons Network (htt:://bbm.hi//llHrrraaa
References
[1] Y. Fu, J. A. Foden, C. Khayter, M. L. Maeder, D. Reyon, J. K. Joung, and J. D. Sander, "High- frequency off-target mutagenesis induced by CRISPR-CC -AS nucleases in human cells." Nature Biotechnology, vol. 31, no. 9, pp. 822-826, 2013.
[2] R. W. Tothill, A. V. Tinker, George, R. Brown, B. Fox, S. Lade, D. S. Johnson, M. K. Trivett, D. Etemadmoghadam, B. Locandro, N. Traficante, S. Fereday, J. A. Hung, Y.-.. Chiew,
10

---

I. Haviv, Australian Ovarian Cancer Study Group, D. Gertig, A. deFazio, and D. D. Bowtell, "Novel molecular subtypes of serous and endometrioid ovarian cancer linked clinical outcome," Clinical Cancer Research, vol. 14, no. 16, pp. 5198-1999990 5208, 2008.
[3] S. Sanci and J. A. Chambers, EEG Signal Processing. John Wiley & Sons, 2013.
[4] J. Bogatinovski, S. Nedelkoski, A. Acker, F. Schmidt, T. Wittkopp, S. Becker, J. Cardoso, and
O. Kao, "Artificial Intelligence for IT Operations workshop white paper," arXiv:2101.06054.
2021.
[5] F. Eberhardt and R. Scheines, "Interventions and causal inference," Philosophy of Science, vol. 74, no. 5, pp. 981-995, 2007.
[6] I.. Bottou, J. Peters, J. Qaiñonero-Candela. D. X. Charles, D. M. Chickering, E. Portugaly, D. Ray. P. Simard, and E. Snelson, "Counterfactual reasoning and learning systems: The example of computational advertising." Journal of Machine Learning Research, vol. 14, no. 65, pp. 3207-3260, 2013.
[7] A. Jaber, M. Kocaoglu, K. Shanmugam, and E. Bareinboim, "Causal discovery from soft interventions with unknown targets: Characterization and learning," in Proc. Advances in Neural Information Processing Systems, Dec. 2020, pp. 9551-9561.
[8] D. Eaton and K. Murphy, "Exact Bayesian structure learning from uncertain interventions," in Proc. International Conference on Artificial Intelligence and Statistics, San Juan, Puerto Rico, Mar. 2007, pp. 107-114.
[9] Y. Wang. C. Squires, A. Belyaeva, and C. Uhler, "Direct estimation of differences in causal graphs," in Proc. Advances in Neural Information Processing Systems, Montreal, Canada, Dec. 2018, pp. 3770-3781.
[10] D. Zhao,
Cai, and H. Li, "Direct estimation of differential networks," " Biometrika, vol. 101, no. 2, pp. 253-268, 2014.
[11] H. Yuan, R. Xi, C. Chen, and M. Deng, "Differential network analysis via lasso penalized d-trace loss," Biometrika, vol. 104, no. 4, pp. 755-770, 2017.
[12] B. Jiang, X. Wang, and C. Leng, "A direct approach for sparse quadratic discriminant analysis." The Journal of Machine Learning Research, vol. 19, no. 1, pp. 1098-1 1 134, 2018.
[13] Z. Tang, Z. Yu, and C. Wang, "A fast iterative algorithm for high- nigh-dimensional differential network," " Computational Statistics, vol. 35, no. 1, pp. 95-109, 2020.
[14] A. Ghoshal and J. Honorio, "Direct estimation of difference between structural equation models in high dimensions," 17X1v::100.12024, 2019.
[15] A. Hauser and P. Bühlmann, "Characterization and greedy learning of interventional Markov equivalence classes of directed acyelic graphs," Journal of Machine Learning Research, vol. 13,
no. 1. pp. 2409-2464, 2012.
[16] Y. Wang, L. Solus, K. Yang, and C. Uhler, "Permutation-based causal inference algorithms with interventions," in Proc. Advances in Neural Information Processing Systems, Long Beach, CA, Dec. 2017, pp. 5822-5831.
[17] N. R. Ke, O. Bilaniuk, A. Goyal, S. Bauer, H. Larochelle, B. Schölkopf, M. C. Mozer, C. Pal, and Y. Bengio, "Learning neural causal models from unknown interventions," arXiv:1910.01075. 2019.
[18] Brouillard, S. Lachapelle, A. Lacoste, S. Lacoste-Julien, and A. Drouin, "Differentiable causal discovery from interventional data," in Proc. Advances in Neural Information Processing Systems, Dec. 2020, pp. 21 865-21 877.
[19] C. Squires, Wang, and C. Uhler, "Permutation--asee -based causal structure learning with unknown intervention targets," in Proc. Conference Uncertainty in Artificial Intelligence, Aug. 2020, pp. 1039-1048.
[20] T. Verma and J. Pearl, "An algorithm for deciding a set of observed independencies has a causal explanation," in Proc. Conference on Uncertainty in Artificial Intelligence, Stanford, CA. Jul. 1992 pp. 323-330.
[21] Erdös and A. Rényi, "On Random Graphs I," Publicationes Mathematicae Debrecen, vol. pp. 290-297, 1959.

---

[22] K. Sachs, O. Perez, D. Pe'er, D. A. Lauffenburger, and G. P. Nolan, "Causal -rinain-signaling networks derived from multiparameter single-cell data," Science, vol. 308, no. 5721, pp. 523- 529, 2005.
[23] R. O. Ness, K. Sachs, P. Mallick, and O. Vitek, "A Bayesian active learning experimental design for inferring signaling networks," in Proc. Research in Computational Molecular Biology, Hong
Kong, May 2017, pp. 134-156.
[24] A. Dixit, O. Parnas, B. Li. J. Chen, P. Fulco, L. Jemnn-Amon, N. D. Marjanovic, D. Dionne, T. Burks, R. Raychowdhury, B. Adamson, T. M. Norman, E. S. Lander, J. S. Weissman, N. Friedman, and A. Regev, "Perturb-seq: Dissecting molecular circuits with scalable single- cell RNA profiling of pooled genetic screens," Cell, vol. 167, 7, pp. 1853-1866.e17, 2016.
[25] A. Ghoshal and J. Honorio, "Learning linear structural equation models in polynomial time and sample complexity," Proc. International Conference on Artificial Intelligence and Statistics, Playa Blanca, Lanzarote, Canary Islands, Apr. 2018, pp. 1466-1475.
[26] M. Pourahmadi, "Covariance estimation: The glm and regularization perspectives." " Statistical Science, vol. 26, no. 3, pp. 369-387, 2011.
[27] P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu, "Hiis--dimensional covariance estima- tion by minimizing & (i-penalized log- log-determinant divergence," Electronic Journal of Statistics,
vol. 5, pp. 935-980, 2011.
12


Reviews:
[{"review_id": "vVYBQ38WIA", "reviewer": "Reviewer_wJ1B", "summary": "The paper consider the problem of learning the interventional Markov equivalence class of causal directed acyclic graph from observational and interventional data where the intervention targets are unknown and there are no unobserved variables. This problem and its variation havve been previously studied by Squires, Wang, and Uhler (2020) among others and is an important problem in the causal inference literature. The main contribution of the paper is an algorithm that is significantly faster than the permutation search algorithm (UT-IGSP) of Squires, Wang, and Uhler 2020 while also having finite sample guarantees which is lacking for UT-IGSP.  However, the paper makes slightly stronger assumptions than the UT-IGSP algorithm in specific form of interventions allowed: that the interventions must change the noise variances, and only works for linear SEMs. The authors also demonstrate the superiority of their method on rigorous synthetic and real world experiments.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n- The paper is well written and the problem is well motivated.\n- Technically, the authors largely build on the work of Ghoshal and Honorio (2019) for directly learning the difference between structural equation models (SEMs) to learn the set of intervened nodes and their parents. While Ghoshal and Honorio (2019)'s algorithm was proposed for the problem of directly estimating the difference DAG of two SEMs under the assumption that noise variances are invariant between the two linear SEMs, one of the key contributions of the paper is to recognize that the main ideas of the algorithm lends itself well to the problem of estimating the target of interventions from observational and interventional data without significant assumptions on the interventional setting.\n- While the main steps of the algorithm are essentially the same as Ghoshal and Honorio (2019)'s algorithm: estimate difference of precision matrices, remove vertices for which the difference of precision matrices has all zeros, then construct an ordering over subsets of remaining vertices, and finally remove edges (in this case vertices) by estimating difference between precision matrices over subsets of vertices; the authors also leverage additional non-trivial insights from the problem like (i) some of the non-intervened targets can be estimated from the covariance matrices, (ii) the ordering can be estimated by only estimating difference of precision matrices over only sets of two nodes, and (iii) finally constructing orderings over equivalence classes, to propose an algorithm whose computational complexity is exponential only over the size of the largest equivalence class. The size of the largest equivalence class can be significantly smaller than the set of changed nodes (in the difference of precision matrices).\n- Another improvement over Ghoshal and Honorio (2019) is the choice of algorithm used to estimate the difference between precision matrices which has a complexity of $O(p^3)$ instead of the $O(p^4)$ used by the former.\n- The authors obtain finite sample guarantees for their method and obtain conditions for high-dimensional recovery.\n- Synthetic experiments demonstrate that the proposed algorithm is significantly faster than UT-IGSP while being comparable in accuracy. Real world experiments are also insightful and demonstrate the applicability of the method even though the method was designed for linear SEMs.\n\n# Weaknesses\n1. Example 1 is incorrect. Node 2 should not be part of $J_0$ since node 2 is not part of $S_{\\Delta}$.\n2. The high-dimensional results are obtained under the assumption that the $\\ell_{1}/\\ell_{\\infty}$ norm of  $\\Sigma^{(1)}$  is constant which is unreasonable since the covariance matrices are generally dense (especially under the assumption that the individual SEMs are dense) and the $\\ell_{1}/\\ell_{\\infty}$ norm is O(p). In comparison, Ghoshal and Honorio (2019)'s method depends on  $||\\Sigma^{(1)}||_{\\infty}$ (element-wise infinity norm).\n\n# Other comments\n- $\\ell_{1}/\\ell_{\\infty}$ group norms are not defined and it is not clear that $||.||_{\\infty}$ is the element-wise norm of a matrix.\n- Line 163: the notation $an_{I}(j)$ has not been defined at this point to mean the ancestors of j in the set $I$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors mention that they assume linear models and that this must be checked in real world data to ensure causal conclusions are not misinterpreted. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "nItAqghmdIO", "reviewer": "Reviewer_LsC2", "summary": "Given two datasets generated from two DAGs, where the second DAG is assumed to be created from the first DAG by varying the noise level in a subset of nodes (called intervened nodes) in the linear structure equation model, this paper proposed an efficient algorithm to identify the subset of intervened nodes and their parents.\n\nThe proposed algorithm consists of three steps. First, apply precision difference estimation (PDE) to identify the set of non-intervened nodes. This is feasible based on the established fact that the diagonal entry of the precision matrix difference is non-zero if and only if the corresponding node or its child receives intervention. Second, from the set of non-intervened nodes identified from step 1, form equivalent classes. Third, those equivalent classes are further processed in step 3.\n\nThe computational complexity of PDE is cubic w.r.t the number of nodes. In step 1, PDE nees to be run multiple times. Furthermore, in step 3, the complexity could be exponential. The algorithm is provided to be consistent in Theorem 1. The sample complexity bound is also established in Theorem 3.\n\nIn the experimental results, the proposed algorithm is shown to be able to recover the ground truth set of intervention targets with high precision given large number of samples. It's also much faster than its competing alternative of UT-IGSP algorithm. the proposed algorithm is also further evaluated on real-world datasets, including protein signaling data and perturb-seq gene expression data.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To the best of my knowledge, the major contribution of this work, i.e. scaling up the identification of intervened nodes given a pair of datasets, seems novel. The experiments show it runs much faster than the baseline approach UT-IGSP.\n\nWill it be difficult to implement the soft intervention in (4)? Does this require the identification of the first DAG structure to determine its noise level?\n\nThe exponential complexity of step 3 is still worrisome. Can the authors present some edge cases where the algorithm might get stuck in this step when the size of A_l becomes too large?\n\nIn section 5.1, the precision seems much lower when the number of samples is 2000. In real-world datasets, does this mean the number of intervened samples have to be at the scale of thousands?\n\nIn the experimental section, besides UT-IGSP algorithm, is there any there baseline approach the proposed algorithm can compare against? To establish the efficiency of the proposed algorithm, it might be more convincing to compare it against at least a few benchmark algorithms.\n\nIs the ADMM solver for the PDE in Equation (6) the most efficient algorithm? Since PDE will be used multiple times in step 1 and 2, it might be useful to explore a more efficient solver of the PDE. Cubic complexity w.r.t. the number of nodes means the algorithm cannot scale to thousands of nodes, correct?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I didn't see any negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "5NMk4dPolxR", "reviewer": "Reviewer_ovCV", "summary": "This paper considered estimating the intervention target nodes in the linear structural equation model with Gaussian noises. The proposed method was built upon the difference in precision matrices across observational and interventional datasets, under the soft intervention setting and sparsity assumption. The authors provided a comprehensive discussion on their algorithm including computational complexity, theoretical analysis, and sample complexity. My main concerns lie in their motivation (about intervention recovery), novelty comparing with existing literature, and utility of the soft intervention setting.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper focused on identifying the intervention target nodes in the linear structural equation model, by defining a soft intervention setting and leveraging the ADMM-based method proposed in B. Jiang et al (2018). The sparsity and normality assumptions are required to guarantee computational efficiency and theoretical consistency. I have several concerns regarding their motivation (about intervention recovery), novelty comparing with existing literature, and utility of the soft intervention setting. \n\n1. *Motivation on Intervention Recovery*: In this paper, the authors care about intervention recovery and causal discovery based on both interventional and observational datasets. I agree the latter one is one of the most important topics in causal structural learning, while why do we care about the unknown interventions? Just one sentence regarding gene-editing example was included in the current paper. The authors should discuss more as it may be the main contribution of this work.  \n\n2. *Novelty Comparing with Existing Literature*: The main idea of this paper is to estimate the intervention nodes from the difference in precision matrices across observational and interventional datasets. There were actually many similar/related works proposed while haven't been discussed in this paper. For instance, Ghassami, AmirEmad, et al (2020) considered causal equivalence of two DAGs *also based on the precision matrices*.  Jaber, Amin, et al (2020) formulated graphical characterization to test whether two pairs of causal graphs and their corresponding interventional target sets. The authors should discuss the contributions beyond these works.\n\n-- Ghassami, AmirEmad, et al. \"Characterizing distribution equivalence and structure learning for cyclic and acyclic directed graphs.\" International Conference on Machine Learning. PMLR, 2020.\n\n-- Jaber, Amin, et al. \"Causal discovery from soft interventions with unknown targets: Characterization and learning.\" Advances in neural information processing systems 33 (2020).\n\n3. *Utility of Soft Intervention Setting*: This paper considered a soft intervention setting that does not remove causal effects on intervention target nodes and claimed that this setting is more practical. It seems such a setting is more friendly to develop theory and related methods, but less related to utility. It will be better to elaborate more on this with some concrete examples.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors claimed their method is limited to linear SEMs. However, the sparsity and normality assumptions are also limitations. The authors could consider improving their motivations and enhancing their contributions, as detailed in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an algorithm for estimating the unknown intervention targets in a causal linear structural equation model (SEM) with Gaussian noise. The paper considers observational and interventional data generated under soft interventions.

This paper was viewed as a borderline paper.

The authors learn the set of intervened nodes (and their non-intervened parents) by building on the work of directly learning the difference directed acyclic graph between SEMs by Ghoshal and Honorio (2019). The main steps of the proposed algorithm are essentially the same as Ghoshal and Honorio (2019)'s algorithm based on estimating the difference of undirected graphical models (inverse covariance matrices). In addition to that, the authors use non-trivial insights from the problem at hand.

If accepted, I recommend to include the following clarifications and modifications:
- I will give the benefit of the doubt regarding experiments. Please try a relatively larger number of samples, so that the F1 score is closer to 100%, thus validating the high-probability exact recovery statement.
- Please assume boundedness of the product $M\_\\Sigma M\_{\\Gamma,\\Gamma^T}$, where $M\_\\Sigma = \\max( \\| \\Sigma^{(1)} \\|\_{1,\\infty} , \\| \\Sigma^{(2)} \\|\_{1,\\infty} )$ and $M\_{\\Gamma,\\Gamma^T} = \\max( \\| \\Gamma\_{S,S}^{-1} \\|\_{1,\\infty} , \\| (\\Gamma\_{S,S}^T)^{-1} \\|\_{1,\\infty} )$, where $S$ is the support of the precision matrix $(\\Sigma^{(2)})^{-1} - (\\Sigma^{(1)})^{-1}$ and $\\Gamma = \\Sigma^{(2)} \\otimes \\Sigma^{(1)}$. I agree with the authors that this change is possible.
- Please check for typos (e.g., Line 250 and Algorithm 2 uses $\\Sigma_1,\\Sigma_2$ instead of $\\Sigma^{(1)},\\Sigma^{(2)}$.)
- Please take into account the comments from the reviewers, e.g., regarding additional literature comparison, exponential complexity.

Decision: Accept (Poster)