Efficient Identification of Direct Causal Parents via Invariance and Minimum Error Testing
Authors: Minh Nguyen
Mert R. Sabuncu
Venue: Accepted by TMLR ()

Abstract: Invariant causal prediction (ICP) is a popular technique for finding causal parents (direct causes) of a target via exploiting distribution shifts and invariance testing (Peters et al., 2016). However, since ICP needs to run an exponential number of tests and fails to identify parents when distribution shifts only affect a few variables, applying ICP to practical large scale problems is challenging. We propose MMSE-ICP and fastICP, two approaches which employ an error inequality to address the identifiability problem of ICP. The inequality states that the minimum prediction error of the predictor using causal parents is the smallest among all predictors which do not use descendants. fastICP is an efficient approximation tailored for large problems as it exploits the inequality and a heuristic to run fewer tests. MMSE-ICP and fastICP not only outperform competitive baselines in many simulations but also achieve state-of-the-art result on a large scale real data benchmark.

Published in Transactions on Machine Learning Research (09/2024)
Efficient Identification of Direct Causal Parents via Invari- ance and Minimum Error Testing
Minh Nguyen
bn24/@cormell.edv
School of Electrical and Computer Engineering, Cornell University and Cornell Tech
Mert R. Sabuncu
msabuncu&@cornnlll.ee
School of Electrical and Computer Engineering, Cornell University and Cornell Tech Department Radiology, Weill Cornell Medicine
Reviewed on OpenReview: https: openreview. net/ forun? id- 3GVMFFGVRR
Abstract
Invariant causal prediction (ICP) is a popular technique for finding causal parents (direct causes) of target via exploiting distribution shifts and invariance testing (Peters et al.) 2016). However, since ICP needs to parents when distribution shifts only affect few variables, applying ICP to practical large scale problems is challenging. We propose MMSE-ICP and fastICP, two approaches which employ an crror incquality to address the identifiaiiltt problem of ICP. The inequality states that the minimum prediction error of the predictor using causal parents is the smallest among all predictors which do not use descendants. fastICP is an efficient approximation tailored for large problems as it exploits the incquality and a heuristic to run fewer tests. MMSE-ICP and fastICP not only outperform competitive baselines in many simulations but also achieve state-of-the-art result on large scale real data benchmark.
exponential number of tests and fails to identify
1 Introduction
Causal discovery (CD) can offer insights into systems' dynamics (Pear] 2018 which are helpful for influencing some outcomes (e.g. having diseases not) or creating robust ML models. For example, model based on a target's causal parents can robustly predict the target despite various distribution shifts. CD can be global or local: global CD scarches for the complete causal graph while local CD only searches for causal relations surrounding a specific target Y. Thus, global CD is often intractable as the search domain grows exponentially with the number of variables. Local CD more tractable and sufficient if the goal is to change Y through interventions or to build domain-invariant ML models of Y. Recently, many works have built on local CD to improve ML models' out-of-distrrbutiin generalization
et al. 2018
Magliacane et al. 2018
Arjovsky et al. 2019 Christiansen et al. 2021
Invariant causal prediction (ICP) is local CD method that finds the causal parents of Y using the invariance property: the distribution of Y conditioned on all of its causal parents will be invariant under interventions on variables other than Y (Peters et al.) 2016). Specifically, ICP tests all subsets of variables for invariance and outputs the intersoction (denoted as Sicr) of all invariant subsets. As the number of subsets grows exponentially, applying ICP to large problems (> 20 variables) difficult. Besides, ICP is guaranteed to identify all causal parents only when every variable in the system except Y is perturbed (Peters et al, 2016). However, in many practical problems (e.g. problems in cell biology with 20,000 variables), it is almost impossible to perturb all variables (Uhler 2024). With limited perturbation/ perturbationninteeevettoo /ite/eeeteeennnn ICP may fail to
identify causal parents (Rsenfeld et al. 2021 Mogensen et al. 2022 as disjoint subsets can be invariant,
yielding an empty intersection (see Figure
Invariant ancestry search (IAS) addresses ICP's failure identify causal parents by outputting the causal
ancestors of Y instead MMogensen al.
2022 The causal ancestors identified is the union (denoted

---

Published in Transactions on Machine Learning Research (09/2024)
E
X2
X1
Figure 1: Consider this directed acyelic graph (DAG) representing a noisy causal structural model as motivating example, where no causal mechanism is noise-free and thus there are no duplicate variables. Let E denote the variable capturing the environment (or context) (Mooij et al.) 2020p. Its children are directly affected by intervention. This reflect distribution shifts between contexts. Y the target variable. SICP 0 because the invariant sets are {X1}, {X2}, and {X1, X2]. In contrast, SIAS {2), Our methods output {Xi} since the prediction error of (X1) less than (X2)'sss.
STAS) of all minimally invariant subsets. A set is minimally invariant if none of its proper subsets is invariant (Mogensen et al., (002)). Like ICP, SIAS can also be used to construct stable predictor of Y across environments even though it is not the most compact stable predictor. Besides, intervening ancestor may not be as effective in influencing the value of Y as intervening on a parent. IAS can be sped up by only testing subsets up to a certain size at the cost of potentially finding fewer causal ancestors, thus trading accuracy for speed.
We propose two approaches that employ an error inequality to address the identifiability and scalability problem of ICP. The error incquality implies that the prediction error of the predictor using Y's causal parents is the smallest among all predictors which do not use Y's descendants. Thus, the first approach, MMSE-ICP (short for minimam mean squared error ICP), finds invariant sets that do not contain Y's descendants and outputs the invariant set with the smallest error for predicting Y. The second approach is fastICP, an efficient approximation that relies on a hcuristic and constrained search scheme (sce Section 3.4). lastICP also exploits the error inequality to reduce the number of tests for invariance to identily the causal parents. Consequently, fastICP can handle large-scale problems with numerous variables. Experiments on simulated and real data show MMSE-ICP and fastICP outperforming competitive baselines.
2 Background
In different anviromments/settinng data are generated using different generative mechanisms. An interven- tion refers perturbation of generative mechanism of specific variable (Pearl 2009). Observational setting indicates no perturbation. Interventional sctting indicates tal dala belong to interventional setling in which the interventions are known (which variables are perturbed and how are they perturbed). Most naturally occurring distribution-shift data also fall under interventional setting, however the interventions are unknown.
more variables perturbed. Experimen-
Many CD methods use solely observational data. Constraini-based (Spirtes et al. 2000) and score- based Chickering 2002) methods can identify up the Markov equivalent class (MEC) of the true graph, leaving some edges with unresolved direction. With additional assumptions (e.g. non Non--aussianity (Shimizu
et al.
2006
nonlinearity (Hyvärinen & Pajunen 1999:
Hoyer et al. 2008 Zhang & Hyvärinen 2009 Peters
et a.l.
2014
Zhang et al.
2015 Rolland et al.] 2022). or independent causal mechanisms (Janzing et al.
2012
methods are able to resolve more edges Glymmuu et al. 2019). Optimization base methods (Zheng
ct al.
2018
Geffner et al.) have become popular recently despite the lack of identifiability guarantees Moo-
gensen al. 2022).
Having data from multiple settings can improve identifiability. When interventions are known, undirected edges in the MEC first estimated using observational data can be resolved using interventional data. (He & Other approaches jointly model interventional and observational data (Hauser & Bühlmann,
Geng 2008
2012
2015
Wang et al.] 2017). There are also optimization- based methods that leverage both types of
data
Lorch et al. 2021 Lippe et al. 2022). In contrast, UT-IGSP (Squires et al. 2020), SDI (Ke et al. 20023) Brouillard et al. 2020) are methods that can work with unknown interventions. ICP PPeters
and
DCDI
ctt al.
2022) and TAS (Mogensen 2022) both assume unknown interventions and only depends on the invariance property identify causal structures. Our approaches also assume unknown interventions.
2016 Pfister et al.] 2019 Gamella & Heinze-Deml 2020 Martinet et al.
et al.
2

