🤖 machine learning

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

This paper introduces a k-order relaxation of the faithfulness assumption to address violations caused by higher-order dependencies like XOR relations, and proposes the k-order Markov blanket (kOMB) algorithm to effectively discover graphical Markov blankets under both true and empirical faithfulness violations.

Original authors: Loong Kuan Lee, Ragavi Krishnamoorthy, Nico Piatkowski

Published 2026-07-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Loong Kuan Lee, Ragavi Krishnamoorthy, Nico Piatkowski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: who is really influencing whom in a crowded room of people? In the world of data science, this is called "learning the structure" of a network. Scientists use special maps called graphs to show how different variables—like temperature, humidity, or stock prices—talk to each other. The most important tool in this detective's kit is the "Markov Blanket." Think of the Markov Blanket as a variable's personal security detail or its immediate family. It includes everyone who has a direct, secret handshake with your target variable. If you know everything about this security detail, you don't need to know anything about the rest of the crowd to predict what your target is doing. This concept is crucial for building smart AI, figuring out what causes diseases, and picking the best features for machine learning models.

However, there is a catch. Most detective methods rely on a rule called "faithfulness." This rule assumes that if two people in the crowd seem to be acting independently (like two strangers ignoring each other), they must actually be strangers in the network's map. But life is messy. Sometimes, two people might look like strangers because they are secretly coordinating their actions in a complex, hidden way—like a group of friends playing a game of "XOR" (where the answer is only "yes" if exactly one person says "yes," but no one can tell just by looking at two of them). When these hidden, high-order games happen, or when we don't have enough data to see the whole picture, the standard detective methods get confused. They might miss the real connections or invent fake ones, leading to a broken map.

This paper, titled "High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption," introduces a new, more flexible way to solve this mystery. The authors, Loong Kuan Lee, Ragavi Krishnamoorthy, and Nico Piatkowski, propose that we stop assuming the world is always simple and straightforward. Instead, they suggest a "k-order relaxation." Imagine that standard methods only look for clues involving two or three people at a time. The new method, called kOMB, is willing to look at groups of four, five, or even more people simultaneously to catch those tricky, hidden coordination games (like the XOR or parity relationships mentioned earlier).

The paper argues that the old "faithfulness" assumption is too rigid. It explicitly rules out the idea that we can always trust simple independence tests to reveal the whole truth, especially when data is scarce or when variables interact in complex, "parity-type" ways (where the whole is different from the sum of its parts). The authors don't just suggest this; they build a proof-of-concept algorithm called kOMB (k-Order Markov Blanket) to test it. They show that by relaxing the rules to allow for these higher-order relationships, kOMB can successfully find the correct "security detail" for a variable even when the data is noisy or when the variables are playing those tricky high-order games.

In their experiments, the team tested kOMB on both made-up data (simulations) and real-world benchmark datasets. They found that when the data was small or the relationships were complex (like the "parity" problem where a variable depends on the sum of others being odd or even), kOMB was much better at finding the true connections than older methods. For instance, in a simulation with just 100 samples, kOMB with a "2-order" setting recovered the full Markov Blanket 100% of the time, while older methods struggled. On real-world datasets like "Alarm" and "Insurance," kOMB also performed very well, often beating established methods, though it did take more time to run, especially when looking at larger groups of variables. The paper concludes that while this new method is a bit slower and more complex, it is a powerful tool for uncovering the hidden, high-order secrets that simpler methods miss, offering a more robust way to understand how variables truly interact in a chaotic world.

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

Problem Statement

The Markov blanket (MB) discovery problem involves inferring the graphical MB of a target variable $Y$ from a dataset sampled from a joint distribution $P$ . This task is fundamental to structure learning in Bayesian networks (BNs) and Markov random fields (MRFs), causal discovery, and feature selection.

Most existing constraint-based MB discovery methods rely on the faithfulness assumption: the premise that any conditional independence (CI) in the distribution $P$ implies a corresponding separation in the graphical structure $G$ (and vice versa). However, this assumption is frequently violated in two ways:

True Violations: Certain functional relationships, such as noisy XOR or higher-order parity functions, create dependencies that are "unfaithful" to the graph structure. For instance, in a noisy parity function involving $k+2$ variables, pairwise and lower-order conditional independencies may exist despite the variables being connected in the graph.
Empirical Violations: Even when the true distribution is faithful, finite sample sizes can lead to statistical errors where empirical CIs do not match the true distribution. In extreme cases with small samples, algorithms may fail to recover the true MB or discover spurious dependencies.

While previous relaxations, such as 2-adjacency faithfulness, address XOR-type relations (involving 3 variables), they fail to capture higher-order parity relationships involving more than 3 variables.

Methodology

The $k$ -Order Faithfulness Relaxation

The authors propose a generalization of the faithfulness assumption called $k$ -order faithfulness. This relaxation is designed to capture parity-type dependencies among $k+2$ variables.

