PaperlayerView exact revision on arXiv

Source-linked AI summary

A survey of Bayesian Network structure learning

Neville K. Kitson, Anthony C. Constantinou, Zhigao Guo, Yang Liu, Kiattikun Chobtham

arXiv:2109.11415v2cs.LGcs.AI

TL;DR

Learning Bayesian Network structure is difficult when models must support transparent, causal reasoning, and algorithm evaluations lack a shared standard. This paper reviews major structure-learning algorithms, knowledge-integration approaches, and evaluation practices, finding diverse methods, conflicting comparisons, and important gaps in real-world causal validation.

  • Problem

    Black-box predictive models are unsuitable for transparent decision-making in domains such as government policy and healthcare, while evaluating structure-learning algorithms lacks an agreed process.

  • Method

    The paper comprehensively reviews algorithms for learning Bayesian Network graphical structures from data, methods for incorporating knowledge, and metrics and comparative studies used to evaluate them.

  • Results

    The review finds a huge diversity of structure-learning approaches, little consensus about the best algorithm for a given real-world context, and inconsistencies in comparative claims.

  • Takeaways & Limitations

    Algorithm choice and comparison require attention to data characteristics, modelling assumptions, prior knowledge, and evaluation metrics rather than reliance on a universally best method.

  • Takeaways & Limitations

    Evaluation commonly lacks real-world datasets with expert-validated causal graphs and often does not assess generalisation or causal inferential properties such as intervention effects.

Abstract

from arXiv · show

Bayesian Networks (BNs) have become increasingly popular over the last few decades as a tool for reasoning under uncertainty in fields as diverse as medicine, biology, epidemiology, economics and the social sciences. This is especially true in real-world areas where we seek to answer complex questions based on hypothetical evidence to determine actions for intervention. However, determining the graphical structure of a BN remains a major challenge, especially when modelling a problem under causal assumptions. Solutions to this problem include the automated discovery of BN graphs from data, constructing them based on expert knowledge, or a combination of the two. This paper provides a comprehensive review of combinatoric algorithms proposed for learning BN structure from data, describing 74 algorithms including prototypical, well-established and state-of-the-art approaches. The basic approach of each algorithm is described in consistent terms, and the similarities and differences between them highlighted. Methods of evaluating algorithms and their comparative performance are discussed including the consistency of claims made in the literature. Approaches for dealing with data noise in real-world datasets and incorporating expert knowledge into the learning process are also covered.

1. INTRODUCTION

Bayesian Networks support reasoning under uncertainty and, under causal assumptions, intervention and counterfactual questions. This survey reviews combinatoric methods for learning BN graphical structure from data, alongside expert-knowledge integration and evaluation concerns.

  • Motivation: Black-box predictive models are unsuitable for decision-making domains requiring transparency and tractability.The paper motivates causal representations for applications such as government policy and healthcare.
  • Motivation: Causal Bayesian Networks can support associational, intervention, and counterfactual reasoning when employed under causal assumptions.These correspond to Pearl and Mackenzie’s seeing, doing, and imagining levels.
  • Bayesian Networks: BNs compactly represent probabilistic relationships among large collections of variables and have applications across biology, healthcare, and engineering.The survey notes examples including protein and gene networks, psychosis and cancer care, and fault diagnosis.
  • Survey scope: The survey focuses on learning BN graphs from data using combinatoric structure-learning algorithms, while recognizing expert-specified and combined approaches.It emphasizes graph recovery because parameter estimation is generally easier than accurately determining the structure.
  • Survey scope: The review covers BN preliminaries, constraint-based, score-based, hybrid, practical, and evaluation approaches, while pointing to other surveys for omitted areas.Related surveys address functional causal models, continuous optimisation, mixed observational and experimental data, cyclic graphs, and other topics.

2. PRELIMINARIES

