Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias
Authors: Raanan Yehezkel Rohekar
Shami Nisimov
Yaniv Gurwicz
Gal Novik
Venue: NeurIPS 2021 Poster (2021)
Keywords: Causal Discovery
Causal Structure Learning
Constraint-based Structure Learning
Causal Graph
Ancestral Graph Learning

Abstract: We present a sound and complete algorithm, called iterative causal discovery (ICD), for recovering causal graphs in the presence of latent confounders and selection bias. ICD relies on the causal Markov and faithfulness assumptions and recovers the equivalence class of the underlying causal graph. It starts with a complete graph, and consists of a single iterative stage that gradually refines this graph by identifying conditional independence (CI) between connected nodes. Independence and causal relations entailed after any iteration are correct, rendering ICD anytime. Essentially, we tie the size of the CI conditioning set to its distance on the graph from the tested nodes, and increase this value in the successive iteration. Thus, each iteration refines a graph that was recovered by previous iterations having smaller conditioning sets---a higher statistical power---which contributes to stability. We demonstrate empirically that ICD requires significantly fewer CI tests and learns more accurate causal graphs compared to FCI, FCI+, and RFCI algorithms.

Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias
Raanan Y. Rohekar, Shami Nisimov, Yaniv Gurwicz, Gal Novik
Intel Labs
traanan.yehezkel. shami .nisimov, yaniv.gurwice. gal. cel.novikJeintee..com
Abstract
We present sound and complete algorithm, called iterative causal discovery (ICD), for recovering causal graphs in the presence of latent confounders and selection bias. ICD relies on the causal Markov and faithfulness assumptions and recovers the equivalence class the underlying causal graph. starts with a complete graph, and consists of single iterative stage that gradually refines this graph by identifying conditional independence (CI) between connected nodes. Independence and causal relations entailed after any iteration are correct, rendering ICD anytime. Essentially, we tie the size of the Cl conditioning set to its distance on the graph from the tested nodes, and increase this value in the successive iteration. Thus, each iteration refines a graph that was recovered by previous iterations having smaller conditioning sets-a higher statistical power-which contributes stability, We demonstrate empirically that ICD requires significantly fewer CI tests and learns more accurate causal graphs compared FCI, FCI+, and RFCI algorithms (code is available at /ttttt:://ee wtt.ttt...o..o.eeeeettooottttttt Intelnaae//eeeeeeeeeeeeeerearslt www.llaaabacausllttyyyaaaaa
Introduction
Causality plays an important role in many sciences, such as social sciences, epidemiology. and finance (Pearl 2010; Spirtes 2010). Understanding the underlying mechanisms is crucial for tasks such as explaining a phenomenon, predicting, and decision making, Pearl (2009) provided a machinery for automating the process of answering interventional and (retrospective) counterfactual queries even when only observed data is available, and determining a query cannot be answered given the available data type (identifiability). This requires knowledge about the true underlying causal structure; however, in many real-world situations, this structure is unknown. There a large body of literature recovering causal relations from observed data- causal discovery (Spirtes al.)
2000 Peters et al.) 2017 Cooper & Herskovits] 1992] Chickering |002) [Shimizu et al. [2006] Hoyer al. 2009] Rohekar et al. [2018] Yehezkel & Lerner [2099] Nisimov et al. 2021). differing the assumptions upon which they rely. In this work we assume a directed acyclic graph (DAG) for the assume the causal Markov and faithfulness assumptions, and consider recovering the structure by performing series of conditional independence (CI) tests (Spirtes et al. (000). In this setting the true DAG is statistically indistinguishable from many other DAGs. Moreover, when considering the possible presence of latent confounders and selection bias (no causal sufficiency). the true DAG cannot be recovered. Instead, |Richardson & Spirtes] (2002) proposed the maximal ancestral graph (MAG), which represents independence relations among observed variables, and the partial ancestral graph (PAG), which is a Markov equivalence class of MAGs- set of MAGs that cannot be ruled out given the observed independence relations.
underlying causal structure and focus on learning it from observational data. Furthermore,
Recently, causal identification was demonstrated for PAG models (Jaber et al. 2018 2019). which is more practical use of these models. That is, by using only observed data and prior knowledge on the underlying causal relations, some identification and causal queries can be answered.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this paper, we address the problem of learning PAG such that interrupting the learning process results in correct PAG. That is. all the entailed independence and causal relations are correct, although it can be less informative. This anytime property is important in many real-world settings where it desired to recover as many causal relations as possible under limited compute power.
2 Related Work
Causal discovery the potential presence of latent confounders and selection bias requires placing additional assumptions. In this paper we assume the causal Markov assumption (Pearl 2009). faithfulness (Spirtes et al., 2000,, and DAG structure for the underlying causal relations. In this
setting, several causal discovery algorithms have been proposed, FCI (Spirtes et al. 20000, RFCI (Colombo al. 2012). FCI+ (Classsen et al. 2013). and GFCI (Ogarrio et al. 2016). Limitations of FCI have been reported previously where it tends to erroneously exclude many edges that are in the true underlying graph, and it requires many CI tests with large conditioning sets. The GFCI algorithm employs greedy score-based approach to improve the accuracy for small data sizes (small sample). However, it requires additional assumptions for justifying the score function that uses. The RFCI algorithm alleviates computational complexity by avoiding the last stage of FCI. This stage requires many CI tests having large conditioning sets. Although is sound (outputs correct causal information), it is not complete (some MAGs in the equivalence class can be ruled out given the data).
Similarily the FCI and FCI+ algorithms, the large sample limit (or when perfect conditional independence oracle is used). However, these algorithms, for MAG, treat nodes that are m m-separated by adjacent nodes differently from nodes that are m m-separated by minimal separating set that includes nodes outside the neighborhood. In contrast, we treat all possible separating sets similar manner. We employ an iterative procedure that gradually increases the search radius on the graph for identifying minimal separating sets. This allows our method be interrupted at any iteration, returning a correct graph, similarly to the anytime FCI algorithm (Spirtes 2001).
consider procedure that is sound and complete in
(a)
(c)
(d)
Figure 1: An example for the construction of conditioning sets by the ICD algorithm. (a) The true underlying DAG, where black circles represent latent variables. (b) A PAG resulting after three ICD iterations, {0, 1, 1,2]-0 2- O-equivvllence class. (c) and (d) PDS-trees with r search radii for nodes D and E, respectively, where radial coordinate indicates distance from the root.
3 Anytime Iterative Discovery of Causal Relations
First, we provide definitions and assumptions. Then, we describe the iterative causal discovery (ICD) algorithm and prove its correctness. We conclude by discussing efficiency and stability.
3.1 Preliminaries
causal DAG, 'D, over nodes V = OUSUL is denoted by D(O,S, L), where O, S, and L represent disjoint sets of observed, selection, and latent variables, respectively. We use an ancestral graph (Richardson & Spirtes] 2002) to model the conditional independence relations among the observed variables O in the causal DAG D. This class of graphical models is useful since for every causal DAG there exits a unique MAG. In this setting, our method is aimed at recovering the MAG of the true underlying DAG, from the result of CI tests. A CI test is commonly a statistical hypothesis test used to determine from observed data whether two variables are statistically dependent conditioned on set of some other variables (a conditioning set). If independence is found, the conditioning set is called a separating set for the tested nodes. However, in this setting the MAG cannot be fully recovered, and only a Markov equivalence class, represented by a PAG, can recovered. PAG. variant edge-mark is denoted by an empty circle '-o X'. Namely, in the equivalence class there

---

exists at least one MAG that has a tail edge-mark X' and at least one MAG that has an arrowhead "->X' at the same location.
Definition (O-equivalence (Spirtes et al. 2000)). ) Two DAGs, D,(O, L.) and D,(O,S,. L,)
are said to be O-equivalent if and only if
X L (I S;) in = X YI in D,,
for every possible disjoint subsets X. Y, and Z o.
That is, the observed d-separation relations in two O-equivalent DAGs, Dj and Dj. are identical. Spirtes (200I) defines equivalence considering an n-oracle for testing conditional independence. It returns "dependence" the conditioning set size is larger than n, otherwise sesparation is tested and returned. Thus, n-- 1--O-equivalenee class is defined by using the n-oracle instead of d-separation in The PAG that represents this equivalence class is called n- n-representing (Spirtes) 2001).
Definition !
In MAG, node X is in D- B) (note the capitalization of 'D") if and only if X * A and there an undirected path between A and X such that every node on the path, except the endpoints, is a collider and is an ancestor of A or B (Spirtes et al. (000). The FCI algorithm utilizes super-set of D-Sep, called Possible-D-Sepp A. B) (Spirtes et al. (2000) for testing CI. defined for a skeleton learned by the PC algorithm (Spirtes et al. 2000) and its identified v-structures, referred in this paper as the first stage of FCI. This super-set, used by FCI in its second stage, includes all the nodes connected by a path to A, where every node on this path, except the end-points, is collider or part of a triangle, hiding its orientation. We consider a smaller super-set of D-Sep for PAGs and take special interest in the path that connects any Z
Dessible-D-Sep(A. B) to A.
(PDS-path) from A to Z, with respect to B, in PAG G, denoted e (A, Z), is a path (A..... Z) such that is not on the path and for every sub-path (U, W of B A, 2), V is collider or VU,V.W W) forms triangle.
Definition 2 (PDS-path). A Dossible---eeppon
Note that an edge in a PAG is a PDS-path. Following the definition of PDS-path, we define a tree rooted given node consisting of all PDS-paths from that node.
Definition 3 (PDS-tree). A possible-D-Sepee D-Sp-rrre (PDS-tree) for A, with respect to B given PAG G, is a free moted at A, such that there is path from A to Z, (A, Vi...., Vv, Z), if and only if there is Pat- (A, V.,..., , Vk, Z) with respect to B, in g.
Lastly, considering the last condition of D-Sep definition, we define possible ancestor of node in a given PAG.
Definition 4 (Possible Ancestor). In a PAG, V; is a possible ancestor of Vi+k if there is path (V,, Viti...., Vi+k) such that, Vj E fi,..., i 1}, on the edge (Vj, Vi+1) there is no arrowhead at V, and no tail edge-mark Vj+1.
3.2 Iterative Causal Discovery Algorithm
We present single stage that is called iteratively, for recovering the underlying equivalence class, represented by a PAG, for the true underlying DAG D(O, L). Each itcration is parameterized by r, where E (0..... . O 2}. Given PAG returned by the previous connected nodes A and B is tested for independence conditioned on a set Z C O. independence is found, the connecting edge is removed. The conditioning set Z should comply with the following conditions for (A, B) or (B,A), which we call ICD-Sep conditions. ICD-Sep conditions for the ordered pair (A, B) are,
iteration, each pair of
1. Z =r,
2. ZZ E Z. there exists a PDS- path II, Z) such that,
(a) [A,(A, 2 < and
(b) every node on B (A, Z) is in Z,
3. ZZ Z. node Z a possible ancestor of A B (not necessary condition).
JCC is a causal discovery algorithm assuming causal sufficiency (absence of hidden confounders and selection bias). Conditioning sets consist of nodes only from the neighborhood of the tested nodes.
3

---

the conditioning set size, and condition 2 restricts its distance from the tested nodes. Tying these two conditions together the key idea of the presented ICD algorithm. Condition 3 follows the last condition in the definition of D-Sep. It is not a necessary condition for the correctness of the proposed method but can reduce the number of considered conditioning sets when testing independence. Sets complying with ICD-Sep conditions are denoted ICD-Sep.
Condition[]
that is utilized by the FCI algorithm, ICD-Sep is a smaller super-set of {S| S C D-Sep, |S] = r]. Nevertheless, ICD-Sep and Possible-D-sse may be similar when considering densely connected graphs or when the recoverable equivalence class is large (many variant edge-marks), such as complete graph. However, these cases are usually rare in real-world scenarios.
In comparison to Possible-D-Sye
Next, consider a PDS-tree for A with respect to B in G. Sets complying with ICD-sep conditions can be created by traversing this tree. Condition D restricts the number of nodes to be included in Z to the specific value of r. Condition (aaditioonnlaaat places constraints on the nodes in Z as follows. Condition 2a limits the radius around A in which the nodes of Z reside, effectively limiting the depth of the PDS-tree. Condition 2b ensures that if a node is in Z, then every node on the PDS-path connecting it A is also in Z. An example is given in Figure [ where (a) is the true underlying DAG and (b) is the corresponding PAG that represents a 2-0-equivalence class. A redundant edge between D and E exists. PDS-trees for D and E are depicted in Figure I (c) and (d), respectively. An example for complying with condition 2b when constructing an ICD- --pepp for (D, E)) is as follows. From Figure | (c) if in the set. then B must also be in the set, as it lies on the only path from D to A.
It is important to note that by parameter r. we bind the conditioning set size to its distance from the tested nodes (ICD-Sep conditions [ and 2a). That is, the conditioning set size is bounded by the shortest PDS-path length connecting its nodes to the tested nodes.
In an ICD iteration r, first, all connected edges are tested for independence conditioned on ICD-Sep sets. Then the ICD iteration concludes by orienting the resulting graph. Initially, v-structures are oriented and then FCI-orientation rules (Spirtes et al., 2000 Spirtes] 2001) repeatedly applied until no more edges can be oriented. For completeness, in the last ICD iteration, a complete set of orientation rules is applied (Zhang] 2008).
The ICD algorithm is described in Algorithm T The main loop, lines 2-4, iterates over conditioning set sizes concurrently with the search radius on the graph. The iterative stage is described in function Iteration, lines 68. This function can be viewed as an operator that maps from an (r 1)-0- equivalence class to an r- 7-O-equivalence. Thus, ICD is anytime in the sense that the main loop, lines 2-4, can be terminated for any value of r. resulting in a PAG that entails correct independence and causal relations. That is, terminating the loop after iteration r = results in a PAG that represents an n- ---uuivvleecee class. Nevertheless, it still may not entail all relations that are entailed from the O O-equivalence class of the underlying causal graph.
In the first ICD iteration, the initial PAG is a complete graph and r Thus every pair of nodes is tested for marginal independence (conditioning sets are empty). In the second iteration r= 1, where only nodes that are adjacent to the tested nodes are included in the conditioning set (PDS-path length limit is one edge). Only in succeeding iterations, nodes that are outside the neighborhood of the tested nodes may be included in the conditioning set. Conditioning sets, composed with from adjacent nodes or from outside the neighborhood, are returned by the function PDSepRange.
The result of PDSepRange( X, Y,,, 9). in Algorithm line 9, is an ordered set of possible separating sets {Z.)<=1> where each Z, complies with the ICD-Sep conditions. The specific order in which these sets are used (Algorithm) [ine 12) to test conditional independence in A Algorithm line 13 may affect the total number of CT test in practice. One possible heuristic for ordering this set is such that Z; sets are sorted based on to the average of the shortest PDS-path lengths connecting each node in Z. to the tested nodes. First, for every set Z E {Z:)<= created by PDSepRange, the following value is calculated,
dx (Z) =
Σ Wez
min( W)D:
Z
where [X, (X, W) is the PDS-path from X W, and | is path length. Then, the possible separating sets, Z; are ordered according to this value. Note that the correctness of ICD is invariant to this order.

---

Algorithm 1: Iterative causal discovery (ICD algorithm)
Input:
n: desired n-representing PAG (default: |O|
Ind: a conditional independence oracle
Output:
9: PAG for n- n--Oeeuivvllence class completed PAG is returned for the default n |0| -2)
initialize: r 0, +- a complete graph with 'o' edge-marks, and done +- False
2 while (r S & (dome = False) do (9, done)= Iteration r) refine G using conditioning sets of size r
return g
Function Iteration r):
done True for edge (X,Y) in edges(g) do
if [Z,] <- PDSepRange (X, r, 9) & Z; complies with ICD-Sep conditions
then done t False for i < 1 to l do Ind(X,)) Zz) then
11
12
13
remove edge (X, from
15
record Z, as a separating set for (X, Y)
break
17
orient edges in G return (9, done)
18
3.3 An Example for the Difference between ICD and FCI
In this section we demonstrate the difference between the ICD and FCI recovering a simple graph that was used by Spirtess et al. (2000) demonstrate FCL. In Figure 2 (a) is the true MAG, and (b) its corresponding PAG. Both FCI and ICD start with an unoriented complete graph (absence of independence and causal information). In Figure 2
(c) the result of the first stage of FCI (PC skeleton and v-structures) is shown, and in Figure 2 (d) the result of ICD after iteration r = (CI tests with up one node in the conditioning set).
In both cases, the independence between and not yet recovered, and both ICD and FCI require similar number of CI tests with conditioning set of sizes 0 and 1. However, for concluding its first stage, FCI required additional 11 CI tests having conditioning set sizes (A, B, D, and E, each has 3 neighbors: one indicates tested edge while the other two serve as the conditioning set).
1 with increasing values of and recovers the independence between A and É after only 3 and CI tests with conditioning set size of and 3, respectively (only 4 conditioning sets comply with ICD-Sep conditions). The CI tests, with conditioning set sizes of 2 are Ind(A, (A, B, D), Ind(A. A, B F), Ind(A, A, E.D, H) (no independence is found), and the single CI test having conditioning set size is Ind(A, E D) (independence found). At this point, ICD terminates. The second FCI stage (an iterative stage executed after concluding the first stage), requires an additional total of 76 tests with conditioning set sizes of up to (76 conditioning sets comply with the definition of Possible-D D-eiiblee--eep).. Overall, FCI requires 83 (11 76 4) additional Cl tests compared ICD. Note that for this specific example, ICD requires fewer CI tests than FCT's PC-stage alone.
ICD continues after iteration
5

---

(a)
(b)
Figure 2: An example for comparing ICD with FCI using simple 7-node graph that was used by Spirtes al. (2000) to describe FCI. (a) MAG corresponding the true underlying DAG. (b) A PAG corresponding to the MAG. (c) Skeleton and v-structure orientations that is used by FCI (and FCI+). (d) The PAG resulting after ICD iteration = both cases FCI (c) and ICD (d) is desired to identify the independence between nodes A and E. ICD requires significantly fewer CI tests compared FCI (and PC in this specific case).
3.4 Correctness
We provide sketch for the proof of correctness and completness of the ICD algorithm. The complete proof is in the supplementary material.
Lemma 1. Let G be PAG n-representing DAG D(O,S,L) L). Denote A, B a pair of nodes from O that are connected
and discomnected in and such that not an ancestor of B in D.
If A subset Z O having the same size of n. + such that that A JL B Z U S, and for every node E Z there exists PDS-path 1 (A, 2) in G, such that every node V on the PDS-path is also in Z.
IL
UZ' where C is a minimal separating set having size n + 1, then there exists
In essence. from the definition of D-Sep (Spirtes et al., 2000 page 134 and Theorem 6.2), node Z is in D-Sep(AA A, B) if and only if in the MAG there is a path between A and V such that every node, except for the end points, S(). For every such path in a MAG, there exists PDS-par patthptthh in the corresponding PAG. In an n-representing PAG, we can rule out paths from being such path in the MAG. Thus, for every such path in the MAG, there is a PDS-Path in an n-representing PAG, which ensures identifying least MAG. addition,
collider and an ancestor of A B (an inducing path for
one minimal separating set between ever pair of nodes that are m-separated every sub- sub-path starting at A, of the DDS-path between A and V, is also a PDS PDS-path. This provides link between the distance of the separating set nodes and the number of nodes in the separating set.
Corollary 1.
Let be a PAG n-representinn DAG D(O,S,L). Denote A, a pair of nodes from O that are connected in G and disconnected in 'D.
If A 1. B [Z'] US where Z' C O is minimal separating having size
then there exists
subset Z C. O having the same size of n + such that that A IL B ZUUS and for every node Z E Z there exists PDS-path 11 (A, 2) or [I,(B, 2), where every node V on the PDS PDS-path also in Z.
The proof follows from Lemma] 1
Lemma 2. Let G be a PAG n-representing causal DAG D. Let S be a skeleton (unoriented graph) that results after removing edges from the skeleton of G between every pair of nodes that are m-separated conditioned on a minimal separating set of size + 1.
If S is oriented using anytime-FC orientation rules, then the resulting graph is PAG that (n + 1)- represents the causal DAG 'D
The proof relies on the correctness of the anytime-FCI algorithm (Spirtes 2001 correctness of the orientation in each ICD-iteration.
This ensures the
Proposition 1 (Correctness and completeness of the ICD algorithm). Let G be a PAG representing causal DAG D(O, L,S) and let Ind be conditional independence oracle that returns d-separation relation for O in D. If Algorithm is called with Ind, then the returned PAG, after uninterrupted termination is G.
We prove by mathematical induction. In each induction step we prove using Corollary | that given an r-representing PAG, ICD iteration r + finds conditional independence relations having minimal conditioning set of size + 1, and removes corresponding edges. By Lemma 2 orientation

---

of the resulting graph results in an (r + 1) represssen PAG. Essentially, we prove that a minimal separating set complies with the ICD-Sep conditions, ensuring identification Algorithm Tline
3.5 Efficiency Analysis
We discuss the number of CI test required by ICD with respect to the number of observed variables |O| for learning an n-representing PAG (n-O-equivalence), Namely, the complexity for returning a PAG after n + 1 iterations (recall that ICD is anytime). Let ID* be the class of causal DAGs for which the resulting PAG is also completed For all D(O, L) D". AA, B E O, if EZ C O, such that A IL B J S, then there exists set Z' C O, such that A IL B US and |Z|| S n. That is, its observable d-separation relations have at most n nodes in their minimal separating sets. Nevertheless, for this class of DAGs, ICD may not terminate naturally after n + iterations. ICD terminates naturally after n + 1 iterations (and returns a completed PAG) if in the true underlying PAG, n is the size of the largest set complying with the ICD-Sep conditions. Consequently, is the largest conditioning set size considered by ICD.
The ICD algorithm starts with a complete graph and consists of a single loop, indexed by r. At iteration ICD considers in the worst case (2) edges, and for each edge, up to 2(10)-3) conditioning sets. Thus, the total number of CI tests bounded by Ninxx
N Mmax= = 2 20111
Σ
0
(2)
In practice, the number of CI tests is significantly smaller. Firstly, up to iteration it is ensured that all the edges between nodes that are m-separated, in the true underlying MAG, by conditioning sets of sizes up r are removed. Secondly, the resulting PAG after each iteration is oriented using FCI orientation rules. These two operations reduce the sizes of PDS-treet trees in successive iterations, which leads to fewer ICD-Sep sets to consider as conditioning sets.
3.6 Stability
Constraint-based causal discovery algorithms rely on the accuracy of CI tests. In general, CI tests errors in early stages of an algorithm may lead errors in later stage. For example, erroneously removing an edge in an early stage may lead to erroneously keeping an edge between nodes that are m-separated in the true underlying MAG, which in turn may lead additional errors. Thus, in general it is desired that causal discovery algorithm relies in early stages on statistical tests that have higher statistical power than statistical tests later stages. Commonly, when limited data is available, statistical CI tests suffer from poor estimates of the statistic for large conditioning sets, compared estimates for small conditioning sets. Thus, it is desired to use CI tests having small conditioning sets in early stages of the algorithm.
The FCI algorithm employs the PC algorithm (Spirtes et al. 2000 as an initial stage. The second stage of FCI relies on the accuracy of the resulting skeleton, where subsets of Possible-D-See are created based on this skeleton and used for further independence testing. The PC algorithm iterates over conditioning sets sizes and possibly concludes with CI tests having large conditioning sets. This might render the FCI algorithm unstable given limited database size.
The ICD algorithm benefits from a single iterative loop over conditioning set sizes (in contrast to FCI that has two loops that executed consecutively). This ensures that CI with small conditioning set sizes are tested before CI test having larger conditioning sets. Thus, ICD is expected to more stable than FCI and its related algorithms that have two iterative loops over the conditioning sizes.
4 Experimental Evaluation
We evaluate the performance of ICD in terms of number of required CI tests and accuracy of the learned structures, and compare the performance of FCI (Spirtes et al. 2000), FCI+ (Claassen et al. 2013), and RFCI (Colombo et al. 2012).
A completed PAG represents an equivalence class of MAGs such that no MAG can be ruled out given all CI relations. Not to be confused with complete graph in which every node is connected to every other node.
7

---

8.110
A110
---TC
todal CI tosta by FCI
25 (b)
C1 seata (a)
DAG
Figure 3: Total number of CI tests. (a) A seatter plot using all DAGs in the experiment (ICD requires fewer CI tests than FCI for all the 100 tested DAGs). (b) Average total number of CI tests function of graph size.
10 11212
2903
12500
10000
condrloring on abe
Goaditooing ont eow
aondiooning 2006
(a)
(b)
(d)
Figure 4: Average number of CI tests per conditioning set size for different graph sizes: (a) 15 nodes, (b) 20 nodes, (c) 25 nodes. (d) 35 nodes.
In all the experiments we follow a procedure, similar to the one described by Colombo et al. (2012) for generating random graphs with latent confounders. We create an adjacency matrix A for variables O of DAG D(O, L, S = 0) by independent realization of (ernoulli(// triangle. If the resulting DAG is unconnected, we repeat until connected DAG is sampled. For each DAG, we sample half of the parentless nodes that have least two children and assign them to be the latent set L (making sure there is at least one). The remaining nodes are the observed set O.
the upper
4.1 Number of Required CI Tests when using a Perfect CI Oracle
In the following experiments we evaluate the number of required CI tests by ICD, FCI, FCI+, and RFCI. We also analyze the conditioning set sizes of the required CI tests, since in many functions used for testing CI. the statistical power decreases and the computational complexity grows exponentially with the conditioning
size. For the following experiments in this section, DAGs having n E (15, 20, 25, 35) nodes with a connectivity factor of p 2 (25 DAGs per graph size). The same DAGs used each of the compared algorithms allowing per-DAG comparison. perfect CI oracle is implemented to returns d-separation relations in the true DAG.
sample 100 random
4.1.1 ICD Compared to FCI
In this experiment we compare the ICD algorithm, using only the necessary ICD-Sep conditions (1 2), to the FCI algorithm- both are anytime, sound, and complete. ICD-Sep conditions 1 & 2 serve the key idea ICD for constructing conditioning sets fits--yinn the condition set size to its distance from the tested nodes.
From Figure 3 (a) it is evident that the ICD algorithm requires significantly fewer CI tests compared to FCI for all 100 tested graphs, and that this advantage of ICD is more dominant for graphs that require larger number of CI tests. From Figure (b) we find that the total number of CI tests required by ICD increases significantly more slowly with the graph size, compared to FCI. This difference is also evident difference run-times. We implemented FCI such that it uses the same routines as ICD, executed both algorithms on single core of an Intel Xeon CPU, and measured runtime. The ratio FCI-runtime/ Lat-attimm////-nuttiii rinttmee for graphs with 15, 20, 25, and 35 nodes is 1 1.3, 1.8, 2.9, and 5.6, respectively. As expected, this ratio increases with graph size.

---

5,110
X10
sonal Ci tusts by FCL or FRC
FCs
sotal Ci
0.5
25 (b)
CI seata ICD
(a)
Figure 5: Total number of CI tests. (a) A seatter plot using all DAGs in the experiment (ICD requires fewer CI tests than FCI+ and RFCI for all the 100 tested DAGs). (b) Average total number of CI tests as function of the graph size.
400
1000
1200
+200
POL
-200
0.200
135
20
conditoinggg
conditoning set
condilooing
conditioingse nut
(a)
(b)
(d)
Figure 6: Average number of CI tests per conditioning set size for different graph sizes: (a) 15 nodes, (b) 20 nodes, (c) 25 nodes, (d) 35 nodes.
In Figure for each tested graph size, we depict the average number of required CI tests per conditioning set size. There are three key observations, (1) ICD requires fewer CI tests than FCI for any conditioning set size, (2) the largest difference is evident for conditioning set sizes for which FCI required the most CI tests, and (3) this difference the number of CI tests per conditioning set size increases with the graph size.
4.1.2 ICD Compared to FCI+ and RFCI
In this experiment we compare the ICD algorithm, using all ICD-Sep conditions, to the FCI+ and RFCI algorithms, which are improved versions of FCI, reducing the required number of CI tests. Both FCI+ and RFCI are sound. FCI+ is also complete. whereas RFCI is aimed at reducing the number of CI tests (compared to FCI) at the cost of not being complete. We were aided by the R package pcalg (Kalisch al. 2012) for evaluating these algorithms.
In Figure 5 (a) is demonstrated that ICD requires fewer CI tests than both FCI+ and RFC On average, evident from Figure 5 (b) the number of CI tests required by FCI+ and RFCI increases similarly with graph size, whereas this number for ICD grows significantly more slowly.
Lastly, we analyze the number of CI tests per conditioning set size, per graph size. Our observation from Figure is threefold: (1) ICD requires fewer CI tests than FCI+ and RFCI for any conditioning set size, (2) the largest difference between ICD and FCI+/RFCI is evident for conditioning set sizes for which FCI+/RFCI, and (3) this difference increases with graph size, whereas the difference between FCI+ and RFCI becomes smaller relatively to the difference between them and ICD.
4.2 Structural Accuracy
In the following experiment we evaluate the accuracy of learned structures and the required number of statistical CI tests. To this end, we sample 100 DAGs, each having 15 nodes and an expected neighborhood 2, and quantify each edge of the DAGs by sampling from Uniform([-O.5-- -2.0] [0.5, 2.0]). probabilistic model created by treating each node value as normally distributed with standard deviation 1, and mean being a weighted sum of the patents' values. From this model, for
We found RFCI to require slightly fewer CI tests than FCI+ for all tested DAGs.

---

---ICD
-0-CC - RICI -
1C1 -P-ICH
RFCI
-+-CD
Alekens E1 50ore
0.29
0.20
0.31
2200
0.6
0.29
1300
0.55
0.24
200
0.5
0,19
2000
1000
1990
2004
1000
number of data rocords
number of data reconds
number data reconds
(a)
(b)
(c)
Figure 7: Average (a) number of CI tests, (b) accuracy of skeleton, and (c) accuracy of oriented edges, as function of dataset size for the FCI, FCI+, RFCI, and ICD algorithms.
each of the 100 DAGs, we sample 5 data sets having sizes [100, 200, 500, 1000, 3000]. For each of the 500 data sets learn graphical models using FCI, FCI+, RFCI, and ICD.
We measure the accuracy of the skeleton by calculating false-positive ratio (FPR), false-negative ratio (FNR) and F1-score. Correctly identifying the presence of an edge is considered que-positive. We measure the accuracy of edge orientation by calculating the percentage of correctly oriented edge-marks. Finally, also count the number of CI tests required by each algorithm per data set. The average values (over 100 graphs) of the number of CI tests, skeleton F1 score, and orientation accuracy summarized in Figure 7
From the experiments, other methods, ICD has higher skeleton FPR (extra-edges), but lower skeleton FNR (missing edges, identified independence relation). Overall, ICD has the highest Fl score. Lastly, is evident that ICD has an advantage in orientation accuracy over the other methods.
evident that ICD requires significantly fewer tests. Compared to the
Conclusions
We presented ICD, an anytime, sound, and complete causal discovery algorithm for learning PAGs representing n---equivalence classes. The ICD algorithm is simple procedure that consists of single loop over conditioning set sizes of CI tests. Having single loop ensures that CI tests with small conditioning sets tested before CI tests having larger conditioning sizes. This can lead to greater stability in practical cases.
The ICD algorithm gradually increases the search radius, from local neighborhood to the entire graph, for separating sets around connected nodes, resulting in an efficient search procedure. In early iterations, where the graph is dense and small number of edges oriented, the search for separating set is localized. In later iterations, where the graph sparser and more edges are oriented, global search for separating set becomes more efficient.
An important difference of the proposed ICD algorithm from FCI and related algorithms is that, right from the outset it considers nodes for the conditioning set that are not in the local neighborhood of the tested nodes. One might suspect that this could result in high number of CI tests evaluated by the ICD algorithm compared to the FCI algorithm. However when proceeding from one iteration to the next, the ICD algorithm reduces the number nodes to consider for the conditioning sets by complete orientation in each iteration, and by limiting the distance of the conditioning nodes from the tested nodes.
Finally, from the experimental results, the ICD algorithm requires significantly fewer CI tests compared to FCI, and its related efficient algorithms FCI+ and RFCI, especially for large conditioning sets. Moreover, it is evident that the advantage of ICD increases with the graph size. In addition, ICD learns more accurate causal graphs. We believe that these advantages can be appealing to many real-world applications in domains such as economics, health, and social sciences.
10

---

References
Chickering, M. Optimal structure identification with greedy search. Journal of machine learning research, 30N0v):007-554, 2002.
Claassen, T., Mooij, J. M., and Heskes, T. Learning sparse causal models is not NP-hard. In Uncertainty in Artificial Intelligence pp. 172. Citeseer, 2013.
Colombo, D., Maathuis, M. H., Kalisch, M., and Richardson, S. Learning nigh-dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pp. 294 321, 2012.
Cooper, F. and Herskovits, E. Bayesian method for the induction of probabilistic networks from data. Machine learning, 94))3099334,, 1992.
Hoyer, P. O., Janzing, D., Mooij, J. M., Peters, J., and Schölkopf, B. Nonlinear causal discovery with additive noise models. In Advances in neural information processing systems, pp. 689-696, 2009.
Jaber, A., Zhang, J., and Bareinboim, E. Causal identification under markov equivalence. In 34th Conference on Uncertainty in Artificial Intelligence, pp. 978-987. Association for Uncertainty in Artificial Intelligence (AUAI), 2018.
Jaber, A., Zhang. J., and Bareinboim, E. Causal identification under markov equivalence: Complete- ness results. In International Conference on Machine Learning, pp. 2981-2989 2019.
Kalisch, M., Mächher, M., Colombo, D., Maathuis, M. H., and Bühlmann. P. Causal inference using graphical models with the R package pcalg. Journal of Statistical Software, 47(11):1-266 2012. URL https://www.sstttssofr
org/ wttaaaaceeevieeee////1....
Nisimov, S., Gurwicz, Y., Rohekar, R. Y., and Novik, G. Improving efficiency and accuracy causal discovery using hierarchical wrapper. In Uncertuinty in Artificial Intelligence (UAI 2021), the 4th Workshop on Tractable Probabilistic Modeling, 2021.
Ogarrio, M., Spirtes, P., and Ramsey, hybrid causal search algorithm for latent variable models. In Conference on Probabilistic Graphical Models, pp. 368-379, 2016.
Pearl, J. Causality: Models, Reasoning, and Inference. Cambridge university press, second edition, 2009.
Pearl, An introduction causal inference. The international journal of biostatistics, 6(2), 2010.
Peters, J., Janzing, D., and Schölkopf, B. Elements of causal inference. The MIT Press, 2017.
Richardson, T. and Spirtes, P. Ancestral graph markov models. The Annals of Statistics, 30(4): 962-1030, 2002.
Rohekar, R. Y., Gurwicz, Y., Nisimov, S., Koren, G., and Novik, G. Bayesian structure learning by recursive bootstrap. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Shimizu, S., Hoyer, P. O., Hyvärinen, A., and Kerminen, A. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, ((0cc):2033-203:) 2006.
Spirtes, An anytime algorithm for causal inference. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 278 778-285, 2001.
Spirtes, P. Introduction to causal inference. Journal of Machine Learning Research, 11(May): 1643-1662, 2010.
Spirtes, P., Glymour, C., and Scheines, Causation, Prediction and Search. MIT Press, 2nd edition, 2000.
Yehezkel, R. and Lerner, B. Bayesian network structure learning by recursive autonomy identification. Journal of Machine Learning Research (JMLR), 10(hu):1527-1570. 2009.
Zhang, J. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17)1883--1887) 2008

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 3.2 third paragraph.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See supplementary material.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See preliminar- ies defined in Section 3.1 Also, the second sentence of the abstract.
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [Yes] A detailed description for generating the data is given in the preamble in Section 2nd and 3rd paragraphs. The code is planned to be released later on.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [N/A] All the data points are provided in scatter plots; see Figure (a) and Figure (a).
(d) Did you include the total amount compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes]] In Section 4.1.1 (runtime measurement).
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Section 1.2 first paragraph citing the package used in that specific experiment.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "rpITkNSFg8o", "reviewer": "Reviewer_v9pH", "summary": "The paper proposes a method for causal discovery in graphs with potential latent common causes, which compared to other similar methods requires significantly less conditional independence tests and smaller conditioning sets. It achieves that by incrementally increasing the size of the conditioning set relative to the distance from the tested nodes. This approach bases the incrementally learnt graph on statistical tests with minimum size of conditioning set, therefore theoretically boosting its statistical strength and stability. Without additional assumptions the method is able to detect PAGs. ", "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": "The authors provide theoretical proofs of their method and experimental comparisons with FCI and its variants. Nevertheless, the authors report results only in terms of numbers of CI tests and size of conditioning set, rather than false positive and false negative rates. As a result I cannot judge how well their algorithm performs in terms of discovery of the graph. From the theory point of view, their algorithm is both efficient and stable, as it is built on CI tests with small conditioning sets. This is also exhibited in the experiments. \n\nIf the authors provide performance - related experiments (FPR, FNR) in comparison with the FCI methods, in order to see whether the algorithm works in practice I am willing to increase my grade.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation of the paper, in my opinion, is that it does not provide any experimental results (neither on simulated nor on real data) about the false positive and false negatives of the method. I would request the authors to do so, comparing the accuracy of their incremental method with the existing methods, with respect to FPR, FNR.\n\nOther points:\n- Proposition 1 is not well written. The G that the algorithm will return depends on the 'n' number of iterations.\n-Line 61: Do you mean returning every time a correct *subgraph* instead of graph? It cannot be that at any step of the iteration the algorithm returns the correct graph since it has not examined all the nodes.\n-Line 73: A CI test is commonly a statistical hypothesis test used to determine from observed data whether two variables are correlated conditioned on a set of some other variables. -> Not just correlated. Whether they are dependent in general (not just linear dependency).\n-Could you elaborate on the statement on line 126?\n-The authors do not provide any paragraph for the Broader Impact of their paper.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concern.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "YVmsX3ja3J7", "reviewer": "Reviewer_WByU", "summary": "The authors describe an algorithm for learning causal relations in the presence of latents and selection bias. The algorithm called ICD recovers the partial ancestral graph (PAG) corresponding to \"some\" equivalence class of the maximal ancestral graph of the underlying DAG. Most prior work for this problem studied the problem of recovering PAG using FCI variants. \n\nIn this work, the authors outline a greedy neighborhood search-based algorithm (ICD) that can be stopped after \"r\" iterations, and the PAG recovered by ICD corresponds to an \"r-equivalence class\". By definition, an \"r-equivalence class\" encodes all causal relations that can be recovered using conditional independence tests that use at most \"r\" observable nodes. Therefore, the guarantees of this paper are weaker than the recovery guarantees of FCI which return the PAG of the equivalence class. Note that FCI uses conditioning sets that can be of size as large as the size of the total observable nodes.\n\nFCI is an anytime algorithm and can be stopped after \"r\" iterations and outputs an \"r-equivalence class\". In the first stage of FCI, the PC algorithm returns a set of nodes S and a partial graph. Then, FCI checks subsets of S in the order of increasing size for conditional independencies. Finally, the orientation rules that are sound and complete are applied. In this paper, the authors suggest a way of bypassing this step-wise procedure, directly generating subsets of increasing size and checking for conditional independencies. Finally, they suggest using the orientation rules of FCI (when asked to terminate after \"r\"th iteration). Although there is no theoretical improvement in the number of conditional independence tests used, the authors empirically demonstrate that their approach is better than FCI in the number of conditional independence tests used.", "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": "\nThe problem that the authors' study is an important problem, and in general the authors take an interesting approach to solve it. I find that the algorithm is a natural idea of greedily growing the neighborhoods using the existing paths, and ensuring that the separating sets are identified correctly (ICD-Sep conditions in the paper). Although the algorithm is not entirely novel, the soundness and completeness of the algorithm make it a good contribution. \n\nI would request the authors to clarify a few things:\n\n1. How \"far away\" is the n-equivalence from the total equivalence, i.e., |O|-equivalence? I am not fully convinced why the notion of this specific equivalence class is useful. \n\n2. Lemma 1 -- why does there exist a PDS path Pi(A, Z) for every Z? I understand if one exists, your proof follows.\n\n3. In general, it would be interesting to understand if there is an actual improvement in the conditional independence tests (theoretically), even for certain graph families.\n\n4. (Lines 285-288) What is the actual time it took in the implementation of your algorithms?\n\n5. Figure 4 on Page 8? How are you able to change the conditioning set size of FCI -- isn't it determined by the PC algorithm in the first stage?\n\nOther comments:\n\n-- Please state the problem of \"anytime learning of causal graphs\" formally in the preliminaries or introduction.\n\n-- (Line 80) Defn 1. For \"every possible\" X, Y, Z.. \n\n-- (Line 95) What is a subpath?\n\n-- Line 17 of Algorithm 1. Orient edges \"using ...\" specify the rules/idea fully.\n\n-- Try relating the computational complexity based on the diameter of the graphs. The constant diameter or low diameter graphs are known to capture many graph families.\n\n-- Please add a reference to the paper \"Learning Causal Graphs with Small Interventions\", and differentiate the notion of separating sets from this to yours.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15-20"}, "extra_text": {}}, {"review_id": "Nq5ctehfARJ", "reviewer": "Reviewer_79JW", "summary": "This paper presents a variant of the FCI algorithm for causal discovery in the presence of latent confounding and selection bias. The proposed algorithm is claimed to be anytime, sound and complete, and is shown to typically require significantly fewer conditional independence tests than other variants of FCI. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The idea of this paper is interesting and promising. If the claims are true, the contribution is in my view fairly significant, as FCI remains an important algorithm to tackle causal discovery when latent confounding and selection bias cannot be assumed away and the large number of conditional independence tests needed in FCI is a major concern. However, I am not yet convinced of the claims of the paper. My main concerns are the following:\n\n1. I do not follow the proof of Lemma 1. First of all, the statement of the lemma is not clear, as the quantifier in front of \"Z\\in \\mathbf{Z}\" is not specified. Given the definition of ICD -Sep on p. 3, I gather that a universal quantifier is intended here. If so, I suspect the lemma, as stated, is false. For example, suppose the graph is A --> X <-- Y --> B and X --> Z --> W --> B. Now A and B are d-separated by {Y, Z}, which is a minimal separating set. But Z does not satisfy the condition stated in the lemma. In this case, there is a minimal separating set, i.e., {Y, X}, which satisfies the condition in question, so I guess the intended lemma here should be IF A and B are d-separated by a set with size n+1, THEN there exists a separating set of that size that satisfies the condition. In any case, the proof does not manage to establish that, as far as I can see. \n\n2. The proof of Proposition 1 cites Spirtes's (2001) proof that FCI-orientation rules are still applicable even if the skeleton contains extra edges. However, this paper claims to also apply Zhang's (2008) orientation rules, and it is not clear that the rules considered by Spirtes are sufficient to cover all the rules in the latter.\n\n3. It is also not entirely clear what a PAG n-representing the underlying DAG needs to be. Spirtes's (2001) definition of a PAG does not require orientation completeness, but this paper seems to require that, as indicated on p. 2. What it means for a PAG n-representing the underlying DAG to be complete should be clearly defined, and that such a PAG would be returned by the algorithm when it is interrupted after the n'th round needs to be more carefully demonstrated. \n   \n\nMinor comments:\n\n1. The definition of \"possible ancestor\" (Definition 4) is a little confusing. Does it require only the first edge on the path to satisfy the said condition? \n\n2. On p. 4, it is claimed that ICD-Sep is a (smaller) super-set of D-Sep. This is confusing on two counts. First, ICD-Sep is said to be \n\"sets complying with ICD-Sep conditions\", which seems to suggest that it is a set of sets of nodes, whereas D-Sep is a set of nodes. Second, ICD-Sep has a parameter r, whereas D-Sep does not, at least as it is defined in the paper. \n\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "5dcRXFQihig", "reviewer": "Reviewer_RqyE", "summary": "The authors propose an algorithm for constraint-based causal discovery in the presence of latent confounders and selection bias. \nIt is similar to FCI while it can have better efficiency than FCI in practice with fewer conditional independence tests. The paper also included sufficient analysis of the algorithm and the experimental results support the claims.", "questions": "", "limitations": "", "rating": 7, "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": "The algorithm contributes to the constraint-based methods in the presence of latent confounders and selections bias from the efficiency perspective. Based on the experimental results, efficiency analysis, and stability analysis, the algorithm can work as the author claimed. The experiments are properly done and the comparison with FCI is clear. So the contribution is sound and it can be an alternative to FCI in many cases. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As for limitations, yes; As for social impact, it showed in the checklist that \"N/A\" in 1(c) of the checklist. Maybe some general concern of causal discovery algorithms, such as the impact of potential errors because of wrongly using the methods?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are favorable after the author responses.

Clearly, this is a fairly significant contribution. Reducing the number of CI tests within the FCI family of algorithms (handling both selection bias AND confounders) is very important. I am impressed by the significant reduction in number of CI tests and significant improvement in orientation accuracy (which is non trivial) empirically. Further the anytime guarantees and associated theoretical results make it a solid paper. The authors even clarified key technical concerns after which reviewers felt more positive.

 Please do add experimental results quoted in the review response about FPR/FNR vs other FCI based algorithms and please do make changes as recommended by reviewers regarding rephrasing of Lemma 1.


Decision: Accept (Poster)