A Survey on Causal Discovery: Theory and Practice

1.1. A General Overview

• Causal discovery combines data and, when possible, prior knowledge to recover causal graphs, supporting the identification and quantification of effects rather than relying on correlation alone.Causal graphs represent cause-effect relationships with arrows and offer a qualitative, explainable description of a system.Source: §1.1 · pp. 1–2

1.2. Related Works

• Only a few earlier surveys reported evaluation datasets or metrics, two listed both, and two discussed software tools.The survey presents these gaps as barriers to practical adoption by researchers new to causal discovery.Source: §1.2 · p. 3
• Earlier surveys varied in scope: examined learning approaches, addressed time series, lacked an interventional section, and lacked a latent-case section.[5] focused on prominent techniques, offered a practical overview, and emphasized the interplay between causal inference and discovery.Source: §1.2 · p. 3
• This survey distinguishes itself from surveys published from 2019 to 2022 by covering theory and practice and guiding inexperienced readers in comparing and assessing causal-discovery results.It addresses differences between observational and interventional data and covers datasets, metrics, hyperparameter tuning, software packages, and practical applications.Source: §1.2 · pp. 3–4

2.1. Notation

• Graphs use vertices and edges; directed edges distinguish ordered relationships and define parents, children, ancestors, and descendants, while paths and cycles distinguish directed acyclic graphs.A path contains nonrepeating vertices; a cycle starts and ends at the same vertex.Source: §2.1 · p. 4

2.2. Causal Model

• A causal graph describes cause-effect relationships; an SCM M = (V, U, F, P) has endogenous observable variables, exogenous unobservable variables, and functions that determine each Vi completely [18].Source: §2.2 · p. 5

2.3. The Causal Discovery Problem

• Causal discovery seeks the true graph from data; soundness requires asymptotic recovery, completeness returns the most informative graph without extra assumptions, consistency matches the data distribution, and identification determines edge directions.“Most informative” means no edge presence or orientation can be changed without additional information or assumptions.Source: §2.3 · pp. 6–7
• Methods may use observational or interventional distributions and are often designed for particular function classes, such as nonlinear equations [20, 21, 22, 23].Source: §2.3 · p. 7

2.4. Acyclicity and Faithfulness

• D-faithfulness links probabilistic and graphical independence in DAGs, while σ-faithfulness [24] extends to cyclic graphs; d-separation blocks paths via conditioned noncolliders or unconditioned colliders.A conditioning set d-separates two vertices when it blocks every path between them.Source: §2.4 · pp. 7–8

2.5. Equivalence Classes

• PDAGs distinguish oriented causal edges from uncertain ones; observationally equivalent DAGs share a skeleton and v-structures, and their MEC may be represented by a CPDAG with compelled and reversible edges.A specific DAG may not be recoverable from observational data when orientations remain reversible.Source: §2.5 · pp. 9–10

2.6. Sufficiency vs. Insufficiency

• Causal insufficiency occurs when unobserved causes affect observed variables; absent prior knowledge, one exogenous parent per observed variable is assumed, while FCI searches for shared latent parents.Causal sufficiency means all causes of variables in the set are included in that set.Source: §2.6 · p. 10
• Mixed graphs allow undirected, directed, and bidirected edges; bidirected neighbors are spouses, and m-separation blocks paths at conditioned noncolliders or colliders with neither the vertex nor a descendant conditioned on.Source: §2.6 · p. 11
• A MAG is maximal when every nonadjacent vertex pair is m-separated, while a PAG represents a MAG equivalence class with shared adjacencies and invariant endpoint marks.PAGs allow tail, arrowhead, and circle marks; arrowheads and tails in the PAG are invariant across the class.Source: §2.6 · pp. 11–12
• The listed PAG patterns distinguish directed causation, latent confounding, partially oriented alternatives, and circle-circle combinations of these possibilities.X → Y means X causes Y but not vice versa, possibly with an unobserved confounder; X ↔ Y indicates an unobserved common cause without causal direction between X and Y. X ◦→ Y allows either X causing Y or an unobserved confounder causing both, but excludes Y causing X; X ◦−◦ Y leaves the listed causal and confounding alternatives open.Source: §2.6 · p. 12
• With additional assumptions such as homoscedasticity or nonlinearity, some algorithms can identify a single causal graph beyond its equivalence class.Source: §2.6 · p. 12

