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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 37 references that are in the map.
- First posted on arXiv 29 Jul 2026.

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

- [Strong Completeness and Faithfulness in Bayesian Networks](https://mlsanity.com/paper/1302.4973/) (2013)
- [Testing Conditional Independence on Discrete Data using Stochastic Complexity](https://mlsanity.com/paper/1903.04829/) (2019)
- [A Weaker Faithfulness Assumption based on Triple Interactions](https://mlsanity.com/paper/2010.14265/) (2020)
- [DCILP: A Distributed Approach for Large-Scale Causal Structure Learning](https://mlsanity.com/paper/2406.10481/) (2024)
- [Are Bayesian networks typically faithful?](https://mlsanity.com/paper/2410.16004/) (2024)

## Abstract (arXiv)

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