---

Published in Transactions on Machine Learning Research (09/2024)
Prototypical global CD methods such as PC (Colombo et al 2014 Li et al. 2019 and GES Chickering 2002) can be slow, so faster global CD ones (Cheng et al. 2002 Tsmardinos et al. 2006 Ramsey et al. 2017 have been proposed, although they make strong assumptions that may be inappropriate in some problems. In contrast, local CD methods only identify local cansal structures surrounding a target variable. For example, several algorithms only search for the Markov Blanket (MB) of the largel (i.e. its parents, children, and spouses) (Koller et al. 1996 Margaritis Thrun 1999; Tsamardinos et al.) 2003 Gao & Ji 2015; Yang eet al. 2021). Consequently, local CD methods often have faster runtime or can afford to make milder assumptions leading to more accurate identification. ICP and IAS only search for parents and ancestors of the target respectively, omitting all descendants of the target. They both make very mild assumptions and offer guarantees in terms of false positive rates. Another local CD approach is CORTH (Soleymani et al. 2022) which is based on double MI. (Chernozhukox et al.) 2018). CORTH assumes that is not a parent of any other variable (a strong assumption which can be unrealistic) and that is a linear combination of other variables, and achieves linear runtime finding parents of Y.
3 Method
3.1
Definitions and assumptions
We represent causal relations between variables using a Directed Acyelic Graph (DAG), where each node is a variable and directed odges between nodes represent direct causal influence (Pear] 2009 We use the usual notations from graphical models (Lauritzen 1996). Specifically, PA(Y), CH(Y), ), AN(Y), DE(Y), and ND(Y) denote the parents, children, ancestors, descendants, and non-descendants of Y respectively, Thus, PA(Y) C AN(Y) C. ND(Y) and CH(Y) C DE(YY. There is an additional node E in the graph to denote the different environments (or contexts) (Mooij et al. 2020). A set of variables /paile/////dc/oosssee S is invariant if Y IL E/S. As is common in the causal inference literature, we assume (1) no hidden confounder, (2) no intervention on Y, (3) no feedback between variables, (4) independence of mechanisms, and (5) independent additive noise structural causal models (SCMs), with no noise- frise-free mechanisms and duplicate variables. We further assume that (6) the additive noise variables in the SCM have unbounded support (e.g. Gaussian assume that (7) E. is exogenous (i.e.,
noise). Like prior work (Mogensen al. 2022 Mooij et al. 2020
E has no parent).
3.2 ICP and IAS
ICP exploits distribution shifts between different environments E to learn a subset of PA(Y) (Pteers et al, 2016). Given a test for the hypothesis Ha,s that S is invariant, ICP outputs the intersection of all in- variant subsets. Specifically, SiCP = Ns. not rejected S. In contrast, IAS tries to identify a subset of AN(Y) MMgenssen et al. 2022h. Let Í be the set of all sets S for which Ho.s is not rejected. Define MI S E VS' CS S' & 7). Thus, SLAS = UsE S. Although Peters et al. 2011)) proposed two different tests for invariance, Ho.s; the approximate test based on residuals of a predictor (Method II) is usually used because of its speed. Specifically, this statistical test chocks whether the distribution (means and variances) of the predictor's errors across environments are the same. The predictor fitted using the data from all environments (see Appendix A for more details).
3.3 Finding causal parents by minimizing error
Instead of taking the intersection or union of invariant subsets, we rely the concept of minimum mean squared error predictor to find the causal parents. The mean squared error (MSE) of a predictior (()) with input variables X of larget. Y is Exy(Y {())²², where E denotes expectation. Let the minimum MSE achieved by an optimal predictor YM( with input variables X be MMSE(X). Note that this is always with respect to predicting a target variable Y. It is well-known that, if the minimization is uncon- strained, the MMSE(X) is the conditional expectation Eyix(Y|X), and the corresponding MMSE is equal to Ex Varyix(Y1)))) Leon-Garcin 1994), where Var denotes variance. In practice, will assume that
3

---

