Verification and search algorithms for causal DAGs
Authors: Davin Choo
Kirankumar Shiragur
Arnab Bhattacharyya
Venue: NeurIPS 2022 Accept (2022)
Keywords: Causality
Causal Inference
Active Structure Learning
Interventions

Abstract: We study two problems related to recovering causal graphs from interventional data: (i) $\textit{verification}$, where the task is to check if a purported causal graph is correct, and (ii) $\textit{search}$, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized set of atomic interventions that is necessary and sufficient to check the correctness of a claimed causal graph. Our characterization uses the notion of $\textit{covered edges}$, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize our results to the settings of bounded size interventions and node-dependent interventional costs. For all the above settings, we provide the first known provable algorithms for efficiently computing (near)-optimal verifying sets on general graphs. For the second problem, we give a simple adaptive algorithm based on graph separators that produces an atomic intervention set which fully orients any essential graph while using $\mathcal{O}(\log n)$ times the optimal number of interventions needed to $\textit{verify}$ (verifying size) the underlying DAG on $n$ vertices. This approximation is tight as $\textit{any}$ search algorithm on an essential line graph has worst case approximation ratio of $\Omega(\log n)$ with respect to the verifying size. With bounded size interventions, each of size $\leq k$, our algorithm gives an $\mathcal{O}(\log n \cdot \log k)$ factor approximation. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs and with bounded size interventions.

Verification and search algorithms for causal DAGs
Davin Choo
Kirankumar Shiragur"
National University of Singapore davinOu. .duu
Stanford University
shiragur@@taaford..cl
Arnab Bhattacharyya
National University of Singapore
arnabbênus.
Abstract
We study two problems related recovering causal graphs from interventional data: (i) verification, where the task is check if purported causal graph is correct, and (ii) search, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give characterization of a minimal sized set atomic interventions that necessary and sufficient to check the correctness of claimed causal graph. Our characterization uses the notion of covered edges, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize results to the settings of bounded size interventions and node-dependent interventional costs. For all the above settings, provide the first known provable algorithms for efficiently computing (optrml verifying sets on general graphs. For the second problem, we give simple adaptive algorithm based on graph separators that produces an atomic intervention set which fully orients any essential graph while using O (log n) times the optimal number of interventions needed verify (verifying size) the underlying DAG
vertices. This approximation is tight as any search algorithm on an essential line graph has worst case approximation ratio of 22llg n) with respect to the verifying size. With bounded size interventions, each of size S k, our algorithm gives an Ollgg n log k) factor approximation. Our result the first known algorithm that gives non-trivial approximation guarantee to the verifying size on general unweighted graphs and with bounded size interventions.
Introduction
Causal inference has long been an important concept in various fields such as philosophy [Rei56, Woo05, ES07], medicine//iologgy/eeneess [KWJ+04 04, SC17, RHT+ POS metrics [Hoo90, RW06]. Recently, there has also been growing interest in the machine learning community to use causal inference techniques to improve generalizability to novel testing environ- ments (e.g. see [GUA+ 16, LKC17, ABGLP19, Sch22] and references therein). Under the assumption of causal sufficiency, where there is no unobserved confounders or selection bias, causal inference using observational data has been extensively studied and many algorithms such as PC [SGSH00] and GES [Chi02] have been proposed. These algorithms typically recover causal graph up to its Markov equivalence class and is known to be fundamentally impossible to learn causal relation- ships solely based on observational data. To overcome this issue, one either adds data modeling assumptions (e.g. see [SHHK06, PB14, MPJ 16]) or performs interventions to obtain interventional
SDS+18), 18), and econo-
Equual contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

