Learning Bayesian and Markov Networks with an Unreliable Oracle

Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:2059-2074, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-harviainen26a, title = {Learning {Bayesian} and {Markov} Networks with an Unreliable Oracle}, author = {Harviainen, Juha and Parviainen, Pekka and Sharma, Vidya Sagar}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {2059--2074}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/harviainen26a/harviainen26a.pdf}, url = {https://proceedings.mlr.press/v337/harviainen26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Learning Bayesian and Markov Networks with an Unreliable Oracle %A Juha Harviainen %A Pekka Parviainen %A Vidya Sagar Sharma %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-harviainen26a %I PMLR %P 2059--2074 %U https://proceedings.mlr.press/v337/harviainen26a.html %V 337 %X 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.
APA
Harviainen, J., Parviainen, P. & Sharma, V.S.. (2026). Learning Bayesian and Markov Networks with an Unreliable Oracle. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:2059-2074 Available from https://proceedings.mlr.press/v337/harviainen26a.html.

Related Material