The preliminaries define BNs as DAG-based probabilistic models whose structures encode conditional relationships, with causal interpretations enabling intervention reasoning. They also frame structure learning as a computationally difficult search problem.

  • BN definitions: A Bayesian Network consists of a DAG and parameters that specify the strengths and forms of relationships between variables.The DAG supplies the graphical structure, while the parameters describe the relationships.
  • BN definitions: A directed edge A⟶B denotes a direct conditional relationship, or a direct cause under a causal interpretation; A is B’s parent and B its child.Non-causal BNs support observational inference, whereas causal BNs support intervention reasoning.
  • Equivalence and assumptions: DAGs can belong to the same Markov Equivalence Class when they share adjacencies and v-structures and therefore entail the same conditional independences.A v-structure has a collider with no edge between its two parent nodes.
  • Graphical separation: D-separation determines whether a conditioning set blocks all paths between two nodes, thereby representing conditional independence in a DAG.An active path is unblocked, and a Sepset is a conditioning set that d-separates two nodes.
  • Equivalence and assumptions: BN assumptions include the Markov Condition and Minimality Condition, linking d-separation-implied independences to the joint distribution while preventing unnecessary edges.The Markov Condition yields a decomposition of the joint distribution by each variable’s parents.
  • Structure learning: Structure learning seeks a graph from data, but the number of possible DAGs grows super-exponentially, making exhaustive search impractical.The problem is NP-hard, including for score-based and constraint-based learning under favourable restrictions.

3. CONSTRAINT-BASED LEARNING

Constraint-based learning uses conditional-independence tests to remove and orient edges, often under causal assumptions, but may identify an equivalence class rather than a unique DAG. The survey organizes methods by scope, assumptions, and output representations.

  • Core principles: Constraint-based algorithms use conditional-independence tests to construct graphs consistent with observed independence relationships.Because multiple DAGs can share those relationships, the output may be a graph class rather than one DAG.
  • Assumptions: Constraint-based causal discovery commonly assumes causal faithfulness and causal sufficiency, although reviewed algorithms vary in the strength of their faithfulness assumptions.Faithfulness concerns whether distributional independences correspond to graph-implied independences.
  • Graph representations: DAGs in the same equivalence class share a skeleton and v-structures, which can be represented by a PDAG or CPDAG.Directed edges encode v-structures, while undirected edges represent orientations not identified by the equivalence information.
  • Assumptions: An unfaithful network can contain causation without association when particular parameter values create an independence absent from the DAG.This violates the correspondence expected between graph structure and distributional independences.
  • Algorithm families: The survey covers global, local, and alternative constraint-based algorithms, whose outputs include CPDAGs, PAGs, and local structures such as Markov blankets.Local structures may later be merged into an integrated graph in software implementations.

3.1. Determining Conditional Independence

Conditional-independence procedures decide whether variables are independent given conditioning sets, using statistical tests or association measures suited to discrete and Gaussian BNs. Their decisions determine Sepsets and therefore influence constraint-based graph construction.

  • Test role: CI tests assess whether A and B are independent given a conditioning set S, including unconditional tests when S is empty.The result determines whether S serves as a Sepset for A and B.
  • Test families: G2, χ2, and mutual-information tests are commonly used for discrete BNs, while Fisher’s z-test is frequently used for Gaussian BNs.Statistical tests typically compare a test statistic or p-value with a predefined threshold.
  • Association measures: Conditional mutual information of 0 indicates no information flow between A and B given S, while values below a chosen threshold ε are treated as conditional independence.Some algorithms also use association measures as graded evidence rather than only binary decisions.
  • Discrete tests: The G2 statistic compares observed joint counts with the product of conditional marginal probabilities across values of A, B, and S.Its degrees of freedom depend on the numbers of distinct variable and conditioning-set values, with adjustments possible for zero counts.
  • Gaussian tests: Fisher’s z-test transforms the partial correlation between A and B given S and uses its normal-distribution-based score to compute a p-value.The partial correlation can be computed recursively for conditioning sets of increasing size.

3.2. Global Discovery Algorithms

