Meek Separators and Their Applications in Targeted Causal Discovery
Authors: Kirankumar Shiragur
Jiaqi Zhang
Caroline Uhler
Venue: NeurIPS 2023 poster (2023)
Keywords: Causality
Graphical Models

Abstract: Learning causal structures from interventional data is a fundamental problem with broad applications across various fields. While many previous works have focused on recovering the entire causal graph, in practice, there are scenarios where learning only part of the causal graph suffices. This is called \emph{targeted} causal discovery. In our work, we focus on two such well-motivated problems: subset search and causal matching. We aim to minimize the number of interventions in both cases.

Towards this, we introduce the \emph{Meek separator}, which is a subset of vertices that, when intervened, decomposes the remaining unoriented edges into smaller connected components. We then present an efficient algorithm to find Meek separators that are of small sizes. Such a procedure is helpful in designing various divide-and-conquer-based approaches. In particular, we propose two randomized algorithms that achieve logarithmic approximation for subset search and causal matching, respectively. Our results provide the first known average-case provable guarantees for both problems. We believe that this opens up possibilities to design near-optimal methods for many other targeted causal structure learning problems arising from various applications.

Meek Separators
and Their Applications in Targeted Causal Discovery
Kirankumar Shiragur" Eric and Wendy Schmidt Center, Broad Institute of MIT and Harvard
Jiaqi Zhang"
LIDS, Massachusetts Institute of Technology Broad Institute MIT and Harvard
Caroline Uhler
LIDS, Massachusetts Institute of Technology Broad Institute of MIT and Harvard
Abstract
Learning causal structures from interventional data is fundamental problem with broad applications across various fields. While many previous works have focused on recovering the entire causal graph, practice, there are scenarios where learning only part of the causal graph suffices. This is called targeted causal discovery. In our work, we focus on two such well-motivated problems: subset search and causal matching. We aim to minimize the number of interventions in both cases.
Towards this, we introduce the Meek separator, which is subset of vertices that, when intervened, decomposes the remaining unoriented edges into smaller connected components. We then present efficient algorithm find Meek separators that are of small sizes. Such a procedure is helpful in designing various approaches. In particular, we propose two randomized algorithms that achieve logarithmic approximation for subset search and causal matching, respectively. Our results provide the first known average-case provable guarantees for both problems. We believe that this opens up possibilities to design near-optimal methods for many other targeted causal structure learning problems arising from various applications.
Introduction
Discovering the causal structure among set of variables is important problem permeating multiple fields including biology, epidemiology, economics, and social science [FLNP00, RHBO0, SGSH00, PeaO3]. A common way to represent the causal structure is through directed acyclic gruph (DAG), where an are between two variables encodes a direct causal effect [SGSH00]. The goal of causal discovery is thus recover this DAG from data. With observational data, DAG is generally only identifiable up to its Markov equivalence class (MEC) [VP90, AMP97]. Identifiability can be the variables. In particular, more refined MEC can be
improved by performing interventions identified with both hard and soft interventions [HB12, YKU18), where hard intervention eliminates the dependency between its target variables and their parents in the DAG and soft intervention modifies this dependency without removing it [ES07].
As intervention experiments tend to be expensive in practice, a critical problem is to design algorithms to select interventions that minimize the number of trials needed to learn about the structure. Previous works have considered both fully identifying the DAG while minimizing the total number/cost of interventions [HB 14, SKDV15, 17,17, GKS 19, SMG+20J and learning the most about the
Equual contributions. Alphabetical order.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

underlying DAG given a fixed budget [GSKB18]. While recovering the entire causal graph yields holistic view of the relationships between variables, it is sometimes sufficient to learn only part of the causal graph for particular downstream task. This is sometimes termed targeted causal discovery [SU22] and has arisen in various different applications recently [ASY+19, GHD20, 7SU21, CS23J. The benefit of targeted causal discovery is that the number of required interventions can be significantly less than that needed to fully identify the DAG. In our work, we consider two such problems, subset search and causal matching, described in the following.
Subset Search. Proposed by [CS23]. the problem of subset search aims to recover subset of the causal relationships between variables. Formally, let g = (V, E) denote the underlying DAG. Given a subset of target edges T S E, the goal is to recover the orientation of edges in T with the minimum number of interventions. Subset search problems arise in many applications, including local graph discovery for feature selection [ATSO3], ouito--distriuution generalization in machine learning [HDPM 8), and learning gene regulatory networks [DI00]]. As a concrete example, consider the study of melanoma [FMT+21], J. type of skin cancer. To understand its development for potential treatments, it may be of interest to identify the causal relationships between genes that are known to be relevant to melanoma. In this case, the problem can be formulated as recovering the subset of edges between melanoma-related genes.
Causal Matching. Motivated by many sequential design problems, [ZSU21] considered causal matching, where the goal is to identify an intervention which transforms a causal system to a desired state. Formally, let V be the system variables and be its joint distribution which factorizes according to the underlying DAG G. Given a desired joint distribution Q over V, the goal is to identify an intervention such that the interventional distribution pl best matches Q under some metric. Similar to [ZSU21], we will focus on a special form of this problem, causal mean matching, where the metric between p and Q is characterized by the mean discrepancy Ep [V] - -Eq[V]ll2 Such problems arise in, for example, cellular reprogramming in genomics, which is of great interest for regenerative medicine [CD12]. The aim of this field is to reprogram easily accessible cell types into some desired cell types using genetic interventions. Since genes regulate each other via an underlying network, targeted strategy can infer just enough about the structure in order to match the desired state.
Contributions. One of our primary contributions is an efficient algorithm for finding an intervention set I of small size that, when intervened, decomposes the remaining unoriented edges into connected components of smaller sizes. This procedure is powerful in its flexibility to be used to design various based algorithms. In particular, we demonstrate this on the two targeted causal discovery problems of subset search and causal matching."
For the subset search problem, we obtain efficient randomized algorithm that in expecta- tion achieves a logarithmic approximation to the minimum number of required interventions (verification number; defined in Section 2).
For the causal mean matching problem, we derive a randomized algorithm that on average achieves a logarithmic competitive ratio against the optimal number of required interventions.
For both problems, we obtain exponential improvements our analysis gives the first non-trivial competitive ratio in expectation; in contrast, prior works [CS23, ZSU21] show that no deterministic algorithm can achieve better than linear approximation against the optimal solution for all instances.
Philosophically, the results in our work are a step towards the study of targeted causal discovery problems arising from various applications, where recovering the entire causal graph is unnecessary.
Organization. In Section 2, we provide formal definitions and useful results. In Section 3, we state all our main results. We provide our algorithm for Meek separator and its analysis in Section 4. We use the Meek separator subroutine to solve for subset search in Scction 5 and causal matching in Section 6. In Section 7, we demonstrate empirically our proposed algorithms on synthetic data.
2 Preliminaries and Related Work
2.1 Basic Graph Definitions
Let G = EV,E) be graph on |V| = n vertices. We use V(G). E(G) and A(g) S E(G) to denote its vertices, edges, and oriented ares respectively. When the referred graph is clear from the
In this work, we assume causal sufficiency [SGSHO0] and noiseless setting with given observational data.

---

