Characterization and Learning of Causal Graphs with Small Conditioning Sets
Authors: Murat Kocaoglu
Venue: NeurIPS 2023 poster (2023)
Keywords: causal discovery
TL;DR: We propose a characterization of Markov equivalence with bounded degree conditional independence statements, and propose an algorithm for learning it from data to address finite-sample issues of current causal discovery algorithms.

Abstract: Constraint-based causal discovery algorithms learn part of the causal graph structure by systematically testing conditional independences  observed in the data. These algorithms, such as the PC algorithm and its variants, rely on graphical characterizations of the so-called equivalence class of causal graphs proposed by Pearl. However, constraint-based causal discovery algorithms struggle when data is limited since conditional independence tests quickly lose their statistical power, especially when the conditioning set is large. To address this, we propose using conditional independence tests where the size of the conditioning set is upper bounded by some integer k for robust causal discovery. The existing graphical characterizations of the equivalence classes of causal graphs are not applicable when we cannot leverage all the conditional independence statements. We first define the notion of k-Markov equivalence: Two causal graphs are k-Markov equivalent if they entail the same conditional independence constraints where the conditioning set size is upper bounded by k. We propose a novel representation that allows us to graphically characterize k-Markov equivalence between two causal graphs. We propose a sound constraint-based algorithm called the k-PC algorithm for learning this equivalence class. Finally, we conduct synthetic, and semi-synthetic experiments to demonstrate that the k-PC algorithm enables more robust causal discovery in the small sample regime compared to the baseline algorithms.

Characterization and Learning of Causal Graphs with Small Conditioning Sets
Murat Kocaoglu
School of Electrical and Computer Engineering Purdue University
mkocaoglu@purdue. edu
Abstract
Constraint-based causal discovery algorithms learn part of the causal graph struc- ture by systematically testing conditional independences observed in the data. These algorithms, such as the PC algorithm and its variants, rely on graphical characterizations of the so-called equivalence class of causal graphs proposed by Pearl. However, constraint-base is limited since conditional independence tests quickly lose their statistical power, especially when the conditioning set is large. To address this, we propose using conditional independence tests where the size of the conditioning set is upper bounded by some integer l for robust causal discovery. The existing graphical char- acterizations of the equivalence classes of causal graphs are not applicable when we cannot leverage all the conditional independence statements. We first define the notion of k-Markov equivalence: Two causal graphs are k-Markov equivalent if they entail the same conditional independence constraints where the conditioning set size is upper bounded by We propose a novel representation that allows to graphically characterize k-Markov equivalence between two causal graphs. We propose a sound constraint bonstraint-based algorithm called the k-PC algorithm for learning this equivalence class. Finally. experiments to demonstrate that the k-PC algorithm enables more robust causal discovery in the small sample regime compared the baseline algorithms.
causal discovery algorithms struggle when data
conduct synthetic, and semi-synthetic
Introduction
Causal reasoning is critical tool for machine learning and artificial intelligence research with benefits ranging from domain adaptation to planning, explainability and fairness 27
Estimating intervention from observational data is called causal inference. A very rich literature of causal inference algorithms have been developed to address this task in the [7 [ The function that used to write an interventional distribution in terms of the observational distribution is called the estimand. Estimand depends on the causal relations between the system variables, which are represented in the form of directed acyclic graph (DAG) called the causal graph. Thus, causal graph is required for solving most causal inference problems.
12 26
the effect of action
literature (T] 21
For small and well-studied systems, it might be possible to construct causal graph using expert knowledge. However, in modern complex systems with changing structure, we need to learn causal graphs from data. This is called causal discovery. In most domains, we have access plenty of observational data, but no interventional data. An important task then is to understand how much causal knowledge we can extract from observational data about system.
The classical approach for addressing this problem is to use the conditional independence (CI) relations in the data to narrow down the space of plausible causal graphs [.. These are called constraint-bare based methods. Even though the number of causal graphs that entail the same set of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

conditional independence relations are typically exponentially many, we can use graphical charac- terization of equivalence between causal graphs compactly represent all of them using a single mixed graph called the essential graph. This notion of equivalence is called Markov equivalence.
Even though such causal discovery algorithms are consistent, i.e., they output the correct essential graph in the large sample limit, in practice, they struggle due to finite number of samples since not all CI tests can be performed accurately [[6]. For constraint-based algorithms, however, it is important for every test to be accurate since previously learned edge orientations are used to orient more edges due to their sequential nature. Thus, they may output very different causal graphs compared to the ground truth with just few incorrect CI statements. Despite the efforts to stabilize PC output [2 [), this fundamental issue still causes problems today. Furthermore, the existing Markov equivalence class characterization and causal discovery algorithmss that rely on this characterization, such as
the PC/IC algorithms 19 22 require access to every CI relation, which is a significant practical limitation for causal discovery from data.
There are several alternatives to constraint-basee causal discovery. For example, score-based ap- proaches, such as GES [3 4 optimize a regularized score function by greedily searching over the space of DAGs to output a graph within the Markov equivalence class. A line of works, such as NOTEARS (28) converts the graph learning problem to a continuous optimization problem by con- verting the acyelicity constraint to a continuous constraint via trace formulation. Note that our goal in this paper is not to beat the state-of-the- art causal discovery algorithm, but provide theoretical basis to characterize what is learnable on fundamental level by using conditional independence tests with restricted cardinality conditioning sets.
Variations of the causal discovery problem with limited-size conditioning sets have been considered in the literature. The special case of marginal dependence is considered in [13] and [20]. The most
related existing work is (23), where the authors aim learning the graph union of all causal graphs that
are consistent with set of conditional independence statements up to a fixed cardinality conditioning set. They propose a concise algorithm that modifies the steps of PC which they show recovers
the union of all equivalent graphs. Similarly in the case with latent variables, AnytimeFCI [18] shows that one can stop FCI algorithm after exhausting all conditional independence tests up to a fixed cardinality conditioning set and the output of the algorithm is still sound for learning parts of the partial ancestral graph (PAG). We propose an alternative route: First, we formally define the equivalence class of causal graphs and propose graphical object to capture this equivalence class called the k-closure graphs. We identify a necessary and sufficient graphical condition to test equivalence between k-closure graphs. Finally, we develop a learning algorithm that leverages the representative power of partial ancestral graphs (PAGs), which are typically used in the case with latents, to obtain a provably finer characterization of the set of equivalent causal structures than [23
In this paper, we propose learning causal graphs using CI tests with bounded conditioning set size. This allows us to ignore CI tests that become unreliable with limited data, and avoid some of the mistakes made by constraint-based causal discovery algorithms. We call CI constraints where the conditioning set size is upper bounded by k as the degree-k: CI constraints. We call two causal graphs k-Markov equivalent they entail the same degree-k CI constraints. We propose k-closure graphs that entail the same degree-k CI relations as the causal graph, and show that we can characterize k-Markov equivalence via Markov equivalence between k-closure graphs. We then propose a constraint based learning algorithm for learning this equivalence class from data, represented by the so-called k- essential graph. Finally, we demonstrate that our algorithm can help alleviate the finite-sample issues faced by the PC algorithm, especially while orienting arrowhead marks and for correctly learning the adjacencies in the graph. We also compare our algorithm with NOTEARS 28 and LOCI (3)
2 Background
In this section, we give some basic graph terminology as well as background constraint based causal discovery: An(x) represents the set of ancestors of x in a given graph that will be clear from context. De(x) similarly represents the descendants of x. Ne(zz) represents the neighbors of 2, i.c., the nodes that are adjacent to x.
Definition 2.1. A path in a causal graph a sequence of nodes where every pair of consecutive nodes are adjacent in the graph and no node appears more than once.
2

---

Definition 2.2 (Skeleton). The skeleton of a causal graph D is the undirected graph obtained by making every adjacent pair connected via an undirected edge.
Definition 2.3 ((Unshielded) Collider). A path of three nodes ca, is collider if the edges adjacent to c along the path are into c. A collider is called an unshielded collider if in addition the endpoints of the path a, b are non-adjacent.
Definition 2.4 (d-connecting path). A path is called d-connecting given set e iff every collider along p is an ancestor some node e, and every non-collider not c.
Definition 2.5 (d-separation). Two nodes a, b on causal graph D said be d-separated given a set c of nodes iff there is no d-comnecting path between a, b given shown by (a TL blc)D. or IL b blc if clear from context.
Definition 2.6 (Causal Markov assumption). A distribution is called Markov relative graph D= (V, E), each variable is independent from its non-descendants conditioned on its parents in D.
There are local, global and pairwise Markov conditions that can all be shown as consequence of the Causal Markov condition above [IO]. This gives us the following:
Proposition 2.7 ((TO). Let p be any joint distribution between varibles on causal model with the graph D. If (a IL blc)D then (a 11. blc)p. ie., d-separation implies conditional independence under the Causal Markov condition.
Definition 2.8 (Markov equivalence). Two causal graphs DI. D2 are called Markov equivalent, shown by D1 ~ D2, if they entail the same d-separation constraints.
Definition 2.9 (Causal Faithfulness assumption). distribution p called faithful to a causal graph D (V, E) iff the following holds Va, b V.c. V: (a TT blc), = (a -l b c)
Constraint cunstraint-based causal discovery is not possible without some form of faithfulness assumption, since otherwise CI statements do not inform of the graph structure. We will later see that restricting ourselves to a small set of CI tests allow us to also weaken the faithfulness assumption we need for causal discovery algorithm.
Theorem 2.10 ). Two DAGs are Markov equivalent if and only if they have the same skeleton and the same unshielded colliders.
Definition 2.11 (Degree-k d- d-separations). The collection of d-separation statements entailed by DAG where the conditioning set has size of at most is called degree-k & d-separation statements.
3 Markoy Equivalence of Causal Graphs with Small Conditioning Sets
We are interested in characterizing the collection of causal graphs that entail the same d-separation constraints for all conditioning sets of size up to l for some k E N. We call this k- k-Markov equivalence: Definition 3.1. Two DAGs D1, D2 are called k-Markov equivalent, shown by D1 ~ D2 if they entail the same d-separation constraints IL c for all V |cl < k.
The notion of A-Markov equivalence partitions the set of causal graphs into equivalence classes: Definition 3.2. k-Markov equivalence class of a DAG defined as the set of causal graphs that are M-Markov equivalent to D, shown by [))a i.e., D' D' D, VD' E [D]..
We first discuss how Verma and Pearl's characterization fails when we cannot test all d-separation statements. Note that if two DAGs have the same skeleton and unshielded colliders, then they entail the same d-separation constraints by Theorem 2.10 Therefore, they also entail the same degree-k d-separation relations. However, the other direction not true: Two graphs with different unshielded colliders or different skeletons may still entail the same degree-k d-separation relations. This is expected since are checking less constraints, which increases the size of the equivalence class: More and more graphs become indistinguishable as we do not rely on certain d-separation constraints.
For example, consider the causal graphs in Figure (a. b). In D1, even though a, b are non-adjacent, they cannot be made conditionally independent unless both e and d are conditioned on. Similarly in D2, c, b cannot be made independent unless both a, d are conditioned on. In both graphs, a, d are independent, and become dependent conditioned on e or Therefore, D1, D2 are k-Markov equivalent for k = 1: They entail the same conditional independence relations for conditioning sets
3

---

d
d
0
(a) D
(b) D2
(c) D3
(d) D4
Figure 1: (a), (b): Both D1 and D2 entail the same degree-1 CI relations although they have different skeletons, thus they are in the same k-Markov equivalence class. (c), (d): Both D3 and D4 entail the same 1 CI relations although they have different unshielded colliders, thus they are the same M-Markov equivalence class.
of size up to 1. Similarly in Figure d), the flipped edge between c, b induces different unshielded colliders in Di and D2. However, the endpoints of these colliders (f) (d, c) and (e, b), (a, b) all dependent conditioned on subsets of size at most 1. Then it is easy to verify that D1. D2 entail the same degree-k d-separation relations for k 1 despite having different unshielded colliders.
These examples show that different structures may induce the same degree-k d-separation relations. One might think that, if collider actually changes the k-Markov equivalence class, then perhaps there is hope that a local characterization around all such equivalence class-chang caass-changing colliders might be possible. However, this is not true. Our example in Section D.I shows that local characterization similar to Theorem i0 is not possible for M-Markov equivalence.
3.1 k-closure Graphs
Our goal is up with graphical representation of M-Markov equivalence class that captures the invariant causal information across equivalent DAGs. This will later be useful for learning identifiable parts of the causal structure from data by CI tests. First, introduce the notion of a k-covered pair.
Definition 3.3. Given DAG D EV) and an integer k, a pair of nodes a, are said to be k-covered if Bc C V |c| < l and a blc.
Therefore, k-covered pairs are pairs of variables that cannot be made independent by conditioning on subsets of size at most k. For example, a, b in Figure I are k-covered for k = 1. In any graphical representation of k-Markov equivalence class, k-covered pairs should be adjacent. This is because is not always possible to distinguish if they are adjacent or not by degree-k & d-separation relations.
We propose k-closure graphs as useful representation characterize k-Markov equivalence class. Definition 3.4. Given DAG D = (V, E) and an integer k, the k-closure of D is defined as the graph shown by Cc( that satisfies the following:
1. If: b are k-covered in D i) if a E An(b), then a - in CD) úi if e An(a), then a + b in CD)), iii) else b in (P)
2. Else: a, are non-adjacent in (D)
The definition of k-closure trivially implies the following:
Lemma 3.5. Given a DAG D and an integer k, the k-closure graph Cx(D) is unique.
Furthermore, there is straightforward algorithm one can employ to recover k-closure from the DAG: Make the non-adjacent pairs that cannot be d-separated with conditioning sets of size at most k adjacent according the definition. Even though this may be poly-time operation, it is unavoidable to characterize the K-Markov equivalence class.
The following lemma shows that k-clossre graphs can be used to capture all the conditional indepen- dence statements with bounded-size conditioning sets imposed by a DAG.
Lemma 3.6. k-closure (D) of a DAG entails the same degree-k d-separation statements as the DAG, i.e. (a I1 6 (c)D + (a IL (l)) Ve V |cl < k.

---

Proof Sketch. The proof relies on two crucial lemmas. If a + b in (D), then in D, conditioned on any subset of size at most k, there is a d-connecting path with arrowheads on both a and b. Similarly, if a + b in C& then in D. conditioned on any subset of size at most & there is d-connecting path with an arrowhead a d-connecting path in D. The other direction is straightforward as the d-connection statements in D
Using these, we can show that any d-connecting path C& (D) implies
hold in C2 (D) since is obtained from D by adding edges. Please see Section A.1 for the proof. [
Inspired by ancestral graphs (15), k-closure graphs are mixed graphs with directed and bidirected edges, where k-covered pairs in the DAG made adjacent in (D) based on their ancestrality.
Definition 3.7. A mixed graph is a graph that contains directed edges a + b, +- b or bidirected edges <> b where every pair of nodes is connected by at most one edge.
Due to bidirected edges, k-closure graphs not DAGs, However, can show that they are still acyclic. In fact, it is worth noting that k-closure graphs are special class of ancestral graphs [[5].
Lemma 3.8. For any DAG D, the k-closure graph CD( is a maximal ancestral graph (MAG).
MAGs have been successfully applied for learning causal graphs with latent variables [15. Similar MAGs, k-closure graphs are simply graph objects to help us compactly represent the k-Markov equivalence class of causal DAGs, rather than expressing the underlying physical system directly. They do, however, represent ancestrality relations between variables by construction.
The relation between k-closure graphs and MAGs is not an if and only if relation. a MAG, one can have bidirected edge between any pair of nodes long does not create a (almost) directed cycle. This is because they represent latent confounders and one might have latent confounders between any pair of observed nodes. However, bidirected edges in k-closure graphs represent k-covered pairs and cannot be added arbitrarily. Accordingly, there are MAGs that are not valid k-closure graphs. An example is given in Section D.2 We have the following characterization:
Theorem 3.9. A mixed graph K = EV is a k-closure graph if and only if is a maximal ancestral graph and for any bidirected edge a ++ b E E the following is true:
. Tc C V V S (a 1L u.bbbe ble)gs, where K' = (V, E {a ++ b)).
The Markov cquivalence between MAGs has been characterized in the literature. This relies not only skeletons and unshielded colliders, but also colliders on discriminating paths being identical.
Definition 3.10. A path = (a, Z1.... 2m; u, Y. U) is called discriminating path for u, Y, af are not adjacent and every vertex {zi u are colliders on p and parents of v.
Theorem 3.11. [[5]]] Two MAGs Mi, M2 are Markoy equivalent if and only if They have the same skeleton, ii) They have the same unshielded colliders, úii) For any node Y for which there is discriminating path p. Y has the same collider status on in M1,
One important observation for our characterization is that Markov equivalence of k-closure graphs do not rely discriminating paths unlike arbitrary ancestral graphs.
Lemma 3.12. Suppose two k-closure graphs K1, K2 have the same skeleton and unshielded colliders. Then along any discriminating path p for a node Y, Y has the same collider status in K₃ and K2.
The above lemma shows that discriminating paths, although may exist in k-closure graphs, do not alter the equivalence class by themselves. Hence, for the graphical characterization of the equivalence between k-closure graphs, we can drop the discriminating path condition.
Corollary 3.13. Two k-closure graphs K1, K₂ are Markov equivalent if and only if
1. They have the same skeleton and
2. They have the same unshielded colliders.
In the next section, we will prove a k-Markov equivalence characterization based on Lemma 3.6 which will later be useful for learning, since we can employ algorithms devised for learning MAGs.
5

---

d
d
d
d
/
0
C
b
a
b
a c b
(10 c b
(a) Dr
(b) Cx()))
Dc)
(d) (D2)
(e) E
Figure 2: Two k- B-Markov equivalent DAGs for k = 0 with the same k-essential graph. D1 ~u D2 for O. Thus, Cx (DD))~(((D))) Thus, they have the same k-essential graphs E (Di)= obtained as the edge union of their k-closures. Note that there are no Markov equivalent k-closures, where a, d are connected with a bidirected edge since removing that edge from the k-closure graph would make a, d separable by empty set, which means it would not be valid k-closure graph by Theorem 3.9. Thus, a, d is connected via undirected edge. Similarly, there is no Markov equivalent k-closure where ++ b since c, would not be k-covered in any Markov equivalent k-closure graph.
3.2 M-Markov Equivalence
Our main result in this section is the following theorem that characterizes k-Markov equivalence: Theorem 3.14. Two DAGs D1, D2 are k-Markov equivalent if and only (D;;) and Cx()2) are Markov equivalent.
Thus, k-Markov equivalence of two DAGs can be reduced to checking Markov equivalence of their k-closures, which can be checked locally using the equivalence condition Corollary 3.13 Based on this result, it is clear that, by using conditional independence tests, we can only hope to narrow down our search up to the equivalence class of k-closure graphs.
Note that when all the CI tests can be conducted, we can learn the arrowheads and tails that consistently appear in all Markov equivalent DAGs. By operating at the k-closure graph-level, we can attain similar objective and hope to learn the invariant arrowheads and tails.
Definition 3.15 (Edge union). For our purposes, we define the edge union operation as follows:
- bUa b a- + bUa bUa + b= ao-ob,
bla b= ao- b
Definition 3.16 (k-essential graph). For any DAG D, the edge union of all k-closure graphs that are Markov equivalent to (D) is called the k-essential grapt" D, shown by (D).
For example, among Markov equivalent k-closures, if a, b are adjacent only as -> b the k-essential graph will have the edge a + b. Thus, the k-essential graph will preserve the invariant arrowhead and tail marks. The difference between a b and a o is significant from causal perspective: In the former, two variables cause each other. In the latter, there is some M-Markov equivalent DAG where a, b do not cause each other and are simply not separable by conditioning sets of size most k.
For any edge type proposed the edge union definition, there are relevant instances of k-essential <- b appear in the k-essential graph. Similarly, the
graphs. In Figure? 2 the edges a bb 00- k-essential graph of in Figure Bwill will contain the edge co-od since e - d, c <- d, e ++ d are all possible edges in different Markov equivalent k-closures. Figure in Section [D3tt shows an instance where <> appears in the k-essential graph. This example also demonstrates that our representation is strictly richer than the graph union that is recovered by LOCI 23] which orients d + c, - and hence cannot distinguish them from the possible edges between e + b unlike our representation. Similarly, consider the simple graph + with is 0. Our representation yields is no DAG where u, v are confounded in any way other than the direct edge. In a triangle graph V, + v, our representation recovers uo-ov which shows there are graphs where u, o do not cause each other. LÓCI cannot make such distinction as it uses u u in both graphs.
v since there
Therefore, the variant edges that can be arrowheads or tails among different k- M-Markov equivalent graphs are replaced with circles and invariant arrowheads and invariant tails are preserved in the k-essential graph. Thus, k-essential graph captures the causal information that is preserved across all k M-Markov equivalent causal graphs. Different from essential graphs where we can test all the
'The reader will notice k-essential graph visually resembles a partial ancestral graph (PAG) (5 more than an essential graph due to the circle marks. Our choice of the name k-essential is motivated by the fact that we assume no latent confounders in the system and thus it positions work better with respect the related work.