2.7. Adding Prior Knowledge

• A knowledge base K is the ordered pair (R, F), encoding required and forbidden directed edges, and algorithms can integrate it before discovery or check graph consistency afterward [31].Such prior constraints can come from expert elicitation of whether cause-effect pairs exist.Source: §2.7 · p. 13

3.1. Constraint-based Algorithms

• Constraint-based discovery uses conditional-independence tests under faithfulness; PC removes edges from a complete graph and orients remaining edges, while FCI relaxes assumptions against latent confounding and selection bias.FCI uses discriminating paths to derive additional orientation rules. Constraint-based methods can incorporate prior knowledge, but may require testing up to 2^|V\{X,Y}| conditioning sets for a variable pair.Source: §3.1 · pp. 13, 15, §3.1.1 · p. 15, §3.1.2 · p. 15

3.2. Score-based Algorithms

• Score-based methods maximize graph fitness; GES uses forward additions and backward deletions, while FGES caches partial scores to speed computation at the cost of memory.GES is optimal in the limit of the number of samples under its stated setting, but under causal insufficiency it may add extra edges to compensate for unobserved relationships.Source: §3.2 · p. 16, §3.2.1 · p. 18, §3.2.2 · p. 18

3.3.1. Adaptively Restricted GES (ARGES)

• ARGES restricts GES to admissible edge additions, yielding a consistent forward phase in low- and high-dimensional settings where hybrid methods often lack formal consistency guarantees.An edge is admissible when its endpoints are adjacent in the estimated skeleton or form a v-structure with another node.Source: §3.3.1 · pp. 18–19

3.3.2. Greedy FCI (GFCI)

• GFCI combines FGES skeleton discovery with FCI orientation rules, improving accuracy over either approach while remaining asymptotically correct under causal insufficiency.It requires both a consistent conditional-independence test and a locally consistent score, limiting its use to settings where such a score exists.Source: §3.3.2 · p. 19

3.4.1. Hidden Compact Representation (HCR)

• HCR embeds discrete states in a low-cardinality proxy and uses BIC to balance model fit and parameter count; it is identifiable under mild conditions and outperforms linear models in accuracy and sensitivity, especially when additive noise fails.The method uses a deterministic mapping followed by probabilistic sampling of proxy-variable values.Source: §3.4.1 · pp. 19–20

3.4.2. Bivariate Quantile Causal Discovery (bQCD)

• bQCD uses quantile scoring as an MDL proxy for causal orientation, leveraging the lower-complexity representation expected when the cause precedes the effect.It is robust to outliers and generalizes across distributions, but requires all population quantiles to be computable.Source: §3.4.2 · p. 20

3.4.3. Linear Non-Gaussian Acyclic Model (LiNGAM)

• LiNGAM uses ICA to recover causal ordering under independent non-Gaussian noises, while NOTEARS [47] formulates DAG discovery as continuous optimization with a smooth acyclicity constraint.LiNGAM has an extension for causally insufficient settings and can use approximate ICA variants for efficiency; NOTEARS has cubic matrix-exponential cost and searches DAGs without ensuring every acyclic graph is causal.Source: §3.4.3 · pp. 20–21, §3.4.4 · p. 21

3.5. Comparison between Methods

• Direct comparisons across method classes are difficult because asymptotic complexity proofs are scarce, evaluation criteria can differ, runtime measurements depend on hardware and input size, and implementations span languages with different efficiencies.Some studies report absolute runtime in seconds, further limiting fair comparisons across hardware configurations.Source: §3.5 · pp. 21–22
• A rigorous analysis of synthetic and real-world data found no systematic accuracy or speed differences across algorithm classes in a wide range of scenarios.The authors do not rule out other potential confounding factors.Source: §3.5 · p. 22
• Constraint-based algorithms are generally fast, but chained conditional-independence tests let early mistakes undermine final structures, especially in high-dimensional settings.Source: §3.5 · p. 22
• These considerations point toward score-based approaches and possible parallelization of score evaluation, but further experiments are needed to assess other methods properly.Source: §3.5 · p. 22

4.1. Cyclic SCM

• Cyclic SCMs are non-recursive SEMs in which endogenous variables can form cycles without violating the causal edge assumption.Source: §4.1 · p. 22

