# Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations

arXiv: https://arxiv.org/abs/1506.02113 · HTML: https://mlsanity.com/paper/1506.02113/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2015.

## Built on by (most cited first, 14 of 14)

- [Deep End-to-end Causal Inference](https://mlsanity.com/paper/2202.02195/) (2022)
- [Discovering Causal Relations and Equations from Data](https://mlsanity.com/paper/2305.13341/) (2023)
- [A Survey on Causal Discovery Methods for I.I.D. and Time Series Data](https://mlsanity.com/paper/2303.15027/) (2023)
- [ALCM: Autonomous LLM-Augmented Causal Discovery Framework](https://mlsanity.com/paper/2405.01744/) (2024)
- [Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventions](https://mlsanity.com/paper/2211.14897/) (2022)
- [Causal Discovery from Time Series with Hybrids of Constraint-Based and Noise-Based Algorithms](https://mlsanity.com/paper/2306.08765/) (2023)
- [Extremely Greedy Equivalence Search](https://mlsanity.com/paper/2502.19551/) (2025)
- [CausalMACE: Causality Empowered Multi-Agents in Minecraft Cooperative Tasks](https://mlsanity.com/paper/2508.18797/) (2025)
- [Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrapper](https://mlsanity.com/paper/2107.05001/) (2021)
- [Optimizing Data-driven Causal Discovery Using Knowledge-guided Search](https://mlsanity.com/paper/2304.05493/) (2023)
- [Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning](https://mlsanity.com/paper/2510.04970/) (2025)
- [Greedy equivalence search for nonparametric graphical models](https://mlsanity.com/paper/2406.17228/) (2024)
- [Less Greedy Equivalence Search](https://mlsanity.com/paper/2506.22331/) (2025)
- [CaM-Wolf: Causal-Aware Multimodal Agents for Social Deduction Games](https://mlsanity.com/paper/2607.26393/) (2026)

## Abstract (arXiv)

We introduce Selective Greedy Equivalence Search (SGES), a restricted version of Greedy Equivalence Search (GES). SGES retains the asymptotic correctness of GES but, unlike GES, has polynomial performance guarantees. In particular, we show that when data are sampled independently from a distribution that is perfect with respect to a DAG cal G defined over the observable variables then, in the limit of large data, SGES will identify cal G's equivalence class after a number of score evaluations that is (1) polynomial in the number of nodes and (2) exponential in various complexity measures including maximum-number-of-parents, maximum-clique-size, and a new measure called em v-width that is at least as small as---and potentially much smaller than---the other two. More generally, we show that for any hereditary and equivalence-invariant property Pi known to hold in cal G, we retain the large-sample optimality guarantees of GES even if we ignore any GES deletion operator during the backward phase that results in a state for which Pi does not hold in the common-descendants subgraph.