Global constraint-based algorithms learn BN structure as a whole by using conditional-independence tests to recover adjacencies, identify v-structures, and orient remaining edges. The section traces efficiency, faithfulness, stability, and orientation improvements across SGS, PC-family, TPDA, and RAI methods.

  • Global discovery algorithms learn the graph structure as a whole under causal sufficiency, unlike local algorithms that learn node-specific structures.
  • SGS Algorithm: SGS begins with a complete undirected graph, removes edges using exhaustive CI tests, identifies v-structures, and repeatedly propagates orientations to produce a CPDAG.
  • SGS Algorithm: n(n−1) ⋅2^n−3 CI tests make SGS exponential and infeasible for a reasonable number of variables, despite relative stability to CI-test errors.
  • PC Algorithm: PC reduces computation by testing conditioning sets in increasing size and using adjacency-phase Sepsets for v-structure identification, but can amplify mistaken edge deletions.
  • Conservative PC (CPC) algorithm: CPC weakens PC’s complete-faithfulness assumption by separating adjacency- and orientation-faithfulness, producing fewer erroneous orientations while being only slightly slower in simulations.
  • PC-Stable Algorithm: PC-Stable reduces ordering sensitivity, learning lower-SHD graphs with much smaller SHD variance than PC in high-dimensional simulations, at a three-to-13-percent runtime cost.
  • PC-MAX selects the highest-p-value Sepset for v-structure decisions, while TPDA and RAI alter search organization to reduce CI-test demands or avoid costly high-order tests.

3.3. Local Discovery Algorithms

Local discovery algorithms learn each variable’s neighborhood or Markov Blanket separately and merge the resulting local structures into a global skeleton. Their methods trade CI-test efficiency against symmetry, spouse-discovery, and network-density considerations.

  • Local algorithms learn each node’s parents and children or Markov Blanket separately, then merge local structures to form the BN skeleton.
  • Local structures can become asymmetric because of CI-test errors, so algorithms commonly retain an edge only when both nodes include each other under the AND-rule.
  • Markov Blanket algorithms: Grow-Shrink discovers each Markov Blanket by adding associated variables that remain dependent and then removing variables rendered conditionally independent.
  • Markov Blanket algorithms: GS completes adjacency determination by removing parents of children and then applies v-structure and orientation phases similar to SGS and PC.
  • Markov Blanket algorithms: GS requires O(n^2 + nb^22^b) CI tests; this is exponential when the largest Markov Blanket scales with n but decreases to O(n^2) for sparse networks.
  • Markov Blanket algorithms: IAMB targets scalability to thousands of nodes by addressing GS’s slow discovery of weakly associated spouses, while Fast-IAMB groups additions to reduce statistic recomputation.
  • Parents-and-children algorithms: MMPC, HITON-PC, and SI-HITON-PC learn parents and children directly through prioritized inclusion, elimination, and interleaving strategies.

3.4. Algorithms assuming the existence of latent variables

Algorithms in this section avoid assuming causal sufficiency by representing observed-variable relationships that may reflect latent confounders or selection bias. Ancestral graphs, MAGs, PAGs, and FCI-family methods extend constraint-based discovery to partially observed settings.

  • Explicitly modelling unmeasured confounders can make learning intractable, motivating observed-variable graphs that account for latent variables and confounding.
  • Ancestral graphs: Ancestral graphs represent relationships among observed variables in the presence of latent confounders and selection bias, while remaining closed under conditioning and marginalisation.
  • Ancestral graphs: Ancestral graphs encode conditional independencies through m-separation, analogous to d-separation for DAGs, while forbidding partially directed cycles and incoming arrows into undirected-edge endpoints.
  • Maximal Ancestral Graphs: MAGs ensure that every absent edge corresponds to a conditional independence by adding bidirectional edges when needed to represent latent-confounding structure.
  • Partial Ancestral Graphs: PAG endpoint marks distinguish invariant arrowheads, invariant tails, and variant endpoints across the MAG equivalence class.
  • FCI algorithm: FCI learns a partially oriented inducing-path representation through skeleton discovery, v-structure identification, Possible-D-Sep refinement, and complex orientation rules.

4. SCORE-BASED LEARNING

Score-based learning searches graph spaces using an objective function and a traversal strategy, with algorithms differing in search space, pruning, and optimality guarantees. The review organizes methods by approximate versus exact search and by DAG, equivalence-class, or node space.

  • Score-based learning combines a search strategy over possible graphs with an objective function that evaluates each explored graph.
  • Approximate score-based algorithms do not guarantee the highest-scoring graph, whereas exact algorithms use sound pruning to preserve the optimal solution.
  • Search strategies differ in the space explored, traversal method, and pruning approach, including greedy arc addition subject to acyclicity.
  • Reviewed approximate algorithms explore DAG space, equivalence-class space, or node space, with node ordering providing a topological ordering compatible with acyclic graphs.
  • Table 3 catalogs reviewed score-based algorithms chronologically by search space, traversal method, approximation or exactness, objective function, and returned graph type.

