# Active Structure Learning of Bayesian Networks in an Observational Setting

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 56 references that are in the map.
- First posted on arXiv 25 Mar 2021.

## Builds on (most cited first, 14 of 14)

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [A Tutorial on Learning With Bayesian Networks](https://mlsanity.com/paper/2002.00269/) (2020)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Theory Refinement on Bayesian Networks](https://mlsanity.com/paper/1303.5709/) (2013)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Local algorithms for interactive clustering](https://mlsanity.com/paper/1312.6724/) (2013)
- [Near-Optimal Adaptive Compressed Sensing](https://mlsanity.com/paper/1306.6239/) (2013)
- [Active Learning Algorithms for Graphical Model Selection](https://mlsanity.com/paper/1602.00354/) (2016)
- [Advances in Bayesian Network Learning using Integer Programming](https://mlsanity.com/paper/1309.6825/) (2013)
- [Finding All Bayesian Network Structures within a Factor of Optimal](https://mlsanity.com/paper/1811.05039/) (2018)
- [A shotgun sampling solution for the common input problem in neural connectivity inference](https://mlsanity.com/paper/1309.3724/) (2013)
- [Active Learning for Undirected Graphical Model Selection](https://mlsanity.com/paper/1404.3418/) (2014)
- [Lower Bounds on Active Learning for Graphical Model Selection](https://mlsanity.com/paper/1607.02413/) (2016)

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

- [Causal discovery using dynamically requested knowledge](https://mlsanity.com/paper/2310.11154/) (2023)
- [Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees](https://mlsanity.com/paper/2110.14341/) (2021)
- [A Fast Algorithm for PAC Combinatorial Pure Exploration](https://mlsanity.com/paper/2112.04197/) (2021)
- [Causal Preference Elicitation](https://mlsanity.com/paper/2602.01483/) (2026)

## Abstract (arXiv)

We study active structure learning of Bayesian networks in an observational setting, in which there are external limitations on the number of variable values that can be observed from the same sample. Random samples are drawn from the joint distribution of the network variables, and the algorithm iteratively selects which variables to observe in the next sample. We propose a new active learning algorithm for this setting, that finds with a high probability a structure with a score that is ε-close to the optimal score. We show that for a class of distributions that we term stable, a sample complexity reduction of up to a factor of widetildeOmega(d3) can be obtained, where d is the number of network variables. We further show that in the worst case, the sample complexity of the active algorithm is guaranteed to be almost the same as that of a naive baseline algorithm. To supplement the theoretical results, we report experiments that compare the performance of the new active algorithm to the naive baseline and demonstrate the sample complexity improvements. Code for the algorithm and for the experiments is provided at https://github.com/noabdavid/activeBNSL.