Causal Discovery Algorithms

21 Sep 2023 13:01

---

Yet Another Inadequate Placeholder, because I should really split Graphical Causal Models into (at least) two notebooks, this being one.

Things I need to think/learn more about:

1. How important is faithfulness? How unreasonable is it, and what strictly weaker assumptions will do (most of) the same work?
2. Confidence sets for the causal graph. The simplest approach is to go over every possible graph, test it, and return the ones which pass the test. But this is computationally infeasible (the number of graphs grows crazily fast with the number of variables) and hard to interpret. Are there more comprehensible representations possible, and/or ones which would make this more computationally tractable?

Recommended, big picture:
• Peter Spirtes, Clark Glymour and Richard Scheines, Causation, Prediction, and Search [Comments]

Recommended, close-ups:
• Séverine Affeldt and Hervé Isambert, "Robust reconstruction of causal graphical models based on conditional 2-point and 3-point information", UAI 2015
• Wenyu Chen, Mathias Drton, Ali Shojaie, "Causal Structural Learning via Local Graphs", arxiv:2107.03597
• Tianjiao Chu and Clark Glymour, "Search for Additive Nonlinear Time Series Causal Models", Journal of Machine Learning Research 9 (2008): 967--991
• Diego Colombo, Marloes H. Maathuis, Markus Kalisch, and Thomas S. Richardson, "Learning High-Dimensional Directed Acyclic Graphs with Latent and Selection Variables", Annals of Statistics 40 (2012): 294--321, arxiv:1104.5617
• Nicola Gnecco, Nicolai Meinshausen, Jonas Peters, Sebastian Engelke, "Causal discovery in heavy-tailed models", arxiv:1908.05097
• Dominik Janzing and Daniel J. L. Herrmann, "Reliable and Efficient Inference of Bayesian Networks from Sparse Data by Statistical Learning Theory", cs.LG/0309015
• Markus Kalisch and Peter Bühlmnann, "Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm", Journal of Machine Learning Research 8 (2007): 616--636
• Marloes H. Maathuis, Markus Kalisch, Peter Bühlmann, "Estimating high-dimensional intervention effects from observational data", Annals of Statistics 37 (2009): 3133--31654, arxiv:0810.4214
• Katerina Marazopoulou, Marc Maier and David Jensen, "Learning the Structure of Causal Models with Relational and Temporal Dependence", UAI 2015
• Garvesh Raskutti, Caroline Uhler, "Learning directed acyclic graphs based on sparsest permutations", arxiv:1307.0366
• Thomas Richardson
  • "A Discovery Algorithm for Directed Cyclic Graphs", UAI 1996 [Short version without details]
  • "A Discovery Algorithm for Directed Cyclic Graphs", Technical Report 68, CMU department of philosophy (postscript) [Long version with details]
• Arjun Sondhi, Ali Shojaie, "The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks", arxiv:1806.06209
• Eric V. Strobl, Kun Zhang, Shyam Visweswaran, "Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery", Journal of Causal Inference 7 (2019): 20180017, arxiv:1702.03877
• Robert E. Tillman, Arthur Gretton and Peter Spirtes, "Nonlinear Directed Acyclic Structure Learning with Weakly Additive Noise Models", NIPS 2009 [Thanks to Prof. Spirtes for a preprint]
• Pawel Wocjan, Dominik Janzing, and Thomas Beth, "Required sample size for learning sparse Bayesian networks with many variables," cs.LG/0204052

Modesty forbids me to recommend:
• CRS, Advanced Data Analysis from an Elementary Point of View, Part III (chapters on causal discovery for undergraduate statistics students)
• Octavio César Mesner, Alex Davis, Elizabeth Casman, Hyagriv Simhan, CRS, Lauren Keenan-Devlin, Ann Borders and Tamar Krishnamurt, "Using graph learning to understand adverse pregnancy outcomes and stress pathways", PLoS One 14 (2019): e0223319

