{ "id": "ep3vkgh1jz", "slug": "causal-structure-learning", "title": "Causal structure learning", "updated": "2026-09-30", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_computation" }, { "id": "technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_methods" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.ml_methods", "label": "Non-geographic · 1946 to 2000: Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_methods", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_methods" } ] }, { "id": "geo.nongeo.t2001.technology.computing.ai.ml_methods", "label": "Non-geographic · 2001 to 2020: Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.ml_methods", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t2001.technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.ml_methods" } ] } ], "excerpt": "Causal structure learning is a machine learning method that infers a causal graph, typically a directed acyclic graph, among variables from observational or interventional data.", "snippet": "Causal structure learning is a machine learning method that infers a causal graph, typically a directed acyclic graph, among variables from observational or interventional data.", "node": "technology.computing.ai.ml_methods", "markdown": "# Causal structure learning\n\nCausal structure learning infers a causal graph, typically a directed acyclic graph (DAG), among a set of variables from observational or interventional data. Because observational data alone usually identify only a Markov equivalence class (MEC) rather than a single DAG, the output is commonly a completed partially directed acyclic graph (CPDAG) representing all DAGs with the same conditional independencies.[1](https://link.springer.com/article/10.1007/s10208-022-09581-9) The IDA method of Marloes Maathuis and colleagues, published in [Nature Methods](https://www.edgepedia.org/nature-methods) in 2010, estimates intervention effects in large-scale systems from observational data this way.[2](https://doi.org/10.1038/nmeth0410-247)\n\n| Key fact | Detail |\n|---|---|\n| Typical output | A Markov equivalence class (CPDAG), not a unique DAG; interventions refine it to an I-MEC and, with enough interventions, the full DAG[1](https://link.springer.com/article/10.1007/s10208-022-09581-9) |\n| Core assumptions | Causal sufficiency (no unmeasured confounders), the causal Markov condition, and faithfulness[3](https://medinform.jmir.org/2023/1/e38266) |\n| NOTEARS constraint | A matrix \\( W \\) is a DAG iff \\( h(W) = \\mathrm{tr}(e^{W \\circ W}) - d = 0 \\)[4](https://doi.org/10.48550/arxiv.1803.01422) |\n| Search complexity | Finding the highest-scoring DAG is NP-hard[5](https://jmlr.org/papers/volume5/chickering04a/chickering04a.pdf) |\n| Scaling barrier | PC's complexity is proportional to \\( 2^{20000} \\) for 20,000-gene RNA-seq data, which is infeasible[3](https://medinform.jmir.org/2023/1/e38266) |\n| Speed gain | DAGMA's log-determinant acyclicity runs in practice about an order of magnitude faster than trace-exponential and polynomial characterizations[6](https://doi.org/10.48550/arxiv.2209.08037) |\n\n## How it works\n\nThe global [Markov property](https://www.edgepedia.org/markov-property) states that all d-separations (graph criterion for when variables are statistically independent) in the graph hold as conditional independencies in the distribution; faithfulness is exactly the converse, that all conditional independence statements in the distribution must hold as d-separations in the graph.[1](https://link.springer.com/article/10.1007/s10208-022-09581-9)\n\nTwo algorithmic principles dominate. Constraint-based methods such as PC and FCI test conditional independencies to build a skeleton and then orient edges by orientation rules.[7](https://ar5iv.labs.arxiv.org/html/1910.08527) Score-based methods evaluate candidate graphs with a predefined score such as BIC; finding the highest-scoring DAG is generally NP-hard, so exact approaches use dynamic programming, A*-style search, or integer linear programming (for example GOBNILP).[1](https://link.springer.com/article/10.1007/s10208-022-09581-9) Identifiability of the full DAG beyond the equivalence class requires restricted model classes: linear non-Gaussian models, linear Gaussian models with equal noise variances, post-nonlinear models, and restricted additive noise models are identifiable.[7](https://ar5iv.labs.arxiv.org/html/1910.08527)\n\n## How it is done\n\nA constraint-based run starts from a complete undirected graph and recursively deletes edges using conditional independence tests with conditioning sets of increasing cardinality, then orients v-structures (three-node patterns used to orient causal edges) and applies Meek rules.[8](https://stat.ethz.ch/Manuscripts/buhlmann/pcalgo2.pdf) A score-based run such as GES greedily searches the space of CPDAGs optimizing the BIC under a linear Gaussian model.[9](https://ar5iv.labs.arxiv.org/html/1906.02226)\n\nThe continuous-optimization workflow introduced by NOTEARS proceeds in three steps: converting the constrained problem into a sequence of unconstrained subproblems, optimizing them, and thresholding the resulting weight matrix; the acyclicity function and its gradient require only an \\( O(d^{3}) \\) matrix exponential.[4](https://doi.org/10.48550/arxiv.1803.01422) Edge extraction uses a thresholding value of 0.3, following the recommendation in the NOTEARS paper.[10](https://proceedings.mlr.press/v97/yu19a/yu19a.pdf) DAGMA drops the augmented Lagrangian in favor of a central-path (barrier) approach, with the solution guaranteed to be a DAG at the limit of the central path.[6](https://doi.org/10.48550/arxiv.2209.08037)\n\n## Origin\n\nThe SGS algorithm is credited to Spirtes, Glymour, and Scheines's book *Causation, Prediction, and Search* ([MIT Press](https://www.edgepedia.org/mit-press), 2001).[11](https://doi.org/10.7551/mitpress/1754.001.0001) GES was reported by David Maxwell Chickering in 2002, in *Optimal Structure Identification with Greedy Search* (JMLR).[22](https://www.jmlr.org/papers/volume3/chickering02b/chickering02b.pdf) • [12](https://causal-learn.readthedocs.io/en/latest/search_methods_index/Score-based%20causal%20discovery%20methods/GES.html) LiNGAM was reported by Shohei Shimizu and colleagues in 2006 (JMLR).[13](https://www.annualreviews.org/content/journals/10.1146/annurev-statistics-031017-100630) DirectLiNGAM was reported by Shohei Shimizu and colleagues in 2011 (arXiv).[14](https://doi.org/10.48550/arxiv.1101.2489) IDA was reported by Marloes Maathuis and colleagues in 2010 (Nature Methods).[2](https://doi.org/10.1038/nmeth0410-247) NOTEARS was reported by Xun Zheng and colleagues in 2018 (arXiv).[4](https://doi.org/10.48550/arxiv.1803.01422) DAG-GNN was reported by Yue Yu and colleagues in 2019 (arXiv),[15](https://doi.org/10.48550/arxiv.1904.10098) GraN-DAG by Sébastien Lachapelle and colleagues in 2019 (arXiv),[16](https://doi.org/10.48550/arxiv.1906.02226) and DYNOTEARS by Roxana Pamfil and colleagues in 2020 (arXiv).[17](https://doi.org/10.48550/arxiv.2002.00498) DAGMA was reported by Kevin Bello, Bryon Aragam, and Pradeep Ravikumar in 2022 (arXiv).[6](https://doi.org/10.48550/arxiv.2209.08037) The order-independent PC-Stable refinement was reported by Diego Colombo and Marloes Maathuis in 2014 (arXiv).[18](https://doi.org/10.5555/2627435.2750365)\n\n## Variants\n\n**Constraint-based.** FCI modifies PC to detect unknown confounding variables and produces asymptotically correct results; RFCI skips FCI's most time-consuming step, gaining speed at the cost of a high false positive rate.[3](https://medinform.jmir.org/2023/1/e38266) GFCI combines GES, which supplies a skeleton supergraph, with FCI pruning and orientation.[19](https://appliedcausalinference.github.io/aci_book/04-causal-discovery.html)\n\n**Score-based and functional.** Exact searches (dynamic programming, A*, GOBNILP) trade runtime for guarantees.[1](https://link.springer.com/article/10.1007/s10208-022-09581-9) Functional methods such as LiNGAM and DirectLiNGAM exploit non-Gaussianity: DirectLiNGAM produces more stable and reliable results than ICA-LiNGAM but is computationally slower and assumes strict linearity and non-Gaussianity.[20](https://arxiv.org/pdf/2407.13054)\n\n**Gradient-based and masked.** DAG-GNN uses a variational autoencoder with graph neural network encoder and decoder whose score is the evidence lower bound (ELBO), and derives an alternative acyclicity constraint avoiding the matrix exponential.[10](https://proceedings.mlr.press/v97/yu19a/yu19a.pdf) GraN-DAG extends the NOTEARS framework to nonlinear relationships using neural networks, applying the acyclicity argument at the level of neural network paths.[9](https://ar5iv.labs.arxiv.org/html/1906.02226) GOLEM is a continuous likelihood-based method with soft sparsity and DAG constraints, using Adam and GPU acceleration with post-processing to remove low-weight edges.[20](https://arxiv.org/pdf/2407.13054) DAGMA replaces the trace-exponential acyclicity with a log-determinant ([M-matrix](https://www.edgepedia.org/m-matrix)) characterization that detects large cycles better, has better-behaved gradients, and runs about an order of magnitude faster.[6](https://doi.org/10.48550/arxiv.2209.08037)\n\n## Applications\n\nTwo structural metrics are standard: structural [Hamming distance](https://www.edgepedia.org/hamming-distance) (SHD) counts missing, falsely detected, or reversed edges, and structural interventional distance (SID) counts variable pairs whose interventional distributions would be miscalculated.[9](https://ar5iv.labs.arxiv.org/html/1906.02226)\n\nOn synthetic Erdős-Rényi and scale-free graphs with \\( d \\in \\{10, 20, 50, 100\\} \\) and \\( n \\in \\{20, 1000\\} \\), NOTEARS outperformed fast greedy search across Gaussian, Exponential, and Gumbel noise, with the gap growing with node count and edge density.[4](https://doi.org/10.48550/arxiv.1803.01422) The Sachs protein-signaling dataset is the common real-world benchmark, and published results disagree: the NOTEARS paper treats it as \\( n = 7466 \\), \\( d = 11 \\), with 20 ground-truth edges, where NOTEARS estimated 16 edges with SHD 22, while the MCSL paper uses an 853-sample observational subset with 17 ground-truth edges, where MCSL-MLP and CAM achieved the best SHD of 12 and NOTEARS 19.[4](https://doi.org/10.48550/arxiv.1803.01422) • [7](https://ar5iv.labs.arxiv.org/html/1910.08527)\n\nThe best-documented applications are in biology. IDA was developed to predict causal effects in large-scale systems from observational data and published in Nature Methods.[2](https://doi.org/10.1038/nmeth0410-247) In gene regulatory networks and brain connectivity networks, machine learning-based methods provide comparable results to traditional methods with more efficient time complexity and scalability; NOBEARS improves NOTEARS scalability with a fast polynomial-regression constraint for gene expression data.[3](https://medinform.jmir.org/2023/1/e38266)\n\n## Limitations and alternatives\n\n**Latent confounders and selection bias.** PC assumes no confounders; FCI gives asymptotically correct results even with confounders, and both output equivalence classes rather than complete causal information.[21](https://public-pages-files-2025.frontiersin.org/journals/genetics/articles/10.3389/fgene.2019.00524/pdf)\n\n**Faithfulness and optimization failures.** Faithfulness is violated when two causal pathways cancel, making nodes seem statistically independent though not d-separated.[19](https://appliedcausalinference.github.io/aci_book/04-causal-discovery.html) Gradient-based methods relax the discrete search to a continuous one, but the resulting non-convex problems may get stuck in local minima.[1](https://link.springer.com/article/10.1007/s10208-022-09581-9) Wei and colleagues showed NOTEARS fails to satisfy the Karush-Kuhn-Tucker regularity conditions, motivating NOFEARS.[3](https://medinform.jmir.org/2023/1/e38266) Kaiser and Sipos (2021) analyzed NOTEARS's lack of scale invariance and concluded this limitation makes NOTEARS unsuitable for identifying true causal relationships from data; exponential, log-determinant, and polynomial DAG constraints perform poorly on normalized data because they rely on scale information across variables (Reisach et al., 2021).[20](https://arxiv.org/pdf/2407.13054)\n\n**Alternatives.** Interventional data refine identifiability from the MEC to the I-MEC, and with enough interventions the DAG is fully identifiable.[1](https://link.springer.com/article/10.1007/s10208-022-09581-9) Functional causal models (LiNGAM, ANM, PNL) can distinguish DAGs within an equivalence class because noise-cause independence holds only for the true direction, but they generally cannot handle latent confounders, and nonlinear methods are feasible on only dozens of variables.[21](https://public-pages-files-2025.frontiersin.org/journals/genetics/articles/10.3389/fgene.2019.00524/pdf) For time series, PCMCI incorporates the MCI test into the [PC algorithm](https://www.edgepedia.org/pc-algorithm) to detect contemporaneous and time-delayed effects, and DYNOTEARS handles instantaneous and delayed causality.[20](https://arxiv.org/pdf/2407.13054)\n\nScaling is the practical constraint. PC is asymptotically consistent for sparse high-dimensional DAGs even when \\( p = O(n^{a}) \\) for any finite \\( a \\),[8](https://stat.ethz.ch/Manuscripts/buhlmann/pcalgo2.pdf) but its complexity grows exponentially with variable count, and PC, GES, and GFCI require considerable time beyond 100 variables.[3](https://medinform.jmir.org/2023/1/e38266) For linear relations, PC and GES can scale to tens of thousands of variables on sparse graphs.[21](https://public-pages-files-2025.frontiersin.org/journals/genetics/articles/10.3389/fgene.2019.00524/pdf)\n\n## References\n\n1. [Causal Structure Learning: A Combinatorial Perspective](https://link.springer.com/article/10.1007/s10208-022-09581-9)\n2. [Marloes H Maathuis and colleagues (2010). Predicting causal effects in large-scale systems from observational data. Nature Methods.](https://doi.org/10.1038/nmeth0410-247)\n3. [Scalable Causal Structure Learning: Scoping Review of Traditional and Deep Learning Algorithms and New Opportunities in Biomedicine (JMIR Medical Informatics, 2023)](https://medinform.jmir.org/2023/1/e38266)\n4. [Zheng, Xun and colleagues (2018). DAGs with NO TEARS: Continuous Optimization for Structure Learning. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1803.01422)\n5. [Large-Sample Learning of Bayesian Networks is NP-Hard](https://jmlr.org/papers/volume5/chickering04a/chickering04a.pdf)\n6. [Bello, Kevin, Aragam, Bryon, Ravikumar, Pradeep (2022). DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2209.08037)\n7. [Masked Gradient-Based Causal Structure Learning (MCSL)](https://ar5iv.labs.arxiv.org/html/1910.08527)\n8. [Estimating High-Dimensional Directed Acyclic Graphs With the PC-Algorithm](https://stat.ethz.ch/Manuscripts/buhlmann/pcalgo2.pdf)\n9. [Gradient-Based Neural DAG Learning (GraN-DAG)](https://ar5iv.labs.arxiv.org/html/1906.02226)\n10. [DAG-GNN: DAG Structure Learning with Graph Neural Networks (ICML 2019)](https://proceedings.mlr.press/v97/yu19a/yu19a.pdf)\n11. [Peter Spirtes, Clark Glymour, Richard Scheines (2001). Causation, Prediction, and Search. The MIT Press eBooks.](https://doi.org/10.7551/mitpress/1754.001.0001)\n12. [GES with the BIC score or generalized score, causal-learn documentation](https://causal-learn.readthedocs.io/en/latest/search_methods_index/Score-based%20causal%20discovery%20methods/GES.html)\n13. [Structure Learning in Graphical Modeling (Annual Review of Statistics and Its Application, Drton & Maathuis 2017)](https://www.annualreviews.org/content/journals/10.1146/annurev-statistics-031017-100630)\n14. [Shimizu, Shohei and colleagues (2011). DirectLiNGAM: A direct method for learning a linear non-Gaussian structural equation model. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1101.2489)\n15. [Yu, Yue and colleagues (2019). DAG-GNN: DAG Structure Learning with Graph Neural Networks. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1904.10098)\n16. [Lachapelle, Sébastien and colleagues (2019). Gradient-Based Neural DAG Learning. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1906.02226)\n17. [Pamfil, Roxana and colleagues (2020). DYNOTEARS: Structure Learning from Time-Series Data. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2002.00498)\n18. [Diego Colombo, Marloes H. Maathuis (2014). Order-independent constraint-based causal structure learning. arXiv (Cornell University).](https://doi.org/10.5555/2627435.2750365)\n19. [Applied Causal Inference, Chapter 4: Causal Discovery](https://appliedcausalinference.github.io/aci_book/04-causal-discovery.html)\n20. [Survey of causal discovery algorithms (2024)](https://arxiv.org/pdf/2407.13054)\n21. [Review of Causal Discovery Methods Based on Graphical Models (Frontiers in Genetics, 2019)](https://public-pages-files-2025.frontiersin.org/journals/genetics/articles/10.3389/fgene.2019.00524/pdf)\n22. [Chickering02b (jmlr.org)](https://www.jmlr.org/papers/volume3/chickering02b/chickering02b.pdf)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Machine learning methods*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/causal-structure-learning", "markdown_url": "https://www.edgepedia.org/causal-structure-learning.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Causal structure learning\", Edgepedia (EdgeChat), https://www.edgepedia.org/causal-structure-learning. Edgepedia Community License 1.0.", "credit_md": "\"[Causal structure learning](https://www.edgepedia.org/causal-structure-learning)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/causal-structure-learning](https://www.edgepedia.org/causal-structure-learning). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Causal structure learning\", Edgepedia (EdgeChat), https://www.edgepedia.org/causal-structure-learning. Edgepedia Community License 1.0.", "speakable": "Causal structure learning is a machine learning method that infers a causal graph, typically a directed acyclic graph, among variables from observational or interventional data." }