Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
Authors: Tian-Zuo Wang
Wen-Bo Du
Zhi-Hua Zhou
Venue: ICML 2025 oral (2025)
Keywords: maximal ancestral graphs
MAG listing
Primary area: probabilistic_methods->graphical_models
TL;DR: We present the first Polynomial-Delay Maximal Ancestral Graph Listing Algorithm

Abstract: A maximal ancestral graph (MAG) is widely used to characterize the causal relations among observable variables in the presence of latent variables. However, given observational data, only a partial ancestral graph representing a Markov equivalence class (MEC) of MAGs is identifiable, which generally contains uncertain causal relations. Due to the uncertainties, \emph{MAG listing}, \emph{i.e.}, listing all the MAGs in the MEC, is critical for many downstream tasks. In this paper, we present the first \emph{polynomial-delay} MAG listing method, where delay refers to the time for outputting each MAG, through introducing enumerated structural knowledge in the form of \emph{singleton background knowledge (BK)}. To incorporate such knowledge, we propose the \emph{sound} and \emph{locally complete} orientation rules. By recursively introducing singleton BK and applying the rules, our method can output all and only MAGs in the MEC with polynomial delay. Additionally, while the proposed novel rules enable more efficient MAG listing, for the goal of incorporating general BK, we present two counterexamples to imply that existing rules including ours, are not yet \emph{complete}, which motivate two more rules. Experimental results validate the efficiency of the proposed MAG listing method.

