# Learning Bayesian Networks in the Presence of Structural Side Information

arXiv: https://arxiv.org/abs/2112.10884 · HTML: https://mlsanity.com/paper/2112.10884/

## 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 (most cited first, 12 of 12)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [Learning Sparse Causal Models is not NP-hard](https://mlsanity.com/paper/1309.6824/) (2013)
- [Bayesian Networks in Healthcare: Distribution by Medical Condition](https://mlsanity.com/paper/2002.00224/) (2020)
- [A Recursive Markov Boundary-Based Approach to Causal Structure Learning](https://mlsanity.com/paper/2010.04992/) (2020)
- [Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Package](https://mlsanity.com/paper/1406.7648/) (2014)
- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Structure Learning for Cyclic Linear Causal Models](https://mlsanity.com/paper/2006.05978/) (2020)
- [Advances in Learning Bayesian Networks of Bounded Treewidth](https://mlsanity.com/paper/1406.1411/) (2014)
- [The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks](https://mlsanity.com/paper/1806.06209/) (2018)
- [Turbocharging Treewidth-Bounded Bayesian Network Structure Learning](https://mlsanity.com/paper/2006.13843/) (2020)

## Built on by (most cited first, 12 of 12)

- [Recursive Causal Discovery](https://mlsanity.com/paper/2403.09300/) (2024)
- [Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables](https://mlsanity.com/paper/2208.06935/) (2022)
- [Causal Bandits without Graph Learning](https://mlsanity.com/paper/2301.11401/) (2023)
- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)
- [Confounded Budgeted Causal Bandits](https://mlsanity.com/paper/2401.07578/) (2024)
- [Reinforcement Learning for Causal Discovery without Acyclicity Constraints](https://mlsanity.com/paper/2408.13448/) (2024)
- [QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs](https://mlsanity.com/paper/2410.23155/) (2024)
- [Learning Linear Gaussian Polytree Models with Interventions](https://mlsanity.com/paper/2311.04636/) (2023)
- [Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding](https://mlsanity.com/paper/2503.07475/) (2025)
- [A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2605.10651/) (2026)
- [Decoupled Causal Discovery](https://mlsanity.com/paper/2609.23535/) (2026)
- [Coupling Noisy Pairwise Knowledge to the DAG Posterior for Causal Discovery](https://mlsanity.com/paper/2610.04559/) (2026)

## 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.