aiqbench analysis
This research introduces a k-order relaxation of the faithfulness assumption to address higher-order dependencies like XOR relations that often break standard Markov blanket discovery methods. By proposing the proof-of-concept kOMB algorithm, it demonstrates improved recovery of graphical structures even when empirical data violates traditional conditional independence assumptions. This work advances causal inference and feature selection by making structure learning more robust in complex, finite-sample scenarios.
High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption
arXiv:2607.26357v1 Announce Type: cross 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
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: this https URL
17 pages (9 pages main text + supplementary material), 4 figures, 8 tables, 3 algorithms. Accepted at the 42nd Conference on Uncertainty in Artificial Intelligence (UAI 2026). Code: this https URL
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)
arXiv:2607.26357 [cs.LG]
(or arXiv:2607.26357v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2607.26357 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 225 words
Related coverage
J++ Lens: Jacobian Filtering Enables More Faithful Workspace Lenses
LessWrong · Oct 8, 2026
LiveLaw Supreme Court Half-Yearly Digest: January - June 2026 [Part 2]
livelaw.in · Sep 13, 2026
[AINews] not much happened today
Latent Space · Sep 18, 2026
PIRAMID: Progress and Plans
LessWrong · Jul 27, 2026