Pelyn MAG Listing with Novel Locally Complete Orientation Rules
Tian-Zuo Wang' Wen-Bo Du 12 Zhi-Hua Zhou 12
Abstract
B
A maximal ancestral graph (MAG) is widely used to characterize the causal relations among observ- able variables in the presence of latent variables. However, given observational data, only a partial ancestral graph representing a Markov equiva- lence class (MEC) of MAGs is identifiable, which generally contains uncertain causal relations. Due to the uncertainties, MAG listing, i.e,, listing all the MAGs in the MEC, is critical for many down- stream tasks. In this paper, we present the first polynomial-delay MAG listing method, where de- lay refers to the time for outputting each MAG, through introducing enumerated structural knowl- edge in the form of singleton background knowl- edge (BK). To incorporate such knowledge, we propose the sound and locally complete orienta- tion rules. By recursively introducing singleton BK and applying the rules, method can output all and only MAGs in the MEC with polynomial delay. Additionally, while the proposed novel rules enable more efficient MAG listing, for the goal of incorporating general BK, we present two counterexamples to imply that existing rules in- cluding ours, are not yet complete, which motivate two more rules. Experimental results validate the efficiency of the proposed MAG listing method.
D
(a) DAG D (b) MAG M
(c) PAG P
(d) PMG H
Figure 1: Fig. I(a): a DAG 'D including a latent confounder
L and a selection variable S. Fig. I(b): The MAG M char- acterizing the causal relations over the observable variables in D. Fig. I()): The PAG P representing the MEC of M. Fig. I(d): When orienting A + B, there must be B + C.
A directed acyclic graph (DAG) is a classical graphical model to characterize causal relations when all relevant variables are fully observable. In practice, however, latent variables generally exist, including latent confounders and selection variables. A latent confounder is a latent variable that influences more than one observed variable, e.g., genes influence both whether a person smokes and whether this person develops lung cancer, which are typically latent. A selection variable is a latent variable influenced by multiple observed variables and plays a role in determining whether the data is collected. E.g., whether a person goes to a hos- pital S depends on both whether he is ill and whether he is alive. If the data is collected only from the hospital, it is conditioned on S = 1, indicating the distribution of the col- lected data differs from the overall population distribution.
In the presence of latent variables, maximal ancestral graph (MAG) is generally used to characterize the causal relations among observable variables (Richardson et al., 2002). Given DAG in Fig. 1(a) with latent confounder L. and selection variable S, the corresponding MAG is Fig. 1 However, existing theoretical results imply that DAG/MAG is not identifiable from observational data (Spirtes et al., 2000), un- less introducing model or functional assumptions (Shimizu et al., 2006; Zhang & Hyvärinen, 2009). In the presence of latent variables, only a Markov equivalence class (MEC) of MAGs, which encode the same conditional independence, can be identified from observational data. This MEC is rep- resented by a partial ancestral graph (PAG), which contains uncertain structures denoted by circles (o) as Fig. 1(c).
1. Introduction
Recently, causality has gathered significant attention in arti- ficial intelligence. In this field, causal graph characterizing causal relations plays vital role. On one hand, a causal graph provides a profound insight into underlying physical mechanism (Cai et al., 2018; Runge et al., 2019). On the other hand, it serves as a crucial tool for estimating causal effects (Pearl, 2009), which are essential in applications.
'National Key Laboratory for Novel Software Technology, Nanjing University, China "School of Artificial Intelligence, Nan- jing University, China. Correspondence to: Zhi-Hua Zhou <zhouzh@ @ lamda.nju.cdu.cn.
Given that only a PAG with uncertainties is identifiable, MAG listing, i.e., listing all the MAGs in the MEC repre- sented by the PAG, is crucial for many downstream tasks.
Proceedings of the 4rnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
For example, when uncovering causal relations within MEC by introducing active interventions, minimizing the number of interventions is often desirable due to their high cost. The maximal entropy criterion is often employed (He & Geng, 2008; Wang et al., 2023b), requiring entropy esti- mation based on all graphs in the MEC, necessitating MAG listing. Additionally, in some studies on structure learning with additional structural knowledge (Kocaoglu, 2023: Ger- hardus, 2024), MAG listing is also required. Despite its importance, MAG listing has received relatively limited at- tention in the literature, unlike DAG listing, which addresses a similar task in the absence of latent variables (Chickering, 1995; Chen et al., 2016; Wienöbst et al., 2023). Inherently, MAG listing is more challenging than DAG listing due to the existence of bi-directed edges and undirected edges.
consistency between the generated MAGS and the PAG, we introduce orientation rules that are sound and locally com- plete for incorporating singleton BK. Building upon these orientation rules, we develop the first polynomial-delan al- gorithm for MAG listing and prove that it outputs all and only the MAGs in the MEC represented by the given PAG.
Beyond MAG listing, as discussed earlier, it remains un- clear what orientation rules are sound and complete for incorporating general BK in the presence of latent variables, which is crucial for solving the open problem of causal rela- tion identification from observational data and BK (Zhang, 2008). The novel orientation rules in this paper highlight the incompleteness of existing rules. Furthermore, we provide two counterexamples to demonstrate that the existing rules, including ours, are not yet complete for incorporating BK. These counterexamples motivate two more orientation rules on incorporating BK. Our contributions are threefold.
For MAG listing, it is necessary to determine all possible orientations of the uncertain structures (circles) in the given PAG. However, directly enumerating the orientation com- binations of all circles is computationally prohibitive. A more feasible approach is to recursively introduce structural knowledge and utilize orientation rules. In each round, we enumerate a part of circles. The enumerated orientation can serve background knowledge (BK), which is then used to orient other circles by orientation rules, thereby reducing redundant enumeration. For example, consider a PAG P in Fig. I(c), if we enumerate the circle at B as an arrowhead on Ac-o B, it follows B- - C according to the orientation rules of Zhang (2008), making it unnecessary to enumerate the circles on the edge between B and C. Notably, the above idea for MAG listing must be applied cautiously: When BK is introduced, the orientation rules need to be sound and complete to orient the circles that may be enumerated later, otherwise we may obtain some extra MAGs inconsistent with the PAG. ! However, despite extensive efforts in the lit- erature (Andrews et al., 2020; Mooij et al., 2020; Wang et al., 2023b; 2024b; Venkateswaran & Perkovic, 2024), remains unclear what orientation rules are sound and complete for incorporating BK in the presence of latent variables.
(1) We present three novel orientation rules to incorporate singleton background knowledge which is involved in MAG listing, and prove that the rules are sound and locally complete for broad class of graphical models.
(2) Building upon the orientation rules, we propose the first polynomial-delay MAG listing algorithm, which can output all and only the MAGs in the given MEC. Experiments validate the effectiveness and efficiency.
(3) Beyond MAG listing, we demonstrate that the existing orientation rules including ours are not yet complete for incorporating BK by two counterexamples, which further motivate two more rules incorporating BK.
2. Preliminary
In this paper, we denote vertex by uppercase letter and a set of vertices by boldface letter. The set of vertices/edges in a graph G is denoted by ((G)/E(G). For a set of ver- tices V' C VG),, the subgraph of G induced by V is the graph consisting with V and the edges connecting V G, denoted by G[V'). Denote G[V(G) by G[-V'.
To the best of our knowledge, Wang et al. (2024a) proposed the first MAG listing method MAGLIST that avoids exhaus- tive search. However, its computational complexity has not been formally analyzed. In this paper, we consider the com- putational complexity of MAG listing. An important metric for evaluating algorithmic complexity is delay (Johnson et al., 1988), which refers to the time required to produce each output. We demonstrate that MAGL.ST incurs an ex- ponential delay, because it enumerates all circles of a vertex simultaneously at each step, resulting in significant computa- tional overhead. To address this issue, we propose a refined approach that enumerates only one circle at each step. The enumerated orientations are termed singleton BK. To ensure
A graph is mixed if it consists of undirected, directed, and bi-directed edges. The endpoints of an edge are referred to as marks. If a graph contains the three kinds of marks arrowheads, tails, and circles, it is a partial mixed graph (PMG). We use to denote a wildcard of anyone of the three marks. structure V,*-+ V,, < <+Vy is a collider, and we further say it is unshielded if V; is not adjacent to Vk-
For two vertices in a PMG H. V; is parent of V, if there is Vn + V, in H. V,2 a-o Vj is circle edge. Consider a path p = (Vi, V2, ... Va). p is directeddcirceeppossiilee di- rected path if for each edge connecting V2 and V++1, 1 S i S d 1, is V;2 - V++iVV, V/+1/no arrowhead V; and
I We provide detailed illustration in Sec. 3.1.
2

---

Polynomial-Dece MAG Listing with Novel Locally Complete Orientation Rules
C1
C2
C
C2
C
C2
C
C2
X
A
x
x
A
'
Vo
Vn
Vo
V
Vo
V
Vo
Vn
C
B
C
B
C
B
C
B
(a)
(b)
(c)
(d)
(a) PAG
(h) Tiered BK
(c) Local BK
(d) Singleton BK
Figure 2: Fig. 2(a): PMG with an unbridged path Vo o-o ...0-0 V relative to {C1, C2). Fig. 2(b)/(c)/((d); MAGS consistent with the PMG in Fig. 2(a).
Figure 3: Given PAG in Fig. 3(a), Fig. 3(b), 3(c), and (d)
depict tiered BK where {X} precedes {A.B, C}. local BK
regarding X, and singleton BK regarding X, respectively.
no tail at V++1- p is uncovered if V1 adjacent to 24+2- is minimal if any two non-consecutive vertices are not adjacent. V; is an ancestor/possible ances- tor of V3 if there is a directed/possible directed path from V; to Vi or Vi = Vy. Descendantpoossible descendant is defined similarly. Denote the set of vertices that are par- entssanestoss//ssendatt/ssssssso
V2 is not
vertices into ordered components, where relations between components are known, while those within each component remain uncertain. In contrast, local BK provides full struc- tural knowledge regarding several vertices. Consider a PAG in Fig. 3(a). Fig. 3(b) and Fig. 3(c) depict tiered BK where {X} } precedes {A.B, C} and local BK regarding X.
descendants of V in H by Pa(V, (V H) DD H) /Voss,Vee, H). V; E Ane( (V, H) if there is V E V such that V, Anc(V, H).
Finally, we introduce a broad class of PMGs, PMG compat- ible with local transformation, in Def. 4 in App. B. Briefly speaking, if PMG fulfills chordal, balance, complete, and constructive conditions, then it is PMG compatible with local transformation. See App. B for details. Evidently, the PAG fulfills the four conditions, thus PAG is special case of PMG compatible with local transformation.
We guide readers to Richardson et al. (2002) for ancestral and maximal property. If a mixed graph fulfills ancestral and maximal property, it is a maximal ancestral graph (MAG), denoted by M. partial ancestral graph (PAG), denoted by P. represents MEC of MAGs. Based on P, we could obtain PMG H by orienting some circles as arrowheads or tails, MAG M is consistent with If if it belongs to the MEC represented by P and has the non-cirele marks in H. Given background knowledge (BK), MM is consistent with BK if M has the marks contained in the BK.
3. The Proposed Method
In Sec. 3.1, revisit existing MAG listing approach, and identify the bottleneck leading to redundant computational complexity. To overcome the limitation, we investigate sin- gleton BK, a critical component in MAG listing. In Sec. 3.2, we propose three novel orientation rules to incorporate sin- gleton BK. Building on these rules, we present a polynomial- delay MAG listing algorithm in Sec. 3.3. Discussions are presented in See. 3.4. All the proofs are given in App. D.
Definition 1 (Unbridged path relative to V'; (Wang et al., 2024b)). Let V' be subset of vertices in PMG H. A path p: Vo o-o ... a-o Vn is an unbridged path relative to V' if there is C₁, C2 E V such that there is a minimal path C1 <o% o-o 11 0-0 ... o-o Vn C2 except for an edge
G C2 in H.
3.1. Revisiting MAGLIST
We present unbridged path in Def. 1, with an example in Fig. 2(a). Intuitively, given a PMG H, unbridged path rela- tive to V' describes case that in any MAG M consistent with H, each vertex V in the unbridged path is always ancestor of V'. See Fig, 2, in any MAG consistent with the PMG in Fig. 2(a), since there cannot be new unshielded colliders introducing additional conditional independence, the MAG can only be as Fig. 2(b), 2(c), or 2(d), where each V,, 0 S i S n is always an ancestor of either C or C2.
In this part, we revisit the MAG listing method MAGLIST proposed by Wang al. (2024a) and briefly explain the reasons behind its exponential delay, which motivates the development of our polynomial-delay method.
Given a PAG P learned from observational data, MAGLIST obtains all MAGs consistent with P by recursively enumer- ating the circles of each vertex. A copy of the realization process of MAGLIST is shown in App. C. Briefly speak- ing, in each round, MAGLIST selects vertex with circles, denoted by X, then (a) enumerates all the circles at X as non-circles; (b) updates the graph based on the enumera- tions. In step (a), each enumerated non-circle configuration at X dictates a local structure of X. Wang et al. (2024a) presented the graphical condition to determine whether it is valid, i.e., whether there is MAG consistent with P and
To learn PAG with observational data, Ali al. (2005a); Zhang (2008) presented some orientation rules. Further, rules for incorporating specific types of BK, such as liered BK (Andrews et al., 2020) and local BK (Wang et al., 2023b), were proposed, along with others (Wang et al., 2024b; Venkateswaran & Perkovic, 2024). These rules R2 - R13 are provided in App. A. Specifically, tiered BK organizes
3

---

Polynomial- Delly MAG Listing with Novel Locally Complete Orientation Rules
C
C
C2
X
X
K 0
T
K
K
Tis
K
K1
T
K
2
Kg
K
K2
K3
F2
(a) PAG Pi
(b) PMG H1
(c) PAG P3
Figure 4: Two examples to show the incompleteness of the existing orientation rules. A PAG P1 is shown in Fig. 4(a) where there must be X + F when introducing BK C+++ X ++C2. For contradiction, suppose there is X ++ F. as shown in Fig. 4(b), the blue edges Tio X toT2 are oriented by R12, which form an unshielded collider. Another PAG P2 shown in Fig. 4(c), where there also X + F but not identifiable by existing rules when introducing BK C1++ X C+
the local structure. Each enumerated valid local structure introduces local BK regarding X. Hence, the existing ori- entation rules for incorporating local BK can soundly and completely update the graph in step (b). It is proved that the graph obtained after each round is a PMG compatible with local transformation, enabling the process to be recur- sively executed for every vertex. Let d denote the number of vertices. In step (a), the enumeration of the circles at X has a complexity of O(24), while the number of valid local structures could be (d), leading to an exponential delay.
at B on B o-o C as an arrowhead, leading to a PMG with Ao B CoC. All the MAGs obtained from this PMG are inconsistent with P, as the additional unshielded colliders relative to P indicate extra conditional independencies.
As discussed above, when enumerating each circle at X one by one, vital establish sound and locally complete orientation rules to transform the circles X. Each trans- formation at X can be viewed as a type of BK. Hence, we study orientation rules to incorporate such BK in Sec. 3.2.
Hence, the simultaneous enumeration of all the circles at X is the main bottleneck for the undesired complexity. To develop a polynomial-delay method, it is essential to elimi- nate the redundant enumeration in step (a). We focus on this step. A direct idea is to enumerate each circle at X one by one, instead of simultaneously. After transforming a circle, we apply the orientation rules to update the graph, thereby avoiding redundant enumeration. For example, given a PMG in Fig. I(c), consider enumerating the circles at B. If we first orient Ao B, then B- > C follows by the rules as Fig. (dd) avoiding enumerating the circle at B on B o-o C.
3.2. The proposed rules to incorporate singleton BK
In this part, we propose the orientation rules for incorporat- ing singleton BK into PMG, where singleton BK refers to the additional structural information regarding a singleton vertex. Using the rules, during MAG listing process, we can update the graph with the enumerations of circles regarding the selected variable. Since a PAG can be identified from observational data (Zhang. 2008), we make convention that when we say PMG, it refers tained based on a PAG, i.e., the PMG at least contains the structural information in a PAG. We assume BK is correct, ensuring the existence of MAGS consistent with P and BK. Definition 2 (singleton BK). Given a PMG H and BK, BK is singleton if the BK only directly indicates the orientation of some circles regarding one vertex.
PAG or PMG ob-
However, the above idea cannot be applied directly. It might not only introduce additional computational overhead but, more importantly, result in outputting MAGs inconsistent with P. This is because when we enumerate only one or a proper subset of circles at X, the existing orientation rules are not locally complete to update the graph, i.e., some circles X that should have been identified as tails or arrowheads might remain unidentified. In such cases, we will obtain extra MAGs by subsequent enumerations. See Fig. 1(c) for an example. Consider enumerating the circle at B on Aoo B as an arrowhead. Since the rules are not locally complete, suppose the circle at B on BooO'n is not identified, which should have been identified by Ri given Ao- B. In this case, we would subsequently enumerate the circle
Singleton BK implies only the orientation of circles regard- ing one vertex, as shown in Fig. 3(d) where BK regarding X is introduced. Note that singleton BK does not necessarily indicate the orientation of all the circles regarding the vertex. It is the main distinction between singleton and local BK.
As discussed earlier, given singleton BK, an important ques- tion for MAG listing is whether the existing orientation rules are sound and locally complete for incorporating such BK. We demonstrate the incompleteness by presenting two counterexamples in Fig. 4. Consider a PAG in Fig. 4(a) and singleton BK regarding X as C1 Ch+ X C Using the
We provide an example to demonstrate that MAGLIST could incur an exponential delay in See. 3.4.

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
existing rules, no new orientations are triggered; however, X + F should be identified. We illustrate it by contradic- tion. Suppose PMG H1 as Fig. 4(b) satisfies the singleton BK but includes X ++ F. For the left shaded region in H1, Tio X is oriented by R12 (see App. A for R12), as there is an unbridged path K1 о-o K2 relative to {C1, Similarly, for the right shaded region, T2o-> X is oriented. Consequently, a new unshielded collider Ti X < is formed. However, introducing new unshielded colliders relative to P is forbidden, as it implies conditional inde- pendence that differs from P such that any MAGs with this structure are inconsistent with P. If we examine why X < F is impossible in Fig. 4(b) given the singleton BK regarding X, orienting Xo-> F as X - F will lead to new arrowheads at X by R12- forming new unshielded colliders that are forbidden. Beyond R12, similar issues may arise with R₂ and R11- To formalize the introduction of new arrowheads by R2, R11, R12, we define prior to in Def. 3. Definition 3. Consider a PMG H. For two vertices A, B with A # X o-+ B. we say that A is prior to B relative to X if there exists set of vertices Fo A), Fi,.... (= B), 21 1 such that for any 0 S i S t 1, there is F, +- X, and one of the three following conditions holds:
Pi41
F+41
K
X
X 6 uncovered p.d. F.
X
F2
Fe
(a) By R₂
(b) By Rn
(c) By R1z
Figure 5: Examples of that Vi is prior to V4+1 relative to X. If we orient X o- Fi+1 as X < Feta in Fig. 5(a))(()/((c)). X o+ F; will be oriented as X ++ F, by R2/ RR1/RR1RR11
R14 Suppose an edge Xo- B in PMG H, if there is Ti # X o- T2 where both T1 and T2 are prior to B relative to X, and there is either (a) an unbridged path F o0o P's relative to {2i, 72} such that X o+ F, VFi,iiii. or (b) T, is not adjacent to T2, then orient Xo+ B as X + B.
R15 If A + R. and Ao+ R. orient Ao+ R as A - R. (generalization of Rs)
R16 If B - or A Bo-R. R, then orient B -oRR or Bo - R or B B+R. R.
(I) there is edge F. + Fi+1 in H.
Additionally, two additional rules R15, Rie are introduced to accommodate the presence of undirected edges. Here- after, the term proposed orientation rules refers to R2 1 Prop. implies that Rı4- R1s are sound for incorporating BK. The soundness of the remaining rules has been demon- strated in previous studies (Ali et al., 2005b; Zhang, 2008; Wang et al., 2024b; Venkateswaran & Perkovic, 2024).
(2) there is an uncovered possible directed path (X, Fi,".,, and an edge M + Fi+1 in H,
(3) there is an unbridged path (K,,... K,)) relative to S in H[-Sp and for every vertex K2 E [KI,... Kmm, there exists an uncovered possible directed path (X, F,.... K2) (F, # Kÿ), where SF. (V E V(H)VV>> X in HJ U (F++))
Proposition 1. R14 Rio are sound for incorporating background knowledge to PMG.
Intuitively, for vertices F; and Fi+1 in Def. 3 fulfilling one of the three conditions, if there is X Fi then X c+ F; is transformed to X F; by R2/R11/R12, of which the corresponding conditions are shown in Fig. 5. Hence, if A is prior to B relative to X as Def. 3, when X a-* B is transformed to X B, X a-* A will be finally transformed to X + by repeatedly triggering R2, R11, R12-
In fact, Rs and Rio are special cases of R15 and R14- respectively. Since Rg and R10 are canonical rules, we introduce new rules to extend their scope. Next, we present our main result in Thm. 1, demonstrating that the proposed rules are locally complete for incorporating singleton BK into any PMGs compatible with local transformation.
Theorem 1 (Locally complete). Consider vertex X in PMG MI compatible with local transformation, the proposed orientation rules R2 RiG are locally complete for intro- ducing singleton BK regarding X into M. That is, in the PMG H obtained from MI using the singleton BK and ori- entation rules, if there is an edge X a- Fi in H, there must exist two MAGS M M2 consistent with M and singleton BK, such that there is X F in Mi and X F in M2.
Based on Def. 3, we present R14, which is inspired by the counterexamples. Intuitively, if Ti and T2 are prior to B relative to X in R11, orienting X + implies X + *T, and X T2 In this case, given the conditions in R14 that (a) there is an unbridged path Fl o-o o-o Fx relative to (T,,T) } such that X c-* F;, VF,. or (b) Ti is not adjacent to T2. there must be new unshielded colliders introduced, which is forbidden in the process of incorporating BK. The example for case (b) in Ri4 has been provided in Fig. 4(a). For case (a), we give another example in Fig. 4(c). In this example, T, is adjacent to T2. but there is an unbridged path F1 o-o Fg relative to {Ti,Ta}, In this case, there is X -> F oriented as well.
Despite being locally complete, the proposed rules are not necessarily complete for incorporating singleton BK. Local complete property ensures that by applying the orientation rules, we can identify all marks at X that are identifiable, but it imposes no restrictions on the identification of marks
5

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
at other vertices. In Sec. 3.3, we demonstrate that locally complete rules suffice develop a polynomial-delay MAG listing algorithm. We discuss the completeness in Sec. 4.
Algorithm 1 MAGLIST-POLY
Require: A PAG P
1:
S = 0 D Record all the MAGs consistent with P
The complexity of implementing the rules. In this paper,
2: ORIENTGRAPH(P)
we do not touch much on the computational complexity to implement the rules. We provide a rough analysis. Sup-
3: function ORIENTGRAPI(M,, S)
4:
if there are no circles in MI then > Ms a MAG
pose a PMG has d vertices and m edges. For R11, there
5:
S SUSU (M)
are (m) edges A o-e B that can be possibly transformed. Finding SA and every vertex that can be K; requires ((d)
6:
else
7:
Select variable X where there circles in MI
and (m)) respectively. The total complexity is d)) For R12. there are (dd) variable where circles are trans- formed. Finding each vertex K; takes ((m), and detecting the existence of unbridged paths requires O (m²). Hence the total complexity is ( d). For R14, For each variable X, there are (cP) pairs of Vi, V such that = o V and detecting whether V; is prior to Vj (or vice versa) rel- ative to X takes O(m d). Additionally, there are (d) variables X such that Xo - V is possibly oriented by R14. For each such X, since we already know which vari- ables are prior to V relative to X, enumerating each pair Ti, T2 prior to V takes (d2), and detecting conditions (a) and (b) in Ri4 takes (m)) Hence, the total complexity is (dF))(OOmmm))) ((()))((P)()))
8:
I == 0 Record all the PMGs without circles at
X obtained from M
9:
LOCALTRANSE TAASFORRAM,, X) for M' in Z do ORIENTGRAPH(MI,
10:
11:
end for 13: end if
12:
14: end function
15: function LOCALTRANSFORM(H,,
16: if there are no circles at X in H then
17:
IU
18:
else
19:
Select vertex V with an edge X a-* V in H Obtain H' from H by orienting X +VV and using the proposed orientation rules
= O(m²d').
20:
For R1G. the complexity is O(m²). For R17, there are (m) edges that can be D++ C. To find the vertices A, B, the complexity is (dd)) Hence the total complexity is (md2). The complexity of implementing R₁ - R10 is less than (m)) Thus, the overall complexity of implement- ing the rules is Omm2d* ) The complexity is significantly higher than that of R₂= R10, which implies the intrinsic difficulty of incorporating BK with latent variables.
21:
LOCAL XX
22:
Obtain H" from H by orienting X ++V and using the proposed orientation rules LOCALTRANSFORM((F,, X)
23:
24: end if
25: end function
Ensure: S
3.3. Polynomial-delay MAG listing
The realization process of an inner loop is shown in Fig. 6 using search tree. Suppose X is the selected vertex where circles are being transformed. The root is a PMG compatible with local transformation. In the first round, we enumerate the circle at X on Xo- A. Enumerating it as an arrowhead and a tail yields two graphs, shown in the first and fourth graphs in the second layer. These graphs are further updated using the orientation rules, resulting in the two additional graphs in this layer. In the second round, we enumerate the circle at X on X c-o B. Due to space limit, only the graphs obtained after both enumerating a circle at X and using the rules are displayed in the third and fourth layers. The shaded graphs denote the PMGs without circles at X, which are passed back to outer loop. For the PMGs with circles at X, we continue enumerating. Through the search process, we obtain all valid orientations of circles at X.
In this part, based on the rules for incorporating singleton BK, we present our MAG listing method MAGLIST-POLY.
The algorithm is detailed in Alg. 1. Starting from a PAG P learned from observational data, the method operates through two nested loops implemented as recursive func- tions. In the outer loop (Function ORIENTGRAPII) each iteration selects a vertex with circles, denoted as X, and invokes the inner loop. In the inner loop (Function LOCAL.- TRANSFORM), each iteration enumerates circle at X as an arrowhead and a tail. The resulting two graphs are then updated using the proposed orientation rules. This process continues recursively until there are no circles at X. The obtained graphs are passed back to the outer loop. The outer loop stops when there is no vertex with circles. Notably, all the graphs obtained on Line 17 are PMGs compatible with local transformation.3 Therefore, in each round of outer loop, the input graph is a PMG compatible with local transformation, in which case the condition of Thm. holds.
Finally, for MAGLIST-POLY. Thm. 2 guarantees that it can find all and only the MAGS consistent with P, and Thm. 3 ensures the polynomial delay. These results establish the theoretical effectiveness and efficiency of MAGLIST-POLY:
We detail it in the proof of Thm. 2.
6

---