---

Algorithm k-PC Algorithm
Input:
Observational Data, V. k. CI Tester (- IL. .I)..
Step 0: Initiate a complete graph K between with circle edges 0-0.
Step 1: Find separating sets S for every pair a, 6 V by conditioning subsets of size most
k
Step 2: Update K by removing the edges between pairs that are separable.
Step 3: Orient unshielded colliders of K: For any induced subgraph a ac-ocoob, set ao-
b-ob for any non-adjacent pair a. b where Sa.b does not contain c. See Algorithm 2 in Section
Step 4: K + FCI #CI1_Orienty Orient(K) K)
Step 5: For any node that has no incoming edges (i.e., a 6, t, 0) construct the sets B, C:
B {b E Ne(a): ao bj. C fcr Ne(a) ao oc)
and define sets B as the set of nodes that are non-adjacent to any of the nodes in C and C* as the of nodes that non-adjacent to other nodes in C::
8 {b B b, non-adjacent Ve C}. C (d' C:: dd non-adjacent vé' + c. e C}
R11: Orient ao+ b as a + b, vb E B R12: Orient co oc as a c, Vc E C*.
Output: K
conditional independence relations, existence of an arrow - b in a k-essential graph does not mean causes in every k-Markov equivalent DAG. Rather, it means that in any k-Markov equivalent DAG where a, are adjacent, a causes b.
It is worth noting that k-essential graphs are in general more informative than partial ancestral graphs (PAGs), which are defined as the edge union of all Markov equivalent MAGs, where the union of - is defined give o-0 instead of the undirected edge. Since every Markov equivalent k-closure graph is a MAG but not every Markov equivalent MAG is a k-closure graph, in general k-essential graphs may have invariant arrowheads and tails where PAGs only have circles. We call any graph that contains arrowheads, tails, or circles as edge marks a partial mixed graph (PMG).
Definition 3.17. For two partial mixed graphs A, B with the same skeleton, A is said to be subset of B, shown by S B, iff the following conditions hold for any pair a,
1. (a- A) = (a- B) 2. (a bb) = (a +
Note that asterisk x stands for a wild-card which can either be an arrowhead, tail, or circle. According the definition, any circle mark in A is also circle mark B. We have the following lemma that relates k-essential graphs to partial ancestral graphs of k-closures.
Lemma 3.18. En (D) S PAG(C& (D)).
Proof. By Theorem 3.9 every k-closure graph is MAG whereas every MAG is not a k-closure graph. Thus the set of Markov equivalent k-closure graphs form a subset of the set of Markov equivalent MAGS. Thus, the arrowheads and tails that appear all Markov equivalent MAGs must also appear in all the Markov equivalent k-closure graphs. The result follows from Definition 3.17
In the next section, we propose a sound algorithm for learning k-essential graphs from data.
4 Learning k-essential Graphs
Constraint-bard causal discovery algorithms use CI tests to extract all the causal knowledge that can be identified from data. the previous section, we proposed a compact graphical characterization of what is learnable from such statistical tests. In this section, we propose a constraint-baser learning algorithm. Since k-closure graphs are a special class of maximal ancestral graphs, we can use FCI algorithm that is devised for learning the invariant arrowheads and tails of maximal ancestral graph.
7

---

FCI algorithm is sound and complete for learning PAGs: It can recover all invariant arrowheads and all invariant tails. One might think that FCI algorithm may also be sound and complete for our task. However, this is not true. Although sound, FCI is not complete for learning k-essential graphs P
For soundness, we need the following lemma, which shows that discriminating paths do not carry extra information about the underlying causal structure.
Lemma 4.1. In any k-closure graph, if there is a discriminating path f (u, Y, and u ++ Y ++v is collider along p. then the orientations u=- Y and Y txu can be learned by finding all unshielded colliders, and then applying the orientation rules R1 and R2 of FCI.
The above lemma shows that the colliders that are part of discriminating paths can be learned by simply orienting the unshielded colliders and then applying the orientation rules of FCI. This is useful since we do not need search for colliders along discriminating paths during learning.
Our constraint- based causal discovery algorithm, called k-PC is given in Algorithm 1. It uses FCI Orient algorithm in Section B with two extra rules specific for learning k-essential graph.
Corollary 4.2. k-PC withoul Step 5 is sound and complete for learning (AG(Ca(DD) of any DAG D.
Proof. By Lemma A.18 any non-adjacent pair are separable by a set of size at most k. Thus, a valid separating set for any non-adjacent pair will be found in Step and will be used to learn the skeleton in Step 2, and to orient all unshielded colliders in Step 3. [25) proved arrowhead and tail completeness of FCI with orientation rules R.1 to R10. By Lemma
colliders on discriminating
paths will be oriented at the end of Step 4. Thus, R4 that is concerned with discriminating path colliders not applicable. Similarly, R5, R6, R7 are only applicable in graphs with selection bias. Thus, they are not applicable. Since the rules that we omit are never applicable during the execution of the algorithm, Step correctly returns the (D)) since the algorithm at that point is identical to the FCI algorithm for learning PAGs.
Definition 4.3. A distribution p is said to be f-faithful to a causal graph D = (V, E), iff (a TT blc]p implies (a b (c)n for all e C V : |c| S k.
Theorem 4.4. k-PC algorithm is sound for learning k-essential graph given conditional indepen- dence oracle under the causal Markov and k-faithfulness assumptions, i.e., if k-PC returns K, we have (D) S K S PAG((*(D))
Proof Sketch. From Corollary 4.2 K obtained at the end of Step 4 is (D)) and by Lemma 3.18 we know EN (D) S PAG(C. i.... every edge and tail orientation of K is consistent with DD. Thus, we only need to show that orientation rules R11, R12 are sound, i.c., there exists no k-closure graph in the Markov equivalence class that is inconsistent with these orientation rules. By Lemma A.2 we know that if x for some xr then conditioned on any subset of size kt there exists a d-connecting path that starts with arrow at a and x. This means that, irrespective of k. a must have some incoming edge. The rules use this fact together with the fact that if there were two incoming edges from two non-adjacent neighbors, this would create an unshielded collider, which would change the Markov equivalence class. Please see Section A.8 for the proof.
For two sample runs of the algorithm, please see Figure 5 and Figure in Section Of Appendix. Note also that our algorithm can be seen as an improved version of AnytimeFCI algorithm [18] for causally sufficient systems, which the author shows can be stopped once every conditioning set of size at most k are tested. While FCI aims at learning arbitrary PAGs partially, k-PC learns k-closure graphs for causally sufficient systems. This allows extracting more causal information, evidenced by the additional orientation rules employed by k-PC For more details on the differences and an example where AnytimeFCI is less informative than k-PC, please see Section D.7
Computational Complexity. Suppose we are given two causal graphs. Our characterization gives an algorithmic way of testing k-Markov equivalence: Construct the k-closure graphs given the two DAGS and check whether they are Markov equivalent. The step to make two variables adjacent requires one to loop through all conditioning sets of size at most k. This would take On+*). This is the main time-consuming step. Afterward, one can test Markov equivalence using the existing
It is worth noting that FCI uses undirected edges to represent selection bias. We use undirected edges for a different purpose. Thus, orientation rules of FCI aimed at orienting undirected edges should not be used here.
8

---

CDF of N-50
CDF Fl.. N-50
CDF of No50
10
0.8
0.8
0.8
0.6
0.6
kPCk=0
KFCk=0
kPC
0.4
KPCk-1
0.2
KPCk-1
0.2
kPCk-1
KPCk=2
WPCk=2
kPCk=2
0.2
0.0
0.0
0.2
0.2
0.4
0.4
0.6
(a) Arrowhead F1 Score
(b) Tail F; Score
(c) Skeleton Fi Score
CDF of FJ", No100
of N-100
CDF F?". N-100
1.0
1.0
0.8-
0.8
0.6
PC
0.4-
PC
0.4
PC
kPCk=00
KPCk=0
kPCk-0
KPCk=1
0.2
KCCk=1
02
kPCk=1
0.2
kPCk=2
KPCk=2
kPCk=2
0.0
0.2
0.6
(d) Arrowhead Fi Score
(e) Tail Fi Score
(f) Skeleton Fi Score
Figure Empirical cumulative distribution function of various Fi scores on 100 random DAGs on 10 nodes. For each DAG, conditional probability tables are independently and uniformly randomly filled from the corresponding probability simplex. Three datasets are sampled per model instance. The lower the curve the better. The maximum number of edges is 15. N is the number of data samples.
approaches. For example, 7 show that this can be done in O(ne2+n²e time, where e is the number of edges. Thus, the overall algorithm will indeed be polynomial-time when k: = O(1)
The complexity of the learning algorithm, k-PC, will be similar to Anytime FCI, an early-stopped version of FCI [18). Although this is more complicated and would depend on other parameters in the graph, such as primitive inducing paths, and thus the number and location of unobserved confounders. we can also roughly bound this by ((+++2) since for any pair, we will not be searching for separating sets beyond the (n**) subsets of size at most k. Further runtime improvements, such as RFCI by (6] might be possible, but this requires a further understanding of the structure of k-closure graphs.
Experiments
5.1 Synthetic Data
In this section, we test our algorithm against the stable version of PC algorithm in causal-learn package. We randomly sample DAGs using the pyAgrum package. Variation of this experiment with a different siffettntsspassttyy level can be found in Section a.d gives similar results. All variables are binary with conditional probability tables filled randomly uniformly from the corresponding dimensional probability simplex, except the linear SCM experiments for comparing with NOTEARS. We observed similar results with larger number of states, which are not reported. We report the Fi scores for identifying arrowheads, tails and skeleton correctly. The results are given in Figure 3 We observe that k-PC provides significant improvement to the arrowhead Fi score in the small-sample regime at little cost to the tail score. k-PC also helps improve skeleton discovery. Similar improvements are seen even for 10 samples whereas the advantage disappears for more than 500 samples (see Section E.3 since PC becomes reliable enough and k-PC does not use some of the informative CI tests that high- regime. We report combined metrics such as the sum of all F; scores in Section E.4
E.5 we compare with the conservative version of PC 14 and observe similar results. In Section E.2 we generate linear SCMs randomly and compare the performance of our algorithm with NOTEARS addition to PC. Even though NOTEARS performs slightly better than PC in general, k-PC maintains an advantage over both in the small-sampi regime. In Section E. we compare our algorithm with LOCI 23 As expected, the two algorithms perform similarly. We observe that our algorithm shows better arrowhead and skeleton F score performance. As side note, show that
In Section

---

xI
X2
X3
X
X
X6
X
(c) k-PC =
X7
X
(a) Ground Truth
(b) k-CC l
(d) Alg.
Figure 4: Causal discovery Asia dataset using 500 random samples. k-PC learn the approx- imate causal order and some edges accurately, whereas PC outputs a very sparse graph since it conditions on subsets of size which over-sparsifies the graph. For example, k-PC with k 1 can recover that X2 is an ancestor of X6. which is an ancestor of X7, whereas PC cannot.
k-PC output is at least as informative as LOCI in Section D.6 See Section further discussions. The Python code is provided at hhttps://github. com CausalML-LLbbtpP
5.2 Semi-synthetic Data
We our algorithm on the semi-synthetic Asia dataset from bnlearn repository and compare it with PC algorithm. The dataset contains 8 binary variables. We randomly sample 500 datapoints from the observational distribution and run PC as well as k-PC for gets some of the causal and ancestral relations (Figure 4 PC, on the other hand, recovers a very sparse graph as utilizes unreliable conditional independence tests with conditioning size of k-PC with A recovers graph in in-between the two, still more informative about the structure than PC.
and k: k-PC for
correctly
6 Discussion
limitation of the method is that it assumes all independence statements up to degree can be tested for some k. In some cases, the of available, the set of reliable CI statements might not have such a structure. Our method is not directly applicable in such scenarios. Another limitation that we assume that can run CI tests for the tests that are deemed reliable. This is non-trivial problem when the data is non IID, such as time-series data. We also make some other usual assumptions that commonly made in causal discovery, such acyclicity.
For more remarks, such as a demonstration of incompleteness of k-PC, please see Section
Conclusion
We proposed new notion of equivalence between causal graphs called the k-Markov equivalence. This new equivalence allows us to learn parts of the causal structure from data without relying on CI tests with large conditioning that tend to be unreliable. We showed that our learning algorithm is sound, and demonstrated that can help correct some errors induced by other algorithms in practice.
Acknowledgements
This research has been supported part by NSF CAREER 2239375. We would like thank Marcel Wienöbst for his insightful comments and suggestions on earlier version of the manuscript that led more thorough comparison with LOCI (3) We would like to also thank the anonymous reviewers for their constructive comments and feedback during the review process.
10

---

References
[1] Elias Bareinboim and Judea Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 113(27):7345-7352 2016.
[2] Facundo Bromberg and Dimitris Margaritis. Improving the reliability of causal discovery from small data sets using argumentation. Journal of Machine Learning Research, 10(2), 2009.
[3] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554, 2002.
[4] Max Chickering. Statisticallyy efficient greedy equivalence search. In Conference on Uncertainty in Artificial Intelligence, pages 241-249. PMLR, 2020.
[5] Diego Colombo and Marloes Maathuis. modification of the pe algorithm yielding order- independent skeletons. CoRR, abs/1211.3295, 2012.
[6] Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high-dimenniioal directed acyclic graphs with latent and selection variables. The Annals of Statistics, pages 294 294-321, 2012.
[7] Zhongyi Hu and Robin Evans. Faster algorithms for markov equivalence. In Conference Uncertainty in Artificial Intelligence, pages 739-748. PMLR, 2020.
[8] Steffen Lauritzen and Kayvan Sadeghi. Unifying markov properties for graphical models. The Annals of Statistics, 46(5):2251-2273 2018.
[9] Steffen L Lauritzen. Graphical models, volume 17. Clarendon Press, 1996.
[10] Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988.
[11] Judea Pearl. Causal diagrams for empirical research. Biometrika, pages 669-688, 1995.
[12] Judea Pearl and James M Robins. Probabilistic evaluation of sequential plans from causal models with hidden variables. arXiv preprint 13Xiv:1302.4977 2013.
[13] Judea Pearl and Nanny Wermuth. When can association graphs admit a causal interpretation. Selecting Models from Data: Artificial Intelligence and Statistics IV, 89:205-214, 1994.
[14] Joseph Ramsey, Peter Spirtes, and Jiji Zhang. Adjacency-faithhe faihhfulesss and conservative causal inference. In Proceedings of the Twenty-Second Conference on Unceriainty in Artificial Intelli- gence, pages 401 401-408, 2006.
[15] Thomas Richardson and Peter Spirtes. Ancestral graph markov models. The Annals of Statistics, 30(4):962-1030 2002.
[16] Rajen D. Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. Annals of Statistics, 4513):1514-1538, 2020.
[17] llya Shpitser and Judea Pearl. Complete identification methods for the causal hierarchy. Journal of Machine Learning Research, 9:1941-1979, 2008
[18] Peter Spirtes. An anytime algorithm for causal inference. In International Workshop on Artificial Intelligence and Statistics, pages 278-285. PMLR, 2001.
[19] Peter Spirtes, Clark Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
[20] Johannes Textor, Alexander Idelberger, and Maciej Liskiewicz. Learning from pairwise marginal independencies. Proceedings of the Thirty-Fre First Conference on Uncertainty Artificial Intelligence, pages 882-891, 2015.
[21] Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables. In Proceedings of the Eighteenth conference on Uncertainty artificial intelligence, pages 519-527, 2002.
11

---

[22] Tom S Verma and Judea Pearl. Equivalence of causal models. 1990.
[23] Marcel Wienöbst and Maciej Liskiewicz. Recovering causal structures from low-order con- ditional independencies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10302-10309, 2020.
[24] Jiji Zhang. Causal reasoning with ancestral graphs. Journal of Machine Learning Research, 9:1437-1474, 2008.
[25] Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17):1833-1886, 2008.
[26] Junzhe Zhang and Elias Bareinboim. Fairnsss in decision Decision-making the causal explanation formula. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[27] Kun Zhang, Bernhard Schölkopf, Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. International Conference on Machine Learning, pages 819-827. PMLR, 2013.
[28] Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Advances in neural information processing systems, 31, 2018.
12

---

Appendix
A
Proofs
In this section, we provide proofs for the lemmas and theorems the paper. We also present FCI orientation rules for completeness, demonstrate why k-PC is incomplete, and give two sample runs of the k-PC algorithm. Each subsection starts from a new page to clearly separate the proofs different lemmas/theorems.
A.1 Proof of Lemma 3.6
We will crucially use the following three lemmas prove our main results. We say collider (u. v, w) is closed, or blocks the path in context if no node in De(v) is in the conditioning set. Similarly, path is called closed it not d-connecting, and open otherwise.
Lemma A.1. Consider a DAG where X An(Y). Suppose there is a d-connecting path p between X, Y given T that starts with an arrow out of X.
1. There is least one collider along p-
2. Let K be the collider closest X on p. Then conditioning T' = T De(K) instead of T does not introduce new d-connecting paths that start with an arrowhead at X.
Proof. 1. Any path that starts with X +.... must either be directed, or there must be at least one collider along the path. Since the path is between X, Y and X & An(Y), it must be that the path has least one collider on
First note that without loss of generality, has the following form for some integer m 2 0 (m = means X + K):
+ X+U U1 - Um k
(2)
Suppose for the sake of contradiction that conditioned on T there is new d-connecting path q that starts with arrowhead into X. q clearly closed conditioned on T' and become open by us removing nodes from the conditioning set T. This can only happen if we removed some node from T that is non-collider along q. Consider the non-collider we removed that was closest to X, call this M. Thus, we have the path y that looks like this:
X W. M...Y,
for some W, where M is non-collider on this path and is in De(K).
We observe that the subpath between M and X cannot be directed from M to X. Because this would create the following cycle:
M
X U1 ... Um + K
M.
Thus closer look at the path & reveals the following structure for some integer m' and node V:
X + W1 + W2... Wm + V...M...I
(5)
We will consider the following two cases: The edge adjacent to M along the subpath between Wmn and M is a tail or an arrowhead.
Suppose the edge adjacent to M along the subpath between Wm and M is a tail: This means there at least one collider between m' and M. Any such collider must active since g is active given TV. Consider the collider that is closest to M. Since it is active, this collider must be an ancestor of T'. However, observe that is an ancestor of this collider which implies that K is an ancestor of T' as well. However, we obtained T' by removing all descendants of K from T, which is a contradiction.
This establishes that the edge adjacent to M along the subpath between W W' and M is an arrowhead, Thus, this reveals the following structure for g:
X t W1 + W2 + Wm + M M..Y
(6)

---

Suppose the directed path from K to M is as follows:
0-0 ... M
Recall that M is non-collider along q. Thus the subpath of between M and Y must start with tail as M - .... Y. Now observe that if the subpath of between M and had no collider, then we would have the following directed path from X to Y:
X + U1 + Um - K 01 + +... 0m"
- M
(8)
However, we know X is non-ancestor of Y. Thus, there must be at least one collider between M and Y along p, all of which are open given T'. Consider the collider that is closest to M. There a directed path from M to this collider, and directed path from this collider to member of T since it is open conditioned on T". But this means there is directed path from K to a member of T since there is directed path from K' this collider. This is contradiction since we obtained T by removing all descendants of K from T.
This establishes the claim that removing descendants of the collider along any d-connecting path that starts with tail at X cannot introduce a d-connecting path that starts with an arrow into X when X (Y)).
O
Lemma A.2. Consider DAG D where X & AYn and Y & An(X), X,Y are non-adjacent and k-covered. Then conditioned on any subset T : [T] S k, there exists a d-connecting path between X, Y.Y that has arrowhead at both X and Y.
Proof. For the sake of contradiction suppose, conditioned on c, there is no d-connecting path with an arrow into X and an arrow into Y. Since neither X is ancestor of Y nor Y is an ancestor of X, it must be that all d-connecting paths have colliders on them. And all such colliders must be ancestors of T.
Consider such a path where the edge adjacent to X has a tail at X. Let K be the collider that is closest to X.
Thus we have
X -
for some {U:)vem V. Since the path is open must be that K An(T). Te where De(K) are all descendants of K. Clearly, is no longer open conditioned on T". We Wn other open paths now, keeping in mind that X, Y being k-covered implies that X H Y since [T'| [T| < k.
Claim 1: Removing the descendants of the collider closest to X from the conditioning set can only add d-connecting puths that start with tail at X but no d-connecting puths that start with arrowhead
at X.
Proof of Claim 1: Since X is not an ancestor of Y, by Lemma A.I descendants of K from T' can only introduce d-connecting paths that are out of X.
we know that removing the
O
Now consider the d-connecting paths under conditioning on T'. We know that these paths must have tail either at X or at Y since started with such d-connecting paths by assumption and by Claim 1, removing De (K) from can only introduce new d-connecting paths that have tails at X. Using the fact that no path that has arrowhead into both endpoints opened, claim that we can make X, Y d-separated by removing descendants of colliders (that are closest to the endpoint that is adjacent
can recursion and
tail) of active paths, which gives the following:
Claim 2: There exists a set T of size at most such that X Y T which leads to a contradiction since X, Y are k-covered by assumption.
Proof of Claim 2: Given claim 1, we can continue removing descendants of the colliders of the active paths that are closest to the tail-end node from the set T. Either no d-connecting path is left some point in this process, or that we end up removing all the variables from the conditioning set. If the former, this is a contradiction since X, Y are k-covered. If the latter, then this is another contradiction due to the following: This means that given empty set, paths that have a tail adjacent to one of the endpoints, i.e., the paths with colliders on them (since all paths that have a tail adjacent to one of the endpoints must have a collider because X & An(Y) and Y & An(X)) are d-connecting, which is not possible. This proves Claim 2.
2

---

Due to the symmetry between X, Y, the supposition that the only d-connecting paths must have a tail adjacent to either endpoint must be wrong, which proves the lemma.
Lemma A.3. Consider DAG D where X & An(Y), X,Y are non-adjacent and k-covered. Then conditioned on any subset T [T] & k, there exists a d-connecting path between X, Y that starts with arrow into X.
Proof. For the sake of contradiction, suppose otherwise. Given T, all the d-connecting paths start with tail at X. We will show that we can find some T' of size most k that d-separates X, Y, which lead to a contradiction since X, Y are assumed to be k-covered.
Consider any path g that is d-connecting given 7 which starts with tail at X. Since X AY()), by Lemma A. Ti it must be that this path has at least one collider on Let be the collider that is closest to X. Thus we have
- - -K
for some {U: V. Since the path is open, this collider cannot be blocking the path It must be that K An).)) Let I" T De(K), where De(K) are all descendants K. Clearly, q is no longer open conditioned on TV. We investigate other open paths now, keeping in mind that X, Y being k-covered implies that ML_ Y 'T' since (T' S [T] S k.
Claim 1: Removing the descendants of the collider closest to X from the conditioning set can only add d-connecting paths that start with a tail X but no d-connecting paths that start with an arrowhead at X.
Proof of Claim 1: Since X is not ancestor of Y, by Lemma A.I we know that removing the descendants of K from T can only introduce d-connecting paths that are out of X.
Now consider the d-connecting paths under conditioning on T'. We know that these paths must have a tail at X since we started with only such d-connecting paths by assumption and by Claim removing De ( from T can only introduce d-connecting paths that have tails at X. Using the fact that no path that has an arrowhead into X, we can use recursion and claim that we can make X, Y d-separated by removing descendants of colliders (that are closest to X) of active paths, which gives following:
Claim 2: There exists a set T of size at most k such that X JL Y 1T", which leads to a contradiction since X,Y are k-covered by assumption.
Proof of Claim 2: Given claim 1, we can continue removing descendants of the first colliders of active paths that closest to X from the set T. Either, no d-connecting path is left at some point in this process or that we end up removing all the variables from the conditioning set. the former, this contradiction since X, Y are k-covered. If the latter, then this is another contradiction due the following: This means that given empty set, paths that start with tail and have colliders on them (as they cannot be directed and collider-free since X is not an ancestor of Y) are d-connecting, which is not possible. This proves Claim 2.
D.
Therefore, the supposition that all the d-connecting paths must have tail adjacent to X must be wrong, which proves the lemma.
The above lemmas will be crucial in proving Lemma 3.6 Now consider a d-connecting path between I, given e and a d-connecting path between 2, y given c. We have the following lemma: Lemma A.4. Let p be an active path between x, z given c, and q be an active path between 2, given e, where x, U, & c. If x and are d-separated given then
1. Paths p. must have overlapping nodes and
2. Y must be a collider along the concatenated path and Y & An(c).
Proof. We would like to allow the possibility that these paths might go through the same nodes. To address this, it helps consider walks.
Definition A.5. A walk on a DAG is any sequence of edges.
Definition A.6. A path on DAG is sequence of edges where each node appears at most once.
3

---

There is direct relation between active walks and d-connecting paths [8. Indeed, this relation is leveraged to efficiently check dependence using paths, rather than having search over all walks, which is much larger space.
Definition A.7. A walk between two nodes a, b is called active given e each collider along the walk is in and each non-collider is not in
Definition A.8. A path between two nodes a, is called open given e if each collider along the path is in An(c) and each non-collider is not in
Consider an active walk where node appears multiple times. Observe that must appear with the same collider status, since otherwise the walk would not be active. If the appearance is of the form
then there must be collider that is in between the two appearances of t's. We can skip the intermediate subpath between the two appearances of t's obtain the walk
a... 2
(10)
Since there is least one collider that is in e along the skipped subpath, we have that t E An(c). Therefore, will not be blocking the path that is obtained after repeatedly applying this and other shortening steps. If the appearances of the form:
...b,
a..
(11)
we can similarly skip the subpath between the two appearances of t's obtain the shorter walk
....,
a
(12)
and repeat this process until not repeated. The resulting walk/pathh is still open since t will appear in the same collider status, namely as a non-collider and if it was not blocking the walk, it will not be blocking the path either. This argument holds for any configuration where is non-collider. the appearances is of the form:
Q.. S + + ...6.
(13)
then it must be that / E e, and thus the walk obtained by skipping the subwalk between the two appearances of ('s, i.e.,
S 2
(14)
must be d-connecting.
This shows that each active walk corresponds d-connecting path and vice verse. Now we can proceed with the proof of the lemma:
1. Suppose p, q have overlapping nodes. Let wp be the walk that corresponds to and w, be the walk that corresponds to q. Consider the concatenated walk w Wp, Wy- If any repeated node has different collider status along w, then the path is not active. But this means that that node was blocking either Up or Wy. which would be a contradiction. Therefore, repeated nodes cannot have different collider status along
Suppose a node is repeated in wp and wy and has the same collider status. this case, consider the walk obtained by concatenating the sub-walk of Wip between æ and i, with the sub-walk of w. from / to y. By repeating this process for any repeated node, we can obtain a path that corresponds to this walk, which would always be active since the repeated nodes have the same collider status along this path that they had in Wp or Wi and were not blocking these walks. Therefore, they cannot block the concatenated path obtained this way either, which is a contradiction since we given that 2, y d-separated given c. Therefore if any node is repeated in Wp and Wy then the concatenated walk is always active. Thus, must be the that there is repeated nodes.
Since there is no repeated nodes from 1., we can operate at the path level instead of considering walks. Suppose Y is not collider. Since Y & it would be d-connecting and thus the concatenating path would be d-connecting, a contradiction. Suppose Y is collider but Y E An(c). In this case, Y would not block the concatenated path either, which is contradiction. This establishes the result. D

---

The next lemma shows that colliders that are closed in D must remain closed in the k-closure C2 (D).
Lemma A.9. If collider is blocked in D conditioned on some c |c| S k then it must also be blocked in (D) conditioned on c.
Proof. Suppose (X + Y)D is a collider that blocked given c. Thus, must be that Z & An(c) in D. For the sake of contradiction, suppose that this collider is unblocked in Cx (D). Thus, it must be the case that Z E An(e) in (D) This means there is a new directed path from Z to c c C& (D). If this path existed in D, the collider would be unblocked, which is a contradiction. Thus, at least one of the edges along this path must have been added during the construction of C& (D). Consider the collection of edges on this path that do not exist in D. Note that by construction of CD),), a directed edge a + added between k-covered pair a. B only if there is directed path from to 3. Consider the path obtained by replacing the directed edge between any k- e-covered pair along this path with the corresponding directed path in D. The resulting directed path must be in D. This shows that there was at least one path already in D that implied Z E An(c), which is contradiction. Therefore, any collider in p that is unblocked in (D) must also be unblocked in D.
Lemma A.10. The set of ancestors of any set e of nodes in CD) are identiaal the set of ancestors of in (D).
Proof. Adding edges to a graph, directed or bidirected, cannot decrease the set of ancestors of any node. We only need to show that the set of ancestors in CD) not larger than the set of ancestors in D.
Suppose otherwise: A node a E An(e) in C& but a & An(e) in D. This can only happen if collection of edges added during the construction of (D) render a an ancestor of c. However, each such edge is added only if there is directed path between its endpoints in D. Consider the path obtained by replacing each such added edge along the path that renders a an ancestor of in C2 (D) with the corresponding directed paths in D. This directed path must be in D, which means that a was an ancestor of c in 1) as well, which is a contradiction.
We are finally ready for the proof of Lemma 3.6
Proof of Lemma 3.6
Since no edge is removed during the construction of the k-closuue, one direction immediately follows: If a IL b bec in C2 (D), then a IL blc in D. The implication is clearly true for any set of size at most k as well. Therefore we only need to show the other direction.
Suppose a _II. ble in D where |c] S k. We will show that a .II b |c in CD). For the sake of contradiction, suppose otherwise. Then there must be a d-connecting path p between a, b given in (D). The length of any such path must be greater than since otherwise, whether this edge already existed in D was added during the construction of C2 (D), a, must have been dependent given in D. which is a contradiction. Since the orientation of the existing edges in D) did not change in C& (D), either this path did not exist in or that it existed but was blocked by some collider that is not in An(c) in D. The latter is not possible due to Lemma A.9 since any unblocked collider in (D) must also be unblocked in D. Thus, it must be that this d-connecting path did not exist in D.
Suppose p does not exist in D. At least one edge must have been added to form this path in Cs during the construction of C& (D).
For any added edge u + v, the following is true: Since u + v was added in Cx( it must be the case that v & An(u) since otherwise there would be a cycle. By Lemma A.3 conditioned on c, there exists a d-connecting path between u, v where the edge adjacent to e is into v. For any added edge ++ the following is true: Since <+ was added in C2 (D), it must be the case that & An(v) and v & An(u). By Lemma A.2, conditioned on c, there exists a d-connecting path between u, v where the edge adjacent to into u and the edge adjacent to is into Call any such path implied by these lemmas a replacement path. Note that replacement path might be directed or not.
Consider path g in D that is obtained from p by switching the edges added during the construction of (D) with the replacement paths using the following policy: Suppose u -> v in C2 (D) for some k-covered pair u, v. If directed path is open given in D, use that path the replacement path
5

---

for the edge + b. If not, use any other path. This means that either the path that replaces an edge - u is directed or that both the endpoints have an arrowhead and that An(e).
Observe that each replacement path is d-connecting and the subpaths of that remain intact in must be d-connecting since p is d-connecting. By Lemma A.4 any two paths whether it is pair of replacement paths or replacement path and subpath of p have overlapping nodes, then their concatenation must be d-connecting. Since assumed that q was not d-connecting, it must be that one of the endpoints of one of the added edges must be blocking q. We investigate each such node to verify that q is indeed d-connecting to arrive a contradiction.
In other words, the collider status of some of these nodes must have changed due to replacing some edges with replacement paths. Specifically due to Lemma A.4 one of the endpoints of replacement paths must be a collider and not an ancestor of c. Since ancestrality status cannot change from D to (p) due Lemma A. the only way for q to not be d-connecting is if some node that is not an ancestor of e changes status from being a non-collider along to being a collider along 4-
Note that for an edge u u, the nodes and are adjacent to an arrowhead in the replacement path. Thus, some node changes collider status in compared to p, it cannot be due bidirected edges along
Now consider the directed edges u v. the replacement path is directed from u to u, similarly is adjacent to a tail and is adjacent to an arrowhead on the replacement path. Therefore, such edges cannot alter the collider status of nodes the junction of different paths. Finally consider the directed edges - u where u and u are both adjacent to an arrowhead on the replacement path. Observe that this edge cannot change the collider status of We now focus on u. If the other edge adjacent along q is tail, remains a non- non-collider and cannot block q. Now suppose the other edge adjacent to u along g is an arrowhead. This makes u collider in whereas u was a non-collider along p since along p. However, by construction of g, we ended up adding a path with arrowheads
we had u at both endpoints, must be that the directed path between u, V (which exists since u - v was added An(c) which
during the construction of C₁ D)) must be blocked via conditioning. This means means that although the status of u changes from non-collider to collider, it must that this collider does not block g since it is an ancestor of Therefore, replacement path can alter the status of node to block the path q, and g must be d-connecting, which contradicts with the assumption that the path was not d-connecting in D)
This establishes that any d-connecting path in C2 (D) also d-connecting in D, which establishes that if ML 6 lc in (D). then a J. ble in D. This establishes the lemma.

