Less Greedy Equivalence Search
Authors: Adiba Ejaz
Elias Bareinboim
Venue: NeurIPS 2025 poster ()
Keywords: causality
reasoning under uncertainty
causal discovery
structure learning
Primary area: probabilistic_methods
TL;DR: We develop the Less Greedy Equivalence Search algorithm for learning causal structure from observational and interventional data with prior knowledge.

Abstract: Greedy Equivalence Search (GES) is a classic score-based algorithm for causal discovery from observational data.
In the sample limit, it recovers the Markov equivalence class of graphs that describe the data.
Still, it faces two challenges in practice: computational cost and finite-sample accuracy.
In this paper, we develop Less Greedy Equivalence Search (LGES), a variant of GES that retains its theoretical guarantees while partially addressing these limitations.
LGES modifies the greedy step; rather than always applying the highest-scoring insertion, it avoids edge insertions between variables for which the score implies some conditional independence.
This more targeted search yields up to a $10$-fold speed-up and a substantial reduction in structural error relative to GES.
Moreover, LGES can guide the search using prior knowledge, and can correct this knowledge when contradicted by data.
Finally, LGES can use interventional data to refine the learned observational equivalence class.
We prove that LGES recovers the true equivalence class in the sample limit, even with misspecified knowledge.
Experiments demonstrate that LGES outperforms GES and other baselines in speed, accuracy, and robustness to misspecified knowledge.
Our code is available at https://github.com/CausalAILab/lges}{https://github.com/CausalAILab/lges.

