Efficient Greedy Equivalence Search for Non-Score-Equivalent Criteria using Sampling

Greedy Equivalence Search (GES) is a standard score-based causal discovery algorithm that searches over Markov Equivalence Classes (MECs). Its efficient implementation applies local MEC operators without enumerating all Directed Acyclic Graphs (DAGs), and is sound and complete under score-equivalent criteria such as BIC. We show that this version can fail for non-score-equivalent criteria and propose SGES to address this issue. SGES samples DAGs from the MEC at each step of forward and backward search and scores candidate operations individually. This lets non-score-equivalent criteria exploit directional information, with the sampling rate interpolating between efficient and original GES. We perform initial experiments to show SGES finds more accurate causal structures than GES when score equivalence is violated, and outline future directions for a PAC-style SGES.