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 learn- ing 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 al- lows for both directed cycles (feedback loops) and the presence of latent variables. Our ap- proach is based on a logical representation of causal pathways, which permits the integra- tion 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 in- formation on whether any given edge can be determined to be present or absent, and re- turns “unknown” otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to cir- cumstances 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 learn- ing 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 al- lows for both directed cycles (feedback loops) and the presence of latent variables. Our ap- proach is based on a logical representation of causal pathways, which permits the integra- tion 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 in- formation on whether any given edge can be determined to be present or absent, and re- turns “unknown” otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to cir- cumstances 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 learn- ing 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 al- lows for both directed cycles (feedback loops) and the presence of latent variables. Our ap- proach is based on a logical representation of causal pathways, which permits the integra- tion 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 in- formation on whether any given edge can be determined to be present or absent, and re- turns “unknown” otherwise. Many existing constraint-based causal discovery algorithms can be seen as special cases, tailored to cir- cumstances 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