Structure-Averaged Multiple Imputation with Bayesian Networks

When a dataset has holes, a common way to analyze it honestly is multiple imputation: fill in the missing entries several times with plausible random values, run the analysis on each completed copy, and combine the results. The spread across copies tells the analyst how much the missing data should widen their confidence intervals. The quality of this procedure depends entirely on the model that generates the fill-ins. Bayesian networks are a natural choice for that model. They describe the joint distribution of many variables as a product of small local tables, each giving one variable's distribution given a few "parent" variables, with the parents forming a directed acyclic graph. Unlike the usual chained-regression imputer, a Bayesian network always defines one coherent joint distribution. Existing Bayesian-network imputers, however, either fill each hole with a single best guess or commit to a single learned graph. With a single graph, any association the graph leaves out is quietly imputed as absent, so downstream estimates are pulled toward zero and their intervals are too narrow.

We propose a sampler that draws each imputed dataset from a different graph, sampled from an approximate posterior over graph structures, as well as from different parameters. The central observation connects the two literatures. Learning structure from incomplete data is hard because the likelihood stops splitting into independent per-variable pieces (Learning Bayesian Networks from Incomplete Data; On the Geometry of Bayesian Graphical Models with Hidden Variables). Once the data are completed by a draw, the score splits again, and local graph moves become cheap. Imputation is therefore not only the output of the method but also what makes sampling over structures tractable. Our main claim is testable: averaging over structure restores nominal confidence-interval coverage for downstream associations whose supporting edges are uncertain. Single-graph Bayesian-network imputation and chained equations both fail on those associations, in opposite ways.

What exists and what is missing

Three papers come closest, and each stops short in a specific way. Bayesian network data imputation with application to survival tree analysis learns a globally optimal network with Structural EM and exact search, then fills each hole with the posterior mean or mode before fitting survival trees. Its single deterministic completion understates variance, and it reports no gain when dependencies are weak. Learning Bayesian Networks with Incomplete Data by Augmentation searches for the one completion that maximizes the network score (a "hard EM" objective). It is again a point estimate, and its exact version is exponential in the number of missing entries. Improving the imputation of missing data with Markov Blanket discovery uses conditional-independence tests to restrict each variable's predictors to its Markov blanket, meaning its parents, children, and children's other parents. It then runs random-forest imputation, which produces a single completed dataset with no probabilistic model behind it.

All three motivate the gap: Bayesian-network structure helps imputation, but none turns it into proper multiple imputation, and none treats the graph itself as uncertain. Two other papers supply the method. The Bayesian Structural EM Algorithm shows that scores decompose under exponential-family factors with parameter independence and modularity, which is exactly what makes our structure step local. Update Rules for Parameter Estimation in Bayesian Networks supplies the classical EM machinery we use for initialization. Correlation visualization under missing values constrains the design. It shows that low imputation error can coexist with badly distorted correlations, so we evaluate the joint structure and the downstream inference, not error on individual entries.

Core mechanism

The sampler is a data-augmentation Gibbs chain over three blocks. $X_{\text{mis}}$ denotes the missing entries, $\theta$ the conditional probability tables, and $G$ the graph. Each sweep performs three steps:

$$X_{\text{mis}} \sim P(X_{\text{mis}} \mid X_{\text{obs}}, G, \theta), \qquad \theta \sim \text{Dir}(\alpha + N(G, X)), \qquad G \sim \text{local MCMC move under } P(G \mid X).$$

Here $N(G, X)$ are the parent-configuration counts in the currently completed data and $\alpha$ the Dirichlet prior pseudo-counts. Each step is chosen to be cheap.

The first step is exact forward-filtering, backward-sampling inference on the current network, done per record with a jointree. The second is conjugate, so it costs nothing beyond counting. The third proposes adding, deleting, or reversing a single edge, or makes a move over node orderings in the spirit of BIC-based node order learning. Because the data are complete at that moment, each proposal changes only one or two terms of the marginal likelihood.

After burn-in, we keep $m$ completed datasets spaced far enough apart in the chain to be nearly independent, and combine analyses with Rubin's rules. Missingness indicators can optionally be added as extra nodes, so that edges into them represent non-random missingness, following the indicator idea in the Markov-blanket paper. We treat this as a stress test rather than a guarantee, because such mechanisms are not always identifiable.

Research Program

The work has three parts.

The first is to build the sampler for discrete networks. We will add a Gaussian-network variant with conjugate normal–Wishart updates for continuous benchmarks such as ECOLI70, and compare order-space and edge-space structure moves for mixing.

The second is to characterize when structure averaging matters. Our hypothesis is that its benefit concentrates on estimands whose supporting edges have intermediate posterior probability. We will report coverage as a function of each edge's posterior inclusion probability, which yields a diagnostic practitioners can compute from the chain.