Published in Transactions on Machine Learning Research (09/2024)
large-capacity model, trained enough data with least square loss, can approximate this MMSE estimator. The following provides the theoretical grounding for MMSE-ICP.
3.3.1 Minimum mean squared error inequality
Lemma 3.1
(Error Inequality). Let X, and X2 denole two sels of variables, not necessarily mulually exclusive. Then: MMSE(X, U 22) S MMSE(X1). Equality holds if Y L X2
Proof. MMSE(X; X2) Ex, X miny Eyxx,,,, ( Ex, Ex,/x, miny ExIx,,x, 872
(Y
Let (M,, x2)== == arg miny Xx 8),, then:
xy (Y (M, & XX va
(1)
Since expectation is monotonic,
+ Ex, X, Xyxx.x, VMr(X, x2)) s Ex,xx, XY,x, (Y (Y -)y] =Evxx, 8)2, Vg (2)
Since Equation 2 holds for every Y, it also true for (Mi) arg ming Exix (Y - 8)2-
Ex, Ex Ey PM (xx,,))))) x2))² S Ex, Erix, (Y FM((X))) MMSE(X, X22 MMSE(X,)
MMSE(X,)
(3)
(4)
Equality occurs when (X, X2) PM (Xi), i.e.;
arg min Ex - 8)²² arg min By,x, (Y -)2, X2
(5)
Y 11 X, then one can easily show that Equation holds.
Corollary 3.2. the causal DAG that satisfies the assumptions stated in Section 3.1 for all subset S of ND(Y):
MMSE(S) MMSE(PA(Y)))
MMSE(S) MMSE(PA(Y)), if and only if PA(Y) CS, and
MMSE(S) > MM)E(PA(Y)), if and only if PA(Y) g S.
Since S C ND(Y), it follows from the Causal Markov condition that Y JL S SIPA(Y). By Lemmna 3.1 MMSE(S U MA(Y)) Furthermore, also by Lemma 3.1 MMSE(PA(Y)) U =)=MMS((PA())) Hence, MMSSES))MMSE(PA(Y))
Proof. The first inequality is immediate corollary of Lemma 3.1
It is casy to show that, in the assumed DAG, MMSE(PA(Y)) = of, where of the variance of the independent additive noise for Y. Furthermore, for any S which a subset. ND(Y), MMSE(S) = Es (f (FA(())))) + oÿ. where (PA(Y)) is the functional mapping from Y's parents to Y in the SCM. It can be shown that in the assumed noisy SCM where the noise distribution has unbounded support (e.g. Gaussian noise), Varyis(fy (PA(Y)){S) > 0 if and only if PA(Y) & S and Vary (PA(Y))) = 0 if and only if PA(Y) S.
For example, in Figure I MMSE((X2)) > MMSE((XX,,X)) MMSE((X1)). Furthermore, since (X1, X2} has 2 elements while (X1) has only element, we can deduce that (X1) is the causal parent and not {X2).

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 1: MMSE-ICP
Input: X, X2. Xa.Y
Output: Potential parents of Y if is invariant(E) X,Y, then return 0 candidates 1
for S C {X1, x,..., Xa} in increasing cordinality order do
if ESL E candidates such that S' CS then continuc
if is issinvariant({B X, Y) then candidates = candidates + [S]
return arg minmmmaaddddatte. MMSE(S)
3.3.2 Combining MMSE and invariance test
Algorithm [ combines the error inequality with the invariance test to find causal parents. Theorem 3.4 shows that Algorithm can identify all causal parents of Y as long as PA(Y) C DE(E). This implies that Algorithm usually requires fewer interventions than the number of variables for complete identification. For example, a single intervention at an upstream variable that affects all causal parents Y is sufficient. This is much more favorable than ICP, which may need as many interventions at as the number of variables (Poters) et al. 2016).
Lemma 3.3. S|S1 is invariant, then S2 = () all nodes in S1 that are not in DE(E) n NN((Y) from S₁ results another invariant set.
also invariant. In other words, removing
Proof. Since S₁ is invariant, Y IL E/S so S1 blocks all paths between E' and Y by d-separation Pearl 2009 If a node X is in S, but not in DE(E) n ND(Y), then one of these two cases must hold.
1. X is not on any blocking path S \ (X) still blocks all paths between E and Y.
2. X is on a blocking path between E and Y. Since E has no parent (see Section 3. X E DE(E) n DE(Y). Thus, this blocking path is out-going from Y. Removing all nodes on this path will keep the path blocked. The removed nodes are descendants Y so they are not in DE(E) n ND()))
In both cases, invariance is not affected by excluding X. Thus, excluding nodes in S that are not in DE(E) n ND(Y) results in S₂ that is also invariant.
Theorem 3.4 (Identifiabliity) Given that all tests of invarionce return the correct results and PA(Y) C DE(F), Algorithm 7 will always find the set of causal parents PA(Y).
Theorem 3.4 follows from Corollary 3.2 and Lemma 3.3 The loop Algorithm 1 finds invariant subsets of DE(E) NY which include PA(Y) when PA(Y) C DE(E). Amongst these subsets, PA(Y') has minimum MSE and is the most compact. The solution is unique (no other subset has the same MSE and cardinality) because other subsets with minimum MSE are all strict supersets of PA(Y) so they have larger cardinality than PA(Y).
Lemma 3.3 implies that for any invariant set S that is not a subset of DE(F)) n ND(Y), there exists an invariant set S2 that is a subset of S, (having smaller cardinality than 's) and of DE(E) n ND(Y). Since Algorithm I itcrates through the sets of variables in incrcasing cardinality order, will first find S2 and add S2 to the Tist. It. will later exclude S because S2 is a subset. of Sj. Thus, all invariant sets that are not subsets of DE(E) n ND(Y) will be excluded. PA(Y) will always be in the list because subset of PA(Y) is invariant.
3.4 Faster search sequence
Although Algorithm ! should be more accurate than ICP, it still needs run an exponential number of invariance tests. We propose Algorithm which is faster and consists of two stages.
5

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 2: fastICP
Input: E, X1, X2........... Xx. Y, MaxDepth
Output: Potential parents of Y
if is invariant E, X,Y,0) then return 0
// Find invariant set S = (X,....,
while not is_ Lni.aiiiaant.EXX Y. do candidates = S: S S
S MaxDepth}
if no candidates then return 0
arg écandidates statDependency(X,
// Prune invariant set while True do candidates = for Z E S do
10
if is s_iinarriant(E X, Y, {Z}) then
L candidates = candidates + [S] [2)]
11
12
if no candidates then break
13
else S = arg ming Ecandidates MMSE(S')
14 return S
FGES
UT-IGSP
ICP
ICP CORTH F1
LAS
MMSE-ICH ICP fastICP
Jaccard
Recall
1.0
0.5
0.0
102
10
10
102
10a
10
10a
10P
10a
Number of samples
Number of samples
Number of samples
Figure 2: Performance when Nint = d = 6 (Table 1 No. 1). Linear simulation. Reference set: PA(Y).
Stage aims find the largest invariant it removes potential colliders and their descendants, which might be unblocking paths from to Y, using the heuristic presented in Cheng et al. (1998). The heuristic assumes that blocking path by removing some nodes from the conditioning set decreases the statistical dependency between E and Y (Cheng et al. 1998). In Algorithm - MaxDepth is at one time. The statistical dependency can be measured using the invariance test of Peters et al. (2016) where the lower the statistical dependency, the higher the probability of being invariant. Stage 2, based on Proposition 3.5 removes variables from S one-by-one while maintaining invariance. The algorithm terminates when S PA(Y).
that includes PA(Y). Starting with the of all variables,
for the maximum number of nodes to be removed
Proposition 3.5. We are given that PA(Y) C DE(E), S is invariant and has the lowest MMSE amongst subsets with the same cardinality, and PA(Y) C S. For each Z E let S := S (Z}. If no subset S-z of is invariant, then PA(Y). Otherwise, PA(Y) arg min invariant S_z MMSE(S_Z).
Proof. If no subset S-z S is invariant, all nodes of must be on blocking paths because removing any node Z from leads to loss of invariance (unblocks a path from E Y). If multiple nodes are on the same blocking path, one node (e.g. W) can be removed and S-w is still invariant which contradictory. Thus, Z PA(Y) because otherwise, exchanging Z with the parent. in the same blocking path would result in

---

Published in Transactions on Machine Learning Research (09/2024)
Table 1: Different setups with different number of nodes (X1,..., Xa, Y, Y,,,, E), graph densities, number of interventions (Nine), and type of interventions. MB: Markov Blanket
No.
Density
MB size
Nit
Type
1.
6
0.240
2.98
6
Perfect
2.
6
0.145
2.58
1,2,3
Perfect
3.
6
0.158
2.89
1
Imperfect
4.
0.153
2.86
1
Noise
5.
100
0.010
3.30
1-5
Perfect
6.
100
0.050
26.99
1-5
Perfect
subset with the same cardinality but with smaller MMSE, which is contradictory. Since PA(Y), VZ E S, then S = PA(Y).
Suppose there exists Z S where S-z is invariant. Let's assume that PA(Y) g S -- aag min $ MMMS(SS22)
Since PA(Y) & S- but PA(Y) S Z' E PA(Y). Besides, S-z' is invariant but Z' $ S- S'z', there must be another node T S-z that is on the same blocking path as Z'.
Let : {Z', Consequently, S-z = {Z'} (T) and S S [T) S' U(z)
Since and Z' are on the same blocking path, S_r is also invariant. In addition, because 7' E PA(Y), T
must procede Z', i.c. Y 1L TJS' {Z') + Y 11 T|S- As a result, by Lemma 3.1 and Corollary 3.2
MMSE(S-22)) --) = MMSE(S U (T)) MMSE(S) = MMSE(S z' U (Z') MMSE(S-2222 -z))
This contradictory because MMSE(S 2 MMSE(S -T) by definition. Hence, PA(Y) C S-2'.
3.5 Complexity Analysis
For problem with V variables, the complexity of ICP and MMSE-ICP is 0(2V) as the number of invariance tests run is exponential. Stage 1 of fastICP is O(V * 2axDep)hh because of the number of candidates checked grows exponentially with MaxDepth. Stage 2 is O(V3). Thus, the complexity of fastICP is O(V MaxDephh + V2). When MaxDepth is less than V, fastICP is faster than ICP.
4 Simulation Experiments
4.1 Data
We generate synthetic datasets according to the assumptions in Section 3.1 (additive noise model with i..dd. Gaussian noise). Similar to Peters et al. (2016); Mogensen al. (0022) consider 2-cnvironment setups (observational and interventional). In each setup, 100 graphs are randomly generated. In graph, beside the target node Y and the environment indicator node E, there are d additional nodes ..,....,ah The edges from E to subset of (X Xa} specify the nodes that may be intervened on. The number of interventions (Nint) varies between different setups. We do not enforce the constraint that PA(Y) C DE(E) to test the robustness of the proposed methods when this assumption invalid. Values of node generated based on its parents' values, through linear or nonlinear functions. Beside linear simulations whereby all functions are linear, we also include nonlinear simulations (see Appendix B). For each graph, 50 sets of coefficients of the generative functions are drawn randomly. For each set of coefficients, with different sample sizes (102, 10 10a, 10"). The data are standardized along the causal order to prevent shortcut learning (Reisach et al. 2021). b. In the interventional environment, interventions are applied to a random subset of children of E. We consider 3 types of interventions: (1) perfect intervention which severs all causal dependencies from parents, (2) imperfect intervention which modifies causal relations between node and its parents, and (3) noise intervention in which the intervened variable's noise variance changes (Cooper
sample 4 datasets
& Yoo 1999 Peters al. 2016). The different setups summarized in Table 1

---

Published in Transactions on Machine Learning Research (09/2024)
ICP
ICP CORTH
IAS
MMSF-ICP
fastICP
Jaccard
Recall
1.0
0.0
10a
10a
10a
10a
10a
10
10a
10
10a
Number of samples
Number of samples
Number samples
Reference set: PA(Y)
ICP
ICP CORTH
LAS
MMSE-IC ICP
fastICP
Jaccard
F1
Recall
1.0
0.5
10a
10a
10
10a Number samples
10"
Number of samples
Number of samples
(b) Reference set: S*=DE(E) PA(Y)
Figure 3: Performance when Nint =1m==;:0 d-6 (Table No. 2). Lincar simulation. See Appendix C.1 for results
when Ni==2 3..
4.2 Baselines and implementation details
We compare MMSE-ICP and fastICP against ICP PPters et al. 2016) Mogensen et al. 2022) .GES- uses ICP to remove false positives in CORTH's output (Soleymani et al. 2022). Since CORTH assumes linear combination of its parents (similar to the simulation setup), CERP-COTH
MB (Ramscy et al. 2017). UT-IGSP (Squires et al. 2020 aand
competitive baseline. To test for invariance, MMSE-ICP and fastICP use the same test ICP and IAS. Specifically, the test checks whether the mean and variance of the prediction residuals (of regression model) is equal across environments. Linear regression is used for linear simulations while gradient boosted tree is used for nonlinear simulat ions (see Appendix A To keep the runtime of the invariance test comparable to ICP and LAS, MMSE is estimated by averaging the prediction residuals (see Appendix C.2 for experiments to test the robustness of MMSE estimation).
at 2. For ICP, TAS, UT-IGSP, MMSF-ICP, and fastICP, the signifi- cance level a is set 0.05. The paramcters of IAS (C and og) are according the original paper (Mo- gensen al., 2022). Since it is intractable to search exhaustively using ICP, IAS and MMSE-ICP for large restricted in these cases. In particular, ICP and MMSE-ICP only search within The 10 variables that are considered for further analysis are determined via
The MaxDepth hyper-parameter
d, their search scopes estimated MB of size 10.
L2-boosting (Friedman 2001 Bühlmann & Yu 2003 Hothorn et al. 2010 IAS only tests for sets with a
single element.
Jaceard similarity and Fi-score are used as metrics. The prediction compared against reference sot,, which could be either (1) the full set parents PA(Y) and (2) the set of perturbed parents S S*=DE(E)nPA(Y), Since IAS finds ancestors instead of parents, also look the parents' Recall rate.
8

---

Published in Transactions on Machine Learning Research (09/2024)
MC CCRRTT CORTI
IAS;
MMSE-ICP MB
fastICP
Jaccard
Recall
1,0
0.0
10a
10a
10
10a
10a
10
10a
10a
10
Number of samples
Number of samples
Number samples
Large sparse graphs (Table No. 5)
ICP MB
ICP CORTH
IAS
MMSE- MB
fastICP
Jaccard
F1
Recall
1.0
0.5
10a
10a
10*
10a Number samples
10a
Number of samples
Number of samples
(b) Large dense graphs (TTbble No. 6)
Figure 4: Performance for large graphs. Reference set: S Also see Figure 11 and 12 in the Appendix.
4.3 Results from linear simulations
When, Nin d 6, invariance-batt based algorithms should be able to discover all parents. Figure shows their results in this setting. With sufficient samples, invarianco-based algorithms outperform fGES-MB (observational constraint-based CD) and UT-IGSP. When the number of interventions is limited (i.e. Nint < d, Table I No. 2 2-6), identifying all direct parents using invariance is more challenging since some invariance subsets may be strict subset of the parents, i.c. |S*] < |PA(Y)]- Duc to the strict inequality, we only benchmark our approaches against wvarriacce-baed algorithms. For perfect interventions, MMSE-ICP and fastICP achieve similar performance and outperform the baselines in both Jaccard similarity and F1-score (Figure 3). The recall of our approaches the same as LAS's and higher than ICP's. Figure shows
ICP
MMSE-ICP
fastICP
ICP ml
MMSE-ICP,,
fastICP,
Jaccard
F1
Recall
1.0
10a
103
10
10a
103
10a
10a
10a
10
Number of samples
Number samples
Number of samples
Figure 5: Performance for nonlinear simulation. dm==1;d=6. Reference set: S nl: using nonlinear regression in invariance test. Also Figure [8 in the Appendix.

---

Published in Transactions on Machine Learning Research (09/2024)
that approaches often found most of the perturbed parents (S"). The same trends are observed for imperfect interventions (Figure 16), noise interventions (Figure 17,, and large sparse graphs (Figure 4a They hold for large sparse graphs since the estimated MB of size 10 is sufficient to cover the true MB (see
Table D... Although MMSE-ICP and fastICP should perform similarly when the former can exhaustively tost subsets, in practice, their performance may differ as they lest the subsets in different orders (increasing cardinality order for MMSE--IP and decreasing cardinality order for fastICP). With imperfect invariance test, the order of testing may impact the performance since some tests may more likely fail than others.
For large dense graph (Figure 4bj, MMSE-ICP and fastICP still outperform the baselines. Since the es- timated MB is much smaller than the true MB, methods that cannot search exhaustively will miss out many parents. ICP-CORTH is worse than ICP probably because CORTH's assumption that the target Y has no children more likely to be wrong. When the graph large and dense, MMSE-ICP cannot search exhaustively so the ability to search through all nodes gives fastICP an edge over MMSF-ICP.
4.4 Computation time analysis
To analyze the runtime complexity invariance based algorithms, we recorded the time each algorithm took when the number of nodes (d) varies. The data were generated from linear SCMs as outlined Section 4.1 but with varying d and N (number of samples) fixed at 1000. Table 2 reports the numbers of seconds elapsed when executing implementation was in R. we employed re-implementation in Python for fair comparison. The algorithms search through the full set of covariates (i.c. no pro-sclection of variables using Markov Blanket estimation).
AMD EPYC 7642 CPU core (@ 2.3GHz). For this benchmark, since the official ICP
Table 2: The average runtime in seconds of different algorithms for varying d.
Method
Language
d= d=6 6
d=
d= 12
d= 15
d= 18
d = 21
ICP
R
0.1610.01
1.78
17.66
339.5153.2
3600
> 3600
ICP
Python
0.06
0.41
3.28
30.2
224.6167.2
1794
MMSE-ICP
Python
0.06
0.42
3.30
29.9
225.5
1806
fastICP
Python
0.03
0.07
0.12+0.00
0.20
0.28+0.01
0.39
From these runtime values, confirm that ICP and MMSE-ICP both have exponential complexity in d. Furthermore, the additional computation overhead of MMSE-ICP as compared to ICP is negligible. In contrast, the runtime of fastICP is polynomial (quadratic) in d so fastICP is much more scalable than ICP and MMSE-ICP.
4.5 Results from nonlinear simulations
For nonlinear simulation, our approaches are still better than ICP (Figure SaurreBanc and Appendix C.4]. As predicted by Heinze-Deml et al. (201),, , it is sometime possible to use the lincar invariance test (invariance test with linear regression) to find causal parents in nonlinear simulations. However, it is preferable to use a nonlinear invariance test obtain more accurate results runtime not a constraint.
5
Experiment on gene expression data
5.1
Data
We apply our methods to a real-world large-scale yeast gene expression dataset with 6170 variables (Kem- meren et al. 2014). There are 160 observational samples and 1479 interventional samples. Each interven- tional sample corresponds an experiment where single Xş has been perturbed. Following Peters et al. 2016 Mogensen et. al. (0022,, assume that direct causal effect X-+Y exists (true positive) if the
10

---

Published in Transactions on Machine Learning Research (09/2024)
40
ICP MB
36
IAS
Number of True Positives
32
MMSE-ICP MB
TastICP
28
24
20
16
8
0
4
12
16
24
28
32
36
40
Number of Predictions
Figure 6: Performance on genes' parents prediction. The dotted line delincates perfect accuracy.
expression level of gene Y after intervening gene X lies in the 1% lower upper tail of the observational distribution of gene Y.
Since neither the ground-truth graph nor a separate set of validation data is available, we must use the same data for validation. Hence, we employ the same vross-validation scheme used in the original ICP paper to prevent information leakage (Peters et al. 2016). Specifically, when predicting whether X a parent of Y, we do include the sample when intervening on X₃ (if the sample exists) in the data used for inference, The interventional samples are split into 3 folds. In cach fold, two thirds of the interventional samples not containing X used as interventional data, and remaining interventional data are used for validation. Thus, for each target, we need to run the algorithms the same number of times the number of folds. Additionally, when looking for potential causes of Y, we exclude samples corresponding to intervention on Y (if it exists).
5.2 Baselines and implementation details
ICP and IAS used as basclines they give confidence estimates for individual predicted par- ents/ancestors. The same linear invariance test is used although the threshold is set at 0.01, fol- lowing Peteess et al.) (2016). L2-boosting (Friedman 2001 Bühlmann & Yu 2003 Hothorn et al. 2010) is used to estimate the MB of size 10 for ICP and MMSE-ICP. Even though fastICP can search exhaustively in simulations of 100 variables, it would too slow for this problem. Hence, we restrict the fastICP search scope to an estimated MB of 100 variables. ICP-CORTH excluded because takes more than days for one gene so obtaining the result for 6170 genes would take more than 18000 days. Instead scoring the methods' output at fixed thresholds, we ranked the set of predicted causal relations and score the most confident predicted relations.
5.3 Results
Figure f shows how the number of true positives vary as the methods are allowed to make more predictions. When the number of allowed predictions lower than 8, the performance of the methods are very similar. However, when the number of predictions is more than 10, MMSE-ICP is generally more accurate than ICP. Moreover, fastICP is the best approach for this task as can afford to search more widely for the parents of
11

---

Published in Transactions on Machine Learning Research (09/2024)
each gene. fastICP obtained 20 true positives when making 30 predictions (66% success probability), setting new state-of-the-art (SOTA) for this benchmark.
6 Discussion
While using only observational data for causal discovery (CD) is common, intorventional data with mech- anism changes are very valuable for inferring causal relations. In fact, changes (e.g. different equipments, locations, demographics, weathers) often arise naturally in distribution-shift data. Given their abundance, harnessing changes for CD would reveal insights useful for understanding and manipulating complex sys- tems. However, exploiting changes in general is difficult they are often imperfect interventions (merely altering the mechanism generating a variable) alfecting some unknown variables. In contrast, controlled experiments are perfect interventions that fix designated variables to predetermined values (Tian & Pearl, 2001 Eberhardt & Scheines 2007). As such, invariance-based CD methods are appealing because they can work with unknown interventions.
Like other invariance- based CD methods, ours also make no assumption about where interventions are and what precisely the effect of interventions may be. We only assume that there is no intervention on the target. This make our approaches appealing in many problems whereby specifying what intervention change of environment actually mcans is difficult. In addition, unlike ICP which needs a sufficient number of interventions to identify all parents (Rosenfeld et al.] 2021 Mogensen et al.) 2022). our approaches can identify all parents even if they are only indirectly effected by interventions. Thus, our methods can be applied to problems where is logistically challenging to exhaustively intervene on many variables (Uhler) 2024). Besides, our work may have implications for robust representation learning. Building ML models with invariant representations has become popular recently since they can generalize better to distribut ion-shitt data (Arjovsky et al., 2019 Rosenfeld et al. 2021 Nguyen et al. 2024c b). It may be possible to build even more accurate invariant representations by identifying causal variables (Subbaswany et al. 2019 Thus, an efficient way to find causal variables from distribution-shin data, fastICP can be a key to more adaptive ML. models.
In this work, we proposed two algorithms: MMSE-ICP which has similar runtime but better recall than ICP; and fastICP which is more scalable. Both approaches outperform multiple baselines in simulations. fastICP also achieves SOTA result the large-scale Kemmeren et al. (2014)'s I benchmark. MMSF-ICP and fastICP are based general theoretical results are orthogonal to the implementations of invariance test and MSE estimation. There are several unaddressed questions that are left as fulure work.
First, despite its speed, fastICP still has worst-case exponential complexity that is controlled by the MaxDepth parameter. The larger the MaxDepth, the closer fastICP is to ICP (i.c. testing exponential number of subsets). Hence, selting a smaller MaxDepth will result in greater speed-up, with an increased risk for inaccurate results. In our experiments, MaxDepth of 2 seems to be good trade-off between accuracy and speed the simulations and the real data. Of course, there may be adversarial case where MaxDepth parameter needs to be increased to yield correct results. However, these adversarial cases seem rare in real data. Although additional speed-up can be achieved by testing multiple subsets at once using amortization techniques such as (Nguyen et al. 2024a), whether there is a general invariance- polynomial-complexiyy algorithm remains an open question.
Second, our algorithms assume accurate invariance test and MMSE estimation. The theoretical analysis of the proposed algorithms' performance under imperfect invariance test is challenging since unlike ICP, they are greedy algorithms that do not exhaustively test all subsets. Thus, the performance bounds are problem-specifiic (dependent on the ground-truth graph) as the invariance test might fail along some greedy optimization path even with perfect MMSE estimation. In practice, MMSE estimation may be inaccurate as well so we need to account for the probability of making a consequential error in ordering the estimated MMSE values. MMSE estimation may be imperfect due to insufficient samples or misspecified model class. Ensuring good MMSE estimation an empirical exercise that will require careful experimentation. We recommend users to account for the uncertainty in the predicted MMSE via approaches like bootstrapping the test. data (Raschka 2022) double ML. (Chernozhukov et al. 2018).
12

---

Published in Transactions on Machine Learning Research (09/2024)
Acknowledgments
Funding for this project was in part provided by the NIH grants RO1AG053949, ROLAG064027 and R01 RG07009888 and the NSF CAREER 1748377 grant.
References
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Pase Paz. Invariant risk minimization. Eprint arXiv:1907.02805 2019.
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Dislerentiable causal discovery from interventional data. volume 33, pp. 21865 21877, 2020.
Peter Bühlmann and Bin Yu. Boosting with the 1 2 loss: regression and classification. Journal of the American Statistical Association, 98(462):324-385 -399, 2003.
Jie Cheng, David Bell, and Weiru Liu. Learning bayesian networks from data: An efficient approach based on information theory. On World Wide Web at http://www. cs. ualberta. ca/" jcheng/ /bpp.. htm, 1998.
Jie Cheng, Russell Greiner, Jonathan Kelly, David Bell, and Weiru Liu. Learning bayesian networks from data: An thoormationn-hoorry based approach. Artificial Intelligence, 137(1):43-90 2002. ISSN 0004-3702. doi: aTT:CCle/p1//900457000000111
URL wathhttp:://// //ww::///wwwwwwe
Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural paramcters, 2018.
David Maxwell Chickering. Optimal structure identification with greedy scarch. JMLR, :5 2002.
Rune Christiansen, Niklas Pfister, Martin Emil Jakobsen, Nicola Gnecco, and Jonas Peters. A causal framework for distribution generalization. IEEE TPAMI, 44(10):6614 6630, 2021.
Diego Colombo, Marloes H Maathuis, et al. Order-independent constraint-based causal structure learning. JMLR, 35(1):3741 3782, 2014.
Gregory Cooper and Changwon Yoo. Causal discovery from a mixture of experimental and observational data. In Proceedings of UAI, pp. 116 116-125, 1999.
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of science, 74(5): 981-995, 2007.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Juan L Gamella and Christina Heinzo-Dent Active invariant causal prediction: Experiment selection through stability. In Processing of NewrIPS, volume 33, pp. 15464 15475, 2020.
Tian Gao and Qiang Ji. Local causal discovery of direct causes and effects. volume 28, 2015.
Tomas Geffner, Javier Antoran, Adam Foster, Wenbo Gong, Chao Ma, Emre Kiciman, Amit Sharma, Angus Tamb, Martin Kukla, Agrin Hilmkil, et al. Deep end-to-end causal inference. In NeurIPS 2022 Workshop on Causality for Real-world Impact.
C. Glymour, K Zhang, and P Spirtes. Review of causal discovery methods based on graphical models. Frontiers in Genetics, 10:524, 2019.
Alain Hauser and Peter Bühhlmann Characterization and greedy learning of interventional markov equiva- lence classes of directed acyelic graphs. JMLR, 13(1) (:2499 24649-2444, 2012.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Alain Hauser and Peter Bühhmmnn. Jointly interventional and observational data: estimation of interven- tional markov equivalence classes of directed acyelic graphs. Journal of the Royal Stalistionl Sociely: Series B: Statistical Methodology, pp. 291 318, 2015.
Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. JMLR, ((Nov):2523-25)) -2447, 2008.
Christina Heinze-Deml, Jonas Peters, and Nicolai Meinshausen. Invariant. causal prediction for nonlinear models. Journal of Causal Inference, 6(2), 2018.
Torsten Hothorn, Peter Bühlmann, Thomas Kneib, Matthias Schmid, and Benjamin Hofner. Model-based boosting 2.0. JMLR, 11(11)2210-22113, 2010.
P Hoyer, D Janzing, J Mooij, J Peters, and B Schölkopf. Nonlinear causal discovery with additive noise models. Proceedings of NIPS, 21, 2008.
A Hyvärinen and Petteri Pajunen. Nonlinear independent component analysis: Existence and uniqueness results. Newral networks, 12(3):429-433 439, 1999.
Dominik Janzing, Joris Mooij, Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniušis, Bastian Steudel, and Bernhard Schölkopf. Information geemmerri approach inferring causal directions. Artificial Intelligence, 182:1-31, 2012.
Nan Rosemary Kc, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf, Michael C Mozer, Chris Pal, and Yoshua Bengio. Neural Causal Structure Discovery from Interventions. TMLR, 2023.
Patrick Kemmeren, Katrin Sameith, Loes AL Van De Pasch, Joris J Benschop, Tineke L, Lenstra, Thanasis Margaritis, Eoghan O'Duibhir, Eva Apweiler, Sake van Wageningen, Chcuk W Ko, et al. Largo-scale genetic perturbations reveal regulatory networks and an abundance of gene-specific repressors. Cell, 157 (3):740 752, 2014.
Daphne Koller, Mehran Sahami, et al. Toward optimal feature selection. In Proceedings of ICML, volume 96, pp. 292, 1996.
Steffen L Lauritzen. Graphical models, volume 17. Clarendon Press, 1996.
Alberto Leon-Garcia Probability and random processes for electrical engineering. Pearson Education India, 1994.
Howard Levene. Robust tests for equality of variances. Contributions to probability and statistics, pp. 278 292, 1960.
Honghao Li, Vincent Cabeli, Nadir Sella, and Hervé Isambert. Constraint-basce causal structure learning with consistent separating sets. Proceedings of NIPS, 32, 2019.
Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclicity constraints. In Proceedings of ICLR, 2022.
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Kranse. Dibs: Differentiable bayesian struc- ture learning. volume 34, pp. 24111-24123, 2021.
Sara Magliacane, Thijs Van Ommen, Tom Claassen, Stephan Bongers, Philip Versteeg, and Joris M Mooij. Domain adaptation by using causal inference to predict invariant conditional distributions. volume 31, 2018.
Dimitris Margaritis and Sebastian Thrun Bayesian network induction via local neighborhoods. Proceedings of NIPS, 12, 1999.
14

---

Published in Transactions on Machine Learning Research (09/2024)
Guillaume G Martinet, Alexander Strzalkowski, and Barbara Engelhardt. Variance minimization in the wasserstein space for invariant causal prediction. In Proceediings of ATSTATS, pp. 8803-8851. PMT.R, 2022.
Nicolai Meinshausen, Alain Hauser, Joris M Mooij, Jonas Peters, Philip Versteeg, and Peter Bühlmann. Methods for causal inference from gene perturbation experiments and validation. Proceedings of the National Academy of Sciences, 113(27):7361 (3667)))361-7368 2016.
Phillip Mogensen, Nikolaj Thams, and Jonas Peters. Invariant ancestry search. In Proceedings of ICML, pp. 15832 15857. PMLR, 2022.
Joris M Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. JMLR, 21(1):3919 4026, 2020.
Minh Nguyen, Batuhan K Karaman, Heejong Kim, Alan Q Wang, Fengbei Liu, and Mert R Sabuncu. Knockout: A simple way to handle missing inputs. arXic preprint (xX.:2445.20444 2024a.
Minh Nguyen, Alan Q. Wang, Heejong Kim, and Mert R. Sabuncu. Adapting to Shifting Correlations with Unlabeled Data Calibration. In ECCV, 2024b.
Minh Nguyen, Alan Q. Wang, Heejong Kim, and Mert R. Sabuneu. Robust Learning via Conditional Prevalence Adjustment. In WACV, 2024c.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge university press, 2009.
Judea Pearl. Theoretical impediments to machine learning with seven sparks from the causal revolution. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 3 3, 2018.
Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. JMLR, 15(1):2009 2053, 2014.
Jonas Peters, Peter Bühhmann, and Nicolai Meinshansen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series (Statistical Methodology), 7854)9947-1012, 2016.
Niklas Pfister, Peter Bühlmann, and Jonas Peters. Invariant causal prediction for sequential data. Journal of the American Statistical Association, 114(527):1264-12766 2019.
Joseph Ramsey, Madelyn Glymour, Ruben Banchez-Romen and Clark Glymour. A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensionall graphical causal models, with application to functional magnetic resonance images. International journal of data science and analytics, 3:121-129, 2017.
Scbastian Raschka. Creating confidence intervals for machine learning classificrs, 2022. URL https://
Alexander G. Reisach, Christof Sciler, and Scbastian Weichwald. Beware of the simulated dag! causal discovery benchmarks may be easy to game, Advances in Neural Information Processing Systems, 34, 2021.
Mateo Carull,, Bernhard Schölkopf, Richard Turner, and Jonas Peters. Invariant models for causal transfer lcarning. JMLR, 19(1):1309-133)) 2018.
Paul Rolland, Volkan Cevher, Matthaus Kleindessner, Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear additive noise models. In ICML, pp. 18741-18753. PMLR, 2022.
Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk minimization.
Tn Proceedings of ICLR, 2021.
15