Less Greedy Equivalence Search
Adiba Ejaz
Elias Bareinboim Causal Artificial Intelligence Lab Columbia University
{adi ba. ejaz, @bc columbia.edt
Abstract
Greedy Equivalence Search (GES) is classic score- score-based algorithm for causal discovery from observational data. In the sample limit, recovers the Markov equivalence class of graphs that describe the data. Still, it faces two challenges in practice: computational cost and sample accuracy. In this paper, we develop Less Greedy Equivalence Search (LGESS), a variant of GES that retains its theo- retical guarantees while partially addressing these limitations. LGES modifies the greedy step; rather than always applying the highest-scoring insertion, it avoids edge insertions between variables for which the score implies some conditional independence. This more targeted search yields up to 10-fold speed-up and a substantial reduction in structural error relative to GES. Moreover, LGES can guide the search using prior knowledge, and can correct this knowledge when contradicted by data. Finally, LGES can use interventional data to refine the learned observational equivalence class. We prove that LGES recovers the true equivalence class in the sample limit, even with misspecified knowledge. Exper- iments demonstrate that LGES outperforms GES and other baselines in speed, accuracy, and robustness to misspecified knowledge. Our code is available at https///iihubbcoo/aaaalllllllll
1 Introduction
Causal discovery, the task of learning causal structure from data, is core problem in the field of causality [54]. The causal structure may be an end in itself to the scientist, or prerequisite for downstream tasks such as inference, decision-making and generalization 2
42 Causal discovery
algorithms have been used in a range of disciplines that span biology, medicine, climate science, and
neuroscience, among others I99 43 47 48).
hallmark algorithm in the field is Greedy Equivalence Search (GES) 9 35 which takes input observational data and finds a Markov equivalence class (MEC) of causal graphs that describe the data. In general, the true graph is not uniquely identifiable from observational data, and the MEC is the most informative structure that can be learne.. Under standard assumptions in causal discovery, GES guaranteed to recover the true MEC in the sample limit. In contrast, many causal discovery algorithms-inee including prominent examples such as max-min hill-climbing [56] and NeTea [6 lack such large-sample guarantees. Many variants of GES have been developed, including faster, parallelized implementations [43,, restricted search over bounded in-degree graphs [10. and Greedy Interventional Equivalence Search (GIES) 24). The last of these can exploit interventional data, though is not asymptotically correct [58]
Despite its attractive features, the GES family faces challenges shared across most causal discovery algorithms. For instance, the problem of causal discovery is NP-hard [II], and GES commonly struggles scale in high-dimensional settings. Moreover, in finite-sample regimes, GES often fails to recover the true MEC. In other words, applying GES in practice is challenging due to both
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

computational complexity (scaling) and sample complexity (accuracy) issues. We refer readers to [56] for an extensive empirical study of GES performance.
At a high level, GES searches over the space of MECs by inserting and deleting edges to maximize exponentially
score reflecting data fit. At each state, it evaluates set of neighbors-possinne many-and moves to the highest-scoring neighbor that scores more than the current MEC. It continues the search greedily until no higher-scoring neighbors are found. In the sample limit, this strategy is guaranteed to find the global optimum of the score: the true MEC.
In this paper, we question the basic assumption of the GES family that the greedy choice of the highest-scoring neighbor is the best one. We first introduce Generalized GES (Alg. B), which allows moving to any score- -oreeinnceasing neighbor of the current MEC, not necessarily the highest-scoring one. This relaxed strategy still finds the glohal optimum of the score in the sample limit (Thm. D More importantly, it opens the door more strategic neighbor selection.
While it may seem that choosing the highest-scoring neighbor would yield the best performance in practice, surprisingly,
show that this is not the case; careful and less greedy choice improves both accuracy and runtime. Specializing GGES, we develop the algorithm Less Greedy Equivalence Search (LGES) (Alg. D advancing GES and its relatives in the following ways:
1. Faster, more accurate structure learning. In Sec. 3.2 we introduce two novel operator selection strategies, CONSERVATIVEINSERS and SAFEINSERT, which LGES exploits for neighbor selection. Empirically, these procedures yield up to 10-fold reduction in runtime
and 2-fold reduction in structural error relative to GES (Experiment) [.T] and other baselines.
LGES with SAFEINSERT asymptotically recovers the true MEC (Prop. 2 Cor. (
2. Robustness to misspecified prior knowledge. In Sec. 3.3 we propose method whereby LGES can guide neighbor selection based on prior knowledge (Alg. while remaining asymptotically correct even if the knowledge is misspecified. Accurate knowledge improves LGES' accuracy and runtime; inaccurate knowledge harms LGES significantly less than it does GES initialized with the knowledge (Experiment 5.2
3. Refining the learned MEC with interventional data. In Sec. 4 develop I-ORIENT (Alg-2) 2 Thm. 2). a score- score-based procedure that LGES (or any structure learning algorithm) can use to refine an observational MEC with interventional data. To our knowledge, this is the first asymptotically correct score-based procedure for learning from interventional data that can scale graphs with more than hundred nodes. LGES with T-ORIENT is 10x faster than GIES 24 while maintaining competitive accuracy (Experiment (.3)
Proofs for all results are provided in Appendix C Additional experiments with synthetic data and real-world protein signalling data 48 are provided in Appendix D
Background
Notation.
Capital letters denote variables (V), small letters denote their values (v), and bold
letters denote sets of variables (V) and their values (v). P(v) denotes a probability distri-
bution over set of variables V. For disjoint sets of variables X, Y, Z. X 1l Y Z de-
notes that X and Y are conditionally independent given Z and X Ia Y | Z denotes that
X and Y are d-separated given Z in the graph in context.
Σ
X
Z
Y
Causal graphs 3 42).
A causal graph over variables V is a directed
91
acyelic graph (DAG) with an edge X + Y denoting that X is possible cause of Y. The parents of variable X in graph G, denoted Pa are those variables with a directed edge into X. The non-descendants of variable X in a graph G, denoted Nd are those variables which there is no directed path from X (excluding X itself). The superscript will be omitted when clear from context. A given distribution P(v) is said to be Markov with respect to a DAG G if for all disjoint sets X, Y. Z C V, if X La Y in 9, then X 11 Y Z in P(v). If the converse is also true, P(v) is said to be faithful to G. In this work, like GES 19, we assume
G2
X
Z
Y
G3
Figure 1: A CPDAG and the three DAGs in the MEC it represents, en- coding X 1. Y Z.
2

---

that the system of interest is Markovian, i.e. it contains no unobserved confounders, and that there exists a DAG G with respect to which the given P(v) is both Markov and faithful.
Two causal DAGS G, H. are said to be Markov equivalent they encode exactly the same d-separations. The Markov equivalence class (MEC) of a DAG is the set of all graphs that are Markov equivalent to it. A given P(v) may be Markov and faithful to more than one DAG. Hence, the target of causal discovery from observational data is the MEC of DAGs with respect to which P(v) is Markov and faithful. An MEC M is represented by a unique completed partially directed graph (CPDAG). A CPDAG & for M has an undirected edge X - Y M contains two DAGs 91, G2 with X - Y in 91 and Y + X in G2. & has directed edge X - Y if X + Y in every DAG in M. We frequently refer to an MEC by representative CPDAG. The adjacencies (neighbours) of variable X in a CPDAG E, denoted Adjx (Ne ) comprise those variables connected by any edge (an undirected edge) to X.
Markov equivalence classes 41 54
Greedy Equivalence Search (9) 353. Greedy Equivalence Search (GES) a score-based algorithm for learning MECs from observational data. It searches for the true MEC by maximizing a scoring criterion given m samples of data D P(v). For example, a popular choice of scoring criterion is
the Bayesian information criterion (BIC) [51].
GES assumes that the given scoring criterion is decomposable, consistent, and score-equivalent, so that the score of an MEC is the score of any DAG in that MEC (Defs. [A.3] A.4
A.5
BIC
satisfies each of these conditions for distributions that are Markov and faithful to some DAG and
curved exponential families, for e.g., Finear-Gaussia or multinomial models 9 21 23
Moreover,
decomposability and consistency imply local consistency 99 Lemma 7J), the key property needed for the correctness of GES.
Definition (Locally consistent scoring criterion g Def. 6)). Let D be a dataset consisting of i.i.d. samples from some distribution P(v). Let be any DAG, and let G' be the DAG that results from adding the edge X + Y to G. A scoring criterion S is said to be locally consistent if, as the number of samples goes to infinity, the following two properties hold:
1. X J Y Pay in P(v) then S(G, D) < S(G', DD.
2. If X Y Paş in P(v) then S(G D) > S(g', DD.
Example 1. Consider a distribution P(v) whose true MEC is E and true DAG is G2 e E as in
Fig. Consider 91 & (Fig. and let 9 G1 (X - Y) and 9 = 91 \ (z Y). Since
Y IL X Pa in P(v). where Pa { f has lower score than G1. Since Y 1 Z Pay 9T
in P(v). where Pay er = 0. 9J has lower score than G1.
Given scoring criterion satisfying the above conditions and data D ~ P(v) where P(v) is Markoy and faithful to some DAG, GES recovers the true MBC in the sample limit g Lemma 10]. The PC algorithm (54 constraint-based method, has similar asymptotic correctness guarantees, but uses conditional independence (CI) tests instead a score. PC starts with a fully connected graph and removes edges using CI tests. In contrast, GES starts with a fully disconnected graph and proceeds in two phases. In the forward phase, at each state, GES finds the highest-scorin INSERT operator that results in score increase, applics it, and repeats until no correinneaasiig INSERT operator exists. At this point, it has found an MEC E with respect to which P(v) is Markov.
Definition (INSERT operator. [9] Def. 12]. Given a CPDAG &, non-adjacent nodes X, Y in E, and some C Ne Adj the INSERT(X, Y, T) operator modifies & by inserting the edge X - Y and directing the previously undirected edges T - Y for T E T as T Y.
Intuitively, an INSERT(X, Y, T) operator applied to an MEC È corresponds to choosing a DAG & E (depending on X, Y, and T), adding the edge X - Y to G. and computing the MEC of the resulting DAG. Though P(v) is Markov with respect to the MEC E found in the forward phase, P(v) may not be faithful to Σ. In the backward phase, GES starts the search with E, finds the highest-scoring DELETE(X, Y. H) operator (Def. A.2) that results a score increase, applies it, and repeats until no score-increasing DELETE operator exists. At this point, it has found an MEC with respect to which P(v) is both Markov and faithful. An optional turning phase is known to improve performance in practice, but is redundant for asymptotic correctness [4]]
3

---

Y
Y
Y
Inve MEC E
Trajectories
Z
X2
X1
2
X1
X2
X1
X2
X2
Y
Y
Y
2
Z
X1
X2
X1
X2
X1
X
X2
X
X2
==
1=
r=
f 5
Figure 2: Possible trajectories, and T2. that GES may take in the forward phase to obtain an MEC with respect to which given distribution P(v) Markov. The true MEC Ex (top right). In each trajectory, g(++) results from applying some INSERT operator to g(()
Less Greedy Equivalence Search
3.1 Generalizing GES
To lay the groundwork for our search strategy, we first introduce Generalized GES (GGES) (Alg. 3) which generalizes GES three ways. Firstly, GGES allows the search be initialized from an arbitrary MEC Eg, rather than the empty graph. Secondly, GGES is not restricted to the forward- backward-turme aarrdtu phase structure of GES; can accommodate any order of operators (e.g., deletions before insertions (36]) as specified by the user. Finally, GGES allows the application of any valid score-increasing operator, instead of just the highest-scoring one.
At each state ε, GGES calls abstract subroutine GETOPERATOR ATOR, which either returns a valid score- increasing operator of the type specified (insertion, deletion, reversal, or either), if one exists, or indicates that there no such operator. This proceeds until no score-improving operators are found.
Theorem (Correctness of GGES). Let denote the Markov equivalence class that results from GGES (Alg. 3) initialised from arbitrary MEC Eo and let P(v) denote the distribution from which the data D was generated. Then, as the number of samples goes to infinity, the Markov equivalence class underlying P(v).
In the next section, we illustrate how GETOPERATOR can be implemented in a way that yields significant improvements in accuracy and runtime relative to GES.
3.2 An improved insertion strategy
In practice, the output of GES is known include adjacencies between many variables that are non-adjacent in the true MEC [36 56). Since these adjacencies are introduced by INSERT operators, this motivates more careful choice of which INSERT operator to apply. Our approach grounded in the following observation.
Proposition Let denote an arbitrary CPDAG and let P(v) denote the distribution from which the data D was generated. Assume, the number of samples goes to infinity, that there exists valid score-decreasing INSERT(X, , Y, T) operator for E. Then, there exists a DAG g E & such that (1) Y La X Pa and (2) Y IL X Pa in P(v).
Then, for variables X and Y, even single score-decreasing INSERT(X, Y, T) implies that X and Y are non-adjacent in the true MEC. However, this does not imply that all INSERT(X, Y, x) ) are also score-decreasing. GES may thus apply different INSERT(X, Y, T'), introducing an adjacency present in the true MEC. The following example shows how such choices can lead GES to MECs that contain many excess adjacencies.
Example 2. Consider distribution P(v) over V (X,, X2, Y, Z) whose true MEC is given by Ex in Fig. (top right). GES starts with the empty graph and successively applies the highest-scoring INSERT operator that finds. Trajectories TI and T2 agree until time 1. Let g(1) denote the CPDAG common to and at = 1. At 1, GES has many INSERT operators it could apply to

---

E(), Recall that each INSERT (a, 3. T) applied to g()) corresponds to choosing some DAG G from g()) and adding + 3 to it. The DAG G is chosen such that for edges 3 in g() where a and are non-adjacent, 9 contains 7 -> / if E and / + 7 otherwise.
1. a - 8 = 2, T = 0. This corresponds to choosing G1 E g (which already has - Y) and adding X1 + Z to it (Fig. 3 left). Since 7 y X1 Pa this edge addition increases the score of 91 (by local consistency, Def. 1 and hence of g(), This operator is chosen in trajectory 71
2. a = X1, 81,8=
{Z}. This corresponds to choosing 91 E g()) (which already has Z + Y) and adding X1 - Y to it (Fig. 3 middle). Since Y IL X1 Paγ this edge addition decreases the score of Gi and hence of g(1), This operator is never chosen.
3. 0 = 3 Y.T = 0. This corresponds to choosing 92 E g()) (which already has Y + Z) and adding X1 - Y it (Fig. right). Since Y # X1 Pay this edge addition increases the score of G and hence of gd)) This operator is chosen in trajectory T2.
In the sample limit, it is unknown whether GA or Gc would score higher. For an extended discussion, see Ex. B.1
The above example shows that GES may insert an edge between non- adjacent variables even in simple set- tings with small number of vari- ables. Such choices accumulate in higher-dimensional settings. This mo- tivates avoiding edge insertions for variable pairs (X, Y) for which score-decreasing INSERT is observed. We hypothesize this has two benefits: (1) accuracy: it avoids inserting ex-
Y
Y
Z
X,
X2
X
X2
X
X²2
9 U [X1 - 2}
9 U (X1 +Y]
G2 (X1 YY
Figure 3: Illustration of some INSERT operators that may be applied to the MEC g at 1 in Fig. 2 These operators correspond to various edge additions to the DAGs G1, G2 E g()) where G1 orients Z Y Z + Y and G2 orients cess adjacencies that the backward Z as Y + Z.
phase may fail to remove, and (2): efficiency: it stops the enumeration of (X, Y) insertions when lower-scoring one found; moreover, reducing excess adjacencies reduces the number of operators that need to be evaluated in subsequent states.
We now formalize two strategies for avoiding such insertions. Strategy 1 (CONSERVATIVEIISERRY)
At given state with CPDAG & for each non-adjacent pair (X, Y), iterate over valid INSERT( X, T). If any score-decreasing is found, stop, discard all INSERT(X, Y, *) operators and continue to the next pair. Among all retained candidates, select the highest-scoring operator that results in score increase, if any.
CONSERVATIVELNSSER avoids inserting edges between any variables (X, Y) for which some condi- tional independence has been found, evidenced by score-decreasing INSERT (Prop. D. While intuitive, is unknown this strategy is guaranteed to find a score-increasing INSERT whenever one exists. To elaborate, the soundness of CONSERVATIVEINS P(v) is not Markov with respect to an MEC &, then there must exist variables X, Y such that for every 9 E E, X J Y Paf. Importantly, the choice of X, Y can not depend on G. This is the main challenge in proving the soundness of CONSERVATIVEINNSERT Still, we provide partial guarantees in Prop.
rests on the following premise: if
but leave the soundness of CONSERVATIVEINSERRT open.
Furthermore, we introduce SAFEINSERT, a relaxation of CONSERVATIVEINSERRY that is guaranteed to find a score-increasing INSERT when one exists. The soundness SAFEINSERT only requires that
We can also ask, which of these INSERT operators scores the highest in practice? We generated 100 linear- Gaussian datasets of 100 samples each according
fixed true DAG in E., following the set-up in Sec. 5.1 Then, we computed the scores of GA G1 (X, + 2). GB : G. UfX, + Y), }. and Go G2 (X1 Y on each dataset. From the fact that GA is closer to the true MEC than Gc, it may seem that GA would always score higher. However, GA was the highest-scoring DAG 96% of the time, and Go 4% of the time. As expected, GB is never the highest-scoring DAG.
5

---

Algorithm 1: Less Greedy Equivalence Search (LGES)
Input: Data ~ P(v), scoring criterion S, prior assumptions (R. F), initial MEC Eo,
insertion strategy GetInsert in [GETSAFFINSERT, GETTONSERVATIVEISSRYY
Output: MEC of ((v)
E < Eo:
// allows initialisation if preferred by user
2 repeat
repeat
E E-&& E-E+ the highest-scoring DELETE(X,) T)
until score-increasing deletions exist;
repeat
E E++ f+ the highest-scoring TURN (X, Y, T)
until no score-increasing reversals exist; g < some DAG in E:
10
priorityLee < GETPRORTTYISSERTSS....... foreach candidates in priority do
12
[Xman, Ymaz mmaz) & -GelnnsertE,, G,D, S);
if (Xmazy Y many T maa) is found then
14
E 8-E+. INSERT( Xmaz> Ymary T Taa)):
15
break;
// no need to check lower priority
until score-increasing operators exist;
17 return 3
if P(v) is not Markov with respect to E, then for every 9 E, there must exist variables X, Y such that X Y Paς. This is unlike CONSERVATIVEINSERR where X, Y can not depend g. Strategy (SEFR) At given state with CPDAG &, pick an arbitrary DAG G E &. For each non-adjacent pair (X, Y) G, check if has higher score than G U {X + Y). so, discard all INSERT(X, Y, operators and continue to the next pair. Among all retained candidates, select the highest-scoring operator that results
score increase, if any.
Proposition 2 (Correctness of SAFEINSERT). Let & denote Markov equivalence class and let P(v) denote the distribution from which the data D was generated. Then, as the number of samples goes infinity, SAFEINSERT returns a valid score-increasing INSERT operator if and only if one exists.
Example 3. (Ex. 2 continued). Let g(1), G1. and G2 be as in Ex. Assume GES is at g(1) and INSERT picks the DAG 91 E. Then, G1 U (X1 + Y has a lower score than 91 since X1 II Pa in P(v), where Pa = {2}. SAFEINSERT thus does not consider any INSERT(X) Y, operators.
contrast, assume SAFEINSERT picks the DAG G2 E Then, Go U [X1 Y} has a higher score than G2. and SAFEINSERT may still consider INSERT(X,, Y, operators. However, CONSERVATIVELNSERYY will not consider any INSERT(X,, Y, *) operators, since INSERT(X,, Y, {2)), corresponding to 9, U (XI - Y). results lower score than (1)
Pseudocode for the above insertion strategies are in Algs. 4 and 5 these strategies, and show how both achieve substantial gains in accuracy and runtime over GES.
Later, in Sec. 5.1 compare
3.3 Learning with prior knowledge
In this section, we present another modification of the forward phase of GES; prioritizing edge insertions based on an expert's prior causal knowledge. The insight that underpins GGES -that we can apply any score- poore-increasing insertion suggests new way to incorporate such assumptions while still correcting them if contradicted by the data. We assume that we are given possibly misspecified causal model as a set of required and forbidden edges S = (R, F) that may be directed or undirected.
Initialization from prior assumptions. A natural strategy, which we refer to as GES-INIT, initializes the search to an MEC consistent with the assumptions, for e.g., by including all edges in R. and then proceeds greedily as in standard GES 2 This approach, an instantiation of GGES, is sound in the targe-sample limit (as a corollary of Thm. even when the assumptions are misspecified.
This empirically evaluated in [1] However, its conrectness not considered.

---

However, given finite samples, such initialisation may harm both accuracy and runtime. If the expert suggests adjacencies that don't exist the true MEC, GES-INIT includes them by default in the initialisation and may fail to remove them later. Moreover, such initialisation precludes the use of insertion strategies from Sec. 3.2 that would avoid introducing such excess adjacencies.
Guided search from prior assumptions. We instead propose strategy that uses prior assumptions to prioritize operators, and not to initialize the search. Specifically, for each non- con-adjacent pair (X, Y). we rank it into one of four categories based on the constraint set S (R, F) using the procedure GETPRIORITY INEPRISSTTYINSERRS only applied if they increase the score. For example, if SAFFINSERT finds no score-increasing insertions for the current MEC, then the remaining expert- apperrt-rovided edges in R (if any) are not consistent with the data, and will not be inserted. In contrast, GES- INIT inserts all edges by default.
INSERTS (Alg- Insertions for higher-priority adjacencies are considered first, but
we incorporate this prioritization scheme into novel algorithm, combining it with the search strategy of Sec. Sec. to enable a less greedy search. In Sec. 5.2 we empirically demonstrate the benefit of this prioritization based strategy.
Next, in Sec. 3.4
3.4 The Less Greedy Equivalence Search algorithm
Finally, we introduce the main result of this work: the algorithm Less Greedy Equivalence Search (LGES, Alg. D. We present three variants:
1. LGES-0 (Alg. 8), which modifies the insertion step of GES based on our insights in the previous sections, while using the same search strategy as GES in the deletion step,
2. LGES (Alg. D which is similar to (1) but additionally incorporates the XGES-O heuristic of prioritizing insertions before deletions 36.. and
3. LGES+ (Alg. 9. which is similar to (2) but additionally incorporates the XGES heuristic of forcing edge deletions and restarting the search [36]
As a corollary of Thm. I and Prop. 2. we can show that each LGES variant with SAPEINSERT recovers the true MEC in the sample limit, even given misspecified set of prior assumptions.
Corollary 1 (Correctness of LGES). Let & denote the Markov equivalence class that results from LGES (Alg. 7 initialized from an arbitrary MEC Eo and given prior assumptions S = (R, and let P(v) denote the distribution from which the data D was generated. Then, as the number of samples goes to infinity, E the Markov equivalence class underlying P(v).
Remark 1. While we only show that LGES with SAFEINSERT is asymptotically correct, LGES Since we only have partial guarantees on CONSER-
can also be run with CONSERVATIVEINSSEN VATIVEINSERT (Prop. C.I C.2). it remains open whether this variant of LGES is asymptotically correct.
4 Score-based learning from interventional data
While the previous sections address causal discovery from observational data, such data alone leaves many edges unoriented. Interventional data can resolve such ambiguities. In this section, we extend the LGES method with I-ORIENT, a score-based procedure for refining an observational MEC with interventional data. Unlike existing score-based methods, which are asymptotically inconsistent or computationally infeasible even in moderate-dimensional settings 24 58 our approach scales while preserving soundness.
we assume soft unconditional interventions, includ- special case. These set the distribution of a variable X to some fixed P" (x:). thereby removing the influence of its parents. Let I denote a family of interventional targets, ie., subsets I C V. with the empty intervention 0 E I producing the observational distribution. We observe data from distributions (PI(v))teI. As in the observational case, we assume there cxists DAG G such that these distributions are I-Markov (Def. A.7) and faithful to the corresponding intervention graphs (G)Iez, obtained by removing edges into any intervened variable V E 16
Background on interventions. Following (24], ing hard (do) interventions
3 PPeeddocdee and correctness results for LGES-O and LGES+ can be found in Appendix C
7

---

Algorithm 2: Z-ORIENT
Input:
Intervention targets I. data (DI)IeI ~ (PI(v))EEI, observational MEC scoring criterion S
Output: T-MEC of (PI()))EEI) foreach X E & and Y ne do
AS
E
SDI (V. x) SD. (y)
IEZ, XELVEI
if AS > 0 then
Orient edge X Y as X + E: Apply Meek's rules in & to propagate orientations 35
else if AS < 0 then
Orient edge X Y as
in :
Apply Meek's 's rules in & to propagate orientations
35
return 3
Just as observational data identifies an MEC, interventional data identifies an I-MEC, a smaller equivalence class encoding constraints both observational and interventional data [24 Def. 7].
Orientation procedure. To recover the Z-MEC, we introduce Z-ORIENT (Alg. 2}. which orients
undirected edges in the observational MEC using scores from interventional data. The underlying idea simple. Consider some undirected edge X in the observational MEC ε, where the ground perform
truth DAG is G". Say there exists intervention I containing X but not Y. When unconditional intervention in g" if and only if X and Y are marginally independent independence using scoring criterion? The key is to local consistency (Def. I compare graph G where Y has no parents to a graph G (X - Y). The former will score higher than the latter if and only if X IL Y in Pv()). This is precisely the test in line of I-ORIENT (Alg. 4
X, erase the causal influence of Pa X. So, Y is parent of X
P1(v). How can we check for marginal
Theorem 2 (Correctness of I I-ORIEET).. Let & denote the Markov equivalence class that results from I-ORIENT (Alg. D given an observational MEC Eg and interventional targets I, and let (PI(v))Ee denote the family distributions from which the data (Dı)ıez was generated. Assume that Eo is the MEC underlying Pv(v). Then, as the number of samples goes to infinity for each E I, & is the I I-Markov equivalence class underlying (PI(V))IEI.
Experiments
5.1 Learning from observational data
Synthetic data and baselines. We draw Fedōss-éény" graphs with variables and (1,2,3) .p edges
in expectation, denoted ER-(1, (1, 2,3) respectively). We most experiments for p up to 150, with additional experiments for p up to 250 in Sec. D.1.6) For each p. we sample 50 graphs and generate
linear-Gaussin data for each graph. Following [37]. we draw weights from 2d( 0.5) U [0.5, 2))
and noise variances from U( [0.1 0.5]). We obtain samples of size n E {103, 10a] via sempler [20]
We evaluate GES, XGES-O 36
XGES 36 LGES-O, LGES, LGES+ PC [54] and NoTears 611.
Results. LGES (both Safe and Conservative) significantly outperforms XGES and GES in runtime and
accuracy. We measure accuracy by Structural Hamming Distance (SHD) [56] between the estimated and true CPDAGs (Fig. 4a). as well as precision, recall, and Fl score (Fig. D.I.2). Furthermore, the less greedy variants of GES, XGES-O, and XGES all improve their respective original algorithms (Figs, [4b] D.I.I D.1.3). Of the GES variants, LGES+ (Conservative) the most accurate, whereas LGES (Conservative) is the fastest. CONSERVATIVEINSEER outperforms SAFEINSERT in accuracy, but both strategies yield similar runtime.
'All implementations in Python. tttps://gitthe www.co///aaaaa httm///aanammlllaage
GES variants implemented by modifying the code in
implementation in causal-lean -learn [6]] and NoTears implementation in causal-nex (5). Our GES implementations share as much code as possible.
We use
We do not use the optimized implementation of the operators proposed in [36] across any of our GES variants, study the effect of the search strategy independent of implementation.

---

LGES (Safe)
PC
GES
(Cons)
XGES
ER2
ER3
Safe
Cons
No knowledge ane
In
Prioniy
(Cons)
271
120
p-100
0-00
6R2
20.0
60
80
17.5
15.0
12.5
20
GES
XGES-0
XGES
GIES
0.25
0.5
0.75
10
10
Time
101
10a
10-1
10-2
6E5
XGES
0.25
0.5
0.75
Number variables
Family
Frection correct (ic)
(a) Observational data performance (h) Impact of less greedy insertion
(c) Impact knowledge
Figure 4: Performance of algorithms 50 simulated datasets from Erdōs-Rényi Rényi graphs with p variables. Lower is better (more accurate faster) across all plots. (a) LGES outperforms baselines in accuracy and runtime graphs with 2p edges in expectation, given 10 observational samples and no prior knowledge, (b) Less greedy insertion improves several GES variants on graphs with p 150 variables and 2p and 3p edges in expectation, given 10 observational samples (and n = 103 samples per intervention for GIES) and no prior knowledge. IGFSS-0, IGES, I.GES+, and LGGISS are the less greedy variants of GES, XGES-0, XGES, and GIES respectively. (c) Given prior knowledge in the form of 3m/4 required edges when the true graph contains m edges, LGES' prioritization strategy more robust to misspecification the knowledge than initialization with the same knowledge, given n 10s observational samples. See Sec. D for additional results.
To elaborate, LGES (Safe and Conservative) is an order of magnitude faster than GES. LGES (Conservative) is up times more accurate than GES, for instance, resulting in only x 30 incorrect edges on average in graphs with 150 variables and 300 edges in expectation. These comparisons also hold for LGES--0, the less greedy variant of GES (Figs. 46 D.I.I D.I.3). The difference in accuracy is due to excess adjacencies and incorrect orientations: missing adjacencies almost never occur (Fig. D.I.Ip PC, though the fastest algorithm, less accurate than GES for a 10a but performs best in the case of many variables and few samples (Fig, D.I.4). NoTears has much worse accuracy than other methods, e.g., average SHD 125 on graphs with 100 variables, though its runtime appears to scale better (Fig. D.1.I See Sec. D.I for additional results and discussion.
5.2 Learning with prior knowledge
Synthetic data and baselines. We study how conrectness of prior knowledge affects performance when data limited (n 10²) on ER2 graphs with 50 variables, with data generated as in Sec. 5.1 For true DAG G with m edges, edges as follows. We vary the fraction fc of the chosen m' edges that is 'correct', with c m' edges chosen correctly from those in G and the remaining chosen incorrectly from those not in G. We compare GES (with and without initialisation) and LGES (without initialisation, with initialisation only, and with priority insertion).
generate prior assumptions on m' E [m/2, 3m/43 required
Results. Fig. 4c summarizes results for m' 3m/4, with additional results in Sec. D.2 LGESS (Conservative) outperforms GES across all levels of prior correctness in terms of time and SHD.

---

First, we compare initialization with prioritization. When the knowledge is majority incorrect (fc {0.5, 0.25, 0.0)), the prioritization strategy significantly outperforms initialization in runtime and accuracy. When the knowledge is mostly accurate ( (fc E {0.75, 1}), initialization yields marginally better accuracy than prioritization. Second, we consider when knowledge improves performance. When the knowledge is largely correct (fc 2 75),, it marginally improves the accuracy of LGES with prioritization, and more visibly improves that of LGES with initialisation. However, as long as fc 2 0.5, knowledge significantly improves the runtime of LGES with prioritization. Thus, our prioritization strategy (Sec. 3.3) can leverage knowledge while being robust to misspecification.
5.3 Learning from interventional data
Synthetic data and baselines. We follow similar set-up as Sec. [5.1 with 104 observational samples and ER- (2 graphs. For a graph on p variables, we randomly con- struct Iz p/10 10 interventions and generate 10 samples for each. We compare GIES [24]; LGES run on observational data followed by
LGES (Sate) H-rrentt
LGIES (Sate) -+- LGES (Cona) - LCES (Coral JOnaat
ARI
Structural Hamming Diszance
80
80
60
60
20
I-ORIENT; GIES-O; and LGIES. LGIES-O and LGIES incorporate less greedy insertion into GIES; the latter also prioritizes deletions be- fore insertions.
25
50
75
100
125
150
25
50
75
100
125
150
30'
Results. All less- less-greedy algo- rithms are up to 10x faster than GIES (Figs. 46 5p. with LGIES (Conservative) being the fastest. LGIES (Conservative) is up to 1.5x more accurate than GIES, In general, all less greedy algorithms are more accurate than GIES with the exception of LGES (Safe) + ORIENT, which has competitive ac- curacy with GIES on ER-3 graphs but performs slightly worse ER- 2 graphs. While being the only combination known to be asymp- totically correct, LGES (Safe) + I- ORIENT is limited by the fact that it uses only observational data to learn the observational MEC, while GIES and LGIES additionally use interventional data to this end.
10
10
Time (s)
10
101
10f
10a
10-1
10
100 150
25
50
75
100
125
150
Number of veriebles (p)
Number of variables (p)
Figure 5: Performance of algorithms on 50 simulated datasets from Erdös Erdös-Rényi graphs with p variables and (left) 2p edges (right) 3p edges in expectation, given = 10 observational samples and Lower is better (more accurate faster) across all plots. LGIES significantly outperforms GIES.
10 samples per intervention (Sec. D.3
6 Conclusions
In this paper, we introduced family of less greedy algorithms for score-based causal discovery from observational and interventional data. Our core insight lies in new operator selection strategies, CONSERVATIVELNSERRTT and SAFEINSERT, that avoid inserting edges between variables for which the score implies a conditional independence. Building on these ideas, we developed LGES (Alg. [. which replaces GES' strictly greedy step with a more careful search. We proved that LGES with SAPEINSERT asymptotically recovers the true Markov equivalence class (Thm. I Cor. [ and showed that LGES can incorporate prior knowledge while remaining robust to misspecification in the knowledge. To extend these advancements beyond purely observational settings. we developed Z-ORIENT (Alg. [ Thm. 2 a theoretically sound and scalable score- based method for refining an observational MEC using interventional data. Across experiments on random graphs of varying sizes and densities, our less greedy strategies consistently improved both the accuracy and the efficiency existing GES-style algorithms (Sec. 5). The moral, there one, simple: even causal discovery, temperance is virtue.
10

---

Acknowledgements
This research is supported in part by the NSF, ONR, AFOSR, DoE, Amazon, JP Morgan, and The Alfred P. Sloan Foundation. We thank Jonghwan Kim and the anonymous reviewers for their insightful comments.
References
[1] Nicos Angelopoulos and James Cussens. Bayesian learning of Bayesian networks with in- formative priors. Annals of Mathematics and Artificial Intelligence, 54(1):53 98, November 2008. ISSN 1573-7470. doi: 10.10077510472--09999333 1 -09-933--
URL
[2] E. Bareinboim and Pearl. Causal inference and the data-fusion problem. Proceedings of the National Academy of Sciences, 11::7345-7352, 2016.
[3] Elias Bareinboim, Juan D. Correa, Duligur lbeling, and Thomas Icard. On Pearl's Hierarchy and the Foundations of Causal Inference, page 507-556. Association for Computing Machinery, New York, NY, USA, edition, 2022. ISBN 978 1450395861. URLhhtss:://do org/10
1145/3501714 3501743
[4] M. J. Bayarri, James O. Berger, Woncheol Jang, Surajit Ray, Luis R. Pericchi, and Ingmar Visser. Prior-based Bayesian information criterion. Statistical Theory and Related Fields, 3(1): 2-13, January 2019. ISSN 2475-4269. doi: 00.080024754229.201999 2019.1582126. URLphttps: 158211
/ ordoi.org//0.
Publisher: Taylor and Francis _eprint:
http://0...0r//11000000444444440
[5] Paul Beaumont, Ben Horsburgh, Philip Pilgerstorfer, Angel Droth, Richard Oentaryo, Steven Ler, Hiep Nguyen, Gabriel Azevedo Ferreira, Zain Patel, and Wesley Leong. CausalNex, October 2021. http:::tt:// http://.....ooguuuuuuuuaa.....aa hwt.a///.....aaaaacccsaaeeeee causalnex
[6] Alexis Bellot, Junzhe Zhang, and Elias Bareinboim. Scores for learning discrete causal graphs with unobserved confounders. Proceedings of the AAAI Conference on Artificial Intelligence 10430):10043-115111 Mar. 2024. doi: 10. 1601////a.ii...... v38110.28980 URL URL httph://ojs...... aaai
org/index.phrr phtppddee.pppppeepeeeeeeeee/e AAAI/ /At.////aaaaiceeeee///////
[7] Robert Castelo and Amo Siebes. Priors on network structures. biasing the search for bayesian networks. International Journal of Approximate Reasoning, 24(1):39-57, 2000.
ISSN 0888-613X.
doi: https://dol.org/10011111//3 (100)/0888886111090000011111 URI. https htwpe//dddeett.cccccccnccnceeeee htt.caaceee.ccc..ooc//c/ooaaaaaa
[8] David Maxwell Chickering, A transformational characterization of equivalent bayesian network structures. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI'95, page 87-98, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603859.
[9] David Maxwell Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res., 3(mul)):507-544, March 2003. ISSN 1532-4435. doi: 10. 10.116211524444031119777 URL https:t/tt/tttt org/ 10. 11111/1155244333218887777
[10] David Maxwell Chickering and Christopher Meek. Selective greedy equivalence search: finding optimal bayesian networks using a polynomial number of score evaluations. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI'15, page 21 1-19,, Arlington, Virginia, USA, 2015. AUAI Press. ISBN 9780996643108.
[11] David Maxwell Chickering, David Heckerman, and Christopher Meek. Large- learning of bayesian networks is hardard. J. Mach. Learn. Res., 5:1287-1330, December 2004. ISSN 1532-4435.
[12] Max Chickering. Statistically efficient greedy equivalence search. In Jonas Peters and David Sontag, editors, Proceedings of the 36th Conference on Uncertainly in Artificial Intelligence (UAI), volume 124 of Proceedings of Muchine Learning Research, pages 241-249, PMIR, 03-06 Aug 2020. URL
mlr pttppp/wss///ppppptppppppppttttt htt.eeess//12///cccccrri22222020 html

---

[13] Tom Claassen and Ioan G. Bucur. Greedy equivalence search in the presence of latent con- founders. In James Cussens and Kun Zhang. editors, Proceedings of the Thirty-Eighth Confer- ence Uncertainty in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pages 443-452. PMLR, 01-05 Aug 2022. URL htttps::/ppoceeedinngge .mlr
press/v180/ claassen22a. html
[14] Anthony C. Constantinou, Zhigao Guo, and Neville K. Kitson. The impact of prior knowledge on causal structure learning. Knowledge and Information Systems, 65(8):3385-3444 August 2023. ISSN 16. doi: 10.1007//10115-023-000 1007/s10115 023 01858-x
URL https://doi.. org/10
[15] Gregory F. Cooper and Edward Herskovits. A bayesian method for the induction of probabilistic networks from data. Mach. Learn., 94):309-337, October 1992. ISSN 0885-6125, doi:
10.1033/A110226444015522 URL http:p::::/aii..rrr//0.000//////
[16] Juan Correa and Elias Bareinboim. A calculus for stochastic interventions:causii effect identification and surrogate experiments. Proceedings of the AAAI Conference on Artifi- cial Intelligence, 34006):10033
Apr. 2020. doi: 10. vtl.aaaiiii0666656..... URL
https://ojs. aaai
www.aaaaaaaaaaaaaaaaaaaaaaaaaaaa org/
php/
[17] Atray Dixit, Oren Parnas, Biyu Li, Jenny Chen, Charles P Fulco, Livnat Jerby-Aronn, Ne- manja D Marjanovic, Danielle Dionne, Tyler Burks, Raktima Raychowdhury, Britt Adamson, Thomas Norman, Eric S Lander, Jonathan S Weissman, Nir Friedman, and Aviv Regev, Perturb-seq: Dissecting molecular circuits with scalable single-cell ma profiling of pooled genetic screens. Cell, 167(7):1533-1866.
December 2016. doi: 10. 10.1016fj.eel.2211.11..
[18] D. Dor and M. Tarsi simple algorithm construct consistent extension of a partially oriented graph. 1992. URL http:://rw..senattccccloool.a
org/ www.:/ucttta--ccisssetttttt--tto www.connnnsnttoieeee a----fa------aaaaaaeeee Mar--or-Taree
[19] Julien Dubois, Hiroyuki Oya, J. Michael Tyszka, Matthew Howard, Frederick Eberhardt, and Ralph Adolphs. Causal mapping of emotion networks in the human brain: Framework and initial findings. Neuropssychologia, 145:106571, 2020, ISSN 0028-3932. doi: https://doi.
1066/.neuupoychhoobe...........0 URL htRpsttts: : //www sciencedirect. www.rreetttceeeeeeeeeeeeeeeeeeee scc//scienn science/ articlee/p11500099323133300
The Neural Basis of Emotion.
[20] Juan L. Gamella, Armeen Taeb, Christina Meeizee-emll and Peter Bühlmann. Characterization and greedy learning of gaussian structural causal models under unknown interventions. arXiv preprint arXiv:22
14897, 1.8497 2022.
[21] Dan Geiger, David Heckerman, Henry King, and Christopher Meek. Stratified exponential families: Graphical models and model selection. The Annals of Statistics, 29(2):505 529, 2001. ISSN 00905364, 21688966. http:://t///ww..j
[22] Uzma Hasan and Md Osman Gani. Optimizing data-driven causal discovery using knowledge- guided search, 2024. URL httpsssss//// abs/ 05493
[23] Dominique M. A. Haughton. On the choice of a model to fit data from an exponential family.
The Annals of Statistics, 16 16(1):342-355, 1988. ISSN 00905364, 21688966. URL http
/ /www. www..jstor. org/ stt/s//abee2221441//
[24] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. J. Mach. Learn. Res., 13(1):2409-2444,
August 2012. ISSN 1532-4435.
[25] Yangbo He, Jinzhu Jia, and Bin Yu. Counting and exploring sizes of markov equivalence classes of directed acyclic graphs Journal of Machine Learning Research, 16679):2589-2699, 2015. http:/tt:://mml org/ wwtgg/apers//ee peoperr/vi6/he155. html
[26] David Heckerman and Dan Geiger. Learning bayesian networks: unification for discrete and gaussian domains. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI'95, page 274-284, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN 1558603859.
12

---

[27] A. Jaber, M. Kocaoglu, K. Shanmugam, and E. Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9551-9561, Vancouver, Canada, Jun 2020. Curran Associates, Inc.
[28] Hyunchai Jeong, Adiba Ejaz, Jin Tian, and Elias Bareinboim. Testing causal models with hidden variables in polynomial delay via conditional independencies. Proceedings of the AAAI Conference Artificial Intelligence, 39025):268113266222 April 2025. ISSN 2159-5399. doi: v39125. 34885
N.l16099aai..v331125. 334855. httt:tt:///e doi. org/ 10.
[29] Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Charac- terization and learning of causal graphs with latent variables from soft interventions. In H. Wallach, H. Larochelle, A. Beygelzimer, F. MAlcé-BBuc E. Fox, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, httpa///a.....lee/////////////// httpee//pppprr//////ieeee pdf
Inc., 2019. URL htttps::/proceeedinggg neurips. http//paa_fffssse/ cac0f1166.bb0000ff0000000fffff..
[30] Steffen L Lauritzen, A Philip Dawid, Birgitte N Larsen, and H. G. G Leimer. Independence Properties of Directed Markov Fields. Networks, 20(5):491-505, 1990. ISSN 10970037. doi: (1.002/net.2330200000
[31] Thuc Duy Le, Tao Hoang, Jiuyong Li, Lin Liu, Huawen Liu, and Shu Hu. A fast algorithm for high dimensional causal discovery with multi-core pes. IFFE/ACM Trans. Comput. Biol. Bioinformatics, 16(5): 1483--44444455 September 2019. ISSN 1545-5963. doi: 10.1 10.1109/TCBB. 2016.2591526. URL hattps://det 1t1.//////0//11111/711133
1109/TCEB 2016. 2591526
[32] Adam Li, Amin Jaber, and Elias Bareinboim. Causal discovery from observational and interventional data across multiple environments. In A. Oh, T. Naumann, A. Glober- son, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Informa- tion Processing Systems, volume 36, pages 16942-16956. Curran Associates, Inc., 2023. URL httpe://ppccoodngg....spsssspspp
neurips httpiipsscccpppp___rrieeee fileserrrffieeeeeeeeeeeeeeeeeeer ptt.leele//ppppr2////11110. 956caa77000022222aa66///bbbbbaa2
[33] Stephanie Long, Alexandre Piché, Valentina Zantedeschi, Tibor Schuster, and Alexandre
Drouin. Causal discovery with language models as imperfect experts, 2023. URL https
/aaxxiv.ogg/bbl htte//abs23307... 02390
[34] Christopher Meek. Causal inference and causal explanation with background knowledge. 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. ISBN 1558603859.
[35] Christopher Meek. Graphical Models: Selecting causal and statistical models. 1 1997. doi: 10. 1184/R1/22696393.vLL URL cmu www.//aticeess/teeeeeeeeeeeeeeee Graasiiiir/raaaaaaaaaa
[36] Achille Nazaret and David Blei. Extremely greedy equivalence search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intel- ligence, volume 244 Proceedings of Machine Learning Research, pages 2716-2745. PMLR, 15-19 Jul 2024. URL httpttss//prccccddnnngee mlr wwwpppees//vveee wwwp/////////e//./...a html
[37] Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the role of sparsity and dag constraints for learning linear dags. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc ISBN 9781713829546
[38] Ignavier Ng. Biwei Huang, and Kun Zhang. Structure learning with continuous optimization: A sober look and beyond. In Francesco Locatello and Vanessa Didelez, editors, Proceedings of the Third Conference on Causal Learning and Reasoning, volume 236 of Proceedings of Machine Learning Research, pages 71-105. PMLR, 01-03 Apr 2024. URL. htttps:/pproceedinggg mlr. wwwpssesssssee....p wwtee/vv3//// 22236//g24a... html
13

---

[39] Chris J. Oates, Jessica Kasza, Julie A. Simpson, and Andrew B. Forbes. Brief report: Repair of 2017. ISSN 10443983,
partly misspecified causal diagrams. Epidemiology, pp. 15315487. URL. wtt.hhtps///// //wp:////wwww// wwtp:www..oo....oo..oo..otttt..t stw.or.ogg/taable2666111..
[40] Rodney T. O O'Donnell, Lloyd Allison, and Kevin B. Korb. Learning hybrid bayesian networks by mml. In Abdul Sattar and Byeong-ho Kang. editors, Al 2006: Advances in Artificial Intelligence, pages 192-203, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-49788-2.
[41] Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo, CA, 1988.
[42] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, 2nd edition, 2009.
[43] Joseph Ramsey, Madelyn Glymour, Ruben Sanchez-Romero, and Clark Glymour. A mil- lion variables and more: the fast greedy equivalence search algorithm for learning high- dimensional graphical causal models, with application to functional magnetic resonance images. International Journal of Data Science and Analytics, 3:121-129, 2017. doi:
10.1007/s41060-016-000
btttstt::://dot /ttp::::///oo..r/11... 1007/ 00gp:0001007//11100001---0022220
[44] Garvesh Raskutti and Caroline Uhler. Learning directed acyelic graph models based on sparsest permutations. Stat, 7(1)=1183, 2018. doi: https://doi..rr//I/ 1002/sta4. 183.. URL e183 18a4.183.
htttps://omlineliirras witery.wwilyy wwwey. http://///aaaa/0..0000000
183
[45] Alexander G. Reisach, Christof Seiler, and Sebastian Weichwald. Beware of the simulated dag! causal discovery benchmarks may be easy to game. In Proceedings of the 35th International Conference Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
[46] Thomas Richardson and Peter Spirtes. Ancestral graph Markov models. The Annals of Statistics, 30(4):962 1030, 2002. doi: aos/1031689015
URL https: httg///ooorr///////// 10. 1214/
[47] Jakob Runge. Causal network reconstruction from time series: From theoretical assumptions to practical estimation. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28(7):075310, 07 2018. ISSN 1054-1500. doi: 10. 10.100631.0025550. 5025050
org/ org/10.10633 1063/1
[48] Karen Sachs, Omar Perez, Dana Pe' er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein-sin soinnii-ig networks derived from multiparameter single-cell data. Science, 308(5721): 523-529, 2005.
[49] Reuben A. Saunders, William E. Allen, Xingjie Pan, Jaspreet Sandhu, Jiaqi Lu, Thomas K. Lau, Karina Smolyar, Zuri A. Sullivan, Catherine Dulac, Jonathan S. Weissman, and Xiaowei Zhuang. A platform for multimodal in vivo pooled genetic screens reveals regulators of liver function. bioRxiv, 2024. doi: 10. 10. 10.110//024.1111..222222
URL BtLhttps::/ :/wps:///www.. biorxiv
wrgg/contentearrly//ee mataarlyyy22241111 /2211//////222222 11. 624217
[50] Richard Scheines, Peter Spirtes, Clark Glymour, Christopher Meek, and Thomas Richardson. The tetrad project: Constraint based aids to causal model specification. Multivariate Behavioral Research, 33(1):65-111) 117, 1998.
[51] Gideon Schwarz. Estimating the dimension of model. The Annals of Statistics, 662):461-46,, 1978. ISSN 00905364, 21688966. URL http:://wwx wttp///www.j.rr.ooo//o/.o/to/... wwrg/ssaable22958880
[52] Rajen D. Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3), June 2020. ISSN 0090-5364. doi: 10.1214/19-a0:18577 URL luttp://an doi. www.org//oooooooooooooo..o...o.. 10. 1214/19-11-/ AOS1857
[53] Peter Spirtes, Christopher Meek, and Thomas Richardson. Causal inference in the presence of latent variables and selection bias. In Proceedings of the Eleventh Conference Uncertainty Artificial Intelligence, UAI'95, page 499-506, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc ISBN 1558603859.
14

---

[54] Peter Spirtes, Clark N Glymour, and Richard Scheines, Causation, Prediction, and Search. MIT Press, Cambridge, MA, 2nd edition, 2000.
[55] Sofia Triantafillou and loannis Tsamardinos. Score based vs constraint based causal learning in the presence of confounders. 2016. URL http::/www/ itt.. cwwtechltc....... wew.ecc..eeceueeeeeeeeeee www/"fehardteeeee 044220/wwws//agaprs///aaaaaaaaaa ....fffffffff
[56] loannis Tsamardinos, Laura E. Brown, and Constantin Aliferis. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 65(1):31-78, October 2006.
ISSN 1573-0565. doi: 10.1007/s 10994-00----88--7 URL https://doi. 0ttp///00...rg/11.00000// 110994-006-68893
[57] 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. ISBN 0444892648.
[58] Yuhao Wang. Liam Solus, Karren Dai Yang, and Caroline Uhler. Permutation- based causal inference algorithms with interventions. In Proceedings of the 3 International Conference on Neural Information Processing Systems, NIPS' 17, page 5824-5833, Red Hook, NY, USA,
2017. Curran Associates Inc. ISBN 9781510860966
[59] Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs, December 2020. URL /tttp://ariv org/ 2012 09679 arXiv:2012.09679 [cs].
[60] Jiji Zhang. On the completeness of orientation rules for causal discovery in the presence latent confounders and selection bias. Artificial Intelligence, 172(166):873-1896 2008. ISSN 0004- 3702. doi: https://doi.org 10. wwwt://...o.......o.o.o..... 001. URL.tttp::/ww.ccieeecee www.:wwwwiiiiiicic....ctc...cce.
http:/cienne/rrricccc /ttp:///cc///////////00000000010
[61] Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. Dags with no tears: continuous optimization for structure learning. In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, page 9492-9503, Red Hook, NY, USA, 2018. Curran Associates Inc.
[62] Yujia Zheng, Biwei Huang. Wei Chen, Joseph Ramsey, Mingming Gong, Ruichu Cai, Shohei Shimizu, Peter Spirtes, and Kun Zhang. Causal-leamn Causal discovery in python. Journal of Machine Learning Research, 25(60):1-8, 2024.
15

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we clearly support our theory with assumptions and proofs and our empirical claims with clearly designed experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
16

---

Justification:
We discuss limitations of our interventional data approach, and demonstrate how our algorithm scales worse than some existing methods.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ten system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:[Yes)
Justification: Clear statements of theoretical results are provided in the main paper. Proofs are provided in the supplement.
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details are provided the appendix, with the broader experi- mental design provided in the main paper.
17

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-soneee open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We excited release the code we want people to use and build on our algorithm. Pseudocode is provided for all algorithms. We will additionally provide anonymized code the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. ctipss.cc/ublic//uui.e www.iiiccguieeeeieeeeeeeeeeeeeee
ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
18

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, these details are outlined in the main paper and provided more speci- ficity in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate
information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, error bars provided in the main paper; where limited in the main paper for legibility, they are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute details are provided in the appendix. We only CPU.
Guidelines:
19

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the code of ethics and do not find concerns related the three mentioned categories since our work is more in the line of basic research.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We present generic structure learning algorithm without direct path to particular negative applications. We discuss applications in some problems in biology and neuroscience, though these are still fairly theoretical.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
20

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not use generative models or scraped datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We credit the implementations we use and build upon.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cww com/datasets: has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Yes, documentation is provided alongside our code which we intend to release
publicly.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
21

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not use human subjects in this work.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
We do not use human subjects in this work.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We do not use LLMs as core method in this work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non standardd components.
Please refer to LLM policy for what should or should not be described.
22

---

Appendices
Contents
Background and related works
23
A.I
Detinitions and previous results
23
A.2
Related works
25
A.2.1
Learning from observational data
25
A.2.2
Learning with prior knowledge
26
A.2.3
Learning from interventional data
26
Discussion and examples
26
B. I
Design of Less Greedy Equivalence Search
26
B.2 Limitations of Less Greedy Equivalence Search
27
Extended example GES trajectories
28
C Proofs and pscudocode
28
Experiments
35
D.1
Learning from observational data
35
D.1.1
Synthetic data details for Experiment 5.1
................................
35
D.1.2
Further baselines and metrics for Experiment 5.1
................................
35
D.1.3
Precision, recall, and Fl score for Experiment 5.1
37
................................
D.1.4
Further experiments with varying edge densities
37
................................
D.1.5
Further experiments with smaller datasets
................................
38
D.I.6
Further experiments with larger graphs
................................
38
D.2
Learning with prior knowledge
39
D.3
Learning from interventional data
39
D.4
Real-world protein signaling data
40
Frequently Asked Questions
41
A Background and related works
A.1 Definitions and previous results
First, we provide definitions and results used in the main text.
Definition A.1 (d-separation 4T]. Given a causal DAG 9, a node on a path æ is said to collider if W has converging arrows into W in x, e.g., W +- W <- is said to be blocked by set if there exists a node W on π satisfying one the following two conditions: 1) W is collider, and neither W nor any of its descendants are in Z, W is not collider, and W is in Z. Given disjoint sets X, Y, and in G. Z is said to d-separate X from Y in G if Z blocks every path from node in X node in Y according the d-separation criterion.
Definition A.2 (DELETE operator, 9 Def. 13]). For adjacent nodes X, Y in E connected as either X + / or X Y, and for any H C NeC n Adjε the DELETE(X. X, Y, T) operator modifies & by deleting the edge between X and and for each 7" T, directing any undirected edges X as X + 7 and any Y - T as Y + T.
23

---

R2
RA
Figure A.1.1: Meek orientation rules for completing partially directed acyclic graphs
The properties and implementation of the TURN operator can be found in 24 Sec. 4.3), though the authors do not provide an exact definition we can reproduce here.
Definition A.3 (Decomposable scoring criterion [9] Sec. 2.3]). Let be a set data consisting of iid samples from some distribution P(v). A scoring criterion S is said to be decomposable if it can be written as a sum of measures, each of which a function only a single node and its parents, as
S D) = Σ (Ui
V.E
Each local score s(U;, pa depends only the values of V; and Pa, in D.
Definition A.4 (Consistent scoring criterion g Def. 5]). Let D be a set data consisting of iid samples from some distribution P(v). A scoring criterion S is said be consistent as the number of samples goes to infinity, the following two properties hold for any DAGs G, H:
1. If P(v) is Markov with respect but not H. then S(G,D) S(H, D).
2. If P(v) is Markov with respect to both G and H. but G contains fewer free parameters than
H. then S) > S),
Definition A.5 (Score-equivalent scoring criterion O See 2.3]). Let D be set of data consisting of iid samples from some distribution P(v). A scoring criterion S is said to be score-equivalent if, the number of samples goes to infinity, for any two DAGs G, H that Markov equivalent,
S(G, D) = S(H, D).
Definition A.6 (Soft unconditional intervention 24
Sec. 2.1]). soft unconditional intervention on set of variables X sets the value of each variable V- E X to an independent random variable U; from given of random variables U. The resulting distribution given by
Px(v)=
II P(u. pa.) Viex
II (w.) VEX
where (*())) denotes the distribution of U, E U corresponding to V; X.
Definition A.7 (Z-Markov property 24 Def. 7J). Let V be a of variables, a causal DAG over V, I family of interventional targets, and (Pr(v))Tez a corresponding family of interventional distributions. We say (PI(v))ıez satisfies the Z-Markov Property of if:
1. Each Pv(v) is Markov with respect to the interventional graph 97. and
2. For interventions I, J and variables V4 & IUJ, Pi(u; pa.) = Pa(u, pa;).
We let Mz(G) denote the set of all (Pr(v))rez that are T-Markov with respect to G. Two causal
DAGs G, H are I-Markov equivalent if Mr(9) = -M)
Meek orientation rules. In Fig. A.L.I we provide Meek's 's orientation rules used in Z-ORIENT to orient an I-MEC. These rules provide an algorithm for completing a PDAG to a completed PDAG. They are applied repeatedly to a PDAG until no eligible motifs exist.
Next, introduce some additional definitions and results that will be used in Sec. C
The skeleton of causal DAG G (denoted (G) is the undirected graph that results from ignoring the edge directions of every edge in G. A triplet of variables (X, Z, YY) in G is said to be unshielded
24

---

if (X, Z) and (Y, 2) are adjacent but (X,Y) Y) are not. An unshielded triplet is said to be a v-structuore (or unshielded collider) if it is oriented as X Z + in G. Theorem A.1 (Graphical criterion for Markov equivalence [57] Thm. IJ.. Two DAGs are Markov equivalent if and only if they have the same skeletons and same v-structures.
Based on the above characterization, obtain the CPDAG for the MEC corresponding to a DAG G. one adds an undirected edge for every adjacency in G; orients any v-structures according to G; then applies Meek's 's orientation rules to complete the resulting PDAG to CPDAG.
Definition A.8 (Global Markov property [T]. A probability distribution P(v) over a set of variables V is said to satisfy the global Markov property for a causal DAG if, for arbitrary disjoint sets X, Y, Z C V with X, Y * *0,
X Y X I1 Y| in P(v).
Let Nd denote the set of non-descendants of a variable X in g, i.e. variables in g (excluding X itself) to which there is no directed path from X.
Definition A.9 (Local Markov property 41)) A probability distribution P(v) over a set of variables V is said to satisfy the local Markov property for a causal DAG G if, for every variable X E V.
X IL Na Pa P(v).
Proposition A.1 (Equivalence of Local and Global Markov Properties [30, Prop. 4]). Let G be causal DAG over variables V. A probubility distribution over V satisfies the global Markov property for 9 if and only if it satisfies the local Markov property for G.
Definition A.10 (Covered edge
88 Def. 2)). An edge X - Y in a given causal DAG G is said to be
covered if Pay Pa J (X}.
Lemma A.1 (Covered edge reversal R. Lemma. 1J.. Let 9 be any causal DAG containing the edge X + Y and let G' be the DAG that is identical to G except it instead contains the edge Y - X. Then, G' is a DAG that is Markov equivalent to 9 iff the edge X + is covered in G.
Theorem A.2 (Transformational characterization of Markov equivalent graphs E Thm. 2)). Let G. G' be pair of Markov equivalent causal DAGs. Then, there exists a sequence of covered edge reversals transforming G to G'.
Theorem A.3 (Chickering- Meek theorem 9 Thm. 4)). let G and H. be a pair of causal DAGs such every d separation that holds in H also holds in G. Then, there exists a sequence of edge additions and covered edge reversals transforming G to H. such that after each reversal and addition, G is DAG and every d-separation that holds H also holds in g.
A.2 Related works
A.2.1 Learning from observational data
Algorithms for causal discovery fall into three broad categories: constraint- score-based, and hybrid. bosstraint-based algorithms like PC (54) and the Sparsest Permutations (SP) algorithm [4] learn the true MEC using statistical tests for whether the chosen type of constraints, typically these approaches
conditional independencies, hold in the data. A challenge
improving the
accuracy of conditional independence tests, for e.g. in controlling type I error [52]. Score-based algorithms such as GES 34 use scoring criterion that reflects fit between data and graph, typically in the form of a likelihood plus a complexity penalty. Hybrid algorithms such max-min (56) use combination of the two approaches, for e.g., first learning the skeleton using constraint-
hill climbing
method then orienting edges in the skeleton using score. There is no general claim about the relative accuracy of these methods; we refer readers to (56) for an extensive empirical analysis, who found, for instance, that GES outperforms PC in accuracy across various sample sizes [56] Tables 4, 5]
Commonly, causal discovery algorithms struggle with scaling in high-dimension settings. This has motivated variants such as Parallel-PC [31] and Fast Greedy Equivalence Search (FGES) 4 which offer faster, parallelized implementations of the algorithms. While FGES offers an additional heuristic over GES, i.e., not adding any edge X - Y in the forward phase if X, Y are uncorrelated in the data, this heuristic is not theoretically guaranteed to recover the true MEC. More recent continuous-optimizatio based approaches such as NoTears [I] are principle more scalable, but lack theoretical guarantees and show brittle performance even in simulated settings [38 45).
25

---

A.2.2 Learning with prior knowledge
Causal discovery with background knowledge is well-studied problem [14. Such background knowledge may be provided by domain expert or even a large language model 13
Perfect background knowledge. Many algorithms under this umbrella, such as tiered- FFred-FCII [50]. the K2 algorithm [15] and Knowledge-Guice Guided GES [22]. assume that the background knowledge is correct, i.e., consistent with the ground truth. They use this knowledge to constrain the search, for e.g. by never inserting ieer-foriidden edges. If the expert's background knowledge is imperfect, such methods necessarily fail to recover the true MEC. Even if the knowledge is perfect, it is unknown whether these methods will output the true graph; for e.g., in Knowledge-Guus Guided GES [22], restricting insertions no longer guarantees reachability of an MEC with respect to which the given data is Markov in the forward phase, as in GES.
Misspecified background knowledge. The constraint-based approach in (39 allows some mis- specification in the expert knowledge the form of missing or excess adjacencies but not incorrect orientations. However, their approach does not guarantee recovery of the true MEC. Certain score- based approaches treat knowledge about edges a 'soft' prior 0 4 7 26 40 to guide the search, but lack theoretical guarantees on the output graph. One exception with theoretical guarantees is the Sparsest Permutations (SP) algorithm [44], which can initialize the search to an ordering over variables provided by expert.
A.2.3 Learning from interventional data
Observational learning algorithms can only learn a causal graph up to its observational Markov equivalence class (MEC). The MEC is the limit of what can be identified from observational data without further assumptions. However, MECs can often be large and uninformative for downstream causal tasks 25] Interventional data can help significantly refine observational MECs 2241. and becoming increasingly available, for e.g., in biological settings due to advances in single-cell technologies [17
4 This has motivated the design of algorithms for causal discovery from observational and interventional data such as the score- score-based Greedy Interventional Equivalence Search (GIES) [24] and the CI-based Interventional Greedy Sparsest Permutations (I-GSP) (58). However, in [58] it was shown that GIES is inconsistent, i.e.. not guaranteed to recover the true interventional MEC in the sample limit. I-GSP is asymptotically consistent, but being permutation- based, struggles to scale in high- high-dimensional settings.
B Discussion and examples
B.1 Design of Less Greedy Equivalence Search
In this section, we elaborate on certain design choices made in the LGES algorithm.
Choice of DAG in SAFEINSERT. As specified in Def. Alg. 5 a given MEC &, SAFEINSERT chooses some DAG G from E to perform its check for conditional independence. In theory, any any procedure for choosing DAG from an MEC suffices. In our implementation. simple polynomial-tmme algorithm for converting a CPDAG to DAG presented in (18) and used in the original GES 9
use Alg.
Another possibility is the polynomial time algorithm for uniform random sampling of DAG from an MEC [59]. We leave investigation of DAG choice to future work.
Backwan ward phase of LGES. LGES only modifies the forward phase of GES, while keeping the backward phase intact. Since score-decreasing INSERT implies independence under some condition- ing set (Prop. D. discarding all X Y insertions when single score-decreasing INSERT(X, Y, T) operator is found promotes more robust edge insertions, i.e., between variables that are not found to be conditionally independent. This significantly reduces false adjacencies in the learned graph (Fig. I.I.I. One may ask, why not use an analogous strategy in the backward phase, discarding all X Y deletions when a single score-decreasing DELETE X, Y, T)) operator is found? This is because one score-decreasing deletion implies dependence given one conditioning set, not given any conditioning set. However, a true Y adjacency implies dependence given any conditioning set. So, skipping all delctions due to one score decrease would lead to many false adjacencies and
26

---

compromise soundness. A true adjacency would imply that all X Y deletes are score vooe-decr..,ing, so LGEE/GGES will not apply any of them. Experiments support this: false non -onaadjccsscees are rare (Fig. D.I.I
Contrast with PC algorithm. There is a surface-level similarity between LGES and the PC algorithm [54]. The PC algorithm begins with a complete graph, then removes edges between variables for which it finds some separating set. In particular, for adjacent variables X, Y in the current graph G. it iterates over all subsets Z S Adjx U Adjy to find some Z such that X TL Y Z. If X, Y are non-adjacent in the ground -ruth graph, then the PC algorithm is guaranteed to find Z which separates them.
LGES, on the other hand, starts with an empty (or user-provided) graph. It then avoids inserting the edge X + Y if it finds a set separating X and Y. However, LGES only searches over restricted space of separating sets. CONSERVATIVEINSERT checks if X IL Y Pay for any G in the current MEC. SAPEINSERT checks if X TL Y Pay for a fixed & in the current MEC. There may exist set Z separating X and Y that does not equal Pay for some G in the current MEC. LGES may not find this Z, and thus insert an edge between X and Y. In this way, it differs from the PC algorithm.
The advantage of LGES is that it does not require conducting any scoring operations beyond those which GES already conducts. On the other hand, an approach which iterates over all possible separating sets of X and Y would require significantly more scoring operations. Still, future work might consider the theoretical guarantees and empirical performance of such a score-based approach.
B.2 Limitations of Less Greedy Equivalence Search
Causal sufficiency. In this work, we assume that the underlying system is Markovian, i.e. no two observed variables have an unobserved common cause. This is also known as the causal sufficiency assumption. While this assumption is standard in causal discovery, it can be violated in practice. In settings with unobserved confounders, i.e., non-Markovian settings, the equivalence class of graphs that can be identified is typically even larger (and hence more uninformative) than in the Markovian case. One reason for this is that two variables may be non-ad adjjeent in the true graph while still being inseparable by any set due to the existence of an inducing path between them (57] Def. 2]. As result, performing causal inference from equivalence classes of non- Mar-Moakovian graphs is challenging.
Still, there has been work causal discovery in non- Markovann settings. Constraint- based approaches include the FCI algorithm [53 60) and its interventional variants (27 29 32), guaranteed to recover the true equivalence class in the sample limit. While there has been progress towards score- based approaches 6 13
46 55). finding algorithms that are asymptotically correct remains an open
problem.
There is a fundamental theoretical challenge to generalizing our approach to the non-Markovian setting. GES relies on two useful properties of Markovian DAGs. First is the local Markov property 30 of such DAGs, allowing for a locally consistent scoring criterion (Def. [T. Second are the transformational characterizations of two Markovian causal DAGs G1 and G2 when (a) G1 and G2 encode exactly the same d-separations (Thm. A.2) and (b) (a) G1 encodes a subset of the d-separations encoded in G2 (Thm. (A.)). A 'transformational characterization' is procedure whereby 91 can be transformed into S2 by a sequence of single-edge changes that satisfy certain criteria. The transformational characterization of (a) has been generalized non-Markovian causal DAGS (60). Moreover, there exists a local Markov property for non- Markovann causal DAGs, as well as an efficient algorithm test condition (b) (88 However, it remains open problem to fully recover (b) in the non- Man-Markviinn setting.
Other assumptions. In this work, we assume we are given distribution that is Markov and faithful with respect to some causal DAG. This is standard assumption causal discovery, often justified by the fact that the set of distributions that are Markov but not faithful with respect to given DAG has Lebesgue measure zero. Moreover, we assume only that the given distribution is Markov with respect to some causal DAG, we can never rule out the true DAG being the fully connected DAG. Still, there has been work on relaxing the faithfulness assumption, giving rise to the Sparsest Permutations algorithm [44].
27

---

Y
Y
OY
Z
Z
X1
X2
X1
X2
X
X
X
X
true MEC g"
current MEC
u + 2
u
partially reproduced for convenience. GES is given a distribution P(v) whose true MEC is represented by Ex (left). GES currently at MEC &, evaluating which INSERT
Figure B.3.1: Figs.
operator to apply next. Each INSERT corresponds to picking some G E E and adding some edge to it.
We further assume in this work that we are given a scoring criterion that decomposable and consistent. This does not strictly mean we make parametric assumptions. Existing scores such as BIC satisfy these criteria as long as the model is a curved exponential family 19 23). This includes multinomial (discrete) and liussrn models. For continuous data, the GaussiGG assumption can be violated in practice. In this case, one can discretize the data before using it for causal discovery, as in (88.. However, since the parameter space of multinomial models is quite large. and information is lost during discretization. it would be valuable future work to investigate scores for other models of continuous data.
B.3 Extended example of GES trajectories
Finally, we return to our explanation of the two trajectories GES might take in Ex.
Fig.
Example B.1. (Ex. continued), Recall that GES is given distribution P(v) whose true MEC is Ex (Fig. B left). GES currently the MEC ε, evaluating which INSERT operator to apply. Each INSERT operator corresponds to picking some DAG G E & and adding some edge to it. One such operator corresponds picking 91 E &, and adding the edge X1 + Z to it. Another such operator corresponds to picking 92 E &, and adding the edge X, + Y to it. Both operators, shown in Fig. B result in score increase by local consistency (Def.
I since Z J.. Xi Pa MEC E* than
and Y V X1 Pay in P(v). Although 91 UX, - Z looks "closer' to the G2 U + Y, when tested empirically, the latter often scores more than the former (Ex.2) (2).
Moreover, even in the sample limit, the consistency (Def. A.4) of the scoring criterion does not guarantee that G2 U (X1 + } will score lower than G1 local consistency of the consistency only allows us to compare graphs when P(v) is Markov with respect to at least one of them; however, P(v) is not Markov with respect to G2 U [X; [X; + Y) 91 U {X1 - Z}. Local consistency (Def. I does not let us compare these graphs either, since they differ by more than an edge addition. Therefore, GES may move either to the MEC of G1 U (X, - Z) (as in 7ı, Fig. 2 or to the MEC of G2 U (X1 > Y) (as in 72, Fig. 2). It is unknown a priori which operator is the highest-scoring.
[X + Z}. Neither the global nor the provide an immediate guarantee for which will score higher. Global
C Proofs and pseudocode
In this section, we provide proofs, additional results, and pseudocode for the algorithms of the main paper.
Theorem T (Correctness of GGES). Let & denote the Markov equivalence class that results from GGES (Alg. 3 initialized from an arbitrary MEC & and let P(v) denote the distribution from which the data D was generated. Then, as the number of samples goes to infinity, & is the Markov equivalence class underlying P(v).
Proof. The proof is similar to that of 99] Lemma 9, 10]. First, we will prove the correctness of GGES with the teraardttuninggbaaee
phase order.
Forward phase. First, we show that P(v) Markov with respect the MEC E' resulting from the forward phase of GGES. Let & be any DAG in E'. By assumption, since GeTOPERATOR ATOR does not find any valid score- soore-inceesiigg INSERT operators, there exists no such operator. Since there exist no
28

---

score-increasing INSERT operators, the local consisteney of the scoring criterion (Def. D implies that for every X E G and Y E Nd X IL Y Pax. Otherwise, if we had some X E G and Y E Nd such that X y. Y Pak. the INSERT(Y, X, x) operator corresponding to G U UU + }} would result in a score increase. Since P(v) is faithful to some DAG, satisfies the compusition axiom of conditional independence [41] if X Y Pa for every Y E Nd then X IL Nd Paa- Since this is true for every X, P(v) satisfies the local Markov property of g. By the equivalence of the global and local Markov properties (Arop.[A.I), this means every d-separation in g implies a corresponding CI in P(v). Thus, P(v) is Markov with respect to G and hence to Er.
Turning phase. NexI, we show that P(v) is Markov with respect to the MEC E" resulting from the turning phase of GGES. The turning phase starts with E", output by the forward phase. We have shown that P(v) is Markov with respect to g'. By construction, each TURN operator applied to the current MEC in the backward phase results in a score increase If any operator resulted in an E" with respect to which P(v) is not Markov, the consistency of the scoring criterion A.4 implies that it would decrease the score. Therefore, P(v) must be Markov with respect to E".
Backward phase. Finally, we show that P(v) is both Markov and faithful to the MEC & resulting from the backward phase of GGES. The argument that P(v) is Markov with respect to E is similar to that of the turning phase above. It remains to show that P(v) is faithful to E. Let Ex be the true MEC underlying P(v). Since P(v) is both Markov and faithful with respect to E and P(v) is Markov with respect to e, every d-separation in E must also hold in m.. Then, by the Chickering- MMek theorem (Thm. ). for any 9 & and 7 E., there exists a sequence of covered edge reversals and edge additions that transform H to G. If this sequence only contains covered edge reversals, then H and G are Markov-equivalent (Lemma. A.I), and we are done. Otherwise, let the last edge addition in this sequence add the edge X - Y. resulting in the DAG g'. Since G' can be transformed to 9 by sequence of covered edge reversals, they Markov equivalent, and have G' & (Lemma. A. Moreover, since this sequence of transformations includes only covered edge reversals and edge additions, and ('v) Markov with respect to H. P(v) is also Markov with respect G' (X + Y (by Lemma. A covered edge reversals and additions do not create additional d-separations). By the consistency the scoring criterion, G' {X - Y} has higher score than G' E & since the former has fewer parameters. The corresponding DELETE operator thus results in score increase, and by assumption, GETOPERATOR is guaranteed to find some score-increasing deletion in this case. Thus, we have contradiction.
Next, we will prove the correctness of GGES without the phase structure, i.e., when GETOPERATOR returns a score-increasing INSERT or DELETE operator if one exists. The proof is similar to the previous case. GGES terminates at an MEC & only when GETÖPERATOR finds no score-increasing INSERT or DELETE operator. By assumption, this implies no such operator exists, If no score- increasing increasing INSERT operator exists, by the same argument as for the forward phase above, the given P(v) must be Markov with respect to E. Given that P(v) is Markov with respect to &, and, furthermore, no score- score-increasing increasing DELETE operator exists, then by the same argument as for the backward phase above, the given P(v) must be both Markov and faithful to E.
Let E denote an arbitrary CPDAG and let P(v) denote the distribution from which the data was generated. Assume, as the number of samples goes to infinity, that there exists a valid score-decreasing INSERT(X, Y, T) operator for E. Then, there exists a DAG G E E such that (1) Y La X Pay and (2) Y IL X Pay in P(v).
Proposition] 1
Proof. The score change of a valid INSERT(X, Y, T) corresponds to picking a DAG g E E and comparing S(G, D) with S(g U (X- - YJ. D). By local consistency (Def. 1. i y X Paς then the score must increase. By contrapositive, must be a non-descendant of Y for g U (X - Y} be a DAG, Y La X Pa in g.
have Y JL Pay in P(v). Moreover, since X
We provide the following guarantee for LGES Alg. Drnn with CONSERVATIVELNSEN (Strategy Proposition C.1 (Partial guarantee on CONSERVATIVE instead of SAFEINSERT in the forward phase. Let
Let LGES* denote the variant of
LGES (Alg. D that uses CONSERVATIVEINSEER denote the equivalence class that results from the forward phuse of LGES initialized to an arbitrary MEC Eo, let P(v) denote the distribution from which the data was generated, and let Ex be the true MEC underlying P(v). Then, as the number of samples goes to infinity.
29

---

1. skellE") S skellE)
2. For any unshielded triplet (X, Z, Y) E E", either X, Y are adjacent in & or (X, 2, Y) is a collider in E" if and only if is a collider in E.
Proof. For any variables X, Y adjacent E", since P(v) is faithful to Ex, X, Y are not independent in the data conditional on any set Z S V. Hence, for any 9 E &, X JAY Pay. Therefore, we always have (() < (g [X + Y)) for any 9 E & such that X E Ndy, and all valid INSERT(X, Y, operators will result in score increase. Hence, CONSERVATIVELNSFERT will consider all such operators. Since & is local optimum of the score, any variables that are adjacent in E" must also be adjacent in &. Therefore, skel(E*) S skel(E).
Then, consider some unshielded triplet (X, Z) Er. Since skel(E*) C skel(E), (X, Z) and (Y, 2) must be adjacent in E. If (X, Y) are also adjacent in E, we are done. Otherwise, we have an unshielded triplet ZY) E E. Assume (X, Z, Y) is collider in E Since CONSERVATIVELN SERT finds no score-increasing INSERT operators for &, and X, Y are non-adjacent in &, must be the case that 3g E & such that Y E Nd and X Ll Y Pax or X E Ndf- and X JL L Paς. Without loss of generality, assume it is the former. Since (X, Z, Y) is collider in E X J. Z in P(v) for any set Z containing Z. Therefore, it must be the case that Z & Pa Hence, g contains the edge X -> Z. Since Y E Nd this further implies that 9 contains the edge Y + Z. Therefore, (X, Z, Y) is collider in G and hence E.. Next, assume that (X, Z, Y) is collider in finds
E. Then, Z & Pax g and Z & Pay for all G E. As before, since CONSERVATIVELNSER no score-increasing INSERT operators for E, and X, Y are non-adjacent in E, must be the case that 3G E & such that Y E Nd& and Y | Pay or X Nd and X IL Y Paς. Then, conditioning Z is not needed to separate X, Y in P(v), which implies that (X, Z, Y) is also collider in m".
We give the following condition, sufficient to guarantec that CONSERVATIVEIINSER returns score-inereasing INSERT operator when one exists. Proposition C.2 (Conditional guarantee on CONSERVATIEINNSERTY, Let & denote a Markov equiv- alence class and let P(v) denote the distribution from which the data D was generated.
Assume the following holds.
Assumption. Let G, H be two DAGs such that some d-separation encoded in G does not hold H. Then, there exists a pair of variables X, non-adjacent in G with Y E Nd& such that for every G' Markov-equivalent to G with Y E Nd X K.Y Pax in H.
Then, the number of samples goes to infinity, CONSERVATIVEIISER returns a valid score- increasing INSERT operator if and only if one exists.
Proof. Let E" indicate the true MEC underlying P(v). If there exists valid score-increasing INSERT operator for the current state ε, then P(v) is not Markov with respect to E. Since P(v) faithful to E", this implies that there exists some d-separation encoded
that does not hold in E". By the assumption, this implies that there exists X, Y non-adjacent in & such that for every G in E with Y E &d X Ya Y Pa in Ex and hence X K. Y Pa in P(v). Therefore, every INSERT(Y, X, operator results a score increase for Then, CONSERVATIVEIN is guaranteed to find score-increasing INSERT. The reverse direction follows by construction, since CONSERVATIVEINSERR enumerates only valid INSERT operators and returns one only it increases
the score.
As corollary of the above and Thm. we can also show that LGES with CONSERVATIVEI instead of SAFEINSERT is guaranteed to recover the true MEC in the sample limit, the assumption in Prop. C.2 holds. We leave the correctness of this assumption open.
30

---

Proposition 2 (Correctness of SAFEINSERT). Let & denote Markov equivalence class and let P(v) denote the distribution from which the data D was generated. Then, as the number of samples goes to infinity, SAFEINSERT returns a valid score-increasing INSERT operator if and only if one exists.
Proof. Assume there exists a valid score-increasing INSERT operator for the given MEC E. Then, P(v) is not Markov with respect E. Hence, P(v) is not Markov with respect to the 9 E & chosen by SAFEINSERT. By the equivalence of the global and local Markov properties (Prop. A.I). this implies that there exists X E G such that X If Nd Pax. Since P(v) is faithful to some DAG, it satisfies the composition axiom of conditional independence [41]; hence, there exists some Y E Nd such that X _L Y Pax. By the local consistency and decomposability of the scoring criterion, we have P. xXX, Pax x (YY)). Then, SAFEINSERT will find the valid score-increasing
INSERT(Y, X, T) operator corresponding to 9 U ( - X}. The reverse direction is similar. If SAFEINSERT outputs some (x, YY T), this implies it has found some X E G and Y E Nd such s(X, Pax) s(X, Pa U(Y)), and hence X f Y Pa This implies that P(v) is not Markov with respect to 9 and hence E, and there exists a valid score-inereasing INSERT for The INSERT output by SAFEINSERT is valid score-increasing operator by construction.
We provide pseudocode for the GETSAFEINSERT procedure in Alg. GETSAFEINSERT generalizes S NFEEINERTT; instead of searching for valid INSERT across all non-adjacencies in E, searches for a valid INSERT in a subset of the non-adjacencies in &, given by the condidales set. This enables the use of the prioritisation scheme of GETPRIORITY/NSERTS.
Let priorityList be the list of sets of (Alg. 66) given a Markov equivalence class and prior assumptions S = (R. F). Then, the union of all sets of edges in priority List is equal the set of variable pairs (X,Y Y) that are non-adjacent in E.
Proposition C.3 (Correctness of GETPRIORITYINSERTS,
edges output by GETPRIORITY
Proof. This follows from the fact that GETPRIORITYINSERR loops over all non-adjacencies in E, and any adjacencies not determined by S are added to priorily Lisl on line 10
Corollary C.1 (Correctness of LGES-0). Let & denote the Markov equivalence class that results from LGES-O (Alg. 8) with SAFEINSERT, initialised from an arbitrary MEC &g and given prior assumptions S = (R, F)) using SAFEINSERT, and let P(v) denote the distribution from which the data D was generated. Then, as the number of samples goes to infinity, & is the Markov equivalence class underlying P(v).
Proof. This follows from Prop. 2 Prop. C.3 and Thm. In the forward phase, if P(v) is not Markov with respect to the current MEC 3, SAFEINSERT will find some score-increasing IN- SERT(X,Y, T)Prop, 2 Since (X,Y) must be in some set in the priority list returned by GETPRIOR- ITYINSERT (Prop. C.3 some call to GETSAFEINSERT will find a score-increasing INSERT operator. Therefore, each forward step is guaranteed to find valid score-increasing INSERT operator, if it exists. In the backward phase, since LGEES-0 enumerates all valid DELETE operators at each step, it is also guaranteed find a valid score- score-increasee increasicn DELETE operator when if one exists. Thus, LGES-0 terminates only when there are no score-increasing operators for the current MEC, As such, LGES-0 satisfies the conditions of GGES (Alg. 3 and its correctness follows from Thm.
Corollary [Corrcttnss of LGES). Let E denote the Markov equivalence class that results from LGES (Alg. with SAFEINSERT, initialised from an arbitrary MEC Eo and given prior assumptions S= (R, F), and let P(v) denote the distribution from which the data D was generated. Then, the number of samples goes to infinity, & is the Markov equivalence class underlying P(v).
and Thm. I When LGES terminates, there exists no score-increasing deletion for the current MEC & by construction. By a similar argument to Cor. C.1 we can further show that there exists no score-increasing insertion for the current MEC E. Thus, LGES satisfies the conditions of GGES (Alg. (3 and its correctness follows from Thm.
Proof. This follows from Prop- 2, Prop.
Corollary C.2 (Correctness of LGES+), Let & denote the Markov equivalence class that results from LGES+ (Alg. 8) with SAFEINSERT, initialised from an arbitrary MEC En and given prior assumptions S (R, F)) using SAFEINSERT, and let P(y) denote the distribution from which the
31

---

Algorithm 3: Generalized Greedy Equivalence Search (GGES)
Input: Data PVV), initial MEC &, scoring criterion S, initial MEC Eg, list of phases phases in {[fforwrdd' "backward"), ['any"]]
Output: MEC P(v)
E <- Epi
2 foreach phase in phases do repeat
OPERATE(X, T) <- D
E+ OPERATE((X
until no score-increasing operators exist;
7 return 3
data D was generated. Then, as the number of samples goes to infinity, & is the Markov equivalence class underlying P(v).
Proof. The correctness of LGES (Cor. implies that the MEC obtained on line I of LGES+ is the highest-scoring MEC. Therefore, the condition on line of LGES+ will never be true, and LGES+ outputs the same MEC as LGES.
Theorem 2 (Correctness of Z-ORIENT), Let & denote the Markov equivalence class that results from I-ORIENT (Alg.) 2 given an observational MEC & and interventional targets I, and let (PI(v)) (v))) denote the family of distributions from which the data (Dı)ıez was generated. Assume that & is the MEC underlying (v).. Then, as the number of samples goes infinity for each E I the Z-Markov equivalence class underlying (P (PI(v))IET.
Proof. Let Ex denote the true I-MEC underlying (PI(V))TET. Since only orients undirected edges in Eg, and & has the same skeleton and v-structures as E" also has the same skeleton and v-structures as E*. Next, we show that for every variable pair (X,Y) adjacent in Ex (and hence E) for which there exists some E I with X e L, I, this edge is directed in both & and E*, and moreover, has the same direction in both.
Consider some edge (X, Y) E E" for which there exists I E I such that X E I,Y & I. Then, (X, Y) directed and I-essential for every such I, (D) > SD, x).
[24 Cor. 13]. We will show that E" contains - X and only
then X + Y in every DAG E E*. This implies that in every G E E" there are no directed paths from Y since all edges into X removed in 97. there are directed paths from X + in 9.- Since Pi(v) is Markov with respect to Gr. this implies X IL Y in Pi(v). Let H. denote the empty graph over variables V. Since X IL Y in Pi(v). by the local consistency of the scoring criterion. H. has a higher score than H U {X - Y). By the decomposability of the scoring criterion, this implies SD, (y) > SD, (y. .). Since I was arbitrary, this must true for each I E I such that X I, Y &
Assume 8" contains Y +
- X in & and hence GT. Moreover,
Assume that sD, (v) > sD, (y.z) x) for some I E I. Let H. denote the empty graph over variables V. Then, since sD, (8) SD, (y. 2), the decomposability of the scoring criterion implies that H has higher score than H HUH [X + YJ. If J. X in Pv(v), ), the local consistency the scoring criterion would imply that H has lower be true that 1 X in Pr(v). Since Pr(v) is faithful to 97 for some G E E*, this must imply that X, Y are non-adjacent in Gp. Since X, Y are adjacent in E*, and X E I, & I, this implies that G and Ex contain Y + X. This further implies that if the supposition is true for some I E I with X I,Y Y & must be true for all of them.
than H {X
Y). By contrapositive, it must
The argument to show that 8x contains X + if and only if for every with X E I,Y & I, SD, (v) < $D, (y.z) z) is analogous.
Moreover, since these statements are true for each E I, they are also true when comparing the sum over sum over all such I: i.e., Σ SD, (v) vs Σ SD, (v.
32

---

Any edge that is directed in & is either (a) already directed in &p. in which case it is similarly directed in E", (b) oriented on lines 4 or 7f T-ORIENT, in which case it is similarly directed in E by the above argument, or (c) oriented by the Meek rules lines or g in which case it is consequence of edges directed due to (a) and (b), in which case it is also similarly directed in E.. Moreover, the edges directed in Ex are also due to (a) their being directed in Eg. (b) there existing some I E I which contains exactly one endpoint that edge, or (c) their being a consequence by the Meek rules of these two edge types. Therefore, edges directed in E" are also similarly directed in &, since Z-ORIENT directs each such edge type. We thus have that =
Algorithm 4: GETCONSERVATIVLINSRRY
Input: MEC &, DAG G E &, data D ~ P(v), edge insertion candidates condidates, scoring
criterion S
Output: A valid score-increasing INSERT operator for & from the adjacencies in candidates, or if none is found.
ASmaz f- -0;;
(Xmazz Ymax: T maz))= 0:
foreach (X, Y) in candidates do
X E Nd and sYY, Paf) < s(Y Pay U (X)) then
AS t 00; (X,Y, T. + 0:
foreach valid T Nof Adj do AS sY, Adj
isSS > AS,y then
AS AS;
11
(X, Y, T) + (X,Y,T;;
12
else if AS < 0 then
A SSp ry 00;
14
break:
15
AS AS then
16
AS mar f -ASpyi
(Xmary Y Ymaz; T Tmaz) + (8, 8, T): return (Xmary Y mazi Tmaz)
17
Algorithm 5: GETSAFEINSERT
Input: MEC E, DAG G E E, data D P(v), edge insertion candidates candidates, scoring
criterion S
Output: A valid score-increasing INSERT operator for & from the adjacencies in candidates, if none is found.
A Smaz f- -0;
2 (Xmaz, Xman: T Tmax) + 0:
foreach (X, Y) in candidates do
if X E Nd and s(Y, Paς s(Y. Pa U (X}) then
foreach valid T Nef Adj do
AS sYY, (Ne JUTUP -s (N
AS > A then
AS max AS;
(X (mmax Ymaxs T Imaz) t (X,Y, Y)T);
10 return (X (Xmax; y Ymaz," T Tmaz)
33

---

Algorithm 6: GETPRIORITYINSERIS
Input: MEC E. prior assumptions (R.F) F)
priority List < (0 x 4);
foreach (X, Y) non-adjacent
do
if X +Y E R then
Add (X, Y) to priorityList()):
// required
else if Y - X R then
Add (X, Y) to priority[is([2:
// weakly required
else if X + Y F or X - Y E F then
Add (X, Y) to priorityList44]:
// forbidden
else
10
Add (X, Y) to priorityList33] return prioritylist
// ambivalent
Algorithm 7: PDAGTODAG
Input: MEC &
E' {-;;
while there exists undirected edge in & do
Choose a vertex V in such that (i) V is a sink node in E" (no outgoing directed edges), and (ii) all undirected neighbors of V are pairwise adjacent in El (form clique);
foreach undirected edge (U, V) in do
Qrient (U, V) as U V in E;
Remove V from E
return 3
Algorithm 8: Less Greedy Equivalence Search-0 (LGES-0)
Input: Data D P(v), scoring criterion S. prior assumptions (R, F), initial MEC Eo, insertion strategy GelInserl in [GETSAFEINSERT GETCONSERAATVELLNEERY Output: MEC & (vv)
< Eo:
// allows initialisation if preferred by user
repeat
G - some DAG in E;
// forward phase
priorityList + GETPRIORITYINSERTISEE...
foreach candidates in priority do
(Xmony Y Ymar: T Tmaa) GetInsert(E D, S):
if (Xmaz, Ymnns T mmax) is found then
E E-E+ INSERTT max, Y Ymans T maa);;
break:
// no need to check lower priority
10 until no improving insertions exist;
repeat
12 E + E+ highest-scoring TURN(X,Y, YYT); until no score-increasing reversals exist;
// turning phase
14 repeat
E+ highest-scoring DELETE (EEEETE(XXX)) (X,Y Y,T): 16 until no score-increasing deletions exist;
15
backward phase
17 return
34

---

Algorithm 9: Less Greedy Equivalence Search+ (LGES+)
Input: Data ~ P(v), scoring criterion S, prior assumptions (R. F), initial MEC &o, insertion strategy GetInsert in {GETSAFFINSERT, CETCCNNERAATVEENSERYY
Output: MEC of ((v)
& < LGES(D, S, Eo, Ep, GetInsert);
2 D f- all deletions valid for E;
while D do
(X (Xmaz; Y Ymaz: T man < highest-scoring deletion D;
E' t & DELETE(XMent Ymaz: T man);
E' f LGGS (D, S. Eg, GetInsert, Xmaz: Ymax):
// LGES" is modified version of LGES that excludes edge insertions between the given X,Y
if S(E' D) > S(E, D) then - 8
D all deletions valid for E:
else
11
- D {(Xmaz; Yman: Tmax))
12
return E
D Experiments
shared compute cluster with 2x Intel Xcon Platinum 8480+ CPUs (112 cores total, 224 threads) at up to 3.8 GHz, and 210 MiB L3 cache.
Compute details. All experiments
D.1 Learning from observational data
Baseline details We ran the PC algorithm using significance level a 0.05 for conditional independence tests, with the null hypothesis of independence. Since NoTears often outputs cyclic graphs, we post-processed the output graph by greedily removing the lowest-weight edges until was acyclic, following (37. This was done so that we could convert the output to a valid CPDAG for comparison with other algorithms. We ran NoTears with default parameters from causalnex library, which uses weight threshold of w O; note that performance may vary depending on the choice parameters, particularly the weight threshold and the acyclicity penalty parameter. However, since the implementation of Tears very compute-heavy, parameters. For fair comparison, we implemented all GES variants, including XGES, LGES, and GIES, by modifying the code provided by [20] Discrepancies in runtime of XGES between results and the results of (36] may result from the latter's 's use of an optimized C++ implementation, which includes an implementation of the search operators that they used in XGES but not in GES.
were not able to tune these
D.1.1 Synthetic data details for Experiment 5.1
For the results shown in Fig. 4 we draw Rénys graphs with p variables and {2p edges expectation (ER2), for p E [5, 10, 15, 20, 25, 50, 75, 100, 1503. For each p. we sample 50 graphs and generate
data for each graph. Following [37], draw weights from u([2, -0.5] U [0.5, 2)). ) In some cases, the resulting weight matrix was (almost) singular, which case each of weights was & normalized. We draw noise means from (/ 1) and noise variances
from (0.1,, 0.5)). We obtain n = 10a samples per dataset via sempler 20
D.1.2 Further baselines and metrics for Experiment 5.1
In Fig. D.I.I
we present additional baselines and accuracy metrics for the setting Sec. 5.1 including the particular types of structural errors (excess adjacencies, missing adjacencies, incorrect orientations). As in the case SHD, LGES outperforms other algorithms across these metrics, with CONSERVATIVEINSERY outperforming SAFEINSERT.
'https://github http://tttubb.ccomaaaaaage////// com//uaaggmeelllges
35

---

NoTears LGES (Safe)
XGES-0
LGES-O (Safe)
LGES-O (Cons
LGES (Cons)
-+-
LGES+ (Safe)
LGES+ (Cons)
ER2
Structural Hamming Distance
175
150
125
40
100
75
0
Excess adjacencies
30
90
10
25
75
100
125
150
160
1.25
140
1.00
Missing adjacencies
120
0.75
0.50
80
0.25
60
0.00
0.25
20
0.50
0
50
75
100
125
150
25
50
75
100
125
150
35
30
30
25
Incorrect orientations
25
20
20
10
50
100
125
150
0
50
100
125
150
Number
Number variables (p)
Figure D.1.1: Structural error of algorithms 50 simulated observational datasets from Erdös-Rényi graphs with p variables and 2p edges in expectation, given 10 samples and no prior knowledge (Sec D.1.2). Lower better (more accurate faster) across all plots. (Left) Common baselines. GES-style algorithms outperform PC and NoTears in accuracy. (Right) GES variants. LGES-0, LGES, and LGES+ are the less greedy variants of GES, XGES-0, and XGES respectively. Each less greedy algorithm improves on its greedy counterpart in accuracy.
36

---

Nolears XGES
PC
GES
LGES (Safe) LGES (Cons)
LGES+ (Cons)
LGES-0 (Safe)
XGES-0 0
LGES+ (Safe)
LGES-0 (Cons)
1.2
1.2
5R2
6P2
BR2
1.0
1.0
0.8
0.8
F1 51.000
Peeciion
0.6
0.6
0.4
0.4
0.2
0.2
25
50
75
100
150
25
50
75
100
125
150
25
50
100
125
150
1.15
1.15
1.15
1.10
1.30
Scone
1.00
1.00
0.95
0.95
0.90
0.90
0.85
0.80
0.80
0.75
0.75
25
50
100
125
150
Number variables
150
Number variables
75
150
Figure D.1.2: Binary classification accuracy of algorithms on 50 simulated observational datasets from Erdös-Rény: graphs with p variables and 2p edges in expectation, given 10 samples and no prior knowledge (Sec. D.I.3). Higher is better across all plots. An MEC is said to contain an edge (x, if contains either X Y-Y or X + Y (but Y - X). (Top) Common baselines. GES-style algorithms outperform PC and NoTaa in accuracy. (Bottom) GES variants. LGES-0, LGES, and LGES+ are the less greedy variants of GES, XGES-O, and XGES respectively. Each less
greedy variant improves on its greedy counterpart in accuracy.
The behaviour NoTears more variable. It misses significantly more adjacencies than all other methods-approxite approximately linearly many the number of variables. It also includes many more excess adjacencies than the other algorithms up to = 50, after which the number of excess adjacencies begins decline, ultimately approaching that of LGES for p 150; however, this could be explained by the increasing number adjacencies that are also missed by NoTears. We show in the next section how, result, the Fl score of NoTears is low across all graph sizes (Fig. D.1.2).
D.1.3 Precision, recall, and F1 score for Experiment 5.1
Next, in addition to structural error, we evaluate accuracy by considering causal discovery as a binary classification task. We use the task definition provided in [36]: MEC is said contain edge (X, Y) if it contains either X - Y or X Y (but not Y - X). The results are shown in Fig. D.1.2 For graphs with < 20 nodes, we find that GES and LGES have similar F1 scores. They both outperform PC, which in turn substantially outperforms NoTears. For >> 20, LGES+ (Conservative) dominates, followed by LGES (Conservative). For large p. LGES (Conservative) achieves a substantially higher Fl score than GES and other algorithms except LGES+ For instance, for p = 150, LGES (Conservative) achieves an F1 score just under 0.95, whereas GES's F1 score slightly under 0.85.
D.1.4 Further experiments with varying edge densities
In Fig. D.1.3 we provide results for select baselines on Erdós Rédōs-Rééyi graphs with p variables and {1,3)- edges in expectation following the set-up in Experiment 5.1 The relative performance of algorithms similar to the ER2 case (Fig. D.I.I). though PC and GES achieve similar accuracy on ER3 graphs. LGGSS+ (Conservative) is the most accurate overall, achieving 2x less structural error than GES on ER and ER3 graphs. For instance, graphs with 150 variables and 450 edges in expectation, LGES (Conservative) achieves SHD 40, and LGES+ (Conservative) x 30. All less
37

---

PC
LGES-O (Safe)
LGES (Safe)
LGES+ (Safe)
GES
LGES-0 (Cans)
LGES (Cons)
LGES+ (Cons)
ENT
E7R3
175
120
Structural Hamming Distance
150
125
100
60
75
40
50
20
25
-20
0
25
50
75
100
125
150
0
25
50
75
100
125
150
10a
10a
10a
10a
10a
Time
10a
101
10-1
10a
10
10a1
10
10-2
50
75
100
125
150
Number of variables (p)
25
50
75
100
variables
Figure D.1.3: Performance of algorithms 50 simulated observational datasets from Erdōs-Rényí graphs with p variables and (left) p edges and (right) 3p edges in expectation, given n = 10 samples and prior knowledge (Sec. D.1.4. Lower is better (more accurate faster) across all plots. See Fig. for graphs with 2p edges in expectation. LGES (Conservative) is the fastest GES variant across edge densities, whereas LGES+ (Conservative) is the most accurate overall algorithm across edge densities.
greedy algorithms are faster and more accurate than GES, with LGES-0 and LGES being up 10x faster.
D.1.5 Further experiments with smaller datasets
To investigate performance in the small-sample setting, we conduct experiments with n = 10x for ER2 graphs with p {10, 25, 50, 1003 variables. The results are summarized in Fig. D.1.4
As in previous experiments, LGES (Safe and Conservative) outperforms GES runtime and accuracy across all graph sizes, with CONSERVATIVE Interestingly, the PC algorithm outperforms LGES for the case of p = 100, suggesting PC's usefulness for settings where the number of samples is small compared with the number of variables.
yielding higher accuracy than SAFEINSERT.
D.1.6 Further experiments with larger graphs
We scaled up Experiment 5.1 to graphs with p {175, 250} variables. We LGES (Safe and Conservative) and PC. We were unable to continue running XGES, GES, and NoTears due to time and compute constraints; for instance, GES took over 10 seconds without terminating for 175 for a single trial. The results are summarized in Table D.I.I
LGES both with SAFEINSERT and with CONSERVATIVEINSERRT is substantially more accurate (in terms of SHD structural error of PC. While PC is faster than LGES, LGES is much faster than GES, taking only Rx5-6 minutes for p 175 and 1-5-20 minutes for p 250. Recall that for p = 150, GES was already approaching runtime of 1 seconds (>2 hours) (Fig. 4a
score) than PC, with IONSERVATTIVEINSRRTT achieving less than half the
38

---

GES
LGES (Safe)
LGES (Cons)
PC
ER2, n =1000
10a
ER2, =1000
Distance
80
10a
60
10
40
109
20
10
25
50 75
100
25
50
75
100
Number of variables
Number variables
Figure D.1.4: Performance of algorithms on simulated observational datastets from Erdös-Rényi graphs with variables and 2y edges in expectation, given the smaller dataset of 10 samples and no prior knowledge (Sec D.1.5p. In terms of accuracy, L.GES (Conservative) outperforms other algorithms except for the case of p 100, when PC is more accurate.
Metric
Method
175
p 250
SHD
LGES-0 (Conservative)
42,04 + 11.51
83.06 14.42
LGES (Conservative)
39.457 10.44
82.80 14.73
LGES O (Safe)
70.62 11.68
135.24 + 14.31
LGES (Safe)
67.65 + 12.31
133.22 1 14.07
PC
91.34 = 17.17
166.20 + 24.34
Runtime
LGES-4 0 (Conservative)
315.83 73.23
989.37 205.53
LGES (Conservative)
326.44 73.166
1019.13 1 198.12
LGES 0 (Safe)
337.45 78.43
1058.11 + 221.32
LGES (Safe)
348.23 80.57
1095.71 + 209.10
PC
29.20 9.50
85.67 + 23.52
Table D.1.1: Performance of algorithms (mean + std) on 50 simulated observational datasets from large Rénós graphs with p variables and 2p edges in expectation, given = 10 samples and no prior knowledge (Sec. (Sec.D.1.6) Lower is better (more accurate faster) across all metrics. Other algorithms are omitted as they exceeded the 10at second bound on runtime for these graph sizes, prohibiting repeated trials. Among these, PC the fastest, makes twice as many structural errors as LGES (Conservative).
D.2 Learning with prior knowledge
In Fig. D.2.1 we present more detailed plots of runtime and SHD for the setting in Sec. 5.2 including
background knowledge comprising m' m/2 and m' 3m/4 edges for ground truth graph with m edges. Resutls for mn' m/2 follow a very similar trend to those with m' 3m/ /4 discussed in Sec. 5.2 Initialisation outperforms prioritization in LGES when the expert knowledge is mostly
correct ffc 2 0.75), but prioritization does better otherwise.
D.3 Learning from interventional data
In this section, we further discuss the performance algorithms given interventional data in Sec. 5.. We observed that LGES (Safe and Conservative) followed by I-ORIENT has higher SHD from the ground truth than LGIES, Safe and Conservative respectively. We hypothesize that this is because, in our experiments, L.GES only uses 10t observational samples during the MEC learning phase. uses the interventional samples only to orient edges using T-ORIENT. In contrast, LGIISS uses 10 + k 10 samples in the MEC learning phase given & interventions, since it uses interventional
39

---

GES
LGES (Sefe)
LGES (Cons)
knowledde
Priority
ER2, 3/2/4 prior edges
40
40
Structural Hamming Distance
30
30
20
10
0.25
0.5
0.75
1
0.25
0.5
0.75
10a
Time
10a
109
0.25
0.5
0.75
0
0.25
0.5
0.75
Fraction (fc)
Fraction correct (fc)
Figure D.2.1: Performance of algorithms 50 simulated observational datasets from graphs with 50 variables and 100 edges in expectation given n = 10 samples (Experiment 5.2 Sec. D.2 Lower is better (more accurate faster) across all plots. We vary the correctness of the prior knowledge on the x-axis; higher fc indicates a higher fraction of knowledge that is correct. (Left)) Algorithms are given m' = m/2 required edges knowledge, for true graph containing m edges, (Right) Similar, but with m' = 3m /4. LGES' prioritization strategy is more robust to misspecification in the knowledge (S 75% correct) than initialization with the same knowledge
data throughtout learning, and generate 10 interventional samples per target. Moreover, since choose & p/10 10 (where is the number of variables), LGIES is making use of much more data than LGES for learning the MEC. Although GIES is known not be asymptotically correct (58), this further motivates research into an asymptotically correct causal discovery algorithm that can make use of interventional data throughout learning.
D.4 Real-world protein signaling data
Sachs dataset. We compare GES and LGES on a real-world protein signaling dataset [48]. The observational dataset consists of 853 measurements of 11 phospholipids and phosphoproteins. We compare the output of our methods with the gold-standard inferred graph [48 Fig. 3)), containing 11 variables and 17 edges. The dataset is continuous but violates the Sinea-GGusssan assumption We test our methods both on the original continuous dataset and on discretized version (3 categories per variable corresponding to low, medium, and high concentration) from the bnlearn repository
Results.
The learned graphs provided in Fig, D.4.1 All algorithms output the same MEC and thus have the same accuracy in both settings. With discrete data, each algorithm had an SHD edges from the reference MEC, all of which were missing adjacencies. With continuous data, each
"nttps://www. bnlearn. haaaa/c//meeeerr///cccaaooo
hhttps://wwx bnlearn. caarm..commbboott com/book-crc--eed
40

---

Raf
Mek
Raf
Mek
PIP2
PIP2
PKC
PKC
Plcg
PKA
Erk
Plcg
PKA
Erk
Jnk
Jnk
Akt
Akt
PIP3
P38
PIP3
P38
(a) Continuous data
Discretized data
Figure D.4.1: Comparison between the reference MEC and the learned MEC for = 853 observa- tional samples from the Sachs protein- soigaiinig dataset [48]. For both continuous and discretized data, the three algorithms (GES, LGES (S (SAFEINSERT) and LGES (CONSERVATIVELNSERY) return same MEC, so only one learned graph is shown per panel. Green solid lines indicate edges correctly recovered by the algorithms. Blue solid lines indicate edges misoriented by the algorithms. Black dashed lines indicate edges missed by the algorithms.
(a) Continuous data: nine edges are missed and two misoriented: Jnk - Pkc and P38 - PKC, both undirected in the reference MEC. (b) Discretised data: nine edges are missed and none are misoriented.
algorithm had an SHD of 11 edges from the reference MEC, 9 of which were missing adjacencies and of which were incorrect orientations.
E
Frequently Asked Questions
Q1. What is the difference between score-based and constraint- causal discovery? Answer. Constraint-based and score-based approaches to causal discovery solve the same problem but in different ways. Constraint-based approaches such as PC (54) and Sparsest Permutations [44) use statistical tests, usually for conditional independence. to learn Markov equivalence class from data. Score-based approaches such as Greedy Equivalence Search I 35 instead attempt to maximize a score (for e.g., the Bayesian Information Criterion BIC (5I) that reflects the between graph and data. There no general claim about which of these methods is superior; we refer readers to [56] for an extensive empirical analysis, who found, for instance, that GES outperforms PC accuracy across various sample sizes [56] Tables 4, 5].
Q2. thought causal discovery was only one problem, but it seems the paper claims to be solving three different tasks: observational observational learning, interventional learning, learning with prior knowledge. Can you elaborate on these tasks (why they are different, how they relate, etc.)?
Answer: The most well-studied problem in causal discovery that of learning causal graphs from only observational data. However, algorithms for this task have few limitations. Firstly, they are computationally expensive and often fail to produce quality estimates of the true Markov equivalence class from finite samples. This motivates using prior knowledge in the search to produce better quality estimates the true Markov equivalence class and do so faster. Secondly, algorithms for learning from observational data only identify Markov cquivalence graphs, since this is the most informative structure that can be learned from observational data. However, MECs can be quite large, and thus uninformative for downstream tasks such as causal inference. When interventional data is available, more edges in the true graph become identifiable. This motivates using interventional data to identify a smaller and more informative interventional Markov equivalence class- the task of interventional learning. When no prior assumptions interventional data available, these tasks collapse to observational learning.
Q3. If GES is asymptotically consistent, why bother to consider LGES?
Answer. While GES guaranteed to recover the true Markov equivalence class given infinite samples, faces two challenges. First, computational tractability: structure learning
41

---

is an NP-hard problem, and GES commonly struggles to scale in high- -igeeniiensio settings. Second, data is often limited in practice, which results in GES failing recover the true MEC. LGES improves on GES in both of these aspects; it is to 10 times faster and 2 times more accurate (Experiment5..) Moreover, while GES and LGES can both incorporate prior assumptions to guide the search, LGES is more robust to misspecification in the assumptions (Experiment (52))
Q4. How well does LGES scale?
Answer. LGES can scale to graphs with hundreds of variables and is up to 10 times faster than GES (Sec.p) [.I. Both variants of LGES (Safe and Conservative) terminate in less than 20 minutes hours on graphs with 250 variables (Sec. (.1.6) and have substantially better accuracy than other baselines (including PC and No NeTears). D.1.6p. LGES also outperforms these baselines in settings with dense graphs (Sec. (.1.4).
Q5. LGES may be asymptotically correct, but how well does perform with finite samples?
Answer. We conduct an extensive empirical analysis of how LGES performs compared with baselines in saaite-sampleeeee settings. Both variants of LGES (S AFEINSERT and CONSERVA- TIVEINSERT) have substantially better accuracy than GES, PC, and NoTears in experiments with n = 10* samples and up to 500 variables (Experiments 5.1 D.I.. For instance, in graphs with 150 variables and 300 edges in expectation, LGES with CONSERVATIVELN. SERT only makes =30 structural errors on average, which is twice accurate as GES, which makes z/60 structural errors. LGES also outperforms GES in smaller sample settings (n E (500, 1000}) (Experiment D.1.5)
Q6. What is the difference between SAFFINSERY and CONSERVATIIVEINSERR?
Answer. LGES can use either the SAFEINSERT or the CONSERVATIVEINSSR strategy to select INSERT operators the forward phase; both result in improved accuracy and runtime relative to GES. We show that LGES with SAFEINSERT is asymptotically guaranteed to recover the true MEC (Cor. D. However, it remains open whether the same true of LGES with CONSERVATIEIINERR though we provide partial guarantees (Prop. C. C.2 Both strategies result in similar runtime, though CONSERVATIVEINSERRY consistently has greater accuracy than NSERT across our experiments (Sec. 5 D)
Q7. How is causal discovery with prior knowledge different from initializing a causal discovery task to the hypothesized model?
Answer. Causal discovery with knowledge is the more general problem of using possibly misspecified prior knowledge in the process of causal discovery to aid the search. Initializing the search to tentative model one way to achieve this. However, initialization is not robust to misspecification in the assumptions and can result in worse runtime and accuracy than our approach of guiding the search using prior knowledge (Sec. 3.3 Experiment 5.2)
Q8. What is the difference between Greedy Interventional Equivalence Search (GIES) 24 and LGES + Z-ORIENT?
Answer. GIES and LGESS are both score-based algorithms for learning from a combination of observational and interventional data. However, LGES has few primary advantages over GIES. First, LGES with SAFEINSERT is guaranteed to recover the true interventional MEC (Cor: [ Thm. 2 in the sample limit whereas GIES is not [58]. Second, both variants LGES are up to 10 times faster than GIES, and LGES with CONSERVATIVEINSE
has accuracy competitive with GIES (Experiment (.3). However, LGES uses interventional data to only to orient edges in learned Markov equivalence class (in the I-ORIENT procedure, Alg. 2 whereas GIES uses a combination of observational and experimental data throughout. We additionally introduce LGIES, which incoporates less greedy insertion into GIES and is thus both faster and more accurate than GIES (Experiment) 5.3).
Q9. Can your work be combined with other causal discovery algorithms?
Answer Several components of our approach are modular and can be combined with other causal discovery algorithms. For one, other algorithms in the GES family like FGES 43 and SGES [12 can be easily modified use the SAFEINSERT or CONSERVATIVEINSERYY strategies that we introduce; simple extension would investigate the resulting changes in accuracy and runtime. For another, the Z-ORIENT procedure can be used to refine the observational MEC output by any causal discovery algorithm (not necessarily LGES) using interventional data.
42


Reviews:
[{"review_id": "McGyeKxjaO", "reviewer": "Reviewer_Bizy", "summary": "It is a known practical issue that the GES algorithm may often produce denser graphs than truth with finite samples. This is partly because when an edge is added in the forward phase, only a single check of score increasing is performed. When this added edge is incorrect, the chance for it to be deleted in the backward phase is often small.\n\nTo deal with this issue, this paper proposes the algorithm \"Less Greedy Equivalence Search\" (LGES). Instead of adding an edge whenever a score increasing is obtained, LGES avoids adding edges even with increased scores whenever it implies **some (other)** conditional independences. Two variants of the insertion steps, named \"Conservative Inserts\" and \"Safe Inserts\" are proposed, one more aggressive with partial guarantees, and another with full guarantee.\n\nFurther, extensions to incorporate prior knowledge (even when some priors can be misspecified) and interventional data are provided.", "questions": "/", "limitations": "/", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n1. The problem to tackle is quite relevant -- the practical issue of often-denser results given by GES indeed needs to be addressed.\n\n2. The key motivation is clear and natural: in each step of the progression, it doesn't have to be the best score to be moved to. As long as the score is increasing it is a valid move. This principle leaves with space to strategically choosing among all candidates to get a balance between greediness and robustness.\n\n3. The running examples used throughout is clear and helpful.\n\n\n**Weaknesses:**\n\n1. The implication of score decreasing to incorrect adjacency (Proposition 1) is sound and useful. **But is it complete (seems no)?** In other words, does the score decreasing in Proposition 1 capture **all** (or just some) possible conditional independence patterns that leads to non-adjacencies? Also, do the two insertion variants capture all what can be captured by Proposition 1? If the answers are no, the authors may need to justify why such heuristics is good enough in avoiding false adjacencies.\n\n2. **The claim for speed-up needs more justification.** Intuitively, such more robust decision for adding edges comes with more tests: instead of just testing between X and Y given Y's current parents, now all possible neighbor sets T need to be tested (e.g., in conservative strategy). Then, why is LGES finally faster? Is it because that less edge is inserted and the graph in progression is sparser? Some kind of complexity analysis is expected.\n\n3. **The backward phase (and the optional turning phase) is not optimized accordingly.** Intuitively the dual operations of choosing stable (not necessarily the best) neighbors can be applied to the backward phase to avoid false non-adjacencies. This also makes the whole algorithm more self contained and symmetric. I am curious why the authors didn't implement that. Is it because that it will usually hurt GES's performance?\n\n4. **The contributions on dealing with interventional data and prior knowledge seem a bit irrelevant.**\n   - For the interventional data, when one treats the experimental domain index as an additional root variable, the whole discovery method becomes nothing but to run plain GES (or any constraint based algorithms) on all variables including the domain index. Under this, I cannot see clearly why the authors need to separate this as a specific contribution. Or, are there any more specific optimization made to algorithmic procedure for interventional data?\n   - For incorporating prior knowledge, the idea of seeing prior knowledge as priority constraints instead of hard initialization is interesting. (Though it is still worth discussing whether data or prior knowledge should be prioritized, or should be customizable to the users). Could the authors confirm whether this idea is newly proposed in this paper, or it is also already used in some existing works? Usually how do other score based variants incorporate background knowledge?\n   - Overall, the technical discussions regarding these two aspects are too short in the main body. For example, the very important algorithm \"GETPRIORITYINSERTS\" is deferred to the appendix. And similarly many other references are deferred (e.g., Defs. A.3, A.4, A.5), making hyper links not work in main body. More detailed analysis of these two contributions are expected. They are now too vague.\n\n5. **Many existing literature on GES are ignored.** There are many existing GES variants aiming to address different aspects of issues. For example, \n   - \"Statistically Efficient Greedy Equivalence Search\" (http://proceedings.mlr.press/v124/chickering20a/chickering20a.pdf), \n   - \"Fast GES\" (https://www.ccd.pitt.edu/wp-content/uploads/2018/10/FGES1c-user-documentation-5_21_2016-sample-size.pdf; this one, together with the point above that interventional GES is nothing different than plain GES, make the claim on \"the first ... for learning from interventional data that can scale to ... more than a hundred node\" suspicious), \n   - \"Extremely Greedy Equivalence Search\" (https://proceedings.mlr.press/v244/nazaret24a.html; this is cited in the paper but not compared), etc.\n\n   Could the authors please have a subsection reviewing those existing variants of GES, and in the experimental section, compare with them all? This is important since the purpose of this paper is for practical gain.\n\n6. **The SafeInsertion strategy needs some more elaboration:**\n   - \"nd_Y^G\" seems undefined?\n   - Is it enough to pick up only one arbitrary DAG from the CPDAG, or should we iterate all DAGs (to find the highest score and to ensure the existence of a score increasing neighbor)?\n   - \"Check if G has a higher score .. if not, discard ..\": then what if the score is unchanged, or an unchanged score is provably impossible (even with possibly misspecified graphs)?\n   - At the first glance the SafeInsertion strategy looks very similar to the original strategy in GES: pick DAGs from CPDAG and then check if X is independent of Y conditioned on Y's current parents. Could the authors highlight the biggest difference there?\n\n\n\n7. (Minor) Sentences like \"This more targeted search yields up to a 10 -fold speed-up and 3 -fold reduction in structural error relative to GES\" seems inappropriate in abstract, without a clear scope and simulation setup.", "was_revised": true, "final_justification": "My concerns have been well addressed by the authors' response.", "rebuttal": "Thank you for your thoughtful and comprehensive feedback. We believe some concerns may stem from a lack of clarity regarding technical aspects of our work. We hope you will reconsider the paper in light of the clarifications below.\n\n# W1\n1.  *Prop 1 complete?* We appreciate the question and will revise the text to better motivate our heuristics.\n    1. The converse of Prop. 1 does hold. Prop. 1 shows which conditional independencies (CIs) can be inferred from the scoring operations that GES already conducts: a fact that LGES uses. Its converse shows which scoring operations can be conducted to test for certain CIs.\n    2. We do not check for the existence of an arbitrary separating set (as in PC). Local consistency only relates score changes to CIs with conditioning sets of the form $pa(Y,G)$ for some $G$ in $\\mathcal{E}$. \n2. *Heuristics reflect Prop 1?*\n      1. ConservativeInsert searches exactly for a score-decreasing Insert per Prop 1.\n      2. SafeInsert may not always detect such an $X-Y$ separation, since it chooses *one* Insert and checks if it decreases the score (details in Examples 2 and 3).\n    3. Both **ConservativeInsert and SafeInsert often successfully detect non-adjacencies in practice**, as suggested by their improvement on GES in Exp 5.1.\n\n# W2 \n*LGES conducts more tests? Why is LGES faster?*\n Thank you for raising this point; we will clarify it in the paper. **Both LGES variants perform no more (often fewer) scoring operations per step than GES**.\n1. *\"more robust decision… more tests… now all $\\mathbf{T}$ need to be tested\"* GES already tests all $X,Y$, and $\\mathbf{T}$ to find the best Insert. In contrast, SafeInsert and ConservativeInsert stop early after finding a score-decreasing Insert. So, LGES is faster per step.\n2. LGES is also faster overall due to its progression; it adds fewer edges, reducing future operator counts (exponential in the node degree).\n\n# W3\n*Deletion phase not optimized accordingly?*\nA score-decreasing Delete implies dependence under some conditioning set, not necessarily all. A true adjacency implies dependence given all conditioning sets. So, skipping all Deletes due to one score decrease would compromise soundness and risk admitting many false adjacencies. A true adjacency would imply all $X-Y$ Deletes are score-decreasing, so GES/LGES will never delete $X-Y$. Experiments support this: **false non-adjacencies are rare** (Fig D.1.1 (f)).\n\n# W4\n*Relevance of interventions/prior knowledge?*\nAlgorithms that can use prior knowledge and interventional data have significant practical implications. In Experiment 5.2, prior knowledge can improve both accuracy and scalability. Interventional data improves identifiability [1] and is increasingly available in domains like biology due to novel experimental techniques, e.g., perturb-seq.\n1. *“run plain GES…on all variables including the domain index.”*\n    1. If this method treats the domain index as a categorical root variable, then it may not be sound:\n        1. Data from different interventions is not identically distributed,  a core assumption in most causal discovery algorithms (including GES). This motivated GIES [1].\n        2. More edges can be oriented using interventional data, and interventional MECs tend to be smaller than observational MECs. However, this method would only learn the observational MEC over the variables plus domain index.\n    2. If you are referring to the use of F-nodes as intervention indicator variables [9, 10], this would be a valid but non-trivial extension of GES.\n    3. If we misunderstand your suggestion, we would appreciate a reference so we can better address the comparison. \n2. *“Is this idea new…how do other score based variants incorporate background knowledge?”* Thank you for the valuable question. We will add this to the Related Works. To our knowledge, using priority constraints to guide the search is new to score-based methods. Other approaches include:\n    1. Knowledge-Guided GES [3], which initializes the search to user-provided edges, and strictly avoids insertions of forbidden edges. It is not theoretically sound if the user’s knowledge is imperfect. Even if the knowledge is perfect, it may not be sound due to the restriction on Insert operators.\n    2. Incorporating the prior into the score [4, 5], which scores the graph using a prior based on background knowledge (in addition to data fit). However, this has not been applied to theoretically sound causal discovery.\n    3. Temporal ordering [6] uses a user-provided ordering to prune the search space, though its guarantees are unclear.\n3. *“technical discussions … too short in body.”*  With the additional content page if accepted, we are open to expanding and prioritizing these sections given reviewer consensus.\n\n\n# W5\n*Other GES variants?*\nWe appreciate the suggestion and will organize a cleaner appendix on this point. \n1. **SGES**. We could not find a public implementation for comparison.\n2. **FGES**. FGES avoids inserting $X-Y$ edges if $X,Y$ are  marginally independent. This means FGES may not be theoretically sound (noted in Sec A.2). FGES also underperforms GES in time and accuracy [2], though its Java implementation prevents fair runtime comparisons.\n3. **XGES**. \n    1. To facilitate a fair comparison and shared implementation across GES variants, we implemented the XGES-0 [5] heuristic of prioritizing deletions over reversals over insertions in our LGES Python code. The accuracy on average degree 2 ER graphs with up to 150 variables was: GES < XGES-0 < LGES (Safe) < LGES (Safe) + XGES-0 < LGES (Cons) < LGES (Cons) + XGES-0. The time: reverse of accuracy, but LGES (Cons) and LGES (Safe) + XGES-0 swapped.\n    2. To elaborate, the XGES-0 heuristic modestly improved the accuracy and runtime of each algorithm. This is consistent with [5], comparing GES-r (our GES) and XGES-0. **Both LGES variants (even w/o the XGES-0 heuristic) significantly outperform XGES-0**. \n    3. XGES extends XGES-0 by forcing edge deletions and restarts. This causes a ~10x slowdown relative to XGES-0 (Fig. 4 [5]), making it less practical for integration with LGES in high-dimensional settings.\n4. **GES with repeats**. We ran GES/LGES with repeated applications of the phases  (proposed in [1] and by reviewer PUwW).  This modestly improved accuracy of GES/LGES, but **both LGES variants (even w/o repeats) significantly outperform GES w/ repeats.**\n\n**SHD**\n| Method/Variables| 25| 50  | 100 | 150 |\n|-|-|-|-|-|\n|GES| 4.38 ± 8.45    | 10.00 ± 9.54   | 31.78 ± 8.59   | 61.78 ± 10.26  |\n|XGES-0 | 3.04 ± 6.85    | 9.14 ± 8.38    | 30.66 ± 7.65   | 59.74 ± 10.10  |\n|LGES (Safe)| 3.62 ± 7.59    | 8.14 ± 9.48    | 25.80 ± 9.06   | 49.69 ± 10.02  |\n|XGES-0 + LGES (Safe)| 2.58 ± 5.80    | 7.14 ± 7.92    | 24.41 ± 7.97   | 47.42 ± 9.19   |\n|LGES (Cons)| 3.06 ± 6.91    | 4.94 ± 6.58    | 15.39 ± 8.82   | 29.94 ± 9.45   |\n|XGES-0 + LGES (Cons)|**2.56 ± 5.95**|**4.42 ± 5.70**|**14.66 ± 7.91**|**26.95 ± 6.88**|\n\n**Time**\n| Method/Variables| 25 | 50|100 |150|\n|-|-|-|-|-|\n| GES| 4.67 ± 1.89    | 58.22 ± 15.05  | 841.76 ± 102.80 | 4509.60 ± 1047.57 |\n| XGES-0| 3.85 ± 0.96    | 50.69 ± 10.94  | 759.37 ± 92.51  | 4043.42 ± 332.04  |\n| LGES (Safe)| 1.28 ± 0.84    | 8.81 ± 3.91    | 69.71 ± 22.33   | 251.39 ± 65.19    |\n| LGES (Cons) | 1.17 ± 0.59    | 8.39 ± 3.68    | 66.92 ± 21.82   | 240.40 ± 62.26    |\n| XGES-0 + LGES (Safe)| 1.07 ± 0.51    | 7.40 ± 3.16    | 55.44 ± 17.30   | 208.16 ± 51.64    |\n| XGES-0 + LGES (Cons)| **1.06 ± 0.57**    | **7.06 ± 2.99**    | **53.33 ± 17.18**   | **198.33 ± 49.03**    |\n\n\n# W6\n*SafeInsert details?*\n1. “$nd_Y^G$ undefined?” Thank you for the catch. We'll define this as the non-descendants of $Y$ in $G$ in the prelim.\n2. “SafeInsert...only one DAG from the CPDAG” Yes. SafeInsert picks one DAG $G$ in $\\mathcal{E}$ and checks if  $X\\perp Y\\mid pa(Y,G)$. If so, we skip $X-Y$ Inserts. While we may skip a higher-scoring Insert, it's undesirable regardless, since $X,Y$ are separable. If $X \\not\\perp Y\\mid pa(Y,G)$, we proceed as in GES. Using one $G$ for all $X,Y$ pairs ensures soundness.\n3. “Unchanged score... impossible“ Correct; local consistency gives a strict score change in both directions.\n4. “SafeInsert similar to GES” Not exactly. SafeInsert avoids adding $X-Y$ if it detects a separating set in its chosen $G$, even if such a separation isn't given by other DAGs in $\\mathcal{E}$. GES may still add $X-Y$ if another DAG gives a higher score. We will clarify this in Ex. 2-3.\n\n[1] A. Hauser and P. Bühlmann. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. JMLR, 2012.\n\n[2] A. Nazaret and D. Blei. Extremely greedy equivalence search. UAI, 2024.\n\n[3] U. Hasan and M. O. Gani. Optimizing data-driven causal discovery using knowledge-guided search. arXiv preprint arXiv:2304.05493, 2024.\n\n[4] M. J. Bayarri, J. O. Berger, W. Jang, S. Ray, L. R. Pericchi, and I. Visser. Prior-based Bayesian information criterion. Statistical Theory and Related Fields, 2019.\n\n[5] N. Angelopoulos and J. Cussens. Bayesian learning of Bayesian networks with informative priors. Annals of Mathematics and Artificial Intelligence, 2008.\n\n[6] A. C. Constantinou, Z. Guo, and N. K. Kitson. The impact of prior knowledge on causal structure learning. Knowledge and Information Systems, 2023.\n\n[7] J. I. Alonso, L. de la Ossa, J. A. Gamez, and J. M. Puerta. On the use of local search heuristics to improve GES-based Bayesian network learning. Applied Soft Computing, 2018.\n\n[8] X. Liu, X. Gao, X. Ru, X. Tan, and Z. Wang. Improving greedy local search methods by switching the search space. Applied Intelligence, 2023.\n\n[9] K. Yang, A. Katcoff, and C. Uhler. Characterizing and learning equivalence classes of causal DAGs under interventions. ICML, 2018.\n\n[10] M. Kocaoglu, A. Jaber, K. Shanmugam, and E. Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. NeurIPS, 2019."}, {"review_id": "QMEFyF2yc5", "reviewer": "Reviewer_RnrE", "summary": "The authors propose a variant of GES that changes the forward phase. Most importantly, they show that if an Insert operation between X and Y decreases the score, then (some) other Insert operations between those variables do not need to be considered. Further, the algorithm allows the incorporation of background knowledge (but will ignore this if it contradicts the data) and can utilise interventional data. Experiments show this new algorithm is both faster and more accurate than the original GES.", "questions": "Q1: I could not quite follow the discussion in section 3.2 about a potential issue with ConservativeInsert. If I understand correctly, the issue is that sometimes, ConservativeInsert may discard the only score-increasing Insert(s). However, from Proposition 1, it seems that such score-increasing Inserts are not desirable because they create d-connections where we want d-separations. Can you give an example to show why it is nonetheless preferable to use a strategy that does consider such Inserts?\n\n### Minor suggestions that don't impact my rating:\n- on page 2, the period after \"starts the search with $\\mathcal{E}$\" should be a comma\n- I believe the \"If not\" in Strategy 2 should be \"If so\"\n- in Example 3, $X$ should be $X_1$", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "This paper makes an important contribution, which is accompanied by theoretical proofs of correctness and thorough empirical evaluation. The paper is relevant both for researchers developing structure learning algorithms and for researchers wanting to apply them. Furthermore, the paper is clearly written.", "was_revised": true, "final_justification": "I think this is a good paper with a valuable contribution, that deserves a place in the conference.", "rebuttal": "We greatly appreciate your feedback and positive assessment of our work.\n\n# Q1\n\n*On section 3.2’s discussion about a potential issue with ConservativeInsert.*\n\nThank you for the perceptive question. We will revise our explanation to make this point more precise.\n1. *\"ConservativeInsert may discard the only score-increasing Insert(s)?\"* Not exactly: it is currently unknown whether there exist cases where ConservativeInsert would (incorrectly) discard the only score-increasing Insert(s). If we can construct an example where it does, it would amount to proving that LGES + ConservativeInsert is theoretically unsound. If we can show no such example exists, it would establish soundness. Our work leaves the soundness of ConservativeInsert as an open question; despite our efforts, we were not able to prove or disprove it. Nonetheless, we include ConservativeInsert as a valuable heuristic, given its strong empirical performance relative to GES.\n\n2. *\"...such score-increasing Inserts are not desirable ...Can you give an example to show why it is nonetheless preferable to use a strategy that does consider such Inserts?\"*\nIt is difficult to construct a concrete example, as doing so would demonstrate that ConservativeInsert is not sound. However, our partial guarantees in Propositions C.1 and C.2 may serve as a starting point for proving soundness or giving an example that shows otherwise. To elaborate, these results imply that for any MEC $\\mathcal{E}$ for which ConservativeInsert would discard the only score-increasing Insert(s), $\\mathcal{E}$ would (a) already contain the skeleton of the true MEC, and (b) not disagree with the true MEC on the orientation of any unshielded triples they have in common. This may provide a useful direction for constructing a counterexample to soundness. Our empirical results suggest that such cases, if they exist, are at least rare in the ER model, since ConservativeInsert significantly outperforms both GES and SafeInsert."}, {"review_id": "VBnwkC8f52", "reviewer": "Reviewer_AAo7", "summary": "This paper introduces Less Greedy Equivalence Search (LGES), which is an improved algorithm for causal discovery that improves upon the classic Greedy Equivalence Search (GES) method. It does so by doing doing edge selection less greedily, instead of greedily maximizing the score. LGES is shown to also leverage possibly misspecified prior assumptions and correct misspecified edges.", "questions": "I felt the paper was fairly clear and I liked how simulation was used to gain intuition on where GES may not do well. My only question is regarding a more extensive set of experiments, which in it of itself would reveal the algorithm's benefits. Finally, I will add that I'm also not super familiar with score based methods for CD and the associated literature, so perhaps other reviewers can champion the paper if they feel strongly about it.", "limitations": "Please see weakness.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:  The paper carefully develops two new strategies for improving on GES. As the authors wrote, it is the first asymptotically correct score-based procedure for learning from interventional data that can scale to graphs with more than a hundred nodes. LGES is also robust in handling misspecified graphs. And the authors do compare with other algorithms such as PC and NOTEARS, and not jus showing that LGES is only an improvement over GES. \n\nWeaknesses: As one comment that stood out to me, I think the paper would be more compelling if a more extensive set of experiments was run. It would be more convincing if LGES was benchmarked on a real world dataset (perhaps Sachs which was considered in NOTEARS), as well as synthetic graphs of varying sparsity.", "was_revised": true, "final_justification": "My overall rating for the paper remains positive.", "rebuttal": "We appreciate your time and thoughtful feedback on our work.\n\n# Q1\n Please see below some new results regarding your comment,\n\n> I think the paper would be more compelling ... more extensive set of experiments… real world dataset (perhaps Sachs which was considered in NOTEARS), as well as synthetic graphs of varying sparsity.\n\n1. **Real world data.** We indeed compared LGES (both variants) against GES using the Sachs dataset, as detailed in Appendix D.4. All algorithms achieve the same structural error, though LGES is faster. We would appreciate suggestions for additional real-world datasets to explore and feedback on the organization, if reviewers feel that this experiment should be highlighted in the main text.\n2. **Synthetic graphs of varying sparsity.** Thank you for the helpful suggestion. We conducted additional experiments on Erdos Renyi graphs of average degree 1 and 3 (ER1, ER3 respectively) with up to 150 variables. Results are consistent with the ER2 case: LGES outperforms GES in both speed and accuracy. Summary results are shown below; we will add the relevant plots to the revised manuscript.\n\n**ER1 graphs, SHD**\n\n| Algorithm           | 25         | 50         | 100         | 150         |\n|--------------------|------------|------------|-------------|-------------|\n| GES                | 1.88 ± 1.98 | 7.52 ± 3.70 | 28.54 ± 7.26 | 61.10 ± 8.19 |\n| LGES (Safe)        | 1.16 ± 1.35 | 5.62 ± 2.84 | 22.40 ± 6.27 | 50.40 ± 7.58 |\n| LGES (Conservative)| **0.82 ± 1.65** | **2.68 ± 1.75** | **10.74 ± 4.37** | **27.52 ± 6.44** |\n\n**ER1 graphs, time**\n| Algorithm           | 25         | 50         | 100           | 150            |\n|--------------------|------------|------------|---------------|----------------|\n| GES                | 1.75 ± 0.41 | 24.70 ± 4.13 | 407.25 ± 48.87 | 2359.30 ± 209.12 |\n| LGES (Safe)        | 0.18 ± 0.10 | 1.29 ± 0.51 | 10.40 ± 2.54  | 43.29 ± 9.45   |\n| LGES (Conservative)| **0.17 ± 0.08** | **1.24 ± 0.51** | **9.67 ± 2.38**   | **39.54 ± 8.75**   |\n\n\n**ER3 graphs, SHD**\n| Algorithm           | 25          | 50          | 100          | 150          |\n|--------------------|-------------|-------------|--------------|--------------|\n| GES                | 13.66 ± 17.84 | 36.06 ± 48.99 | 55.34 ± 39.32 | 87.39 ± 34.99 |\n| LGES (Safe)        | 11.12 ± 16.57 | 32.00 ± 47.71 | 47.47 ± 33.98 | 75.67 ± 33.73 |\n| LGES (Conservative)| **10.44 ± 16.65** | **29.66 ± 47.32** | **35.57 ± 34.16** | **58.00 ± 34.97** |\n\n**ER3 graphs, time**\n| Algorithm           | 25          | 50            | 100            | 150             |\n|--------------------|--------------|---------------|----------------|-----------------|\n| GES                | 9.17 ± 4.88   | 1515.92 ± 5715.32 | 7166.08 ± 33723.75 | 13768.44 ± 18749.97 |\n| LGES (Safe)        | 3.40 ± 2.93   | 284.79 ± 996.03   | 326.55 ± 574.96    | **846.54 ± 487.28**     |\n| LGES (Conservative)| **3.29 ± 2.85**   | **212.79 ± 841.08**   | **266.61 ± 241.66**   | 914.51 ± 789.88 |\n\n3. **Additional experiments varying the number of prior edge assumptions.** We varied the number of edges included in the background knowledge (Experiment 5.2). Again, results are similar: LGES outperforms GES-Init.\n4. **Additional baselines.** To evaluate LGES more comprehensively, we conducted experiments with two new GES variants, as suggested by other reviewers: GES with repeated applications of the forward, backward, and turning phases (proposed in [1]), and the XGES-0 [2] heuristic of prioritizing deletions before insertions. We also combined LGES with these strategies. We evaluated all algorithms on ER2 graphs with up to 150 nodes. Findings include:\n    1. Repeated phase application modestly improved the accuracy of GES/LGES (both variants). However, **both variants of LGES (even without repeats) significantly outperform GES with repeats**.\n    2. The XGES-0 heuristic modestly improved the runtime and accuracy of GES and LGES (both variants). However, **both variants of LGES (even without the XGES-0 heuristic) significantly outperform XGES-0**. The resulting ranking by accuracy is: GES < XGES-0 < LGES (Safe) < LGES (Safe) + XGES-0 < LGES (Conservative) < LGES (Conservative) + XGES-0. Runtime followed the reverse order, but with LGES (Safe) + XGES-0 and LGES (Conservative) swapped.\n\n**SHD**\n\n| Algorithm                     | 25            | 50            | 100           | 150           |\n|------------------------------|---------------|---------------|---------------|---------------|\n| GES                          | 4.38 ± 8.45    | 10.00 ± 9.54   | 31.78 ± 8.59   | 61.78 ± 10.26  |\n| XGES-0                       | 3.04 ± 6.85    | 9.14 ± 8.38    | 30.66 ± 7.65   | 59.74 ± 10.10  |\n| LGES (Safe)                  | 3.62 ± 7.59    | 8.14 ± 9.48    | 25.80 ± 9.06   | 49.69 ± 10.02  |\n| XGES-0 + LGES (Safe)         | 2.58 ± 5.80    | 7.14 ± 7.92    | 24.41 ± 7.97   | 47.42 ± 9.19   |\n| LGES (Conservative)          | 3.06 ± 6.91    | 4.94 ± 6.58    | 15.39 ± 8.82   | 29.94 ± 9.45   |\n| XGES-0 + LGES (Conservative) | **2.56 ± 5.95**    | **4.42 ± 5.70**   | **14.66 ± 7.91**   | **26.95 ± 6.88**   |\n\n\n\n**Time**\n| Algorithm                     | 25            | 50            | 100            | 150             |\n|------------------------------|---------------|---------------|----------------|-----------------|\n| GES                          | 4.67 ± 1.89    | 58.22 ± 15.05  | 841.76 ± 102.80 | 4509.60 ± 1047.57 |\n| XGES-0                       | 3.85 ± 0.96    | 50.69 ± 10.94  | 759.37 ± 92.51  | 4043.42 ± 332.04  |\n| LGES (Safe)                  | 1.28 ± 0.84    | 8.81 ± 3.91    | 69.71 ± 22.33   | 251.39 ± 65.19    |\n| LGES (Conservative)          | 1.17 ± 0.59    | 8.39 ± 3.68    | 66.92 ± 21.82   | 240.40 ± 62.26    |\n| XGES-0 + LGES (Safe)         | 1.07 ± 0.51    | 7.40 ± 3.16    | 55.44 ± 17.30   | 208.16 ± 51.64    |\n| XGES-0 + LGES (Conservative) | **1.06 ± 0.57**    | **7.06 ± 2.99**    | **53.33 ± 17.18**   | **198.33 ± 49.03**    |\n\n\n[1] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional\nMarkov equivalence classes of directed acyclic graphs. J. Mach. Learn. Res., 13(1):2409–2464,\nAug 2012. \n\n[2] Achille Nazaret and David Blei. Extremely greedy equivalence search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 2716–2745. PMLR, 15–19 Jul 2024."}, {"review_id": "Svgg3vs9H2", "reviewer": "Reviewer_PUwW", "summary": "The paper presents a Generalized- (GGES) and two variants of Less Greedy Equivalence Search (LGES) algorithms that hold identifiability results in a generalized setting, by modify the edge insertions step of the well-known GES algorithm. In a first step the authors prove that under particular conditions choosing any score-increasing edge insertion within GES still leads to identifiability of the true Markov Equivalence Class (MEC), even if this does not correspond to the most score-increasing edge insertion. They, furthermore, reason that performing particular edge insertions between two variables, A-B, with the largest score increase might not be optimal in the presence of similar, score decreasing insertion operations on A-B under the same MEC. In consequence two approaches are presented: a 'conservative' variant that only selects edge insertions with no score-decreasing insert throughout the whole MEC, and a 'safe' variant the considers score-decreases from an arbitrary DAG sampled from the MEC.\n\nThe authors furthermore prove that GGES can start from arbitrary MEC, and also softly incorporate and correct for (possibly misspecified) prior knowledge, dividing given knowledge into four categories of (weakly) required and forbidden knowledge, that get prioritizes in the search, but ignored if inconsistent with the current MEC. Finally, they a variant for the incorporation of interventional data for LGES via a novel \"I-Orient\" algorithm is presented that identifies an the I-MEC, based on additional interventional data.\n\nExperiments are performed on Erdős–Rényi graphs with p variables 2p edges and up to 150 variables on data of randomly sampled additive linear Gaussian noise models. The presented experimental results on the synthetic ER graphs indicate consistent superior performance over the compared to GES and GIES algorithms for observational and interventional data in terms of inference performance (SHD, Precision, Recall) and overall runtime. Similarly, the authors show in the appendix on-par performance for real-world protein signaling data between their LGES and the standard GES algorithm. Similarly, the recovery from misspecified knowledge shows good recovery rates over GIES.", "questions": "1) Could the authors provide further insights on the changes related to enabling repeated phase application with all LGES and GES-type baselines? In particular, can GES baselines overall improve and is the GES-Init algorithm more able to remove and recover from misspecified edges?\n2) Similarly, could the authors provide further insights in comparison to the performance under the possibly more competitive xGES algorithm? Could the presented LGES itself benefit from interleaved phase applications?\n3) In corollary 2, the authors utilize the property of SafeInsert to operate on arbitrary DAGs of the current MEC in order to consider possible score-decreases. I assume that the corresponding DAG is sampled randomly? Could the authors confirm this or explain their method for choosing a particular DAG?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper provides overall significant theoretical results and insights which do result in seemingly large empirical performance increases, and might have lead to further developments on edge-selection strategies beyond this paper. While I do not believe, that conclusions drawn from experiments will largely change in qualitaty, my main critique is the omission of a possibly recent competitive xGES baseline and the decision to not consider the common choice of phase repetition within GES baselines, (but also the proposed LGES itself).\n\n**Strengths**\n\n1) The paper is generally well written. The authors provide clear and convincing arguments, towards weaknesses of the original GES algorithm, that limit its efficiency and performance. The modification towards the GGES and LGES variants, are well described. The corresponding proofs for the various theorems and propositions towards correctness and MEC identifiability of the algorithms are well described (as they partly align the original GES proofs) and, to the best of my understanding, seem to be correct.\n2) The theoretical proofs for MEC identifiability under arbitrary score-increasing edge insertion operations provides a novel and significant generalization for the choice of edge selection strategies of GES-class algorithms which might initiate to further developments on this topic.\n3) The experiments are well setup and follow standard procedure on Erdős–Rényi (ER) graphs with sufficient variation on the number of variables, applied metrics and repetitions. The authors are able to demonstrate superior performance of both LGES variants in comparison to the chosen baselines (PC,GES,GIES,NOTEARS) over all experiments in the main paper for MEC identifiability for observational and interventional data, as well as the recovery from misspecified knowledge, in terms of performance and runtime. An additional evaluation on real-world protein signaling data indicates the same performance as the GES algorithm.\n\n\n\n**Weaknesses**\n\n1) While the authors discuss and cite recent this recent GES variant, they do not compare to Extremely Greedy GES (xGES, [1]), which performs insert/delete/turning operations in an interleaved sequence and has also shown strong improvements over the original GES. While this approach is unlikely to improve in runtime, it might pose a more competitive baseline in terms of overall MEC inference.\n2) While the authors make use of mention the additional use of turning phase of [2], the work additionally suggests the repeated application of the forward, backward and turning phases until no further improvements in score can be observed. The presented pseudo code suggests that such repeated applications are not performed for LGES, and (if I did not miss the particular spot) the corresponding parameter in the code is set to false for all GES-like algorithm calls. While the presented results on a single iteration performance show remarkable performance increases, comparisons to GES/GIES with repeated phases might provide for a more competitive comparison. This particularly applies for the recovery of misspecified edges from prior knowledge, where the GES-Init algorithm can have the ability to insert novel edges after the, otherwise final, edge removal phase which is the otherwise only chance to eliminate erroneous edges.\n\n\n\n**Minor Points**\n\n* I would like to recommend to briefly mention the meaning of $Nd^G_Y$ in the background section.\n* Additionally, I believe the term $nd^G_Y$ in line 217 should be capitalized and made bold, similar to the other notation.\n\n\n\n[1] Nazaret, Achille, and David Blei. \"Extremely greedy equivalence search.\" *arXiv preprint arXiv:2502.19551* (2025).\n\n[2] Hauser, Alain, and Peter Bühlmann.  \"Characterization and greedy learning of interventional Markov  equivalence classes of directed acyclic graphs.\" *The Journal of Machine Learning Research* 13.1 (2012): 2409-2464.", "was_revised": true, "final_justification": "The authors provided good experimental comparisons with the XGES-0 and XGES methods, which I consider a generally competitive GES variant. The new results position the proposed LGES method well within existing work and seem to show competitiveness of the method. The clarifications with regard to runtime measurements seem plausible.", "rebuttal": "Thank you for your perceptive comments and suggestions.\n\n# Q1, W2\n*Can GES/LGES benefit from repeated phase applications?*\nThank you for raising this valuable point. Indeed, our submitted experiments did not include repeated phase applications. In response to your suggestion, we ran GES and both variants of LGES with repeated applications of the forward, backward, and turning phases [4] on ER graphs of average degree 2 with to 150 variables. We found that **repeated phases modestly improved the accuracy of GES/LGES (both variants). However, even without repeats, both variants of LGES significantly outperformed GES with repeats**. Please see summary results below. We will note this in our paper.\n\n# Q2, W1\n*How do interleaved backward/turning/forward phases in XGES compare with and improve on LGES?*\nThank you for this insightful question. \n1. To faciliate a fair comparison and shared implementation across GES variants, we implemented the XGES-0 [5] heuristic of prioritizing deletions before reversals before insertions in our Python implementation of GES/LGES. We again evaluated these algorithms on ER2 graphs with up to 150 variables. The resulting ranking by accuracy was: GES < XGES-0 < LGES (Safe) < LGES (Safe) + XGES-0 < LGES (Conservative) < LGES (Conservative) + XGES-0. Runtime followed the reverse order, but with LGES (Safe) + XGES-0 and LGES (Conservative) swapped.\n2. To elaborate, we found that the XGES-0 heuristic modestly improved the accuracy and runtime of each algorithm. This is consistent with [5], when comparing their GES-r (our GES) and XGES-0. **Even without the XGES-0 heuristic, both variants of LGES significantly outperform XGES-0.** \n3. XGES extends XGES-0 by forcing edge deletions and restarts. This causes a ~10x slowdown relative to XGES-0 (Fig. 4 [5]), making it less practical for integration with LGES in high-dimensional settings.\n\n**SHD**\n| Algorithm                     | 25            | 50            | 100            | 150             |\n|------------------------------|---------------|---------------|----------------|-----------------|\n| GES                          | 4.67 ± 1.89    | 58.22 ± 15.05  | 841.76 ± 102.80 | 4509.60 ± 1047.57 |\n| GES (Repeats)                | 4.11 ± 1.43    | 52.56 ± 13.64  | 767.14 ± 94.54  | 4060.84 ± 380.35  |\n| XGES-0                       | 3.85 ± 0.96    | 50.69 ± 10.94  | 759.37 ± 92.51  | 4043.42 ± 332.04  |\n| LGES (Safe)                  | 1.28 ± 0.84    | 8.81 ± 3.91    | 69.71 ± 22.33   | 251.39 ± 65.19    |\n| LGES (Safe, Repeats)         | 1.00 ± 0.66    | 6.73 ± 2.98    | 52.08 ± 16.48   | 192.57 ± 47.90    |\n| XGES-0 + LGES (Safe)         | 1.07 ± 0.51    | 7.40 ± 3.16    | 55.44 ± 17.30   | 208.16 ± 51.64    |\n| LGES (Conservative)          | 1.17 ± 0.59    | 8.39 ± 3.68    | 66.92 ± 21.82   | 240.40 ± 62.26    |\n| XGES-0 + LGES (Conservative) | 1.06 ± 0.57    | 7.06 ± 2.99    | 53.33 ± 17.18   | 198.33 ± 49.03    |\n| LGES (Conservative, Repeats) | **0.95 ± 0.50**    | **6.56 ± 2.86**    | **50.65 ± 16.31**   | **185.35 ± 45.55**    |\n\n**Time**\n\n| Algorithm                     | 25            | 50            | 100            | 150             |\n|------------------------------|---------------|---------------|----------------|-----------------|\n| GES                          | 4.67 ± 1.89    | 58.22 ± 15.05  | 841.76 ± 102.80 | 4509.60 ± 1047.57 |\n| GES (Repeats)                | 4.11 ± 1.43    | 52.56 ± 13.64  | 767.14 ± 94.54  | 4060.84 ± 380.35  |\n| LGES (Safe)                  | 1.28 ± 0.84    | 8.81 ± 3.91    | 69.71 ± 22.33   | 251.39 ± 65.19    |\n| LGES (Safe, Repeats)         | 1.00 ± 0.66    | 6.73 ± 2.98    | 52.08 ± 16.48   | 192.57 ± 47.90    |\n| LGES (Conservative)          | 1.17 ± 0.59    | 8.39 ± 3.68    | 66.92 ± 21.82   | 240.40 ± 62.26    |\n| XGES-0                       | 3.85 ± 0.96    | 50.69 ± 10.94  | 759.37 ± 92.51  | 4043.42 ± 332.04  |\n| XGES-0 + LGES (Safe)         | 1.07 ± 0.51    | 7.40 ± 3.16    | 55.44 ± 17.30   | 208.16 ± 51.64    |\n| XGES-0 + LGES (Conservative) | 1.06 ± 0.57    | 7.06 ± 2.99    | 53.33 ± 17.18   | 198.33 ± 49.03    |\n| LGES (Conservative, Repeats) | **0.95 ± 0.50**    | **6.56 ± 2.86**    | **50.65 ± 16.31**   | **185.35 ± 45.55**  |\n\n\n# Q3\n*How does SafeInsert choose a DAG in the current MEC?*\n1. Thank you for your careful reading. We do not sample the DAG randomly, but use a simple polynomial-time algorithm for converting a PDAG to DAG presented in [1] and used in the original GES [2]. It works as follows. \n    - Given a PDAG $\\mathcal{G}$, copy it to $\\mathcal{G}'$.\n    - Choose some vertex $V$ in $\\mathcal{G}'$ such that\n        1. $V$ is a sink node (no outgoing directed edges) in $\\mathcal{G}'$\n        2. all undirected neighbors of $V$ are adjacent to each other in $\\mathcal{G}'$. \n    - Direct all edges in $\\mathcal{G}$ into $V$. \n    - Remove $V$ from $\\mathcal{G}'$. \n    - Repeat with another $V$ and $\\mathcal{G}'$, until all edges in $\\mathcal{G}$ are directed. \n\nCondition 1 ensures that orienting edges into $V$ will not create any cycles. Condition 2 ensures that orienting edges into $V$ will not create any new v-structures (aka unshielded colliders).\n\n2. In theory, any procedure for choosing a DAG from an MEC suffices. There is a poly-time algorithm for uniform random sampling of a DAG from an MEC [3], with C++/Julia implementations available. We are open to investigating how the choice of DAG affects SafeInsert performance if the reviewers think this is a fruitful direction. Presumably, any SafeInsert variant would not be as performant as ConservativeInsert, which checks for the existence of any DAG witnessing a separation.\n\n\n[1] Dorit Dor and Michael Tarsi. A simple algorithm to construct a consistent extension of a partially oriented graph. Technical Report R-185, Cognitive Systems Laboratory, UCLA Computer Science Department, October 1992.\n\n[2] David Maxwell Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res., 3(null):507–554, March 2003. \n\n[3] Marcel Wienobst, Max Bannach, and Maciej Liskiewicz. Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications. J. Mach. Learn. Res. 24(213):1-45, Jul 2023. \n\n[4] Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional\nmarkov equivalence classes of directed acyclic graphs. J. Mach. Learn. Res., 13(1):2409–2464,\nAug 2012.\n\n[5] Achille Nazaret and David Blei. Extremely greedy equivalence search. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 2716–2745. PMLR, 15–19 Jul 2024."}]

Author rebuttal:

Meta-review: This paper introduces Less Greedy Equivalence Search (LGES), which improves upon the classic Greedy Equivalence Search (GES) method by choosing edge orientations less greedily, instead of greedily maximizing the score. 

In terms of strengths, the reviewers unanimously recognized the importance of the problem being studied and the significance of the new insights that this work offers. The writing quality of the paper (e.g., the illustrative and motivating examples) was also praised. Their I-Orient algorithm is also the first asymptotically correct score-based procedure for learning from interventional data that can scale to graphs with more than a hundred nodes.

There were a number of issues raised in the reviews, which the authors successfully responded to. We would request the authors to include in their revision the data and discussion from the new experiments they conducted for the rebuttal.
Decision: Accept (poster)