Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure

Antti Hyttinen, Patrik Hoyer, Frederick Eberhardt, Matti Järvisalo
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:451-460, 2013.

Abstract

We present a very general approach to learning the structure of causal models based on d-separation constraints, obtained from any given set of overlapping passive observational or experimental data sets. The procedure allows for both directed cycles (feedback loops) and the presence of latent variables. Our approach is based on a logical representation of causal pathways, which permits the integration of quite general background knowledge, and inference is performed using a Boolean satisfiability (SAT) solver. The procedure is complete in that it exhausts the available information on whether any given edge can be determined to be present or absent, and returns “unknown” otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to circumstances in which one or more restricting assumptions apply. Simulations illustrate the effect of these assumptions on discovery and how the present algorithm scales.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-hyttinen13a, title = {Discovering Cyclic Causal Models with Latent Variables: A General {SAT}-Based Procedure}, author = {Hyttinen, Antti and Hoyer, Patrik and Eberhardt, Frederick and J{\"a}rvisalo, Matti}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {451--460}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/hyttinen13a/hyttinen13a.pdf}, url = {https://proceedings.mlr.press/r11/hyttinen13a.html}, abstract = {We present a very general approach to learning the structure of causal models based on d-separation constraints, obtained from any given set of overlapping passive observational or experimental data sets. The procedure allows for both directed cycles (feedback loops) and the presence of latent variables. Our approach is based on a logical representation of causal pathways, which permits the integration of quite general background knowledge, and inference is performed using a Boolean satisfiability (SAT) solver. The procedure is complete in that it exhausts the available information on whether any given edge can be determined to be present or absent, and returns “unknown” otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to circumstances in which one or more restricting assumptions apply. Simulations illustrate the effect of these assumptions on discovery and how the present algorithm scales.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure %A Antti Hyttinen %A Patrik Hoyer %A Frederick Eberhardt %A Matti Järvisalo %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-hyttinen13a %I PMLR %P 451--460 %U https://proceedings.mlr.press/r11/hyttinen13a.html %V R11 %X We present a very general approach to learning the structure of causal models based on d-separation constraints, obtained from any given set of overlapping passive observational or experimental data sets. The procedure allows for both directed cycles (feedback loops) and the presence of latent variables. Our approach is based on a logical representation of causal pathways, which permits the integration of quite general background knowledge, and inference is performed using a Boolean satisfiability (SAT) solver. The procedure is complete in that it exhausts the available information on whether any given edge can be determined to be present or absent, and returns “unknown” otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to circumstances in which one or more restricting assumptions apply. Simulations illustrate the effect of these assumptions on discovery and how the present algorithm scales. %Z Reissued by PMLR on 04 October 2026.
APA
Hyttinen, A., Hoyer, P., Eberhardt, F. & Järvisalo, M.. (2013). Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:451-460 Available from https://proceedings.mlr.press/r11/hyttinen13a.html. Reissued by PMLR on 04 October 2026.

Related Material