---

Published in Transactions on Machine Learning Research (09/2024)
Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721):523 529, 2005.
S Shimizu, P Hoyer, A Hyvärinen, Antti Kerminen, and Michael Jordan A linear non-gaussian acyclic model for causal discovery. JMLRR 7(10), 2006.
Ashkan Soleymani, Anant Raj, Stefan Bauer, Bernhard Schölkopf, and Michel Besserve. selection via orthogonal search. TMLR, 2022.
Causal feature
P Spirtes, C Glymour, R Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation- based causal structure learning with unknown intervention targets. In Proceedings of UAI, pp. 1039-1048. PMLR, 2020.
Adarsh Subbaswamy, Peter Schulam, and Suchi Saria. Preventing failures due to dataset shift: Learning predictive models that transport. Proceedings of AISTATS, pp. 3118 3127. PMLR, 2019.
Jin Tian and Judea Pearl. Causal discovery from changes. In Proceedings of UAI, pp. 512-521, 2001.
Joannis Tsamardinos, Constantin Aliferis, and Alexander Statnikov. Time and sample efficient discovery of markov blankets and direct causal relations. In Proceedings of KDD, pp. 673 673-678, 2003.
Ioannis Tsamardinos, Laura E Brown, and Constantin Aliferis. The max-min hill-climbing bayesian
network structure learning algorithm. Machine learning, (5(1):31-75 78, 2006.
Caroline Uhler. Building a two-way street between cell biology and machine learning. Nature Cell Biology, 26(1):13-LL 14, 2024.
Yuhao Wang, Liam Solus, Karren Yang, and Caroline Uhler. Permulation-based causal inference algorithms with interventions. volume 30, 2017.
Shuai Yang, Hao Wang, Kui Yu, Fuyuan Cao, and Xindong Wu. Towards efficient local causal structure learning. IEEE Transactions on Big Data, 86)):1592-1609 2021.
K Zhang and A Hyvärinen. Causality discovery with additive disturbances: An ieformation-thhoreticall perspective. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 570 585, 2009.
K Zhang, Zhikun Wang, Jiji Zhang, and B Schölkopf. On estimation of functional causal models: general results and application to the post-nonl causal model. ACM Transactions on Intelligent Systems and Technology (TIST), (22):1-22, 2015.
Xun Zheng, Bryon Aragam, Pradeop K Ravikumar, and Eric P Xing. Dags with tears: Continuous optimization for structure learning. In Proceedings of NewrIPS, 2018.
16


