Graph-Guided Blocking for the E-Step in Missing-Data Causal Discovery

Learning a causal graph from data with missing entries forces a circular problem. You cannot fit the graph without the missing values, and you cannot fill in the missing values without the graph. The standard fix is expectation-maximization (EM). EM alternates between guessing the missing values under the current model (the E-step) and refitting the model to those guesses (the M-step). The current leading method for continuous nonlinear data, MissDAG, performs the E-step by jointly sampling all of a row's missing values with rejection sampling. That becomes too expensive long before graphs reach realistic size. This proposal uses the current candidate graph to split that joint sampling problem into small independent pieces. The splitting rule is d-separation, the graphical rule that tells you which variables in a directed acyclic graph are independent once you know certain others.

The idea can be stated in two sentences. For each data row, given which variables were observed in that row, the current graph says which groups of missing variables still depend on one another; we sample each group jointly and sample different groups independently. Groups linked through an observed common effect stay together, because observing a shared effect makes its causes dependent ("explaining away"), and a known information-theoretic bound tells us how much error this splitting can introduce when the graph is only approximately right.

Core Claim

The E-step of missing-data causal discovery can be made both cheaper and more faithful by using the graph that EM is already learning, rather than ignoring it. Two existing E-steps sit at opposite extremes. MissDAG's rejection-sampling Monte Carlo EM samples everything jointly, which is correct but scales poorly, as its authors report (MissDAG). Mean-field approximations sample everything independently, which is cheap but wrong when observed variables act as colliders (Structured Recognition for Generative Models with Explaining Away). We claim that the blocks d-separation defines are the right middle ground. Kenig's approximate-implication theorem makes this quantitative.

The bound works as follows. Let $A$ and $B$ be two blocks of a row's missing variables, and let $O$ be the variables observed in that row. Suppose the current graph declares $A$ and $B$ d-separated given $O$. Sampling $A$ and $B$ independently then incurs an average divergence from their true joint posterior equal to their conditional mutual information:

$$\mathbb{E}_{O}\,\mathrm{KL}\big(p(A,B\mid O)\,\|\,p(A\mid O)\,p(B\mid O)\big) = I(A;B\mid O) \le \epsilon .$$

Here $I(A;B\mid O)$ is the conditional mutual information and $\epsilon$ is the total conditional mutual information of the graph's local Markov statements. Those are the statements "each variable is independent of its non-descendants given its parents," evaluated on the current completed data. The equality is a standard identity. The inequality is Theorem 4.1 of Approximate implication with d-separation: for the recursive independencies that define a Bayesian network, any statement derived by d-separation inherits error at most $\epsilon$.

That paper proves robustness of graphical implication in the abstract. We turn its result into a runtime diagnostic inside EM. When the estimated $\epsilon$ is large, which usually happens in early iterations while the graph is still wrong, blocks are merged. As the graph improves, blocks are split.

Research Program

The algorithm keeps MissDAG's M-step unchanged: continuous acyclicity-constrained fitting of an additive noise model, in which each variable is a function of its parents plus independent noise. Only the E-step is replaced, so any change in accuracy or speed can be attributed to it.

At each iteration, rows are grouped by their missingness pattern. For each pattern, Bayes-Ball (Bayes-Ball) runs on the current graph. It serves two purposes. It finds the "requisite" observed variables that actually bear on each missing one. It also partitions the missing variables into blocks that are mutually d-separated given the observed ones. The Bayes-Ball traversal correctly keeps parents of an observed collider in the same block.

Each block is then sampled jointly with importance or rejection sampling, restricted to its requisite variables. This shrinks the dimension of each sampling problem from the number of missing variables in the row to the size of the largest block. Rejection sampling's acceptance rate decays roughly exponentially in that dimension, so this is where the speedup comes from.

After each M-step, $\epsilon$ is re-estimated from the completed data using a k-nearest-neighbour or Gaussian-copula conditional mutual information estimator. If the bound exceeds a tolerance relative to the data's total dependence, the two blocks with the highest estimated cross-dependence are merged for the next E-step.

The analytical part of the program asks when the blocks actually stay small. On the Unlikelihood of D-Separation proves that d-separation by a random conditioning set becomes exponentially rare as dense random graphs grow. That result constrains this proposal and could sink it. It concerns random conditioning sets for arbitrary pairs, however, whereas our conditioning set is the large observed portion of a row. The open question is whether that observed portion separates the few missing variables well enough, or whether conditioning on many observed colliders reconnects everything. We will characterize block-size distributions as a function of edge density and missingness rate, both analytically for Erdős–Rényi graphs and empirically. The goal is to state plainly in which regime the method helps and where it degrades to MissDAG.

