Sound and Complete Causal Identification with Latent Variables Given Local Background Knowledge
Authors: Tian-Zuo Wang
Tian Qin
Zhi-Hua Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: background knowledge
partial ancestral graph

Abstract: Great efforts have been devoted to causal discovery from observational data, and it is well known that introducing some background knowledge attained from experiments or human expertise can be very helpful. However, it remains unknown that \emph{what causal relations are identifiable given background knowledge in the presence of latent confounders}. In this paper, we solve the problem with sound and complete orientation rules when the background knowledge is given in a \emph{local} form. Furthermore, based on the solution to the problem, this paper proposes a general active learning framework for causal discovery in the presence of latent confounders, with its effectiveness and efficiency validated by experiments.

Sound and Complete Causal Identification with Latent Variables Given Local Background Knowledge
Tian-Zuo Wang, Tian Qin, Zhi-Hua Zhou National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China. {wangtz, qint, zhouzh]@lamm .jju. edu.
Abstract
Great efforts have been devoted to causal discovery from observational data, and it is well known that introducing some background knowledge attained from experiments human expertise can be very helpful. However, it remains unknown that what causal relations are identifiable given background knowledge in the presence of latent confounders. In this paper, we solve the problem with sound and complete orientation rules when the background knowledge is given in a local form. Furthermore, based on the solution to the problem, this paper proposes general active learning framework for causal discovery in the presence of latent confounders, with its effectiveness and efficiency validated by experiments.
Introduction
Causality has attracted tremendous attention in recent years, for its application explainability [1], fairness [2. 3, 4], decision [5, 6, 7, 8, 9]. and so on. In Pearl's causality framework [10]. one important problem is causal discovery, i.e., learning a causal graph denote the causal relations among all the variables [11, 12, 13, 14, 15, 16). Generally, we cannot identify all the causal relations from observational data, unless we make some additional functional assumptions [17, 18, 19] or exploit the abundant information in multiple or dynamic environments [20, 21].
In light of the uncertainty of the causal relations, common practice to reveal them is introducing background knowledge, which is called BK for short. BK can be attained from experiments or human available,
expertise. When experiments
collect interventional data learn additional causal relations [22, 23, 24, 25, 26, 27, 28, 29, 30, 31]. And if in the causal discovery task, there are some variables familiar to humans, is also possible that the human expertise can be helpful [32]. For example, if we study the causal relations among some variables including sales and prices, the causal relations such as price causes sales can be obtained directly according human expertise.
When BK is available in addition to observational data, fundamental problem is: what causal relations are identifiable in the presence of latent variables? This problem is fundamental for its implication on the maximally identifiable causal knowledge with the observational data and BK. Its difficulty results from the fact that, in addition to the BK itself, some other causal relations can also be learned when incorporating BK. For example, they can be identified on the basis of some restrictions, such the causal relations acyclic. It is quite challenging to find the complete characterization for such additional causal knowledge in the presence of latent variables, and the complete characterization is necessarily accompanied with theoretical guarantee for the existence of causal graphs consistent to the observational data and local BK that have exactly different causal relations for the unidentifiable ones. Unfortunately, the problem remains open.
In this paper, we solve the problem with sound and complete orientation rules when the background knowledge is given in local form. In the presence of latent variables, partial ancestral graph (PAG)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

