mlsanityData to 14 Oct 2026

Learning Bayesian Networks in the Presence of Structural Side Information

arXiv 2112.10884 ↗First posted 20 Dec 2021cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning a Bayesian network (BN) of a set of variables when structural side information about the system is available. It is well known that learning the structure of a general BN is both computationally and statistically challenging. However, often in many applications, side information about the underlying structure can potentially reduce the learning complexity. In this paper, we develop a recursive constraint-based algorithm that efficiently incorporates such knowledge (i.e., side information) into the learning process. In particular, we study two types of structural side information about the underlying BN: (I) an upper bound on its clique number is known, or (II) it is diamond-free. We provide theoretical guarantees for the learning algorithms, including the worst-case number of tests required in each scenario. As a consequence of our work, we show that bounded treewidth BNs can be learned with polynomial complexity. Furthermore, we evaluate the performance and the scalability of our algorithms in both synthetic and real-world structures and show that they outperform the state-of-the-art structure learning algorithms.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 12 of its 75 references that are in the map. First posted on arXiv 20 Dec 2021.

Builds on

12 of 75 references.

References · 12

  1. 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 752
  2. 2019Learning Sparse Nonparametric DAGscited by 207
  3. 2019Causal Discovery with Reinforcement Learningcited by 145
  4. 2013Learning Sparse Causal Models is not NP-hardcited by 49
  5. 2020Bayesian Networks in Healthcare: Distribution by Medical Conditioncited by 23
  6. 2020A Recursive Markov Boundary-Based Approach to Causal Structure Learningcited by 21
  7. 2014Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Packagecited by 19
  8. 2020Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysiscited by 13
  9. 2020Structure Learning for Cyclic Linear Causal Modelscited by 13
  10. 2014Advances in Learning Bayesian Networks of Bounded Treewidthcited by 10
  11. 2018The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networkscited by 10
  12. 2020Turbocharging Treewidth-Bounded Bayesian Network Structure Learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 2; 2024: 4; 2025: 1; 2026: 3.

12 papers.

  1. 2024Recursive Causal Discoverycited by 12
  2. 2022Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variablescited by 10
  3. 2023Causal Bandits without Graph Learningcited by 10
  4. 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
  5. 2024Confounded Budgeted Causal Banditscited by 4
  6. 2024Reinforcement Learning for Causal Discovery without Acyclicity Constraintscited by 3
  7. 2024QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMscited by 1
  8. 2023Learning Linear Gaussian Polytree Models with Interventionscited by 0
  9. 2025Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confoundingcited by 0
  10. 2026A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variablescited by 0
  11. 2026Decoupled Causal Discoverycited by 0
  12. 2026Coupling Noisy Pairwise Knowledge to the DAG Posterior for Causal Discoverycited by 0