Thank you for your perceptive comments and suggestions.

Q1, W2

Can GES/LGES benefit from repeated phase applications? Thank 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.

Q2, W1

How do interleaved backward/turning/forward phases in XGES compare with and improve on LGES? Thank you for this insightful question.

1. 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.
2. 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.
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.

SHD

Time

Q3

How does SafeInsert choose a DAG in the current MEC?

1. 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.
   • Given a PDAG $\mathcal{G}$, copy it to $\mathcal{G}'$.
   • Choose some vertex $V$ in $\mathcal{G}'$ such that
     1. $V$ is a sink node (no outgoing directed edges) in $\mathcal{G}'$
     2. all undirected neighbors of $V$ are adjacent to each other in $\mathcal{G}'$.
   • Direct all edges in $\mathcal{G}$ into $V$.
   • Remove $V$ from $\mathcal{G}'$.
   • Repeat with another $V$ and $\mathcal{G}'$, until all edges in $\mathcal{G}$ are directed.

Condition 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).

2. 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.

[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.

[2] David Maxwell Chickering. Optimal structure identification with greedy search. J. Mach. Learn. Res., 3(null):507–554, March 2003.

[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.

[4] 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–2464, Aug 2012.

[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.

Thank you for the positive remarks and for engaging with our new results.

Regarding your note:

“...why the authors do not compare to the 'full' XGES.”

We appreciate your suggestion. The initial omission was due to the effort required to implement full XGES fairly in our codebase, which was challenging within the rebuttal window. However, since submission, we have implemented full XGES and evaluated it on ER2 graphs of 25 and 50 nodes. Larger graphs are in progress and will be included in the revised manuscript.

In terms of accuracy, both insertion heuristics improve XGES. While XGES outperforms XGES-0, the comparison with LGES (Conservative) is indecisive: LGES outperforms XGES for 50 nodes, while the opposite holds for 25 nodes, both by slim margins. XGES + LGES (Conservative) is the most accurate overall.

In terms of runtime, both heuristics provide up to a 10x speedup of XGES. Without them, XGES is $\approx$30x slower than LGES and $\approx$4x slower than GES/XGES-0. Combining LGES with XGES slows LGES by 3x. XGES-0 + LGES (Conservative) is the fastest overall.

(Table 1) Runtime

We hope Table 2 below also addresses your note:

“...the authors accidentally copied the timetable twice.”

Thank you for catching this ($\dagger$).

(Table 2) SHD

Finally, regarding your note that

“Fig. 4 of the XGES paper, run time scaling for both XGES and XGES-0 seemed to be similar or rather below that of GES.”

We want to address why our runtime results seem to be in disagreement with those of [5].

Like [5], we find that XGES-0 is faster than GES, but the speed-up is modest (see table in original rebuttal), unlike the $\approx$30x speedup reported in Fig. 4 [5]. Moreover, [5] reports that XGES is faster than GES, while we find that XGES to be $\approx$4x slower (Table 1 above).

To explain why, it’s important to emphasize that the implementations of GES and XGES in [5] differ significantly from each other, and from ours. [5] use a C++ implementation of XGES(-0) with optimized MEC operators. Our implementation, like theirs, changes the search heuristic, but does not include those optimizations. Importantly, the same optimizations could also accelerate GES, but were not used in [5], as far as we can tell.

We elaborate on why XGES is naturally expected to be slower than GES, all else being equal. First, even in [5], XGES is $\approx$10x slower than XGES-0 (Fig. 4). As [5] notes, “XGES repeatedly applies XGES-0,... one order of magnitude more score evaluations than XGES-0.” This overhead is expected: XGES forces a deletion on the output of XGES-0, restarts XGES-0 from the resulting graph, and repeats. In the worst case, it may apply all possible deletes (up to exponentially many in the node degree) to a given MEC, meaning exponentially many re-runs of XGES-0. Second, as stated, we find XGES-0 is only modestly faster than GES.

Because our simulation setup closely mirrors that of [5], we believe the discrepancy in runtime arises primarily from implementation choices. For a fair comparison, full XGES would need to be reimplemented in our codebase (as we did) or vice versa.

Our goal in this work is to advance the Pareto frontier in the accuracy/scalability tradeoff via new, principled search strategies. We believe we achieve this by providing two novel heuristics that improve both accuracy and scalability of existing GES variants. We hope this clarifies our decisions and are happy to incorporate more optimized implementations in a future version of the work.

($\dagger$) Based on this table, we revise our earlier claim about repeated phase applications: they have no significant impact on the accuracy of GES/LGES.

We appreciate your time and thoughtful feedback on our work.

Q1

Please see below some new results regarding your comment,

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.

1. 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.
2. 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.

ER1 graphs, SHD

ER1 graphs, time

ER3 graphs, SHD

ER3 graphs, time

3. 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.
4. 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:
   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.
   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.

SHD

Time

[1] 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–2464, Aug 2012.

[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.

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.

W1

1. Prop 1 complete? We appreciate the question and will revise the text to better motivate our heuristics.
   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.
   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}$.
2. Heuristics reflect Prop 1?
   1. ConservativeInsert searches exactly for a score-decreasing Insert per Prop 1.
   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).
   3. Both ConservativeInsert and SafeInsert often successfully detect non-adjacencies in practice, as suggested by their improvement on GES in Exp 5.1.

W2

LGES conducts more tests? Why is LGES faster? 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.

1. "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.
2. LGES is also faster overall due to its progression; it adds fewer edges, reducing future operator counts (exponential in the node degree).

W3

Deletion phase not optimized accordingly? A 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)).