4.1. Objective functions

Objective functions score BN graphs by fit to data while incorporating prior knowledge or penalising complexity. Bayesian scores support posterior reasoning and model averaging, whereas information-theoretic scores balance fit against dimensionality and include decomposable and score-equivalent variants.

  • Bayesian scores: Score equivalence assigns the same score to DAGs in one Markov equivalence class because observational data cannot distinguish them.Interventional data may orient some otherwise undirected edges.
  • Bayesian scores: Bayesian scores evaluate graph posterior probability using data and prior beliefs about structure or parameters, enabling Bayesian Model Averaging.A feature such as an arc can be averaged across likely structures.
  • Bayesian scores: BDeu is score equivalent but its learned graph depends strongly on the user-chosen equivalent sample size (ESS).Smaller ESS values favor arc deletion and sparser graphs, while larger values can increase the number of arcs.
  • Information-theoretic scores: Information-theoretic scores balance goodness of fit with model dimensionality to reduce overfitting.Common examples include BIC, AIC, MIT, NML, and fNML.
  • Information-theoretic scores: AIC uses a softer complexity penalty than BIC and therefore tends to favor networks with more free parameters.As sample size grows, the complexity penalty becomes less influential and log likelihood increasingly dominates.
  • Information-theoretic scores: fNML was reported to perform well on small datasets, while qNML was introduced as a score-equivalent NML-based alternative.fNML is not score equivalent; qNML is score equivalent.

4.2. Approximate score-based algorithms

Approximate score-based methods search DAGs, equivalence classes, or node orderings without generally guaranteeing the globally highest-scoring graph. They use greedy, neighborhood, restart, sampling, or hybrid strategies to address local maxima, slow mixing, and uncertainty over plausible structures.

  • Search strategies: Approximate score-based algorithms generally return locally maximum-scoring graphs rather than guaranteeing the global optimum.Some approximate methods are classically consistent, reaching the optimal graph with probability approaching one as sample size grows.
  • DAG-space search: K2 assumes a known node ordering and greedily adds candidate-parent arcs, but does not examine all parent sets for that ordering.Consequently, K2 cannot guarantee the highest-scoring DAG under the supplied ordering.
  • DAG-space search: Hill-climbing evaluates legal arc additions, deletions, and reversals, applying the highest positive score change to the current DAG.Changes must not create cycles, and the procedure stops when no positive change remains.
  • DAG-space search: Local restarts, tabu lists, and variable-neighborhood search are used to escape local maxima; VNS changes several arcs per iteration and outperformed plain hill-climbing in a small Alarm-network experiment.Tabu search permits some score-decreasing moves while preventing recent revisits.
  • Sampling-based search: MCMC methods sample posterior distributions over DAGs or node orderings, with each Markov-chain state representing a different model.Hybrid MCMC converged faster than MC3 and Order-MCMC, while broader Gibbs proposals mixed better than MC3 and REV-MCMC and produced more accurate DAGs.
  • Equivalence-class search: GES searches equivalence-class space through insertion and deletion phases and, despite being approximate, guarantees classical consistency.GIES extends GES to multiple datasets with different intervention targets and increasingly improves accuracy relative to GES as intervention datasets differ.
  • Node-ordering search: Node-ordering methods address weak nearby local maxima by using larger order changes, perturbations, or population-based search.Order-space sampling can also counter slow mixing encountered in DAG-space MCMC, while Partition-MCMC scores partial topological-order partitions by aggregating consistent DAGs.

4.3. Exact score-based algorithms

