Certified Markov Blanket Discovery Under Synergy

Many causal questions concern one variable: which measurements directly cause a disease outcome, or which genes sit right next to a clinical trait in the causal graph. Local causal discovery answers these questions without reconstructing the whole graph. It finds the target's Markov blanket, the parents, children and co-parents of children that together make the target independent of everything else. Most such methods grow the blanket one variable at a time and keep a variable only if it carries signal about the target on its own. That rule fails when causes act only jointly. In a parity (XOR-like) relationship, each parent looks independent of the target, and the standard Grow-Shrink method recovers only about 28% of the parents (High-Order Markov Blanket Discovery via a k-Order Relaxation of the Faithfulness Assumption). The existing fix, kOMB, searches all variable groups up to a fixed size $k$ everywhere. It recovers the parity parents, but on dense networks like Barley it runs hundreds of times slower than the baselines.

This proposal takes from the optimization literature the tool designed for exactly this failure mode, the submodularity ratio. That is a number between 0 and 1 measuring how far a set function departs from "diminishing returns", and therefore how badly one-at-a-time greedy selection can miss a group whose value only appears jointly. The claim is that the information a candidate set carries about the target, $F(S) = I(T; S)$, is the right set function. A block version of its submodularity ratio is the quantitative form of the faithfulness relaxation that kOMB assumes qualitatively. Making that link explicit yields something no local discovery method currently returns: a data-computable bound on how much target information the returned blanket might still be missing. That bound in turn tells the algorithm when to stop and when to pay for higher-order search.

Core Claim

Write $\Omega$ for the candidate variables, $T$ for the target, and $F(S)=I(T;S)$ for the mutual information between $T$ and a set $S$. Under the usual Markov and positivity conditions, $F$ is monotone and the Markov blanket is the smallest set achieving $F(\Omega)$. Das and Kempe (Submodular meets Spectral) define the submodularity ratio $\gamma$. It is the largest number such that, from any current set $U$, the summed single-variable gains of the elements of any small set $\Omega'$ are at least $\gamma$ times the joint gain of $\Omega'$. They show greedy selection then achieves $(1-e^{-\gamma})$ of the optimum. We generalize singletons to blocks of at most $k$ variables:

$$\gamma_k \;=\; \min_{U,\;\Omega'} \; \max_{\mathcal{P}} \; \frac{\sum_{B \in \mathcal{P}} \big[F(U\cup B)-F(U)\big]}{F(U\cup \Omega')-F(U)},$$

where $\mathcal{P}$ ranges over partitions of $\Omega'\setminus U$ into blocks of size at most $k$. With $k=1$ this is the Das–Kempe ratio.

The proposal makes three claims.

The first is a correspondence theorem: positivity of $\gamma_k$ restricted to the target's neighborhood is equivalent to a quantitative version of Lee et al.'s $k$-order faithfulness. We expect the block size to be offset by one from their $k$. Under 3-parent parity, every single parent and every pair has zero gain from the empty set, so $\gamma_1=\gamma_2=0$ and only $\gamma_3>0$. Yet kOMB with their $k=2$ succeeds, so the exact indexing must be pinned down rather than assumed.

The second is a stopping certificate. Suppose greedy block selection has reached a set $U$, and let $g_k(U)$ be the largest gain of any size-$\le k$ block. Repeating the Das–Kempe argument gives a bound on the information still missing:

$$F(\Omega)-F(U) \;\le\; \frac{s\, g_k(U)}{\gamma_k},$$

where $s$ bounds the blanket size. The bound is small exactly when no affordable block adds information and the function is not too synergistic.

The third is an adaptive procedure. It runs cheap single-variable growth while a lower estimate of $\gamma_1$ along its own path stays high. It escalates to pairs or triples only when the certificate stays loose, and it samples blocks stochastically rather than enumerating them.

Relation to Prior Work

The work that supplies the method is the weak-submodularity line. Das and Kempe give the ratio and the greedy bound. Bian et al. (Guarantees for Greedy Maximization of Non-submodular Functions) tighten it with a curvature term and show that the ratio measured along the greedy path is near 1 on real data. Santiago and Yoshida (Weakly Submodular Function Maximization Using Local Submodularity Ratio) show that ratios measured along the algorithm's trajectory beat worst-case ones. Their "local" means "along the search path", not "near a node in a graph". We use that trajectory idea to estimate $\gamma_k$ on the path instead of globally. Khanna et al. (Scalable Greedy Feature Selection via Weak Submodularity) prove that stochastic greedy keeps $(1-e^{-\gamma}-\delta)$ guarantees, and we reuse this for block sampling. None of these papers touches causal structure. Their objectives are predictive fit, and they never consider blocks or faithfulness.

The work that motivates the proposal is the local discovery line. Lee et al. document the synergy failure and fix it with fixed-order enumeration, but they offer no stopping bound and no adaptivity. HITON (HITON) and HLCD (Hybrid Local Causal Discovery) both select and prune greedily, using p-values and local score differences respectively, with no approximation guarantee. HLCD and CMB (Local Causal Discovery of Direct Causes and Effects) also note that a parent dropped in the first phase can never be recovered. Our certificate targets that dropped-variable failure directly. We leave edge orientation to CMB-style routines downstream.

The closest bridge between the two lines is ABCD (ABCD-Strategy), which uses DR-submodularity to choose interventions for targeted discovery. It is interventional and assumes full diminishing returns. We are observational and deal with exactly the regime where diminishing returns fails.

One tension from the literature constrains the design: causal set functions are often non-monotone, because conditioning on a collider or a noisy variable can hurt. That concern applies to conditional-independence statistics. Population mutual information $I(T;S)$ is monotone, so the standard theory applies. Plug-in estimates, however, inflate with set size. We therefore use permutation-calibrated gains, which subtract the gain expected from an independent variable of the same arity, and we treat estimation error as an additive slack in the certificate.

Research Program

The theory phase proves the block greedy bound and the certificate inequality. It then makes precise the correspondence between $\gamma_k$ and $k$-order faithfulness, including the off-by-one question raised by parity. Finally, it bounds $\gamma_k$ restricted to the candidate blanket from below in two settings. For Gaussian systems this goes through sparse eigenvalues of the conditional covariance, following Das and Kempe. For discrete systems it goes through the smallest nonzero interaction information of order at most $k+1$.

The algorithm phase builds an estimator for $\gamma_k$ along the trajectory. For each step it computes the ratio of the best block gain to the joint gain of the next accepted group, and it takes a running minimum with a bootstrap lower confidence bound. The escalation rule raises $k$ when the certificate exceeds a tolerance and the single-variable ratio estimate falls below a threshold. Block candidates come from stochastic sampling. A shrink phase removes false positives, as in Grow-Shrink.

The evaluation phase measures blanket recovery, test counts, and whether the certificate is calibrated, meaning whether the true missing information stays below the bound.

Baselines

The naive reference point is Grow-Shrink and IAMB, single-variable greedy blanket growth with no escalation. On noisy 3-parent parity it reaches about 28% recall, the figure reported by Lee et al.

The strongest method for synergy is kOMB at $k=2$ from High-Order Markov Blanket Discovery. It reaches 100% recall on noisy parity with 100 samples and outperforms baselines in F1 on ALARM1 and Insurance. However, no reported result was found on Lacuna for its exact F1 values on those networks, and it is reported as hundreds of times slower than baselines on Barley. To beat it, our method must match its recall on the Boolean networks and its F1 within noise on ALARM1, Insurance and Mildew, while using at least an order of magnitude fewer conditional-independence tests on Barley.