Polynomial-Dede -ellay MAG Listing with Novel Locally Complete Orientation Rules
A PMG compatible with local transformation
update with rules
update with rules
Orienting circle odge (A.
Round
Orienting the circle X edge (B.X)
Orlenting the clecle edge (C,
Round
Figure 6: A realization process of Line 9 of Alg. 1, which transforms the circles at X given a PMG compatible with local transformation. In the first/second/third round, we transform the circle at X on the edge between X and A/B/C. After each transformation, we further use the rules to update. Shaded graphs denote the PMGs without circles at X, where the inner loop stops and the outer loop is executed to select the next vertex with eircles. Due to space limit, we show the circle transformation X (colored by red) and the update with rules (colored by blue) respectively only for the first round.
Theorem 2. Algorithm is valid to list all and only the MAGs consistent with P.
Theorem 3. Given PAG P with d vertices and m edges, suppose there are N MAGs consistent with P. Denote the complexity of implementing Alg. I for P by T(N,d) d). Then T(N, d)/N < O(m2d*)
Figure 7: An example to show that MAGLIST proposed by Wang et al. (2024a) could incur an exponential delay.
3.4. Discussions on MAG listing
According to the results above, we have demonstrated that using sound and locally complete rules for incorporating singleton BK suffices to develop a polynomial-delay MAG listing algorithm. Next, we present an example to illustrate that MAGLIST proposed by Wang et (2024a) can incur exponential-delay. Consider PAG P in Fig. 7. When MAGLIST is applied, the method selects X and enumerates the circles at X. In this case, the method will enumerate 2d possible orientations, resulting in a total complexity of at least (24)) Next, consider the number of MAGS consistent with P. Since no additional unshielded colliders can appear these MAGs, the number of valid local structures of X is d ++ The delay is O(2d /d), indicating exponential delay.
able, we need to perform an additional validity check using Lemma 2 in App. D, which is costly yet effective for MAG listing. In such cases, extra time spent detecting and dis- carding invalid transformations, which could be avoided by using locally complete rules. Now, is unclear whether this extra computation leads to delay exceeding polynomial time. The main challenge lies in that the number of MAGs consistent with given PAG unknown, making it difficult to analyze the delay introduced by the extra computations.
Regarding the calculation of the number of MAGs consistent with a given PAG, related task the DAG setting, known DAG counting. aims to determine the number of DAGs within a MEC. This problem has been extensively stud- ied (He et al., 2015; Ganian et al., 2022), and can be solved with a complexity of Odd*) (Wienöbst et al., 2023). How- ever, for the analogous task of MAG counting, to the best of our knowledge, there are no relevant studies. There are two
Compared to MAGLIST, method achieves polynomial delay by transforming one circle at a time. This raises natural question: is the locally complete property of the rules necessary for achieving polynomial delay? the rules are not locally complete, then for each local transformation obtained from transforming the circles one by one a vari-

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
main challenges for generalizing DAG counting MAG counting: (1) Bi-directed edges in ancestral graphs prevent using an order to describe uncertain edge orientations, and it is unclear what mathematical tool could replace order in this context; (2) The orientation of o-> connecting different circle components can affect the orientation within a circle component. For example, consider A o-o Bo-+ C A. If there is B- + C < A, there must be A B, illustrating that the orientations within component not independent of those outside. Determining the size of the MEC in the presence of latent variables remains an open problem.
R1s If Ao B ++ D, there are two minimal possible directed paths Ti,...... AA and (D,72, A), if (a) there is an unbridged path Fi o-o....-o Fx relative to {Ti, T2} such that D o Fú, Fi..Fi,ssisk or (b) T1 is not adjacent to 72, then orient Ao- B as A <> B. Proposition 2. R17, RAs are sound for incorporating BK.
5. Related Works
Dealing with latent variables is vital in causal inference. One line is to recover latent variables and discover causal relations among observed and latent variables (Xie et al., 2022; Li et al.). Another line focuses on identifying causal relations or causal effects among observed variables with- out explicitly recovering the latent variables (Tian & Pearl, 2002; Miao et al., 2018; Lee et al., 2019; Jung et al., 2023). For example, Wang et al. (2023a) proposed a method for determining the set of possible causal effect of a variable X variable Y given MEC with latent confounders. Wang & Miao (2024) presented sound average causal effect identi- fication result with unmeasured confounders under the light- tailedness assumption. Ancestral graphs are such a kind of graphical model to characterize causal relations among ob- served variables (Richardson et al., 2002), and many studies are developed based on ancestral graphs (Cheng et al., 2022: Hu & Evans, 2024; Park et al., 2025).
4. Additional Rules for Incorporating BK
Beyond MAG listing, establishing sound and complete rules for incorporating BK into MBC is a fundamental problem in causal inference (Zhang, 2008). It is essential for deter- mining which causal relations can be identified from BK and observational data, with BK derived from interventions or human expertise. In the absence of latent variables, the canonical Meek rules are sound and complete (Meek, 1995); but it remains unresolved in the presence of latent variables.
Causality attracts extensive attention in decision tasks (Lee & Bareinboim, 2018; Ruan et 2024). Recently, a de- cision problem called avoiding undesired future (AUF) is studied, i.e., if an ML model predicts an undesired event, how to find effective actions to prevent it. Considering that causal relations are often hard to identify in practice and, even when identifiable, may not be helpful if they are un- actionable, Zhou (2023) proposed the concept of influence relation, which lies between correlation and causation, to address AUF problems (Zhou, 2022). Based on graphical models characterizing influence relations, some efforts are made for AUF problems (Qin et al., 2023; Du et al., 2024).
(a) PAG Pi
(b) PMG HI
(c) PAG P3 (d) PMG H2
Figure& 8: Examples to show the incompleteness of the pro- posed rules. Given PAG Pi in Fig. 8(a), when add BK D B as Fig. 8(b), the proposed rules (R2 R16) cannot identify C A. Given P2 in Fig. 8(c), when we add BK D + B as Fig. 8(d), the rules cannot identify A ++ B.
In Sec. 3.2, to develop a polynomial-delay MAG listing method, we propose novel orientation rules, and prove that they are sound and locally complete for incorporating sin- gleton BK into PMG compatible with local transformation. The additional rules Ru - RiG reveal the incompleteness of the existing rules, singleton BK is specific type of BK. A direct question arises to whether the rules in this paper achieve completeness for incorporating BK. To address this, we exlend our investigation to the completeness of these rules beyond the MAG listing algorithm. Unfortunately, the rules are not yet complete. We present two examples in Fig. implying the incompleteness, highlighting the need for further study. Motivated by the examples, we present two additional rules, whose soundness is ensured by Prop. 2.
6. Experiments
In this section, we evaluate the effectiveness and efficiency of the proposed MAG listing algorithm. Our method, MAGLIST-POLY, is compared with MAGLIST and BRUTE- FORCE, which are presented by Wang et al. (2024a).
We follow the experimental setup of (Wang et al., 2024a), focusing on MAG listing under varying parameters. There are two parameters: the number of vertices d and graph den- sity p- the probability of an edge between two vertices. For each combination of d and p, we generate 100 Erdös- Rénni graphs as DAGs. For each DAG, three vertices are randomly selected as latent variables to generate a MAG M charac- terizing the causal relations among the observed variables.
R17 Suppose D +C ** A++ D and C BB o A in a PMG H. if D is not adjacent to B, then orient A o B as A + B.
8

---

Polynomial- Delayy MAG Listing with Novel Locally Complete Orientation Rules
BruteForce
MagList
-aglist-poly
d=6
8=8
d=
d=
12
14
Logarithmic time (6)
2.00
&iistd MAGs
2000
130
500
0.0
0.15
0.30
0.25
6.30
0:30
0.5
0.30
0.25
0.30
0.00
0.5
0.20
0.25
0.30
0.0
0.55
0.30
0.5
0.50
0.0
0.15
0.50
025
0.50
Graph density
Figure 9: The logarithmic running time and number of listed MAGs within 3600 seconds for BRUTE- in 100 simulations under each combination of the number of vertice d {6. 8, 10, 12, 14) including 3 latent variables and the graph density P E {0.1, 0.15, 0.2, 0.25, 0.3). The vertical line represents the 95% confidence interval generated by bootstrap sampling. It is determined by the 2.5th and 97.5th percentiles of 1000 estimates from the random sample of equal size with replacement from the original sample.
DBRCE/MAGLIST/M..LLSTTTOM
We then derive the PAG P representing the MEC to which M belongs and use P as the input for the experiment.
with random strategy (RS). For RS, variable with circles is randomly selected to intervene. For ME, interventional vari- able is selected based on maximizing Hy = -E T. log 4 where I, denotes the number MAGs with i-th local struc- ture of and L denotes the total number of MAGs. Three variables are randomly selected as latent variables. We calculate the number of marks that are identified by inter- ventions in the two strategies. Repeat the process above for 10 times, the number of marks identified by ME is 98, which is more than 81 by RS. It demonstrates that the maximal entropy criterion is useful causal discovery, where the MAG listing algorithm is needed find all MAGs.
4
We implement BRUTEFORCE, MAGLIST, and MAGLIST- POLYY for each PAG, recording the number of MAGs re- turned and the time required to list them. To handle cases with extremely long computation times, we impose maxi- mum running time of 3600 seconds per experiment. If the time limit is exceeded, the process is forcibly terminated, and the MAGs listed up to that point are returned.
When d 2 10, the three methods may require more than 3600 seconds to complete. In such cases, the running time is capped at 3600 seconds. These results are excluded from the average runtime calculations since they do not accurately reflect actual execution times. The experimental results are shown in Fig. 9. When d < 10, all the methods return identical set of MAGs, demonstrating the effectiveness of MAGLIST-POLY. Moreover, MAGLIST-POLY consistently outperforms the other methods runtime, highlighting its efficiency. These results validate that the method by trans- forming the circles by one and applying the proposed rules significantly reduces computational complexity.
7. Conclusion
In this paper, we consider a specific kind of BK, singleton BK. We present the sound and locally complete orientation rules for incorporating singleton BK into PMG compatible with local transformation. Based on the rules, we propose the first polynomial-delan MAG listing algorithm. Experi- ments validate the effectiveness and efficiency. Finally, present two examples to demonstrate the incompleteness of existing rules for general BK, and further propose two rules.
Finally, we conduct an experiment using real data processed from Wang et al. (2017) consisting of 7466 measurements of the abundance of phosphoproteins and phospholipids recorded under various experimental conditions. The dataset includes both observational and interventional data. We fo- on causal discovery and apply MAG listing method to support interventional variable selection by maximal en- tropy criterion (ME) (He & Geng, 2008). ME is compared
While this paper focuses on MAG listing, we highlight the five novel proposed rules. Establishing sound and complete orientation rules for incorporating general BK remains an open problem for long time. The proposed rules this paper can
part of the complete ones in the future, which could be helpful for many areas such as causal dis- covery, causal effect estimation, and experimental designs.
9

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
Acknowledgements
the 11th Annual Conference on Uncertainty in Artificial Intelligence, pp. 87-98, 1995.
This research was supported by NSFC(624950922, Jiangsu Science Foundation Leading-edge Technology Program (BK20232003). Jiangsu Science Foundation (BK20241201). Tian-Zuo Wang was supported by National Postdoctoral Program for Innovative Talent and Xiaomi Foundation. We thank the reviewers for their helpful comments, In particular, we greatly appreciate meta-reviewer's valuable suggestion on discussing the necessity of local complete property for developing polynomial delay algorithm, which inspires our discussion in Sec. 3.4. We are also grateful Lue Tao and Zhongyi Hu for helpful discussions.
Du, W.-B., Qin, T., Wang, T.-Z., and Zhou, Z.-H. Avoiding undesired future with minimal cost in non-stationary envi- ronments. In Advances in Neural Information Processing Systems 37, pp. 135741-135769, 2024.
Ganian, R., Hamm, T., and Talvitie, T. An efficient algo- rithm for counting markov equivalent dags, Artificial Intelligence, 304:103648, 2022.
Gerhardus, A. Characterization of causal ancestral graphs for time series with latent confounders. The Annals of Statistics, 52(1):103 130, 2024.
Impact Statement
He, Y. and Geng. Z. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9:2523-2544 2008
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
He, Y., Jia, J., and Yu, B. Counting and exploring sizes of markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 16:2589 2015.
References
Ali, A. R., Richardson, T. S., Spirtes, P., and Zhang, Towards characterizing markov equivalence classes for directed acyclic graphs with latent variables. In Proceed- ings of the 21st Conference in Uncertainty in Artificial Intelligence, pp- 10-17, 2005a.
Hu, Z. and Evans, R. J. Towards standard imsets for maxi- mal ancestral graphs. Bernoulli, 3063):0026 2024.
Johnson, D. S., Yannakakis, M., and Papadimitriou, C. H. On generating all maximal independent sets. Information Processing Letters, 27(3): 19-123, 1988.
Ali, R. A., Richardson, T., Spirtes, P., and Zhang, J. Orien- tation rules for constructing markov equivalence classes of maximal ancestral graphs. Technical report, 2005b.
Jung, Y., Diaz, I., Tian, J., and Bareinboim, E. Estimating causal effects identifiable from combination of observa- tions and experiments. In Advances in Neural Information Processing Systems 36, 2023.
Andrews, B., Spirtes, P., and Cooper, G. F. On the com- pleteness of causal discovery in the presence of latent confounding with tiered background knowledge. In Pro- ceedings of the 23rd International Conference on Artifi- cial Intelligence and Statistics, pp. 4002-4011, 2020.
Kocaoglu, M. Characterization and learning of causal graphs with small conditioning sets. In Advances in Neu- ral Information Processing Systems 36, pp. 74140-74179, 2023.
Cai, R., Qiao, J., Zhang, K., Zhang, Z., and Hao, Z. Causal discovery from discrete data using hidden compact repre- sentation. In Advances in Neural Information Processing Systems 31, pp. 2666-26666 1666-2674,22 2018.
Lee, S. and Bareinboim, E. Structural causal bandits: Where to intervene? In Advances in Neural Information Pro- cessing Systems 31, pp. 2573-2583, 2018.
Lee, S., Correa, J. D., and Bareinboim, E. General identifia- bility with arbitrary surrogate experiments. In Proceed- ings of the 35th Conference on Uncertainty in Artificial Intelligence, pp. 144, 2019.
Chen, E. Y. Choi, A.. and Darwiche, A. Enumerating equiv- alence classes of bayesian networks using EC graphs. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp. 591-599, 2016.
Li, Y., Zheng, Y., Chen, G., Zhang, K., and Huang, H. Iden- tification of intermittent temporal latent process. In The 13th International Conference on Learning Representa- tions.
Cheng. D., Li, J., Liu, L., Yu, K., Le, T. D., and Liu, J. Toward unique and unbiased causal effect estimation from data with hidden variables. IEEE Transactions on Neural Networks and Learning Systems, 34(9):6108-6122) 2022.
Meek, C. Causal inference and causal explanation with background knowledge. In Proceedings of the 1 An- nual Conference on Uncertainty in Artificial Intelligence, pp. 403-410, 1995.
Chickering, D. M. A transformational characterization of equivalent bayesian network structures. P Proceedings of
10

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
Miao, W., Geng, Z.,, and Tchetgen Tchetgen, E. J. Identify- ing causal effects with proxy variables of unmeasured confounder. Biometrika, 105(4):987-993, 2018.
Wang, T.-Z., Qin, T., and Zhou, Z.-H. Sound and complete causal identification with latent variables given local back- ground knowledge. Artificial Intelligence, 2221103964 2023b.
Mooij, J. M., Magliacane, S., and Claassen, T. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 21:99:1-99:10; 2020.
Wang, T.-z., Du, W.-.,, and Zhou, Z.-H. An efficient maxi- mal ancestral graph listing algorithm. In Proceedings of the 41st International Conference on Machine Learning, pp. 50353-50378, 2024a.
Park, M. W., Arditi, A., Bareinboim, E., and Lee, S. Struc- tural causal bandits under markov equivalence. 2025.
Wang, T.-Z., Tao, L., and Zhou, Z.-H. New rules for causal identification with background knowledge. arXiv preprin! arXiv:2407. 15259, 2024b.
Pearl, Causality, Cambridge University Press, 2009.
Qin, T., Wang. T.-Z., and Zhou, Z.-H. Rehearsal learning for avoiding undesired future. In Advances Neural Information Processing Systems 36, pp. 80517-80542, 2023.
Wang, Y., Solus, L.,, Yang, K., and Uhler, C. Permutation- based causal inference algorithms with interventions. In Advances in Neural Information Processing Systems 30, pp. 5824-5833 2017.
Richardson, T., Spirtes, P., al. Ancestral graph markov models. The Annals of Statistics, 30(4):922-1030, 2002.
Wienöbst, M., Luttermann, M., Bannach, M., and Liskiewicz, M. Efficient enumeration of markov equiva- lent dags, arXiv preprint arXiv:2301.122111 2023.
Ruan, K., Zhang, J., Di, X., and Bareinboim, E. Causal imitation for markov decision processes: partial identi- fication approach. Advances in Neural Information Pro- cessing Systems 37, pp. 87592-87620, 2024.
Xie, F., Huang, B., Chen, Z., He, Y., Geng, 2., and Zhang, K. Identification of linear non-gaussian latent hierarchical structure. In Proceedings of the 39th International Con- ference on Machine Learning, pp. 24370-24387, 2022.
Runge, J., Bathiany, S.. Bollt, E., Camps- Valls, G., Coumou, D., Deyle, E., Glymour, C., Kretschmer, M., Mahecha, M. D., Muñoz-Marí, J., et al. Inferring causation from time series in earth system sciences. Nature communica- tions, 10(1):2555) 2019.
Zhang, J. On the completeness of orientation rules for causal discovery in the presence latent confounders and selection bias. Artificial Intelligence, 172(16-17): 1873-1896, 2008
Zhang, K. and Hyvärinen, A. On the identifiability of the post-nonlinear causal model. In Proceedings of the 25th Conference on Uncertainty Artificial Intelligence, pp- 647-655, 2009.
Shimizu, S., Hoyer, P. O., Hyvärinen, A., and Kerminen, A. J. A linear non non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7: 2003-2030, 2006.
Zhou, Z.-H. Rehearsal: learning from prediction to decision. Frontiers of Computer Science, 16(4):164352, 2022.
Spirtes, P.. Glymour, C. N., and Scheines, R. Causation, prediction, and search. MIT Press, 2000.
Zhou, Z.HH. Rehearsal: learning from prediction to decision.
Tian, J. and Pearl, J. A general identification condition for causal effects. In Proceedings of the 18th AAAI Confer- ence on Artificial Intelligence, pp. 567-573, 2002.
Keynote at the CCF Conference on AI, Urumqi, China, 2023.
Venkateswaran, A. and Perkovic, E. Towards complete causal explanation with expert knowledge. arXiv preprint arXiv:2407.07338, 2024.
Wang, R. and Miao, W. satreme-based causal effect learn- ing with endogenous exposures and light-tailed error. arXiv preprint ar arXiv:2408.06211. 2024.
Wang, T.-Z., Qin, T., and Zhou, Z.H. Estimating possi- ble causal effects with latent variables via adjustment. In Proceedings of the 40th International Conference on Machine Learning, pp. 36308-3633, 2023a.