Exact score-based algorithms guarantee the highest-scoring DAG for the input data, using combinatorial search and pruning strategies to manage large spaces. However, the highest score may not identify the ground-truth graph, while newer methods improve exact search efficiency and can return sets of near-optimal graphs.

  • Exact algorithms guarantee the highest-scoring DAG for the input dataset, unlike approximate methods whose guarantees may require infinite sample sizes.
  • The highest-scoring DAG may differ from ground truth because of limited or noisy data and biases in the scoring function.
  • 4.3.1. Exact search of node-ordering space: Dynamic programming searches node-ordering space by recursively exploiting sink nodes and independently maximising their parent-set scores.
  • 4.3.1. Exact search of node-ordering space: A* improves lattice navigation by estimating future scores, addressing dynamic programming's inefficient evaluation of the exponential solution space.
  • 4.3.1. Exact search of node-ordering space: CPBayes combines node ordering, parent sets, and depth variables with acyclicity, symmetry-breaking, and dominance constraints to prune exact search.
  • 4.3.1. Exact search of node-ordering space: ELSA found optimal graphs within 10 hours for considerably more datasets with 61–111 variables than GOBNILP or CPBayes, excluding parent-score precomputation.
  • 4.3.2. Exact search of DAG space: Branch and Bound decomposes cyclic candidate graphs and queues subgraphs by score until the globally optimal DAG is identified, using cached parent-set scores.
  • 4.3.2. Exact search of DAG space: GOBNILP represents candidate parent sets with binary family variables and enforces one parent set per node plus acyclicity through integer-programming constraints.

5. HYBRID LEARNING AND OTHER APPROACHES

Hybrid and other structure-learning approaches combine or extend constraint-based, score-based, sampling, functional-causal, and continuous-optimization strategies. The reviewed methods differ in search space, traversal, assumptions, and treatment of uncertainty, with reported gains in consistency, efficiency, accuracy, or causal identifiability under specific settings.

  • Restrict/Maximise hybrids: Restrict/Maximise hybrids first constrain the search space with a constraint-based method, then optimize a score within that restricted space.MMHC uses MMPC to construct a skeleton before Tabu hill-climbing learns the output DAG; the approach was reported to outperform GES, PC, and TPDA and scale to 1,000 variables.
  • Restrict/Maximise hybrids: Early hybrid algorithms interleaved restriction and score optimization across iterations, using procedures such as PC, K2 scoring, mutual-information tests, Tabu search, or evolutionary operations.CB alternated restricted PC learning with K2-based orientation, while Sparse Candidate retained prior parent sets as candidates in later iterations.
  • Other ordering-space approaches: Ordering-space methods traverse node orderings, with TSP asymptotically consistent and GSP using depth limits and restarts for shorter runtimes.GSP was reported to match GES and PC at high sample size and produce more accurate graphs in a low-sample-size setting.
  • Other approaches: Other approaches handle latent variables, interventions, non-Gaussian noise, nonlinear effects, or continuous acyclicity constraints through probabilistic CI scoring, functional models, and differentiable optimization.RFCI-BSC uses stochastic Bayesian scoring and model averaging; FCMs support causal identification under assumptions on functions and noise; NOTEARS compares favorably with FGES on denser graphs.

6. PRACTICAL CONSIDERATIONS

This section reviews how BN structure-learning algorithms are evaluated, emphasizing the lack of an agreed effectiveness standard and the limitations of common metrics. Structural, inference-based, and causal metrics each capture different aspects of learned-graph quality.

  • Evaluation approaches: Evaluation methods include structural comparisons, inference-based scores, predictive accuracy, and causal metrics, but no agreed process determines algorithm effectiveness.The appropriate evaluation depends partly on the learning algorithm’s class and aims.
  • Structural metrics: Precision and Recall measure different edge-discovery properties, while F1 combines them through their harmonic mean.Precision concerns correct discovered edges; Recall concerns discovered true edges.
  • Structural metrics: SHD counts edge insertions, deletions, and reversals needed to transform a learned graph into the true graph.Variants can assign different penalty weights to these operations, often weighting reversals less heavily.
  • Causal metrics: SID compares DAGs by counting ordered node pairs whose intervention distributions differ between the two graphs.Its value can be asymmetric, and the described variant for CPDAGs considers only identifiable interventions.
  • Inference-based evaluation: Inference-based scores and predictive accuracy do not necessarily indicate accurate causal structure, especially with limited or noisy data.The highest BIC-scoring graph is often not the ground-truth graph; larger, cleaner datasets improve confidence in scores.
  • Evaluation limitations: Structural and inference metrics scale with graph size, and inference metrics also scale with sample size, complicating comparisons across datasets.Scaled variants such as SHD divided by the number of true arcs have been proposed.