To read:
• Constantin F. Aliferis, Alexander Statnikov, Ioannis Tsamardinos, Subramani Mani, Xenofon D. Koutsoukos, "Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification"
  • "Part I: Algorithms and Empirical Evaluation", Journal of Machine Learning Research 11 (2010): 171--234
  • "Part II: Analysis and Extensions", Journal of Machine Learning Research 11 (2010): 235--284
• Holly Andersen, "When to expect violations of causal faithfulness and why it matters", phil-sci/9204
• Mona Azadkia, Armeen Taeb, Peter Büülmann, "A Fast Non-parametric Approach for Local Causal Structure Learning", arxiv:2111.14969
• Facuno Bromberg and Dimitris Margaritis, "Improving the Reliability of Causal Discovery from Small Data Sets Using Argumentation", Journal of Machine Learning Research 10 (2009): 301--340
• Peter Bühlmann, Jonas Peters, Jan Ernest, "CAM: Causal additive models, high-dimensional order search and penalized regression", Annals of Statistics 42 (2014): 2526--2556, arxiv:1310.1533
• Wenyu Chen, Mathias Drton, Y Samuel Wang, "On causal discovery with an equal-variance assumption ", Biometrika 106 (2019): 973--980
• David Maxwell Chickering, "Optimal Structure Identification With Greedy Search," Journal of Machine Learning Research 3 (2002): 507--554
• Luis M. de Campos, "A Scoring Function for Learning Bayesian Networks based on Mutual Information and Conditional Independence Tests", Journal of Machine Learning Research 7 (2006): 2149--2187
• Mathias Drton and Marloes H. Maathuis, "Structure Learning in Graphical Modeling" Annual Review of Statistics and Its Application 4 (2017): 365--393
• Robin J. Evans, "Model selection and local geometry", Annals of Statistics 48 (2020): 3513--3544, arxiv:1801.08364
• Ming Gao, Yi Ding, Bryon Aragam, "A polynomial-time algorithm for learning nonparametric causal graphs", arxiv:2006.11970
• Enrico Giudice, Jack Kuipers, Giusi Moffa, "The Dual PC Algorithm for Structure Learning", arxiv:2112.09036
• Glymour and Cooper (eds.), Computation, Causation and Discovery
• Siyuan Guo, Jonas Wildberger, Bernhard Schölkopf, "Out-of-Variable Generalization", arxiv:2304.07896
• Naftali Harris, Mathias Drton, "PC Algorithm for Nonparanormal Graphical Models", Journal of Machine Learning Research 14 (2013): 3365--3383
• Alain Hauser, Peter Bühlmann, "Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs", Journal of Machine Learning Research 13 (2012): 2409--2464, arxiv:1104.2808
• Yang-Bo He and Zhi Geng, "Active Learning of Causal Networks with Intervention Experiments and Optimal Designs", Journal of Machine Learning Research 9 (2008): 2523--2547
• Biwei Huang, Kun Zhang, Mingming Gong, Clark Glymour, "Causal Discovery and Forecasting in Nonstationary Environments with State-Space Models", arxiv:1905.10857
• Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, Bernhard Schölkopf, "Causal Discovery from Heterogeneous/Nonstationary Data with Independent Changes", arxiv:1903.01672
• Antti Hyttinen, Frederick Eberhardt, Patrik O. Hoyer, "Experiment Selection for Causal Discovery", Journal of Machine Learning Research 14 (2013): 3041--3071
• Markus Kalisch and Peter Bühlmnann, "Robustification of the PC-Algorithm for Directed Acyclic Graphs", Journal of Computational and Graphical Statistics 17 (2008): 773--789
• Xiaohan Kang, Bruce Hajek, "Lower Bounds on Information Requirements for Causal Network Inference", arxiv:2102.00055
• Grigor Keropyan, David Strieder, Mathias Drton, "Rank-Based Causal Discovery for Post-Nonlinear Models", arxiv:2302.12341
• Thuc Duy Le, Lin Liu, Emre Kiciman, Sofia Triantafyllou and Huan Liu (eds.), proceedings of The KDD'22 Workshop on Causal Discovery
• Manuele Leonelli, Gherardo Varando, "Context-Specific Causal Discovery for Categorical Data Using Staged Trees", arxiv:2106.04416
• Junning Li, Z. Jane Wang, "Controlling the False Discovery Rate of the Association/Causality Structure Learned with the PC Algorithm", Journal of Machine Learning Research 10 (2009): 475--514
• Svante Linusson, Petter Restadh, Liam Solus, "Greedy Causal Discovery is Geometric", arxiv:2103.03771
• Po-Ling Loh, Peter Bühlmann, "High-dimensional learning of linear causal networks via inverse covariance estimation", arxiv:1311.3492
• Dhafer Malouche and Sylvie Sevestre-Ghalila, "Estimating High dimensional faithful Gaussian graphical Models : uPC-algorithm", arxiv:0705.1613
• Daniel McDuff, Yale Song, Jiyoung Lee, Vibhav Vineet, Sai Vemprala, Nicholas Gyde, Hadi Salman, Shuang Ma, Kwanghoon Sohn, Ashish Kapoor, "CausalCity: Complex Simulations with Agency for Causal Discovery and Reasoning", arxiv:2106.13364
• Jean-Philippe Pellett and Andre Elisseeff, "Using Markov Blankets for Causal Structure Learning", Journal of Machine Learning Research 9 (2008): 1295--1342
• Ronan Perry, Julius von Kügelgen, Bernhard Schölkopf, "Causal Discovery in Heterogeneous Environments Under the Sparse Mechanism Shift Hypothesis", arxiv:2206.02013
• Sergey Plis, David Danks and Jianyu Yang, "Mesochronal Structure Learning", UAI 2015
• Anant Raj, Luigi Gresele, Michel Besserve, Bernhard Schölkopf, Stefan Bauer, "Orthogonal Structure Search for Efficient Causal Discovery from Observational Data", arxiv:1903.02456
• Kayvan Sadeghi, Terry Soo, "Conditions and Assumptions for Constraint-based Causal Structure Learning", arxiv:2103.13521
• Silva, Scheines, Glymour and Spirtes, "Learning the Structure of Linear Latent Variable Models", Journal of Machine Learning Research 7 (2006): 191--246
• L. Solus, Y. Wang and C. Uhler, "Consistency guarantees for greedy permutation-based causal inference algorithms", Biometrika 108 (2021): 795--814
• Peter Spirtes, Jiji Zhang, "A Uniformly Consistent Estimator of Causal Effects under the $k$-Triangle-Faithfulness Assumption", Statistical Science 29 (2014): 662--678
• David Strieder, Tobias Freidling, Stefan Haffner, Mathias Drton, "Confidence in Causal Discovery with Linear Causal Models", arxiv:2106.05694
• Sara van de Geer, Peter Bühlmann, "$\ell_0$-penalized maximum likelihood for sparse directed acyclic graphs", arxiv:1205.5473
• David S. Watson, Ricardo Silva, "Causal discovery under a confounder blanket", arxiv:2205.05715
• Xianchao Xie, Zhi Geng, "A Recursive Method for Structural Learning of Directed Acyclic Graphs", Journal of Machine Learning Research 9 (2008): 459--483
• Raanan Yehezkel, Boaz Lerner, "Bayesian Network Structure Learning by Recursive Autonomy Identification", Journal of Machine Learning Research 10 (2009): 1527--1570
• Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, Eric P. Xing, "Learning Sparse Nonparametric DAGs", arxiv:1909.13189

To write:
• CRS, "An Apology for Causal Discovery", expanding on two talks, "Lessons (?) for causal discovery from Markov models" and "Commentary on Kun Zhang"