context, we use V (or E) instead of (G)) (or E(G) for simplicity. The graph g is fully oriented if A(G)= = Eg),, and partially oriented otherwise. For any two vertices u, u E V. we write v they are adjacent and u & otherwise. To specify the are orientations, we use n - or u <- v. For any subset V S V and E' S F. let 9 [ and G [F'] denote the vertex-induced and edge-induced subgraphs respectively. Consider vertex E V in a directed graph, let Pa(r)) Anc(v) and (es(v) denote the parents, ancestors and descendants of respectively. Let Des(t) = Des(t) U {F} and Anc[u] = Anc(v) U {v}. The skeleton sGe of graph & refers to the graph where all edges are made undirected. A v-structure refers to three distinct vertices u, V w such that u + v f w and o6 w. A simple cycle is sequence of l 2 3 vertices where t1 02 ~ ...... 2k 21. The cycle is directed if at least one of the edges is directed and all oriented ares are in the same direction along the eycle. A partially oriented graph is chain graph if it contains no directed cycle. In the undirected graph g FE \ A] obtained by removing all arcs from a chain graph 9, each connected component in g(F) \ A] is called a chain component. We use (g(() to denote the set of all such chain components, where each chain component H E CC(() is a subgraph of G and V = Úxecc(g) V(H). For any partially oriented graph, an acyclic completion consistent extension refers to assignment of orientations to undirected edges such that the resulting fully oriented graph has no directed cycles.
2.2 Graphical Concepts in Causal Models
Directed acyelic graphs (DAGs) fully oriented chain graphs, where vertices represent random variables and their joint distribution P factorizes according to the DAG: P(vi...., vn)) I P(r; Pa(v)). We can associate a valid permutation topological ordering V - [n] to any (partially oriented) DAG such that oriented ares u + v satisfy T(u)- x(V)) (and assigning undirected edges u as u - u when ru)) < π(t) is an acyclic completion). Note that such valid permutation is not necessarily unique. Two DAGs G1, G2 are in the same Markov equivalence class (MEC) if any positive distribution P which factorizes according to Gi also factorizes according G2. For any DAG G, we denote its MEC by [G]. It is known that DAGs in the same MEC share the same skeleton and v-structures [VP90, AMP97]. A moral DAG is a DAG without v-structures. Figure illustrates this definition. The essential graph E (G) of [g] is partially oriented graph such that an are u - oriented if u - v
(a) A moral DAG.
(b) A DAG with v-structure 2 + 4 + 3.
An example of moral DAGS. (a) moral DAG without v-structures. (b) an immoral DAG.
Figure 1:
in every DAG in MEC (G). and an edge ~ is undirected if there exists two DAGs G1, G2 E [g] such that u - v in G1 and u +- v G2. An edge u ~ V is covered edge [Chi95, Definition 2] if Pa(u) \ {v) = Pa(u) {u). We now give some useful definition and result for graph separators:
Definition 1 (a-separator and ax-liquee separator [CSB22J. Let A, B, C be a partition of the vertices V of a graph G. We say that C' is a-separator if no edge joins* vertex in A with a vertex in B and |A|, [B] a IV.. We call C' is an a-clique separator if it is an a-separator and a clique. 5
Lemma 2 (Theorem 1,3 in [GRE84], instantiated for unweighted graphs). Lei G = (V, E) be chordal graph with [V] 2 2. Denote w(G) the size of us largest clique. There exists a 1/2-clique separator C involving at most wG)) vertices. The clique C can be computed in O( ((FE)) time.
2.3 Interventions and Verifying Sets
An intervention I C V. associated with random variables V with joint distribution P that factorizes according G. is an experiment where the conditional distributions P(u Pa(v)) for changed. Hard interventions refer to changes that eliminate the dependency between v and Pa(u). while soft interventions modify this dependency without removing it [ES07]. Let p' denote the interventional distribution. Observational data is special case where I = Ø. An intervention is
are
atomic if T and bounded if |7| < k. We call a set of interventions I C 2 an intervention set.
We denote Ú B as the union of two disjoint sets A and B. 'Edge ~ e joins vertex with vertex
A clique is fully connected graph, i.c., u ru e for every pair of distinct vertices in the graph.
"A chordal graph is graph where every cycle of length at least has a chord (c.f. [BP93].
3

---

(a) Essential graph Eg).
(b) (g) with I (13), {4}}
(c) Connected components of (C))
Figure 2: An example illustrating essential graphs and connected chain components. Suppose the groud-truth DAG is given in Fig. 1a. (a) the essential graph of G. (b) the Z-essential graph of g after two atomic interventions I = {{3), }. {4]} where edges oriented by I are indicated in red. (c) three connected components of (g) after removing the oriented edges.
With observational data, DAG G is generally only identifiable up to its MEC", i.e., E(G) [AMP97]. Identifiability can be improved with interventional data and is known that intervening on allows us to infer the edge orientation of any edge cut by I and V \ and possibly additional edges given by the Meek rules (Appendix A), for both hard [HB 12] and soft [YKU18] interventions. 8 For intervention set I, let the Z-essential graph & of G be the essential graph representing all DAGs in [g] whose orientations of ares cut by I and \ I are the same as G for all E I. Figure 2 illustrates these concepts. The aforementioned results state that G can be identified up E9( with observational and interventional data from I. We state some useful properties about I-essential graphs from [HB14], First, every I-essential graph is chain graph with chordal chain components. This includes the case of I = Ø. Second, orientations in one chain component do not affect orientations in other components. In other words, fully orient any essential graph (g)) it is necessary and sufficient to orient every chain component in Ez (g).
A verifying set I for DAG & [CSB22] is an intervention set that fully orients G from E(g), possibly with repeated applications of Meek rules (see Appendix A). In other words, for any graph ς = (V, E) and any verifying set I of G, we have (G( = G. A subset verifying set I [CS23] for a subset of target edges T S E in a DAG G is an intervention set that fully orients all ares in T given Eg). possibly with repeated applications of Meek rules. Note that the subset verifying set depends on the target edges and the underlying ground truth DAG the subset verifying set for the same T C E may differ across two different DAGs 91, G2 in the same Markov equivalence class.
For bounded interventions of size most k, the minimum verification number vs (9, T) denotes the size of the minimum size subset verifying set for any DAG g = (V, E) and subset of target edges T C E. We write v1 (G, T') when we restrict to atomic interventions. When & = 1 and = E (i.e., full graph identification), [CSB22] showed that it is necessary and sufficient to intervene on a minimum vertex cover of the covered edges in G. For any intervention set I C 2", we denote R(G,I) (G)) E as the set of oriented ares in the I-essential graph of DAG G. For cleaner notation, we write R(G, I) for one intervention I = {I} for some C V, and R(G, v) for one atomic intervention I {{u}} for some e EE V.
Definition 3. For any intervention set C 2V, define G = G|E \ R(G, I)] as the fully oriented subgraph of G induced by the unoriented edges in Er In addition, for u E V. let Pag.z(u) {z é V x + u E R)G as the recovered parents of u by I.
3 Results
Here we state all the main results of the paper. One of the primary contributions of our work is a randomized algorithm that outputs an intervention set I of small size such that all connected components in the resulting I-essential graph have small sizes. We now formally define such intervention sets as Meek separators. An example of 1/2-Meek separator is shown in Figure 3.
Definition 4 (a-Meek separator). We call an intervention set an a-Meek separator of & if each connected component H. E CG) satisfies: [VH)) aGV(
Note that Meek separators differ from the traditional graph separators in Definition 1, where in the latter we have bounds on the sizes of connected components in G\I instead of CC(Ex(9)) Graph separators of small size may not exist. For example, consider a fully connected DAG g = (V, E)
With additional parametric assumptions (c.g., [PB14]), additional identifiability can achieved. For both cases, "faithfulness" assumption needs to be assumed for P, pd (c.f. [YKU18]).

---

(a) DAG G. (b) 1/2-Meck separator Z= ((2)). (c) CC(E=(9)).
(d) 1/2-//apppppp separator {2,3}.
Figure 3: An example comparing a 1/2-Meek separator with a 1/2-graph separator. (a) the underlying
true DAG G. (b) the essential graph &r(9) after intervening the 1/2-Meek separator I ([2) where edges oriented are indicated red. (c) connected components of size I (i99)/2 in (g) (d)
the undirected version of with the 1/2-graph separator {2, 3) highlighted.
that forms a clique. Any a-graph separator in 9 must contain at least (1 - a:) VV vertices, since every pair of vertices in the clique is connected. In contrast, show that small-sized Meek separators always exist for any DAG. Moreover, we can efficiently find such separators by performing very few interventions, given by the following theorem which we prove in Section 4.
Theorem 5 (Meek separator). Given essential graph E(G) of unknown DAG G. there exists a randomized procedure MeekSeparator (given in Algorithm 1) that runs in polynomial time and adaptively intervenes
sel of atomic interventions I such that we can find 1/2-Meek separator of size at most and I. [[Z]] I Ollog (G)), where w(G) denotes the size of the largest clique in G.
Although in the above result, we intervene on (log (g)) nodes, our proofs show that there always exists Meek separator of size at most 2. However, to find such Meek separator without knowing 9 priori, our algorithm needs to perform (log (g)) many interventions. The above result is significant because it can be used to design divide-and- hiide-and-conquee conquur based approaches for various problems. Specifically, we use the Meek separator algorithm as a subroutine to develop approximation algorithms for the subset search and causal matching problems.
Subset Search. Our first application of the Meek separator result that it can be used as a subroutine for approximately solving the subset search problem, as demonstrated in Algorithm 2. The analysis of our algorithm for subset search consists of two parts: (1) lower bound on the number of interventions required for any algorithm (even with knowledge of G) to solve subset search, and (2) an upper bound on the number of interventions needed for our algorithm to solve subset search. By combining the two parts, we can bound the competitive ratio of our algorithm.
For the first part, we provide lower bound for the subset verification number described below. Recall that the subset verification number is the minimum number of interventions needed to orient edges in T by any algorithm with full knowledge of G. Therefore it is a natural lower bound the number of interventions required for any algorithm to solve subset search.
Lemma 6 (Lower bound). Let G = E) be a DAG and T C E be a subset of target edges, then, (G, 2 maxigv ΣhECOLE ((E(H) nT + Ø)
For the upper bound, we show that our randomized algorithm, designed using the Meek separator subroutine, is competitive with respect to the aforementioned lower bound. Thus, it achieves logarithmic approximation to the optimal number of interventions required to solve subset search.
(V, be a DAG with [V] = n and T C F. be a subset of target edges. Algorithm that takes essential graph E(G) and T input, runs in polynomial time and adaptively intervenes on a set of atomic interventions C V that satisfies, E [[]] I O logn- n- (g)) 1n (G.T) and T S R(G.I) Furthermore, the special case Tf E, the solution returned by it satisfies, E [[Z]]] S O(log n) (9) and E. C R(G,I).
Theorem 7 (Upper bound). Let
Importantly, our result provides the first known competitive ratio with respect to the subset verification number Vn (G, T). Prior our work, a full- full-graph identification algorithm that competitive with respect to 2 (g) = 2 (G, E) was provided by [CSB22]. 2 (g) is not a valid lower bound for the subset search problem. In particular, the value of 1n (9,T) for certain T could be substantially smaller than v (G). For instance, if G is a clique and T is an edge incident to particular node, then (9 T) = 1 while vn (9) = 4/2. Hence, the benchmark based on the full-graph verification number can be significantly weaker compared to that based the subset search verification number.
The expectation in the result is over the randomness of the algorithm.
5

---

Additionally, for the subset search problem, [CS23] showed that there does not exist any deterministic algorithm that achieves a competitive ratio better than ((n) with respect to 2i (g. T). Therefore. our result shows that subset search is part of the large class of problems in algorithm design where randomization substantially helps. Finally, when T = F., we get a Olog n) approximation for recovering the entire DAG, which matches the current best approximation ratio by [CSB22].
Causal Matching. Another application of our Meek separator result is for solving the causal matching problem. We consider the same setting as [ZSU2I] (details provided in Section 6). In [ZSU21], it was shown that causal mean matching has a unique solution and can be solved by iteratively finding source vertices" 10 of induced subgraphs of the underlying DAG (Lemma I and Observation I in [ZSU21]]. We therefore provide an algorithm to find source vertices of any DAG, which can be used in the iterative process. Our algorithm uses the Meek separator result and is given Algorithm 3; the iterative process of using this algorithm to solve causal mean matching provided in Section 6 and Algorithm 4 in Appendix F.
Our analysis for causal mean matching consists of two layers. We first establish an upper bound on the number of interventions required in Algorithm 3 to identify a source vertex. Then we use this result within the iterative process derive an upper bound on the number of interventions needed in Algorithm/ 4 to solve causal mean matching.
Lemma 8 (Source finding). Let G = (V, E) be a DAG and U CV be a subset of vertices. Algorithm 3 that takes essential graph E() and U as input, runs in polynomial time and adaptively intervenes on a set of atomic interventions I C V, identifies a source veriex of the induced subgraph G(U] with E | & (log n- log (())
Theorem 9 (Causal mean matching). Let G be a DAG and I be the unique solution to the causal mean matching problem with desired mean v². Algorithm 4 that takes E(G) and μ¹ as input, runs in polynomial time and adaptively intervenes on set I S V, identifies I' with [| S
O (lgg (ggw(G)) |
Note that for causal mean matching with unique solution I", [I' provides trivial lower bound on the number of interventions required to match the mean. Therefore this result shows that our algorithm achieves a logarithmic approximation to the optimal required number of interventions.
Of note, this is the first average-case competitive algorithm with respect to the instance- based lower bound [Z*]. Prior our work, [ZSU21] provided an efficient algorithm. which is log (n) competitiive with respect to any algorithm in the worst case. Such worst-case analysis is equivalent to the scenario where there exists an adaptive adversary when running the algorithm. This may limited as it relies on extreme cases that may not accurately represent real-world scenarios. Furthermore, the number of interventions required by any algorithm in the worst case can be much larger than the instance-based lower bound | For example, if G is a clique and I is atomic intervention on its source vertex, then I is but the number of interventions required by any algorithm in the worst case is n. !1
4 Algorithm for Meek Separator
For any general DAG G, we consider the largest connected component H. E CC))(G)). It is well known that H is moral DAG. I is 1/2-Meck separator for H. we show that I also serves 1 1/2-Meek separator for G (Appendix D). Therefore, for the remainder of the section, we make the assumption that G is moral DAG without loss of generality.
4.1 Existence of Size-2 Meek Separator
For any vertex u E V(g), let A, = ((G))Des(u and B. = Des(u). Note that & A, and v & B therefore |Agl + B.ll + 1 = [V(G)). At the heart of our algorithm the following result which shows the existence of a Meek separator of size at most 2 with some nice properties.
Lemma 10 (Meek separator). Let G be moral DAG and K be a 1/2-clique separator of G. There exists vertex K satisfying the constraints |Aul S IV())/2 and |A,l |V(011/2 for all v e Des(u) n K. Furthermore, such a vertex u satisfies one of the two conditions: 1). either u is sink
10p is source vertex if and only if has no parents.
"Tis can be deduced by using Lemma 5 in [ZSU21].

---

