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

Max Chickering, Chris Meek
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:771-779, 2015.

Abstract

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 $\Gr$ defined over the observable variables then, in the limit of large data, SGES will identify $\Gr$’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 necessarily not larger—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 $\Gr$, we retain the large-sample optimality guarantees of GES even if we ignore any GES deletion operator that results in a state for which $\Pi$ does not hold in the common-descendants subgraph.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-chickering15a, title = {Selective Greedy Equivalence Search: Finding Optimal {B}ayesian Networks Using a Polynomial Number of Score Evaluations}, author = {Chickering, Max and Meek, Chris}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {771--779}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/chickering15a/chickering15a.pdf}, url = {https://proceedings.mlr.press/r13/chickering15a.html}, abstract = {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 $\Gr$ defined over the observable variables then, in the limit of large data, SGES will identify $\Gr$’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 necessarily not larger—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 $\Gr$, we retain the large-sample optimality guarantees of GES even if we ignore any GES deletion operator that results in a state for which $\Pi$ does not hold in the common-descendants subgraph.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations %A Max Chickering %A Chris Meek %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-chickering15a %I PMLR %P 771--779 %U https://proceedings.mlr.press/r13/chickering15a.html %V R13 %X 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 $\Gr$ defined over the observable variables then, in the limit of large data, SGES will identify $\Gr$’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 necessarily not larger—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 $\Gr$, we retain the large-sample optimality guarantees of GES even if we ignore any GES deletion operator that results in a state for which $\Pi$ does not hold in the common-descendants subgraph. %Z Reissued by PMLR on 04 October 2026.
APA
Chickering, M. & Meek, C.. (2015). Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:771-779 Available from https://proceedings.mlr.press/r13/chickering15a.html. Reissued by PMLR on 04 October 2026.

Related Material