4.2. No Acyclicity Assumption

• Feedback cyclic SCM independencies may have no DAG encoding [48]; d-separation suits causally sufficient cases [84], while σ-separation handles insufficient DMGs [52] [33] and reduces to d-separation for DAGs.Source: §4.2 · pp. 22–23

4.2.1. Cyclic Causal Discovery (CCD)

• CCD [48] is a provably sound constraint-based method for general directed graphs, but its d-separation-complete PAG supports dependency queries, not full causal-edge or SCM representation.It is not complete in the sense of representing every feature common to graphs in an equivalence class.Source: §4.2.1 · p. 23

4.2.2. Linear Non-Gaussian (LiNG)

• LiNG allows cycles by targeting loop-free graphs with a zero diagonal in B, but may admit multiple graphs and selects one via the k-th-best assignment.Approximate or sparse ICA can replace full ICA when the latter is computationally expensive.Source: §4.2.2 · p. 24

4.2.3. σ-Connection Graphs

• σ-CGs [52] represent conditional independencies with cycles and latent variables; synthetic low-dimensional benchmarks show consistent recovery, especially with more interventions, but ASP-based σ-separation checks slow learning.Source: §4.2.3 · pp. 24–25

4.2.4. bcause

• bcause [51] uses branch-and-bound exact search to return a globally optimal graph, but exponential complexity limits feasibility; low-dimensional pruning uses bounds, incremental constraints, and linear programming.The benchmark reports lower execution time when acyclicity is assumed.Source: §4.2.4 · p. 25

5. Causal Discovery with Interventions

• Causal discovery with interventions differs from observational learning, which has been studied extensively, while methods for properly handling experimental data have only recently been proposed.Table 3 organizes layers of causation with associated questions, practical examples, and methods.Source: §5 · p. 25, Table 3 · p. 26

5.1. Observational vs. Interventional

• The ladder of causation [8, 87] orders observational, interventional, and counterfactual information by the cognition level and potential queries each supports.Observational data are associational or factual, interventions alter the system, and counterfactual queries ask what would have happened under a different intervention.Source: §5.1 · p. 26
• Each higher layer subsumes the previous one: observational data are the no-intervention case, while counterfactuals add hypothetical actions beyond interventions.The hierarchy is therefore nested rather than composed of distinct information levels.Source: §5.1 · p. 26
• do-calculus represents interventions with the do operator, so natural-language queries can, when possible, be expressed as probability distributions; do(X = x) sets X to x.The operator can extend to sets of variables, and the value vector may be omitted for brevity.Source: §5.1 · pp. 26–27
• A causal effect is identifiable when a finite sequence of the correct and complete do-calculus rules yields an expression without do operators.This section gives only a minimal introduction; is cited for broader discussion of causal-effect identification and estimation.Source: §5.1 · pp. 26–27

5.2. Types of Interventions

• A perfect intervention removes incoming causal edges to its target, whereas an imperfect intervention preserves the dependence but alters the functions representing it.Imperfect interventions can change parameters that quantify causal strength; perfect interventions are a special case that sets them to zero and removes variables from the functional equations.Source: §5.2 · p. 27
• Do-calculus expresses perfect interventions in an operative framework, but cannot express every type of intervention.Source: §5.2 · p. 27
• Mechanism change [90] maps an SCM M with graph G and parameters Θ to M′ by replacing Ψ with differing Ψ′, where Θ′ = Ψ′∪(Θ \ Ψ), inducing a changed function set F′.Imperfect interventions formally define this broader concept.Source: §5.2 · pp. 27–28

5.3. Defining the Intervention Target

• An intervention target contains exactly the variables involved in an intervention; the empty target is observational, and sets of targets form an intervention family.A single-variable target contains one variable, while a multi-variable target contains more than one.Source: §5.3 · p. 28
• A family is conservative when each variable is excluded from at least one target, allowing its behavior to be observed unchanged and intervention effects to be disentangled.The unaffected variable provides a comparison across experiments in the family.Source: §5.3 · p. 28
• An intervention graph removes every directed edge pointing into a target variable, matching the graph surgery induced by a do-intervention.The interventional distribution is expressed by a factorization formula; for perfect interventions, it can also be written in do-notation.Source: §5.3 · pp. 28–29
• Graphs are interventionally Markov equivalent for a family when their intervention graphs share the same skeleton and v-structures for every target; the resulting class is the I-MEC.The equivalence condition decomposes into observational-equivalence statements for the individual targets in the family.Source: §5.3 · p. 29
• An I-covered edge requires matching parent sets and equality of the relevant conditional distributions when intervening on its source, while an I-contradictory edge meets either of the stated intervention-based conditional-distribution tests.I-contradictory edges differ across interventional equivalence classes, violate the I-Markov property, and can be exploited consistently during discovery.Source: §5.3 · pp. 29–30

