High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption

Loong Kuan Lee, Ragavi Krishnamoorthy, Nico Piatkowski
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:3338-3354, 2026.

Abstract

The problem of learning the graphical {Markov} blanket (MB) of a variable from data has applications in many areas such as structure learning for {Bayesian} networks and {Markov} random fields, causal discovery, and feature selection. However, a common assumption most methods make is that the conditional independencies in the distribution imply the same separation in the graphical structure—also known as the faithfulness assumption. Unfortunately, this assumption can be violated by higher-order dependencies such as {XOR} and parity-type relations, and—on finite samples—by empirical violations that, in extreme cases, even induce spurious dependencies absent from the true distribution. Therefore, in this paper we propose a “k-order” relaxation of the faithfulness assumption that captures parity type relationships between k+2 variables. We then propose a proof of concept algorithm called k-order {Markov} blanket (kOMB) that uses this relaxation for MB discovery. Finally, we empirically show how kOMB can recover the MB of a variable under both true and empirical violations of faithfulness. Code available at: https://github.com/lklee9/k-order-{Markov}-blanket.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-lee26b, title = {High-Order {Markov} Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption}, author = {Lee, Loong Kuan and Krishnamoorthy, Ragavi and Piatkowski, Nico}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {3338--3354}, 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/lee26b/lee26b.pdf}, url = {https://proceedings.mlr.press/v337/lee26b.html}, abstract = {The problem of learning the graphical {Markov} blanket (MB) of a variable from data has applications in many areas such as structure learning for {Bayesian} networks and {Markov} random fields, causal discovery, and feature selection. However, a common assumption most methods make is that the conditional independencies in the distribution imply the same separation in the graphical structure—also known as the faithfulness assumption. Unfortunately, this assumption can be violated by higher-order dependencies such as {XOR} and parity-type relations, and—on finite samples—by empirical violations that, in extreme cases, even induce spurious dependencies absent from the true distribution. Therefore, in this paper we propose a “k-order” relaxation of the faithfulness assumption that captures parity type relationships between k+2 variables. We then propose a proof of concept algorithm called k-order {Markov} blanket (kOMB) that uses this relaxation for MB discovery. Finally, we empirically show how kOMB can recover the MB of a variable under both true and empirical violations of faithfulness. Code available at: https://github.com/lklee9/k-order-{Markov}-blanket.} }
Endnote
%0 Conference Paper %T High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption %A Loong Kuan Lee %A Ragavi Krishnamoorthy %A Nico Piatkowski %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-lee26b %I PMLR %P 3338--3354 %U https://proceedings.mlr.press/v337/lee26b.html %V 337 %X The problem of learning the graphical {Markov} blanket (MB) of a variable from data has applications in many areas such as structure learning for {Bayesian} networks and {Markov} random fields, causal discovery, and feature selection. However, a common assumption most methods make is that the conditional independencies in the distribution imply the same separation in the graphical structure—also known as the faithfulness assumption. Unfortunately, this assumption can be violated by higher-order dependencies such as {XOR} and parity-type relations, and—on finite samples—by empirical violations that, in extreme cases, even induce spurious dependencies absent from the true distribution. Therefore, in this paper we propose a “k-order” relaxation of the faithfulness assumption that captures parity type relationships between k+2 variables. We then propose a proof of concept algorithm called k-order {Markov} blanket (kOMB) that uses this relaxation for MB discovery. Finally, we empirically show how kOMB can recover the MB of a variable under both true and empirical violations of faithfulness. Code available at: https://github.com/lklee9/k-order-{Markov}-blanket.
APA
Lee, L.K., Krishnamoorthy, R. & Piatkowski, N.. (2026). High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:3338-3354 Available from https://proceedings.mlr.press/v337/lee26b.html.

Related Material