SAT-Based Causal Discovery under Weaker Assumptions

Zhalama, Jiji Zhang, Frederick Eberhardt, Wolfgang Mayer
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:671-680, 2017.

Abstract

Using the flexibility of recently developed methods for causal discovery based on Boolean satisfiability (SAT) solvers, we encode a variety of assumptions that weaken the Faithfulness assumption. The encoding results in a number of SAT-based algorithms whose asymptotic correctness relies on weaker conditions than are standardly assumed. This implementation of a whole set of assumptions in the same platform enables us to systematically explore the effect of weakening the Faithfulness assumption on causal discovery. An important effect, suggested by simulation results, is that adopting weaker assumptions greatly alleviates the problem of conflicting constraints and substantially shortens solving time. As a result, SAT-based causal discovery is potentially more scalable under weaker assumptions.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-zhalama17a, title = {{SAT}-Based Causal Discovery under Weaker Assumptions}, author = {Zhalama and Zhang, Jiji and Eberhardt, Frederick and Mayer, Wolfgang}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {671--680}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/zhalama17a/zhalama17a.pdf}, url = {https://proceedings.mlr.press/r15/zhalama17a.html}, abstract = {Using the flexibility of recently developed methods for causal discovery based on Boolean satisfiability (SAT) solvers, we encode a variety of assumptions that weaken the Faithfulness assumption. The encoding results in a number of SAT-based algorithms whose asymptotic correctness relies on weaker conditions than are standardly assumed. This implementation of a whole set of assumptions in the same platform enables us to systematically explore the effect of weakening the Faithfulness assumption on causal discovery. An important effect, suggested by simulation results, is that adopting weaker assumptions greatly alleviates the problem of conflicting constraints and substantially shortens solving time. As a result, SAT-based causal discovery is potentially more scalable under weaker assumptions.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T SAT-Based Causal Discovery under Weaker Assumptions %A Zhalama %A Jiji Zhang %A Frederick Eberhardt %A Wolfgang Mayer %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-zhalama17a %I PMLR %P 671--680 %U https://proceedings.mlr.press/r15/zhalama17a.html %V R15 %X Using the flexibility of recently developed methods for causal discovery based on Boolean satisfiability (SAT) solvers, we encode a variety of assumptions that weaken the Faithfulness assumption. The encoding results in a number of SAT-based algorithms whose asymptotic correctness relies on weaker conditions than are standardly assumed. This implementation of a whole set of assumptions in the same platform enables us to systematically explore the effect of weakening the Faithfulness assumption on causal discovery. An important effect, suggested by simulation results, is that adopting weaker assumptions greatly alleviates the problem of conflicting constraints and substantially shortens solving time. As a result, SAT-based causal discovery is potentially more scalable under weaker assumptions. %Z Reissued by PMLR on 04 October 2026.
APA
Zhalama, , Zhang, J., Eberhardt, F. & Mayer, W.. (2017). SAT-Based Causal Discovery under Weaker Assumptions. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:671-680 Available from https://proceedings.mlr.press/r15/zhalama17a.html. Reissued by PMLR on 04 October 2026.

Related Material