6.2. Algorithm Performance

Algorithm performance varies across accuracy, runtime, data type, sample size, objective functions, and data quality. The literature therefore supports context-dependent comparisons rather than a single universally optimal algorithm.

  • Accuracy comparisons: Comparative studies make definitive algorithm recommendations difficult because they use varied algorithms, datasets, evaluation methods, and data types.Most comparisons include representatives from PC, hill-climbing or Tabu, GES, and hybrid families.
  • Accuracy comparisons: Tabu often performs strongly, but its advantage depends on the setting: it was most accurate in 14/20 cases yet underperformed constraint and hybrid methods on Gaussian BNs.For score-based comparisons, Tabu had lower SHD than FGES in 18/20 cases.
  • Accuracy comparisons: Constraint-based methods can obtain better edge precision but worse recall than score-based methods, while PC- and FCI-family methods performed better on some real datasets.The literature also reports no systematic accuracy difference between constraint-based and hybrid algorithms.
  • Efficiency comparisons: Runtime rankings are inconsistent, although exact score-based algorithms are considerably slower and generally limited to problems with fewer than 100 variables.Approximate methods have handled much larger networks, including FGES experiments with up to one million variables using high-performance computing.
  • Efficiency comparisons: Implementation choices can change runtime substantially: two CPC implementations differed by an order of magnitude, while reported MMHC advantages were not consistently reproduced.Reported speedups included MMHC being 41.35 and 10.09 times faster than PC and Tabu in one implementation.
  • Other performance factors: Increasing sample size generally improves learned-graph accuracy, but the general relationship between sample size and accuracy remains unclear.A 24-variable CLGBN was learned accurately at sample sizes of 5 million cases and above in one study.
  • Other performance factors: Objective functions and conditional-independence tests can substantially affect accuracy, making them confounding factors in algorithm comparisons.Structural priors within hill-climbing also affected the accuracy of learned graphs.
  • Data factors: Synthetic evaluations often lack real-world representativeness, while real datasets generally lack a reference ground-truth graph for structural comparison.Studies span from a handful of variables to one million, with higher-dimensional evaluations generally relying on synthetic graphs and data.

6.4. Knowledge

The review covers soft, hard, and active approaches for incorporating expert knowledge into BN structure learning. These approaches influence candidate graphs, scores, search constraints, or human input during learning.

  • Soft constraints: Soft constraints incorporate expert knowledge by influencing the learning process rather than enforcing mandatory graph properties.Bayesian objective functions use priors over parameters and graph structures, while other methods specify priors for arcs or general graph characteristics.
  • Soft constraints: Ordering constraints can encode partial ancestral or temporal relationships among variables in the learned structure.Such constraints may be derived from time and causality considerations.
  • Hard constraints: Hard constraints require learned graphs to include or exclude specified features, respect orderings, or obey parent and parameter restrictions.Methods support required or prohibited arcs, topological orderings, node-specific parent limits, and restrictions on parental effects.
  • Hard constraints: Increasing constraints improved most structural metrics but sometimes increased extraneous arcs produced by the PC algorithm.The review attributes this possible effect to fewer conditional-independence tests being performed, leaving fewer arcs removed.
  • Hard constraints: Around 10 ancestral constraints oriented approximately 30% of variant endpoints, with stronger effects in PDAGs than PAGs.Constraints propagate more in PDAGs when confounding variables are absent.
  • Effects of knowledge: Required arcs had the greatest effect on learned graphs, while prohibiting arcs appeared to have little effect.An initial graph sharing edges with the true graph had the next-largest effect in the reviewed comparison.
  • Active learning: Active learning asks experts about relationships that algorithms find difficult to determine from data alone.This may reduce redundant human input by requesting knowledge only where the data are insufficient.

6.5. Structure Learning Software Packages and Datasets

