Learning Bayesian and Markov Networks with an Unreliable Oracle

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.