$k$ -Order Dependence: Two variables $Y$ and $X$ are defined as $|Z|$ -order dependent given a set $Z$ if they remain conditionally dependent regardless of any subset of a separating set $S$ being added to the conditioning set, provided $|Z| = k$ .
Assumption: A graph $G$ is $k$ -order faithful to $P$ if, for any variables $Y, X$ and any set $S$ , if $Y$ and $X$ are conditionally independent given $Z \cup S'$ for some $Z$ of size $\le k$ and some $S' \subseteq S$ , then they are graphically separated by $S$ .
Contrapositive: If $Y$ and $X$ are not separated by $S$ in the graph, there must exist a set $Z$ of size $\le k$ such that $Y$ and $X$ are associated (dependent) over $Z$ relative to $S$ .

To make the algorithm computationally feasible, the authors introduce a $l$ -bounded separator assumption. This assumes that if $Y$ and $X$ are conditionally independent given a large set, there exists a subset of that set with size $\le l$ that also renders them independent. This bounds the search space for conditioning sets during CI tests.

The kOMB Algorithm

The paper introduces kOMB ( $k$ -order Markov blanket), a proof-of-concept algorithm that modifies the Grow and Shrink (GS) algorithm to operate under these new assumptions.

Grow Phase: Instead of testing individual variables, kOMB iteratively searches for subsets of variables (up to size $k$ ) that, when conditioned upon with the current candidate MB, reveal dependencies between the target $Y$ and other variables. It utilizes a recursive search (find_inter_dep) to identify "inter-associated" sets.
Shrink Phase: The algorithm removes variables from the candidate MB if they can be separated from $Y$ by a subset of the remaining MB variables (bounded by $l$ ).
Theoretical Guarantees: The authors prove that under the Global Markov Property, $k$ -order faithfulness, and the $l$ -bounded separator assumption, kOMB correctly recovers the graphical MB of a variable.

Key Contributions

Theoretical Framework: The definition of $k$ -order faithfulness, which generalizes previous relaxations (like 2-adjacency faithfulness) to handle higher-order parity relationships involving $k+2$ variables.
Algorithmic Implementation: The development of kOMB, a constraint-based algorithm that leverages $k$ -order faithfulness to discover MBs in the presence of high-order dependencies.
Empirical Validation: Demonstration that kOMB can recover MBs in scenarios where traditional methods fail due to both true unfaithfulness (e.g., parity functions) and empirical unfaithfulness (finite sample effects).

Experimental Results

Synthetic Data

The authors tested kOMB on synthetic Bayesian networks with 4 variables, where the target $Y$ was generated via five different Boolean functions (including XOR, parity, and "exactly-1").

Performance: kOMB consistently outperformed the Grow and Shrink (GS) algorithm and other existing methods (IAMB, HITON, etc.).
High-Order Recovery: For the parity function (a 3-variable XOR extension), standard methods failed to recover the MB. kOMB with $k=2$ achieved perfect recovery (F1 score of 1.0), confirming its ability to detect dependencies requiring 3 conditioning variables.
Sample Size Sensitivity: In low-sample regimes, kOMB with higher $k$ values demonstrated superior robustness against empirical faithfulness violations compared to lower-order methods.

Benchmark Datasets

Experiments were conducted on four standard datasets: Alarm1, Barley, Insurance, and Mildew.

Performance: kOMB generally achieved competitive or superior F1 scores compared to state-of-the-art methods like BAMB, HITON, and MMMB.
Order Sensitivity: The benefit of higher $k$ values was dataset-dependent. On lower-cardinality networks (Alarm1, Insurance), $k=2$ improved performance. On high-cardinality networks (Barley, Mildew), $k=1$ often performed better, as larger conditioning sets led to underpowered CI tests at the given sample size (5000 samples).
Runtime: As expected, runtime increased significantly with $k$ and network cardinality. For high-cardinality networks, $k=2$ configurations were substantially slower than $k=1$ or baseline methods.

Significance and Claims

The paper positions kOMB as a proof-of-concept demonstrating that exploiting higher-order dependencies can improve MB discovery in the presence of faithfulness violations.

Modest Claims: The authors explicitly state that kOMB is not optimized for efficiency; its primary goal is to validate the theoretical utility of $k$ -order faithfulness.
Practical Implications: The results suggest that for problems involving parity-like relationships or where sample sizes are limited, relaxing the faithfulness assumption to higher orders is beneficial.
Future Directions: The paper identifies the need for approximate algorithms to reduce the worst-case computational cost, principled methods for selecting $k$ and $l$ without expert knowledge, and the integration of more recent conditional independence tests beyond the G-test and SCI test used in the experiments.

The work establishes that while traditional faithfulness assumptions are often sufficient, specific structural relationships (like parity) and finite-sample realities necessitate a more flexible, higher-order approach to graphical model learning.