This section surveys software packages, datasets, data-type support, algorithm choices, and evaluation practices relevant to applying BN structure learning. It emphasizes practical selection because no single best algorithm is established for every context.

  • Resources: The listed open-source packages and datasets focus on algorithms and evaluation resources discussed in the paper rather than providing exhaustive inventories.Table 7 covers software packages, while Table 8 covers repositories of networks and datasets.
  • Evaluation: Synthetic evaluation commonly generates data from a known BN, learns a DAG, and compares it with the generating DAG when a reference graph exists.Reference graphs can also be obtained from random graph generation or available network repositories.
  • Data types: Algorithm choice depends partly on whether variables are continuous, discrete, or both, although software support often determines this capability.Implementations supporting both types vary in flexibility, including restricted mixed networks and more general mixtures.
  • Algorithm selection: Exact score-based algorithms can be feasible up to around 100 variables, but may not improve accuracy with latent confounding, selection bias, or measurement error.The review also notes that limiting node in-degree is often necessary.
  • Algorithm selection: Packages and algorithms differ in their treatment of latent confounders and selection variables, including FCI-family methods in Tetrad and FCI+ in Pcalg.These methods have theoretical advantages when causal sufficiency does not hold.
  • Algorithm selection: Practitioners may choose single-graph methods or methods returning multiple graphs, with model averaging useful for identifying probable causal features.Sampling graph spaces can also characterize uncertainty in graphs or features such as arcs and Markov blankets.
  • Evaluation: Structural comparison with a true causal graph is robust but usually limited to simulations, while bootstrapping can assess result reliability without a reference graph.Column ordering can affect some algorithms, so it may warrant investigation during evaluation.
  • Guidelines: The review recommends using multiple suitable algorithms and considering model averaging because rankings vary with metrics and system characteristics.The authors state that no structure learning algorithm is perfect and literature rankings are inconsistent.

7. CONCLUDING REMARKS

The paper reviews BN structure-learning algorithms, their evaluation, and knowledge-integration methods across a broad and rapidly developing field. It concludes that substantial diversity, difficult comparisons, and unresolved data and knowledge challenges remain.

  • Scope and contribution: The review aims to cover major BN structure-learning developments from the past thirty years, including pioneering and current state-of-the-art algorithms.Its scope includes learning graphical structures from data and incorporating knowledge into that process.
  • Scope and contribution: The paper organizes algorithms into score-based, constraint-based, and hybrid categories and describes their principles, assumptions, similarities, and differences consistently.It covers 24 constraint-based, 22 score-based, and 15 hybrid algorithms.
  • Evaluation: The review discusses practical evaluation metrics, graphical discovery, inference, accuracy, runtime, and large-scale comparative analyses.It uses recent comparative studies to indicate the increasing scale of problems addressed by available algorithms.
  • Limitations and open questions: Theoretical accuracy guarantees generally depend on unrealistic assumptions about input data across exact, approximate, constraint-based, and hybrid algorithms.Learned-graph quality also depends on interacting choices involving algorithms, scores or tests, and data characteristics.
  • Knowledge integration: The review covers hard constraints, soft constraints, and active learning as ways to incorporate expert knowledge into structure learning.Active learning lets algorithms identify which expert knowledge would be most beneficial.
  • Limitations and open questions: Open questions include limited consensus on algorithm choice, scarce real-world causal reference graphs, and better integration of knowledge and interventional data.Comparisons are complicated by factors including sample size, assumptions, noise, dimensionality, hyperparameters, and evaluation metrics.

APPENDIX A: GLOSSARY OF SYMBOLS

The glossary defines notation used throughout the review for independence, conditioning, set relations, statistical metrics, and discrete-variable complexity.

  • Independence notation: ⊥ denotes independence, ⊥/ denotes non-independence, and | denotes conditioning or being given another variable.For example, A⊥B means A is independent of B.
  • Set notation: \ denotes set subtraction, while ⊂ and ⊆ denote strict-subset and subset relationships, respectively.The glossary distinguishes whether the containing set has additional elements.
  • Statistical notation: ρ_ab denotes partial correlation, while TP, FP, TN, FN, P, and R denote classification metrics.These symbols represent true and false positives and negatives, precision, and recall.
  • Statistical notation: G2 and χ2 denote the G-squared and Chi-squared test statistics, and MI(A, B) denotes mutual information.The glossary also lists notation for Bayesian-network quantities and related statistics.
  • Discrete-variable notation: r denotes the stochastic complexity of N values for a discrete variable with r states.This notation is defined specifically for the stated discrete-variable setting.
Loading 2109.11415v2…