Single vs. Multi-Variable Interventions

• n-1 experiments suffice with single-variable targets to collect enough evidence to identify the causal graph [92].The nth intervention is redundant because the other interventions identify incoming causal edges for each variable.Source: §5.4 · p. 30
• ⌊log(n)⌋ + 1 interventions are necessary and sufficient in the worst case; randomized schemes can achieve an O(log log(n)) lower bound with high probability [92].The worst case is a complete causal graph, while randomized intervention planning can minimize the number of interventions.Source: §5.4 · p. 30

Unknown Intervention Targets

• Unknown intervention targets make structural learning more complex because the affected variables may be unclear even when an intervention is known to have occurred [54].Source: §5.4 · p. 30

5.5.1. Interventional GES (GIES)

• GIES extends GES to perfect interventions, retaining its forward and backward score-search phases while formalizing intervention distributions and targets.The survey identifies relevant performance improvements from moving from observational to interventional data once those theoretical aspects are addressed.Source: §5.5.1 · pp. 30–31

5.5.2. Interventional Greedy Permutation (IGSP)

• IGSP and UT-IGSP outperform GIES below 10 vertices, while GIES pools interventional datasets more efficiently in high-dimensional spaces despite lacking general consistency.IGSP prioritizes I-covered, I-contradictory edges; UT-IGSP adapts the definition of I-covered edges to partially unknown targets.Source: §5.5.2 · p. 31

5.5.3. Joint Causal Inference with FCI (FCI-JCI)

• FCI123, which uses all three JCI assumptions, is less accurate in general but significantly faster, enabling application to more complex scenarios with a sensible number of variables.JCI adds context variables and pools observations across experimental conditions before applying an observational discovery algorithm such as FCI.Source: §5.5.3 · pp. 32–33

5.5.4. Unknown Intervention Targets using

• Ψ-FCI extends the I-MEC to unknown intervention targets, and its edge orientations are more accurate than those of FCI-JCI.Its Ψ-Markov property combines observational separation with invariance across intervention targets and does not require assumptions about the experimental setting.Source: §5.5.3 · p. 33, §5.5.4 · pp. 33–34

5.5.5. backShift

• backShift outperforms LiNG in observational and interventional settings, handles latent variables under mild assumptions, and has complexity O(|I| · n^2 · m).It recovers linear, possibly cyclic models from shift interventions with unknown targets and shift values.Source: §5.5.5 · p. 34

5.5.6. bcause+

• bcause+ incorporates intervention-derived constraints and can handle nonlinear cyclic models, but exponentially increasing execution time limits its use in high-dimensional settings.Intervention targets constrain separation checks and can yield linear-programming constraints.Source: §5.5.6 · p. 35

5.5.7. Differentiable Causal Discovery with Interventions (DCDI)

• DCDI [58] supports perfect or imperfect interventions, including unknown targets, and shows marginal structural-recovery advantages with O(n^3) training-step scalability.Its score uses conditional distributions that remain invariant across interventions; unknown targets add a regularization term.Source: §5.5.7 · p. 35

6.1. Evaluation Datasets

• Reference datasets span real-world and synthetic observational, interventional, or mixed data; examples include 108 Tuebingen pairs, Sachs interventions, and Klein data.Sachs contains measurements of 11 proteins and phospholipids across nine interventions; Klein ground truth is derived from TRRUST.Source: §6.1 · p. 36, Table 4 · p. 37

6.2. Evaluation Metrics

• Adjacency precision and recall assess graph skeletons, while arrowhead precision and recall evaluate inferred causal relationships, especially distinct marks in PAGs.Adjacency metrics can overestimate performance when invariant marks may be interpreted as heads or tails.Source: §6.2 · p. 37
• Structural Hamming Distance counts edge additions, deletions, and reversals; Structural Intervention Distance counts wrongly inferred interventional distributions and relies on adjustment sets [77, 105, 88].The paper describes SID as a pre-metric strongly related to SHD.Source: §6.2 · p. 38