Baselines

The naive reference point is the two-step pipeline MissDAG evaluated against: impute with MissForest or optimal transport, then run NOTEARS or GOLEM on the completed data (MissDAG). It will be run with the same data, the same M-step hyperparameter grid, and the same wall-clock budget.

The strongest existing method is MissDAG itself, with its joint rejection-sampling E-step. This is the true competitor on nonlinear data. It will be run from identical initializations with an equal number of EM iterations and equal Monte Carlo sample counts per row. The file gives no numeric SHD for MissDAG on DREAM4; its values appear only in a figure ("no reported result found on Lacuna for MissDAG DREAM4 SHD"). We will therefore rerun it ourselves. Beating it means matching its structural Hamming distance (SHD, the number of edge additions, deletions, and reversals separating the learned graph from the truth) within noise at graph sizes where it runs, while cutting E-step time by at least an order of magnitude. At larger graph sizes, beating it means achieving lower SHD within the same time budget where MissDAG must drop samples.

For discrete networks, the reference is Bayesian Structural EM (The Bayesian Structural EM Algorithm), for which the file reports only qualitative wins ("no reported result found on Lacuna for ALARM/INSURANCE scores").

For the Sachs protein data, FASK reports adjacency precision 0.84, adjacency recall 0.80, and zero reversed orientations on complete data (FASK with Interventional Knowledge Recovers Edges from the Sachs Model). We treat this as a complete-data ceiling rather than a missing-data competitor.

Three ablations isolate the key ingredient, collider-aware blocking chosen by the current graph. The first is fully factorized mean-field sampling, which removes the blocks. The second is blocks computed from the true graph, an oracle that gives an upper bound. The third is blocks computed once from the initial graph and never updated, which removes the adaptive $\epsilon$-driven merging.

Why not just…?

Why not just impute first and then run standard causal discovery? MissDAG already showed that two-step pipelines yield significantly higher SHD, degrading toward 50% missingness. The cause is that imputers optimize distributional fit and smooth away the residual structure that orients edges (MissDAG). We include the pipeline only as the floor.

Why not just run single-site Gibbs sampling, where each missing variable is resampled given its Markov blanket? This is the serious threat. Single-site Gibbs already uses graph structure, is cheap per step, and could plausibly match our method on sparse graphs with weak coupling. Its known weakness is slow mixing precisely when explaining away induces strong posterior correlation between parents of an observed child. Blocking addresses exactly that case. We will run Gibbs at matched compute, with a sweep over collider strength (the noise scale of the child relative to its parents' effects). If Gibbs matches us across the sweep, the contribution shrinks to the $\epsilon$ diagnostic, and we will report it that way.

Why not just use mean-field variational EM? Structured Recognition for Generative Models with Explaining Away shows that mean-field recognition models give worse likelihoods and entangled latents when observations have multiple latent causes. The mean-field ablation measures whether that failure carries over to SHD in graph learning.

Why not just run PC on the rows that are complete for each test? Constraint-based search with small conditioning sets loses precision on non-sparse graphs, and removing size limits makes it exponential (On the Unlikelihood of D-Separation). We will still run the causal-learn PC implementation (Causal-learn) with test-wise deletion as a reference.

Proposed Experiments

Synthetic nonlinear additive-noise graphs will range from 20 to 1000 nodes, with expected degree 1 to 6 and missingness under both MCAR (missing completely at random) and MAR (missing at random) at 10% to 50%. These measure SHD, E-step wall-clock time, and block-size distributions.

DREAM4 in silico networks follow MissDAG's protocol, for a direct comparison. The Sachs data with artificially masked entries measure how close each method stays to FASK's complete-data precision and recall. ALARM and INSURANCE with masking test the discrete version of the blocked E-step inside Bayesian Structural EM.

We will also test whether the $\epsilon$ diagnostic is informative. On synthetic data, where the true posterior coupling can be computed, we check whether the estimated $\epsilon$ upper-bounds the measured cross-block dependence and whether adaptive merging improves final SHD over fixed blocks.

The decisive checks are three. First, at 1000 nodes the blocked E-step must complete where rejection-sampling MissDAG cannot within a fixed budget. Second, it must beat single-site Gibbs at high collider strength. Third, on dense graphs, block sizes must stay well below the number of missing variables per row. If the third check fails, the Feigenbaum–Arpit rarity result applies to this conditioning regime too, and the method's scope is limited to sparse graphs.