---

A.2 Proof of Lemma 3.8
For mixed graph be maximal ancestral graph, we need to show that it does not have directed or almost directed cycles and that any non con-adjacent pair of nodes can be made conditionally independent by conditioning on some subset of observed variables [24] We first define almost directed cycle, and propose a lemma that shows that k-closure graphs do not have directed or almost directed cycles.
Definition A.11 (24). directed path from to b and the edge a t+ is called an almost directed cycle.
Lemma A.12. For any DAG D, and integer k. CD( does not have directed or almost directed cycles.
Proof. Suppose, for the sake of contradiction that there is directed cycle in (D). Since each edge X - Y in (D) either exists in or for each such edge in C₂(D), there is a directed path from X to Y in D, existence of directed cycle in (D) would imply directed cycle in D, which contradicts with the DAG assumption of D.
Suppose, for the sake of contradiction that there is an almost directed cycle in C2 (D), i.e., we have directed path from a to b for two nodes a ++ b. Since a ++ is added during construction Cx(( (D), must be the case that neither nor b are ancestors of each other. However, from the above argument, there must directed path from a to b D, which is contradiction. Thus, Cx (D) cannot have almost directed cycles.
The other condition for a mixed graph to be a maximal ancestral graph is that for any non-adjacent pair of nodes, there exists subset of the observed variables that make them conditionally independent. For the k-closure graphs, this simply follows by construction: Any pair of nodes that are non-adjacent in C&(D) (D) can be made conditionally independent given some of size most & in D by construction of (D). From Lemma 3.6 this conditional independence relation must be retained in CD(D). Thus any non-adjacent pair of nodes in Cs (D) can be d-separated in Cj (D) by some conditioning set of size at most k. This establishes the claim.

---

A.3 Proof of Theorem 3.9
Our main observation is that parallel of Lemma A.2 works for MAGs with k-covered bidirected edges. The following lemmas are for any mixed graph K. that satisfies the constraints in Theorem 3.9 i.e., those that are MAGs and that satisfy the condition that for any bidirected edge a b. a, b are k-covered in the graph K. - (a < b).
Lemma A.13. Suppose X & An(Y), Suppose there is a d-connecting path p between X, Y given T that starts with an arrow oud of X.
1. There is at least one collider along
2. Let K be the collider closest to X on p. Then conditioning on T = De(K) instead of T does not introduce new d-connecting paths that start with an arrowhead at X.
Proof. 1. Any path that starts with X + must either be directed, or there must be at least one collider along the path. Since the path between X, Y and X AY(Y), it must be that the path has at least one collider on it.
2. First note that without loss of generality, has the following form for some integer 2 0 (m 0 means X + K);
X+ U2... Un K +
(15)
is wildcard representing either an arrowhead or tail.
Suppose for the sake of contradiction that conditioned on T', there is new d-connecting path q that starts with an arrowhead into X. was clearly closed conditioned on T and became open by us removing nodes from the conditioning set T. This can only happen if removed some node from T that is a non-collider along q. Consider the non-collider we removed that was closest to X, call this M. Thus we have the path q that looks like this:
X * X M...Y,
(16)
where M is a non-collider on this path and is in De(K).
We observe that the subpath between M and X cannot be directed from M to X. Because this would create the following cycle, since K is assumed to be the first collider along p. and an ancestor of M.
M
X + U....U, Um + K ... M.
(17)
Thus closer look at the path g reveals the following structure for some integer m' and node V:
X + W1 + W2... + W M...M..Y
(18)
We will consider the following two cases: The edge mark adjacent to M along the subpath between Wm and M is a tail or an arrowhead.
Suppose the edge mark adjacent to M along the subpath between Wm and M is a tail: This means there is at least one collider between Wmn and M. Any such collider must be active since q is active given T'. Consider the collider that is closest M. Since it is active, this collider must be an ancestor of T'. However, observe that is an ancestor of this collider which implies that K is an ancestor of T' well. However, obtained T' by removing all descendants of K from T, which is a contradiction.
This establishes that the edge mark adjacent to M along the subpath between Wm and M is an arrowhead. Thus, this reveals the following structure for q:
X -
W W2 W
M...
(19)
Suppose the directed path from K to M is as follows for some {0, )s for some integer m":
K ...00m + M
+ ...
(20)
Recall that M a non-collider along q. Thus, the subpath of a between M and Y must start with tail as M ....& Y. Now observe that if the subpath of p between M and Y had no collider, then we would have the following directed path from X Y:
X + Ui ..... Um + K + 0 + ... 0mn + M + +.... +Y
(21)
8

---

However, we know X is non-ancestor of Y. Thus, there must be at least one collider between M and Y along p. all of which are open given T". Consider the collider that is closest M. There is a directed path from M to this collider, and a directed path from this collider to member of TV. But this means there is directed path from K to member of T' since there is directed path from K to this collider. This is contradiction since we obtained T" by removing all descendants of K' from T.
This establishes the claim that removing descendants of the collider along any d-connecting path that starts with a tail at X cannot introduce a d-connecting path that starts with an arrow into X when X & AY(Y).
The following is the parallel lemma to Lemma A.2 for any mixed graph K that satisfies the conditions of Theorem 3.9
Lemma A.14. Consider bidirected edge X + Y in K. Suppose conditioned on any subset T : [T] S k X PL Y in G (X ++ Y). Then conditioned on any T (T] I k, there exists d-connecting path between X,Y Y. that starts with an arrow into and an arrow into Y.
Proof. For the sake of contradiction suppose, conditioned some T [T] k, there is d- connecting path with an arrow into X and an arrow into Y. Since neither X is an ancestor of Y nor Y is an ancestor of X, all d-connecting paths must have colliders on them, And all such colliders must be ancestors of T"
Consider such path p where, without loss of generality, the edge adjacent to X has tail at X. Let K be the collider that is closest to X.
Thus we have
X U1 +... Um +
(22)
for some {Ua)e, V and integer m. Since the path open, this collider must be unblocked. must be that K E An))). Let T' = T De( K), where De(K) are all descendants of K. Clearly, is no longer open. We investigate other open paths now, keeping in mind that X, Y are dependent given T since [T' S k.
Claim 1: Removing the descendants of the collider closest X from the conditioning set can only add d-connecting paths that start with a tail at X but no d-connecting path that starts with an arrowhead at X.
Proof of Claim 1: Since bidirected edge exists between X, Y, and that K is MAG, neither X nor Y are ancestors of one another, since then we would have an almost directed cycle. By Lemma/A.13 we know that removing the descendants of K from T can only introduce d-connecting paths that out of X.
Now consider the d-connecting paths under conditioning on T'. We know that these paths must have tail either at X or at Y. Using the above claim that no path that has an arrowhead into both endpoints are opened, we can use recursion and claim that we can make X, Y d-separated by removing descendants of colliders (that are closest to the endpoint that is adjacent to a tail) of active paths, which gives the following:
Claim 2: There exists set T of size at most k such that X TL Y [T" which leads to contradiction since X, Y cannot be made independent by conditioning on sets of size most by the assumption.
Proof of Claim 2. Given claim 1, can continue removing descendants of the colliders of the active paths that are closest to the tail-end node from the set T. Either no d-connecting path is left at some point in this process, that we end up removing all the variables from the conditioning set. If former, this is a contradiction since X, cannot be made conditionally independent given empty set. If the latter is true, then there is another contradiction due the following: This means that given empty set, paths that have a tail adjacent to one of the endpoints, i.e., the paths with colliders on them (since all paths that have tail adjacent to of the endpoints must have collider because X & An(Y) and Y & An(X)) )) are d-connecting, which is not possible. This proves Claim 2.
Therefore, the supposition that the only d-connecting paths must have a tail adjacent to either endpoint must be wrong, which proves the lemma.