vertex of G[] or 2). there exists vertex I such that, z E Des(u) n K and ((V(g)) n Des(u)) = (i.e., Z and are consecutive vertices in the valid permutation of clique K). In both the cases respectively, either { or {{a). {x}} is a 1/2-Meek separator.
Proof Sketch. Here we present an overview of the proof, focusing solely the case where is not a sink node of K, since this case encompasses all the key concepts. To demonstrate the existence (Lemma 10), we begin by establishing the following crucial result.
Lemma (Connected components). Let G be a moral DAG and e E V()) be an arbitrary vertex. Any connected component H. CC)E,(G)) satisfies of the following conditions: V(H) v or V(H) S B, or (HH) - A..
Returning Lemma 10, consider vertices and and note that when we intervene on both u and I, all the connected components within CC(E(u,a) (9)) are either individual nodes or subsets of the subgraph induced by either A, or B₃ or B,, n Ag. Since |A,| | < (V())/2 and [ar S (V( (as A /2)) we can conclude that all the connected components within A, or Bn have a maximum size of [V( Therefore, all that remains now is to bound the size of connected components that subsets of 2. Notably, these connected components H have intersection with the clique K and satisfy the condition V(H) n V(K) = Ø. To establish a size bound for these connected components, we prove the following result.
Lemma 12 (Size of connected components). Let G be a graph and K be an a-separator of G. Suppose H. a connected subgraph of 9 and V(H) n K Ø, then VVH) S a- (V))..
Combining all the previous analyses, we conclude that all the connected components within CC (G) have a maximum size of [GG))/2, and the set {u, x) is a 1/2-Meek separator.
4.2 Binary Search Algorithm
To make the existence result algorithmic, additionally observe the following structural properties.
Lemma 13 (Properties of connected components). Consider a moral DAG 9 and let K be an a-clique separator: Let U1, .......
... Ug be the vertices of this clique in valid permutation. We observe that
|Bm.. < B which in turn implies [Armm 2 A. Additionally, we have |A,, S a [V
To identify the Meek separator set [u, .). we simply need to locate two consecutive vertices in the clique where |Aul < (V())/22 and |A. > /221)/2. The aforementioned result indicates that we can utilize standard randomized binary search procedures to find these vertices efficiently.
Algorithm 1 Mcelsooparator(C.12
1: Input: Essential graph E(G) of a moral DAG G.
2: Output: A 1/2-Meek separator I ZU2
3: Let K be a 1/2-clique separator (Lemma 2). Initialize i = 0, Kg = K and Io = 23
4: while K; is non empty do
5: Let u, be a uniform random vertex from K,. Intervene on u,-
6:
Find H. CC(E,, (9)) such that IV [HH)) maximized.
7:
if IV (H.) < IV (91122 then
>> u, is a 1/2-Meck separator.
8:
Let ug I U (ug)), and return I. Let Pa,- = (v K - } and Qu, {(o E K u wi).
9:
10:
if there exists a directed path from to H4 then b VVHH) C Des(u;) and |Au, (V(9)1/2
Update K4+1 K, n Qu, and U4.
12: else
Update Ki+1 K2 n Pa, and x u4-
14:
Update i + 1.
15:
I = {[+}} U3=1 {(2,))
16:
return I.
Figure 4 gives an example of the proposed Algorithm." 13 In general, at each iteration i, we randomly select a vertex u; and determine the connected component H, with the maximum cardinality.
12 is sink vertex if and only has no children.
II Appendix C, we provide an extended example where the skeleton is not complete, highlighting that the Meek separator can be found by focusing the 1/2-clique separator.
7

---

(a) Iteration Ko (1,2,3.4)
(b) Iteration Uo K1 (2,3,4)
(c) Iteration 2 M1 K₂ (2,3).
(d) Iteration
Mg
Figure 4: An example of Algorithm finding the Meek separator in the ground-truth DAG in Fig. 3a. The sets K; are highlighted; oriented edges e., (G) by intervening on u, are in grey; connected components in CC(E., (G)) are in black. (a) suppose we take Kg K = V(G)
the 1/2-clique separator. (b) suppose we pick uo = from Ko. then Ki = Ko n Quy = {2, 4]. (c) suppose we pick W1 4 from K1, then K₂ = K1 n P.j (2.3). (d) suppose we pick U2 = 2 from K2, then
Algorithm terminates (line 7) returning meek separator = {2] and = {1, 4} that helps find it.
[V(H)) < IV(21 we have found Meek separator. Otherwise, we verify if a directed path exists from uy Hi. In appendix (Lemma 19), we demonstrate that if such a path exists, then (HH)) C Des(u:) = B.,, implying that |A,, S (V(9)//2 (since IAu, + Bu, + confirm if u, the desired vertex u, we need verify that all its descendants satisfy |A, (V(01//2. Consequently, we recursively examine the vertices in K that are descendants of u, in K, Similarly, the u, to H. path doesn't 't exist, then Lemma 19 implies that V(H)) S ((g) Des [u Au, and |Aa, /2) Therefore, to find the desired vertex u. we recursively examine the vertices in K that are ancestors u, K, similar analysis holds for the desired vertex æ, and intuitively we conclude that the above algorithm outputs intervention set that contains vertices and satisfying the conditions of Lemma 10. The guarantees of the above algorithm are summarized below.
(V))). To
Lemma 14 (Output of MeekSeparator), The algorithm MeekSeparator performs at most Olog K() interventions in expectation and finds vertex u E K that either a 1/2-Meek separator or satisfies the following conditions: |Aul s IV(0)/2 and [A,] > IV for all Des(u) n K.
All proofs can be found in Appendix D. Combining Lemma 14 and Lemma 10 results in Theorem 5.
5 Algorithm for Subset Search
Here we present our algorithm for the subset search problem that proves Theorem 7. Our algorithm is based on the Meek separator subroutine and a description of the algorithm is given in Algorithm 2. In the remainder of this section, we present proof sketch to establish the guarantees.
Algorithm 2 Atomic adaptive subset search.
1: Input: Essential graph (() of a DAG G and a set of target edges C E(g).
2: Output: Atomic intervention set I s.t. T C R)G
3: Initialize i = and In Ø.
4: while R(G I+) Ø do
5: Initialize T, < Ø
6: for CC(E,, (G)) of size |H| > 2 and E(H) nT + + do
7: Invoke JH = McckSoparator(71, 1//2). Update J, = JTU Ju.
8: Update I+1 + I, U J. and iit
9: return I,
Correctness. Upon the termination of our algorithm, it is worth noting that all the connected components that encompass the target edges T have a size of 1. This observation leads to the immediate implication that the edges belonging to T are oriented.
Competitive Ratio. To bound the competitive ratio, we first bound the total cost our algorithm and then relate to the subset verification number. To bound the total cost, first show that the number of outer loops in our algorithm is at most (log n.). This holds because, in each outer loop. the size of the connected components containing the target edges T decreases at least by multiplicative factor of 1/2. After (log n) such loops, all these connected components will have a size of 1, implying that all edges in 7' are successfully oriented, leading the termination of our algorithm.
Next, to bound the cost per outer loop, we consider Ts, which represents the set of interventions performed during the i-th loop. It is worth noting that Ti is union of Meek separators JH for

---

each connected component H. E CC(EL, (G)) such that E(H) & Ø. Thus, the cost per loop can be expressed as [J. = ΣhECCLET, (9)) ((H(H) nT + 2) [Jxl.- By Theorem 5, the Meek separator we obtained for each H is of size (log w/ (H)) S (log (G)) We can conclude that the cost per iteration is at most: |Jil S Olog (()) Σ ExeCoiEz, (9)) (((H) nT + Ø). To relate this cost to the subset verification number, we utilize the lower bound result from Lemma 6, which states that: / (G, T) 2 maXIcv (Hecc(E1(9)) (H) nT' * Ø). Combining the above equations, we obtain |T.] & (log (()) (G. T). As there are at most (log n) iterations in total, the total cost of our algorithm can be bounded by: (log log (L)))) T) We defer the detailed proofs of Theorem (upper bound) and Lemma (lower bound) to Appendix E.
6 Algorithm for Causal Mean Matching
Here we study the causal mean matching problem. En route, provide algorithm that, given an essential graph Eg) of a DAG G and a subset U of vertices, finds a source vertex within the induced subgraph G[U]. This source vertex, denoted as s, satisfies the property that there exists no vertex E U such that v E Asc(s). The description is given in Algorithm 3. This algorithm identifies source vertex of U in (log n log (G)) interventions and its guarantees are summarized in Lemma 8. Below, we present a concise overview of its proof.
Algorithm 3 FindSourcc(((())..)
1: Input: Essential graph {() of a DAG 9 and a subset of vertices U C V()).
2: Output: Atomic intervention set I and a source vertex in U.
3: Initialize i = 0 and To = Ø.
4: Let Co {H. E (C) (H) n n + Φ and let Ho E C be a connected component with no incoming directed path from any other component ' E Co.
5: while (V(HH: n U| > 1 do
6: Compute J. = McckScparator((((H)) 1/2) and intervene on it.
7: Let C++1 {H e CC(E,, (H,) ((H) n U + Ø} and let H4+1 E C++11 1 be connected
component with no incoming directed path from any other component H E C.+1.
8: Let I++1 = I U Jr Increment by I.
9:
return I, and ((H)).
As stated in the description, our algorithm invokes the Meek separator in each iteration and identifies the connected component containing source vertex and recurses on it. This connected component can be identified by finding the component that has no incoming directed path from any other components. Then as we invoke the Meek separator in each iteration, the size of the connected component decreases at least by a factor of 1/2. Therefore the algorithm terminates in Ollog n.) Since we perform at most Ollo (G)) interventions in each iteration, the total number of interventions performed by our algorithm is at most Olog n log (G)). This concludes our proof overview for the fource-finding algorithm. In the remainder, we use it to solve the causal mean matching problem.
Causal Mean Matching, We consider the same setting as in [ZSU21] with atomic interventions, where the goal is to find set of shift interventions I such that the mean of the interventional distribution Ey] [V] matches a desired mean μ². An atomic shift intervention set I with shift values (a. Joxkez modifies the conditional distribution as pz (v: = x + a, Upa()) = P(u; particular, [ZSU21] show that there exists a unique solution I" such that Ex [V] = 1a" and to find such I" it suffices iteratively find the source vertices of all vertices whose means differ from that of n² The intuition behind this is that (1) intervening on other vertices will not change the mean of the source vertex, and (2) the shift value of the source vertex equals exactly the mean discrepancy with respect to μ², Thus, our Algorithm 3 can be used as subroutine to solve for I iteratively. We
Upa(i)) for E I. In
describe the full procedure in Algorithm 4 in Appendix Our analysis of Lemma 8 is used derive the guarantee of A Algorithm 4 in Theorem 9. Details are deferred to Appendix F.
7 Experiments
Here, we implement our Meek separator to solve for subset search and causal mean matching discussed in the previous sections. Details and extended experiments are provided in Appendix G.

---

MadSSp
NetSpp
Werkaton
Madksp
vaticctton
2.5
(a) Subset search on r-oop model with r = 3 (b) Causal mean matching with varying
[T]
Figure 5: Meek separator for (a) subset search and (b) causal matching. Each dot is averaged across
20 DAGs, where the error bar shows 0.5 and 0.2 standard deviation in (a) and (b), respectively.
Subset Search. For this experiment, we consider the local causal graph discovery problem where the goal is to identify the target edges within an r-hop neighborhood of a random vertex v. We compare our method in Algorithm and its variant, MeekSep and MeekSep-1, against four carefully constructed baselines. The variant MeekSep-1 runs Algorithm 2 but checks after performing every intervention inside line 7 and terminates if the subset search problem solved. The Random baseline intervenes randomly sampled vertex at every step and terminates when the subset search problem is solved. The Coloring-PP FG baseline identifies the full causal graph using [SKDV15], where Coloring- NI is the variant that only identifies the subgraph induced by vertices incident to the target edges, similar to the method suggested by [CS23]. Our proposed methods consistently outperform these baselines across different graph sizes in Figure 5a. Finally, Verification shows the subset search verification number [CS23] which serves as a lower bound.
Causal Mean Matching. We consider Rénói graphs [ER60] with 50 vertices where the ground-truth solution I is randomly sampled from these vertices. We compare our Algorithm 4 and its variant, MeekSep and MeekSep-1, against four baselines proposed in [ZSU21]. The variant is in the fashion described for the subset search. The Random and CliqueTree baselines use the same backbone as MeekSep, but search for source vertex using randomly sampled interventions and the clique-tree tree strategy proposed in [ZSU21], respectively. Coloring- FG first identifies the full graph then solves for Z", whereas Verification is the lower bound that uses [Z*] interventions. The number of extra interventions relative to Verification is shown in Figure 5b, where observe our methods to outperform Random and Coloring-PP Empirically, our approach is competitive with the state-of-the-ar method CliqueTree while providing far better theoretical guarantees.
8 Discussion
In this work, we introduced Meek separators. In particular, we established the existence of a small- sized Meek separator and presented efficient algorithms to compute it. Meek separators hold great potential for designing
strategies to tackle various causal discovery problems. We demonstrated this by designing efficient approximation algorithms for two important problems in targeted causal discovery: subset search and causal mean matching. Our approximation guarantees exponentially better than the guarantees achievable by any deterministic algorithm for both problems. It would be an interesting future research endeavour to explore the application of Meek separators address other problems in the field of causal discovery.
Limitations and Future Work. We made several standard assumptions such as causal sufficiency and we considered the noiseless setting. In future work, it would be of interest to relax some of these assumptions. Particularly, we believe that investigating the sample complexity for conducting targeted causal discovery would be an important avenue to pursue.
In addition to these broad questions, there are some specific open problems. One such problem is understanding the weighted subset search problem. Although efficient algorithms have been proposed [CS23] to compute weighted subset verification numbers, the weighted subset search problem remains open. Exploring its approximability would be an interesting research direction. Moreover, for the causal mean matching problem, extending the matching criteria beyond the mean to encompass other higher-order moments of the distribution would be natural and compelling future direction.
10

---

Acknowledgements
The authors were supported by the the Eric and Wendy Schmidt Center at the Broad Institute, as well as NCCIH/NIH (IDP2AT012345), ONR (N00014-22-1-2116), DOE-ASCR (DE-SC0023187) the MIT-IBM Watson AI Lab, and Simons Investigator Award. J.Z. was partially supported by an Apple AI/L PhD Fellowship.
References
[AB02] Réka Albert and Albert-LászIó Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
[AMP97] Steen A. Andersson, David Madigan, and Michael D. Perlman, A characterization of Markov equivalence classes for acyclic digraphs. The Annals of Statistics, 25(2):505-541, 1997.
[ASY+19] Raj Agrawal, Chandler Squires, Karren Yang, Karthikeyan Shanmugam, and Caroline Uhler. Abed-strategy: Budgeted experimental design for targeted causal structure discovery. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3400-3409. PMLR, 2019.
[ATS03] Constantin F Aliferis, loannis Tsamardinos, and Alexander Statnikov. Hiton: novel markov blanket algorithm for optimal variable selection. In AMIA annual symposium proceedings, volume 2003, page 21. American Medical Informatics Association, 2003.
[BP93] Jean R. S. Blair and Barry W. Peyton. An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation, pages 1-29. Springer. 1993.
[CD12] Anne BC Cherry and George Q Daley. Reprogramming cellular identity for regenerative medicine. Cell, 148(6):1 1000::11000010 10-11112221111221111 2012.
[Chi95] David Maxwell Chickering. A Transformational Characterization of Equivalent Bayesian Network Structures. In Proceedingy of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI'95, page 87-98, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.
[CS23] Davin Choo and Kirankumar Shiragur. Subset verification and search algorithms for causal dags. arXiv preprint arXiv:2301.03/ 2023.
[CSB22] Davin Choo, Kirankumar Shiragur, and Arnab Bhattacharyya. Verification and search algorithms for causal DAGs. Advances Neural Information Processing Systems, 35, 2022.
[DL05] Eric Davidson and Michael Levin. Gene regulatory networks. Proceedings of the National Academy of Sciences, (02(14):4935-493 2005.
[ER60] Paul Erdös and Alfréd Rényi.
evolution of random graphs. Publ. Math. Inst.
Hung. Acad. Sci, 5(1): 1960.
[ES07] Frederick Eberhardt and Richard Scheines. Interventions and Causal Inference. Philoso- phy of science, 74(5):981 9959 2007.
[FLNPOO] Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er. Using bayesian networks to analyze expression data. Journal of computational biology, 7(3--):0116600 2000.
[FMT+21] Chris J Frangich, Johannes C Melms, Pratiksha I Thakore, Kathryn R Geiger-Schuller, Pa- tricia Ho, Adrienne M Luoma, Brian Cleary, Livnat Jerby-Arnnn, Shruti Malu, Michael Cuoco, al. Multimodal pooled perturb-cite-seq screens in patient models define mech- anisms of cancer immune evasion. Nature genetics, 53(3):332-335 221211111244 2021.
[GHD20] Juan L. Gamella and Christina Heinze-Deml. Active invariant causal prediction: Experi- ment selection through stability. Advances Neural Information Processing Systems, 33: 13:15444-55475 2020.
11

---

[GKS 19] Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Adsera, and Guy Bresler. Sample Efficient Active Learning of Causal Trees. Advances in Neural Information Processing Systems, 32, 2019.
[GRE84] John R. Gilbert, Donald Rose, and Anders Edenbrandt. A Separator Theorem for Chordal Graphs. SIAM Journal on Algebraic Discrete Methods, 5(3):306-313, 1984.
[GSKB18] AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted Experiment Design for Causal Structure Learning. In International Conference on Machine Learning, pages 1724-1733. PMI.R 2018.
[HB12] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, (1l:)):209224444 2012.
[HB14] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926-939, 2014.
[HDPM18] Christina Heinze- Jonas Peters, and Nicolai Meinshausen. Invariant causal predic- tion for nonlinear models. Journal of Causal Inference, 6(2), 2018.
[HSSC08] Aric Hagberg, Picter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National LLb.(LA Los Alamos, NM (United States), 2008
[KDV17] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-Optimal Learning of Causal Graphs. In International Conference on Machine Learning, pages 1875-1884. PMLR, 2017.
[Mee95] Christopher Meek. Causal Inference and Causal Explanation with Background Knowl- edge. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI'95, page 403-410, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.
[PB14] Jonas Peters and Peter Bühlmann. Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1):219-228, 2014.
[Pea03] Judea Pearl. Causality: models, reasoning, and inference. 19(4):675-685, 2003.
Econometric Theory,
[RHBOO] James M Robins, Miguel Angel Hernan, and Babette Brumback. Marginal structural models and causal inference in epidemiology. Epidemiology, pages 550-560, 2000.
[SGSH00] Peter Spirtes, Clark N. Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT press, 2000.
[SKDV15] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vish- wanath. Learning Causal Graphs with Small Interventions. Advances in Neural Informa- tion Processing Systems, 28, 2015.
[SMG* 20] Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active Structure Learning of Causal DAGs via Directed Clique Trees. Advances in Neural Information Processing Systems, 33:21500-21511, 2020.
[SU22] Chandler Squires and Caroline Uhler. Causal structure learning: a combinatorial per- spective. Foundations of Computational Mathematics, pages 1-35, 2022.
[VP90] Thomas Verma and Judea Pearl. Equivalence and Synthesis of Causal Models. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, UAI '90, page 255-270, USA, 1990. Elsevier Science Inc
12

---

[WBL21] Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Extendability of causal graphical models: Algorithms and computational complexity. Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 1258-1257. PMLR, 27-30 Jul 2021.
[YKU18] Karren Yang, Abigail Katcoff, and Caroline Uhler. Characterizing and learning equiva- lence classes of causal dags under interventions. In International Conference on Machine Learning, pages
PMLR, 2018.
[ZSU21] Jiaqi Zhang, Chandler Squires, and Caroline Uhler. Matching a desired causal state via shift interventions. Advances in Neural Information Processing Systems, 34:1 34:19923- 19934, 2021.
13

---

Contents of Appendix
Meek Rules
15
B Preliminaries and Other Useful Results
15
Another Example of Algorithm
15
D Remaining Proofs for Meek Separator
16
D.1 Proof for Lemma 11.
16
D.2 Proof for Lemma 12.
17
D.3 Proof for Lemma 13.
17
D.4 Proof for Lemma 10.
17
D.5 Proof for Lemma 14.
18
D.6 Proof for Theorem 5
19
E Remaining Proofs for Subset Search
20
E.1 Lower Bound for Subset Search (Lemma 6)
20
E.2 Upper Bound for Subset Search (Theorem 7)
20
Remaining Proofs for Causal Mean Matching
21
F.1 Proof for Lemma
22
F.2 Proof for Theorem 9
22
Details of Numerical Experiments
23
G.1 Subset Search
23
G.2 Causal Mean Matching
24
14

---

A
Meek Rules
Meek rules refer to collection of four edge orientation rules that are proven to be sound and complete when applied to a set of arcs that possesses a consistent extension to a directed acyclic graph (DAG) [Mee95]. With the presence of edge orientation information, it is possible iteratively apply Meek rules until reaching a fixed point, thereby maximizing the number of oriented arcs.
Definition 15 (Consistent extension). For a given graph G, set of ares is considered have consistent DAG extension if there exists permutation of the vertices satisfying the following conditions: (i) for every edge {u, v in G, is oriented as u - v whenever (u) < (T)), (ii) there are no directed cycles, and (iii) all the given arcs are included in the extension.
Definition 16 (The four Meek rules [Mee95], see Figure 6 for an illustration).
RI Edge {a,6} 63 E E' \ i oriented + b if V such that + and cf b.
R2 Edge {a.b) E E \ A is oriented as a + b if 3 E V such that - -
R3 Edge b) E A is oriented as + b if C, d E V such that d ~ c, d + b t and c d.
R4 Edge b) b +f d.
E' \ | is oriented as + b 3 c, d E V such that d a d + and
K4
Figure 6: An illustration of the four Meek rules
An algorithm [WBL21, Algorithm 2] has been developed to compute the closure under Meek rules efficiently. The algorithm runs in Odd (EE) time, where dl represents the degeneracy of the graph S
B Preliminaries and Other Useful Results
Here we state some useful notation and results. For an are v in G, we define RT' v) C V and (G, u v) C 2 to refer to interventions orienting are - v. Equivalently, v) (ICV |1| < k,u
I u + v) (w E V v E R(G. I)}.
R (G,u
E R(G,w) w)) and
Proposition 17 (Theorem in [CS23]). Consider DAG G = (V, and intervention sets I,J C
2V. The following statements are true: 1) ske is exactly the chain components of Eg( 2) G does not have new v-structures. 3) For any two vertices u and v in the same chain component (g)), we have Pag.z(u) = (v). 4) if -VU R(G, I), then u and belong to different chain components of (g)). 5) Any acyclic completion of (g² can be combined with R(G, I) to obtain valid DAG that has the same essential graph and I-essential graph as E(g) and (g),,, respectively. 6) R(GZ, (T) = R(G.T) I). 7) R(G,IUJT = RiGT. U R(G,I). 8) R(G.T)).
R(G,IUJ) = R(GT. J] R(G ()Ú
Lemma 18 (Theorem 10 in (CS23J). Let G = E) be DAG without v-structures and u + in G be unoriented in E().. Then, B (G, u + v) = Des[w] n Anc(v) for some w E Anccuu].
C Another Example of Algorithm
We provide another example of Algorithm in incomplete graph, highlighting that Meek separator by solely focusing on the 1/2-clique separator.
A d dedegenerate graph is an undirected graph in which every subgraph has vertex of degree at most d, Note that the degeneracy of graph is typically smaller than the maximum degree of the graph.
15