data (see Section 2.1 for a literature review). In our work, we study the causal discovery problem via interventions. As interventions often correspond to real-worls experimental trials. they can be costly and it is of practical importance to minimize the number or cost of interventions.
In this work, we consider ideal interventions (i.e. hard interventions with infinite samples²) to recover causal graphs from its Markov equivalence class - the Markov equivalence class (MEC) of G, denoted by [G], is the set of graphs that encode the same conditional distributions and it is known that any MEC [G] can be represented by unique partially oriented essential graph ( While ideal interventions may not always be possible in practice, they serve as first step to understand the verification and search problems. Such interventions give us clean graph-theoretir way to reason and identify are directions in the causal graph G = E). With these interventions, it is known that intervening on a set S S V allows us to infer the edge orientation of any edge cut by S and V \ S (Ebe07, HEH13, HLV14, SKDV15, KDV17J.
Using the ideal interventions, we solve the verification and search problems. The search problem is the traditional question of finding minimum set of interventions to recover the underlying ground truth causal graph. As for the verification problem, consider the following scenario: Suppose we have performed observational study obtain MEC and consulted an expert about the identity of the ground truth causal graph. The question of verification involves testing if the expert is correct using the minimal number of interventional studies.
Definition 1 (Search problem). Given the essential graph E(G*) of an unknown causal graph G*, use the minimal number of interventions to fully recover the ground truth causal graph G*.
Definition 2 (Verification problem). Given the essential graph E (G') of an unknown causal graph G and an expert's s graph G E [G*], use the minimal number of interventions to verify G _ G*.
To solve both these problems, we compute verifying sets (see Definition 4). A verifying set is collection of interventions that fully orients the essential graph. Note that the minimum size/cost verifying set serves as natural lower bound for both the search and verification problems. One of our key contributions is to efficiently compute these verifying sets for given causal graph.
Contributions We study the problems of verification and search for a causal graph from its MEC using ideal interventions. In our work, we make standard assumptions such as the Markov assumption, the faithfulness assumption, and causal sufficiency [SGSH00].
Verification: We provide the first known efficient algorithms for computing minimal sized atomic verifying sets and near-optimal bounded size verifying sets (that use at most one more intervention than optimal) on general graphs. When vertices have additive interventional costs according to weight function : - R. we give efficient computation of verifying sets I that minimizes a w(I) + 3 [Z]. Our atomic verifying sets have optimal cost and bounded size verifying sets incur total additive cost of at most 2,3 more than optimal. To achieve these results, we prove properties about covered edges and give a characterization of verifying sets as a separation of unoriented covered edges in the given essential graph. Using our covered edge perspective, we show that the universal lower bounds of [SMG* 20, PSS22] are not tight and give a simple proof recovering the verification upper bound of [PSS22].
2. daptive search: We consider adaptive search algorithms which produce a sequence of interventions one-at-a-time, possibly using information gained from the outcomes of earlier chosen interventions. Building upon the lower bound of [SMG*) BMMG+20,, we establish stronger (but not computable) lower bound to verify a causal graph. This further implies a lower bound on the minimum interventions needed by any adaptive search algorithm. We also provide an adaptive search algorithm (based on graph separators for chordal graphs) and use our lower bound to prove that our approach uses at most logarithmic multiplicative factor more interventions than a minimum sized verifying set of the true underlying causal graph.
Outline Section 2 introduces notation and preliminary notions, as well as discuss some known results on ideal interventions. We give our results in Section and provide an overview of the techniques used in Section 4. We discuss our experimental results in Section 5. Full proofs, side discussions, and source code/scripts are given in the appendix.
We do not consider sample complexity issues in this work.

---

2 Preliminaries and related work
For any set A, we denote its powerset by 24, We write (I...., ..,.....7..................... n) as [n] and hide absolute constant multiplicative factors in using asympiotic notations (+). ( and (-)). Throughout, we use G*
to denote the (unknown) ground truth DAG and we only know its essential graph E(G*).
Graph notions
We study partially directed graphs G (V,E,A) on V== = and oriented arcs A. Any possible edge between two distinct vertices u, U E V is either undirected, oriented in one direction, or absent in the graph. We write u if these vertices are connected (either through an unoriented edge or an arc) in the graph and u of e to indicate the absence of any edge/are connection. If (u, v) E A or (v, u) E A, we write -> or u < v respectively. When E = 0, we say that the graph is fully oriented. For any graph G, we use V(G), E(G), A(G) to denote its vertices, unoriented edges and oriented ares.
vertices with unoriented edges E
For any subset of vertices V' V. GIV"] denotes the vertex-induced subgraph on V" Similarly, we define G' and G[E'] as are-induced and edge-induced subgraphs of G for A' C A and E' C E respectively. For an undirected graph G, (G)) refers to the size of its maximum clique and x(G) refers to its chromatic number. For any vertex parent set of o and pa(e) denotes the vector of values taken by v's parents.
V in a directed graph, Pa(v) S V denotes the
The skeleton of graph G refers the graph G' (V, F. A, () where all ares made unoriented.
v-structure refers to three distinct vertices u, v, w E V such that u - v t- w and u o w. A simple eycle is a sequence of k 2 3 vertices where U1 ~ 12 ... 2k 01. The cycle is directed if at least one of the edges is directed and all directed ares are in the same direction along the cycle. A partially directed graph is a chain graph if it contains no directed cycle. In the undirected graph G' obtained by removing all arcs from a chain graph G. each connected component in G' is called a chain component. We use (C) to denote the set of chain components in G. Note that the vertices of these chain components form partition of V.
Directed acyclic graphs (DAGs), special case of chain graphs where all edges are directed,
commonly used as graphical causal models [Pea09] where vertices represents random variables and the joint probability density f factorizes according the Markov property: f(U1,-.-. Mn)) IT. f(ua pa(e)). We can associate a valid permutation / topological ordering π. V - [n] to any (partially oriented) DAG such that oriented arcs (u, v) satisfy x(u) T(v) and any unoriented are {u, u can be oriented as u + U whenever (u)) < T(r) without forming directed cycles. While there may be multiple valid permutations, we often only care that there exists least one such permutation. For any DAG G, we denote its Markov equivalence class (MEC) by [G] and exsential graph by {G)). It is known that two graphs are Markov equivalent if and only if they have the same skeleton and v-structures [VP90, AMP97J.
A clique is graph where u for any pair of vertices u, u E V. A maximal clique is vertex- induced subgraph of a graph that is a clique and ceases to be one if we add any other vertex to the subgraph. If all edges in the clique are oriented in an acyclic manner, then there is unique valid permutation ı that respects this orientation. We denote v argmax uey (u) as the sink of the clique.
Interventions, verifying sets, and additive vertex intervention costs
An intervention C V is an experiment where the experimenter forcefully sets each variable & E S to some value, independent of the underlying causal structure. An intervention is called an atomic intervention if [S] = and called a bounded size intervention if | < k for some size upper bound k. One can view observational data as a special case where S = 0. Interventions affect the joint distribution of the variables and are formally captured by Pearl's do-calulus [Pea09]. An intervention set I C 2 is collection of interventions and UserS is the union of all intervened vertices.
In this work, we study ideal interventions. Graphically speaking, an ideal intervention S on G induces an interventional graph Gs where all incoming ares to vertices v E S are removed [EGS 12] and it known that intervening on a set S C V allows us to infer the edge orientation of any edge cut by S and V S [Ebe07, HEH13, HLV14, SKDV15, KDV17J. For ideal interventions, an I-essential graph (G) of G is the essential graph representing the Markov equivalence class of graphs whose interventional graphs for each intervention is Markov equivalent to Gs for any intervention S e I.
3

---

There are several known properties about Z-essential graph properties [HB12, HB14, SMG 20]: Every I-essential graph is chain graph with chordal' chain components. This includes the case of S 0. Orientations in one chain component do not affect orientations in other components. In other words, to fully orient any essential graph E(G"), is necessary and sufficient to orient every chain component in {(") independently. More formally, we have
Lemma 3 (Modified lemma 1 of [HB14]). Let I S 2 be an intervention set. Consider the I- essential graph Ez(G") ) of some DAG G and let H CC(Er(G")) be one of its chain components. Then, for any additional interventional set I' 2 such that I n @. we have
EzUT (zur (G)) E(SnV(H) SEZ'Y (G*
As consequence of Lemma 3, one may assumee without loss of generality that CC()(G)) is single connected component and then generalize results by summing across all connected components.
A verifying set I for DAG G E [G"] is an intervention set that fully orients G from (('),, possibly with repeated applications of Meek rules (see Appendix A). other words, for any graph = (V, F) and any verifying set I of G, we have (V)) = G[V"] for any subset of vertices V C V. Furthermore, if Z is verifying set for G. then I U also a verifying set for for any additional intervention S S V. While DAGs may have multiple verifying sets in general, we are often interested in finding one with minimum size or cost.
Definition (Minimum size/cost verifying set). Let w be weight function intervention sets. An intervention set I is called a verifying set for a DAG G" if ( = G" I is a minimum size (resp. cost) verifying set if Ez (G") + G for any [I| < [Z] (resp. for any w (T') (I))
When restricting to interventions of size at most k, the minimum verification number (G( of G denotes the size of the minimum size verifying set for any DAG G E [G*]. That is, any revealed are directions when performing interventions on {G') respects G. in (G) denotes the case where restrict to atomic interventions. One of the goals of this work is to characterize v(G) given essential graph (G*) and some G E [G*].
Covered edges
Covered edges are special ares in causal graph where the endpoints of u v share the same set of parents in \ {u, J). These edges are crucial causal discovery because their orientation can be reversed and they still yield the same conditional independencies. See Fig. 1 for illustration. Note that one can compute all covered edges of a given DAG G in polynomial time.
((G))
G2
h
b
Figure 1: A DAG G* with its essential graph E(G*) on the left. G1 and G2 are two other DAGs that belong to the same Markov equivalence class [G*). Dashed ares are covered edges in each DAG. One can perform sequence of covered edge reversals transform between the DAGs (see Lemma 7). Note that the sizes of the minimum vertex cover the covered edges may differ across DAGs.
Definition (Covered edge). An edge u is covered edge if Pa(u) {o) Pa(u) \ {u). Definition 6 (Covered edge reversal). A covered edge reversal means that we replace u u with W + u, for some covered edge + v, while keeping all other ares unchanged.
'A chordal graph is a graph where every cycle of length at least 4 has a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. See [BP93] for more properties.
'Lemma of [HB14] actually considers a single additional intervention, but closer look at their proof shows that the statement can be strengthened to allow for mudtiple additional interventions. For completeness, we provide the proof of this strengthened version in Appendix B. Note that we can drop the 0 intervention in the statement since essential graphs are defined with the observational data provided.

---

Lemma 7 ([Chi95], If G and G' belong in the same MEC if and only if there exists sequence of covered edge reversals to transform between them.
Definition 8 (Separation of covered edges). We say that an intervention S C V separates a covered edge u if Ku, b) n 1. That is, exactly one of the endpoints is intervened by S. We say that an intervention set I separates a covered edge u ~ u if there exists 5 E I that separates u ~ V.
Relationship between searching and verification
Recall Definition 1 and Definition 2. The verification number is a useful analytical tool for the search problem vx (x") is lower bound on the number of interventions used by optimal search algorithm. Furthermore, since the search problem needs to fully orient {(G)) regardless of which DAG is the ground truth, any search algorithm given {(G*) requires at least minGe[G"1 vx(G) interventions, even if it is adaptive and randomized. In fact, the strongest possible universal lower bound guarantee one can prove must be al most mingelG-1 us (G) and the strongest possible universal upper bound guarantee one can prove must be at least maxGe(G*) (G) Note that if the search algorithm is non-adaptive, then it trivially needs at least maxGe]G"1 (C) interventions.
Example Consider the graph G* in Fig. where the essential graph E(G") representing the MEC [G*) is the standing windmill Now, consider only atomic interventions. We will later show that the minimum verification number of a DAG is the size of the minimum vertex cover of its covered edges (see Theorem 11). One check that Vn (G*) (G1) 4 while (G2) 3. In fact, we actually show that minGe[G-1 #1 (G) = 3 and maxGe[G"| P (G) = 4 in Appendix C. Thus, any search algorithm using only atomic interventions on E(G") needs at least 3 atomic interventions.
2.1 Related work
Table I and Table in Appendix D summarize" the existing upper (sufficient) and lower (worst case necessary) bounds on the size ([Z), or F[[Z]] for randomized algorithms) of intervention sets that fully orient a given essential graph. These lower bounds are "worst case" in the sense that there exists a graph, typically clique, which requires the stated number of interventions. Observe that there are settings where adaptivity" and randomization strictly improves the number of required interventions.
Separating systems [HEHI3] drew connections between causal discovery via interventions and the concept of separating systems from the combinatorics literature. This was extended by [SKDV15] 15] to the bounded size and adaptive settings. An (n. -essparrt system is Boolean matrix with n columns where each row has at most ones, indicating which vertex is be intervened upon. Using their proposed separating system construction based on "label indexing", [SKDV15] showed that roughly n interventions. On cliques (i.e. worst case lower bound), [SKDV15] showed that the bound tight while only roughly xlε(G)) log x (G)) interventions are necessary for general graphs S, even if the interventions are chosen adaptively or in a randomized fashion.
E logg n interventions is sufficient to fully an essential graph G with bounded size
Universal bounds for minimum sized atomic interventions Beyond worst case lower bounds, recent works have studied universal bounds for orienting essential graphs E(G') using atomic interventions [SMG+20, PSS22J. These universal bounds depend on graph parameters of E(G) beyond the number of nodes n. [SMG+20] showed that search algorithms must use at least ΣHEOC(EGG-)) w(H) interventions, where // is chain component of E(G' and the summation across chain components is a consequence of Lemma 3. They also introduced a graph concept called directed clique trees and designed an adaptive, deterministic algorithm. On intersection iawrriioonnncmmaaabllbb.. chordal graphs, their algorithm outputs an intervention set of size (log, ( ECC(E(G")) w (H) '1 (G")). More recently, [PSS22] introduced the notion of clique- block shared- sarredtsarents orderings and showed that
"To be precise, is the Wd(3.3) windmill graph with an additional edge from the center.
'Some known results are discussed in further detail below instead of being summarized in the table format. 'Given an essential graph E(G non-adaptive algorithms decide sei of interventions without looking at the outcomes of the interventions. Mcanwhile, adaptive algorithms can provide sequence of interventions one-at-a- mme-at-a-tmme, possibly using any information gained from the outcomes of carlier chosen interventions.
Note that there is a slight gap between ((E
log x( x()( and & log n on general graphs.
5

---

any search algorithm for an essential graph {G') with maximal cliques requires at least ["2"] interventions and Vn (G) S n for any G [G*)
Non-atomic interventions The randomized algorithm of [HLV14] fully orients an essential graph using (log())))())) unbounded interventions in expectation. Building upon this, [SKDV15] shows that O g (og(log(k))) bounded sized interventions (each involving at most &o nodes) suffice.
Additive vertex costs [KDV17, GSKB18, 8, LKDV18] studied the non non-adaptive search setting where vertices may have different intervention costs and intervention costs accumulate additively. [GSKB 18] studied the problem of maximizing number of oriented edges given budget of atomic interventions while [KDV17, LKDV18) 18] studied the problem of finding a minimum cost (bounded size) intervention set that fully orients the essential graph. [LKDV 18] showed that computing the minimum cost intervention set is NP-hard and gave search algorithms with constant approximation factors.
Other related work [HLV14, KSSU19] showed that Rényi graphs can be easily oriented.
3 Results
3.1
Verification
Our core contribution for the verification problem deriving an interesting connection between the covered edges and verifying sets. We show importance of this connection by using it to derive several novel results on finding optimal verifying sets in various settings such as bounded size interventions and when vertices have varying interventional costs. For detailed proofs, see Appendix E.
Theorem 9. Fix an essential graph E(G") and G E [G*]. An intervention set I is verifying set for G if and only if II is set that separates every covered edge of that unoriented in E(G)).
Together with Lemma 7 (any undirected edge in E(G) is covered edge for some G [G*]), Theorem 9 implies a simple alternative proof for an earlier known result that characterizes non- adaptive search algorithms via separating systems [HEH13, SKDV15]: any non-ade adaptive search algorithm, which has no knowledge of G*, should separate every undirected edge in {(G)).
Another immediate application of Theorem 9 is the following result for the verification problem.
Corollary 10. Given an essential graph ((") of an unknown ground truth DAG G and a causal DAG G e [G*), we can test G _ G by intervening on any verifying set of G. Furthermore, in the worst case, any algorithm that correctly resolves G _ G needs at least v(G) interventions.
The above corollary provides solution to the verification problem in terms of verifying sets and in the following we give efficient algorithms for computing these verifying sets that are optimal in the atomic setting and are near-optimal in the case of bounded size.
Theorem 11. Fix an essential graph ((')) and G [G*). An atomic intervention set I is minimal sized verifying set for G if and only if is a minimum vertex cover of unoriented covered edges of G. A minimal sized atomic verifying set can be computed in polynomial time.
Our result provides the first efficient algorithm for computing minimum sized atomic verifying set for general graphs. Previously, efficient algorithms for computing minimum sized atomic verifying sets were only known for simple graphs such as cliques and trees. For general graphs, only a brute force algorithm known [SMG+ + 20, Appendix F] which takes exponential time in the worst c In contrast to optimal algorithms, [PSS22] provides an efficient algorithm that returns a verifying set of size at most 2 times that of the optimum.
Theorem 12. Fix an essential graph E(G*) and G E [G*). (Gv = E, then va (G) 2 and there exists a polynomial time algo. to compute bounded size intervention set I of size [I]
+1.
To the best of our knowledge, our work provides the first known efficient algorithm for computing near-optimal bounded sized verifying sets for general graphs. Furthermore, we note that, for every
Theorem 11 also provides a rigorous justification to the observation of [SMG*20) that "In general, the size of an Jatomic verifying set] cannot be calculated from just its essential graph". This is because essential graphs could imply minimum vertex covers of different sizes (see Fig. 1).

---

there exists a family of graphs where the optimum solution requires at least [ + 1 bounded size interventions. Thus, our upper bound is tight in the worst case (see Fig. 6 in Appendix E.5).
Beyond minimal sized interventions, a natural and much broader setting in causal inference is one where different vertices have varying intervention costs, e.g. in smoking study, it is easier modify a subject's 's diet than to force the subject to smoke (or stop smoking). Formally, one can define a weight function on the vertices w + I which overloads w(S) -vvs w()) on interventions and w[I) E SET S intervention sets. Such an additive cost structure has been studied by [KDV17, GSKB18) 18.. Consider an essential graph which is a star graph on n. nodes where the leaves have cost 1 and the root has cost significantly larger than n. For atomic verifying sets, we that the minimum cost verifying set is to intervene on the leaves while the minimum size verifying set is to simply intervene on the root. Since one may be more prefemed over the other, depending on the actual real-life situation, we propose to find a verifying set I which minimizes
a (I) + 3 I
where a, 2
(1)
so as to explicitly trade-off between the cost and size of the intervention set. This objective also naturally allows the constraint of bounded size interventions by restricting |S|| S l for all S E
Note that the earlier results on minimum size verifying sets correspond to a = 0 and , = 1. Interestingly, the techniques we developed in the minimum size setting generalizes to this broader setting. Furthermore, our framework of covered edges allow us to get simple proofs.
Theorem 13. Fix an essential graph {()) and G [G*]. An atomic verifying set I for G that minimizes Eq. (1) can be computed in polynomial time.
Theorem 14. Fix an essential graph E(G') and G E [G*]. Suppose the optimal bounded size intervention set that minimizes Eq. (1) costs OPT. Then, there exists a polynomial time algorithm that computes a bounded size intervention set with total cost OPT + 23.
3.2 Adaptive search
Here, we study the unweighted search problem in causal inference where one wishes fully orient an essential graph obtained from observational data while minimizing the number of interventions used. Formally, we give an algorithm (Algorithm 1) that fully orients E(G') using at most a logarithmic multiplicative factor more interventions than 2% (G"), ), the number of (bounded size) interventions needed to verify the ground truth G*. Since any search algorithm will incur at least vn (G*) ) interven- tions, our result implies that search is (almost, up to log n multiplicative approximation) as easy as the verification. For detailed proofs, see Appendix
Theorem 15. Fix an essential graph {(G)) with an unknown underlying ground truth DAG G* Given k = 1, Algorithm I runs in polynomial time and computes an atomic intervention set I in deterministic and adaptive manner such that Er(G²) =G and [Z] E O(log(n) 1 (G")).
Theorem 16. Fix an essential graph ((G)) with an unknown underlying ground truth DAG G* Given k 1, Algorithm I runs in polynomial time and computes a bounded size intervention set I in a deterministic and adaptive manner such that Er(G*) = G and [ E Ollo((n) log(k) vn (G*)).
These results are the first competitive results that holds for using atomic or bounded size interventions on general graphs. The only previously known result of Ologz (cCKs w (H)) vi (G")
by [SMG+20] was algorithm based on directed clique trees with provable guarantees only for atomic interventions on interseciion-inoomaaabbl chordal graphs. To obtain our results, we are not simply improving the analysis of [SMG+20). Instead, we developed new algorithmic approach that is based on graph separators which is a much simpler concept than directed clique trees.
The approximation of (log to 2ı (G*) is the tightest can hope for atomic interventions in general. For instance, consider the case where E(G") is an undirected line graph on n vertices. Then, any adaptive algorithm needs 2(log n) atomic interventions in the worst case while V1 (G*) 1. The line graph also provides a clear distinction between adaptive and non-adaptive search algorithms since any non-adaptive algorithm needs (n))) atomic interventions to separate all the edges in E(G)).
The lower bound reasoning is similar to the lower bound for binary search.
7

---

Overview of techniques
4.1 Verification
Our results for the verification problem are broadly divided into two categories: (I) Connection between the covered edges and verification set (Theorem 9, Corollary 10); (II) Efficient computation of verification sets under various settings using the connection established.
For the first type of results, we show that any intervention set is verifying set if and only if it separates every unoriented covered edge of G E {G*). For necessity, we show that all four Meek rules (which are known to be consistent and complete) will not orient any unoriented covered edge of G that not separated by any intervention. Our proof is simple due to the usage covered edges. For sufficiency, all covered edges are separated. We prove this using a subtle induction over a valid topologiaal ordering of the vertices of G*: Let Vú be the first smallest vertices in π,, for i 1, ................................ Consider subgraph E ((') induced by V; with e being the last vertex in the ordering of V,, By induction, it suffices to show that all non-covered - i edges are oriented for Vi-1- To show this, we perform case analysis to argue that either u > 22 is part of v-structure (i.e. is already oriented in (G')) )) Meek rule R2 will orient it.
show that every unoriented non-covered edge of G will be oriented by Meek rules
The previous result only establishes equivalence between the verifying sets and the intervention sets that separate unoriented covered edges. For efficient computation of optimal verifying sets, we prove several additional properties of covered edges, which may of independent interest.
Lemma 17 (Properties of covered edges).
1. Let H be the edge-subgraph induced by covered edges of a DAG G. Then, every vertex in has at most one incoming edge and thus is a forest of directed trees.
2. If DAG G a clique on n 2 3 vertices u1 U2..... Vn, with π ((1) T(22) .... (V,).
then - ,2n.-..Vn-11 + Un are the covered edges of G.
Un-1
3. If + is a covered edge in a DAG G, then u cannot be a sink of any maximal clique of G.
The fact that the edge-induced subgraph of the covered edges is a forest enables us to use standard dynamic programming techniques to compute (weighted) minimum vertex covers for the unoriented covered edges of G, corresponding to minimum size atomic verifying sets (Theorem 11 and The- orem 13). For bounded size verifying sets, we exploit the fact that trees are bipartite and so we can divide the minimum vertex covers into two partitions. Since vertices within each partite are non-adjacent, we can group them into larger interventions without affecting the overall number of separated edges, giving the guarantees in Theorem 12 and Theorem 14.
Through the lens of covered edges, we see that existing universal bounds of [SMG*20 20, PSS22] are not tight". Consider the case where the essential graph (('') is the standing windmill graph given maximal cliques and the largest maximal clique
Fig. The graph E(G") ) has n nodes,
size 3. The lower bound of [SMG 20] yields EHEco(eaG))
- 1 = 1 while lower bound
of [PSS22] yields 2
8
2 2. Meanwhile, we show minge(a-) v1 (G) in Appendix
We can also recover the vn (G*) S bound of [PSS22] with short proof using covered edges. Lemma 18. For any essential graph E(G*) on vertices with maximal cliques, there exists an atomic verifying set of size at most r.
Proof. By Theorem 11. it suffices to find vertex cover of the unoriented covered edges of E(G*). By Lemma 17, any covered edge u - cannot have as sink of any maximal clique. So, the set of all vertices without the sink vertices a vertex cover of the covered edges E(G').
4.2 Search
Here we provide the description and proof overview of the search results. Our search algorithm (Algorithm 1) relies graph separators that formally define next. Existence and efficient
"The non tn-tightness of the universal lower bound of [PSS22] was known and verified via random graph experiments.
8

---

computation of graph separators are well studied [LT79, GHT84, GRE84, AST90, KRIO, WNII] and are commonly used in divide-and and--enuuerr graph algorithms and as analysis tools.
Definition 19 (a-separator and a-clique separator). Let A, B, C' be partition of the vertices V of graph G = (V, E). We say that an a-sepurator no edge joins a vertex in A with vertex in B and | B S [V] We call C' is an a-clique separator if it is an a-separator and clique.
Algorithm Search algorithm via graph separators.
1: Input: Essential graph {("),, intervention size k. Output: A fully oriented graph G E [G*).
2: Initialize i 0 and Ia V.
3: while Ez, (G*) still has undirected edges do
4: For each H CC((T, (G*)) of size [/I] 2 2, find a 1/2-clique separator Kи using
Theorem 20. Define Q = (K# ) HECC(E,, (G*)), H|22 as the union of clique separator nodes.
5: if = or [Q| = 1 then Define C; Q as an atomic intervention set.
6: else Define k = min(k: [Q1/2), a = [1Q) scheme of [SKDV15, Lemma I] on Q with (IQ), k", .a), and define C; = (S2.g (es()_w()
2, and & = [log, n! Compute labelling
where S.,yy S Q is the subset of vertices whose 2thh letter in the label is y-
7: Update - i + 1, intervene on C, to obtain &T, (G*), and update I; t- I UC:.
8:
end while
We first give the proof strategy for Theorem 15, the atomic case where k = 1. We divide the analysis into two steps. the first step, we show that the algorithm terminates Ollog n) iterations. In the second step, we argue that the number of interventions performed in each iteration is in (G))
The analysis of the first step relies on the following result of [GRE84].
Theorem 20 ([GRE84), instantiated for unweighted graphs). Let G = E) be a chordal graph with [V| 2 and p vertices in its largest clique. There exists ca--cliue-seppratan of size [C] S - 1. The clique C can be computed in ((E)) time.
At each iteration i of the algorithm, we intervene on a 1/2-clique separators of each connected chain component. Note that the size of each connected chain compoenent at the end of iteration i is at most n/2'. Therefore, after Olog n)) iterations, each connected chain component will contain at most 1 vertex, implying that all the edges have been oriented.
To bound the number of interventions used in each iteration, prove a stronger universal lower bound that built upon the lower bound of ISMG-200. While not computable" 12 it a very powerful lower bound for analysis: In Fig. of Appendix G, give an example where (G*) Ro while the lower bound of [SMG- 20] on CC(E(G") is a constant. Meanwhile, there exists set of atomic interventions I such that applying [SMG+20 20] on CC(Ez yields much stronger 22() bound. Lemma 21. Fix an essential graph E(G*) and G E [G*]. Then,
(G) > max TCV
Σ
W
H 2
HECCLEN(G))
As we intervene on cliques in each connected component at every iteration, Lemma 21 shows that we use at most 2 1 (G*) interventions per iteration. Therefore, the total interventions used by Algorithm is in (log(n) vi (G()))
For bounded size interventions (Theorem 16), follow the strategy as above but modify how we orient the edges within and cut by the 1 1/2-clique separators. More specifically, we compute a separating system for the union of clique separator nodes based on the labeling scheme of [SKDV15] 15] and perform case analysis to argue that we use (log(k)) vn (G*)) bounded size interventions per iteration.
Lemma 22 (Lemma 1 of (SKDV15]). Let (n, k, a) be parameters where k < n/2.. There is polynomial time labeling scheme that produces distinct length labels for all elements in [n] using letters from the integer alphabet {0} U [[a] where { = [log, n. Further, in every digit (or position), any integer letter is used at most [n/ a times. This labelling scheme is a separating system: for any i.j E [n), there exists some digit d E [6] where the labels of and j differ.
Pt involves maximization over all possible atomic interventions and we do not know the Ez

---

Experiments and implementation
We implement verification algorithm and test its correctness some well-known graphs such as cliques and trees, for which we know the exact verification number. In addition, we implement Algorithm and compare its performance with other known atomic search algorithms [HG08, HB 14, SKDV15, SMG+ 20] via the experimental setup of [SMG+ on synthetic graphs of varying sizes, we compare the runtime and total number of interventions performed compared to the verification number of the underlying DAG. In Appendix H. we provide the full exper- imental details and results of running various search algorithms (including ours) on different graphs. Qualitatively, our algorithm is competitive with the state-of-the-at search algorithms while being 100 faster in some experiments. Fig. shows subset of these results. We also investigated the impact of different k values on the performance of our search algorithm in Ap- pendix H. The implementations, along with entire experimental setup, are available https: //gi thub. wethub.coomeeeeeeeee wwwp/vaa//eerriiaaaattttoo wnw.ffiiiiiinnnnd-aaee--e-n---ee
al algori sewritthssforr fattmms-o--cuusa---a-- causal-DAGs.
I
Colbring
Coloring
OCT
CCT
GreedyCrnropyy Groe2yMEC
1/
Average Compettive Retto
Average Competttvee Ratio
Curs (Km3)
2,5
OptSingle
Random
Ours
30
2.0
8
3.5
1.
12
200 200
J00
350
Number Vodie
Number
Figure 2: The figures show the average competitive ratios with respect to synthetic graphs of different node sizes. See Appendix H for details about how the synthetic graphs are generated and for details on the algorithms benchmarked. We also show the maximum competitive ratios in Appendix H.
Conclusion, limitations, and societal impact Learning causal relationships is of fundamental importance to science and society in general. This is especially important when one wishes to correctly predict effects of making changes to system for downstream tasks such as designing fair algorithms. In this work, gave complete understanding of the verification problem and an improved search algorithm under the standard causal inference assumptions (see Section 1). However, if our assumptions lead to unintended downstream consequences. Hence, it is of great interest to remove/weaked these assumptions while maintaining strong theoretical guarantees. A erucial limitation of this work is that we study an idealized setting with hard interventions and infinite samples while soft interventions may be more realistic in certain real-life scenarios (e.g. effects from parental vertices are not completely removed but only altered) and sample complexities play a crucial role when one has limited experimental budget (e.g. see [KJSB19] and [ABDKI8] respectively).
violated by the data, then wrong causal conclusions may be drawn and possibly
Acknowledgments and Disclosure of Funding
This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: CLGG-PDD/2211-8-0111 KS was supported by a Stanford Data Science Scholarship. Dantzig-Lieberman Lieberman Research Fellowship and a Hemnons-Berkeley Re- search Fellowship. AB partially supported by an NUS Startup Grant (R-252-000-A33--333) and an NRF Fellowship for AI (NRFFAI1-2019-00D) Myrisiotis, and Chandler Squires for valuable feedback and discussions. Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing.
We would like to thank Themis Gouleakis, Dimitrios
10

---

References
[ABDKI8] Jayadev Acharya, Arnab Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy. Learning and Testing Causal Models with Interventions. Advances in Neural Information Processing Systems, 31, 2018.
[ABGLPI9] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 2019.
[AMP97] Steen Andersson, David Madigan, and Michael D. Perlman. A characterization of Markov equivalence classes for acyclic digraphs. The Anmals of Statistics, 25(2):505- 541, 1997.
[AST90] Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, 3(4) 1990.
[BP93] Jean R. S. Blair and Barry W. Peyton. An introduction to chordal graphs and clique trees. In Graph theory and sparse malrix computation, pages 1-29. Springer, 1993.
[Chi95] David Maxwell Chickering. A Transformational Characterization of Equivalent Bayesian Network Structures. In Proceedings of the Eleventh Conference on Un- certainty in Artificial Intelligence, UAI'95, page 87-98, San Francisco, CA. USA, 1995. Morgan Kaufmann Publishers Inc.
[Chi02] David Maxwell Chickering. Optimal Structure Identification with Greedy Search. Journal of machine learning research, 3(Nov)5507-554, 2002.
[Ebe07] Frederick Eberhardt, Causation and Intervention. Unpublished doctoral dissertation, Carnegie Mellon University, page 93, 2007.
[Ebe10] Frederick Eberhardt. Causal Discovery as a Game In Causality: Objectives and Assessment, pages 87-96. PMLR, 2010.
[EGS06] Frederick Eberhardt, Clark Glymour, and Richard Scheines. N-1 Experiments Suffice Determine the Causal Relations Among N Variables. In Innovations in machine learning, pages 97-112. Springer, 2006.
[EGS12] Frederick Eberhardt, Clark Glymour, and Richard Scheines. On the Number of Ex- periments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among Variables. arXiv preprint arXiv: /20. 2012.
[ES07] Frederick Eberhardt and Richard Scheines. Interventions and Causal Inference. Philos- ophy of science, 74(5):981-99) 995, 2007.
[GHT84] John R. Gilbert, Joan P. Hutchinson, and Robert Endre Tarjan. A Separator Theorem for Graphs of Bounded Genus. Journal of Algorithmss, 5(3):391-407, 1984.
[GKS+ 19] 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.
[GRE84] John R. Gilbert, Donald J. 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 Confer- ence on Machine Learning, pages
PMLR, 2018.
[GUA+16] + 16] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domainnadveesariia training of neural networks. The journal of machine learning research, 17(1):2096- 2030, 2016.
11

---

[HB12] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interven- tional Markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, (11):2409-24644 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-93,, 2014.
[HEH13] Antti Hyttinen, Frederick Eberhardt, and Patrik O. Hoyer. Experiment Selection for Causal Discovery. Journal of Machine Learning Research, 14:3041-3071, 2013.
[HG08] Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(No)): 2547, 2008
[HLV14] Huining Hu, Zhentao Li, and Adrian Vetta. Randomized Experimental Design for Causal Graph Discovery. Advances in neural information processing systems, 27, 2014.
[Hoo90] Kevin D Hoover. The logic of causal inference: Econometrics and the Conditional Analysis of Causation. Economics & Philosophy, 6(2):207-234, 1990.
[KDV17] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-Optimal Learning of Causal Graphs. In International Conference on Muchine Learning, pages 1875-1884. PMLR, 2017.
[KF09] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[JSBB19] Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Charac- terization and Learning of Causal Graphs with Latent Variables from Soft Interventions. Advances in Neural Information Processing Systems, 32, 2019.
[KR10] Ken-ichi Kawarabayashi and Bruce Reed. A separator theorem in minor-closed classes. In 2010 IEEE 51st Annual Symposium Foundations of Computer Science, pages 153-162. IEEE, 2010.
[KSSU19] Dmitriy Katz, Karthikeyan Shanmugam, Chandler Squires, and Caroline Uhler. Size of Interventional Markov Equivalence Classes Random DAG Models. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3234-3243. PMLR, 2019.
[KW]+04] Ross King, Kenneth E. Whelan, Ffion M. Jones, Philip G. K. Reiser, Christopher Bryant, Stephen H. Muggleton, Douglas B. Kell, and Stephen G. Oliver. Functional genomic hypothesis generation and experimentation by robot scientist. Nature, 427(6971):247- 2004.
[LKC17] Gilles Louppe, Michael Kagan, and Kyle Cranmer. Learning pivot with adversarial networks. Advances in neural information processing systems, 30, 2017.
[LKDV18] Erik M. Lindgren, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath. Experimental Design for Cost-Aware Learning of Causal Graphs. Advances in Neural Information Processing Systems, 31, 2018.
[LT79] Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979.
[Mee95] Christopher Meek. Causal Inference and Causal Explanation with Background Knowl- edge. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelli- gence, UAI'95, page 403-410, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.
[MP]+ 16] Joris M. Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Bernhard Schölkopf. Distinguishing Cause from Effect Using Observational Data: Methods and Benchmarks. J. Mach. Learn. Res., 1030)41003,124, Jan 2016.
12

---

[PB [4] Jonas Peters and Peter Bühlmann. Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1):219-225) 2014.
[Pea09] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, USA, 2nd edition, 2009.
[POS+ Jean-Baptiste Pingault, Paul F O'reillly, Tabea Schoeler, George B Ploubidis, Frühling Rijsdijk, and Frank Dudbridge. Using genetic data to strengthen causal inference in observational research. Nature Reviews Genetics, (999)566-588) 2018.
[PSS22] Vibhor Porwal, Piyush Srivastava, and Gaurav Sinha. Almost Optimal Universal Lower Bound for Learning Causal DAGs with Atomic Interventions. In The 25th International Conference on Artificial Intelligence and Statistics, 2022.
[Rei66] Hans Reichenbach. The direction of time, volume 65. Univ of California Press, 1956.
RHT 17] Maya Rotmensch, Yoni Halpern, Abdulhakim Tlimat, Steven Horng, and David Sontag. Learning Health Knowledge Graph from Electronic Medical Records. Scientific reports, 7(1):1-11, 2017.
[RW06] Donald B Rubin and Richard P Waterman. Estimating the Causal Effects of Marketing Interventions Using Propensity Score Methodology. Statistical Science, pages 206-222, 2006.
[SC17] Yuriy Sverchkov and Mark Craven. A review of active learning approaches to ex- perimental design for uncovering biological networks. PLoS computational biology, 13(6)=e100546) 2017.
[Sch22] Bernhard Schölkopf.
Causality for Machine Learning, page 765-804. Association for Computing Machinery, New York, NY, USA, I edition, 2022.
[SGSH00] Peter Spirtes, Clark N. Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT press, 2000.
[SHHK06] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non- gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[SKDV15] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vish- wanath. Learning Causal Graphs with Small Interventions. Advances in Neural Information Processing Systems, 28, 2015.
[SMG+20] Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Ko- caoglu, and Karthikeyan Shanmugam. Active Structure Learning of Causal DAGs via Directed Clique Trees. Advances in Neural Information Processing Systems, 33:21500-
21511, 2020.
[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.
[WBL21] Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Extendability of causal graphical models: Algorithms and computational complexity. In 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 1248-1257 PMLR, 27-30 Jul 2021.
[WN11] Christian Wulff-Nilsen. Separator theorems for minor-free and shallow minor-free graphs with applications. In 2011 IEEE 52nd Annual Symposium Foundations of Computer Science, pages 37 46. IEEE, 2011.
[Woo05] James Woodward. Making Things Happen: A theory of Causal Explanation. Oxford university press, 2005.
13


Reviews:
[{"review_id": "tP_2hC-qPwE", "reviewer": "Reviewer_vQyV", "summary": "The authors study the problems of verification and search for identifying causal DAGs from minimal-cost interventions. Using the concept of covered edges, they provide a theoretical result characterizing verifying sets, as well as a practical method for constructing such sets optimally. For the problem of search, the paper provides a novel algorithm for search, with complexity bounded by a connection to the minimum cost verifying set.", "questions": "1) Have the authors considered adaptive solutions for the verification problem also, and whether this might provide further benefit?\n", "limitations": "Yes, limitations and social impact have been addressed explicitly in the text.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, this is a strong theoretical work which provides novel perspectives on minimal-cost identification of causal DAGs. The authors make a number of novel connections between the verification and search problems, some of which in particular are very interesting and even surprising:\n- Thm 9, which states that it is N+S to separate all covered edges in G to verify G (reduce G’s I-MEC to a singleton); this is a stronger version of prior results on the search problem (e.g. Thm 1 in [KDV17]) which say it is N+S to separate all edges to find the true graph (reduce all I-MECs to singletons).\n- That the search problem can be algorithmically linked to the verification problem by Lemma 21, with a strategy of intervening on cliques whose size can be bounded by intervention sizes for the verification problem.\n\nThe theoretical connections also give rise to efficient algorithms for performing verification and search on general graphs, which are a significant advance over prior approaches.\n\nFrom a presentation standpoint, the paper is generally well written with clear presentation of the results and comparison to prior work. However, it is also very dense, particularly with the novel results and algorithms, which are packed into the final 4 pages of the paper. For instance, Algorithm 1 would benefit from explanation of the function/intuition behind each step, as well as bounding the complexity. I would suggest that the authors move some of the (arguably) more peripheral content to the Appendix (e.g. lines 258-277), to make more space to explain the key results. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iG6l5Xx8cYO", "reviewer": "Reviewer_ua5U", "summary": "The paper proposed recovering and verification of causal graphs via sufficient hard interventions with unlimited data.  Contributions are constructing bounds on the “minimum verification number” of a graph G belonging to the Markov equivalent class of the underlying ground truth.  Compared to existing approaches, their method could deal with general graph.  They characterize the verifying intervention sets via separation of un-oriented cover edges of the input essential graph. \n\nThey also consider a relative new setting, i.e. verifying if an expert provided causal graph is correct using minimal interventions. \n\nFurthermore, they use an objective function to measure the optimality of intervention policies by trading  off the additive weights of verification inventions as well as the size of the verification set. \nThe main contribution of this paper seems to theoretical, by proving a strengthened version of previous work. \n\nThe paper is well written with clean explanations, the contributions are summarized clearly, lemmas correspondence to existing works are well indicated. \n\nThere is no conclusion section, for page limit, it looks like algorithms could still be moved to appendix to save some space for another summary at the end if the authors did not find this unnecessary. ", "questions": "Q1. I believe a tighter bound would give better guidance in practice, before verification/adaptive search, for the experiment carrier to evaluate how many resources one might need to allocate to finish the experiment, i.e. identify the causal graph. \n\nWhat would be the future work of this work, consider if this paper get cited in the future, what would be the improvements based on this paper? \n\nQ2. If I did not miss it, there seems to be no empirical study to support the claims made in the paper, compared to SMG 20, PSS 22.\nRegarding the new scheme used in this contribution, does the author think it might be helpful to carry out empirical studies to validate those bounds or show the superiority of the new policy?\n\nQ3. In line 351, what does “arefi9x” mean?\nQ4. it seems that there is no conclusion of the paper?\n\n", "limitations": "L1:\nI would suggest conducting an empirical study validating the proposed algorithm alongside the theorems. ", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n\n\n\nStrengths:\nS1. They extend previous results to general graphs and provide tighter bounds\nS2. They also consider a relative new setting, i.e. verifying if an expert provided causal graph is correct using minimal interventions. \nS3. They derived richer results  beyond single vertex intervention. \n\n\n\nWeakness:\n\nW1. The paper assume causal sufficiency, which is usually not true in reality. \nAs noted in the introduction part, the hard intervention is also not a realistic assumption. \n\nW2. If I did not miss it, there seems to be no empirical study to support the claims made in the paper, compared to SMG 20, PSS 22.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eliRm7ZFsWf", "reviewer": "Reviewer_A2Kf", "summary": "This paper considers the problem of recovering causal graphs from interventional data (search problem). Additionally to recovering of an unknown causal graph, the authors studied the problem of verifying whether a given directed causal graph is indeed the correct one using an optimal number of interventions (verification problem). They proposed lower bounds for both of the considered questions which are based on the minimum verification number. Finally, they proposed an algorithm for both problems and derived bounds on the number of performed interventions.", "questions": "- Lemma 35 looks different from Lemma 6 in [SMG+20], but in the paper, it is asserted that they are the same. How can Lemma 35 be obtained from Lemma 6 [SMG+20]?\n- Why the proposed search algorithm is better than already existing algorithms and what are the main differences between them?\n", "limitations": "The authors briefly mentioned possible limitations for transferring the results to the real world, which are reasonable. All the limitations do not have a negative social impact. \n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- The authors studied an interesting connection between the optimal number of interventions that are needed to verify whether the given directed causal graph is correct and the optimal number of interventions that one needs to recover the causal graph. Furthermore, they compare their results with existing works.\n\nWeaknesses: \n- Despite there is an example that the minimum verification number is larger than the lower bounds derived in [PSS22], it is not clear how much this bound is better. It seems that the difference between these two values may be just a constant or just a constant ratio. \n- Lemma 35 is different from the lemma introduced in [SMG+20] and it is not obvious how it is possible to get Lemma 35 from Lemma 6 in [SMG+20]. Lemma 35 is then used for the proof of Lemma 21, which are one of the main results in comparing achieved lower bounds with another work.\n- The proposed algorithm is fully composed of steps irrelevant to the minimum verification number. Moreover, the whole analysis of the algorithm follows the theorems from the other works, and it is not unclear how this algorithm is different from already existent ones and why it would have better performance. \n- No experiments were done for comparing the proposed algorithm with already existing algorithms.\n- Some of the results about minimum verification number are easy corollaries of already existing theorems (such as Theorem 11 and 12).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept