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

• URL: http://arxiv.org/abs/2607.26357v1
• Date: Wed, 29 Jul 2026 00:12:43 GMT
• Title: High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption
• Abstract summary: We propose a proof of concept algorithm called k-order Markov blanket (kOMB) that uses this relaxation for MB discovery.<n>We empirically show how kOMB can recover the MB of a variable under both true and empirical violations of faithfulness.
• Score: 1.6669836414758343
• License: http://creativecommons.org/licenses/by/4.0/
• 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

Related papers

• When Does Low-Bit Quantization Preserve the Decisions of Vector Search? [13.71460633144793]
  Low-bit quantization can achieve high recall on some vector representations and fail sharply on others.<n>We study quantized vector search at the level of the comparisons consumed by ranking and graph-pruning algorithms.<n>Across learned, classical, and synthetic embeddings, standardized exact margins predict held-out ranking and pruning flip rates substantially better than global rank correlation.
  arXiv  Detail & Related papers  (2026-09-09T08:06:50Z)
• Locally Confident, Globally Stuck: The Quality-Exploration Dilemma in Diffusion Language Models [52.61023005303122]
  We show that low-confidence remasking improves a proxy for quality while constraining the entropy of the induced sequence distribution.<n>We develop a simple Independent--Hastings sampler that approximately targets this distribution during decoding.
  arXiv  Detail & Related papers  (2026-04-01T02:01:30Z)
• Causal computations in Semi Markovian Structural Causal Models using divide and conquer [0.20999222360659608]
  Bjru et al. proposed a novel divide-and-conquer algorithm for bounding counterfactual probabilities in structural causal models.<n>In this paper, we investigate extending the methodology to textitsemi-Markovian SCMs.<n>Such models are capable of representing confounding relationships that Markovian models cannot.
  arXiv  Detail & Related papers  (2025-11-17T19:08:53Z)
• Flock: A Knowledge Graph Foundation Model via Learning on Random Walks [26.568227939080703]
  We study the problem of zero-shot link prediction on knowledge graphs (KGs)<n>We present Flock, a KGFM that iteratively samples random walks, encodes them into sequences via a recording protocol, embeds them with a sequence model, and aggregates representations of nodes and relations via learned pooling.<n>Flock perfectly solves our new diagnostic dataset Petals where current KGFMs fail, and achieves state-of-the-art performances on entity- and relation prediction tasks on 54 KGs from diverse domains.
  arXiv  Detail & Related papers  (2025-10-01T23:09:46Z)
• Prototype-based Aleatoric Uncertainty Quantification for Cross-modal Retrieval [139.21955930418815]
  Cross-modal Retrieval methods build similarity relations between vision and language modalities by jointly learning a common representation space. However, the predictions are often unreliable due to the Aleatoric uncertainty, which is induced by low-quality data, e.g., corrupt images, fast-paced videos, and non-detailed texts. We propose a novel Prototype-based Aleatoric Uncertainty Quantification (PAU) framework to provide trustworthy predictions by quantifying the uncertainty arisen from the inherent data ambiguity.
  arXiv  Detail & Related papers  (2023-09-29T09:41:19Z)
• Covariate shift in nonparametric regression with Markovian design [0.0]
  We show that convergence rates for a smoothness risk of a Nadaraya-Watson kernel estimator are determined by the similarity between the invariant distributions associated to source and target Markov chains. We extend the notion of a distribution exponent from Kpotufe and Martinet to kernel transfer exponents of uniformly ergodic Markov chains.
  arXiv  Detail & Related papers  (2023-07-17T14:24:27Z)
• Disentanglement of Correlated Factors via Hausdorff Factorized Support [53.23740352226391]
  We propose a relaxed disentanglement criterion - the Hausdorff Factorized Support (HFS) criterion - that encourages a factorized support, rather than a factorial distribution. We show that the use of HFS consistently facilitates disentanglement and recovery of ground-truth factors across a variety of correlation settings and benchmarks.
  arXiv  Detail & Related papers  (2022-10-13T20:46:42Z)
• Learning with Stochastic Orders [25.795107089736295]
  Learning high-dimensional distributions is often done with explicit likelihood modeling or implicit modeling via integral probability metrics (IPMs) We introduce the Choquet-Toland distance between probability measures, that can be used as a drop-in replacement for IPMsational. We also introduce the Variational Dominance Criterion (VDC) to learn probability measures with dominance constraints.
  arXiv  Detail & Related papers  (2022-05-27T00:08:03Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.