W4

Relevance of interventions/prior knowledge? Algorithms 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.

1. “run plain GES…on all variables including the domain index.”
   1. If this method treats the domain index as a categorical root variable, then it may not be sound:
      1. Data from different interventions is not identically distributed, a core assumption in most causal discovery algorithms (including GES). This motivated GIES [1].
      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.
   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.
   3. If we misunderstand your suggestion, we would appreciate a reference so we can better address the comparison.
2. “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:
   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.
   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.
   3. Temporal ordering [6] uses a user-provided ordering to prune the search space, though its guarantees are unclear.
3. “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.

W5

Other GES variants? We appreciate the suggestion and will organize a cleaner appendix on this point.

1. SGES. We could not find a public implementation for comparison.
2. 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.
3. XGES.
   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.
   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.
   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.
4. 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.

SHD

Time

W6

SafeInsert details?

1. “$nd_Y^G$ undefined?” Thank you for the catch. We'll define this as the non-descendants of $Y$ in $G$ in the prelim.
2. “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.
3. “Unchanged score... impossible“ Correct; local consistency gives a strict score change in both directions.
4. “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.

[1] A. Hauser and P. Bühlmann. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. JMLR, 2012.

[2] A. Nazaret and D. Blei. Extremely greedy equivalence search. UAI, 2024.

[3] U. Hasan and M. O. Gani. Optimizing data-driven causal discovery using knowledge-guided search. arXiv preprint arXiv:2304.05493, 2024.

[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.

[5] N. Angelopoulos and J. Cussens. Bayesian learning of Bayesian networks with informative priors. Annals of Mathematics and Artificial Intelligence, 2008.

[6] A. C. Constantinou, Z. Guo, and N. K. Kitson. The impact of prior knowledge on causal structure learning. Knowledge and Information Systems, 2023.

[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.

[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.

[9] K. Yang, A. Katcoff, and C. Uhler. Characterizing and learning equivalence classes of causal DAGs under interventions. ICML, 2018.

[10] M. Kocaoglu, A. Jaber, K. Shanmugam, and E. Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. NeurIPS, 2019.

We greatly appreciate your feedback and positive assessment of our work.

Q1

On section 3.2’s discussion about a potential issue with ConservativeInsert.

Thank you for the perceptive question. We will revise our explanation to make this point more precise.

1. "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.

2. "...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?" It 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.