6.3. Parameters Tuning

• AIC or BIC tuning minimizes causal-graph complexity, often reusing score-based intermediate scores; the general approach uses grid search over parameter configurations.The method is particularly effective with score-based approaches that use the same function.Source: §6.3 · p. 38
• StARS selects parameter configurations with low graph instability across data subsamples and uses a β threshold to avoid trivial empty or complete graphs.Edge instability is the probability that an edge appears in a graph learned from a subsample; graph instability averages edge instabilities.Source: §6.3 · pp. 38–39
• Out-of-sample Causal Tuning evaluates models through prediction without parametric distribution assumptions, and applies when BIC and AIC are undefined, including discrete models with hidden variables.Source: §6.3 · p. 39

6.4. Software Packages

• CDT pools discovery algorithms across subpackages [108], while bnlearn provides structural-learning algorithms and parallel computing support suited to large-scale applications.CDT includes constraint-based, score-based, and nonlinear approaches; bnlearn includes PC, MMPC, and IAMB variants.Source: §6.4 · p. 39
• pcalg offers varied PC, FCI, GES, and LiNGAM methods suited to causal insufficiency; Java-based TETRAD provides a graphical, drag-and-drop pipeline interface.TETRAD offers a wide range of discovery options and is suited to researchers with limited programming experience.Source: §6.4 · pp. 39–40

7.1. Causal Discovery in Economics

• In, modified time-series PC found nonlinear links among emissions, energy, and economic activity; the global graph cautioned rapid net-zero transition could hinder growth, while regional integration supported coordinated policy.The authors also note that PC avoids conditioning on irrelevant variables, yielding larger effect sizes and lower dimensionality than approaches such as Granger causality.Source: §7.1 · p. 40

7.2. Causal Discovery in Medicine

• In, adding trivial background knowledge significantly improved Alzheimer’s graph recovery, longitudinal data added edges and removed incorrect ones, and score-based FGES was more stable than constraint-based FCI.Comparing structures under causal sufficiency and insufficiency helped identify possible effects of unmeasured variables and guide evaluation of hypotheses against a literature-derived gold-standard graph.Source: §7.2 · p. 40
• [120] used GFCI on baseline and six-month RAISE-ETP data to build an SCM, linking social and occupational functioning through socio-affective capacity to motivation and revealing causal cycles.GFCI was selected to address latent-variable effects; its FGES-based phase caches score evaluations to reduce discovery time.Source: §7.2 · p. 41

7.3. Causal Discovery in Psychology

• In, GFCI linked drinking craving as the strongest causal influence on drinking, with craving influenced by DTC, while depression’s links to social anxiety and stress remained directionally ambiguous.GFCI’s ability to handle causal insufficiency supported consideration of potential hidden variables in the drinking-anxiety relationship.Source: §7.3 · p. 41

8.1. A Brief Summary

• The survey presents algorithms, evaluation criteria, and software tools across varied scenarios, comparing strengths and weaknesses and reporting tuning strategies and public datasets.Its comparison includes unobserved variables, cyclical dependencies, nonlinear relationships, and unknown interventions.Source: §8.1 · pp. 41–42

8.2. Future Directions

• Time-series causal discovery remains unexplored in the survey and merits separate discussion, particularly alongside the other topics covered.Temporal causal dependencies differ from those in static settings and add complexity.Source: §8.2 · p. 42
• Missing-data discovery remains underexplored; imputing data missing not at random can introduce bias, and recent advances [123] are limited to constraint-based approaches.Source: §8.2 · p. 42
• Pooling heterogeneous observational sources can perform poorly under distribution shifts, leaving causal representation learning across multiple contexts unresolved.Shifts can arise when context variables differ significantly, for example because of environmental changes.Source: §8.2 · p. 42
• Other limited settings include non-identical overlapping variable sets [28, 125], streaming data, and federated learning [127].Source: §8.2 · p. 42

• Alessio Zanga was granted a Ph.D. scholarship by F. Hoffmann-La Roche Ltd.Source: Funding · p. 42