---

Ground-truth DAG.
(b) Iteration Kp {1,2,3, 4).
(c) Iteration up 1, Ki = (2,3, 4).
3
6
9
3
6
(d) Iteration 2: 4, K₂ 32,3).
Iteration U2 2.
Figure 7: An example of Algorithm finding the Meek separator in an incomplete graph. The sets K; are highlighted; oriented edges in &v, (9) by intervening u, in grey; connected components in (C,(,,, (9)) are in black. (a) ground-truth DAG G. (b) suppose we take Ko K = V(g) as the 1/2-clique separator. (c) suppose we pick un
from Ko. then K1 Ko Quo {2, 4]. (d)
suppose we pick K2, then Algorithm terminates (line 7) returning meek separator I {2} and =1,,4 4) that helps find it.
from K1, then K2 = K1 n Pu. {2, 3]. (e) suppose we pick u2 = from
D Remaining Proofs for Meek Separator
Here we provide all the remaining proofs for the Meek separator algorithm.
D.1 Proof for Lemma
Lemma 11 (Connected components). Let G be moral DAG and v E (G) be arbitrary vertex. Any connected component H (9)), satisfies one of the following conditions: V(H) or (HH) S B, or ((H) C A,
Proof. Performing an intervention node results in orienting all its adjacent edges. Consequently. one of the connected components in (G). {u), and it adequate to focus on the remaining connected components.
Suppose, for the sake of contradiction, that there exists connected component H CC(E, such that H contains two vertices a and b, such that, a E A,, and E B, Since a and belong to the same connected component, we consider the path within H that connects these vertices. Notably, this path includes two adjacent vertices and d, where e e A, and d B,, and the edge (c, d) remains unoriented.
However, according to Lemma 18, intervening on any vertex within the set Des[w] n Anc [d] for some fixed w Anc [c] will orient edge (c, d). As Anc/c), we have Des Des (w] and therefore Des c] O Anc [d] C Des[w] n Anc[d] Consequently as E Des[c] n Anc[d], we get that intervening on orients the edge (c,d).
Hence, it is impossible for vertices a A, and E B, to belong to the same connected component. Consequently, conclude the proof.
16

---