Reviews:
[{"review_id": "YGoeDmaZbf", "reviewer": "Reviewer_iEGW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Synthetic experiments show, in a variety of settings, that these proposed methods are often more accurate than existing methods for causal detection.\n- Notation of common elements from this work and related work (such as ancestors and descendants) is clear in their definitions. These also are all located in a common section, which helped greatly in parsing statements throughout the paper.\n- Theorems and lemmas proved defend well that, as long as invariance tests are accurate, MMSE-ICP will find the parents of Y. It's a clear and concise theorem that showcases the validity of this method.\n\nWeaknesses:\n- While there are extensive results on simulated settings, there is only a single experiment on real data with expert-knowledge/ground-truth causal graphs. \n- In the theory, there's no elaboration on if the invariance tests fail. What comes to mind is a sample complexity result using existing results for invariance tests to create an overall complexity result for MMSE-ICP.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors extend existing methods for causal detection to using squared error. This retains the exponential time complexity of ICP, but allows for the method to have identifiability which ICP lacks (without additional restrictions). Additionally, the authors provide a heuristic algorithm that accelerates the original algorithm, MMSE-ICP, by using a pruning size to accelerate removing non-blocking nodes. Both methods perform better than ICP on various simulated settings of causal models, alongside a setting with real data. The faster method also performs better than MMSE-ICP when under compute constraints.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Recommendations:\n- I noticed that there was a choice of MaxDepth of 2 in some of the linear settings for fastICP. Is there any reasoning behind this choice? Especially for larger graphs, it seems as though a larger MaxDepth would accelerate fastICP without hindering discovery too greatly. That tradeoff or some mention of anecdotal evidence for why only a MaxDepth of 2 was used would be interesting to have.\n- It would be nice to see these methods tested on other real datasets with well-established causal graphs as well.", "broader_impact_concerns": "No direct ethical implications are present from the work, so no broader impacts are left unaddressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AWw2MiEj0F", "reviewer": "Reviewer_qx4X", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The paper is relatively well written and the method intuitive\n- The application of MMSE to this setting is, as far as I am aware, novel\n- There are performance improvements on real world data\n\n### Weaknesses\n- The MMSE inequality is asymptotic and applies to cases where a) one can obtain the actual best regressor and b) there are enough data to do so. Therefore, given the fact that the authors use finite datasets and model classes, it would be good to extend the theoretical analysis with some form of non-asymptotic results.\n- There are no clear winners in the results and generally there seems to be one other baseline on par with MMSE-ICP/FastICP.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes two improvements upon Invariant Causal Prediction (ICP); minimum mean square ICP and fastICP. The main improvements stem from using a specific inequality that allows for principled filtering of nodes where the invariance tests are applied to. The inequality states that the minimum mean squared error (MMSE) of predicting the target variable $Y$ based on specific covariates $X_1 \\cup X_2$ is lower than when including just $X_1$. This is a consequence of the fact that the minimum mean squared error considers the best possible estimator, the conditional expectation of the target variable conditioned on the inputs. The authors use this inequality to argue for a selection rule over invariant subsets of the non-descendants of $Y$ (and descendants of the environment $E$) that involves two things; a) use the MMSE to select subsets with the smallest MMSE and b) pick the smallest subset out of those remaining as the parents of $Y$. This is the MMSE-ICP procedure which, despite being generally better than ICP in identifying the parents of $Y$, it still scales exponentially in the number of variables. To combat that, the authors propose fastICP, which first filters the set of all variables based on a specific heuristic from prior work, then applies the invariance test when removing variables from the remaining set one-by-one to create final set of candidates. The parents are then the set of variables that achieves the minimum MMSE. The authors test these methods along with baselines on both simulated and real data demonstrating some improvements upon the baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "This work is generally interesting and, as far as I am aware, novel. The results could also be generally useful for the community. For this reason, I am on the positive side. I only have a few minor remarks / questions:\n- The error inequality applies when one can identify the correct estimator and has enough data to do so. It is unclear whether this inequality would still hold with finite data and restricted model classes. While the authors do provide some empirical measurements of the robustness of the results at Appendix D.2, it would be beneficial to discuss how such considerations also affect theoretically the error inequality. \n- Corollary 3.2, I do not exactly follow how the first inequality is an immediate corollary of Lemma 3.1; to me it seems to be a direct consequence of the other two inequalities. Perhaps the authors could expand on that part. \n- The results presented in the main text are a bit lukewarm; MMSE-ICP and fastICP can yield some improvements on the low data regime but across all experimental settings it seems that the improvements are not statistically significant. Also, it would be good if the authors expand on why fastICP seems to generally be better than MMSE-ICP; from the method discussion, it seems that the main motivation for fastICP was speed at the expense of accuracy.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dVfAVudmJ7", "reviewer": "Reviewer_hc2X", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths ###\n1. The paper is clearly written.\n2. There are theoretical results characterizing when the proposed algorithm is guaranteed to find the parents of the target variable.\n3. Experimental results (on both synthetic and real data) indicate that the proposed method is able to find the parents of the target variable more effectively than existing methods in many cases and is competitive in others.\n\n### Weaknesses ###\n1. The theoretical results assume that the tests of invariance are accurate, which is fairly strong. The appendix provides some ablations on synthetic data that show that MMSE-ICP and fastICP are robust to increasing the difficulty of these tests, but adding some theory would make the paper stronger.\n2. The paper argues that fastICP is able to reduce the computational complexity from a theoretical perspective. It would strengthen the work to show some experimental evidence to this effect, e.g. by recording the wall clock time needed by each method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of discovering the parents of a target variable in a structured causal model. It builds on ICP, proposing the minimum mean squared error of prediction as the criterion (MMSE-ICP). Since ICP requires an exponential number of invariance tests, it also proposes fastICP, which employs a heuristic to prune variables to reduce the computational complexity. Theoretical analysis is done showing that MMSE-ICP is guaranteed to find the causal parents if the invariance tests are accurate and that the heuristic in fastICP is reasonable. Empirical results are shown on synthetic datasets (both linear and nonlinear) and gene expression data. MMSE-ICP and fastICP often outperform ICP and IAS in Jaccard similarity, F1 score, and recall, especially for larger datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical: Adding analysis of the computation time to the experimental results.\n\nIt would strengthen the paper to add some theoretical analysis for the case where the tests of invariance may be incorrect, but I understand that this could be difficult.", "broader_impact_concerns": "The authors do not include a broader impact statement. I think this is fine because the paper proposes a general purpose causal discovery method, which only has indirect effects by applying it.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a nice paper that improves invariant causal prediction in multiple ways. While the theoretical results make fairly strong assumptions, the overall work innovative and covers some important limitations of the standard existing techniques. All reviewers found that there is substantial value in the work, and I agree with them.
Decision: Accept (poster)