BishtRef
Articles Journals Publishers Authors Subjects Most Cited New Papers Year Stats Open Access
journal article Nov 21, 2022

D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery

Matthew J. Vowels ORCID Necati Cihan Camgoz ORCID Richard Bowden ORCID
ACM Computing Surveys Vol. 55 No. 4 pp. 1-36 · Association for Computing Machinery (ACM)
View at Publisher Save 10.1145/3527154
Abstract
Causal reasoning is a crucial part of science and human intelligence. In order to discover causal relationships from data, we need structure discovery methods. We provide a review of background theory and a survey of methods for structure discovery. We primarily focus on modern, continuous optimization methods, and provide reference to further resources such as benchmark datasets and software packages. Finally, we discuss the assumptive leap required to take us from structure to causality.
Topics

No keywords indexed for this article. Browse by subject →

References
284
[1]
O. Ahmed, F. Träuble, A. Goyal, A. Neitz, M. Wütrich, Y. Bengio, B. Schölkopf, and S. Bauer. 2020. CausalWorld: A robotic manipulation benchmark for causal structure and transfer learning. arXiv:2010.04296v1 (2020).
[4]
B. Aragam and Q. Zhou. 2015. Concave penalized estimation of sparse Gaussian Bayesian networks. Journal of Machine Learning Research 16 (2015).
[5]
H. Araki (Ed.). [n.d.]. International Symposium on Mathematical Problems in Theoretical Physics. Springer-Verlag, New York, Chapter Lecture Notes in Physics. 39.
[6]
M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz. 2020. Invariant risk minimization. arXiv:1907.02893v3 (2020).
[7]
H. Ashton. 2020. Causal Campbell-Goodhart’s law and reinforcement learning. arXiv:2011.01010v1 (2020).
[8]
O. Banerjee, L. El Ghaoui, and A. d’Aspremont. 2008. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. Journal of Machine Learning Research 9 (2008).
[9]
Emergence of Scaling in Random Networks

Albert-László Barabási, Réka Albert

Science 10.1126/science.286.5439.509
[10]
E. Bareinboim, J. D. Correa, D. Ibeling, and T. Icard. 2020. On Pearl’s Hierarchy and the foundations of causal inference. ACM Special Reports (2020).
[11]
P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santori, R. Faulkner, C. Gulcehre, F. Song, A. Ballard, J. Gilmer, G. Dahl, A. Vaswani, K. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. 2018. Relational inductive biases, deep learning, and graph networks. arXiv:1806.01261v2 (2018).
[12]
D. Beaini, S. Passaro, V. Létourneau, W. L. Hamilton, G. Corso, and P. Liò. 2020. Directional graph networks. arXiv:2010.02863v2 (2020).
[13]
M. B. Bear, C. Fan, D. Mrowca, Y. Li, S. Alter, A. Nayebi, J. Schwartz, L. Fei-Fei, J. Wu, J. B. Tenenbaum, and D. L. K. Yamis. 2020. Learning physical graph representations from visual scenes. arXiv:2006.12373v2 (2020).
[14]
I. A. Beinlich, H. J. Suermondt, R. M. Chavez, and G. F. Cooper. 1989. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine (1989).
[15]
A. Bellot and M. van der Schaar. 2019. Conditional independence testing using generative adversarial networks. arXiv:1907.04068v1 (2019).
[16]
Y. Bengio. 2019. The consciousness prior. arXiv:1709.08568v2 (2019).
[17]
Representation Learning: A Review and New Perspectives

Y. Bengio, A. Courville, P. Vincent

IEEE Transactions on Pattern Analysis and Machine... 10.1109/tpami.2013.50
[18]
Y. Bengio, T. Deleu, N. Rahaman, N. R. Ke, S. Lachapelle, O. Bilaniuk, A. Goyal, and C. Pal. 2019. A meta-transfer objective for learning to disentangle causal mechanisms. arXiv:1901.10912v2 (2019).
[19]
R. Bhattacharya, T. Nagarajan, D. Malinsky, and I. Shpitset. 2020. Differentiable causal discovery under unmeasured confounding. arXiv:2010.06978v1 (2020).
[20]
D. M. Blei, A. Kucukelbir, and J. D. McAuliffe. 2018. Variational inference: A review for statisticians. arXiv:1601.00670v9 (2018).
[21]
P. Bloebaum, D. Janzing, T. Washio, S. Shimizu, and B. Schölkopf. 2018. Cause-effect inference by comparing regression errors. Int. Conf. on Artificial Intelligence and Statistics (2018), 900–909.
[22]
L. Bottou, J. Peters, J. Quinonero-Candela, D. X. Charles, D. M. Chickering, E. Portugaly, D. Ray, P. Simard, and E. Snelson. 2013. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research 14 (2013).
[27]
C. P. Burgess, L. Matthey, N. Watters, R. Kabra, I. Higgins, M. Botvinick, and A. Lerchner. 2019. MONet: Unsupervised scene decomposition and representation. arXiv:1901.11390v1 (2019).
[28]
A Limited Memory Algorithm for Bound Constrained Optimization