D.2 Proof for Lemma 12
Lemma 12 (Size of connected components). Let G be a graph and K be an a-separator of g. Suppose H. is a connected subgraph of G and ((H) n K = 2, then [V(H) S a (V(G)).
Proof. Since H. is a connected subgraph of G and (H) n (K) 2, removing K from 9 does not result in the deletion of any edges or vertices from the subgraph H. Consequently, the vertices in H will remain connected even after the removal of K, and they will all belong to the same connected component in the graph g K. Considering that K' is an a-separator, this further implies that [V(H) s a (V(()) Thus, we can conclude the proof.
D.3 Proof for Lemma 13
Lemma 13 (Properties of connected components), Consider a moral DAG 9 and let K be an a-clique separator: Let U1, Ugy.... Ut be the verfices of this clique in valid permutation. We observe that
[Bega| < Beeb which in turn implies
Amr41 2 An Additionally, we have |Au, S a [V()))-
Proof. Since es precedes 1e+1 in the true ordering defined by the underlying ground truth DAG G, follows that 1/+1 E Des(r;)- Consequently, we can deduce that (es("; S Des( which implies [ B S [Be,). Additionally, note that |A B + 1 [VG) Therefore, it holds that
|A 2 1-
Furthermore, U1 is the souree node of the clique, removing K ensures that all vertices in A., still in the remaining graph. They also induce a connected subgraph. Otherwise suppose a E Ag, and b E A., not connected. Then the parent of U1 path from a to v1 and the parent d of 11 path from b to 2i are not connected. This creates a v-structure c - 21 < d, contradicting 9 being moral. Thus As, is connected subgraph with no intersection with K. As K is a-clique separator, we have by Lemma 12 that AA, S a [V())) We conclude the proof.
D.4 Proof for Lemma 10
Lemma 10 (Meek separator). Let G be moral DAG and K be a 1/2-clique separator of G. There exists a vertex u E K satisfying the constraints |Aul S [V())/22 and |Apl > (V(011/2 for all v e Des(u) n K. Furthermore, such a vertex u satisfies one of the two conditions: 1). either u is sink vertex!5 of GK), or 2). there exists vertex x such that, x E Des(u) n K and ((V(s))ees()) n Des(u)) n K = Z (i.e., E and are consecutive vertices in the valid permutation of clique K). In both the cases respectively, either {u]} or {u). {m}} is 1/2-Meek separator.
Proof. Consider the vertices u1,.... Fgg of the clique K the true ordering defined by the underlying ground truth G. Since K is 1 1/2-clique separator, according to Lemma 13, we deduce that [A,y s [V(G)/ /2. Let u denote the last vertex, in terms of the true ordering, within the clique K that satisfies A. S (G)))/ It is important to note that u fulfills the constraints specified in the lemma.
Therefore there exists vertex u that fulfills these constraints. Now we show that any vertex that fulfills these constraints will satisfy one of two conditions, and that either {{u}} or {(w), { is 1/2-Meek separator.
Suppose u is a sink vertex of K. Let H E (C) and note that according to Lemma 11,
V(H)= {u] or V(H) Des(u) (u) V(H) C Des)) Since AA < <VV any H such that V(H) S V(G) (Des)eessp (uj satisfies [V(H) & [V()))/2. Now, suppose V(H) S. Des(u). (u). In this case, observe that (HH) n K = Ø and H is a connected subgraph of G. By utilizing Lemma 12, we immediately have V(H) S (9)1/22 Therefore, {[u}} will be a 1/2-Meek separator.
Suppose is not sink vertex. Consider the vertex that follows within the clique K in the ordering defined by the DAG G. Note that a E Des( (u) K and (Des(u) (V)) Furthermore from the definition of u, we also have that [ > (G) which further implies [B&| & I2) As intervening on more vertices only creates finer- finer-grained connected components, we have that for any J C VG),, w V(G), and H' CC(ESu(w) (G)), there exists an H" CC(E)(G) such that H' is a subgraph of H".
= Ø.
is sink vertex if and only if it has children.
17

---

Let I = fz, u), consider any H. E (C)) and note that there exist connected components M E CC(E,, (9)) and L E (G) such that H a subgraph of both M and L. We apply Lemma 11 to deduce that ((M) = u or (MM) C Des(u) or ((M) S (V(G))Deslu and V(I.)
or V(L) S (x) or V(L) _ (e)))e)))))
If (MM = u or ((M) S (es)) or V(L) = or V(L) C Des( then V(H) = u or V(H) x or (HH) S A. or (H) S Bg. As |Aul, - (g))) in all of these cases, we have that [(H) < [V(g))/2. Now consider the remaining cases where ((M) C Des(()) and V(L) S (es)) As is a subgraph of both M and L. we have that H. is subgraph of C, where C' satisfies V(C)= = Des(()) n ( Des(=]) As (Des(u) n (V()), (=l)) n = D, we have that V(C) n K = Ø. Furthermore, as H is subgraph of C' we also have that ((H) n K 2. As H. is a connected subgraph of G and VHH) n K = Ø, by utilizing Lemma 12, we have that [V(H) < [V(9)1/2. Therefore in all cases, we have that [V(H) S (V(9)1/2, and thus ((u), {x)) is a 1/ /2-Meek separator, which concludes the proof.
L
D.5 Proof for Lemma 14
Here we present proof for Lemma 14, which describes the structure of the solution returned by our Meek separator algorithm. In order to prove this lemma, we first establish the following result.
Lemma 19. Let 9 be a connected moral DAG and E V(g) be an arbitrary vertex. For any connected component H CC(E, there exists a directed path from H in (g) if and only i satisfies V (H) C Des(v). Furthermore, we can certify if H is a subset of G Des(u] or Des(v) in polynomial time.
Proof. Suppose there exists a directed path from e to a connected component H. then note that all the vertices in this directed path are descendants of and there exists vertex u E VHH) such that, E (v) Furthermore, by Lemma 11, we know that all the connected components H. should {u} or VHH = (es VHH) = (G)))De((o)) Using the fact that there exists a vertex u E V (H) which belongs to Des(v). Therefore, (v) n V(H) is not empty and we conclude that V (H) Des(v).
satisfy: V (H)
In the subsequent part of the proof, we examine the converse direction. Assume there exists a connected component H. such that V(H) S Des(c), and we aim to demonstrate the existence of a directed path from v to H in the interventional essential graph (G). Since H C Des(v), we consider the shortest directed path from v to H in G. Let w be the endpoint of this path P within H.
Suppose that all edges in P are oriented. In this case, we have already found directed path from v to H in (G). and our objective is achieved. Hence, we focus on the scenario where some edges in P are unoriented. Let P; V u0 + 21 + + Vy- - w denote the vertices along the path P. and let vs 1j+1 represent the first unoriented edge encountered.
Since all edges incident and 2/+1 are not adjacent. In such a case, the Meek rule RI would orient the edge 1, - 2/+1- However, since vj + Uj+1 remains unoriented, implies that the edge U + Ui+1 must exist. However, this contradicts the fact that P is the shortest directed path. Therefore, it must be the case that P is either entirely oriented or entirely unoriented. As some edges in P are oriented, we conclude that path P is completely oriented, thereby establishing the presence of a directed path from to H in the interventional essential graph (G).
are oriented, we have 2 * U. Now, consider the situation where U--1
In the remaining part of the proof, we discuss the time complexity of finding these directed paths. To certify whether V V(H) S (v) or (H) C VG) (es])Desl...... all we need do check whether
directed path exists between e and any u E ((H). If the direction of the path is from v to H. then
V(H) S Des(o) or else (H) S ( Des(u]. To check whether a directed path exists between two
vertices can be done in polynomial time and therefore we can certify if V(H) C Des(v) or (HH) S V(G) (o). We conclude the proof.
Lemma 14 (Output of MeekSeparator). The algorithm MeekSeparator performs at most
(log Kl) interventions in expectation finds a vertex u E K that is either a 1/2-Meek separator or satisfies the following conditions: |Aul < (V(0))/2 and [A,| > 1V 22 for all Des(u) n K.
Proof. Consider clique K and a true ordering क defined on the vertices V(g) of the underlying ground truth DAG G. Let U1, ......, Ui represent the vertices in the clique K. labeled according to
18

---

the true ordering т. In other words, V precedes vj in x whenever i < j. Since K is a 1/2-Clique separator, according to Lemma 10, we have [A,, S [ Additionally, based on Lemma 13, we know that |A,1 S | for all j E [1, 1]. Let Eir- be the last vertex within the clique K in the true ordering such that A S V(2)
In our proof, we demonstrate that our algorithm can either discover a 1 2-Meeee separator or identify the vertex zy- within (log []) interventions, average. If, at any stage of the algorithm, u, is a 1/2-Meck separator, our task is complete. Consequently, for the remainder of the proof, we concentrate on the alternative scenario and establish that our algorithm locates vy.. In this case, observe that either V.-- corresponds to the sink node of K or we uncover the subsequent vertex, +1++1. in the ordering. Notably, according to Lemma 10, either case implies that I = {u} I {u, constitutes a 1 1/2-Meek separator.
During each iteration i of our algorithm, we intervene uniformly random chosen vertex u, from the remaining clique K;. Let Hi represent the largest connected component in the interventional essential graph & (G). The algorithm terminates when the size of the clique becomes empty. Notably, when we intervene on a vertex ug by Lemma 19, the existence of a directed path from u, to H, implies that Hi corresponds to connected component in the descendant subgraph of u,. Since [V(H)) > [V(G))/2. 2/222z it follows that [Des(u) (u.) > [V())/ which further implies [A..) S (V()) /2. We assign u, and observe that (De(()) ()) = (es(u,) > (V)))/2, implying |Aul S (V /2. In this scenario, we recursively proceed with the set Qu, n K;, which comprises the nodes that appear after the vertex u; in the true ordering It is worth noting that these vertices y E Qu, 0 K; satisfy |4, 2 |A,,| since E Des (u:) (Lemma 10).
In the other case, when no path exists from u; to Hi by Lemma 19, we deduce that V(H.) C Aug. thereby leading to |A,, > V())/2. Consequently, we assign x = uy and therefore |Aal > V(g)/2. In this situation, recursively proceed with the set P.ù OK, which represents the vertices appearing before the vertex u, in the true ordering π.
In both cases, it is important to note that K; always consists of a contiguous set of vertices (defined by the true ordering) within the clique K. Let 81+1 and 4,+1 denote the source and sink vertices, respectively. in the remaining clique Ki+1. In the first case, where Ki+1 = Qu, O K, the vertex Ø. In the latter case, where K2+1 = Pa, n K,,
u, satisfies Des(u) (u) n (G) the vertex u4 satisfies Des( (V()))Dee(()) n K Ø. In simpler terms, this means that vertex u (immediate parent) precedes the remaining clique K+ in the true ordering स, while vertex (immediate child) succeeds it within the clique K.
n
Our algorithm terminates when the remaining clique becomes empty, implying that either u is a sink vertex or u and x are consecutive vertices within the clique. In other words, Des(u) n (V(G) (z)(()) n K = Ø. Therefore, the solution returned by our algorithm satisfies the conditions of the lemma. The only remaining task is to bound the number of interventions required by our algorithm.
To bound the number of interventions or iterations, we need to analyze the decrease in the size of the clique K; at each iteration. Recall that K; consists of a contiguous set of vertices from the original clique K, and in each iteration, we randomly select a vertex u, As discussed earlier, our algorithm either outputs a 1/2-Meek separator some intermediate step or performs randomized binary search to locate the vertices vy- and +1++1 (if it exists), satisfying AA < (V())// and |A, IV /2)
Since the parents and children of a vertex within the clique K are known after intervening it, the algorithm essentially performs a binary search to find the vertices Vy- and t1+ The standard analysis of randomized binary search provides expected upper bound of Olog (K]) iterations.
Combining these insights, we can conclude the proof by establishing that the expected number of iterations is bounded by Ollog [K].
11
D.6 Proof for Theorem 5
Theorem 5 (Meek separator). Given an essential graph E(G) of an unknown DAG G, there exists randomized procedure MeekSeparator (given in Algorithm 1) that runs in polynomial time and
19

---

adaptively intervenes on set of atomic interventions I such that we can find 1/2-Meek separator of size most 2 and E [ (l))w(()), where w()) denotes the size of the largest clique in G.
Proof. The proof of the theorem for moral DAG follows immediately by combining Lemma 14 and Lemma 10.
In the remainder, extend result to encompass general directed acyclic graphs. While an informal argument for general DAGs has been provided at the beginning of Section 4, we now delve into further details to substantiate that argument. Let recall the definition of G G R(G, I and focus on the graph go This subgraph derived by removing both the v-structure edges and the oriented edges resulting from the application of Meek rules. According Proposition 17, we establish that G does not introduce any new v-structures and, therefore, is moral DAG.
To proceed, let H. & be the largest connect component within (G) and designate Z as a 1 1/2-Meek separator of H. Note that R(H.I) C R(g I) and as highlighted Proposition 17, 2). Consequently, the connected components
also determine that R(g I) within both the intervention essential graphs (g) and (g are identical. Since is a a/ 2-Mck separator for 9o it also functions half 1/2-Meek separator for G.
E Remaining Proofs for Subset Search
Here we present all the proofs for the subset search problem. The proof for the lower bound and the upper bound results are presented in Appendix E. and Appendix E.2 respectively.
E.1 Lower Bound for Subset Search (Lemma 6)
Here prove our lower bound result for the subset verification problem.
Lemma 6 (Lower bound). Lei G (V, E) be DAG and T C E be subset of target edges, then, (9 T) 2 maxigy ΣhECOLE (H) nT 20)
Proof. Consider intervention set I and let CC(E)(G) be the set of all connected components in the intervention essential graph Eg()). As interventions within each connected components are independent(HB111 14), have that,
(g,TT)
T (ECCCEE(()
Σ
For each H. E (9)), where TO E(H) is non-empty, it is trivial that v (H, T E(H)) 2 1 as we need at least one intervention to orient all the edges in E(H). Therefore the lower bound follows, which concludes the proof.
E.2 Upper Bound for Subset Search (Theorem 7)
Here we present comprehensive proof for the upper bound result. Although proof sketch of this result has already been presented in Section 5, we now provide additional details to solidify our argument.
Theorem 7 (Upper bound). Let g (V,E) be DAG with VV = n and T C E be a subser of target edges. Algoritium that takes essential graph Elg) and T as input, runs in polynomial time and adaptively intervenes on a set of atomic interventions S V that satisfies, E [[]]] < O log n lg): (G,T) and T C R(G,I) Furthermore, the special case of E. the solution returned by it satisfies, E [ I O(log n) vn (9) and E. C R(G,T).
Proof. As discussed in Section 5, the correctness of the Algorithm 2 follows because of the termi- nation condition of the algorithm. Note that, upon termination, all the connected components that encompass the target edges T have size of 1. This observation leads the immediate implication that all the edges belonging to T are oriented.
The expectation in the result is over the randomness of the algorithm.
20

---

In the remaining part of the proof, we analyze the cost of the algorithm and divide the analysis into two parts: the number of outer loops and the cost per loop.
The bound on the number of outer loops is straightforward. Since the size of connected components containing the target edges decreases at least by factor of /22 in each iteration, and after (log n) iterations all connected components either consist of a single vertex or do not have any incident target edges T, therefore our algorithm terminates in (log n) iterations.
To bound the cost per loop, note that, we invoke the Meek separator only on the connected components H. that have at least one target edge. For each such component H. Lemma 6 establishes that any algorithm must perform at least one intervention on this component. Our Meek separator algorithm performs at most O ([llg(((H) iteration, we perform at most Ollog (() (g, T) interventions. It is important to mention that when T F., use the lower bound from [SM++20] which states that any algorithm would require at least (+))) interventions to orient all edges within the connected component H. whereas we only perform (log (H)) interventions in that iteration. Consequently, in the special case of E, the cost per iteration is at most (v (g, E)).
Ollog (G)) interventions for each component H. Hence, in any
Combining these analyses, we conclude that our algorithm orients all the edges in T by performing at most (log n log (()) (21 (9.T) T) interventions. In the special case of T = E, our total number of interventions is at most (log n) (9). This completes the proof.
F Remaining Proofs for Causal Mean Matching
Similar to the subset search, we use the Meek separator subroutine to provide approximation algorithm. A crucial step of our algorithm is a source finding algorithm, which given an essential graph E() and a subset of nodes U C V(G), returns a source node of U by performing at most (log n log (G)) number of interventions. Such a source-finding algorithm immediately helps us solve the causal mtatemmttching problem. In the remainder of the section we provide the source finding algorithm and use it solve the causal state matching problem. To understand our source finding algorithm, we need the following lemma.
Lemma 20. Let EV be a DAG, I C V be an intervention set and let S, H E Eg( Suppose there exists a directed path from S to H. then directed path exists from H. to S. Furthermore, if s, V be such that E Des(s) and they are not in the same connected component, then there exists directed path that is oriented from the connected component containing to the connected component containing t.
Proof. We are given that there exists directed path from S to H. As there exists a directed path from S to H. there exist a vertex & VSS) and / E (HH such that / E Des(s).
Suppose for a contradiction assume that there exists a directed path from H to S. Let u and v be the endpoint of this directed path in H and S respectively. By Proposition 17, we know that all the recovered parents for the vertices within the same connected component are the same; therefore we have that, (g) = Pa (9) and (9) = Pa., (9). Let t' be the parent of the directed path that connects the vertices s and t. Note that t' E Des [s] and could be $ or some other vertex. As and belong to different connected components t' + t is oriented. As Pa,,,((9) have that l' E Pa,,.T()) therefore u E Des((') which further implies E (8). As v E Des(u) (u) and as they are in different connected components, similar argument as above implies that s Des(u), which is a contradiction. Therefore H to S directed path does not exist. The analysis conducted above verifies the first claim of the lemma. In the subsequent portion, we focus on establishing the second part.
(9), we
Consider vertices and t such that & E Des I If both and t belong to the same connected compo- nent in the interventional essential graph &y (9), the lemma statement holds trivially. Henceforth, we assume that and belong to distinct connected components, denoted as S and T respectively.
Since E (+), there exists a directed path from vertex 8 to vertex / in the ground truth DAG G. Let us denote Q as the shortest directed path from 8 to I. in G. To form path P. we remove the edges within the connected components S and T from Q and retain only the edges that connect $ and T. Consequently, P represents this modified portion of path Q. Furthermore, let and w be the
21

---

respective endpoints of path P in S and T. As S and T are two different connected components, we have that some of the edges in oriented.
Suppose that all edges in P are oriented. In this case, we have already found a directed path from S to T in (9), and objective is achieved. Hence, focus the scenario where some edges in + + + - w denote the vertices along the path P. and uj+1 represent the first unoriented edge encountered.
P are unoriented. Let P let V/
Since U1 does not belong to the connected component S, we have that v - 01 is oriented and we have / # Now, consider the situation where 8j-1 and 0y41 not adjacent. In such case, the Meek rule RI would orient the edge V - 2-+1- However, since + v/ remains unoriented, it implies that the edge Uー-1 - 1j+1 must exist. However, this contradicts the fact that P is the shortest directed path. Therefore, it must be the case that is either entirely oriented or entirely unoriented. As some edges in P are oriented, we conclude that path P is completely oriented, thereby establishing the presence of a directed path from S to 7 the interventional essential graph & (9). which concludes the proof.
F.1 Proof for Lemma 8
We now provide the analysis of the source-finding algorithm. The guarantees of this algorithm summarized in the lemma that follows.
Lemma 8 (Source finding). Let G = (V, E) be a DAG and U C V be a subset of vertices. Algorithm: that takes essential graph {()) and U as input, runs in polynomial time and adaptively intervenes a set of atomic interventions C V, identifies a source vertex of the induced subgraph GUU) with | I Ollogn n log (
Proof. As Ti is /2eMeek separtors, immediately have that [V(H++1) S (V.))) Therefore our algorithm terminates in at most (log n.) iterations. By Theorem 5, note that, in each iteration, we make most (log w (H.)) (log (G+)) number of iterations. Therefore, the total number of interventions are at most Olog n log ((+)) It remains to show that we find the source node of U.
As in each iteration recurse on connected component H. E C₁ that has incoming edge from any other component H. E C. From Lemma 20, we know that Hi contains one of the source nodes of U. Therefore our algorithm always recurses connected component containing source node until the algorithm finds
Algorithm 4 CuusaaMeaMaccc(((()
1: Input: Essential graph EG) of DAG G, observational distribution of V, and desired mean μ²"
2: Output: Atomic intervention set I.
3: Initialize I" Ø and I (0).
4: while p2. (V) * p
5: Let T'= {ili
Ep- (V:) p.). Let Up be the identified source nodes in T.
6: Let G be the subgraph of (g) induced by T.
7:
8:
while Uy- Ø
9:
Let C be chain component of with no incoming edges. Perform interventions by FindSource(E(()) S) and append interventions to Z.
10:
11:
Update G and UT as the outer loop.
12:
Set a; 14 pz (V;) for i in Ur.
13:
Include the atomic interventions with perturbation targets Up and shift values {a heur respectively in I and perform I".
14:
return I
F.2
Proof for Theorem 9
Given such a source-finding algorithm, we can use to solve the mean matching problem. We summarize this result below.
22

---

Theorem 9 (Causal mean matching). Let G be a DAG and I' be the unique solution to the causal mean matching problem with desired mean y². Algorithm 4 that takes E(g) and μ¹" as input, runs in polynomial time and adaptively intervenes set I C V, identiiies Ie with R[[Z]] s O( logn log (ogw(G))- (
Proof. Note the outer loop in Algorithm takes at most [T'] round. In each of this round, the inner loop is ended with at most Olog log w(G")) interventions in expectation, proven by Lemma 8. Therefore, in expectation, the number of interventions performed is upper bounded by Olog n log (Z)))
G Details of Numerical Experiments
We implemented our methods using the NetworkX package [HSSC08] and the CausalDAG package https://githin com/uhlerlab//eee caa.aaaaaaaaaagg.... All code is written in Python and run on CPU. The source code of our implementation can be found at https://gtt thub. htmm/hherlab/meess
G.1 Subset Search
Problem Generation: We consider the r-hop model in [CS23]. In this model, an Erdös-Rényí graph [ER60] with edge density 0.001 on nodes is first generated. Then a random tree on these n nodes generated. The final DAG is obtained by (I) combining the edge sets using fixed topological order, where u - if it is in the combined edge sets and has smaller vertex label than and (2) removing y-structures by connecting + where u + v <- w and has a smaller vertex label than w. Then the subset of edges is selected to be the edges within r-neighborhood of randomly picked vertex.
For each dot presented in the results, we run each method on 20 different instances using the generation method described above. The average and standard deviation across instances are reported in the results.
Multiple Runs:
Figure shows similar results Figure 5a on the 3-hop model, where we vary the number of hops r E 11,2,4,5) 5} on DAGs with different sizes. Figure 9 shows the trend of varying number of hops on DAGs with different sizes. We observe method MeekSep and MeekSep-1 consistently outperform existing baselines.
Meripp
Menite
11
(a) y
(b) 2
319
302
(c)
(d) 5
Figure 8: Meek separator for subset search on r-hop model. Each dot is averaged across 20 DAGs, where the error bar shows 0.5 standard deviation.
23

---

(a) T1 50
(b) 71 75
(c) 100
(d) 150
Figure 9: Meek separator for subset search on r-hop model. Each dot is averaged across 20 DAGs, where the error bar shows 0.5 standard deviation.
G.2 Causal Mean Matching
Problem Generation: We consider three random graph models: Erdös-Rényí graphs, Barabási-Albert graphs [AB02]. and random tree graphs. The edge density in Erdös-Rényi graphs is 0.2 where the number of edges to attach from a new node to existing nodes in Barabási-Albert graphs is set 2. The intervention targets I is a random subset of vertex in the DAG.
For each dot presented in the result, we run each method on 10 different instances using the generation method described above. The average and standard deviation across instances are reported in the results.
Multiple Runs:
Figure 5b shows the result on Erdös-Rényi graphs, where we vary the number of targets in I" on DAGs with 50 nodes. Figure 10a and Figure 10b show similar results on random tree graphs and Barabási-Albert graphs. In Figure 10c, we consider Frdöös-Rény' graphs where [T*] is set to 25. This result shows the trend of varying number of nodes. We observe that our method is empirically competitive with the ttate-ofthee of-toh--ttttrt-r- art method CliqueTree across all cases.
(a) Random tree graphs
(b) Barabási-Albert graphs
(c) |T'| = 25
Figure 10: Meek separator for causal matching. Each dot is averaged across 10 DAGs, where the error bar shows 0.2 standard deviation
24


Reviews:
[{"review_id": "HdsjaeA0Cg", "reviewer": "Reviewer_BZ2Z", "summary": "* The paper provides an algorithm for finding a subset of vertices in a causal graph that, when intervened, can turn undirected edge into smaller connected components for learning a part of the causal graph. \n* The proposed algorithm comes with first known average-case provable guarantees for two applications:  subset search and causal matching. ", "questions": "* Suggestions:\n   * It would be good to use an example that both illustrates the idea of Meek separator and the limitations of the graph separator in Figure 1. Also, use the same example to show why any alpha-graph separator must contain at least $(1-\\alpha) |V|$ vertices. \n   * Add the description of w(G) in the Lemma 2 like theorem 5.\n   * Lemma 2 should cite Theorem 1 and Theorem 3 in the reference.\n   * Defining what “joins” means in Definition 1 would be good. \n   * In line 272, “the set $u,x$” should have curly brackets around $u, x$. Same for line 277.\n   * In line 536 of the supplement, $H$ should be $\\mathcal{H}$\n   * In line 575, $V(\\mathcal{H}) = V(\\mathcal{G}) \\setminus Des[u]$ should be $V(\\mathcal{H}) \\subseteq V(\\mathcal{G}) \\setminus Des[u]$.\n\n* Questions: \n  * The intervention set $\\mathcal{I}$ is defined as a set of sets right above definition 3, shouldn’t Figure 1b write $\\mathcal{I} = \\{\\{ 2\\} \\} $? \n  * In line 267, the authors use $V(\\mathcal{H}) \\cap V(K) = \\emptyset$, in line 270, the authors use $V(\\mathcal{H}) \\cap K = \\emptyset$, what is the difference between $K$ and $V(K)$?\n  * Is it possible to have different Meek separators where one is preferable to the other per iteration?\n  * Will the performance of the algorithms be different for soft interventions and hard interventions in the experiment?\n  * Regarding Lemma 11, how can you conclude intervening on $v$ orients the edge $(c,d)$ without proving $v \\in Des[w] \\cap Anc[d]$ for some $w \\in Anc[c]$ for any $v$ as described by Lemma 18?\n  * In the proof of Lemma 10, in line 573, it says \"It is important to note that u fulfills the conditions specified in the lemma.\", can you specify on which condition specifically? Also, in line 574, why does it need to suppose $u$ is a sink vertex of $K$ when $u$ is defined as the last vertex in terms of true ordering within $K$? \n  \n\n  \n", "limitations": "yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors propose a randomized algorithm that finds an intervention set of small size that, when intervened, decomposes the remaining undirected edges into connected components of smaller sizes. \n* The authors demonstrate the utility of the proposed targeted causal discovery algorithm in the problems of subset search and causal mean matching with analysis to show exponential improvements upon existing results in those domains.  \n", "weaknesses": "* It would be advisable to add examples to show how the algorithm finds a Meek separator.\n* The paper concerns problems motivated by practical scenarios, but the paper lacks real-world experiments to demonstrate the utility of the proposed algorithm.\n* The proofs of the theorems and lemma often omit details. Please see the questions below.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you so much for your detailed review, and for acknowledging our randomized algorithm! We would like to address your points below:\n\n> **”add examples to show how the algorithm finds a Meek separator.”** \n\nWe thank the reviewer for this suggestion. The added examples and detailed explanations can be found in the general response.\n\n> **”lacks real-world experiments to demonstrate the utility of the proposed algorithm.”**\n\nIn our paper, we used synthetic simulations as a means to demonstrate how our algorithm can be useful in real-world applications. These simulations serve as idealized models for real-world experiments. For example, the task of mean matching can be used as an abstraction of a cell reprogramming experiment, where the shift interventions can be used to model gene over-expression or knockdowns (as discussed in the introduction). \n\nWhile we acknowledge the importance of real-world experiments, one major challenge lies in the nature of the adaptive policy algorithm, where access to real-world sequential data is not readily available. Similar constraints are present in previous papers in this line of work (e.g., [1-4]), where the evaluations are often based on synthetic data. Moreover, the implementation of these algorithms in real-world applications necessitates close collaboration with individuals engaged in experimentation. Going forward, we are actively considering collaborations with experimentalists or the utilization of semi-synthetic data generated from real experiments. However, much work remains to be done to benchmark these real datasets and thus we consider it out of scope for this work. \n\n\n> **”an example that both illustrates the idea of Meek separator and the limitations of the graph separator in Figure 1... why any $\\alpha$-graph separator must contain at least $(1-\\alpha) |V|$ vertices.”** \n\nWe thank the reviewer for this suggestion. In *Figure 1* in the *PDF attached to the general response* (which will replace Figure 1 in the revised manuscript), we added detailed explanations of the Meek separator as well as a separate panel illustrating a graph separator. Figure 1d shows the 1/2-graph separator which contains 2 vertices. Since each pair of vertices is adjacent, removing 1 vertex will leave a connected component of size 4-1=3>2. Therefore any 1/2-graph separator must contain at least 2 vertices.\n\nThis example shows a 4-vertex fully connected DAG and a 1/2-graph separator. It can be extended to fully connected DAGs with $|V|$ vertices and $\\alpha$-graph separators. Since every pair of vertices in the clique is adjacent, removing $<(1-\\alpha)|V|$ vertices will leave a connected component of size $>\\alpha |V|$. Thus any $\\alpha$-graph separator in this case must contain at least $(1-\\alpha)|V|$ vertices. This discussion is provided in lines 162-164.\n\n> **”Add the description of w(G) in the Lemma 2”**\n\nIn Lemma 2, we stated $\\omega(\\mathcal{G})$ as \"vertices in its largest clique”. However, we will make this clearer by separating this description into its own sentence.\n\nThank you for the other suggestions as well:\n\n> **”Lemma 2 should  …  should be** $V(\\mathcal{H})\\subset V(\\mathcal{G})\\subset Des[u]$**.”** \n\nWe will add detailed pointers to Theorem 1,3 in the reference in Lemma 3 and change lines 272, 277, 536, and 575 as suggested.\n\n> **”shouldn’t Figure 1b write $\\mathcal{I}=${{2}}?”** \n\nThank you for pointing this out. $\\mathcal{I}$ is defined to be the set of sets and therefore it should be $\\mathcal{I}$={{2}}. \n\n> **“In line 267, the authors use $V(\\mathcal{H})\\cap V(K)=\\varnothing$, in line 270, the authors use $V(\\mathcal{H})\\cap K=\\varnothing$, what is the difference between $K$ and $V(K)$?”** \n\nWe use $K$ to denote the graph and $V(K)$ to denote its vertices. Therefore, it should be $V(\\mathcal{H})\\cap V(K)=\\varnothing$ in line 270. We tried to change all the vertex sets referred to as $V(\\cdot)$; however, we missed some. In the revised version, we will change the remaining ones.\n\n> **”different Meek separators where one is preferable to the other?”** \n\nFor the current set of applications, the Meek separators are only used to break down a larger graph into smaller, manageable subgraphs. In this context, any Meek separator that can be efficiently computed with minimal interventions provides the same guarantee. Therefore, for our current use cases, we do not find a significant difference between different Meek separators, and they all seem to be equally effective in solving the problems.\n\n> **”performance of the algorithms different for soft interventions and hard interventions in the experiment?”**\n \nNo, the performance of the algorithms is not different for soft interventions and hard interventions in our experiment. The property of the interventions that we utilized is to identify additional edges. For both soft and hard interventions, the identifiability of the interventions remains the same, where we can learn the orientations of any edge cut by $I$ and $V\\setminus I$ (here $I$ denotes the vertices being intervened and $V$ denotes all the vertices in the graph) and possibly additional edges given by the Meek rules (Appendix A). This discussion can be found in lines 125-127.\n\n> **”Regarding Lemma 11, ..., described by Lemma 18?”** \n\nThank you for pointing this out. Lemma 18 establishes that the edge $(c,d)$ is orientable through intervention on any vertex within the set $Des[w] \\cap Anc[d]$ for some fixed $w \\in Anc[c]$. As $w \\in Anc[c]$, we have that $Des[c] \\subseteq Des[w]$, and therefore $Des[c] \\cap Anc[d] \\subseteq Des[w] \\cap Anc[d]$; consequently as $v \\in Des[c] \\cap Anc[d]$, we immediately get that $v$ orients the edge $(c,d)$. We will incorporate these lines into our proof to enhance its readability.\n\n> **”In the proof of Lemma 10...”**\n\nWe apologize for the confusion! Due to character limits, we gave detailed clarifications in the general response. \n\n---\nAll references in this response can be found in the general response."}, {"review_id": "fZJKeezhdx", "reviewer": "Reviewer_Zms6", "summary": "This work explores the problem of learning the local causal structure from intervention data. Specifically, the authors introduce a novel separator called the $\\alpha$-Meek Separator. Unlike traditional $\\alpha$-Separators, their separator imposes bounds on the sizes of connected components in a subgraph. The authors also apply the Meek separator to address two typical tasks: subset search and causal matching. Furthermore, they validate the effectiveness of their methods through experiments conducted on synthetic datasets.", "questions": "See above.", "limitations": "All theoretical results are based on the assumption that all variables are observable, meaning that there are no hidden variables.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles a very challenging problem.\n\nThe meek separator introduced in this paper is novel and interesting.\n\nThe applications of the Meek Separator in subset search and causal matching are both significant.\n\nThe analysis in this paper is presented in a logical manner.", "weaknesses": "Regarding readability: The majority of the article consists of descriptive statements that provide definitions and conclusions but lack simple examples for illustration. In order to help more readers understand and learn, it is recommended to provide some basic examples for key definitions and algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for the encouraging comments! We appreciate that you think our proposal is novel and significant. We’ve added illustrative examples for better readability and we’d like to address your comments here:\n\n> **”Regarding readability: The majority of the article consists of descriptive statements that provide definitions and conclusions but lack simple examples for illustration. In order to help more readers understand and learn, it is recommended to provide some basic examples for key definitions and algorithms.”** \n\nThank you for this suggestion. In the *PDF attached to the general response*, we added a few examples illustrating the key definitions and algorithms. In particular, \n\n- *Figure 1* now includes detailed explanations of our defined Meek separator and a separate panel illustrating the traditional graph separator. We will replace Figure 1 in the revised manuscript with this.\n- We added *Figure 2* to show how Algorithm 1 finds the Meek separator in a 4-vertex DAG example. In this example, we walk through the iterations of Algorithm 1 while specifying the realizations of the selected $u_i$ in line 4 of Algorithm 1. We will add this example to section 4 of the revised manuscript.\n- *Figure 3*  and *Figure 4* illustrate key graphical concepts that were used, including moral graphs, essential graphs, and connected components. We will add these examples to Appendix B and refer to these figures when they are introduced in Section 2.\n\n> **”All theoretical results are based on the assumption that all variables are observable, meaning that there are no hidden variables.”** \n\nWe appreciate this comment regarding our assumptions of no hidden variables. We agree that it would be very interesting to explore settings with latent confounders. We consider this as an important aspect to extend this line of work that often assumes causal sufficiency, and we hope to address this further in future works."}, {"review_id": "P06qPeJE3T", "reviewer": "Reviewer_2LUY", "summary": "This paper studies the problem of learning causal structure by learning a minimal intervention set, which is formalized as the Meek separator. The authors show that the Meek separator can orient the maximum number of edges with the minimum intervention set while limiting the size of the remaining undirected connected components to $\\alpha |V|$. Furthermore, the authors provide a logarithmic-time algorithm to determine the variables of the Meek separator based on a binary search on the essential graph.  Also, the authors show that the problems of subset search and causal matching can be well addressed by the Meek separator.\n", "questions": "\nCan your method be directly applied to learn the entire causal graph？Will there be any new challenges?\n", "limitations": "Refer to Weaknesses", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a Meek separator and algorithm that only require logarithmic time complexity, which addresses an important problem of causal discovery.\n\n\n2. The proposed Meek separator can be flexibly applied to subset search and causal matching. The experimental results verify the effectiveness of the proposed algorithms.\n\n3. The proposed theorem looks sound.", "weaknesses": "1. Section 2 is poor readability due to many notions and symbols.  I suggest the definition part and related work can be divided into two subsections.\n\n2. I think some examples should be provided for illustrating significant graphical concepts, such as moral graph and essential graph.\n\n\n3. The result of Lemma 10 is interesting but is not easy to understand. Can you provide an intuitive explanation for it?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating the problem we studied, and for your recognition of our result! We’ve added illustrative examples as per your suggestion and we’d like to address your concerns below:\n\n> **”Section 2 is poor readability due to many notions and symbols. I suggest the definition part and related work can be divided into two subsections.”** \n\nThank you for this feedback. When we originally wrote the definitions in Section 2, it seemed to be a natural place to refer to related work, as these concepts were first defined in those works. However, to improve readability, we will divide this section into subsections describing:\n\n- basic graphical concepts (paragraph 1, lines 81-97),\n- graphical concepts relating to DAGs and causal models (paragraph 2, lines 98-116), and\n- concepts involving interventions (paragraphs 3-6, lines 117-152).\n\nIn addition, we will also add a few illustrative examples describing some key definitions in Appendix B (see our response to the other comment regarding examples below).\n\n> **”I think some examples should be provided for illustrating significant graphical concepts, such as moral graph and essential graph.”** \n\nThank you for this suggestion! In the *PDF attached to the general response*, we added a few examples illustrating the key graphical concepts. In particular, \n\n- *Figure 3* illustrates a moral graph versus a graph that is not moral. We will add this example to Appendix B and refer to it when moral DAGs are introduced in Section 2.\n- *Figure 4* illustrates the essential graph, $\\mathcal{I}$-essential graph, and connected components. We will add this example to Appendix B and refer to it when they are defined in Section 2.\n- In addition, *Figure 1* now includes a separate panel illustrating the traditional graph separator and detailed explanations of our defined Meek separator. We will replace Figure 1 in the revised manuscript with this.\n\n> **”The result of Lemma 10 is interesting but is not easy to understand. Can you provide an intuitive explanation for it?”** \n\nThank you for this suggestion! Intuitively, we can explain the result of Lemma 10 below.\n\nLemma 10 establishes the existence of a subset of at most two vertices that form a Meek separator. It also shows that this subset will satisfy several nice properties. These properties empower us (as depicted in Algorithm 1) to discover such subsets using a binary search method within the vertices of the provided 1/2-clique separator.\n\nTo elaborate, the statement of Lemma 10 is three-fold. Firstly, it states that there is a vertex u that is almost central to the graph (i.e., fulfills the **constraint** “$|A_u| ≤ |V(\\mathcal{G})|/2$ and $|A_v | > |V (\\mathcal{G})|/2$ for all $v ∈ Des(u) \\cap K$”). Then, it states that any vertex that fulfills this constraint will satisfy one of the two **conditions** (i.e., “ 1). either $u$ is a sink vertex …  2)…..”). Thirdly, it states that the $u$ (and potentially $x$) stated in the conditions corresponds to Meek separators. Consequently, by finding a vertex that fulfills the constraint, we find the Meek separators by the conditions it satisfies.\n\nSee also the general response for an intuitive explanation of its proof.\n\n\n> **”Can your method be directly applied to learn the entire causal graph? Will there be any new challenges?”** \n\nYes. Our algorithm for subset search can be directly applied to learn the entire causal graph, by specifying the target edges to be the set of all edges. In this case, we get a $\\mathcal{O}(\\log n)$ approximation for recovering the entire DAG, which matches the current best approximation ratio in [4]. This discussion can be found in lines 208-209.\n\n---\nThe references in this response can be found in the general response."}, {"review_id": "TlvwuKzXfF", "reviewer": "Reviewer_wSxh", "summary": "The paper focuses on applications of causal discovery, in which it is not necessary to learn the full graph. Instead, the authors propose to recover what they call the Meek separator---which consists of a set of vertices that decomposes the unoriented edges into smaller connected components when intervened on. Further, they propose two randomized algorithms (for subset search and causal mean matching) for which they prove logarithmic approximation guarantees. ", "questions": "- It would be great if the authors could provide more intuition as to why the Meek separator is a good set of vertices to learn. For example, if we are interested in the neighborhood of a node, we could also learn the Markov blanket---which advantages does the Meek separator bring with it?\n- In Figure 1, why can we ignore all directed edges? The intervention on 2 should only delete the edge $1 \\to 2$.\n", "limitations": "- No real-world examples have been provided.\n- To me, it is unclear what exactly the benefits of the proposed Meek separator are, and how it relates to, e.g., Markov blankets.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors provide strong theoretical guarantees (logarithmic approximation expectation) for both of their proposed randomized algorithms.\n- On synthetic data, the proposed algorithms perform well compared to the baselines.\n- The code for the experiments is provided.\n", "weaknesses": "- The paper is very dense and hard to follow. Especially, I would appreciate it if more effort was put into motivating the main concepts---i.e., why do we want to learn the Meek separator, and why is the definition reasonable? Figure 1 is supposed to provide an example, but very little intuition is provided to guide the reader through the proposed concepts.\n- Although the problem is motivated by learning partial information from gene expression networks and referring to [FMT+21], no real-world example was studied.\n\nMinor feedback:\n- In the introduction, it is stated that only the Markov equivalence class can be learned from observational data. This is only partially true. The Markov equivalence class can be learned assuming, e.g., faithfulness and the causal Markov property, but with different assumptions, e.g., assumptions w.r.t. the SCM (linear non-Gaussian additive noise), the DAG is identifiable.\n- Line 84: The $\\sim$ relation is used to indicate if two vertices are “connected”. I think the notion of “adjacent” is more common since connected could also mean that the path between the vertices has length $> 1$.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that the reviewer found our theoretical results to be strong. We would like to address some of the reviewer’s comments below:\n\n> **”motivating the main concepts---i.e., why do we want to learn the Meek separator, and why is the definition reasonable? Figure 1... guide the reader through the proposed concepts.”** \n\nWe are motivated to study the Meek separator due to its ability to break down *the remaining unoriented edges* of the DAG into more manageable connected components upon interventions. As emphasized in both the abstract and introduction, the Meek separator discovery algorithm holds promise for enabling divide-and-conquer strategies in solving diverse targeted causal discovery challenges. Specifically, our research showcases its application in crafting approximation algorithms for problems like subset search and mean matching. \n\nFurthermore, this definition is in contrast with the traditional *graph separator*, which decomposes the *full graph* (instead of *the remaining unoriented edges*) into smaller connected components (Definition 1). Note that the graph separator does not make use of the information of interventions. Since we are able to learn some edge orientations after interventions, the set of *unoriented edges* can be much smaller than the set of edges in the *full graph*. Therefore the size of a Meek separator can be much smaller than the size of a graph separator. Figure 1 aims to illustrate this. \n\nIn the *PDF attached to the general response,* we provided an updated version of Figure 1 (which will be used in the revised manuscript). In particular, we added detailed explanations of the Meek separator and a separate panel illustrating the graph separator. Figure 1d shows the 1/2-graph separator which contains 2 vertices. Since each pair of vertices is adjacent, removing 1 vertex will leave a connected component of size 4-1=3>2. Therefore any 1/2-graph separator must contain at least 2 vertices. However, Figure 1b shows that there exists a Meek separator that contains only 1 vertex.\n\n\n> **”no real-world example was studied.”** \n\nWe thank the reviewer for this comment. In our experiments, we used synthetic simulations as a means to demonstrate how our algorithm can be useful in real-world applications. These simulations are idealized models for real-world experiments. For example, the task of mean matching can be used as an abstraction of a cell reprogramming experiment, where the shift interventions can be used to model gene over-expression or knockdowns (as discussed in the introduction). \n\nWhile we acknowledge the importance of real-world experiments, one major challenge lies in the nature of the adaptive policy algorithm, where access to real-world sequential data is not readily available. Similar constraints are present in previous papers in this line of work (e.g., [1-4]), where the evaluations are often based on synthetic data. Moreover, the implementation of these algorithms in real-world applications necessitates close collaboration with individuals engaged in experimentation. Going forward, we are actively considering collaborations with experimentalists or the utilization of semi-synthetic data generated from real experiments. However, much work remains to be done to benchmark these real datasets and thus we consider it out of scope for this work. \n\n> **”In the introduction, it is stated that only the Markov equivalence class can be learned from observational data. This is only partially true. The Markov equivalence class can be learned assuming, e.g., faithfulness and the causal Markov property, but with different assumptions... ”** \n\nWe thank the reviewer for pointing this out. In the introduction, we stated that a DAG is *generally* only identifiable up to its MEC with observational data. But we will make this clearer by adding a statement that this result holds in nonparametric SCMs while additional identifiability can be achieved by considering parametric SCMs (e.g., linear SCMs with non-Gaussian additive noises).\n\n> **”Line 84: The ∼ relation is used to indicate if two vertices are “connected”. I think the notion of “adjacent” is more common since connected could also mean that the path between the vertices has length >1.”** \n\nThank you for this comment. We will revise “connected” to “adjacent” accordingly.\n\n> **”provide more intuition as to why the Meek separator is a good set of vertices to learn... if we are interested in the neighborhood of a node, we could also learn the Markov blanket---which advantages does the Meek separator bring with it?”** \n\nSee above for the intuition of why we want to learn the Meek separator and its benefits. Regarding Markov blankets, we do not see a way to make direct comparisons. First, Markov blankets can be learned from the observational data, while our work aims to learn a pre-specified subset of edges from interventional data using the least number of interventions. Second, an identified Markov blanket does not distinguish causes from effects (i.e., edge orientations) [5], while we aim to learn edge orientations in subset search. More importantly, our goal lies not only in learning the neighborhood of a node, but learning an arbitrary set of edges for the subset search problem or a matching intervention for the mean matching problem.\n\n> **”In Figure 1, why can we ignore all directed edges? The intervention on 2 should only delete the edge 1$\\rightarrow$ 2.”** \n\nIntervening on a vertex allows us to identify all edges adjacent to it and possibly additional edges given by the Meek rules (Appendix A). See lines 125-127 for details. Therefore in Figure 1b, when we intervene on vertex 2, it allows us to identify the edges $1\\rightarrow 2, 2\\rightarrow 3, 2\\rightarrow 4$ and $1\\rightarrow 3, 1\\rightarrow 4$ by Meek rules. Then in Figure 1c, we show the connected components of the graph after removing all the oriented edges.\n\n---\nAll references in this response can be found in the general response."}]

Author rebuttal:
We thank all the reviewers for their insightful comments and suggestions. 

---
In this general response, we attached a pdf of the additional figures that we will add to the manuscript. To summarize, this includes:

- A modified *Figure 1,* which now includes detailed explanations of our defined Meek separator and a separate panel illustrating the traditional graph separator. We will replace Figure 1 in the revised manuscript with this.
- *Figure 2,* which shows how Algorithm 1 finds the Meek separator in a 4-vertex DAG example. In this example, we walk through the iterations of Algorithm 1 while specifying realizations of which $u_i$ is picked in line 4 of Algorithm 1. We will add this example to section 4 of the revised manuscript.
- *Figure 3*, which illustrates a moral graph versus a graph that is not moral. We will add this example to Appendix B and reference to it when moral DAGs are introduced in section 2.
- *Figure 4*, which illustrates the essential graph, $\mathcal{I}$-essential graph, and connected components. We will add this example to Appendix B and reference to it when they are defined in section 2.

---

In addition, we’d like to provide further information regarding two common points raised by the reviewesr:

> **How the algorithm finds a Meek separator.** 

In the *attached PDF*, we added a 4-vertex DAG example showing how Algorithm 1 finds the Meek separator in *Figure 2*. Further details can be found above and in the figure caption. 

Intuitively, Algorithm 1 finds the Meek separator by doing *binary search* among the vertices of the inputted $1/2$-clique separator $K$. Lemma 10 establishes the existence of a subset of at most two vertices that form a Meek separator. It also shows that this subset must satisfy several nice properties. These properties empower us (as depicted in Algorithm 1) to identify such subsets using a binary search method within the vertices of the inputted 1/2-clique separator $K$. 

To elaborate, since $K$ is a clique, its vertices have a natural order specified by the topological order of $K$. In each iteration, a vertex $u_i$ of $K$ is intervened, where the remaining vertices of $K$ are separated into $u_i$’s parents and children (i.e., before or after $u_i$ in the topological order). Then the algorithm moves on to search in the interval of the topological order ($K_i$ in Algorithm 1) that can potentially contain the Meek separator. This binary search procedure outputs a subset of vertices that satisfy the conditions of Lemma 10, which is guaranteed to form a Meek separator. 

>**Statement, proof, and usefulness of Lemma 10.** 

The statement of Lemma 10 is three-fold. Firstly, it states that there is a vertex u that fulfills the **constraint** “$|A_u| ≤ |V(\mathcal{G})|/2$ and $|A_v | > |V (\mathcal{G})|/2$ for all $v \in Des(u) \cap K$”. Secondly, it states that *any* vertex that fulfills this **constraint** will satisfy one of the two **conditions** “ 1). either $u$ is a sink vertex … 2) …”. Thirdly, it states that the $u$ (and potentially $x$) stated above corresponds to Meek separators.

Based on this statement, the proof proceeds in the following logic:

- Paragraph 1 (line 570-573) is showing that there exists a vertex $u$ that fulfills the **constraint**. Therefore the conditions asked by the Reviewer BZ2Z refer to “$|A_u| ≤ |V(\mathcal{G})|/2$ and $|A_v | > |V (\mathcal{G})|/2$ for all $v\in Des(u) \cap K$”. We will clarify this in the revised version by adding this description to line 573.
- Upon showing that the **constraint** can be fulfilled. We then try to show *any* vertex that fulfills this **constraint** will satisfy one of the two **conditions** “ 1). either $u$ is a sink vertex … 2) …”. Therefore paragraph 2 (line 574-575) starts by discussing if the $u$ that fulfills the constraint satisfies the first of the two conditions (i.e. if it is the sink node). Then paragraph 3 and onwards show that if $u$ does not satisfy condition 1, it will satisfy condition 2. We will clarify this in the revised version by adding these descriptions to line 574 and line 579.

The usefulness of this lemma lies in finding a vertex that satisfies the **constraint** (by using binary search, see response above regarding Algorithm 1). Subsequently, the **conditions** that such vertex satisfy lead to Meek separators. The division of two different conditions is for handling technicalities.


---
We provide the full list of references here:


[1] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath. Learning Causal Graphs with Small Interventions. Advances in Neural Information Processing Systems, 28, 2015.

[2] Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Boix-Adserà, and Guy Bresler. Sample Efficient Active Learning of Causal Trees. *Advances in Neural Information Processing Systems*, 32, 2019.

[3] Jiaqi Zhang, Chandler Squires, and Caroline Uhler. Matching a desired causal state via shift interventions. *Advances in Neural Information Processing Systems*, 34:19923– 19934, 2021.

[4] Davin Choo and Kirankumar Shiragur. Subset verification and search algorithms for causal dags. *arXiv preprint arXiv:2301.03180*, 2023

[5] Yu, Kui, Lin Liu, and Jiuyong Li. "Discovering Markov blanket from multiple interventional datasets." *arXiv preprint arXiv:1801.08295* (2018). 


Meta-review: The authors propose Meek separators, basically intervention targets that reduce the remaining graph size, taking into account the Meek rules. Different from the most existing work, the authors' strategy is to identify this critical set of intervention targets with interventions. Compared to prior work, it does not provide an improvement on full graph discovery problem. But it nicely interpolates the existing solution by Choo 2022, to aiming to learn any specific subset of edges. It also has another application in the so-called causal (mean) matching problem that was proposed by Zhang 21.

The reviewers, although not very confident, unanimously recommended acceptance. Based on my own reading of the paper I believe there is sufficient merit and discoveries in the paper to warrant acceptance. One minor point is that the paper might be a bit hard to read for non-experts on this particular field, as noted by many reviewers. So it would be of great help if the authors can add the example in their rebuttal. I would actually instead recommend adding an example where skeleton is not complete, to better showcase the idea of Meek separator.

Thank you for the great work!
Decision: Accept (poster)