The third is to study the regime in which Bayesian network data imputation with application to survival tree analysis found no gain, its "Model A" with weak dependencies. There the honest answer may be that the method merely matches simple imputation while reporting appropriately wide intervals. We will test whether that is so.

Baselines

The naive reference points are complete-case analysis and single mean or mode imputation. They establish how much any imputation buys and how badly variance is understated when it is ignored.

The strongest existing competitor for valid inference is standard chained-equation multiple imputation. Each incomplete variable gets a logistic or multinomial regression on all other variables, with parameter draws, as used in Clinical predictive modelling of post-surgical recovery in individuals with cervical radiculopathy. It is the default analysts actually use, and because it includes every predictor, it rarely drops an association. We will run it with the same $m$, the same number of iterations as our chain, and default regularization tuned on a held-out mask. Beating it means equal or better coverage with narrower intervals and lower bias, especially as the number of variables grows (ALARM, ARTH150-scale) and the full conditionals become over-parameterized.

For record-level completion, the strongest Bayesian-network competitor is optimistic augmentation from Learning Bayesian Networks with Incomplete Data by Augmentation. It reports imputation accuracy "between 79% and 84%" on ASIA and Breast Cancer, against "around 43–50%" for Structural EM, and 97.5% classification accuracy on LUCAS under non-random missingness. We will reproduce its hill-climbing version on the same masks. Beating it on its own terms means matching that accuracy using the mode across our $m$ draws, while also delivering calibrated intervals, which it cannot produce. On the inference metrics there is no comparison to quote: we found no reported coverage results on Lacuna for any Bayesian-network imputer, nor for MBMF or RefiDiff. We will also include Rancoita-style deterministic imputation and the Markov-blanket random-forest imputer, each run with its published settings on the same masks.

Two ablations isolate the key ingredient. The first, single-graph multiple imputation, fixes the MAP graph from Structural EM and draws only parameters and completions. The second, parametric Markov-blanket chained equations, runs chained regressions restricted to Markov blankets read off that same graph. If the full method does not beat the first ablation on uncertain-edge estimands, structure averaging is not doing the work.

Why not just…?

Why not just use chained equations with all predictors? Including every predictor avoids omitting associations, which is exactly our concern, so this is a real threat in low dimensions. Its weaknesses are incompatible conditionals and over-parameterization as the number of variables grows. The correlation study found it competitive only at small scale (Correlation visualization under missing values). Our sweep from ASIA (8 variables) to ALARM (37) and ECOLI70/ARTH150 is designed to locate the crossover. If chained equations match us everywhere, we will report that.

Why not just bootstrap the data and rerun Structural EM for each imputation? This also yields structure variation and is the most serious alternative. It costs $m$ full structure searches, and each replicate can stall in a separate local optimum, so the spread across replicates mixes posterior uncertainty with optimizer noise. We will include it as a baseline at matched wall-clock time. If it gives equal coverage, the contribution narrows to showing that structure uncertainty must be propagated, and that a cheap bootstrap suffices to do it. That is still a useful negative result for the field.

Why not just use a deep generative imputer such as MIDA or RefiDiff? MIDA and RefiDiff produce stochastic fill-ins but have no parameter posterior. The correlation study found that GAIN-style models distort joint structure even when their per-entry error is low. We will run RefiDiff on the discretized Adult and Default datasets from its own suite and compare coverage and the error in the matrix of pairwise association strengths, not just per-entry error.

Proposed Experiments

On the synthetic networks ASIA, ALARM, Insurance, and ECOLI70, we sample complete data at $n \in \{200, 1000, 5000\}$. We then apply completely random, random-given-observed, and non-random masks at 10%, 30%, and 50%, using the protocol of the Markov-blanket paper.

Because the true network is known, we define estimands with known ground truth. These are pairwise log odds ratios between variable pairs grouped by the true edge strength and by graph distance, together with coefficients of a fixed logistic regression of a designated outcome on five covariates. Metrics are bias, coverage of nominal 95% Rubin intervals over 200 replicates, interval width, error in the matrix of pairwise association strengths, imputation accuracy, and runtime. On real data we use LUCAS, the discrete UCI sets Car and Mushroom, and discretized Adult, applying artificial masks to observed cells so that ground truth is retained.

The decisive check is coverage stratified by the true edge strength. We predict that single-graph imputation undercovers sharply on weak true edges at moderate sample sizes, where the learned graph often omits them, and that structure averaging restores coverage to near 95%. We further predict that chained equations hold coverage but lose efficiency and accuracy on the associations as dimension grows. If structure averaging fails to improve weak-edge coverage over single-graph imputation, or if bootstrapped Structural EM matches it at equal cost, the central claim is wrong.