---

Proof of Theorem 3.9 Now, we are ready to prove the main characterization theorem. We will need the following lemma:
Lemma A.15. Let K. be a mixed graph that satisfies the conditions in Theorem 3.9 Let K' be the graph obtained by removing all the bidirected edges from K. Then
1. K' is a DAG and
2. I'' ~ K.
Proof. Since the only difference between K' and IK is the removal of bidirected edges, any directed cycle that exists in K' would also have existed in K, which contradicts with the assumption that K is MAG. This establishes that KK has directed cycles.
Clearly, any independence statement K. holds in KK, since it obtained from K. by removing edges. Thus any degree-k d-separation relation that holds in IK also holds in IK' Therefore, we only need to show that for any c of size at most & (a K. 6 (c)x implies (a 1 6 l)))..
Suppose for the sake of contradiction that a J |e in K. but JL ble in K'. Let p be a d-connecting path between a, given in IK. This path must be closed K'. Since the only difference between the two graphs is the removal of bidirected edges, ancestrality relations cannot be different. Thus, it cannot be the case that a collider that was open in IK is now closed in K' and is closing the path p. Any collider that was open must still be open. Thus, the only way for p to be closed in K' is if some bidirected edge X <+ Y along p removed. However, by Lemma A. for any such bidirected edge in K, and for any conditioning set of size at most we have d-connecting path called replacement path with an incoming edge to both X and Y. Consider the path obtained by replacing every bidirected edge along p with corresponding replacement path. Since b are d-separated by assumption, this path cannot be open. As this path a concatenation several d-connecting paths either sub-paths of p, which must be open, or replacement paths which must be open, by Lemma A.4 they must have no overlapping nodes, and some node at the junction of these paths must be collider and non- -on-stccstor of c. However, since
replaced bidirected edges X <+ Y with paths of the form X + * + Y. both X and must have the same collider status on both p and q. Thus, they cannot be blocking 9 since they are not blocking p. This means that is d-connecting in K', which is a contradiction. This proves the lemma that KK and K' must entail the same degree-k d-separation relations, which implies they are M-Markov equivalent.
The only if direction: Suppose a mixed graph is a k-closure graph, i.e., K- Cx() for some DAG D and has the edge <> b. Suppose for the sake of contradiction that a, b K - (a ++ b). Let K' be the graph obtained from K. by removing all the bidirected edges. Note that K' is DAG since K has no directed cycles. Also note that all edges in D must appear in K' by construction of k-closure graphs. D can therefore be obtained from K by removing edges. Thus, any d-separation statement K. must also hold in D. Therefore, a, must be conditionally independent given some subset of size at most l in D. This means K, in which a, b are adjacent, cannot be the k-closure graph of D, which is a contradiction.
k-covered in
If direction: any such mixed graph K, there is DAG whose k-closure is I, which shows that any such IK is valid k-closure graph, proving the theorem.
Suppose a mixed graph IK satisfies the conditions in Theorem 3.9 By Lemma A.15 for
10