---

Polynomial-Dekee MAG Listing with Novel Locally Complete Orientation Rules
A. Existing Orientation Rules
In this section, we show the existing orientation rules. Zhang (2008) proposed the sound and complete rules Ri- Rio for causal discovery with observational data in the presence of latent variables. R12 is proposed by Wang et al. (2024b). R13 and Rnew are proposed by Venkateswaran & Perkovic (2024). Since in this paper we only focus on the orientation rules for incorporating singleton BK, in which case Rnew is not utilized, we do not denote it by rule with number. R11 is proposed by Wang et al. (2024b) and Venkateswaran & Perkovic (2024) independently.
R1: If A+ B o+ R, and A and R are not adjacent, then orient the triple as A B - R.
R2: If A + B+ R or A B > R2 and A * R. then orient A # R as A+ R.
Ry: If A+ B + H2 A +o Doe o+ R. A and R are not adjacent, and D &o B, then orient D A-o B as D+ B.
R4: If (K,..., A. B, R) is discriminating path between K and R for B, and B o-s R: then if B E Sepset(K, K, R), orient B o- R as B + Ri otherwise orient the triple (A, B, R2) as A ++ B ++ R.
R3: For every (remaining) A o-o R, if there is an uncovered circle path = (A, B. ... ,, Rt) between A and R s.t.
A, D are not adjacent and B, R are not adjacent, then orient A a-o R and every edge on p as undirected edges.
Rs: If - B c-+ R (A and R may or may not be adjacent), then orient B o-+ R as B +R.
Ry: If A B o-+ R, and A, R are not adjacent, then orient B a R as B R.
Rg: If A + B > R. and Ao- R, orient Ao+ R as A + R.
Rg: If Ao R. and p- = (A, B, D,... ....., R) is an uncovered possible directed path from A to such that R and B are not adjacent, then orient Ao- R as A- + R.
R1o: Suppose Ao- R, B- > R <- D. pı is an uncovered possible directed path from A to B, and p2 is an uncovered possible directed path from A to D. Let U be the vertex adjacent to A on p1 (U could be B), and W be the vertex adjacent to A on P2 (W could be D). If U and W are distinct, and are not adjacent, then orient Ao R as A + R.
R1I: Suppose an edge Ao+ B in a PMG H. Let SA {V E V(H) A in H [A). in H there is an uncovered possible directed path (A, B. ... ,K), where K E Anc(SA. H), then orient A a-* B as A +.B.
R12: Suppose an edge A o-* B in a PMG H. Let S = (V E V(H)IV ++ A in H) U (A). If there is an unbridged path (KI,..., Km,) relative to A in H [S] and for every vertex K; E { Km), there exists an uncovered possible directed path (A, B, .............................. K,) (B jf K2), then orient A a-e B as A B+B.
Suppoee D++ C ++ A *+ D and C' B # A in a PMG H. if D is not adjacent to B, then orient Ac+ as A +B
Rnew: If (Qo. Q1.... Qx(= A), B) is an almost discriminating path for A in PMG H and there is A o B in H,
then orient o B as > B.
B. Some Definitions
The circle component of graph G is the subgraph of G that only remains all the vertices and all the circle edges. A graph is chordal if any cycle with more than four vertices has a chord that connects two vertices.
Next, we introduce PMG compatible with local transformation in Def. 4 proposed by Wang et al. (2024a). A PMG compatible with local transformation is initially introduced to represent the PMGs, which are obtained from incorporating local BK into PAGs and using the orientation rules to soundly and completely update the PMGs.
Definition 4. A PMG M is called PMG compatible with local transformation if it satisfies the four conditions:
(Chordal) The circle component in M is chordal.
(Balance) For any three vertices A, B, C' in M, if A++ Bo* C, then there is an edge between A and C' with an arrowhead at C, namely, A+ C. Furthermore, if the edge between A and is A + B, then the edge between A and C' is either A + C' or Ac- C' (i.e., it is not A ++ C). And if A BoB a C, then A is adjacent to C. Furthermore, if A BoB o-o C, then A -oC; if A Bo C, then A C or Ao C.
12

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
(Complete) For each circle at A on A c-* B in M, there exist MAGs M1 and M2 consistent with M with A < E(M1) and A B E E(M2).
(Constructive) We can always obtain MAG consistent with M by transforming -o 0/0>> to - and transforming the circle component into a DAG without new unshielded colliders.
C. The Realization Process of MAGLIST
Here, we briefly introduce the MAG listing method MAGLIST proposed by Wang et al. (2024a). All the figures and illustrations directly refer to Wang et al. (2024a). We guide the readers to Wang et al. (2024a) for details.
MAGLIST is a recursive method. In each round, they select one vertex with circles, denoted by X. They enumerate all the circles at X simultaneously (As discussed in Sec. 3.1, this part leads to the undesired exponential delay), which is called local structures of X. And they present the graphical conditions to determine whether the local structure valid, i.e. whether there is a MAG consistent with the given PAG P and this local structure. For each valid local structure, the local structure can be seen as a local BK. thus they use the established sound and complete orientation rules to incorporae the local BK. The implementation example of MAGLIST in the format of a search tree is shown in Fig. 10. The graph in the root node denotes PAG P. They aim to list all the MAGs consistent with P. In the first round, they consider the local structures of A. According to their result for determining the valid local structures, they can determine that there are six valid local structures of A, and thus obtain six PMGs on the second line according to the marks implied by the local structures of A. Then they update these six graphs using the proposed rules and obtain the graphs on the third line. After the local transformation and the updates with rules, the implementation in the first round completes. the second round, they further consider the local structures of B, and based on the valid local structures of B, they update the graph with the proposed rules. There are some PMGs without any circles, which are MAGs consistent with P. They shade these graphs with green color. For the unshaded graphs, they updated in the third round by considering the local structures of C. Some branches are omitted (those unshaded but unexpanded) for brevity. The algorithm stops until there are no new unshaded leafs.
00
D0
C
oB
BB
oB
oB
oB
local transformation:
00
D
D
D
D
Round 1
B
B
B
B
update with rules:
8
8
Round
B C
C
D
D
A
B
B
B
B
Round 3
Figure 10: A realization process of MAGLIST. The graph in the root node denotes a PAG P. The graphs in the firt//scondd/hirr round are obtained from the previous round by introducing the valid local structures of A/BIC. There are two parts in a round: introduce the valid local structures and update the graph using the proposed orientation rules. The two parts are separately shown for only the first round. The shaded graphs denote the MAGS that are output by MAGLIST.
13

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
D. Proofs
D.I. Proof of Proposition 1
Proof. For R14, when the conditions in R1 hold, suppose X ++ B for contradiction. Following Def. 3, it is direct that if ii prior to B relative to X, then there exists series of vertices Jo T1,, ,J--1, J+(= B), 2 1 such that for any Jes J one of the three conditions in Def. 3 holds. When X o+ [+(= B) is oriented as X <++]([= B), if the first condition of Def. 3 holds for J{-1 and Jz, there is Jt-1 - J2, thus X o-* J--1
be oriented X f= by R2; if the second condition of Def. 3 holds for J and Jr, X o- Jt-1 can be oriented as X h+J,-1 by Ru1; if the third condition of Def. 3 holds for J--1 and Jr X o-+ J can be oriented as X <++ by R12. Due to the soundness of R2, R11, R12, if there is B) and one of the three conditions in Def. 3 holds for J--1 and Jr, there must be X <+J+-1- Recursively, we
X (= can conclude that there must be X (= 71). Similarly, we can also conclude that there is X T- In this case, if T1 is not adjacent to T2, there is a new unshielded collider Ti + X ++7, relative to H. contradiction. If there is an uncovered path Ti foFi C-O... o-o F T2 such that there X c- F; for every F,, 1 S S Consider the structure comprised of Ti, Fi, F2, X, where T1 is not adjacent to F3 and there is + X. According to R13, there is F1 F2 in any MAG F& - T2 oriented. Due to the ancestral property and T2++ X, there is Fa-1* +- X in M. Hence there is an additional unshielded collider F X <= in M relative to H, which contradicts with the fact that M is consistent with P. Hence X ++ B is impossible.
consistent with H and BK. Using R1, there is Fi + F22
For R1s suppose A ++ R for contradiction. There is A B + R ++ A, where ancestral property will always be violated no matter is -> B or A B.
Rio directly follows the ancestral property that there cannot be an arrowhead into an undirected edge.
D.2. Proof of Theorem 1
We first introduce some existing results, which support the proof of the main theorem. + denotes concatenation of paths.
Lemma (Wang et al. (2024a)). Consider a PMG M compatible with local transformation. If there a possible directed path A to B in Ml, then there is a minimal possible directed path from A to B in M.
Definition 5 (Bridged relative to V in H, Wang et al. 2023b). Let H be a partial mixed graph. Let G denote a subgraph of H induced by a of vertices V. Given set of vertices V' in H that is disjoint of V, two vertices A and B in the circle component of G are bridged relative to V in each minimal circle path from to B in G as Vo(= A)se V, B), there exists one vertex Vz, 0 I S n, such that Fi S F,+1,0 0 S i S s
and Fit1 S F,, S - 1, where F. (V E V V x- V; in H). Evidently, both case A = B and case that A and B are not connected in the circle component are the trivial cases that A and B in G are bridged relative to V'. Further, G is bridged relative to V in H if any two vertices in the circle component of G are bridged relative to V'.
Lemma 2 (Wang et al. (2024a)). Suppose M a PMG compatible with local transformation. Given a set of vertices C (VIX a+ V in M), let Z = (V E VMM)V = X,, or there is V -o...o V' -oX in MI and V & C). There exists a VV MAG M consistent with MI with X ++V for VV E and X +V for VV (V X o V in Ml C if and only if
(1) PossDe(Z,M[[CN) n Pa(C. = 0:
(2) the subgraph M[C] of MI induced by C is a complete graph;
(3) M[PossDe(Z, MI[-C]) Z is bridged relative to C CUZ Z in Ml;
(4) either [x) or (V E V(M))V X or V E C} is empty.
Next, we first present some results.
Proposition 3. Denote a PMG compatible with local transformation by M. Suppose there is a set of vertices V C V(M) and a minimal circle path p in MI[-V'] which is not bridged relative to V as Def. 5. If no variables in Vi, Vm are ancestors of V' in M. and any two vertices C1, C2 E V are adjacent in M. then there must be at least one sub-path of p which is an unbridged path relative to V' as Def. 1.
Proof. According to Def. 5, suppose there is sub-path of as P1 (Vi,... Vnn), where C1 E F1 and C2 E FmA where F, = (V E V' V to V in M.. Without loss of generality, suppose p1 is minimal sub-path such that pt not
14

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
bridged relative to V", iie., for any proper sub-path of P1. it bridged relative to V'. Note this supposition is reasonable, since if there is a proper sub-path of pi which is not bridged relative to V', then we consider this path instead of pr. Note for any vertex V; E {V2. V3.. Vm J. there cannot be C + V,, for otherwise there must be C ++++ VV E {Vi, V2, V...... Vm due to R1 and the balance property of M, contradicting C1 E F1; there cannot be C₁ +- Vi in M., for otherwise there is C1 E Fi. such that the subpath of from V2 to Vm is not bridged relative to V', contradicting with the supposition. Hence if V; is adjacent to C1, there must be C1 V.
Next we consider the adjacency of each vertex and C1. Suppose V2 is adjacent to C1. We consider the edge. Note that has been proved be as C1 V.2 We first prove that the edge cannot be C₁ - V/2. Suppose there is C₁ 122 Due to V/2 o-o Vg, and we have proven that there is not C1+> V/3 or C1 # V/3 in M., there must be C1 V/3 in M due to the balance and complete property. Repeatedly, we conclude that there is Ci Vn. In this case there cannot be C2 - Vn in M, for otherwise there is C2 * Vm by Rs. contradicting with C22 E Fv... Hence there cannot be C1 - V2. We then prove the impossibility of C o- Vz2. Consider V, a-o V/2 -oC and C₁ E Fvv, there is V1 0-0 1/2 -oC * V1, the balance property of M is not satisfied, contradiction. Thus C1 o is impossible. According to the condition, there is no C1 + V2 since no vertex in p are ancestors of V'. Hence there cannot be Ci - / /-/ V2. We conclude that C1 is not adjacent to V/2 We then prove that C1 is not adjacent to V/.. If they are adjacent, according to the proof above, the edge is as C₁ V3. Note there is sub-structure comprised of C1, V1, V2,, V'3 such that con-cosseee vertices not adjacent except an edge between C1 and V3. In this case either R3 is triggered to transform all the edges into undirected edges, or there is an unshielded collider Vio+ C1 V due to V1 o-o V/2 a-o V/3. For the former case, there is V1= - V2 oriented, contradiction. For the latter case, there is Ci + Vi oriented by Rg, contradicting with C E Fvz. Hence C1 is not adjacent to V/. Recursively, we can prove that C1 is not adjacent to V22 Vg..... Vn. Similarly, we can prove that C2 is not adjacent to Vm-1, V 2, V1.
Further, since C1 is adjacent to C2. we consider the sub- structree comprised of C1, Vi, V2,..., Vn, C2. There must be a collider in this structure, for otherwise all the edges are oriented as undirected edges by Rs. Consider V1 a-o ... Vm. there must be a collider as C2* G1 1oVi or C1 C2 <o Suppose there is only C2+ C1 toV1, in this case, there must be C22 - C1 + V1 by Rg. contradicting with C1 E Fvi- Hence there must be both +2+-+ Ci <oV, and C1+ C2 Vo. Thus there is Vi-> C1 ++ C2 foFm
We conclude there is a minimal path Cj < o-o o-o o C2 except for an edge C + C2 in M, where C₁ C2 E V thus p1 is an unbridged path relative to V
Lemma 3. Consider a vertex X in PMG MI compatible with local transformation. Suppose we obtain PMG H by introducing non- non-empty singleton BK regarding X and using the proposed orientation rules (R1 R1sh. IfC = [+ (VIV + X in M), then there exists a MAG M consistent with M with X ++V for AV E C and X +V for VV (V X o+ V in M)
X in HYM
Proof. It suffices to show that the set C satisfies the four conditions in Lemma 2, then we conclude the desired result according to Lemma 2.
We first prove that either Z ZX or (V E V(M) X in or V E C) is empty. Suppose both Z\(X} and {V E (MI)|V>+ X in M or E C} are not empty. There is Z -oX and C' X in H. which is impossible due to Rio-
Then, we prove that the subgraph M[[] of M induced by Cs a complete graph. According to the soundness of the rules, the additional arrowheads at X in H relative to MI are from either BK or the orientation rules, and the rules sound. Hence, if M [C is not complete, there must be additional unshielded colliders at X in any MAGs consistent with BK relative to M. Thus there are not MAGs consistent with M. and BK, violating the correctness of BK.
Then, we prove that PossDe
CI) n Pa(C, M) = 0. Suppose F E Poss Z, MI [M[-Cp CI) n Pa M). Suppose there is F + C1 in M, where C1 E C. According to the BK, there is C1++ X. If F is adjacent to X in M, as F E PossDeeZ, IZ, Mi[ CC). there cannot be X F=F in H. If there is X F in H, the structure X F + Ci+> X violates the ancestral property. If there is X a+ F' in H. there must be X a+ F in M, F > C+++ X a+ F in M violates the balance property of M.. Hence F cannot be adjacent to X. However, if F is not adjacent to X in M, according Lemma 1, there is minimal possible directed path from X to F in M and F + Ci++ X, which is impossible since R1 would transform the circle at X in the minimal possible directed path to an arrowhead. Hence that F is adjacent to X is also impossible. Thus there is PossDe(Z, MJ) n Pa (C, M1) = 0.
Finally, we prove that M PossDe M[-CI) [Z] is bridged relative to CUZ in M. Suppose M PossDee, (Z, ([, M[- Z) is not bridged relative to C U Z in M. for contradiction. We have proven that either Z (X) or C is an empty set. Suppose
15

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
[X] is non-empty. Then there must be two vertices Z1: Zg E Z such that F1 o-0 F2 o-o... FE, k 2 is not bridged relative (2,, 32). We omit the tedious proof for that Z1 must be adjacent to Zz. The main idea is, according to the definition of Z, if there is path Z -0...... -06o- -o... -oX (or swap Zi and Zg in the path), then we could prove that the sub-structure comprised of Z1 a- Fi o-o... o-o F& o+ Ze and a minimal tail-circle path Z1 - -oZz between Z1 and Zg in M. will never appear due to the balance and complete property of M: if there is not such a path Z -o... = -Q... -oX,, then there must be a path 21 -o... -o. a-.... c- Zz, we could prove that for each vertex between X and Zz in the path, it must be adjacent to Z1, for otherwise the balance and complete property of MI is not fulfilled. Additionally, there cannot be an arrowhead into Z1, Zz, for otherwise the - edges will be transformed to + in MI due to ancestral property. Hence, if there are Z1, Zz Z such that F1 o-o F2 a-0 o-0 Fk, k 2 2 is not bridged relative to [Z1, Z2), according to Def. 5 and Prop. 3, there are Zi ++ Zz, which is impossible since there cannot be arrowhead into Z1, Zz We conclude the impossibility of Z (X) # 0.
In the following it suffices to consider the case that C' is non-empty. Suppose there are two vertices C₁ C2 E C such that
pl: : Fi o-o F2 0.......000 Fs. k 2 2 is not bridged relative to {C1, C2). We have proved that for any two vertices C2, C2 E C
they are adjacent. Additionally, every vertex V in pi cannot be an ancestor of C1 in MI, for otherwise there must be V E C
when C E C according to R2 or R11- Similarly, we conclude V is not an ancestor of Cz. Hence, according to Def. 5 and
Prop. 3, there exists an unbridged path p F1 o-o F2 o-0 o-0 Fm 2 2 relative to (C1, C2), where C1, C2 C and
there is an edge C1 ++ C2-
Due to the soundness of the orientation rules and the correctness of BK, for any MAG M consistent with M and BK, there is C X C+22 in M. Since there is C₁ Fo a-o ... o-o Fm a- C2 in M. it is evident that VF E (F), FF. J. F is an ancestor of either C1 or C2 in the corresponding path of p in M.
Next, we first prove that X cannot be adjacent to any vertex in F1,..., Fm Without loss of generality, suppose F; is adjacent X. Hence, according to Prop. 3, P: is not adjacent to C2 (if = 1, then we consider C1 instead of C2). Hence there must be C2++ X + F; in M, for otherwise there are new unshielded colliders at X in M relative to M. However, we have proven that F; is an ancestor of either C1 or C2 in the corresponding path of p in M. Given C+ X + F;->... -.... - C, where C E {C1, C2]. the ancestral property are not fulfilled, which contradicts with the correct BK assumption. We thus conclude that X cannot be adjacent to any vertex in Fi, "", Fm
Next, due to F1 E PossDe (Z, [ Z. according to Lemma 1, there is minimal possible directed path p' (X, Ki.... K(-1, K2(= F t 2 1 from X to F1 in M[PossDe M[-C]]] Since p' is a minimal possible directed path, and X is not adjacent to F2, (X, K2) + p" is minimal possible directed path from X to F2, where p" is a sub-pat of p|K1, (- Fi)
(F1, F2). Hence, there is a minimal possible directed path from X to F2, where Ki is the vertex adjacent to X in the path. Similarly, we could prove that for any vertex F E {F1, ... F. there is minimal possible directed path from X to F, where K2 is the vertex adjacent to X in the path. In this case, R11 should be triggered to orient X +- K2, that is K1 E C, contradicting with K₁ E PessDe (Z, M[ CC).
Hence, the four conditions in Lemma 2 are satisfied. We conclude the desired result according to Lemma 2.
Lemma 4. Consider a vertex X in PMG M compatible with local transformation. Suppose we obtain PMG H by introducing non-emply singleton BK regarding X and using the proposed orientation rules (R) - Rie). If there is an edge X x T in H, then there is a MAG M consistent with M and BK such that there is X < in M.
Proof. According to Lemma 3, we could always obtain a MAG M with X ++V for VV E C and X +V for VV E (V) X a V in M) ( C by the procedure in the proof of Lemma 2. Consider the edge X a+ T in H. We will prove that there is a MAG M with an edge X T consistent with M. and the BK. Suppose we can obtain a PMG H' from H by introducing
X < +T with the orientation rules R2, R11, R12, R16- Note here when we apply R16, we only consider the case that if there is A+ B o- R, then orient B o- R as B +- R, as here we only introduce an additional arrowhead at X and care about the identification of the marks at X.
Denote C' = (VIV+> X in H'M (VVVVVV> X in MJ. Evidently, we can divide C' into two disjoint sets C₁ and C2, where C₁ denotes the set of vertices C in Lemma 3, and C2 denotes the set of vertices {VIV>> X in H' X in H). As we introduce X + based on H, C2 is not empty. It suffices to show that there is MAG M consistent with MI such that C' = [VIV>>>X X in MMMVVV** X in M). Next, we adopt the similar ideas with Lemma 3. We will prove that C' fulfills the four conditions in Lemma 2. Note that the proof here is quite different from that of Lemma 3, as here there no correct BK assumption when we further incorporate X .T Note according to the definition of Z that
16

---

Polynomial-Deke MAG Listing with Novel Locally Complete Orientation Rules
Z = (V V(M)VV = X, or there is V -o... V -oX in M and V & C), Z relies on C. When we consider C', to distinguish them, we denote Z'= {V E V(M)VV = X, or there is V -o... -o V -oX in M and V & C*)
We first prove that either ) or {V E VIV+> X in M or V E C'} is empty. Suppose both Z' Z'XX) and {V e viV= X in M or or E } are not empty. Suppose in H there is Z -oX. According to Lemma 3, there is not a vertex C' E C1 such that there is C++ X in H. It suffices to consider C' E C2. In this case there must be X a-s C in H. C must be adjacent to Z, for otherwise there is X +CC in H. due to R7, contradiction. In this case, there is + X in H' due to R16. thus Z E Cg. There cannot be Z E Z', contradiction. Hence, for any vertex V with an edge V -oX in H. there is V X in H'. In this case Z" Z' { = 0. contradiction. We get the desired result.
Then, we will prove that PossDe(Z', ; M[[C'')nPa(C'' M) = 0. Suppose F E PossDe (MI M). Evidently C' is not empty, thus Z" } is empty and F E PossDe(X, X,
n Pa(C", , M). Suppose there is C' E C' such that there is F + C. According to the proof of Lemma 3, C' & C1, thus there is C E C2. Due to F E PossDe(X, M[-C
there is a minimal possible directed path p from X to F in M. Suppose = (X, F1, ... [=((= F)), k 2 1. As F E PossDe( X,
(AAIDeeX,MMCC))) M(CC")) and M satisfies the complete property, p is either X + ... * F3 in M or X o+ Fi ... F& in M.. For the former case, there cannot be X c- C in M., for otherwise the complete property of MI is violated since there cannot be X +*C in any MAGS consistent with MI given F&- + C. Thus there must be X + C in M, which contradicts with C' E C2. For the latter case, since C E C2, if there is X o++ F1 in H, X c-+ F1 should be oriented as X ++ by R2 or R11, which implies that Fi E C2, contradicting with Fi E PossDe (Z', MI -()) If there is X Fi in H, there must be Fi-1 + C, F + C, X + C' in H triggered by R15 due to Fi + C' (we omit the details), contradicting with C' E C2. Hence F' E PossDe(Z' (z', MM-C') n Pa( C', M) is impossible.
Then, we prove that the subgraph M(C') is a complete graph. According to the proof of Lemma 3, for any vertex G, C₁, C1 are adjacent C2; for any vertex C E C₁ and C22 E Czz, C1 are adjacent to C22, for otherwise there is X- C2 in H due to C + X, contradicting with C2 C2 which means that there is X o- C2 in H.
We then prove that for C1, C2 E C2. it is impossible that C₁ is not adjacent to C2. Note X o+ T is firstly oriented as X T+T based on H. Since we only use the orientation rules R2, R21, R12. R16 to obtain H' based on H, the other additional arrowheads at X are only triggered by R2, R11, R We first consider the case that C1, C2 * T. We consider which rules triggers the transformation of X a- C1 to X ++C1. For simplicity, we say vertex C is triggered by rule R, if R, triggers the transformation of X o-e C' to X C.C. It is impossible that there is C1 -oX o- C2 in H, for otherwise there is C1 X C2 in H due to Ry. Note after we orient X o-* T as X + we only apply R2, R11, R12. R16, in which process there are no tails introduced. Hence if there is C1 -o.X in H', there must be C1 -oX in H. Similarly, if there is C2 -oX in H!', there must be C2 -oX in H. Thus there is Cj -oX o-C2 in H, contradiction. Hence it is impossible that both C1, C2 are triggered by R1G-
If C1 is triggered by RR16 and C2 is triggered by R2, R11, R12- As we do not introduce new tails in H' relative to H, there is Ci -ox. Since C₁ is not adjacent to C2. hence there cannot be C2 # X, contradiction. Hence neither of C₁ C2 could be triggered by R16.
Note if vertex V is triggered by R16, then an edge X V is oriented as X <- V. Note this edge will not be necessary part of the sub-structures where R2, R11, Ry2 are triggered, because the necessary arrowhead at X that activates R2, R11, R12 is on an edge in the form of Xo- V. Hence, in the following, we only need to consider the transformation triggered by R2, R11, R12. Then, according to Def. 3, if X ++T triggers orienting X a- T as X ++1" by R2, R1I, or R12, then 7" is prior to T. Recursively, we conclude that either (a) C1 and C2 are prior to T or (b) C2 or C2 is T. If both C1 and C2 are prior to T, T,C, and C2 are not adjacent, then according to R14, there is X + T in H. contradicting with o- T in H.
Then we consider the case that one of C1, C2 is T. Without loss of generality, suppose C1= =. R2, R11 and R12 cannot trigger a transformation of X o-* C2 to X +2 due to X c+C, where C1 and C2 are not adjacent. If C2 is triggered by R1e, then there is X o-C2 in H, in which case there cannot be X c- T) in H and C₁ is not adjacent to Cz. contradiction.
Till now, we have proven the impossibility of all possible cases that C, is triggered by R2, R11 R12, Rio and C2 is triggered by R2, R11, R12, R16. Hence MC] is a complete graph.
In the following we will prove that M|PossDe M[[CC]) [Z]] is bridged relative to C' U Z' in M. Suppose M|PossDee (Z', (C] (Z) is not bridged relative to C' U Z' in M. for contradiction. Based on the similar proof process as
that for Lemma 3. according to Def. 5 and Prop. 3, there must exist an unbridged path p = Fi a-o F2 o-o o-0 F m 2 2
17

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
relative to {C1, C2), where C2 C2
We then prove that X cannot be adjacent to any vertex in Fi.... Fmm Suppose X is not adjacent to Fi,... ... ,i, but adjacent to F,, i 2 2. There is a sub-structure comprised X, Fi. Fi, X, where any two non non-consecutive vertices are not adjacent. Note there must be a collider in this sub- sut-sstuuctue and Fi a-o F/2 o-o... o-o F, in M. If there is not collider C1+> X F; in M, there will be only a collider F1 - C1 < F; due to Rg, contradicting with C1 E C'. Hence there is X F+ in MI, contradicting with F; E PossDe(Z', - Zz. Hence X is adjacent to some vertex in F1, F'.. then X is adjacent to any vertex in F.,
Here we consider the case that X is adjacent to Fi,.... FF.- According to the proof of Lemma 3, we have proven the impossibility of Ci C2 C₁ If 1 E C1 and C2 E C2, considering C₁ is not adjacent to F2, there must be X - F2 and Fi > F22 .... F............................... Fm + C2 in H according to R13- Thus there is X - C2 according to Rs, contradicting with X o- C2 in H. We then consider the case that C₁, C2 E C2. Due to the complete graph MI[C", C1 is adjacent to C2. We consider the sub-structure comprised of C1, Fi.... .... C2, where any two non-consecutive vertices are not adjacent except for an edge connecting Cj and C2. In this case, if there is no unshielded collider +i+ C1 c++2, there must be F' - C2 f- Ci in MI by Rg, which contradicts with C2 E Fm. Hence, there is an unshielded collier Fi++ C1 c+0² in M. Similarly, there is an unshielded collider + C2 + in Ml. Hence there is C1 + C2 in M. In the following, we will prove the impossibility of C1 ++ C2 in M.
We first consider the case C1 T C2= = T. Without loss of generality, suppose C1 = T. Consider the transformation series is as Jo(= 7), J1, .... J/(= C2), 1 2 2, i.e, when orienting X o-t T as X f the orientation of X o-* Ji triggers the transformation of X o- Jj to X J.J,, by R2, R11, R12. Next, we will prove the impossibility of C1 ++ C2. We first consider the edge connecting Jo and J1. When X o-* Jg oriented as X <+Jo, X o-* J1 is oriented as X <+ by R2, R1, R12 (there are arrowheads at C2 thus R1s cannot trigger the transformation, and we have proven before that Rio will not trigger the transformation of R2, R11 R12). We discuss the rules that trigger the orientation. If it is R2, then there must be J1 - Jo in M. it is R11, then there must J1 -100> Jo in MI (we omit some details here, which can be proved according to the balance and completer property of M.. If it is R12, then there must be JI Ju in M. Hence, there is JI - Jo or Jiaz Jo in MI. Similarly, we could prove that there is J2 + JI or J2oZ J1. As MM[['] is a complete graph, Jo must be adjacent to J2. According to the balance property and the rules, there can only be J22 - Jo or J20-> Jo in M.. Recursively, for any vertex Jj, S i S t, we could prove that there is Jj + Jo or Jio- Jo in M. Hence there is ( C2) - Jo(= T) or [= C2)0 Jo(=11 T), which contradicts with C2 + T in M. Hence C1 T or C2 = T is impossible.
If + T and C22 + T, then there is an unbridged path (Fi,-.., .i) relative to (Ci, C2) such that X a-t F; for every F,, 1 S S m. According to R14, there should be X + T in H, contradicts with X a T in H. Hence, X cannot be adjacent to any vertex in Fi,'.,, Fm
Next, due to Fi E PossDe(Z', M[-C')). according to Lemma 1, there is a minimal possible directed path p' (X, K,... K1-1,
K2(= Fi)).t 2 from X to Fi in M|PossDeeZZ MM[ Since p' is a minimal possible di- rected path, and X is not adjacent to F2. (X, K1) Pp" is a minimal possible directed path from X to F2, where p" is a sub-path of p|K,, K2(= Fi) (F1, F2). Hence, there is a minimal possible directed path from X to F2, where K₃ is the vertex adjacent to X in the path. Similarly, we could prove that for any vertex F E [F...... }. there is a minimal possible directed path from X to F, where K₁ is the vertex adjacent to X in the path. In this case, R12 should be triggered to orient X < K, that is K2 E C², contradicting with K₁ E PossDe Z M C")).
Hence, we have proven that the four conditions in Lemma are satisfied. We conclude the desired result according to Lemma 2. There is MAG M consistent with M and BK such that there is X ++T in M.
Proof of Theorem 1. Combining Lemma 3 and Lemma 4, we conclude the desired result in Theorem 1.
D.3. Proof of Theorem 2
Proof. For MAGLIST- and MAGLIST, they have the same outer loop that selects vertex with circles and transforms all the circles at this vertex. The only difference is, for MAGLIST, in each outer loop they enumerate all possible local structures of the selected vertex and determine the validity of each local structure, while for MAGLIST-POLY. there is an inner loop as shown in Function LOCALTRANSFORE of Alg. 1 to find all valid local structures. We will get the desired result by proving that MAGLIST-POO POL-OOL and MAGLIST obtain the same set of PMGs after each round of outer loop. Suppose
18

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
in this outer loop, the input graph is PMG MI compatible with local transformation. Without loss of generality, suppose in this round, we select vertex X and transform the circles at X. We consider MAGILIST-POLY in the following. We will prove (a) by the inner loop MAGLIST-POLY can find all the valid local structures of X in the form of PMGs on Line 17 of Alg. 1, where a valid local structure of X implies that there is a MAG M consistent with M such that M has this local structure of X, (b) the obtained graphs on Line 17 of Alg. 1 are PMGs compatible with local transformation.
(a) Denote C S (VIV +o X in M.. For a given set C, it dictates a local structure of X based on MI such that the circle at X on an edge between X and V is oriented as an arrowhead if V C and the circle is oriented as a tail if V & C. Hence, we use {C) ours and Hocal to represent the local structures obtained by LOCALTRANSFORM and Wang et al. (2024a), respectively. In the following we will prove that Jours
set
Local-
Since M. is a PMG compatible with local transformation, MI fulfills the complete condition, i.e., for every circle at X, it could be an arrowhead in a MAG M₁ consistent with M and a tail in a MAG M2 consistent with M. Hence it is valid to enumerate it as an arrowhead and a tail, and the proposed rules are sound to incorporate singleton BK into M. according to Prop. 1. Without loss of generality, suppose we first enumerate X o V1 as X <+V1 and obtain an updated graph Hı using the proposed orientation rules. If there are circles at X in H1, suppose it is X o-* V22 without loss of generality, as the proposed rules are locally complete for incorporating singleton BK into a PMG compatible with local transformation, there must be MAGS consistent with H1 with X <~V2 V/2 and X -V2. Hence it is valid to enumerate the circle at X on the edge between X and 1/2 as an arrowhead and a tail, and the proposed rules are also sound to incorporate singleton BK into M. Suppose we enumerate X o-+ 1/2 as X + and obtain an updated graph H2 using the proposed orientation rules. Essentially, the process above is that we incorporate the singleton BK Vi + X < into M. Due to the locally completeness of the proposed rules, it is also valid to enumerate another circle at X as an arrowhead and tail. Repeat the process above, for all the obtained local structures, it must be a valid local structure since the rules are locally complete, thus {C)ours S Hooal-
For a valid local structure represented by C in {C]local, without loss of generality, suppose C = (V1, V/2 V.J. Consider we enumerate the circles at X. In the first round, when we enumerate X o-* V1 as X <+Vi, as the rules are sound, we will not introduce a mark which contradicts with the valid local structure dictated by C. Hence, there is either X o-* 1/2 or X V obtained by using the orientation rules. For the former case, we continue considering the circle at X on the edge between X and V2. By enumerating it as an arrowhead and a tail, we will obtain a local structure with will not introduce mark which contradicts with the valid
X V- And since the rules are sound and locally complete, local structures dictated by C. For the later case, there have been X V2 Repeat the process above for V1, V2,.... Va. LOCALTRANSFORG can find a local structure represented by C. Thus there is {C]ours 2 {C]
Hence there is {Coours set [C]ooett- That implies that LOCALTRANSFORM can find all and only the valid local structures of X.
(b) In the process of updating the graph based on singleton BK regarding X with the proposed orientation rules, the rules R1 Ris- And after transforming all the circles at X, essentially, we introduce the local BK regarding X. Note the rules used in MAGLIST are a proper subset of R₁ R16, and Wang et al. (2024a) proved that the rules are sound and complete for incorporating local BK into a PMG compatible with local transformation (Theorem 2 of Wang et al. (2024a)). Hence, by using R₁ - RIG or the rules of Wang et al. (2024a), we can obtain the same PMGs. Since the obtained graph by MAGLIST a PMG compatible with local transformation, the obtained graph on Line 17 of Alg. also a PMG compatible with local transformation.
In light of the fact that the input PAG P is PMG compatible with local transformation, given the results (a) and (b) above, we get the desired result by mathematical induction.
D.4. Proof of Theorem 3
Proof. According to Alg. 1, there are two nested loops. In each outer loop, select one variable/vertex with circles. Then, in each inner loop, we transform a circle at this vertex. Without loss of generality, suppose in the i-th round of outer loop, the circles at V; are transformed to non-circles. And we suppose the outer loop runs for more than one round. It is a trivial case that the outer loop finishes in one round.
As discussed in the main paper, the complexity of implementing the orientation rules is O(m2 where mn denotes the number of edges and d denotes the number or vertices. For brevity, we denote this complexity by S.
19

---

Polynomial-Delay MAG Listing with Novel Locally Complete Orientation Rules
We first consider the complexity for an inner loop, i.e., the complexity of implementing Line of Alg. 1 in one round. In this round Vi is selected. Suppose there are kn kinds of local structures of Vi- Hence, by implementing Line 9 of Alg. 1, we will find ky PMGs. When the function LOCALTRANSFORM is triggered, circle at Vi will be enumerated as an arrowhead and tail, hence we could use a binary tree Twithin to denote the process of finding all L PMGs, where each node denotes a PMG obtained by enumerating a circle at V1 and using the orientation rules, and only the leaf node denotes the PMGs with no-circles at V1. The binary tree is as Fig. 6, with only the difference that in the binary tree there are only the second and third graphs in the second layer. Since the proposed rules are locally complete, every non-leaf node must have two children nodes, i.e., there cannot be a non-leaf node with only one child node. In Tinner. denote the number of edges and number of nodes by [[(nnerr) and | (Tinnerr)] Denote the number of leaf nodes and the nodes with two children by 7i and n2. There is |[((inner)) )| [V - no + n2 and |B[[Tnerr]] = 2 * n2.. Hence, n22 1og 1. Since no = 11, there is [[ the proposed rules are incorporated. Hence the total complexity is (2k) - 2).S.
I| = 2k - 2. In the process of obtaining each PMG from the PMG in the parent node,
We then consider the total complexity of implementing Alg. 1. After we incorporate the singleton BK regarding V/1 we will transform the circles at Vi,..., Va. Note that there are 1 local structures of X since there are kj PMGs obtained in the inner loop, where a local structure implies an orientation of all the circles X. Suppose there are N MAGs consistent with P. For the complexity T(N, d) of implementing Alg. 1 for p that contains d vertices with circles, there is
hi T(N, d) Σ T(N,, 1) (2k) - 2)S
where Ni, denotes the number of MAGs consistent with the PMG M., that is obtained from P with the i1 local structures of V1, TN, d 1) denotes the complexity of implementing Alg. 1 for M4,.
We another search tree Touter denote the process of finding all N MAGs, where each node in the j-th layer denotes a PMG which is obtained from P and local structures of Vi.... -, and the leaf node denotes MAG consistent with P. The format of the search tree is as Fig. 10. In the second layer (j = 2), there are k; PMGs due to kú sub-structures of VI. We consider the i1 PMG M,, in the second layer. There are N,, MAGs consistent with M,, Suppose there are k2n, sub-structures of 1/2 given a PMG M.,. Using the calculation above, we can directly conclude that
Aain
T(N d 1)
Σ
d- + (2k2g - -2),,
=2=1
where 12,,, denotes the number of local structures of V22 for the PMG in the i1-th node on the second layer of Touter. Hence, there is
k2i
T(N, d)
Σ
Σ T(N d d 2) + 25(k1 +
k2n ) - 4S.
Repeat the above process, we could conclude that
l
k
T(N, d) + +
1255
+
kaidk +... .....)444 -48
(1)
11=12==1
k1 Note kn >ii=> k2n, + +
Di==1 k3 +... is essentially the number of edges in the search tree Touter. Hence, we only need to consider the number of edges in Touter in the following.
R:211
Denote Z the number of edges in Touter. Denote the number of node which has j child nodes by my. Without loss of generality, suppose the maximum j equals to 8. As Z equals to the number of edges in Touter. there are Z - 1 nodes in Touter. Due to the completeness of the orientation rules for incorporating local BK, there does not exist a node with only one child node. Hence mi = 0. There is
Z m1 + +2* * m2 + + S m,
m2 + S M.
20

---

Polynomial-Deke MAG Listing with Novel Locally Complete Orientation Rules
Consider the number of nodes, there is
-- mo
m2 + m3 + + m.
With the two equations above, there
mg E
1jmy 1.
j=2
mo essentially the number of leaf nodes, which equals the number of MAGs consistent with Hence,
1)mm = +1.
j=2
Therefore, considering there must be at least my # #0,j 2
Z mg m2 + mg +
m,
<
Σし - 1y +
J=2
< 2N +
Hence, according to Eq. 1, there is
T(N, d) S N + 2S(2NN + 2) 4S
T(N,d)/N - 484.
Note S denotes O(m dd), we conclude T(N, dN & d()2d*).
D.5. Proof of Proposition 2
Proof. We prove the soundness by contradiction.
For R17, suppose A B in M by R2. There must be A + in M. Due to the ancestral property and +CC, there can only be D + in M. Hence there - C due the ancestral property and C - B in any MAG M consistent with the given PMG according R₁. Note in this case the sub-structure A C + B+ A contradicts with the ancestral property. Hence A B B is impossible.
For Ris. suppose A - B. As (a) D is a possible ancestor of Ti and D is a possible ancestor of T2, (b) Ti is not adjacent to T2 or an unbridged path relative to {Ti, }2), (c) B + D, in any MAG consistent with the given PMG, there is either D + T, or D + Tz. Without loss of generality, suppose there is D + T,. There is D - Ti ..... A. In this case D an ancestor of B due to + B. However, there D ++ B, contradicting with the ancestral property.
21


Reviews:
[{"review_id": "NkqBvvnavo", "reviewer": "Reviewer_ZQmR", "summary": "The paper proposes a method for enumerating (listing) MAGs consistent with a given PAG with a polynomial delay, i.e., the ratio between the time complexity of enumeration and the number of consistent MAGs is polynomial in the graph size. The method is based on resolving one circle at a time, followed by applying orientation rules to direct as many edges as possible. In particular, the paper introduces three novel orientation rules, which, along with existing rules, are sound and locally complete for incorporating singleton background knowledge (BK). These rules ensure that the listing algorithm has a polynomial delay.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for careful reading and providing many valuable and constructive suggestions, which will definitely help us improve our work. As suggested, we will provide proof sketches and examples for Lemmas 3/4 in the revised version.\n\n1.\t…I don't think all local transforms produce a PMG that has a consistent MAG…: \n\nThank you for raising this critical question. We can confirm that the cases you described will never occur in our proposed algorithm. Below, we will explain (a) why the example you mentioned has been prevented, and (b) why cases where all local transformations produce a PMG not having a consistent MAG will not happen in our algorithm.\n\n(a)\tAccording to Alg.1, when we locally transform $D\\circ-\\circ C$ to $D-\\circ C$ given the PMG in Fig.7(a), the orientation rules are applied immediately after the local transformation (Line 20,22 of Alg.1). As a result, $R_7$ orients $C-\\circ A$, ensuring that $C\\leftarrow\\circ A$ is not considered in subsequent transformations. \n\nFurther, note in Function LocalTransform(H,X), all circles at X are recursively transformed. Although transforming $D\\circ-\\circ B$ to $D-\\circ B$ **itself** cannot orient $C-\\ast A$ by $R_1-R_{16}$, $C-\\ast A$ can still be always obtained by $R_7$ or $[R_{16},R_{13}]$ **after the following transformation** of $D\\circ-\\circ C$ to $D-\\circ C$ or $D\\leftarrow\\circ C$. Hence the problematic structure $C\\circ-\\ast A$ will not occur during subsequent transformations on $C$.\n\n(b)\tThe examples in Fig.7 imply the incompleteness of the rules. However, in LocalTransform(H,X) in Alg.1, we **only** transform the circle at $X$, followed by applying rules. The locally complete property ensures that transforming the circles at $X$ will not result in a PMG without a consistent MAG. Once all circles at $X$ are transformed into non-circles, the resulting non-circles at $X$ **essentially correspond to a valid local transformation** proposed by Wang (2024a), as detailed on Line 984. Due to two facts: (1) Wang (2024a) proved that $R_1-R_{10}$ as well as the first case of $R_{16}$ are sound and complete to incorporate valid local transformations given a PMG compatible with local transformations, (2) our rules are sound and properly contain the rules of Wang (2024a), we conclude that **the PMG obtained after transforming all circles at $X$ into non-circles and applying our rules (Line 17 of Alg.1) is equivalent to the PMG obtained by applying the local transformations and rules of Wang (2024a)**, as detailed on Line 992. Wang (2024a) proved that such PMGs are compatible with local transformations and fulfill complete property. Thus, local transformations on PMGs obtained on Line 17 of Alg.1 will not yield a PMG without a consistent MAG.\n\n2.\tThe succinctness of rules: \n\nThank you for this excellent question. We discuss it from two perspectives: (1) whether a simpler rule combined with the existing rules can replace $R_{14}/R_{18}$; (2) whether the rules themselves can be simplified.\n\nFor (1), we believe that such a simpler rule is unlikely to exist. Suppose, for contradiction, a simpler rule combined with other existing rules can replace $R_{14}/R_{18}$. Then, in any cases where $R_{14}/R_{18}$ is triggered, **the existing rules alone should transform at least one circle**. However, in the examples in Fig.4(c) and Fig.7(d), when adding BK $C_1\\leftrightarrow X\\leftrightarrow C_2$ and $D\\leftrightarrow B$ respectively, no existing rules except for $R_{14}/R_{18}$, can transform any circles. The examples suggest that the existing rules play no role, contradiction. Thus no simpler rule, combined with existing rules, can replace $R_{14}/R_{18}$.\n\nFor (2), if the goal is to simplify the rules themselves, we think it is hard to achieve but cannot rule out the possibility. However, we would like to highlight the contributions of our proposed rules. In causal insufficiency, finding an analog of ``Meek rules`` for incorporating BK into a MEC is an open problem for many years. Our rules can orient edges that existing rules fail to handle. We believe these rules make a significant advancement toward addressing this fundamental problem.\n\n3. MAG listing application: \n\nThank you for your question. Due to space limits, we outline three applications in Response 1 to Reviewer gZDH. We will incorporate them in our revised version.\n\n4. It's hard to understand what's special about \"prior to\" relation in Def.3:\n\nThank you for raising this question. Intuitively, consider a sub-structure $A\\ast-\\circ X\\circ-\\ast B$ in $H$, the relation “$A$ is prior to $B$ relative to $X$’’ characterizes the case where $X\\leftarrow\\ast A$ must be oriented given the transformation of $X\\circ-\\ast B $ to $X\\leftarrow\\ast B$. The three conditions in Def. 3 are three possible cases for that. We will adjust the expression to make it clearer in the revised version.\n\nWe sincerely appreciate your thoughtful feedback and hope these clarifications address your concerns. We welcome any additional questions.", "claims_and_evidence": "Proofs for theorems were included in the appendix. The setup for experiments is clear. \n\nHowever, I found some of the proofs lengthy and difficult to follow (e.g., Lemma 3 & 4). I highly suggest authors provide sketches and intuitions/examples for each part of the proof -- maybe break them into smaller lemmas.", "methods_and_evaluation_criteria": "The paper contains both theoretical results and simulations The method is based on proposing more orientation rules that are sound and locally complete for incorporating BK, which can be exploited to accelerate the listing of MAGs.", "theoretical_claims": "I checked the proofs for Proposition 1, Theorem 2, Theorem 3, and Proposition 2.", "experimental_designs_or_analyses": "I checked the experiments section and the results made sense to me. The listing algorithm proposed in the paper was more efficient than bruteforce and the previous method in [Wang, 2024a] with exponential delay.", "relation_to_broader_scientific_literature": "The paper improves upon the previous work in [Wang et al, 2024] by introducing additional orientation rules that empower the polynomial listing of MAGs.", "essential_references_not_discussed": "I'm not aware of any essential references not discussed.", "other_strengths_and_weaknesses": "Strengths:\n- The topic of listing MAGs from PAGs is important, and the results (assuming correct) are significant since they constitute the first polynomial listing methods on MAGs. \n- The paper contains both theoretical results and experiments to demonstrate the improvement.\n\nWeaknesses:\n- The main results rely on complicated graphical notions without clear intuitions, making them somewhat difficult to follow. The main Definition 1 contains typos. See more details below.", "other_comments_or_suggestions": "- pg 3: Definition 1 is ill-defined. This notion is used frequently later so please make sure it's defined accurately. Also, please cite it if the notion was introduced previously in [Wang, 2024]. I would suggest moving \"Intuitively, given ... must be an ancestor of V'\" after the Definition. \n\n- pg 4, col1, line 200 \"fig. 1(d)\" -> \"fig 1(c)\"\n\n- pg4, col1, line 214-216 \"Since the rules ... due to $A \\circ\\rightarrow B$\" confusing. \n\n- pg4, end of section 3.1. Please elaborate more on how the enumeration of each circle can be viewed as a type of background knowledge (BK). I don't think this connection is well articulated in the paper. If possible, I'd suggest providing some concrete examples. \n\n- pg 5, col 1, line 230. It took me a while to figure out what $R_{12}$ is. Please make sure you mention that Rules 1-13 are shown in the Appendix.\n\n- pg 5 lines 261-267. I don't think the intuition here is explicit enough. It's still hard for me to understand what's special about the \"prior to\" relation in Definition 3. Is it possible to explain it more succinctly?\n\n- pg 5 line 273: two \"an\"'s.\n\n- pg 7 col 2 lines 376-379. Mention the examples are shown in Figure 7.", "questions_for_authors": "- Unless I missed something, I don't think all local transforms produce a PMG that has a consistent MAG. In particular, how do you check if $H'$ obtained from $H$ (Algorithm 1 lines 20, 22) always has a valid MAG? Consider Figure 7(a), for example, suppose we have run LocalTransform on variable D to set edges $D - \\circ B$ and $D - \\circ C$. Now if we run LocalTransform on $C$, we will try (i) $C \\leftarrow \\circ A$; and (ii) $ C - \\circ A$ for the edge $C \\circ - \\circ A$. However, case (i) here will yield a PMG that is not consistent with any MAG (by $R_{17}$), which brings additional cost to the search since it cannot lead to any MAG. Are there any methods to prevent such cases? Also, was this issue addressed in the Proof of Theorem 3 (Appendix D.4)?\n\n- I'm curious about the succinctness of the new orientation rules proposed in this work. Do you believe there may be simpler rules, which, combined with other existing rules, can imply some of the complicated rules (e.g., $R_{14}, R_{18}$) in this paper?\n\n- Could you please provide some specific applications for MAG listing?", "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": "", "extra_scores": {}}, {"review_id": "IeF05xb7qz", "reviewer": "Reviewer_dgb7", "summary": "This paper proposes a MAG listing algorithm (i.e., output all and only MAGs in the MEC, represented by a PAG) with polynomial delay.\n\n---\n\n## update after rebuttal:\n\nI thank the authors for the clear explanation to my questions. I keep my score of acceptance.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your positive evaluation! We will incorporate the discussion you mentioned (DAG listing, counting…) in the revised version. \n\n1. …to count size… would complexity be different? Would the method help: \n\nThank you for your insightful question. Currently, we do not have a clear idea about MAG counting under latent confounding, although DAG counting is thoroughly solved (Wienöbst, 2021). The two main challenges are: (1) bi-directed edges prevent using an order to describe uncertain edge orientations, and it is unclear what mathematical tool could replace order in this context; (2) the orientation of $\\circ\\rightarrow$ connecting different circle components can influence the orientation within a circle component. Consider $A\\circ-\\circ B\\circ\\rightarrow C\\leftarrow\\circ A$. If there is $B\\leftrightarrow C\\leftarrow A$, there must be $A\\ast\\rightarrow B$, showing that the orientations within a component are not independent of the outside orientations. Due to these challenges, we do not have a clear idea about MAG counting method which does not need MAG listing. However, in cases with **only** selection variables, the two obstacles might be resolved: (1) since there cannot be an edge into an undirected edge and no bi-directed edges, an order could be defined among variables without undirected edges; (2), all edges connecting components are directed, thus avoiding the scenarios above. \n\nIf the two obstacles could be solved, we conjecture that some results, such as Lemma 2 and locally complete rules, may be helpful. Nevertheless, without addressing these obstacles, we are unable to provide a definitive answer at this time.\n\n2. …a-priori no selection bias or no latent variables, can this prior knowledge be incorporated? Will the rules be sound and locally complete? Will the time complexity different:\n\nThank you for this excellent question. Yes, **this prior knowledge can be incorporated, but it requires an additional rule: orient $-\\circ$ to $\\rightarrow$ (no selection variable) or orient $\\circ\\rightarrow$ to $\\rightarrow$ (no latent confounding)**. To ensure Thm. 2 holds in the new setting, two key results must be proven: (A) **the new set of rules are sound and complete to incorporate a valid local transformation (LT)**. This is not required in our paper because Wang 2024a has proven that a subset of our proposed rules is sound and complete. However, under the new setting, this must be proven; (B) **the new set of rules are sound and locally complete for singleton BK.** Soundness is evident. We only prove locally completeness. (A) ensures the validity of outer loop of Alg.1 (Line 322-324), (B) ensures that of inner loop (324-329). Due to space limit, we only give a proof sketch.\n\nNo-selection bias: for (A), we refer to Thm. 2 of Wang (2023). Note the PAG in Thm.2 can be easily generalized to a PMG compatible with LT. For (B), following Wang (2023), PMG compatible with LT contains no $-\\circ$. We will prove that Lemmas 3,4 in our paper still hold. Lemma 3 evidently holds. For Lemma 4, consider $H$ on Line 832. If $H$ contains no $\\circ-$, then we directly follow the proof of Lemma 4. If $H$ contains $\\circ-$, it can be shown that the singleton BK transforms at least one edge $X\\circ-\\circ V$ to $X-\\circ V$. In this case, there cannot be an edge $V’\\ast\\rightarrow X$, as this would force $X-\\circ V$ to $X\\rightarrow V$ by $R_{16}$. Thus $\\mathbf{C}$ on Line 830 is empty. Thus, if $H$ contains $X\\circ-\\ast T$, it can be shown that $\\mathbf{C}’={T}$ satisfies the four conditions in Lemma 2 as it contains only one element, ensuring a MAG consistent with $H$ and $X\\leftarrow\\ast T$. Lemma 4 holds.\n\nNo-latent confounding: for (A), consider a PMG $M$ compatible with LT and no $\\circ\\rightarrow$. It suffices to prove that no bi-directed edges are formed by Alg.2 of Wang (2024a), which would otherwise lead to invalid structure $\\leftrightarrow$. \n\nAccording to Lemma 22 of Wang (2024a), bi-directed edges can only form in Step 2 of Alg.2. Note $M$ contains no $\\circ\\rightarrow$. If $K\\circ\\rightarrow T$ in Step 2 is transformed to $K\\leftrightarrow T$, according to balance property and $K\\in$PossDe\\Z, there is $X\\circ\\rightarrow T$ in $M$, contradiction. We can thus directly apply Thm. 2 and Thm. 3 of Wang (2024a) to prove (A). For (B), the proof follows almost entirely from our paper, as Lemma 3 and 4 unaffected by the new rule.\n\n**The complexity changes without latent confounding.** In this case, there are no unbridged paths (Def.1), as their existence would imply a bi-directed edge. Hence, detecting the third condition in Def. 3 ($O(m^3d)$) is unnecessary, leaving only $O(m)$ for the first two conditions. Thus the complexity of $R_{14}$ improves by $O(m^2d)$. Similarly, all rules involving unbridged paths can be applied more efficiently. However, for no selection bias, the complexity of $R_{14}$ remains unchanged.\n\nWe appreciate your positive and thoughtful feedback, and welcome additional questions.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes I read the theorems, ran the examples, and skimmed through the proofs. They look correct to me. But I cannot guarantee.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "To me, the result presented in this paper is very necessary and crucial for the field of causal discovery.\n\nSeveral problems that can directly benefit from this work include FCI with background knowledge, causal effect estimation from PAG, and experimental design with latent variables.", "essential_references_not_discussed": "I would suggest authors to also discuss the DAG listing algorithms. To the best of my knowledge their current best time complexity is O(n^4) where n is the number of nodes (https://arxiv.org/abs/2301.12212).\n\nSince DAG is a specific kind a MAG, it would be interesting to see how the technical development of DAG listing algorithm share some same insights that can benefit MAG listing, or which technical obstacle is unique to the MAG case.", "other_strengths_and_weaknesses": "This work is novel and crucial. I do not see major weaknesses.", "other_comments_or_suggestions": "/", "questions_for_authors": "1. If the purpose is not enumerating all the MAG instances in the MEC but just to count the size of the MEC, would the time complexity be different? Would the proposed method in this paper still help?\n\n2. If one knows a-priori that there is no selection bias (so that there is no -- edge and all -o edge can be oriented to ->), or similarly no latent variables, can this prior knowledge also be incorporated into the MAG listing algorithm? Will the rules still be sound and locally complete? Will the time complexity be different?", "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": "", "extra_scores": {}}, {"review_id": "xFArFyniBq", "reviewer": "Reviewer_Wkax", "summary": "The paper presents a novel polynomial-delay algorithm for listing all maximal ancestral graphs (MAGs) in a Markov equivalence class (MEC) while incorporating singleton background knowledge (BK). The core contribution is the development of three new orientation rules that improve computational efficiency compared to existing methods. The authors provide formal proofs of soundness and local completeness of the proposed rules and compare their algorithm’s performance with previous approaches through experiments on synthetic data. They also discuss the limitations of existing methods and the incompleteness of current orientation rules for incorporating general BK, motivating future research.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for insightful comments and positive evaluation! We will add more illustrations and examples to make it easier to read for average readers in the revised version.\n\n1. Is there any intuition or idea how to further optimize the rule applications to reduce the complexity: \n\nThank you for raising this insightful question. In the submitted version, we mainly focused on the polynomial-delay and the orientation rules to incorporate BK, without delving deeply into the specific complexity of rule application. Your question, along with Reviewer ZQmR’s comments, prompted us to carefully examine the complexity, and we found that it can indeed be improved to $O(m^3d^5)$. Below, we provide a rough analysis of the implementation of $R_{14}$, which is the most time-consuming part.\n\nThere are $d$ variables. For each variable $X$, there are $ O(d^2)$ pairs of $V_i,\nV_j$ such that $V_i\\ast-\\circ X\\circ-\\ast V_j$, and detecting whether $V_i$ is prior to $V_j$ (or vice versa) relative to $X$ takes $O(m^3d^2)$. Additionally, there are $O(d)$ variables $V$ such that $X\\circ\\rightarrow V$ is possibly oriented by $R_{14}$. For each such $V$, since we already know which variables are prior to $V$ relative to $X$, enumerating each pair $T_1,T_2$ prior to $V$ takes $O(d^2)$, and detecting conditions (a) and (b) in $R_{14}$ takes $O(m)$. Hence, the total complexity is $d* (O(d^2)* O(m^3d^2)+ O(d)* O(d^2)* O(m))=O(m^3d^5)$.\n\nThe main computational bottleneck lies in detecting the \"prior to\" relation defined in Def. 3. Since we check this relation for every pair, the computational cost is high. In our current analysis, we did not exploit certain properties of the \"prior to\" relation that could potentially reduce the number of pairs to consider or improve the detection efficiency. Exploring these properties could lead to further optimization, which we leave for future work.\n\n2. In the experiment for $d=6$, why the computation time has a local drop for $\\rho=0.15$: \n\nThank you for your careful observation. This is an excellent and thoughtful question. We have analyzed the phenomenon and found that it is not caused by the algorithm itself but rather by the **parallel implementation** of the simulations.\n\nSpecifically, we have ever tried to run simulations for $d=6$ under different parameter settings ($\\rho=0.1$ and $\\rho=0.15$) **separately**, the average running time for $\\rho=0.15$ is indeed higher than $\\rho=0.1$. However, in our experiments, we adopted the same parallel implementation manner as Wang (2024a), where each thread processes different combinations of $d\\in${6,8,10,12,14},$\\rho\\in${0.05,0.1,0.15,0.2,0.25},$graphindex\\in$[1:100]. Under this parallel setup, although the method returns **totally same** MAGs as the method implemented under the separate setup for each parameter, the running time for $d=6,\\rho=0.1$ and $d=6,\\rho=0.15$ can exhibit slight variations. Hence we analyze it is due to the differences in resource allocation across threads. For $d=6$, the computation time for each PAG is extremely short (ranging from 0.000x seconds to 0.0x seconds, with some recorded as 0). In such cases, the dominant factors influencing running time are not the algorithm itself but external factors such as thread-level resource allocation. When $d$ and $\\rho$ are relatively large, the algorithm’s implementation becomes the primary time-consuming part, and this anomaly no longer occurs.\n\nIn the revised version, we will include an explanation to clarify this phenomenon. Thank you!\n\n3.\tHow does the \"brute-force\" in the experiments work:\n\nThank you for pointing out this issue—it is indeed a result of insufficient clarity in our writing. The brute-force method used in our experiments follows Alg. 4 of Wang (2024a). Below is a brief explanation of its main idea:\n\n(a)\tEnumerating configurations: Given a PAG, the method enumerates all non-circle configurations of all circles (Line 5 in Alg. 4 of Wang (2024a)). This process generates multiple mixed graphs.\n\n(b)\tFiltering Mixed Graphs: For each mixed graph, the algorithm checks whether it satisfies three conditions: ancestral property, maximal property, and consistency with the given PAG (Line 6-12 in Alg. 4 of Wang (2024a)). If the mixed graph meets these criteria, it is included in the output (Line 13 in Alg. 4).\n\nIn the revised version, we will add the brute-force algorithm in the appendix for reference and provide a concise introduction in the main paper to avoid confusion.\n\n**Beyond MAG listing, we want to highlight the contributions of our proposed orientation rules. In causal insufficiency setting, the analogical ``Meek rules`` for incorporating BK into a MEC have remained an open problem for many years. We believe our new rules make a significant advancement towards addressing this fundamental problem.**\n\nWe sincerely appreciate your thoughtful feedback and hope these clarifications address your concerns. We welcome any additional questions.", "claims_and_evidence": "- The claims of polynomial-delay of the proposed algorithm and soundness and locally completeness of the proposed orientation rules for incorporating singleton BK are supported by theoretical proofs.\n- The claim that MAGLIST-POLY significantly outperforms previous methods in efficiency is supported by experiments.", "methods_and_evaluation_criteria": "- The paper builds on previous MAG listing algorithms but improves efficiency by introducing singleton BK and new orientation rules.\n- The method is evaluated by correctness, computational complexity and experimental validation.", "theoretical_claims": "The main theoretical contributions include: \n- Theorem 1: The new orientation rules are locally complete for incorporating singleton BK.\n- Theorem 2: The algorithm outputs all and only the MAGs in the MEC.\n- Theorem 3: The method has polynomial delay $O(m^5d^4)$ where $m$ is the numebr of edges.\n\nThe proofs appear rigorous, leveraging formal graph-theoretic arguments, while not carefully checked.", "experimental_designs_or_analyses": "The authors generate random ER graphs, convert them into MAGs, and compare listing algorithms under different densities and graph sizes. They use 100 random graphs per setting, with time limits of 3600 seconds per experiment. The design and conclusion make sense to me.", "relation_to_broader_scientific_literature": "Structure learning is widely used in scientific research where latent variables as confounders are pervasive. Using MAG for flexble modelling and understanding the possible Markov equivalent graphs are essential to the application of these methods.", "essential_references_not_discussed": "Not clear due to limited familiarity. But the discussion w.r.t related work is smooth and clear.", "other_strengths_and_weaknesses": "**Strengths**\n- It provides the first polynomial-delay MAG listing algorithm.\n- It proves the soundness and local completeness of orientation rules.\n- The experiments show noticeable improvement.\n\n**Weaknesses**:\n- Due to the theoretical nature, the paper is dense in mathematical notations and concepts and not easy to comprehend for average readers.", "other_comments_or_suggestions": "- Apart from ER graphs in the experiments, it would also be helpful to consider scale-free graphs to reflect real-world causal structures.", "questions_for_authors": "- It there any intuition or idea how to further optimize the rule applications to reduce the $O(m^5d^4)$ complexity?\n- In the experiment for $d=6$, why the computation time has a local drop for $\\rho=0.15$?\n- How does the \"brute-force\" in the experiments work?", "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": "", "extra_scores": {}}, {"review_id": "zLRAqkV1Kw", "reviewer": "Reviewer_gZDH", "summary": "This paper introduces an enhanced algorithm for the MAG listing task that outputs MAGs in the MEC with polynomial delay. Experimental results confirm the effectiveness of the proposed approach, and a counterexample construction is provided to demonstrate the incompleteness of current orientation rules.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments and suggestions. We are grateful for your positive evaluation of the theoretical contributions and experimental designs in our paper. We also appreciate your suggestion to discuss real-world tasks and datasets, as well as to clarify the practical applications of the proposed MAG listing algorithm.\n\n1.\tHow the algorithm can be used in practice:\n\nBelow, we **outline three key applications** where the proposed algorithm can be used:\n\n(a). Intervention Variable Selection:\n\nIn causal discovery with active interventional data, selecting the optimal variables for intervention can significantly reduce the number of required interventions, which is critical given the high cost of interventions in real-world scenarios. In the causal sufficiency setting, He & Geng (2008) proposed a maximum entropy criterion for selecting variables based on the distribution of local structures in the Markov equivalence class (MEC) of DAGs. This requires efficient DAG listing to calculate the frequencies of local structures. In the causal insufficiency setting, MAG listing can generalize this approach by enabling the computation of analogous distributions for MAGs, allowing for optimal intervention variable selection.\n\n(b). Determining the Distribution of Possible Causal Effects Given a Markov Equivalence Class (MEC):\n\nGiven a MEC learned from observational data, sometimes we want to estimate the distribution of possible causal effects of one variable $X$ on another $Y$. In this case, it is necessary to consider all possible causal graphs within the MEC. Note different causal effects may appear with different possibilities since they may correspond to different numbers of causal graphs. In the causal sufficiency setting, Maathuis et al. (2009) enumerated all DAGs in an MEC to determine the distribution of possible causal effects. In the causal insufficiency setting, MAG listing method allows for determining the distribution of possible causal effects.\n\n(c). Complete Causal Discovery Algorithms:\n\nIn causal discovery tasks, completeness is a desirable property, ensuring that all valid causal graphs (DAGs or MAGs) consistent with the data are considered. For example, in Appendix D.4 of Kocaoglu (2023) and Alg. 1 of Gerhardus (2024), MAG listing is explicitly used to achieve completeness in causal discovery. Efficient MAG listing allows these algorithms to systematically explore all equivalent MAGs, ensuring that no potential causal graphs are overlooked.\n\nIn summary, the three applications-intervention variable selection, determining distributions of possible causal effects, and enabling complete causal discovery algorithms—highlight the importance of MAG listing in advancing causal inference methods under causal insufficiency. The development of efficient MAG-listing algorithms makes these applications feasible and opens new possibilities for research and practical implementation.\n\nIn the revised version, we will elaborate on the applications of MAG listing. \n\n2.\tDiscussion about datasets:\n\nIn our experiments, we focused on synthetic datasets because they allow us to systematically evaluate the correctness, effectiveness, and efficiency of the proposed algorithm under controlled conditions. Synthetic data also enable us to test the algorithm across a wide range of parameter settings, which would be difficult to achieve with real-world datasets. \n\nTo the best of our knowledge, there are currently no publicly available datasets with ground-truth causal graphs that account for the causal insufficiency setting (i.e., the presence of latent confounders and selection variables). This lack of ground-truth data makes it difficult to directly validate the algorithm on real-world datasets in this context.\n\nWe fully agree that testing the algorithm on real-world datasets would provide stronger evidence of its practical utility. As part of future work, we plan to explore real-world datasets that approximate the causal insufficiency setting. Additionally, we hope that the community will develop and release open datasets containing both latent confounders and selection variables, which would further advance research in this area. We will explore the possibility of incorporating real-world case studies in future work to further strengthen the practical contributions of this research.\n\n\n**Beyond MAG listing, we want to highlight the contributions of our proposed orientation rules. In causal insufficiency setting, the analogical ``Meek rules`` for incorporating BK into a MEC have remained an open problem for many years. We believe our new rules make a significant advancement towards addressing this fundamental problem.**\n\nThank you once again for your thoughtful feedback, which has helped us improve the clarity and impact of our work.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I looked through the theoretical claims and proofs, and do not find any issues.", "experimental_designs_or_analyses": "Given the theoretical contribution is solid in this paper, the experiments focus on verifying the effectiveness and efficiency of the proposed MAG listing algorithm on synthetic datasets. The experimental designs and results are sound and valid. Nevertheless, I would like to also suggest the authors add some discussions about real-world tasks and datasets.", "relation_to_broader_scientific_literature": "It may influence fields where the causality is curical with latent variables.", "essential_references_not_discussed": "I don't know any related works that are essential to understanding but are not currently cited/discussed in the paper.", "other_strengths_and_weaknesses": "The paper is theoretically sound and solid and is well-written. My only concern is that it is unclear how the proposed algorithm could be used in practice. As the author mentioned in Sec. 1, causality is \"a key component in numerous applications.\" Therefore, I think this paper could be stronger if there are some verifications on applications.", "other_comments_or_suggestions": "I do not have any other comments or suggestions.", "questions_for_authors": "I do not have other questions.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors consider the problem of listing MAGs from a PAG. In causal discovery, MAG represents a class of causal graphs with latents (and selection bias) that all entail the same conditional independence relations. PAG represents an equivalence class of MAGs. PAG is what is learnable from data. MAG listing is a very hard problem, and the presented paper provides the first polynomial delay algorithm to do this. It fills an important fundamental gap in our understanding of observational causal discovery. Their approach relies on replacing a critical step of the previous algorithm from jointly orienting all circle marks locally to orienting them one at a time. This basic idea can only be realized properly if complemented with a sound and complete set of orientation rules. The authors develop these in this paper. They also show that even after we add the orientation rules in this paper, we still do not have global orientation completeness. This is perhaps not surprising, but it is also very valuable to establish formally through counterexamples. 

The reviews have been positive, and after rebuttal, all reviewers recommend acceptance, acknowledging that it fills an important gap in the literature. The only minor weakness is seen as dense notation and dense theory. But I think this is unavoidable for a paper like this. 

The notion of local completeness is interesting and valuable, in my opinion. However, its necessity in the context of the paper is a bit less clear. The authors argue that without it, we would have a problem because we would potentially create orientations that are inconsistent with the Markov equivalence class. However, it is unclear why this is such a big issue. We can check if the current partial structure is still consistent with the Markov equivalence class learned from data. This would incur computational overhead, but it is not obvious that this is a deal-breaker, in the sense that such an algorithm would not be polynomial time. Since the authors mention the main reason the previous method had exponential time was that it jointly oriented all circles at one node. Therefore, it is important for the authors to either provide a counterexample that, without local completeness, their algorithm would not be polynomial time in the worst case, or refrain from suggesting the necessity of local completeness as a precondition for poly delay. As I said, local completeness is already valuable on its own, in my opinion.
Decision: Accept (oral)