Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

In 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.

FCI 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.
main_review: 
The 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. 

I would request the authors to clarify a few things:

1. 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. 

2. Lemma 1 -- why does there exist a PDS path Pi(A, Z) for every Z? I understand if one exists, your proof follows.

3. 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.

4. (Lines 285-288) What is the actual time it took in the implementation of your algorithms?

5. 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?

Other comments:

-- Please state the problem of "anytime learning of causal graphs" formally in the preliminaries or introduction.

-- (Line 80) Defn 1. For "every possible" X, Y, Z.. 

-- (Line 95) What is a subpath?

-- Line 17 of Algorithm 1. Orient edges "using ..." specify the rules/idea fully.

-- 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.

-- Please add a reference to the paper "Learning Causal Graphs with Small Interventions", and differentiate the notion of separating sets from this to yours.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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:

1. 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. 

2. 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.

3. 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. 
   

Minor comments:

1. 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? 

2. 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 
"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. 

 
limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose an algorithm for constraint-based causal discovery in the presence of latent confounders and selection bias. 
It 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.
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. 
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

If 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.
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.

Other points:
- Proposition 1 is not well written. The G that the algorithm will return depends on the 'n' number of iterations.
-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.
-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).
-Could you elaborate on the statement on line 126?
-The authors do not provide any paragraph for the Broader Impact of their paper.
review_title: null

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)