can be learned by FCI algorithm from observational data [33, 34, 35]. PAG can imply the existence of causal relation between any two variables but not necessarily imply the causal direction. We say BK is local, if when the BK contains the causal information with respect to variable X, for each variable adjacent to X in the PAG, the BK implies whether X causes it or not. The local BK is common in real tasks no matter it is from experiments or human expertise. For example, when we make experiments and collect the data under intervention on X, for each variable V that has a causal relation with X, the interventional data can tell whether X causes V; and businessman often has enough domain knowledge about price, thus they usually know whether price causes other variables or not, such price causes sales and number of customers, and price is not caused by stocks. Given a PAG and local BK, we propose a set of orientation rules to determine some causal directions in the PAG. We prove that the rules are sound and complete, which state that all the causal relations that are identifiable given available information are exactly those determined by the proposed rules, thus closing the problem given local BK.
The establishment of orientation ventions possible in the presence of latent variables. We propose the first general active learning framework for causal discovery, with the target of identifying a maximal ancestral graph (MAG), which implies the causal relations when there are latent variables. Considering that intervention is expensive in reality, we hope to achieve the target with as few interventions as possible. Hence we present a baseline maximal entropy criterion, equipped with Metropolis- the intervention variable such that we can learn more causal relations by each intervention. Our contributions in this paper are twofold:
rules compatible with local BK makes causal discovery by inter-
sampling, to select
We show what causal relations are identifialle given local background knowledge in the presence of latent confounders with sound and complete orientation rules.
(2) We give the first active learning framework for causal discovery that is applicable when latent variables exist, where maximal entropy criterion equipped with Netropolis-Hasttnng sampling is introduced to select intervention variables.
Related works. In the literature, Meek [36] established sound and complete rules, generally called Meek rules, for causal identification given BK under the causal sufficiency assumption. The as- sumption requires that there are no latent variables that cause more than one observed variable simultancously. However, causal sufficiency untestable in practice. When we apply causality in subjects such as biology, sociology, and economics, it is quite often that there are latent variables. For example, the macroeconomic policy influences purchase price, the population of customers, and advertising cost, but it is hard to evaluate it, thereby a latent confounder. Andrews et al. [37] showed that FCI algorithm is complete given tiered BK, where all variables are partitioned into disjoint sets with explicit causal order. While in many cases, e.g., when BK is revealed by interventions, BK is not tiered. And Jaber et al. [28] investigated the complete algorithm to learn a graph when there are additional interventional distribution, while such knowledge is not needed in our paper.
2 Preliminary
graph G (V, E) consists of a set of vertices V -Vi...., .Vz) and set of edges E. For any subset V C V, the subgraph induced by V' is Gy: = Ev.), where Ev. is the set of edges in E whose both endpoints are in V'. For a graph G. V(G) denotes the set of vertices in G. G is a complete graph if there is an edge between any two vertices. The subgraph induced by an empty set is also a complete graph. GI- V'] denotes the subgraph Gvay: induced by V.V' Usually, bold letter (e.g., V) denotes set of vertices and normal letter (e.g., V) denotes a vertex. A graph is chordal if any cycle of length four or more has a chord, which is an edge joining two vertices that are not consecutive in the cycle. If G = (V, E) is chordal, the subgraph of G induced by V C V is chordal.
A graph G is mixed if the edges in G are either directed + or bi-directed ++, The two ends of an edge are called marks and have two types arrowhead or tail. A graph is partial mixed graph (PMG) if it contains directed edges, bi-directed edges, and edges with circles (o). The circle implies that the mark here could be either arrowhead or tail but is indefinite. V; is adjacent to V, in G if there an edge between Vú and V,. A path a graph G is a sequence of distinct vertices (Vo...., Vn) such that for ( S S n 1, V. and Vi+1 are adjacent in G. An edge in the form of Vi o-o Vy is a circle edge. The circle component in G is the subgraph consisting of all the o-o edges in G. Denote the set of vertices adjacent to V, in G by Adj(V,, G). A vertex V, is
2

---

parent of vertex V, if there is V, + VG. A directed path from V. to V, is path comprised of directed edges pointing to the direction of V A possible directed path from V; to V is a path without an arrowhead at the mark near V; on every edge in the path. V, is an ancestor/possible ancestor of Vi if there is a directed path/possible directed path from V; to V or V, = =v. V, is a descendant/possible descendant of V, if there is a directed path/possible directed path from V; to V, pnccetootdexccendnnttosss
or Vi = Vi. Denote the set of parentaaccssorlpossinnn V; in G by Pa(V,, G)/Anc(VV C)/,ossAnVV G), De,,, G). If V; E Anc(V,, G) and V + Vi/V, + V,, it forms a directed cycle/almost directed cycle. * is a wildcard that denotes any of the marks (arrowhead, tail, and circle). We make a convention that when an edge is in the form of o-+, the+ here cannot be a tail since in this case the circle can be replaced by an arrowhead due to the assumption of no selection bias.
descendant of
non-endpoint vertex V; is collider on a path if the path contains +-+ V2 <+. A path p from V; to V, is collider path if V; and V, are adjacent or all the passing vertices are colliders on p. is minimal path if there are no edges between any two non-consecutive vertices. path p from V2 to Vj is a minimal collider path if p is collider path and there is not proper subset V of the vertices in p such that there is a collider path from V; to V3 comprised of V A triple (V,, Vj, V&s) on a path is unshielded if Vi and V22 are not adjacent. p is uncovered path if every consecutive triple on p is unshielded. A path is a minimal possible directed path if p is minimal and possible directed.
A mixed graph is an ancestral graph if there is no directed or almost directed cycle (since we assume no selection bias, we do not consider undirected edges in this paper). An ancestral graph a maximal ancestral graph ( (MAG, denoted by M) if it is maximal, ie., for any two non-adjacent vertices, there a set of vertices that m-separates them [33]. A path p between X and Y in an ancestral graph G is an inducing path if every non-endpoint vertex on is a collider and meanwhile an ancestor of either X or Y. An ancestral graph is maximal if and only if there is no inducing path between any two non-adjacent vertices [33].
In an MAG, a path p- (X,.... W, W,V,Y) is a discriminating path for V if (1) X and Y are not adjacent, and (2) every vertex between X and V on the path is collider on p and a parent of Y. Two MAGs are Markov equivalent if they share the same m- seppeaattins.. A class comprised of all Markov equivalent MAGs is a Markov equivalence class (MEC). We use partial ancestral graph (PAG, denoted by P) to denote an MEC, where a tail/arrowhead occurs if the corresponding mark is tail/arrowhead for all Markov equivalent MAGs, and a circle occurs otherwise.
For PMG M. that is obtained from PAG P by orienting some circles either arrowheads tails, an MAG M is consistent to the PMG MI if (1) the non-circle marks in MI are also in M, and (2) M in the MEC represented by P. Sometimes we will omit the PAG P and just directly say a PMG M (obtained from the PAG P) since in this paper we study the rules to incorporate local BK to PAG. We say an MAG M is consistent to the BK if M is with the orientations dictated by the BK.
3 Sound and Complete Rules
In this section, we present the sound and complete orientation rules to orient a PAG P with local background knowledge (BK), where P is learned by observational data [11, 35] and V(P) (V1, V2.-.., , Va). The local BK regarding X means that the BK directly implies and only directly implies all the true marks at X, denoted by BK (X). We assume the absence of selection bias and that the BK is correct. The correctness indicates that there exists an MAG consistent P and the BK. Without loss of generality, we suppose the local BK is regarding V1, V/2, ....... Ve. 1 < k < d. That is, for any vertex X E Ví, V2, .... VE. all the marks at X are known according to the local BK; and for any vertex X E VA-1, Va, the local BK does not directly imply any marks at X.
First, we show the orientation rules incorporate local BK. They follow the rules of Zhang [35] for learning a PAG but with one replacement and one addition. Due to the page limit, we do not list them here but the replaced and additional ones. See Appendix A for the rules proposed by Zhang [35].
RdJ: If (K, ... ; A, B, R)) is a discriminating path between K and R for B, and B o R, then orient B a-* as B- + R.
R11: If A + B, then A + B.
3

---