---

A.4 Proof of Lemma 3.12
be two k-closure graphs with the same skeleton and unshielded colliders. Suppose for the sake of contradiction that there is path p that is discriminating for a triple (u, Y, 2) in both such that Y is a collider along p Cj (D1) and non-collider in C₃ (D2). Thus, in
Let K1 =
(P) we have the path p as
a
+ 7m + u ++ Y +
(23)
where 24 - U, Vi and u + and a, U are non- non-adjacent. Note that we cannot have Y <- u instead of Y ++ U since this would create the almost directed cycle u + Y t The same path with Y' as a non-collider can take two configurations in C2 (D2), either as
a+ ž1 ++ 22
++
+ 7m u ++ Y +
(24)
or as
a ++
++ 2m + u t- Y +
(25)
Other paths where Y is a non-collider would either render u a non-collider, which cannot happen by definition of discriminating path, create directed or almost directed cycle. Since a, are non-adjacent by definition of a discriminating path, there must be some S : |S] < k where (a TT v (S) (Dz)- Note that S must include all 2 is and u, and not include Y since otherwise there would be d-connecting paths between a, v in C2 ( (D)) due to the discriminating path. This means that (L v v (Dz)
Since <> Y in (Di). by Lemma A.2 there must be d-connecting path between u, Y in D1 conditioned on S that has an arrowhead at Y. By construction, this path must also appear in C2 (D)). Since the path is inherited from DI, it does not have bidirected edges. Consider the shortest of all
such d-connecting paths, call this path q. Let X be the node adjacent to Y along Thus, has the form
U + -
(26)
We have that X + Y in both Dj and C2 (D)) In (DL), we have X + Y <> v. Since the edge between Y, v has tail at Y in C. (D2). this collider cannot exist in C2 (D2). Thus, it must be the case that this collider is shielded in C2 (D)), i..., X' and v are adjacent in C2 (D)). Since C2 (&,)). have the same skeleton, they must also be adjacent in (D2).
Now consider the path obtained by concatenating the subpath of + u, and the subpath of between u and X, and the edge between X and v in C2 (D1). Call this path r. Note that the subpath of q is d-connecting given S, as well as the subpath of p since 2, 's and u are in S. Thus, unless X is collider on it, the path between a, v will be open, which would lead to a contradiction since a, are d-separated given 5 in C. Bx(i,, (D:). Thus, the edge between X, v must have an arrowhead at X. Let W be the node before X along q- Thus have W + X < in (D2)) Note that X <- is not possible since this would create an almost directed cycle X + Y + v + X in Co (D)).
Suppose this collider is unshielded and appears in Cx in (D2), we have Y - U* > X <-W. Since X,Y are adjacent, it must be that X ( Y or X ++ Y to avoid directed or almost directed cycle. Thus in (D2), we have X <+Y. However, this creates the collider W*-> X <+Y in Cx( Note that this collider cannot appear in (Dz) since the edge between X, has a tail at X in (D)).. Thus the collider must be shielded, meaning that W, Y must be adjacent, and both in C& D2) and in (Dz). Since we have W + X + Y in (Di), the edge must be W - Y in C& (ii). Furthermore, similar to X, W cannot be in the conditioning set since this would block the path q. This means there is a d-connecting path that has an arrowhead at Y that is shorter than q, which is contradiction.
well: W X ++ in Cx Thus
Thus the collider W + X ++ e in (D1) must be shielded. Similar to the above argument, W must be a collider along the path constructed by concatenating the subpath a=-> ... of p, and the subpath of q between u and W, and the edge between W and v since otherwise this path would be open, which would contradict with IL S. Let V be the node next to W along g. Thus we have V + W + X along q and V + W + is a collider in C. (D,). In fact, it must be that W ++ v since otherwise there would be almost directed cycle u - W X Y +> in (D1).
Suppose the collider V - W < e in (Di) is unshielded and also appears in Ce (D2). Note that V. X were adjacent in (D1), the orientation would have to be as V*-> X since otherwise there
11

---

would be directed cycle V + W + X - V in C.(D)). But this would imply that there is shorter path than g that connects u, and has an arrow into Thus, V. X must be non-adjacent in (x(P)) and hence in C2( (2).. Thus, (V, W. X) is an unshielded non-collider in C& (D1) and must also be in (D)). Thus it must that W - in (D2) Since us uw W - X in C& (D2), must be that vs X in (x2)) to avoid directed or almost directed cycle. Since Y + we-> X in C2 (D2), it must be that f+Y to avoid cycle or almost directed cycle in C. (D2). However, now we have a collider W - X ++Y in (D2) that is non-collider in Cx(Di) since in (Di) we have X + Y. Thus, this collider must be shielded, i.e, W.Y must be adjacent C2 (D2). Thus, they must also be adjacent in C2 (D1). Since W - X Y in C& (D1), it must be that W + Y in C& (D)) to avoid a cycle. But this means there is shorter d-connecting path between u, Y given S with arrowhead at Y. which is contradiction.
Therefore, the collider V W ++ must be shielded in C2 (D1). We can repeat the above argument as many times as needed continuing from the parent of V along q. As we keep shielding more and more colliders in C2 (D eventually when we shield the first node along q next to u, we will end up with directed path from u to Y. However, this is contradiction since bidirected edge was added between u, which implies that u is not an ancestor Y.
Therefore, two k-closure graphs (D2), C. (D2) have the same skeleton and unshielded colliders, then they cannot have different colliders along discriminating paths, which proves the lemma.
12

---

A.5 Proof of Corollary 3.13
(=) If they are Markov equivalent then by Lemma 3.8 they are two Markov equivalent MAGs. Therefore by Theorem 3.11 they have the same skeleton, and the same unshielded colliders.
(+) If they have the same skeleton and the same unshielded colliders, then by Lemma 3.12 they must have the same colliders along discriminating paths. Thus, by Theorem 3.1 they are equivalent.
13

---

A.6 Proof of Theorem 3.14
(=) Suppose D1, D2 are M-Markov equivalent. For the sake contradiction suppose that C& (D1) and Cs (D2) are not Markov equivalent. By Corollary [.13 this happens when either they have different skeletons, or different unshielded colliders. Thus, there are two cases:
k-closures have different skeletons: (D)) and (2 have different skeletons. Suppose without loss of generality that Cs (1) has extra edge, i.e., a, b adjacent in C& (Pi) but not in C& (2)) This can only happen if 3S C V |S| s such that (a 11. b b Dy, while there is no such separating set in Dj, implying that (a (8)) D. This is a contradiction with the supposition that D1, D2 are k-Markov equivalent. Therefore, C& (D1) and C2 (D2) must have the same skeletons.
For completeness, restate the definition of unshielded collider in k-closure graphs, which is identical to how it defined in MAGs.
Definition A.16. triple (a, c, b) in k-closure graph is called an unshielded collider if a, b non-adjacent, a, and b are adjacent and the edges adjacent to c have an arrowhead mark at c.
According to the definition, triple (a, c, b) in a k-closure graph Cs (D) can be unshielded collider the induced subgraph on the nodes take either of the following configurations:
1. c
2. a -
3. a + c
4. a
We use asterisk to represent either an arrowhead or tail. +-+ represents either -, ++. Similarly, ++ represents either ++.
k-closures have different unshielded colliders: Without loss of generality assume that (a+ -> < (D)) but this unshielded collider does not exist in (D2), i... (a, b) is unshielded non-collider in (D2).
Lemma A.17. k-closure graph CD(D), two nodes a, are non-adjacent iff (a OlS))..(D) for some S C V.
Proof. Suppose a, b are non-adjacent in C₃ (D). Thus must be the case that (a TL b b)$), for some S such that [S] < k, since otherwise a, would be made adjacent during the construction of CD( By Lemma 3.6 this means (a TT b b|$) (D)) This establishes the only direction.
(+) Suppose now that (a IL (D)) By definition of d-separation, adjacent nodes cannot be d- d-separated and thus a, must be non-adjacent in Cx(D).
Lemma A.18. In a k-closure graph C&(D), any pair of non-adjacent nodes b are separable by set of size at most k ie., ES |S| & k, b blS)).(()
Proof. Suppose otherwise: For some non-ace adjjaaeacent pair a. b all d-separating sets in CD have size greater than k. Let S be the smallest subset that makes b d-separated, i.c., (a IL b|S )c, (D) one exists by Lemma 1. Clearly, |S| > k. Note that non-adjacency of a, b in C2 (D) implies that a, are separable in D with some set T' of size most k: (a IL b p. Since [2'] S is the smallest subset that d-separates a, in (D). it must be that (a K. blT)). However, this contradicts with Lemma 3.6 which says that D and (D) must entail the same d-separation constraints for conditioning sets of size up to k.
|S| and
Since a, are non-adjacent in both graphs, by Lemma A.18 there are two subsets S1, S2 of size at most k such that
(a IL b|St (CL(D.) (a IL b|S2 (c.(D))-
(27)
Clearly, S1 c, S2 3 e since e is a collider between a, in C2 (D1) and a non-collider in (D2). If switch the conditioning sets, due to the different collider status of e in both graphs the d-separation statements will switch to d-connection statements:
(a )..()))))))))))))))))))))))))))) (a b bl5a (C.)
(28)
14

---

Since S1 and Sy have size of at most k, then from Lemma 3.6 we have that:
(a TL b Dr, (a fr. b blSi). D,
(29)
This implies that D1, D2 are not k-Markov equivalent which a contradiction.
This establishes that if D1, D2 are k-Markov equivalent then (o(D)),C((D) must have the same skeleton and the same unshielded colliders. By Corollary 3.13 Cx are Markov equiva- lent.
(+)
Suppose that (x) and (D2) are Markov equivalent. Then they impose the same d-separation statements. Therefore they impose the same d-separation statements when the conditioning set is restricted to size most By Lemma 3.6 this means that D1, D2 must also impose the same d-separation statements for conditioning sets of size of at most k. This establishes that Di, D2 are k-Markov equivalent.
15

---

A.7 Proof of Lemma 4.1
Suppose in the k-closure graph (D) for some DAG and integer k. we have discriminating path for Y between the nodes a, u of the form
a+ + u e
By definition of discriminating path, must be collider along the path, and - v. If Y + c, then we would have an almost directed cycle w - u + Y <+ u. Thus, we have ++ Y <+ v.
First, we show that the arrowhead at Y of the edge Y + can be learned by first orienting unshielded colliders and then applying R1 and R2. Consider the bidirected edge u ++ Y. By definition of discriminating path a, must be non-adjacent and thus separable by set of size most & by Lemma A.18 Therefore, we have a set S |S| S & such that a 1L v S. By the discriminating path definition, every collider along the path must be parent of and therefore it must be the case that every collider along the discriminating path including u must be in S, since otherwise there would be d-connecting path. From Lemma A.2 conditioned
any set of size at most k we have d-connecting path that starts with an edge into Y. Consider the shortest such path q. Let X be the node immediately before Y along y- Since this path exists in the DAG by the lemma, we have X - Y. If X, non-adjacent, then + Y <> would be an unshielded collider and we are done.
adjacent. Note that conditioned on S, and X are d-connected. If X is non- collider along the path obtained by concatenating the subpath of q between a, XX and the edge between X, u. then a, would be d-connected given 8, which is contradiction. Therefore, X must be collider along this path. Thus we have X + v. Note that we cannot have X + e since this would create almost directed cycle in C& (D). Let V be the node immediately before X along q. Thus have -X + v (not V + X since this edge exists in D).
Suppose X,
Suppose V, are non-adjacent. Thus, the collider V + X <+UU is unshielded, and therefore can be learned. Furthermore, V, Y must be non-adjacent since otherwise, we must have V - to avoid a cycle and there would be path that is shorter than q. which "jumps over" the node X along Thus, we can learn that + Y from R1. Finally, since now we have learned u= X + Y and that Y, v adjacent, by R2, must have Y <+v. Thus the arrowhead mark at Y of the edge Y ++ can be learned, and we are done.
Suppose V, are adjacent. Following a similar argument, we either have some unshielded collider that can be propagated using the argument above to orient Y <- or we can continue covering unshielded colliders, which would imply the previous nodes are always parents along But this implies that has a directed path to Y, which cannot happen since we have u ++ Y in CD) This establishes that Y <-x can be learned by orienting unshielded colliders and applying the rules R1 and R2.
For the arrowhead mark at Y of the edge u + Y, similarly consider the shortest d-connecting path q between Y, v in D given S that starts with an arrow into Y. The argument follows similarly that either there would be directed path from v to Y, which is a contradiction with the existence of the edge Y ++ in the k-closure graph, or that there exists an unshielded collider along that can be learned by orienting unshielded colliders, which can be propagated to learn u+ Y using rules R1, and R2, This establishes the lemma.
16

---

A.8 Proof of Theorem
We show soundness of the two new rules with the following two lemmas:
Lemma A.19. Let K be mixed graph that is sandwiched between (D) and PAG(C&(D)), i.e. (D) S K S PAG(C&(D)) R11 is sound on K for learning the k-essential graph, i.e, if K" -RI1(K),, then (x( CKCCK'
Proof. For the sake of contradiction, suppose otherwise: R11 orients an edge ao- b in K as + b. and there is DAG D' with a k-closure graph (D") that is Markov equivalent to (D) and is consistent with K where ++ b. This means a, b are k-covered in D'. Then from Lemma A.2 conditioned on any subset S of size at most there must be d-connecting path that starts with an arrow into both and in D. By construction of the k-closure graph, this path must also exist in Cg (D').. Therefore, there must be some node w such that a <- w. Since a has no incoming edges, it must be the case that w E C. However, b is chosen so that b is non non-adjacent to any node in Therefore, b must be non-adjacent to w K. However, this creates the unshielded collider w - ++ b. However, note that w0-0000+ b in PAG(C, D)), and thus (w, a, b) is non-collider in CD)) Therefore, (D') cannot be Markov equivalent to (D), which is contradiction. L
Lemma A.20. Let K be mixed graph that is sandwiched between ex and PAG(Cx i.e. (D) C K S (D)))((D). R12 is sound on K for learning the k-essential graph, i.e. if K' -R]((K), then (x(e) K' C.
Proof. For the sake of contradiction, suppose otherwise: R12 orients an edge ao-oc in K as a-c, and there is DAG D' with a k-closure graph (D') that is Markov equivalent to C2 (D) and is consistent with K where ++ c. This means are k-covered in D'. Then from Lemma A.2 conditioned on any subset S of size most k, there must be a d-connecting path that starts with an arrow into both and in D. By construction of the k-closure graph, this path must also exist in Cx')") Therefore, there must be some node w such that a +- w. Since a has no incoming edges, must be the case that E C. However, c is chosen so that e is non-adjacent to any other node in C. Therefore, e must be non-adjacent to w in K. However, note that wo wvo-oao-60 in PAG and thus (w, a, c) is non-collider in (D). Therefore, C2 (D") cannot be Markov equivalent to C2 (D). which is a contradiction.
Now consider the execution of the algorithm k-PC When the algorithm completes Step 4, from Corollary 4.2 we have that K = (D))., Since we start Step 5 with K = (A, (D)), from Lemma A.19 and A.20 any arrowhead and tail orientation of the K obtained the end of step must be consistent with the k-essential graph of D. Therefore, we have that & (D) C K.
17