The strongest general local method is HLCD, which achieved the highest F1 in 27 of 28 setups across 14 networks at $n=500$ and $n=1000$. It shows we lose nothing on ordinary faithful networks, where our method should reduce to single-variable growth. On those networks we must tie HLCD's F1 and structural Hamming distance, and on synergy-injected variants we must exceed it.

CMB serves as the downstream orientation stage and as a sanity reference, using its reported total error of 4.30 versus 8.55 for PC on INSUR3.

All methods run through causal-learn (Causal-learn) or the authors' code where available. They share the same samples and the same CI test family: G-squared for discrete data and Fisher-z or kernel tests for continuous data. Significance levels are tuned on the same grid, and every method gets the same cap on CI tests. We report accuracy against test count, not just at convergence.

Two ablations isolate the key ingredient. The first is fixed-$k$ block greedy with no certificate-driven escalation, which isolates adaptivity. The second is adaptive escalation triggered by a raw residual-dependence test instead of the $\gamma$-scaled certificate, which isolates the role of the ratio itself.

Why not just…?

Why not just run Grow-Shrink and then sweep all pairs once at the end? This is the most serious threat. On pairwise synergy, a single residual pair sweep could match our recall at comparable cost. Our answer is that the sweep returns a set but no statement about what it may have missed, and it has no principled reason to stop at pairs: it misses triple synergies such as 3-parent parity unless it is told to sweep triples. The second ablation above is exactly this sweep with a heuristic trigger. If it matches our method on F1, test count, and missed information at every synergy order, we will report that the practical gain is nil. The contribution would then reduce to the certificate and the theory, and we would say so.

Why not just run kOMB with a larger $k$? Its cost grows combinatorially, and the Barley runtime already shows this at small $k$. Our experiments measure where on the accuracy-versus-tests curve each method sits, and they check whether adaptive escalation pays the higher-order price only on targets that need it.

Why not just use Lasso or graphical lasso on the target? Convex penalties rank variables by their linear contribution, which is zero for parity-like dependence, so they cannot see these synergies at all. Kaufmann et al. (Bayesian Markov Blanket Estimation) also report that global Bayesian graphical lasso over-fits with spurious edges relative to local blanket estimation. We include Lasso on the Gaussian synthetic settings as a check.

Why not just learn the global graph and read off the neighborhood? The file's evidence argues against it. CMB is one to two orders of magnitude cheaper in tests on CHILD3 and INSUR3, and it halves total error versus PC on INSUR3. Global methods share the same faithfulness blindness, so they gain nothing on synergy.

Proposed Experiments

The first decisive check runs on Lee et al.'s 4-variable Boolean networks (AND, OR, XOR, exactly-2, parity) at 100 to 2000 samples. We compute exact population $\gamma_k$ by enumeration and verify that it is zero exactly where the theory predicts. We confirm that the estimated trajectory ratio tracks it, and that the method escalates only on XOR, parity and exactly-2.

The second embeds these Boolean mechanisms as replacement conditional distributions for chosen targets in ALARM, Insurance, Mildew and Barley. This creates realistic networks with known synergistic blankets. We measure blanket F1, recall of synergistic parents, and CI-test counts against all baselines, using the unmodified networks as the faithful control.

The third tests calibration. Across many targets and sample sizes, we compute the fraction of runs in which the true missing information $F(\Omega)-F(U)$, known from the generating network, exceeds the certified bound. Our claim fails if this fraction substantially exceeds the nominal level.

The fourth uses Gaussian synthetic graphs with strong collinearity, where the spectral lower bound on $\gamma_1$ can be checked against the trajectory estimate.

The fifth runs on Sachs flow cytometry as a real-data sanity check. There, HLCD's reported 0.01s runtime sets the efficiency bar. We report which targets triggered escalation and whether the added variables are consistent with the accepted signaling network.

The proposal fails if the certificate is badly miscalibrated at realistic sample sizes. It also fails if the heuristic-trigger ablation matches the full method everywhere, in which case the submodularity ratio contributes theory but not a better algorithm.