# Learning Bayesian and Markov Networks with an Unreliable Oracle

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 13 references that are in the map.
- First posted on arXiv 10 Mar 2026.

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

- [Properties of Bayesian Belief Network Learning Algorithms](https://mlsanity.com/paper/1302.6792/) (2013)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Models](https://mlsanity.com/paper/2502.08531/) (2025)
- [Structural perspective on constraint-based learning of Markov networks](https://mlsanity.com/paper/2403.08562/) (2024)

## Abstract (arXiv)

We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded number of errors. For Markov networks, we observe that a low maximum number of vertex-wise disjoint paths implies that the structure is uniquely identifiable even if the number of errors is (moderately) exponential in the number of vertices. For Bayesian networks, however, we prove that one cannot tolerate any errors to always identify the structure even when many commonly used graph parameters like treewidth are bounded. Finally, we give algorithms for structure learning when the structure is uniquely identifiable.