---

B FCI Orientation Rules
Algorithm 2
Input:
Mixed graph K
Apply the orientation rules of R.1, R2, R3 of 25 to K until none applies.
Apply the orientation rules of R8, R9, R.10 of 25
Output:
We restate the FCI orientation rules in detail and demonstrate how they are applicable for learning k-closure graphs. The following definitions are from [25]
Definition B.1 (Partial Mixed Graph (PMG)). Any graph that contains the edge marks arrowhead, tail, circle is called a partial mixed graph (PMG).
Definition B.2 (Uncovered path). In PMG, path (u1, Ug........ ... um) is called an uncovered path if M4 4442 are non-adjacent for all i E {1,2, (1.2 m2
m
Definition B.3 (Potentially directed path). a PMG, a path (u1, ug... un) is called a potentially directed (p.d.) path if the edge between u, and 1441 does not have arrowhead u, for all i E {1,2, m7 1}.
Definition B.4 (Circle path), In a PMG, path (ui.... is called a circle path if u,0-ou44 for all i (1, m.
Note that circle paths are special cases of p.d. paths.
Rules 1, 2, are straightforward extensions of the orientation rules for constraint- based learning to mixed graphs. For completeness, we restate them below. The star marks that appear both before and after the application of the rules are edge marks that remain unchanged by the rule.
RI: If a+- bo-* c, and a, are not adjacent, then orient the triple as a+ c.
R2: a + b-- c or a=> + e and a =coc, then orient * Oc as a+ c.
R3: If a=-> b +c, odo
are non-adjacent, and db then orient d are d*-> b.
We now restate FCI+ rules R8, R9, R10 and explain their relevance for learning k-closure graphs. Note that the rules are simplified since we do not have undirected edges that represent selection bias, and our undirected edges treated as if they circle edges.
R8: If + b > and ao e, orient ao- c as
R9: If aoo+ c, and = (a, b, U2 Um, c) is an uncovered p.d. path from to such that 6, non-adjacent, then orient ao- c a
R10: Suppose ao-> c, + c, d + C, Pr is an uncovered p.d. path from a to d and p2 is an uncovered p.d. path from b. Let ta be the node adjacent node adjacent to a on Pa (t, can be c). ta, te are distinct and non-adjacent, then orient ao- > c css
pı (ta can be d) and f, be the
C.
R11 and R12 cannot replace any the above rules. For example, consider Figure 5) None of the FCI rules apply to the output of Step 3, thus we can only learn of the unshielded colliders at the end of Step 4 of the algorithm. The completeness of FCI implics that any edge xo~> y can be oriented as y and give MAG consistent with the PAG. However, not all such MAGs are valid k-closure graphs. R.1 can be applied to orient several tails, which gives the graph (d). Similarly in Figure 6 R12 helps orient the tail edges between o, b which cannot be learned by FCI rules.
y
'This version was originally called A-FCI, short for augmented FCI rules by (25) Augmented graphs are recently used in a different context in the causality literature, which is why in this work we are calling this version FCI+ avoid confusion.
18

---

C Sample Runs of k-PC Algorithm
Consider the figures below for two sample runs of k-PC algorithm. Note that k-PC outputs the k-essential graph in these examples, i.e., it can orient every invariant arrowhead and tail mark in the k-closure graph of D.
do
u
V
U
V
V
(a)
(b) (D(
(c) K After Step (d) after Step
(e) D' ~o D (I) C.(D') is
5. R11 applied
consistent with the output of k-PC.
Figure 5: An example where R11 helps orient tails. (a) DAG D. (b) k-closure graph of D for O. (c) K after Step k-P the same as (A). (d) R11 helps orient several tail edges. (e) A DAG D' that is k-Markov to D. (f) k-closure graph of D', which is Markov equivalent
to (D), showing that the circle at bo-> e is not an invariant tail. Thus k-PC outputs k-essential graph (D) in this case.
a
e
a
e
0
a
6
a
e
6 (a)
b0
b
b
(b) Cz(D)
(c) after Step (d) the end of Step 5.
(e) D'
(I) D"
4.
Figure 6: (a) A causal graph D. (b) k-closure of D for k = 0. (c) K at the end of Step 4. (d) Node since b is non non-adjacent to any other nodes in C
has one edge ao-o, ao-ob. Thus we have since there are no other nodes in C. Thus it oriented as a-b due to R12. + c is oriented due R11, similarly since C = 0 and the node e is trivially non-adjacent to all nodes in C. (e, f) D', D" k-Markov equivalent
D and their k-closure graphs contain + and c, respectively. This shows that the graph in (d) given by k-PC is the k-essential graph E (D).
19

---

D Discussions
D.I No Local k-Markov Equivalence Characterization on DAG Space
c - -cc
(a) Dr
(b) D2
Figure 7: As a collider, d blocks the path (a, d, e, b) in Da. but not in D4. Accordingly, (a IL b) D (a Al Dy and D1, D2 are k-Markov for 0. However, this does not appear as local condition since are not separable by conditioning sets of size up to in both graphs. Therefore, local characterization of equivalence like Verma and Pearl is not possible when are only allowed to check degree-k d-separation tests.
Consider the graphs in Figure 7 The only difference is the orientation of the edge between e, d. Due to the collider e + d + e, we have a IL b in D2 but not in D2. Therefore for = O, we have that D1, D2 are not k-Markov equivalent. However, this is not detectable locally: The endpoints of the collider responsible for the change of the k-Markov equivalence class cannot be d-separated. The effect of the collider can be detected only farther in the graph between a, b. This shows that local characterization similar to Theorem 2.10 is not possible for k-Markov equivalence.
D.2 k-closure Graphs vs. MAGs
U2
U2
e
d
d
1
b
a b
(a)
(b) = Cs(D) for t
Figure 8: The mixed graph on the right is valid k-closure graph for 1: It is the k-closure graph of the DAG in (a). However, it is not valid k-closure graph for k = 2. Because after removing c + d, it is possible d-separate c, d by conditioning on U1, u2-
In this section, we give an example for a MAG that is not valid k-closure graph. Consider the graph in Figure 8 K in (b) a valid k-closure graph for However, K is not valid k-closure graph for h 2. This is because the bidirected edge ++ d is added between a pair that not k-covered for
since is the k-closure graph of D.
We have e d [u,, u2 if and only if characterization in Theorem 3.9 we can show that there does not exist any D' with the
fact, using the
given k-closure graph where c, have a bidirected edge.
D.3 Bidirected Edge in k-essential Graphs
In Figure 9 since every endpoint an arrowhead and is part of an unshielded collider, there is no other Markov equivalent k-closure graphs, which implies that the k-essential graph is the same as the k-closure graph. Thus, the edge ++ e E& (D). This example shows that we can learn that two nodes do not cause each other using conditional independence tests that are not even powerful enough to make them conditionally independent. It is worth noting that LOCI 23 can also infer this fact by removing this edge.
20

---

d
0
6 b (a)
b
(b) (E(
Figure 9: A DAG with size-I k- k-Markov equivalence class for k 1. Observe that (D) only has unshielded colliders and thus there is no other k-closure graph that is Markov equivalent. Thus, this k-closure is at the same time the k-essential graph of D and can be learned from data. In this case, we can learn e do not cause each other despite not being separable the data.
D.4 k-PC is Incomplete
One might hope that k-PC is complete and outputs the k-essential graph ex(D). This, however, is not true. We discuss an example where k-PC cannot orient an invariant tail mark.
First, observe that k-PC does not leverage the value of k. If we had an efficient way to answer the question "Is there k-closure graph that is consistent with K in which 6 are k-covered ?" then could leverage this to orient more o-+ edges as - edges. As an example, consider the causal graph in Figure 10 d may have incoming edge that prevents from eliminating the possibility that do-> is bidirected edge d ++ b. However, we can only have a single d-connecting path between d, b. Since is non-collider along a-d-c,
of the edges must be out of d. Suppose <- a and 1+ c. For e to not block this path it has to be a non-collider, and thus c + b. This is the only way can have two d-connecting paths between d, b in the underlying DAG. However, now we have the path d + e + b, which makes d an ancestor of b. Therefore the edge d ++ b is inconsistent. Thus in k-essential graph of D, we must have tail at d d + b. This cannot be learned by k-PC
d
do
b
(a) D1
(b) Cx (Di)
(c) k-PC Output
Figure 10: A graph where k-essential graph contains an invariant tail that cannot be learned by k-PC algorithm. & == 1; thus d, are k-covered but not a, c, which gives the k-closure graph on the right. k-PC algorithm outputs the graph in (c). However, there is no k-closure in the Markov equivalence class where d ++ b. Thus the edge in the k-cssential graph should be - b. Similarly, ao- should be a + b, however this requires reasoning about the number of d-connecting paths between a, b in K that is not captured in k-PC
We observe that local algorithm such as k-PC cannot be used to assess if there is some k-closure graph that is consistent with the current graph in which two nodes are k-covered without the edge between them. One practical strategy would be take the output of the k-PC algorithm and list all MAGs consistent with the circle edges, and then check they are valid k-closure graphs by pruning every edge using Theorem 3.9 For small sparse k-closure graphs, k-PC could be a practical way to reduce the search space efficiently, and then we can conduct an exhaustive search as the next step to obtain sound and complete algorithm for learning the k-essential graph.
D.5 Heuristic Uses of Bounded Size Conditioning Sets
For large number of variables, and except for very sparse graphs, constraint- basse algorithms take significant time to complete. This is because the progressive nature of such tests is not able to sufficiently sparsify the graph with low-degree conditional independence tests, and they have to perform many tests: If the neighbor size is O(n), where is the number of nodes, algorithm needs to check exponentially many subsets of nodes in the conditioning set.
To prevent this issue, several implementations of these algorithms have the added functionality to restrict this search by limiting the size of the conditioning set. For example, causal-learn package has this functionality. However, this is a heuristic that simply prematurely stops the search algorithms.
21

---

The results of our paper build the theoretical understanding of what is learnable in this setting with new equivalence class and its graphical representation.
D.6 Comparison of k-PC Output to LOCI Output
Lemma D.I. Consider three nodes a, b. Suppose H b c S: S k and b & S. If are k-covered, then k-PC orients the edge between b, e as b +cc.
,a -L cIS for some set
Proof. In the following, we show that given the CI pattern that LOCI uses orient edges, k-PC also orients the same edges. Consider the CI pattern that LOCI uses between three nodes o, b,
Conditioned on S, there is d-comnecting path between a, b; let us call this path p. Conditioned on S. there is a d-connecting path between b, c; let us call this path q. Consider the path obtained by concatenating p, q. Since this path must be d-separating, b must be a collider on it and it must be the case that b & (n(S). Let the node that is adjacent to b along p be a' and the node adjacent to b along q be c'. Thus we have a' b < d.
Case 1: Now suppose that a' and are separable by some T [T] < k. k-PC would then orient a'*+ b <-cc since b, e remains adjacent throughout the execution of k-PC Thus b <-cc would be oriented in this case.
Suppose that a', are k-covered Then, given S, there is a d-connecting path between a', c. Now consider the path obtained by concatenating the subpath p between a, a' and this d-connecting path. Since a, are d-separated given S, a' must be a collider along this path and a non-ancestor of S. Thus we must have a" a'
Case 2:
the last three nodes of path p.
Case 2.a: Suppose a", c are separable by some T: : |T| S k. Since d', c are k-covered, they remain adjacent throughout the execution of k-PC Thus, k-PC would orient a"* a' x-*c. Now consider two sub-cases:
Suppose a", b are separable by some set of size at most k. Then, a"* a' - b is an unshielded triple and it would be oriented by the first Meek rule of k-PC as a"*-> a' -> Now we have the following edges oriented: b +==a <cc, and b, c adjacent. By the second Meek rule, k-PC will then orient <c.. This establishes that in this sub-case, k-PC would also orient the arrowhead adjacent to b for the edge between c.
Case 2.a.i:
Case 2.a.ii: Now consider the second sub-case: Suppose a", b are k-covered Thus, throughout the execution of k-PC, a", b are adjacent. In this case, abo-obo oc forms an unshielded collider and the algorithm would orient them as a"*>> b <=c due to the independence statement a" IL c.T. Therefore, the arrowhead at b would be oriented in this case well.
Case 2.b: Now suppose a", e are k-covered Thus, there must be d-connecting path between a", e given S. Now consider the path obtained by concatenating the subpath of p between a, a" and this d-connecting path. Since a IL clS. must be that a" is a collider along this path and that a" & SS))). Thus, along this path we have a" + a" +.... Therefore, the last four nodes of the path p a"" + a" + a' + b, and a', c are k-covered, a", c are k-covered.
c
Case 2.b.i: Now suppose a", are separable by some T I
Case 2.b.i.0: If the pair a" is k-covered, following the above argument, we would orient a"l * + b <- with the statement a" e elS, and the arrowhead adjacent to b along the edge between b, would have been oriented.
Case 2.b.i.3: Suppose a"", b pair is separable.
Case 2.b.i. Suppose a"" a' is k-covered. . We would orient am* d' < +C due to the statement a" IL (S. And since a" b are not k-covered, Meek rule one would orient the subgraph a'*++o d'o as a"*+> a'v+ b. Since xaa < and bo second Meek rule would orient the arrowhead at b along the edge between b.c.
Case 2.b. Finally, suppose a"" b and a"" a' are both separable. Now k-PC applies Meek rule one directly to orient a" a"*>> a'. Now that we have a' <-*a" ++c, and that a', are adjacent, Meek rule two will orient a' <<c. Another application of Meek rule one would give d'*+ a'--> and now since we have b <=aa <c and that b, c are adjacent, Meek rule two would orient b <-*c.
22

---

Case 2.b.j and beyond: Finally, if a" cre k-covered, following similar argument, either the node adjacent a" along p (towards a) separable with c, in which case following a similar argument as above would orient b <-*c, or we continue until a, c become adjacent. The latter cannot happen since that contradicts with the fact that IL c [S.. Thus, there must exist some node u along p that is separable from c, and the subpath of p between u, b is directed. Following the argument above, repeated application of Meek rules one and two will result in the orientation of the edge between 6, c as b <-cc. This establishes that k-PC orients at least as much arrowheads as LOCI.
The corollary of this lemma is that k-PC orients all arrowheads oriented by LOCI: Corollary D.2. Any arrowhead oriented by LOCI is also oriented by k--PC.
Proof. Suppose a J. b blS. b J. clS LL c for some set S | < k and b & S. Observe that if a, b and e are k-covered then k-PC would orient the edges between them as a+ <-*c due to the independence statement ILL с clS. Moreover, if b and b, are both separable by some sets of size at most k, then both LOCI and k-PC would make a, and b, e non-adjacent and thus neither algorithm orients edge between them. Therefore, the only non-trivial case is when only one of the two pairs is k-covered. For this case, since the pre-condition of Lemma D.1 is identical to the condition of LOCI to orient any edge.
LOCI applies the three Meek rules after orienting these arrowhead marks. Since k-PC repeatedly applies a set of Meek rules that include these three rules, k-PC orients at least as many arrowheads as LOCI. Thus, the corollary follows.
Next, we show that they both carry the same adjacency information.
Corollary D.3. Any pair that is non-adjacent in LOCI oulput is either non-adjacent, or adjacent via a bidirected edge in k-PC output.
Proof: LOCI makes a pair non-adjacent in two ways. If LOCI makes a pair non-adjacent since they are separable. kPPC also will make them non-adjacent. Suppose LOCI makes a pair a, non-adjacent due to the following CI pattern, which are otherwise k-covered: : u.K a [S] , a. k b [[S -l. b [S
and a 1 b SS2 6.4 v IS2 a IL [S2 for some u, v, S1 Note that by Lemma D.1 k-PC marks both endpoints of the edge between a, b as arrowheads. This concludes the proof.
These results can be combined with the example in Figure 2 show that the k-PC output carries strictly more information about the set of causal graphs that entail the set of degree-k: d-separation statements than the output of LOCI, even though k-PC is not complete for learning our equivalence class as discussed in Section D.4
D.7 Comparison of A-PC Output to AnytimeFCI Output
The undirected edges in our representation do not represent selection bias. We use them to represent a different graph union operation. The lack of latents gives us this flexibility, which allows us to distinguish different sets of graphs by using both - and o-o edge marks for this.
For concrete example on why AnytimeFCI is less informative than k-PC in our setting, consider the causal graph in Figure 2 Here, k-PC will learn the representation on the right: We can infer that either a causes d or d causes noted by the undirected edge a - d in our representation, rather than the circle edge o-o, which would allow a, d to be non-adjacent in some DAGs. Anytime FCI here will instead output circle edges between and d, i.c., ao-od. od. Even if we try to incorporate the knowledge that the underlying graph causally sufficient, is not obvious how one can conclude that a and d must be adjacent in every DAG that induces the same degree-k d-separation statements from the Anytime FCI output. One way to do this would be to remove the edge from this PAG and check whether a, d can now be d-separated by some conditioning set of size at most k. If yes, this changes the equivalence class, which means the edge must be there in any DAG. Our local rule R12 can instead orient this as an undirected edge, signifying that a and d must be adjacent in every underlying DAG by leveraging our equivalence class representation, without having to run this type of post processng which might be computationally intensive for larger graphs.
23

---

E Additional Experiments
E.1
Experiments vs. LOCI
N-50
of
1.0
1.0
100
0.0
0.8
0.8
KPC,K=0
k=C
kFC,k=0
0.6
kPC,k-1
kFC,k-1
KFC,K-2
KPC,K=2
0.4
kPC,K=2
0.4
LOCI
LOCIK-0
LOCIK=0
LOCIK-1
LOCIK=1
0.2
LOCIK=1
0.2
LOCI,k2
LOCIK=2
LOCIK=2
0.2
0.4
0.6
0.0
0.2
0.0
0.2
0.6
0.8
(a) Arrowhead Fi Score
(b) Tail F) Score
(c) Skeleton Fi Score
CDF Ff" F0..F..NN. N=100
CDF of N=100
CDF of N=100
1.0
1.0
1.0
0.8
KPC,K-0
kPC,k=0
kFC,k=0
kPC
0.6
kFC,k=1
0.6
kFC,k=1
0.6
kPC,k-2
KFC,K=2
LOCIK=0
0.4
LOCIK=0
kPC,K=2
0.4
LOCIK=1
LOCIK=0
0.2
LOCIK=1
LOCIk=1
LOCI,=2
LOCIK=2
LOCIK-2
0.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
(d) Arrowhead Fi Score
(e) Tail Fi Score
(f) Skeleton Pi Score
Figure 11: Empirical cumulative distribution function of various F1 scores on 100 random DAGs on 10 nodes. We pick the parents of each node fixed total order randomly so that the expected value of parents is 3. The conditional distribution of every node given any configuration of its parent set is sampled independently, uniformly randomly from the corresponding dimensional probability simplex. Three datasets are sampled per instance. Performance of k-PC and LOCI (23) are similar as expected. We still observe similar trend as PC that arrowhead score of k-PC is better. For tail accuracy, the result depends on the value of k. For small k, LOCI outperforms k-PC whereas for larger k; k-PC outperforms LOCI in the small sample regime. Different from Figure we compare the outputs to the true DAG instead of essential graph since no algorithm in this comparison can achieve essential graph.
24

---

E.2
Experiments vs. NOTEARS
CDF of N-50
CDF Fl. N-50
CDF of No
0.9
0.8
0.8
KPC,K=0
kFC,k-1
PC
0.6
PC
0.6
KPC,k=2
kFC
NOTEARS
0.7
k=C
kFC,k-1
0.6
kFC
0.2
kPC,k=2
0.2
NOTEARS
NOTEARS
0.0
0.0
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
1.0
(a) Arrowhead F1 Score
(b) Tail F1 Score
(c) Skeleton F1 Score
of N=100
of N-100
CDF of N-100
PC
PC
kFC,K-O
0.8
kFC
0.8
kFC,k=1 kFC,k-2 NOTEARS
kFC,k=1
kFC,k=1
0.6
kPC,k-2
0.6
kPC
NOTEARS
NOTEARS
0.2
0.2
0.0
0.0
0.50
0.75
1.00
0.50
0.75
1.00
10
(d) Arrowhead Fi Score
(e) Tail F Score
(f) Skeleton F Score
Figure 12: Empirical cumulative distribution function of various F1 scores on 100 random DAGs on 5 nodes. For each DAG, linear SCM is sampled as follows: Each coefficient is chosen randomly the range [-3, 3). Exogenous noise terms are jointly independent unit Gaussian. Performance of k-PC vs. NOTEARS [28] We observe similar trend as PC. NOTEARS is slightly better than PC consistently. Despite this, k-PC outperforms both in the low-sample regime, Metries are computed against the true DAG.
25

---

E.3
More Experiments vs. PC
In this section, we show a larger range of N (number of samples). We also explore the behaivor for graphs with different edge densities and higher number of nodes (10).
CDF of N-10
CDF fft N=10
CDF of N0
1.00
1.0
10
0.95
0.8
0.8
0.90
0.6-
0.85
PC
0.6
PC
kPCk=0
KPCk00
kPCk=0
0.80
KPCk-1
0.4
KPCk-1
kPCk-1
0.75
KPCK=2
KPCk=2
0.2
KPCK=2
0.0
0.1
0.2
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.4
(a) Arrowhead Fi Score
(b) Tail Fi Score
(c) Skeleton Fi Score
CDF Ff N-50
CDF of Fl, N=50
CDF F5550
1.0
1.0
0.8-
0.8
0.6
0.6
PC
PC
kPCk-0
KPCk-0
kPCk-0
KCCk=1
0.2
KPCk=1
0.2
kPCk=1
kPCk-2
KPCk-2
KPCk-2
0.0
0.0
0.2
0.4
0.0
0.1
0.2
0.3
0.4
0.0
0.4
(d) Arrowhead F1 Score
(c) Tail F1 Score
(f) Skeleton F1 Score
CDF
CDF of N-100
CDF of N-100
1.0
1.0
0.8
0.8
0.8
0.6-
0.6-
0.4 PC
0.4
PC
0.4
PC
kPCk=0
KPCk=0
kPCk=0
1PCk=1
0.2
WCC-1
02
kPCk=1
kPCk=2
KPCk=2
kPCk=2
0.0
0.0
0.0
0.2
0.4
0.2
0.4
(g) Arrowhead Fi Score
(h) Tail Fj Score
(i) Skeleton Fi Score
CDF of N=1000
CDF 6 N000
CDF of Fff, N=1000
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.4-
PC
0.4
PC
0.4
PC
kPCk=0
KPCk=0
kPCk=0
0.2
kPCk=1
0.2
KPCk-1
0.2
KPCk=1
kPCK=2
KPCk-2
KPCk=2
0.0
0.6
0.0
0.4
0.6
0.6
(i) Arrowhead Fi Score
(k) Tail Fi Score
(1) Skeleton Fi Score
Figure 13: Empirical cumulative distribution function of various F1 scores on 100 random DAGs on 10 nodes. For each DAG, conditional probability tables are independently and uniformly randomly filled from the corresponding probability simplex. Three datasets are sampled per instance. The lower the curve the better. The maximum number of edges is 30. Even in the extreme case of just 10 samples (10 node-graphs), k-PC for = provides improvement to all scores. k should be gradually increased more samples are available to make best use of the available data. For example, for 1000 samples, k = 2 provides the best arrowhead score while not giving up as much tail score as = O.
Next, we present combined metrics for this same setup. Namely, we show the advantage of our algorithm in terms of the sum of arrowhead and tail Fj scores, and the sum of arrowhead, tail and skeleton Fj scores.
26

---

E,4
Experiments of Section E,3
CDF of + N-10
CDF of FF N=10 N=10
1.00
1.00
0.95
0.95
0.85
kPC,k=D
0.85
kPC,k=D
kPC,k-1
kPC.k-1
kPC,k-
KPC,k-2
0.0
0.2
0.4
0.6
0.00
0.25
0.50
0.75
(a) Arrowhead Tail Fi
(b) Arrowhead Tail + Skeleton Fi
CDF of FY*+F), N-50
of +AP. N-50
1.0
1.0
0.8
0.8
0.6
0.6
kPC,==0
kPC.k=D
0.4
kPC.k1
0.4
KPCk-1
kPCk--
KPCkk-
0.0
0.2
0.4
0.6
0.8
0.0
0.5
1.0
(c) Arrowhead Tail F1
(d) Arrowhead + Tail + Skeleton Fj
CDF F3 N-100
CDF #FR N-100
1.0
1.0
0.8
0.8
0.6
0.6
0.4
kPC
0.4
kPC,k=D
kPCkk=1
kPC,k=1
kPCkk=
kPC,k-2
0.0
0.2
0.6
0.0
0.5
1.0
1.5
(e) Arrowhead + Tail Fi
(1) Arrowhead + Tail + Skeleton Fi
FM+FR, N=1000
+F N=1000
1.0
1.0
0.8
0.8
0.6
0.6
0.4
PC
0.4
PC
kPC.k-0
KPC.k0D
kPCkk=1
kPCkk1
kPC,k-2
kPCkk-2
0.0
0.0
0.5
0.0
0.5
1.b
1.5
2.0
(g) Arrowhead
Tail F
(h) Arrowhead + Tail + Skeleton Fi
terms of combined scores. For each instance, arrowhead and tail Fi scores are added before computing CDFs on the left. On the right, arrowhead, tail and skeleton F1 scores are added together.
Figure 14: Results of the experiments Section E.3
27

---

E,5
Experiments vs. Conservative PC
We use pealg package in R as the implementation for conservative PC
14
of N=10
CDF of N=10
CDF of N=
1.0
1.0
1.0
0.8-
0.8
0.8
0.6
Cons_FC
0.6
Cons FC
Cons PC
kPC,k=0
kPC,k=0
0.4
kPC,k=0
0.2
kPC,k=1
kPC,k=1
kPC,k=1
0.4
0.0
KPC,k=2
KPC,k=2
02
kPC,k=2
-0.50
-0.25
0.00
0.25
0.0
0.2
(a) Arrowhead Ai Score
(b) Tail Fi Score
(c) Skeleton Fi Score
F(". N-50
Fl.. N-50
off
1.0
1.0
1.0
0.8-
0.8
Cons PC
0.4
Cons PC
0.4
Cons PC
kPC,k-0
kPC,k-0
kPC
kPC,k=1
0.2
kPC,k=1
k=C
kFC,k-2
kPC,k=2
kPC,k-2
0.0
0.0
0.2
0.4
0.0
0.2
0.4
0.0
0.2
0.4
0.6
0.8
(d) Arrowhead F1 Score
(c) Tail F1 Score
(f) Skeleton F1 Score
CDF of of
CDF of N-100
CDF of F?t N=100
1.0
1.0
1.0
0.8
0.6-
0.6
0.6
Cons PC
0.4
Cons, FC
0.4
Cans, PC
kFC
kPC,k=0
kFC
0.2
kPCk=1
kPC,k=1
kPC,k=1
kPC,k=2
kPC,k=2
kPC,k=2
0.0
0.0
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.2
0.4
0.6
0.8
(g) Arrowhead Fj Score
(h) Tail Fi Score
(i) Skeleton F Score
CDF of [T" N=500
CDF of N=500
CDF of N=500
1.0
1.0
0.6-
0.6
0.6
Cons_
0.4
Cons_Pt PC
0.4
Cons
kPC.k=0
kPCkk=0
kPC,k=0
k
02
kPC,k=1
0.2
kPC,k=1
kPC,k=2
kPC,km2
kPC,k=2
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
0.6
0.8
(i) Arrowhead Score
(k) Tail Fi Score
(1) Skeleton Score
Figure 15: Empirical cumulative distribution function of various F1 scores on 100 random DAGs on 10 nodes. For each DAG, conditional probability tables are independently and uniformly randomly filled from the corresponding probability simplex. One dataset is sampled per instance. The lower the curve the better. The maximum number of edges is 15. k-PC maintains an advantage against conservative PC in the arrowhead and skeleton F1 scores in the low-sample regime.
28


Reviews:
[{"review_id": "y1ayG44jFX", "reviewer": "Reviewer_XPAW", "summary": "This paper aims to address the problem that in constraint-based causal discovery based on conditional independence tests, the tests become statistically unreliable with limited data when the conditioning sets are large. The proposed solution is to use only conditional independence tests for relatively small conditioning sets. To facilitate this goal, this paper provides a characterisation of k-Markov equivalence between causal DAGs, in the sense of entailing the same conditional independence statements in which the conditioning set has a cardinality not exceeding k. Since the characterisation is in terms of maximal ancestral graphs, a FCI-like algorithm is proposed to learn such equivalence classes and is empirically evaluated against some benchmarks. ", "questions": "Are the main results of this paper a reproduction of Spirtes's (2001) results?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This paper is well written and very readable. The technical results are sound and the empirical evaluation is reasonable.", "weaknesses": "Unfortunately, as far as I can tell, this paper largely reproduces the results of an old paper by Peter Spirtes (2001), \"An Anytime Algorithm for Causal Inference\", Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics. It seems to me that all the main results and insights of this paper were already presented in Spirtes's paper. I may have missed something important. I will increase my score if the authors can convince me that their contributions remain sufficiently original and significant given Spirtes's paper.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to first thank the reviewer for pointing out such a relevant paper to us. Please allow us to compare our work with Spirtes (2001).\n\nThe short answer to your question \"Are the main results of this paper a reproduction of Spirtes's (2001) results?\" is no, they are not a reproduction of Spirtes's results. We elaborate below:\n\nFirst, Spirtes 2001 says: You can halt FCI after running it until any conditioning set of size k. The result will still be a correct PAG, but a potentially less informative one. \n\nThere are at least three main algorithmic differences: \n1. We are not trying to learn a PAG. Our goal post is different. Namely, we don't actually have any latents in the system, nor any selection bias. We define the equivalence class to be learned by the algorithm a priori, knowing that we won't be conditioning on sets of size greater than k given a DAG. \n \n2. The undirected edges in our representation do not represent selection bias. We use them to represent a different graph union operation. The lack of latents gives us this flexibility, which allows us to distinguish different sets of graphs by using both - and o-o edge marks for this. Please see Definition 3.15 for how each edge in our k-essential graph represents something specific about our equivalence class of graphs without latents. This machinery allows us to develop a finer equivalence class representation than LOCI [20]. \n\n3. Even if we simply compare the two algorithms ignoring this context, since our goal post is different, we have additional orientation rules that do not appear in FCI. Please see the new rules R11 and R12 in Algorithm 1. This again is because our goal post is different from learning a PAG of the true causal graph. Furthermore, we modified the existing FCI rules since we do not have undirected edges that represent selection bias, and therefore our undirected edges are treated as if they are circle edges. This can be seen in lines 1064-1072 in the supplementary material. \n\nIn terms of the contributions of the paper, we also have a new representation to capture all the d-separation statements of bounded conditioning set size. Importantly, we use these to give necessary and sufficient graphical k-Markov equivalence conditions between two causal DAGs. These are not implied by the results of Spirtes 2001, which focuses on the soundness of early stopping of FCI in relation to the true PAG.\n\nWe hope that this convinces the reviewer that the results of our paper are not simply reproductions of Spirtes 2001. It goes without saying that we will cite this paper and thanks to your input, we will be able to put our paper's contributions in better and clearer context in relation to the existing causal discovery literature.\n\nThank you once again for your valuable feedback.\n\n\n "}, {"review_id": "zz8uj5TGtq", "reviewer": "Reviewer_fQhL", "summary": "While I have the background to understand this paper, I'm afraid I am not well positioned to judge its novelty and significance in the causal discovery subfield. In short, the PC algorithm struggle when conditioning sets are large, so the authors propose a modification of Markov equivalence for bounded conditioning sets, then graphically characterize this relationship, and then propose the k-PC algorithm that is more successful in synthetic small small regimes.\n\n Nothing in the math or presentation seems incorrect to me, though I did not closely examine the more technical parts of the paper. The experiments are on synthetic data, which is typical in this subfield, but that makes it difficult to know whether k-PC has practical advantages over PC in real-world cases, as there are likely regimes where PC is superior. \n\n\nOverall, this seems like competent well done work, but I lean towards rejection for this paper. The modification of PC and Markov equivalence for bounded conditioning sets seems like a straightforward and simple modification of existing definitions, so the contribution does not seem novel and significant to me. If there were convincing empirical results that showed this change makes causal discovery viable in new real-world contexts I might be convinced, but as it stands its unclear to me whether the synthetic experiments are good evidence of this, especially with how little prose was in the main text describing them. This might be more appropriate for a conference or workshop that is more narrowly focused on causality.  \n\nI'm perfectly happy to be convinced otherwise, or have my opinion ignored in favor of reviewers/metareviewers with a better understanding of the subfield!\n\n", "questions": "See main", "limitations": "See main", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "See main", "weaknesses": "See main", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your feedback and insights. Our responses are below.\n\n\"this seems like competent well done work\"\nThank you! We appreciate this. \n\n\"The modification of PC and Markov equivalence for bounded conditioning sets seems like a straightforward and simple modification of existing definitions, so the contribution does not seem novel and significant to me.\"\nWe respectfully disagree with this assessment. As we stated in the paper, by giving up conditioning on a set of variables, we no longer have the classic Markov equivalence condition. In fact, it is not a priori clear if there even is a simple graphical Markov equivalence condition when we restrict the size of conditioning sets. \n\nOur results show that one can do this by using ancestral graph machinery - which is typically used for handling latent confounders - in the context of characterizing k-Markov equivalence class for systems without latents. This, in our opinion, is a surprising finding. The comparison with LOCI shows the power this representation has over the existing work addressing this problem. \n\nIn terms of novelty, the key lemmas are all derived from first principles, and as far as we are aware of, the k-Markov equivalence characterization is not implied by any of the existing literature.\n\nIn terms of significance, our goal was to demonstrate that the proposed approach could lead to more robust causal discovery (various F1 scores are used in the experiments) in the small sample regime where large CI tests become unreliable. We believe that rendering causal discovery more reliable in practice is a significant goal and hope that our contribution takes us one step closer to this goal. \n\nWe hope that this re-iteration of our contributions helps convince the reviewer that our results are novel and significant and that the reviewer would reconsider their evaluation in light of this. \n\nIf you have follow-up questions, please let us know. We would be happy to engage further.  \n\nThank you once again for your time and feedback! "}, {"review_id": "C6LipDECnm", "reviewer": "Reviewer_iDG2", "summary": "The authors study the problem of causal learning with bounded conditioning sets. It is an important question that up to what set of equivalence graphs a learner can  infer a causal graph when it can only perform conditional independence tests with limited size of the conditioning sets. They characterize the equivalence set and propose a sound constraint-based algorithm for learning it. ", "questions": "See above.", "limitations": " The authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The authors study an important research question. The paper is well-organized. \n\nThe results are quite relevant and important. It nicely establishes the connections between the existing results about Markov equivalence class and newly define k- Markov equivalence class that is the set of causal graphs that have the same conditional independences with conditioning sets at most k.\n\nThis results can be a foundation for further developments in causal graph learning.", "weaknesses": "A discussion about the complexity of the proposed algorithm will improve the paper. \nFor instance, what is the complexity of checking whether two given DAGs are k-Markov equivalent?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their constructive comments and we are happy to hear that they found our results relevant and important. \n\n\"Complexity of checking k-Markov equivalence.\"\nThis is a good question. Currently, one needs to explicitly construct k-closure graphs given the two DAGs and check whether they are Markov equivalent. The step to make two variables adjacent requires one to loop through all conditioning sets of size at most $k$. This would take $\\mathcal{O}(n^k)$. This is the main time-consuming step. Afterward, one can test Markov equivalence using the existing approaches. For example, Hu and Evans 2020 show that one can do this in $\\mathcal{O}(ne^2+n^2e)$ time, where $e$ is the number of edges. Thus, the overall algorithm will indeed be polynomial-time when $k=\\mathcal{O}(1)$. \n\nThe complexity of the learning algorithm will be similar to an early-stopped version of FCI, called Anytime FCI by Spirtes 2001. Although this is more complicated and would depend on other parameters in the graph, such as primitive inducing paths, and thus the number and location of unobserved confounders, we can also roughly bound this by $\\mathcal{O}(n^{k+2})$ since for any pair, we will not be searching for separating sets beyond the $\\mathcal{O}(n^k)$ subsets of size at most $k$. Further runtime improvements, such as RFCI by Colombo et al. 2012 might be possible, but this requires a further understanding of the structure of k-closure graphs, which might be an interesting future direction. \n\nWe will add this discussion with the relevant citations below to the manuscript. Thank you for your time!\n\n[Hu and Evans] Zhongyi Hu, Robin Evans, \"Faster algorithms for Markov equivalence,\" 2020.\n\n[Spirtes] \"An Anytime Algorithm for Causal Inference,\" 2001.\n\n[Colombo, Maathuis, Kalisch and Richardson] \"Learning High-Dimensional Directed Acyclic Graphs With Latent And Selection Variables,\" 2012."}, {"review_id": "7RcqoTRmgo", "reviewer": "Reviewer_Gg3j", "summary": "A new structure learning approach is proposed in limited data settings. In these settings, existing constraint-based causal discovery approaches struggle with statistical tests of independence. The main insight is that we can define an equivalence class of graphs based on an upper bound on the size of the conditioning set. Using this, a new learning algorithm is presented to learn the equivalence class. ", "questions": "Are there real-world examples of learning from limited conditioning sets that could perhaps be used to strengthen the experimental evaluation?", "limitations": "There are no limitations that are explicitly mentioned in the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-motivated and clear in its contributions. The problem of causal discovery from limited datasets seems to be a significant one. The novel contributions include introducing the formalism of K-Markov equivalence which can then be used to derive a learning algorithm. The soundness of the algorithm is guaranteed and the completeness is shown in some cases. Overall the theoretical contributions seem strong in this work.", "weaknesses": "On the empirical side, comparisons are performed with state of the art structure learners on synthetic and semi-synthetic datasets. Since the motivation of the work was causal discovery from limited data, using some more real-world cases could have made the experiments much stronger. Overall, perhaps the empirical evaluation is not as strong as the theoretical contributions of the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and feedback. \n\n\"real-world examples of learning from limited conditioning sets\"\\\nWe share the reviewer's sentiment that more experiments with real-world datasets would make the paper stronger. bnlearn repository is the main resource that causality researchers typically use, which is what we used as well. Note that the lack of datasets with ground truth causal structures is a common struggle with causality research, which makes the theoretical groundings of any proposed solution ever more important than some other fields. We hope our work to initiate a line of research and that the follow-up work could apply our methods to more datasets as these become available. We will make our code available upon publication to help speed up this process. \n\nA related practical setting where it is naturally difficult to condition on certain subsets of variables is the following: Consider a causal graph where some variables are high-dimensional, such as images, while others are binary such as labels or classifier outputs. It is very difficult to run reliable conditional independence tests with images in the conditioning set in practice. What can we learn about the causal structure then? An important future work is to extend our results to when an arbitrary set of CI tests cannot be performed. We hope that our work can motivate research in this direction. \n\nOnce again, thank you for your positive comments! We would be happy to discuss these points further. "}, {"review_id": "OtyFcdD0g8", "reviewer": "Reviewer_mhM7", "summary": "Besides computational complexity, the weak spot of constraint-based causal discovery is the assumption of having an independence oracle. Especially with large conditioning sets, independence testing is difficult. This paper aims to address this limitation by restricting the number of conditioning variables and provides a sound framework that allows us to study the guarantees one can obtain for constraint-based structure learning if one restricts the size of the conditioning sets. The authors show that the results can contain bi-directed edges and relate the obtained graph to maximal ancestral graphs. They further provide a sound algorithm to learn such graphs and evaluate it on a few synthetic and semi-synthetic examples. \n\nThe theoretical contributions of the paper are interesting and presented clearly to most parts. The main limitation of the work are the points that I mention with respect to the empirical evaluation.\n", "questions": "- What is the intuition of step 5 in the algorithm? Why do we have to exclude it for Corollary 4.2? Not much intuition is provided regarding this step, and it just occurs in Corollary 4.2.\n- I understand that if we just run the PC algorithm and restrict the conditioning set it does not inherit the same guarantees as PC-k, e.g., it would not find any bi-directed edges. What would be the other differences/failure cases of this naive approach?\n- Assume one naively restricts the maximum size of the conditioning set in the PC algorithm, which I think is an option in the pcalg package, for example. How does this version of PC perform if we restrict the conditioning size in a similar manner as for the proposed method (e.g., for the experiments shown in Fig. 3 & 4)?\n- How does the computational complexity or empirical runtime compare to PC?\n", "limitations": "Standard limitations occurring in constraint-based causal discovery (a variant of faithfulness, independence oracle).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Rigorous definition of assumptions, goal, and solution that can be obtained under the concept of restricting the size of the conditioning set.\n- The new formulation of k-closed graphs was introduced well and discussed in the context of previous notions (ancestral graphs). Further, Markov equivalence and faithfulness are adapted for the introduced graphs.\n- The authors propose a learning algorithm k-PC to learn the Markov equivalence class of the introduced k-closure of the true DAG.\n- The proposed algorithm has been empirically evaluated to PC, LOCI and NOTEARS, and the code has been provided for reproducibility.\n", "weaknesses": "- The performance gain seems to be only evident in small sample regimes.\n- The new approach does not clearly outperform LOCI & it would be interesting to see how PC performs when restricting the conditioning set, as well.\n- It would be interesting to study a real-world example, or DAGs with non-linear relations. I could imagine that on the latter, using a smaller conditioning set can be a more substantial advantage, as independence testing with large conditioning sets is especially difficult for arbitrary functional relationships. For more details on the problem and maybe a good source to motivate the proposed algorithm please consider Shah and Peters (2020)\n\nShah, Peters, The Hardness of Conditional Independence Testing and the Generalised Covariance Measure, The Annals of Statistics, 2020\n\nMinor (suggestions):\n- For easier comparison, it might be beneficial to compute the area under the curve for the metrics shown in Figure 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed comments and suggestions. Please see below for our replies.\n\n**1.** \"performance gain seems to be only evident in small sample regimes\"\\\nNote that showing our method outperforms the existing approaches in the small sample regime was the main goal of our experiments. When the sample size is large, k-PC will only be less informative than PC since high-degree CI tests become more reliable, and they carry information about the underlying causal structure. \n\n**2.** \"what if we run PC, and early terminate? Any failure cases?\"\\\nThis is a great question. Note that running PC only for conditioning sets of size at most k will lead to wrong causal conclusions. To see this, consider the graph in Figure 9 (in appendix), reproduced below for convenience:\n\nX->Y<-Z->U<-V\n\nLet k=0. Modifying PC to only condition on the empty set leaves in the spurious edge Y-U in the skeleton phase. Applying orientation rules afterwards, we can get Y<-U or Y->U depending on which unshielded collider orientation phase is conducted, either X->Y<-U or Y->Z<-T. Both of these would be wrong. Thus, basic PC is not sound if we simply do not condition on certain subsets. Alternative versions such as stable PC might detect these incompatibilities, but they don't have a systematic way to handle them except not orienting such edges. Our algorithm orients as bidirected, which allows inferring them as spurious edges.  \n\nSince PC with this kind of early stopping is not sound even in the infinite sample regime, we have not included it in our experiments. \n\n**3.** \"DAGs with nonlinear relations?\"\\\nApologies for not being clear on this: Please note that most of our experiments are with non-parametric relations, i.e., with discrete variables with randomly chosen conditional probability tables (uniformly from the probability simplex). All discrete variables are binary since the results did not change with larger support and we were able to scale graphs easier with binary nodes. Note that we use linear models only while comparing our method against NOTEARS, whose baseline version uses the linearity assumption. We will clarify this in the manuscript. \n\n**4.** \"Shah and Peters (2020)\"\\\nThank you for this pointer! We will add this citation to help motivate our work from the hardness of independence testing. \n\n**5.** \"Corollary 4.2 and Step 5 of Alg.\"\\\nCorollary 4.2 says that we can learn as much as the PAG of our representation. And this is sound and complete. However, to learn more about the representation (k-essential graph), we need to have more orientation rules. These arise since our k-essential graph is not any ancestral graph, but has more structure. In other words, there is more to be learned beyond PAG. The rules in Step 5 allow us to learn more about the k-essential graph beyond the FCI orientation rules. We show that the overall algorithm with these rules is sound in Theorem 4.4. For a discussion on the challenges of completeness for learning the k-essential graph, please see the discussion in Section E.2 (appendix).\n\n**6.** \"Computational complexity vs PC\"\\\nThe complexity of the learning algorithm will be similar to an early-stopped version of FCI, called Anytime FCI by Spirtes 2001. Although this is complicated and would depend on other parameters in the graph, such as primitive inducing paths, and thus the number and location of unobserved confounders, we can also roughly bound this by $\\mathcal{O}(n^{k+2})$ since for any pair, we will not be searching for separating sets beyond the $\\mathcal{O}(n^k)$ subsets of size at most $k$. Further runtime improvements, such as RFCI by Colombo et al. 2012 might be possible, but this requires a further understanding of the structure of k-closure graphs, which might be an interesting future direction. PC on the other hand runs roughly in time $\\mathcal{O}(n^d)$ where $d$ is the degree of the graph. Thus, for sparse graphs and small $k$, we can expect a similar runtime.  \n\nWe will add this discussion with the relevant citations below to the manuscript. \n\n[Spirtes] \"An Anytime Algorithm for Causal Inference,\" 2001.\n\n[Colombo, Maathuis, Kalisch and Richardson] \"Learning High-Dimensional Directed Acyclic Graphs With Latent And Selection Variables,\" 2012.\n\nThank you very much for your feedback and valuable comments! We hope that our responses will give the reviewer more confidence in their acceptance recommendation and that they would consider increasing their score. "}]

Author rebuttal:

Meta-review: The paper extends the PC algorithm in the small data regime, by limiting the size of the variable sets considered in the conditional independence tests. This goal is very relevant for practitioners, and the reviewers appreciate the fact that the proposed approach is soundly built on a definition of Markov equivalence, coming with necessary and sufficient equivalence conditions between two causal DAGs.

The rebuttal convincingly established the originality of the approach w.r.t. Anytime FCI (Spirtes 2001).  It is recommended that the discussion about the computational complexity be added to the camera-ready version.
Decision: Accept (poster)