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

AI summary

Authors: Loong Kuan Lee, Ragavi Krishnamoorthy, Nico Piatkowski (Hybrid Intelligence, Fraunhofer IAIS, Sankt Augustin, Germany) arXiv: 2607.26357v1 [cs.LG], 29 Jul 2026 — License: CC BY 4.0 Code: https://github.com/lklee9/k-order-Markov-blanket

Overview

Research area: Probabilistic graphical models — specifically Markov blanket (MB) discovery, which sits at the intersection of structure learning for Bayesian networks (BNs) and Markov random fields (MRFs), causal discovery, and feature selection.

Technical level: Intermediate to Advanced. The paper is definition-and-proof heavy, assuming comfort with conditional independence, graph separation, the Global Markov Property, and the faithfulness assumption. The core idea, however, is statable plainly: some relationships between variables only show up when you look at several variables at once.

Scope: The paper proposes a parameterized relaxation of the faithfulness assumption that accounts for parity-type dependencies among k+2 variables, and presents a proof-of-concept algorithm (kOMB) built on that relaxation.

What This Paper Is About

Most constraint-based MB discovery methods assume that any conditional independence present in the data distribution corresponds to a separation in the underlying graph — the faithfulness assumption. This assumption fails for higher-order relationships such as XOR and parity functions, and it can also fail on finite samples even when the true model is faithful, which in extreme cases makes algorithms report dependencies that do not exist in the true distribution. The paper generalizes faithfulness so that parity-like relationships spanning k+2 variables are explicitly permitted, and then builds an algorithm that exploits this relaxation.

Key Contributions

1. A k-order relaxation of faithfulness. The paper defines "k-order association" and "k-order dependence" for two variables Y and X relative to a set Z of cardinality k, formalizes the k-order faithfulness assumption (Assumption 2) and a strict version, and shows the relationship between the two via Lemma 1.

2. A bounded-separator assumption for tractability. The l-bounded separator assumption (Assumption 3) caps the cardinality of the "separating" sets that need to be tested, making the conditional independence tests feasible when the candidate Markov blanket is large. The paper notes an analogous but distinct notion, weakly K-separable graphs, from Soh and Tatikonda [2019].

3. The kOMB algorithm. A proof-of-concept algorithm, presented as three routines (Algorithm 1, the entry point; Algorithm 2, association mining; Algorithm 3, the practical conditional independence test), which modifies the Grow and Shrink algorithm of Margaritis and Thrun [1999] to consider adding entire sets of variables and to restrict conditioning sets to subsets of the current candidate MB. Correctness is established in Theorem 1 and Theorem 2.

4. Empirical demonstration against true and empirical faithfulness violations. The paper reports that kOMB recovers the MB under both kinds of violation and that it outperforms some existing constraint-based methods on benchmark datasets, with the authors arguing there is merit in examining relationships between 4 variables at a time rather than only 3.

Main Findings

• The 2-order relaxation fully recovers the MB with 100 samples in the motivating example. In Figure 1, the target Y is the output of a noisy Boolean function that returns 1 when only one of X1, X2, X3 is 1, with pr(Y = Z | X) = 0.9. Recall at 100 samples: Grow and Shrink 28.33, 0-OMB 28.33, 1-OMB 77.50, 2-OMB 100.0. At 1000 samples, all four methods reach 100.

• Parity violates both faithfulness and 2-adjacency faithfulness. Example 1 constructs a noisy parity BN over 4 variables where pr(Y = f(x) | X = x) = 0.9 and f(x) is the sum of inputs modulo 2. The paper shows Y is marginally independent of each X, and Y is independent of each pair {Xi, Xj}, yet Y is adjacent to all X in the DAG — so the graph is neither faithful nor 2-adjacent faithful to the distribution.

• Higher order can matter even when the graph is 2-adjacent faithful. Example 2 gives a noisy exactly-1 BN over 4 variables with pr(Y = g(X) | X) = 0.9 where g is the indicator that exactly one X equals 1. The true model is faithful (pr(Y=1, X=1) = 1/8 while pr(Y=1)·pr(X=1) = (3/8)×(4/8)), but a pathological sample yields empirical marginals E(Y) = 1/2 and E(Y, X1) = 1/4 = (1/2)×(1/2), inducing an empirical faithfulness violation. The paper notes that this particular DAG is still 2-adjacent faithful, so the Marx et al. [2021] algorithm would recover the MB — but argues this is not always the case, and that considering higher-order relationships can help.

• 1-order dependence captures unfaithful triples. The paper states that at k = 1, its notion of k-order dependence is capable of capturing relationships between unfaithful triples, including XOR-type relationships, similar to 2-association in Marx et al. [2021].

• Low sample sizes cause spurious dependencies. The paper anticipates (in Section 6.1, described via Figure 4) that limited sample size can lead MB discovery methods to discover spurious dependencies absent from the true distribution, observable as low precision at low sample sizes. The specific precision figures are not contained in the available text.

• Theorem 2 characterization. The call find_inter_dep(Y, ∅, S, V′, k, l) returns the empty set if and only if for every X in V′ and every Z of cardinality ≤ k, there exists an S′ of cardinality ≤ l such that Y is conditionally independent of X given Z ∪ S′. Otherwise it returns a nonempty set satisfying an l-bounded association condition.

Methodology in Plain English

The paper proceeds in the standard way for this literature: define assumptions, build an algorithm under them, prove the algorithm correct, then test it.

First, the authors formalize what it means for two variables to be dependent only when conditioned on a set Z of exactly k variables. Their definition requires that Y and X remain dependent given Z plus every subset of a separating set S — not just given Z ∪ S itself. This forces a clean distinction between the "dependants" Z and the potential "separators" S. They then define the k-order faithfulness assumption: if Y and X are graphically dependent given some set S, there must exist a set Z of size at most k such that Y and X are k-order associated with respect to Z over S.

Second, they add the l-bounded separator assumption, which says that if conditional independence holds given Z and every subset of S of size at most l, then it holds given Z and any subset of S at all. This bounds the number of conditional independence tests the algorithm has to run, which would otherwise be exponential in the size of the candidate MB.

Third, they adapt Grow and Shrink: instead of testing one new variable at a time against the current candidate MB, kOMB tries adding whole sets of up to k variables (to catch parity-type relations), and it restricts the conditioning sets used in tests to subsets of the current candidate MB of size at most l. Algorithm 2 searches for inter-dependent variable sets and prunes found dependence sets toward an inter-associated one; Algorithm 3 handles the practical conditional independence testing with the l-bound. Proofs appear in Appendix B (lemmas) and Appendix C (theorems), with Appendix F addressing whether the l-bound is mild on the networks used in Section 6.2.

The empirical evaluation is on benchmark datasets, per the contributions statement, but the specific dataset names, sizes, and the full result tables are outside the retrieved content.

Why This Matters

Impact on research. Faithfulness is a load-bearing assumption across constraint-based causal discovery and structure learning. A relaxation that explicitly accommodates parity-type and higher-order relations — rather than treating them as measure-zero oddities — widens the class of distributions under which MB discovery can be claimed correct. The paper's framing that empirical violations from finite samples are common (citing Uhler et al. [2013], Lemeire et al. [2012], Boeken et al. [2025]) makes the relaxation relevant even to researchers who never expect to meet a true parity relation in nature.

Real-world applications. The paper itself names its application areas rather than specific domains: structure learning for Bayesian networks and Markov random fields, causal discovery, and feature selection — with a further use as a subroutine in distributed, divide-and-conquer approaches to large-scale BN structure learning (Dong et al. [2025]). Downstream, these capabilities feed into:

• Feature selection pipelines where the goal is to identify the minimal set of variables that renders a target conditionally independent of everything else.
• Causal discovery workflows that need to distinguish genuine direct influences from relationships that only appear under specific joint configurations.
• Distributed or federated structure learning, where MB discovery is run locally before results are combined.
• Any modeling setting with parity-like or XOR-like structure, where standard constraint-based methods systematically miss edges.

Note: the paper text available here does not name specific industry domains or deployments; the above are the downstream uses implied by the stated application areas.

Industry relevance. MB discovery is attractive in industry precisely because it scales better than full structure learning and doubles as a principled feature selector. The 100-sample result in Figure 1 is the practically interesting one: a method that recovers the full MB at very small sample sizes has direct value where data collection is expensive.

Future Directions

1. Scale beyond the proof of concept. The paper explicitly labels kOMB a proof of concept. The search space of variable sets grows quickly with k, and the paper only commits to arguing (Appendix F) that the l-bound is mild on the networks used in Section 6.2. How the algorithm behaves on large or dense graphs is open.

2. Automating the choice of k. kOMB takes k and l as inputs. The Figure 1 results show that k = 2 succeeds where k = 0 and k = 1 fail on that instance, but the paper does not report a procedure for selecting k from data.

3. Broadening beyond parity-type violations. The relaxation targets parity-like relationships among k+2 variables. Whether other classes of unfaithfulness — including the "extreme" finite-sample cases producing spurious dependencies described in Section 6.1 — are equally handled is not resolved in the available text.

4. Finite-sample guarantees. The theorems are stated with respect to an estimated distribution E, while the motivating arguments concern empirical faithfulness violations. The gap between correctness given an oracle-style estimate and correctness from a finite sample is a natural next question, and connects to the low-precision-at-low-sample-size phenomenon reported in Figure 4.

Target Audience

Researchers in causal discovery and probabilistic graphical models who work on constraint-based structure learning; methodologists interested in weakening faithfulness and related assumptions (adjacency faithfulness, Pearl-minimality, SGS-minimality, frugality, 2-adjacency faithfulness); and applied machine learning practitioners using MB discovery as a feature selection or variable selection tool, particularly those working with data where XOR, parity, or exactly-one-of relationships are plausible. Readers need enough background in conditional independence and graphical models to follow the formal definitions; the algorithmic description in Section 5 is more accessible than the assumption machinery in Section 4.

Authors’ 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