Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a recursive structure learning algorithm when there are latent confounders and selection bias. They focus in on a subclass of graphs with a key property that there always is a vertex such that after its removal, the dependency structure of the remaining graph does not change. 

The second key fact they utilize is that understanding if a node can be removed without changing the m-separation relations in the rest of the graph only requires the neighborhood information. This can be (somewhat efficiently) learned by first finding the Markov boundary of the node and then finding the separable nodes within the Markov boundary, which only requires testing subsets of the Markov boundary. 

I did enjoy reading the paper overall and I believe it provides a good contribution. 
main_review: One issue that needs to be addressed is that the authors make an assumption about the graph structure to ensure this property is satisfied throughout. However, this assumption becomes apparent only in the appendix (proof of Thm. 2 and Lemma 10). I believe this assumption and node-removability from the MAG has to be the centerpiece of the discussion. I don't believe this is a very restrictive assumption, especially if there are no selection nodes, it should always hold (there is no partially directed cycle in a MAG by construction), however, the discussion should be there in the main paper.  

Another issue is that Proposition 3 or (6), which gives the number of CI tests RCD uses excludes the initial phase of Markov boundary discovery. Please add this quadratic term to be precise. The discussion after Proposition 3 is useful. 

The lower bound is useful but a discussion on this bound being over all graphs would be useful. An instance-wise bound will look very different from this. 

Some comments on why p(V\{x}) is used instead of p(V\{x}|x) would be nice to have. 

line 129: authors do not make the distinction between Ancestors and Anteriors of a node. This is because they only operate on a DAG rather than another ancestral graph. It might be worth making a footnote about this. 

line 133: seems like the wrong reference as [26] doesn't include selection variables. Authors should refer to Richardson & Spirtes 2002 pg. 20. 

I was initially a bit concerned that there is no explicit mention of the selection variables S in the proofs in Appendix A. I believe it's not needed since authors operate on a MAG level. 

Lemma 6: Is G assumed to be a MAG?

Remark 1 of appendix, which is an assumption about the underlying graph, should be in the main text. 

On Theorem 1: Suppose Z<->X-Y. Then Mb(X)={Y,Z}. Y is not ind of Z hence C1 fails. Similarly, Y is indep of Z given X then C2 fails. I believe this cannot be a MAG or a part of a MAG but examples like these would be very helpful to convey that there will always be a removable node, which is the crux of the approach. 

theses variables-> these variables

line 760: FindAdjcent->FindAdjacent

Post-rebuttal: I would like to thank the authors for engaging in the discussion. The paper demonstrates a surprising fact about learning causal graphs - that a recursive approach taking out one node at a time is possible. I will keep my original score of "accept".
limitations_and_societal_impact: No. Limitations should be discussed. Only MB accuracy is mentioned as future work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study the problem of learning a causal maximal ancestral graph (MAG) from observational data in the presence of latent variables and selection variables. They introduce a sound and complete recursive constraint-based algorithm (RLCD) with which they learn the causal structure efficiently. The algorithm uses Markov boundary information in order to reduce the number of required conditional independence (CI) tests. They introduce the notion of *removable* variables, which are variables that can be removed without changing the CI statements in the induced subgraph, and prove a graphical criterion for finding these variables from CI information. At each iteration of the algorithm, the *removable* variable with the smallest Markov boundary is removed, while the Markov boundaries and list of adjacencies are updated. The authors prove that this approach exhibits an upper bound on the number of CI tests that differs from a provable general lower bound only by (at most) a factor equal to the number of variables. The authors showcase the performance of their algorithm in a series of experiments on simulated data and benchmark Bayesian network structures. 
main_review: *Originality*: The authors have come up with a very promising approach for learning the causal MAG from observational data by means of a sound and complete recursive algorithm through which the number of CI tests that have to performed is greatly reduced. While the idea of using *removable* variables has been previously employed for DAGs in reference [9] from the main paper, the extensions and proofs that the authors have introduced with this paper are, to the best of my knowledge, novel and greatly expand the applicability of the method by allowing for the presence of latent variables and selection bias.

*Quality*: The submission appears to be technically sound. I have partially checked the proofs in the supplement and the logic seems to hold water. The claims are well supported and the proofs are in general detailed enough.

A significant issue I have with the paper is that the proof of Theorem 1 excludes a very restricted set of MAGs, namely MAGs that contain non-chordal undirected cycles of length at least four. While I agree with the authors that this is a very restrictive structure and will not significantly influence the applicability of the algorithm, I do not find it completely above board that this caveat is only mentioned in the supplement. I think that the final version of the main paper should necessarily include this disclaimer, even if just as a footnote. 

Another gripe I have is the definition for an $m$-connecting path, which I do not think is entirely accurate. The $m$-connecting part is fine, as under the conditions specified, $X$ and $Y$ will be $m$-connected. However, this connection may be due to a different path when the colliders are ancestors of the endpoints, namely a path that goes through the directed path from endpoint to collider.

*Clarity*: The paper is well structured and very well written, virtually error-free.

*Significance*: The results obtained are impressive and carry great significance. While constraint-best methods include some of the most tractable algorithms for causal discovery, they often run into trouble, particularly on dense graphs, when the number of conditional tests that have to be performed becomes exponential in the worst case, while the size of the conditioning tests performed becomes very large. This approach promises to tackle both of these issues to an important degree.

To further showcase the significance of the results, I would have also liked to see a comparison for sparse and dense graphs. Dense graphs are generally much more problematic for constraint-based causal inference than sparse graphs (see e.g., reference [2] from the paper), which is why I would have been really interested in looking at the benefit of the present work for the two cases separately. On that note, it would have been nice to include the FCI+ algorithm from the same reference [2] in the experiments, since it was specifically design to have a polynomial computational complexity on sparse graphs.  

*Minor comments*: 
-	Line 74: Formatting error – “Proposition 5” should be “Proposition 3”
-	Lines 201 and 206: I think $X$ should be $X_1$ everywhere.
-	Figure 2, rightmost column: y-axis label should be “Avg. Cond. Set Size”


limitations_and_societal_impact: The authors have not addressed a technical limitation of their algorithm in the main paper, which involves excluding a specific restricted set of MAGs from the proof of Theorem 1, namely MAGs that contain non-chordal undirected cycles of length at least four. The authors have discussed this limitation adequately, however, in the supplement to the paper (see Remark 1 and Appendix D). Nevertheless, in the spirit of transparency, I think that this limitation should also be clearly mentioned in the main paper, even if just in footnote form.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on causal discovery especially focusing on the casual structure learning in the presence of latent variables and selection bias. \
A recursive constraint-based method is proposed for learning causal structure. The Markov boundary information and 'removable' variable are introduced to reduce the CI tests.
main_review: The paper considers an important problem of learning causal graphs in the presence of latent variables and selection bias.  \
The paper builds on constraint-based methods, such as FCI and RFCI.\
The paper provides a theoretical study of the connection between Markov boundary and separating set, which is closely related to the proposed algorithm. \
The analysis and the algorithm are sound and presented in a logical way.
 
 
However, there are some concerns or suggestions:
1. What's the reason for restricting the variables follow the structural equations model (Line 146)? It is not clear to me whether your method needs this assumption.  Please clarify it.

2. It's not clear to me whether the removable variables always exist in the subgraph?  It would be good to add some examples to explain the removable variable after definition 4 or Theorem 1.
3. In the experiments (Benchmark Structures Part), could you explain why the Precision of the RFCI is almost one while RLCD is not?

The algorithm's performance is a cause for concern, especially when the Markov boundary information can not discover correctly. 
This is because the algorithm highly relies on the Markov boundary.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents a method to learn a Maximal Ancestral Graph (MAG), a mixed graph, an extension of DAGs, capable of representing a system with selection bias and hidden variables. The method is constraint-based (based on conditional independence tests) and recursive. The main innovation is the introduction of the concept of a “removable” variable, a variable that can be removed from the current graph such that the subgraph corresponding to the marginal distribution of the remaining variables can be learned correctly. The problem of learning the whole graph is then decomposed by always identifying the next removable variable and then recursively learning the graph for the remaining variables.
main_review: PROS:
- Very clear presentation. Also the math seems impeccable, although I only glanced through the lengthy proofs in the Appendix.
- Good motivation and intuition, and in general the problem is relevant to the community.
- Novel idea, which improves computational efficiency (because the removable variable has small Markov boundary resulting in a small number of CI tests in each iteration) and accuracy (because the order of the graph decreases over iterations and hence the size of the conditioning set in the CI tests is reduced).
- Theoretical analysis of the number of CI tests needed by the method and also a novel proof for the lower bound of the number of tests needed by any algorithm.
- Experiments with several synthetic and real graphs that thoroughly demonstrate that the method outperforms alternatives in terms of accuracy and/or runtime.

CONS:
- Actually, I did not identify any major limitations in this article (not with the first reading at least).

QUESTIONS:
- Could you clarify if there always is a removable variable when the size of V is greater than 1?
- Very minor: the output and input of the “isRemovable” function on line 8 in Algo1 are not the same or in the same order as in Algo2.
 

limitations_and_societal_impact: Sufficiently yes, although the limitations are a bit narrowly discussed (just one sentence in Conclusion).
review_title: null

Meta-review: This paper proposes a recursive structure learning algorithm for Maximal Ancestral Graph (MG) when there are latent variables and selection bias. The proposed algorithm is built on a novel notion of ``removal variable'' which many reviewers find interesting and reasonable. The theoretical analysis of computational efficiency and effectiveness was properly evaluated through experiments. All reviewers found the paper useful for the ML community. The authors are encouraged to consider updating the paper based on the reviewers' comments and suggestions.
Decision: Accept (Poster)