Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents sound and complete orientation rules to incorporate local causal background knowledge to PAGs and applies these rules to active learning. Here, the local causal background knowledge regarding a variable $X$ refers to the causal relations about X with any adjacent variable. Note that, this paper assumes no selection bias. 
strengths_and_weaknesses: This paper is clearly written and the contributions are novel. The authors prove sound and complete orientation rules to orient a PAG with local background knowledge. Although I did not check the proof, the sketch seems reasonable. I only have one suggestion: it would be better to explain the steps to construct the PAGs in the example presented in Figure 1 in more detail.
questions: I also only have some questions for the authors
1. The authors assume the local BK is correct, meaning that the orientation rules can only be applied when the local BK is correct. When the local BK is not correct, will applying the orientation rules cause some mistakes (such as cycles or new colliders), or we can still get a PAG?
2. Regarding the MH sampling, it seems that Proposition 2 only gives a method to construct an equivalent MAG from a given one. Can any two Markov equivalent DAGs be transformed into each other in a limited number of these transformations? Is it possible that a sample MAG from $S({\cal M}_{t-1})$ is not consistent with the given BK (line 3, Algorithm 2)? What is the computational complexity of Algorithm 2?

limitations: Not applicable.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Nonparametric causal discovery can identify the true DAG up to some undertainty. The uncertainty can be eliminated only by incorporating background knowledge (BK). Under causal sufficiency assumption, Meek rules established a complete rule to orient the CPDAG to DAG with BK. While in the presence of latent variables, authors provide the first sound and complete rules to orient the PAG. The orientation rules are based on local form of BK. With these rules, authos propose an active learning framework, aiming to orient a given PAG with the minimum number of interventions (BKs). Since it is hard to count the number of MAGs in some consistent space, authors further equipped the method with the adaptive rejection Metropolis-Hastings sampling. Experimental results demonstrate the effectiveness of the proposed framework.
strengths_and_weaknesses: + Pros:
  - **Clarity.** The paper is generally well-written and organized. The problem definition is set clear, the preliminaries are described in a detailed and clean way, and theoretical analyses are also well carried out.
  - **Technical quality of the proposed rules.** The proposed orientation rules are technically dense. I haven't read the rules (section 3) in detail, and could not ensure the correctness. But I tried on some simple graphs example, and the rules appear to be correctly identifiable to me.

+ Cons: Overall this is good to me. Currently I could not give any specific weaknesses of this paper, but only some questions. See the questions section.
questions: 1. **local BK**: now BK is defined as _all marks_ on a variable X - which seems expensive - and usually BK is given as some specific direct edges. Could the authors please give more motivation on why this BK is defined over some node, instead of edge? If some BK is given in the edge form, could it also be incorporated into this framework?
2. **Latent**: by _with latent variables_, is it assumed that all latent variables are exogenous (or mutually independent), similar as assumptions in FCI, so that the Markov equivalence class can be represented as a PAG. And thus, in experiments, L348 "take three nodes as latent variables and the others as observed ones" - are they taken randomly or with some criteria?
3. **Correctness of BK**: L134: "The correctness indicates that there exists an MAG consistent to P and the BK." So the authors also assume that the learned P at the first stage is correct. What if P is incorrect (which is often the case), and the given BK has confict with P - is there any correction rule to prevent cascading error?
4. **About originality**: the active learning framework (maximal entropy criterion, rejection metropolis sampling etc, section 4) seems to be a classic paradigm in combinational search. Is this originally proposed by authors, or very similar to some existed methods on orientation rules?
5. **Accuracy difference in Table 1**: why there is accuracy difference between MCMC and random? Since the orientation rules are deterministic, given the same PAG, the maximum oriented graph should be exactly the same, with only the difference in the number of interventions required. Where does the accuracy difference come from? What if the starting PAG is exactly the true PAG (asymptotic result, not by FCI)?
6. L86: letters (V, E) should be bold face.
limitations: The problem setup is quite clear, and the authors have adequately addressed the limitations. I only have some questions above, regarding assumptions on latent, and assumptions on correct P and BK.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: For a given PAG, the paper presents a sound and complete procedure to incorporate local background knowledge (BK). For a given node X, the local BK the paper considers is knowledge of the edge marks at X, i.e., the circle marks at X in the given PAG are converted to an arrowhead or a tail using the BK. Then the procedure orients further edges/nodes in the PAG. For a given set of nodes with BK, the procedure sequentially incorporates the BK for each node one at a time.
Next, the paper presents an algorithm to decide which nodes to intervene on (interventions are essentially equivalent the BK) with the goal of learning the MAG with a small number of interventions.


strengths_and_weaknesses: Originality, quality, and significance:
The primary contribution of the work is to propose two new orientation rules that allow for sound and complete incorporation of BK for a given node V_i (in Alg. 1). I think the work is significant as it proposes a way to further narrow down the MEC beyond what can be learned using only observational data. And incorporating this specific kind of BK is also novel (although I think more comparison is needed to related literature --- please see my remarks in the "Questions" section).

Clarity:
Overall, I think the paper is hard to read. I would have appreciated some more examples to illustrate how the algorithm work. It would have been nice if the proof sketches were explained with concrete examples of why the two new rules are sound and complete (especially for Thm. 2).


questions: Comparison to learning PAGs with interventional data:
There is some work on incorporating interventional data into PAGs. As an example, see [1], which provides a characterization as well as a learning algorithm for causal discovery under unknown interventions (with known interventions being a special case). This algorithm is also sound and complete. BK is not necessarily the same as soft interventions (which can reveal more information). But to me, they seem very closely related as interventions are one way of obtaining BK, so it seems to me that algorithms that are sound and complete in incorporating interventions can also be leveraged for BK. Can the authors comment on how their work is related to this line of work?

Line 156:
What do you mean by "algorithm can be achieved"? What does it mean for an algorithm to be achieved?


[1]  Jaber, A., Kocaoglu, M., Shanmugam, K., & Bareinboim, E. (2020). Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in neural information processing systems, 33, 9551-9561.
limitations: I have addressed this in the previous sections.
review_title: null

Meta-review: metareview: This paper presents sound and complete orientation rules to incorporate local causal background knowledge along with algorithms implementing these rules. Reviewers were universally appreciative of the contributions and in favor of acceptance.
confidence: Certain
Decision: Accept