Richard H. Byrd, Peihuang Lu, Jorge Nocedal et al.

SIAM Journal on Scientific Computing 10.1137/0916069
[29]
R. Cai, J. Qiao, K. Zhang, Z. Zhang, and Z. Hao. 2019. Causal discovery with cascade nonlinear additive noise model. Proceedings of the 28th International Joint Conference on Artificial Intelligence (2019).
[30]
D. C. Castro, I. Walker, and B. Glocker. 2019. Causality matters in medical imaging. arXiv:1912.08142v1 (2019).
[32]
D. Chicharro, M. Besserve, and S. Panzeri. 2020. Causal learning with sufficient statistics: An information bottleneck approach. arXiv:2010.05375v1 (2020).
[33]
D. M. Chickering. 1996. Learning from Data. Lecture Notes in Statistics, Vol 112. Springer, New York, Chapter Learning Bayesian networks is NP-complete.
[34]
D. M. Chickering. 2002. Optimal structure identification with greedy search. Journal of Machine Learning Research 3(Nov.2002).
[35]
J. Choi, R. Chapkin, and Y. Ni. 2020. Bayesian causal structure learning with zero-inflated Poisson Bayesian networks. 34th Conference on Neural Information Processing Systems (2020).
[36]
D. Colombo and M. H. Maathuis. 2014. Order-independent constraint-based causal structure learning. Journal of Machine Learning Research 15 (2014).
[38]
A Bayesian method for the induction of probabilistic networks from data

Gregory F. Cooper, Edward Herskovits

Machine Learning 10.1007/bf00994110
[39]
O. Corcoll and R. Vicente. 2020. Disentangling causal effects for hierarchical reinforcement learning. arXiv:2010.01351v1 (2020).
[41]
A. P. Dawid. 2008. Beware of the DAG!NeurIPS Workshop on Causality (2008).
[42]
P. de Haan, D. Jayaraman, and S. Levine. 2019. Causal confusion in imitation learning. 33rd Conference on Neural Information Processing Systems (2019).
[43]
M. de Jongh and M. J. Druzdzel. 2009. A comparison of structural distance measures for causal Bayesian network models. Recent Advances in Intelligent Information Systems (2009).
[44]
Understanding and misunderstanding randomized controlled trials

Angus Deaton, Nancy Cartwright

Social Science & Medicine 10.1016/j.socscimed.2017.12.005
[45]
D. Ding, F. Hill, A. Santoro, and M. Botvinick. 2020. Object-based attention for spatio-temporal reasoning: Outperforming neuro-symbolic models with flexible distributed architectures. arXiv:2012.08508v1 (2020).
[46]
M. Drton, M. Eichler, and T. S. Richardson. 2009. Computing maximum likelihood estimates in recursive linear models with correlated errors. Journal of Machine Learning Research 10, 10 (2009).
[47]
D. Eaton and K. Murphy. 2007. Exact Bayesian structure learning from uncertain interventions. AISTATS (2007).
[50]
S. Ehrhardt, O. Groth, A. Monszpart, M. Engelcke, I. Posner, N. Mitra, and A. Vedaldi. 2020. RELATE: Physically plausible multi-object scene synthesis using structured latent spaces. arXiv:2007.01272v1 (2020).

Showing 50 of 284 references

Cited By
159
Causal Graphical Models and Their Applications

Luis Enrique Sucar, David Danks · 2026

Entropy
Metrics
159
Citations
284
References
Details
Published
Nov 21, 2022
Vol/Issue
55(4)
Pages
1-36
License
View
Authors
M
Matthew J. Vowels

CVSSP, University of Surrey, Guildford, U.K.

N
Necati Cihan Camgoz

CVSSP, University of Surrey, Guildford, U.K.

R
Richard Bowden

CVSSP, University of Surrey, Guildford, U.K.

Cite This Article
Matthew J. Vowels, Necati Cihan Camgoz, Richard Bowden (2022). D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery. ACM Computing Surveys, 55(4), 1-36. https://doi.org/10.1145/3527154
Related

You May Also Like

Data clustering

A. K. Jain, M. N. Murty · 1999

9,568 citations

Anomaly detection

Varun Chandola, Arindam Banerjee · 2009

8,799 citations

Machine learning in automated text categorization

Fabrizio Sebastiani · 2002

5,027 citations

Object tracking

Alper Yilmaz, Omar Javed · 2006

3,632 citations

A Survey on Bias and Fairness in Machine Learning

Ninareh Mehrabi, Fred Morstatter · 2021

3,466 citations