Algorithm 1: Update a PMG with local background knowledge
Input: PMG M.,, (X)
Output: Updated graph M,+1
For any K E (XssDe(X, Mc[-C]] and any T' E C such that K a- T' in M,, orient K <+T (the
mark at T remains); for all K E PossDe X, M, [M|[-C] CJ) such that X o- K, orient X + K; follows until no feasible updates: for any two vertices Vi and V such that V/2 a-o V,, orient it as Vi + V if () Fv, \v, * 0 or (ii) Fv, = Fv; as well as there is vertex Vn E PossDe X, M, [X) not adjacent to V2 such that V. + Vi 0-o Vy;
Orient the subgraph M. PoossDe M CI)
3 Apply the orientation rules until the graph is closed under the orientation rules.
Prop. 1 implies the soundness of R4 to orient a PAG P or a PMG obtained from P with local BK. See Appendix A for the proof. R11 is immediate due to no selection bias assumption. In the following. we make a convention that when we say the orientation rules, they refer to R1 R3, Rs- R1o of Zhang [35] and R4 R11- A PMG is closed under the orientation rules if the PMG cannot be oriented further by the orientation rules.
Proposition 1. Given PAG P, for any PMG M. that is obtained from P by orienting some circles in P (or M- = P), R4 is sound to orient M with local buckground knowledge.
Proof sketch: If there is B + R in an MAG consistent with the case of R4. there must be a minimal collider path between K and R across B. in which case B R should have been identified in the PAG according to Zhao et al. [38], Zhang [35], contradiction.
Next, we will prove the completeness of the proposed orientation rules. It is somewhat complicated. We first give roadmap for the proof process. There are mainly two parts. The first is that we present a complete algorithm to orient P with the local BK regarding Ví, V2,,.. Vic. The second part is to prove that the algorithm orient the same marks as the proposed orientation rules. Combining these two parts, we conclude the orientation rules are complete to orient a PAG. The construction of the algorithm and the corresponding proof for the completeness of the algorithm in the first step is the most difficult part. To achieve the construction, we divide the whole process of orienting a PAG with BK regarding V/, V2.... V&& into k steps. Beginning from the PAG P (P is also denoted by Mo), in the (i + 1)-th (0 <i < k 1) step we obtain PMG M,+1 from M, by incorporating (V+++)) and orienting some other circles further. To obtain the updated graph in each step, we propose an algorithm orienting a PMG with local BK incorporated in this step. Repeat this process by incorporating (V1),, (V2)). VV...... BK (V&) sequentially, we obtain the PMG with incorporated BK regarding V1, ... Vr. We will prove that the k-step algorithm to orient PAG with local BK regarding Vi,..., ...,,,,. V2 is complete, by an induction step that if the first i-step algorithm is complete to update the PAG P with BK regarding Vi,... Vi, then the (i + 1)-step algorithm is complete to update P with BK regarding V..... V++1- Hence the proof in the first part completes. In the second part, we show that the k-step algorithm orients the same marks the proposed orientation rules. We thus conclude that the orientation rules are sound and complete for causal identification in the presence of latent variables given local BK.
We present Alg. to obtain M4++1 from M, by incorporating BK )) For brevity, we denote V by X, and introduce set of vertices C defined as C = (V E V(P) V+, X E (K(X) to denote the vertices whose edges with X will be oriented to ones with arrowheads at X according to BK(X) directly. In M.+ there is X ++V V for V E C and X + for V E (V V(P) V X in M.NCC oriented directly according to (X). We define FM. (V E (X)
in M.) for which is denoted by Fv, for short. Fv, denotes the vertices in
any V2 E PossDe(X,, CJ) CU (X) whose edges with Vi are oriented to ones with arrowheads at V in the first step of Alg. 1.
In the first step of Alg. 1, the orientation at X follows (X and the orientation at the vertices apart of X is motivated as the necessary condition for the ancestral property. Speaking roughly, there is an oriented edge K - T in the case of the first step, then no matter how we orient the other circles, there will directed or almost directed cycle, unless we introduce new unshielded colliders (which takes new conditional independences relative to those in P), both of which are evidently

---

2c
V
V
(a) PMG M;
(b) After Step 1
(c) After Step 2
(d) After Step 3
An example to demonstrate the implementation of each step of Alg. 1. Fig. 1(a) depicts a PMG M., Suppose the local BK is in the form of V1 2 V1 VV,,, V1 +v The Fig. 1(b)/I()/((() displays the graph obtained after the first/second/third step of Alg. 1. The edges oriented by each step are denoted by red dashed lines.
Figure 1:
invalid to obtain an MAG in the MEC represented by P. And the orientation in the second step is motivated as the necessary condition for that there are no new unshielded colliders in the oriented graph relative to the PAG P.. If there is an MAG where there is an inconsistent edge with the edge oriented in this step, then there must new unshielded colliders relative to P. which implies that the MAG is not consistent to P. The third step orients some other circles based on the updated structure.
Example 1. See the example in Fig. I. Suppose the input PMG M. in Alg. / is the graph shown in Fig. I(a). And there is local BK regarding X V1, which is in the form of V1 <+ V1 ~Vs, V1 V4- PossDe( V1, (M[[12] = {V1, Vs, Va, V-}- And Fv:- = [V2), Fv, {Vi]. Fv,. {Vi, V2). When we implement Alg. 1, in the first step, the edges denoted by red dashed lines in Fig. I(b) are oriented. Among them, Vi 0-0 V2/V o- V//V o- V4 transformed Vi VVV//V - V//Vi + V4 due V1 = X, 1/2 E C, V4, V/S E (V E V(P) V* X in Mi C; and V20+ V//V20~> V3 is oriented due to V/2 E C and V3, V/S E PossDe(X, ,ossDe(X,M,(-C) In the second step of Alg. 1, the edge denoted by red dashed line in Fig. I(c) is oriented due to (1)
Hence C {V23. In this case, PossDe( XX M, M
circle edge V/3 c-o Vs after the first step, where V3, Vs PossDe(X, M,[-C]); (2) Fv, [V2] C
(V1. = Fv.. In the third step of Alg. 1, the edges denoted by red dashed lines in Fig. l(d) is oriented by R1 of the orientation rules.
Then, we present the key induction result in Thm. 1 for the graph obtained by Alg. I in each step. Due to the page limit, we only show a proof sketch, with a detailed version in Appendix B. Then with Thm. 1, we directly conclude that k-step algorithm is complete to orient the PAG with the local BK regarding Vi...., V& in Cor.
Theorem 1. Given i, suppose M,, Vs E 10.1....,, satisfies the five following properties:
(Closed) M. is closed under the orientation rules.
(Invariant) The arrowheads and tails in Ml, are invariant in all the MAGs consistent P and BK regarding Vy,...,V.
(Chordal) The circle component in M, is chordal.
(Balanced) For any three vertices A, B, C in Ms,, if A+ B C. then there an edge between A and C with an arrowhead at C, namely, A+ C. Furthermore, the edge between A and B is A B, then the edge between A and C is either A + C or Ao C (i.e., it is not A ++ C).
(Complete) For each circle at vertex A on any edge Ao* B in Ml,, there exist MAGs M1 and M2 consistent P and BK regarding Vi...., V. with A B+BB E(M1) and A - B E E(M2).
Then the PMG M,+1 obtained from M, with (K(())1) by Alg. I also satisfies the five properties.
Proof sketch: For brevity, we denote Vi+1 by X. (A) The closed property holds due the third step of Alg. I.(B) The invariant property holds because all the orientations in Alg. 1 either follow BK(X) or are motivated as the necessary condition for the ancestral property and the fact that there cannot be new unshielded colliders introduced relative to M,, (C) The chordal property is proved based on the fact that only the first two steps of Alg. possibly introduce new arrowheads, while the third step will only transform the edges as Ao- B to A + B, which is proved in Lemma 12 in Appendix B. With this fact, it suffices to prove that the circle component in the graph obtained after the first two steps chordal. Denote the graph after the first two steps by M,+1. We can prove that the circle components
5

---

F in M,+1 (PossDe(X, M [I) and in there are no circle edges connecting PossDe(XX, M, |-C) and V PossDDe.X, C- (otherwise has been oriented in the first step of Alg. 1), we conclude the desired result. (D) The balanced property of M1+1 is proved based on three facts that (1) in Alg. 1, if we transform a circle to arrowhead at V. then V E PossDe(X in M, then E PossDe X, C[):
M, [-C]] are chordal, respectively. Since
(-]: (2) if there is A E PossDDe X, [-C- and A o-+ B, B & C, (3) MI, satisfies the balanced property. We can prove that it is impossible that there is a sub-structure + V1, a- V&2 where V, is not adjacent to V/2 or there is Vi #- V& in M4++ by discussing whether V,, V2, V& belongs to PossDe(X, (X, M.|-C)) (E) The completeness property is proved by showing two results: (1) for edge circle edge A o-o B and Co- D in M, Co- D can be transformed to C + D and the circle edge can be oriented as both A and A 4- B in the MAGs consistent to P and local BK regarding Vi..... V4+1; (2) in M,+1. each edge Ao B can be oriented as + B in an MAG consistent to P and local BK regarding Vi, V In this part, the most difficult part is to prove the first result, with which the second result can be proved directly following the proof process of Thm. 3 of Zhang [35]. In the proof for the first result, we show that any MAG obtained from 1 by transforming the edges as Ao-> B to A + B and the circle component into a DAG without new unshielded colliders is consistent to P and local BK regarding Vi...., V1+1- 1- If not, we can always find an MAG obtained from Mi, by transforming the edges as Ac B to A - B and the circle component into a DAG without new unshielded colliders that is not consistent to P and local BK regarding V12 ...... V,. By induction, there is an MAG obtained from P by transforming the edges as Ao B to A + B and the circle component into DAG without new unshielded colliders that is not consistent to P. contradiction with Thm. 2 of Zhang [35]. We conclude the first result.
M Corollary 1. The k-step algorithm from My(= P)) to M, is sound and complete. That is, the non-cirele marks in Mg are invariant in all the MAGs consistent to P and BK regarding Vi...., Vi- And for each circle in M,. there exist both MAGs with an arrowhead and MAGs with a tail here that are consistent to P and BK regarding Vi,...,VV= Vi.
Proof. Previous studies [34, 35] show that the last four properties in Thm. are fulfilled in PAG, the case in R2 will never happen in P because such circles have been oriented by R4 in the process of learning P. and the case in R 11 is never triggered by the rules to learn P. Hence P satisfies the five properties. With the induction step implied by Thm 1, we directly conclude that M2 satisfies the five properties, thereby satisfying the invariant and complete property.
Theorem 2. The orientation rules are sound and complete to orient a PAG with the local background knowledge regarding Vi...., Vs.
Proof. The soundness of R4 is shown by Prop. 1. The soundness of other rules immediately follows Thm. 4.1 of Ali et al. [34] and Thm. 1 of Zhang [35]. We do not show the details. Roughly speaking, the violation of these rules will lead to that there are new unshielded colliders or directed almost directed cycles in the oriented graph relative to P. The main part is to prove the completeness.
According to Cor. I, it suffices to prove that in each step by Alg. to incorporate BK (X) into PMG M,, the orientations in Alg. either follow BK(X) directly, or can be achieved by the proposed orientation rules. The orientation in the second step of Alg. can be achieved by R2, because no matter Fv, /v, * 0 or Vn + Vi o-o Vj. there is F E Fv, or F= Vm respectively such that F Vi a-o Vj where F is not adjacent to V,. The orientation in the third step naturally follows the orientation rules. For the orientation in the first step, X ++V for V E C is dictated by B (X), and X- V for V E (V E V(P) X o-* VJ is obtained from X =VV dictated by (K( and R11- The remaining part is to prove for K E PossDee X, M and E C, if there is K o- T in M4, K <+1 can be oriented by the proposed orientation rules when we incorporate BK (X).
Due to K E PossDe(X, M, | CI) there is a possible directed path from X to K that does not go through C. According to Lemma 2 in Appendix B, there is a minimal possible directed path p= (X Fo). F1, Fi..... K(= K(=F))), 2 1 where each vertex does not belong to C. Hence X + F, is oriented by (K(X) and R1 unless X + F1 has been in M,, Hence, X - F -
can be oriented by R, after incorporating (X unless they have been in M,. If = 1, there is T X K, thus K T can be oriented by R2. Next, we consider the case when / 2.
We first prove that for any Fm E Fi...., F,, 1. 2 2, Fm adjacent to T, and there is not Fm -> T in M. Suppose Fm is not adjacent to T, there must be sub-structure of M, induced by

---

(a) PAG P(=Ma)
(b) M
(c) Mla
Figure 2: Fig. 2(a) depicts a PAG P. with the local BK regarding V1 in the form of V12 <+ 2 V12 + *V,, V1 -i+1/1 and the local BK regarding 1/2 in the form of V/2 < V/2 ~VV3, V22 +VV3. The connected circle components are denoted by shaded area. The edges oriented by the orientation rules are denoted by red dashed lines.
Fm-s: Fm Fmm-+11--- F & m, m, m, such that T is only adjacent to Fm-s and
Fn+t in this sub-structure. There are at least four vertices in this sub-structure. Hence there must be an unshielded collider (denoted by UC for short) in this sub-structure in P. otherwise no matter how we orient the circle there is either new UC relative P or a directed or almost directed cycle there. Since p is possibly directed, the UC is at either Fm+i or T (i.e., ++ Fm+z( ( or T) <+). If there is a UC Fn T+ Fi+t and F f Fm+1 are identified in P. Thus F Fm+1 - Fm+++1 1........................
F, is identified in P. Due to the completeness of FCI algorithm to learn P, there is K T+T in P, because there is not an MAG with K + T' (there has been T' Fm+ .... K in P). Hence there is K ++I in M,, contradicting with K c-+ T in Ml, If there is not UC at Fm++, UC can only be at T, Thus F T <+ F F+ 1 identified in P. Since p is possibly directed, Fm+i-1 not adjacent to T, and there is not a UC at Fm+H in the sub-structure, there cannot be Fm+# < T in P. Hence the path (Fm-s Fm- s+1......... Fm+11 T) in P is an uncovered possible directed path, Fm-. + T is identified in P (otherwise Rg applies). When incorporating (X),, there is (almost) directed cycle T + >.... > Fm-s + T. contradicting with the correctness BK. Hence, F,, is adjacent to T. Similarly, if Fm. T in M, there is T X - Pm + T, impossibility.
Finally, since Fi is adjacent to T. and T= X + Fi is oriented according BK(X), there is T* Fi oriented by R2 unless T - Fi has been in M,, Hence there is always T>- F1 by the orientation rules. Consider T* Fi + F2, there is T* F22 oriented by R₂ unless T F22 has been in M, Repeat the process for F3, Fa,... Fi(= K), we can prove that if there is Ft K) o+ T in M,, there is T+ F((= K) oriented by R2. The rules thus orient the same marks as Alg. 1. O
Example 2.
We give example in Fig. 2. Suppose
obtain a PAG Fig. 2(a) with observational
data and have the local BK regarding V1, Vz. We divide the whole process of obtaining a PMG from P with the local BK into obtaining MI, from P with B (K(V)) ) by Alg. I and then obtaining M1, from Mr, with BK (V2) ) by Alg. 1. Mi, and M2 are shown in Fig. 2(b) and 2(c), respectively. It is not hard verify that all of PP M,, Ml satisfy the closed, chordal, and balanced properties defined in Thm J. Note if we do not consider R4, the edge colored red in Fig. 2(b) cannot be oriented. Fig. 2(a) also shows a case where BK(V, is not tiered [37]. The reason that the vertices V1, V4, Vs cannot partitioned into disjoint subsets with explicit causal order because Vi and Va belong to different subsets according BK (V)) but V3 has ancestor relation with neither V1 nor Va.
4 Active Causal Discovery Framework
The establishment of the orientation rules for causal identification with local BK makes causal discovery by interventions possible in the presence of latent variables. Hence, on the basis of the theoretical results, we propose an active learning framework for causal discovery in the presence of latent variables, with the target of learning the MAG with as fewer interventions as possible. The framework is comprised of three stages. In Stage 1, we learn PAG with observational data. In Stage we select a singleton variable X Vi,..., Va to intervene and collect the interventional data. In Stage 3, we learn causal relations with the data. For each edge X ao V,, the circle at X can be learned by a two-sample test on whether the interventional distribution of Vú equals to the observational one. There is X <+VV learned if they are equal, and X <V;; otherwise. Hence, the knowledge taken by the
7

---

Algorithm 2: Intervention variable selection based on maximum entropy criterion with MH alg.
Input: A PMG M. oriented based on P and BK regarding Vi,-.. Vi, numher of MAGs T.
Output: The selected intervention variable
Obtain an MAG Mo based on M, by transforming c- to + and the circle component into a DAG without new unshielded colliders;
for f 2........
do
Sample an MAG M' from S(M-11):
p= p= min(1,
[S(MP] [S(M,_111)
Sample from uniform distribution 00, 1};
if then
then M, M' else M. M
[MrLs M has the non-circle marks in M.} The of MAGs consistent to M,; 8 8 + x 0;
for V V.41.....W Va do V(M) VG a V in M,). L (S];
10
Denote =(V))=(V
For each possible local structure La of Vj. 1 I & VVV() count the number No. of the appearance of L* in the L MAGs from S:
-2 22 No log No. L if s S s' then X + Vj, S s';
12
s' = --
-- k==
13
14 return X.
interventional data is local. We repeat the second and third stages until we identify the MAG. Since the orientation rules complete, the graph can be updated completely by each intervention. The only remaining problem how to select the intervention variable Stage
Considering that the whole process is sequential, we only focus on the intervention variable selection in one round. Without loss of generality, suppose we have obtained PMG MI, by interventions on V1, V.,... V,, and will select variable from [V++1..... V2} to intervene. We adopt the maximum entropy criterion [22]. For M., we select the variable X that maximizes
M
Hx =
Σ j=1
log
(1)
L
where j is index for a local structure of X (a local structure of X denotes definite orientation of the marks at X). M denotes the number different local structures, Iy denotes the number of MAGs consistent to M, which has the j-th local structure of X, and L denotes the total number of MAGs consistent to M,. Intuitively, the maximum entropy criterion is devoted to selecting the intervention variable X such that there is similar number of MAGs with each local structure of X and more as possible local structures of X. justification for intervening on such variable is that we hope to have a small space of MAGs after the intervention matter what the true local structure of X is.
However, is hard to count the number of MAGs consistent to M, with each definite local structure. Even in causal sufficiency setting. implementing such operation (generally called counting maximally oriented partial DAGs) #P-complete [39]. Considering DAG is a special case for MAG, counting of MAGs is harder. Hence, we adopt sampling method based on Metropolis-Hasting (MH) algorithm [40], to uniformly sample from the space of MAGs. The algorithm begins from an MAG consistent to MI, and in each round transform the MAG to candidate MAG and decide to accept or reject with some probability. Here, we introduce an important result of Zhang and Spirtes [41] for MAGs transformation in Prop. 2.
Proposition 2 (Zhang and Spirtes [41], Tian [42]). Let M be an arbitrary MAG, and A + B an arbitrary directed edge in M. Let M' be the graph identical to M except that the edge between A and is A + B. M' is an MAG Markov equivalent to M if and only if
(1) there is no directed path from A to B other than A + B in M;
(2) for any C + A in M, C is also in M; for any D ++ in M, either D + or
D e B is in M:
(3) there is no discriminating path for A on which B is the endpoint adjacent to A in M.
8

---

In the MAG sampling algorithm, in each step we transform the current MAG to new MAG by converting a directed edge to bi-directed edge or bi-directed one to directed one, where we use Prop. 2 to determine whether an MAG Markov equivalent to the current MAG can be obtained by the conversion. For MH algorithm, a stationary distribution equal to the desired distribution can be obtained if any two states can be transformed to each other in limited steps [43]. As implied by Theorem 3 of Zhang and Spirtes [41], any MAG can be transformed to another Markov equivalent MAG in limited number of transformations above. Hence, MH algorithm is valid to sample MAGs uniformly from the space of MAGs consistent to P. Then, we only remain the MAGs that have the same non-circle marks as M, In this way, we obtain set of MAGs which are uniformly sampled from the space of MAGs consistent to M,.
Given an MAG M, let S(M) denote the set of MAGs that can be obtained from M by transforming one bi-directed edge to directed edge or one directed edge to bi-directed edge according to Prop. Denote the cardinality of S(M) by [S(M). We set the probability QMM" M) of an MAG M transformed to another MAG M' E ((M) as 1/IS(M)). Hence, the acceptance ratio p that used to decide whether to accept or reject the candidate is
P p= min min((,
P(M)Q( (4 P(M)((M M2) min (1| 1S(MM)
We propose Alg. 2 to select the intervention variable X. As shown by Lemma 15.1 in Appendix B, the graph Mo is an MAG consistent to Ml, From Line 2-Line 6, we execute MH algorithm to sample L' MAGs. Then, we select the MAGs among them which are consistent to M. on Line 7. Finally, we estimate the entropy by (1) and select X from Line 9-Line 14.
5 Experiments
In this section, we conduct simple simulation of the three-stage active learning framework. We generate 100 Frdös-Rényy random DAGs for each setting, where the number of variables d = 10 and the probability of including each edge p E {0.1, 0.15, 0.2, 0.25, 0.3). The weight of cach edge is drawn from 2[1, 2]. We generate 10000 samples from the linear structural equations, and take three variables latent variables and the others as observed ones. In the implementation of the MH algorithm in Alg. 2, we discard the first 500 sampled MAGS and collect the following 1000 MAGs. For each intervention variable X, we collect 10000 samples under dx = 2). and learn the circles at X by two-sample test with a significance level of 0.05.
We compare the maximum entropy criterion with baseline random criterion where we randomly select one variable with circles to intervene in each round. We show the results in Tab. 1, # int. denotes the number of interventions to achieve MAG identification. The effectiveness of the maximum entropy criterion is verified by noting that the number of interventions with maximum entropy criterion is fewer than that with random criterion. Further, we evaluate the three stages respectively. In Stage 1, we obtain a PAG by running FCI algorithm with a significance level of 0.05. In Stage 2, we adopt the two criteria to select intervention variables. In Stage 3, we learn the marks with corresponding interventional data and orientation rules. We evaluate the performance of Stage by # correct PAG/# wrong PAG. # correct PAG/# wrong PAG denotes the number of edges that are correctly/wrongly identified by FCI. An edge is correctly/wrongly identified by FCI if the edge learned by FCI is identical/not identical to the true PAG. The performance of Stage 2 is evaluated by # int.. And we evaluate the performance of Stage 3 by # correct int./# wrong int., where # correct int./# wrong int. denotes the number of edges whose direction are correctly/wronglyy identified by interventions. An edge is correctly/wrongly identified by interventions if its existence is correctly identified in P but the direction is uncertain, and after interventions we learn its direction correctl correctly/wrongly. We evaluate the performance of the whole process by Norm. SHD and FI. Norm. SHD denotes the normalized structural hamming distance (SHD), which calculated by dividing SHD by d(d - 1)/2. Fl score calculated by the confusion matrix to indicate whether the edge between any two vertices is correctly learned. According to the SHD and Fl score, the active framework can learn the MAG accurately when p is not large. And as shown by the evaluations of Stage I and Stage 3, the marks are learned accurately in Stage 3, and most of the mistakes are generated in Stage Hence, in the active learning framework, the PAG estimation in the first stage is the bottleneck of having good performance.

---

Table Number of interventions, normalized SHD, score, number of correctly/ wrongly learned marks by interventions, and number of correctly/wrongly learned marks in PAG over 100 simulations with d and varying p the format of mean std.
Strategy-P
Norn.
correct int.
wrong int.
correct PAG
wrong PAG
Random-0.10
2.88
1.28
0.02 0.04
0.85 + 0.29
3.92 + 2.40
0.11 + 0.53
4.78 + 3.11
0.39 = 0.82
MCMC-0.10
2.77
1.19
0.02 +: 0.04
0.85 +: 0.29
4.00 + 2.40
0.03 4: 0.22
Random-0.15
3.30
1.15
0.02 + 0.05
0.91 + 0.17
5.17 + 2.62
0.10 + 0.41
7.21 3.85
0.40
MCMC-0.15
3.20
1.03
0.02 0.04
0.92 1 0.16
5.25 d: 2.66
0.02 :: 0.14
Random-O 20
3,59 = 1.22
0.04 + 0.06
0.91 + 0.15
6,26 +: 2.75
0.19 + 0.61
9.26 + 3.94
0.59 + 1.30
MCMC-0.20
0.03
0.92
2.70
0.07
Random-0.25
3,47 1.34
0.08 + 0.14
0.89 +
3.37
0.06
11.92 + 4.01
1.59 + 2.85
MCMC-0.25
3.22 1.19
0.08 0.14
0.89 0.18
+ 3.39
0.09 0.35
Random-0.30
3.64 1.32
0.14
0.83 0.18
3.33
0.36 + 1.01
12.59 4.08
2.63 + 3.19
MCMC-0.30
3.55 1.37
0.14 0.15
0.83 0.18
7.25 + 3.50
0.14 = 0.43
Conclusion
In this paper, we show what causal relations are identifiable in the presence of latent variables given local background knowledge with sound and complete orientation rules. Based on the theoretical results, we give the first active learning framework for causal discovery in the presence of latent variables. In the future, will investigate the causal relations identifiability with general background knowledge. It is also worthy to study how our research may help some recent novel decision-making methodology [44].
Acknowledgment
This research was supported by NSFC (61921006), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the program A for Outstanding PhD candidate of Nanjing University. We are grateful to the reviewers for their valuable comments.
10

---

References
[1] Raha Moraffah, Mansoorch Karami, Ruocheng Guo, Adrienne Raglin, and Huan Liu. Causal interpretability for machine learning problems, methods and evaluation. SIGKDD Explor, 22 (1):18-33, 2020.
[2] Julius von Kügelgen, Amir- Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. On the fairness of causal algorithmic recourse. arXiv:2010.06522, 2020.
[3] Niki Kilbertus, Mateo Janzing, and Bernhard Schölkopf. Avoiding discrimination through causal reasoning. In Advances in Neurul Information Processing Systems, pages 636-666, 2017.
Giambattista Parascandolo, Moritz Hardt, Dominik
[4] Junzhe Zhang and Elias Bareinboim. Faimess decision-making the causal explanation formula. In Proceedings of the 32nd Conference on Artificial Intelligence, pages 2037-2045, 2018.
[5] Jin Tian and Judea Pearl. A general identification condition for causal effects. In Proceedings of the 18th National Conference Artificial Intelligence and 14th Conference on Innovative Applications of Artificial Intelligence, pages 567-573, 2002.
[6] lya Shpitser and Judea Pearl. Identification of joint interventional distributions in recursive semi-markovian causal models. In Proceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, pages 1226, 2006.
[7] Sanghack Lee and Elias Bareinboim. Causal effect identifiability under partial-observabiliy In Proceedings of the 37th International Conference on Machine Learning, pages 5692-5701, 2020.
[8] Tian Qin, Tian-Zuo Wang, and Zhi-Hua Zhou. Budgeted heterogeneous treatment effect estimation. In Proceedings of the 38th International Conference on Machine Learning, pages 8693-8702, 2021.
[9] Zhuangyan Fang, Ruiqi Zhao, Yue Liu, and Yangbo He. On the representation of causal background knowledge and its applications in causal inference. arXiv, 2022.
[10] Judea Pearl. Causality. Cambridge University Press, 2009.
[11] Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. MIT Press, 2000.
[12] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554, 2002.
[13] Sara Magliacane, Tom Claassen, and Joris M. Mooij. Ancestral causal inference. In Advances in Neural Information Processing Systems, pages 4466 4474, 2016.
[14] Biwei Huang, Kun Zhang, Yizhu Lin, Bernhard Schölkopf. and Clark Glymour. Generalized score functions for causal discovery. In Proceedings of the 24th ACM International Conference on Knowledge Discovery & Data Mining, pages 1551-1560, 2018.
[15] Daniel Irving Bernstein, Basil Saced, Chandler Squires, and Caroline Uhler. Ordering based causal structure learning in the presence of latent variables. In The 23rd International Conference on Artificial Intelligence and Statistics, pages 4098-4108. 2020.
[16] Zheng-Mao Zhu, Xiong-Hin Hui Chen, Hong-Long Tian, Kun Zhang, and Yang Yu. Offline reinforcement learning with causal structured world models. arXiv, 2022.
[17] Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15:2009-2053,
2014.
[18] Ruichu Cai, Jie Qiao, Kun Zhang, Zhenjie Zhang, and Zhifeng Hao. Causal discovery from dis- crete data using hidden compact representation. Advances in Neural Information Processing Systems, pages
2018.
[19] Ignavier Ng, Sébastien I Lachapelle, Nan Rosemary Ke, Simon Lacoste-Julien, and Kun Zhang. On the convergence of continuous constrained optimization for structure learning. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 8176-81999 8198, 2022.
11

---

[20] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 7865):977-1012 2016.
[21] Biwei Huang, Kun Zhang, Jiji Zhang, Joseph D. Ramsey, Ruben Samchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from heceengennoouu/nonstationnyy data. Journal of Machine Learning Research, 21:89:1-89:53, 2020.
[22] Yangbo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9:2523-2541 2008.
[23] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 13:2409- 2464, 2012.
[24] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. In Advances in Neural Information Processing System, pages 3195-3203, 2015.
[25] Solia Triantafillou and Ioannis Tsamardinos. Constraint- causal discovery from multiple interventions over overlapping variable sets. Journal of Machine Learning Research, 16: 2147-2205, 2015.
[26] Yuhao Wang, Liam Solus, Karren Yang, and Caroline Uhler. Permutation-based causal inference algorithms with interventions. In Advances in Neural Information Processing Systems, pages 5824-5833, 2017.
[27] Juan Gamella and Christina Heinze-Deml. Active invariant causal prediction: Experiment selection through stability. In Advances in Neural Information Processing Systems, 2020.
[28] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. In Advances in Neural Information Processing Systems, 2020.
[29] Tian-Zuo Wang, Xi-Zhu Wu, Sheng-Jun Huang, and Zhi-Hua Zhou. Cost-effectively identi- fying causal effects when only response variable is observable. In Proceedings of the 37th International Conference Machine Learning, pages 10060-10069, 2020.
[30] Tian-Zuo Wang and Zhi-Hua Zhou. Actively identifying causal effects with latent variables given only response variable observable. In Advances in Neural Information Processing Systems, pages 15007-15018, 2021.
[31] Kui Yu, Lin Liu, and Jiuyong Li. Learning markov blankets from multiple interventional data sets. IEEE transactions on neural networks and learning systems, (1)):20005-201 2019.
[32] Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, Simon Gyorgy, Weiner Michael W, Aisen Paul, Petersen Ronald, Jack Clifford R, Saykin Andrew J, Jagust William, et al. Challenges and opportunities with causal discovery algorithms: Application to alzheimer's pathophysiology. Scientific Reports (Nature Publisher Group), 10(1), 2020.
[33] Thomas Richardson, Peter Spirtes, et al. Ancestral graph markov models. The Annals of Statistics, (0(4):962-1030 2002.
[34] R Ayesha Ali. Thomas Richardson, Peter Spirtes, and Jiji Zhang. Orientation rules for con- structing markov equivalence classes of maximal ancestral graphs. Technical report, 2005.
[35] Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17)1183--1896 2008.
[36] Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the 1sst Annual Conference on Uncertainty in Artificial Intelligence, pages 403-410, 1995.
[37] Bryan Andrews, Peter Spirtes, and Gregory F. Cooper. On the completeness of causal dis- covery in the presence of latent confounding with tiered background knowledge. In The 23rd International Conference on Artificial Intelligence and Staristics, pages 4002-4011, 2020.
[38] Hui Zhao, Zhongguo Zheng, and Baijun Liu. On the markov equivalence of maximal ancestral graphs. Science in China Series A: Mathematics, 48(4):548-56) 2005.
12

---

[39] Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Polynomial sarnomial-time algorithms for count- ing and sampling markov equivalent dags. In 35th AAAI Conference on Artificcal Intelligence. pages 12198-12221 12206, 2021.
[40] Siddhartha Chib and Edward Greenberg. Understanding the metropolis-hastnng algorithm. The american statistician, 4974)3327-335, 1995.
[41] Jiji Zhang and Peter Spirtes. A transformational characterization of markov equivalence for directed acyclic graphs with latent variables. In Proceedings of the 21 Conference in Uncertainty in Artificial Intelligence, pages 667-674, 2005.
[42] Jin Tian. Generating markov equivalent maximal ancestral graphs by single edge replacement. In Proceedings of the 21st Conference Uncertainty in Artificial Intelligence, pages 591-598. 2005.
[43] Luke Tierney. Markov chains for exploring posterior distributions. the Annals of Statistics, pages 1701-1728, 1994.
[44] Zhi-Hua Zhou. Rehearsal: learning from prediction to decision. Frontiers of Computer Science, 16(4), 2022.
[45] Ayesha R. Ali, Thomas S. Richardson, Peter Spirtes, and Jiji Zhang. Towards characterizing markov equivalence classes for directed acyclic graphs with latent variables. In Proceedings of the 21st Conference in Uncertainty Artificial Intelligence, pages 10-17, 2005.
[46] Peter Spirtes and Thomas Richardson. A polynomial time algorithm for determining dag cquivalence in the presence of latent variables and selection bias. In Proceedings of the 6th International Workshop Artificial Intelligence and Statistics, pages 489-500, 1996.
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]
(c) Did you discuss any potential negative societal impacts of your work? [No] It is mainly theoretical paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms
them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(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 ex- perimental results (cither in the supplemental material or as a URL)? [No] will be publicly available later.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "Zlx1MFXuf7H", "reviewer": "Reviewer_Zw4J", "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.\nNext, 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.\n\n", "questions": "Comparison to learning PAGs with interventional data:\nThere 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?\n\nLine 156:\nWhat do you mean by \"algorithm can be achieved\"? What does it mean for an algorithm to be achieved?\n\n\n[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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality, quality, and significance:\nThe 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).\n\nClarity:\nOverall, 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).\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XKI6qh_BGcG", "reviewer": "Reviewer_Wrk3", "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.", "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?\n2. **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?\n3. **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?\n4. **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?\n5. **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)?\n6. 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Pros:\n  - **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.\n  - **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.\n\n+ 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H1dvx5xfTYi", "reviewer": "Reviewer_BMb7", "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. ", "questions": "I also only have some questions for the authors\n1. 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?\n2. 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?\n", "limitations": "Not applicable.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept