SCORE-EM: Ordering-Based Causal Discovery with Missing-at-Random Data

Causal discovery from observational data is fundamental to machine learning and statistics, yet its application to real-world datasets is often complicated by the prevalence of missing values. Among ordering-based approaches, SCORE (Rolland et al., 2022) estimates a topological ordering using score-function identities under an additive-noise model, but cannot be directly applied to incomplete data. We introduce SCORE-EM, an EM-inspired framework for causal discovery under missing-at-random (MAR) mechanisms that jointly refines missing-value estimates and causal structure ordering. In the conditional-sampling step, missing entries are updated using Metropolis-adjusted Langevin algorithm (MALA) transitions targeting the conditional distribution induced by the current additive-noise model. In the structural-refinement step, the model is refitted and the causal ordering is updated using SCORE statistics aggregated across the resulting ensemble of completed datasets. Unlike structure-agnostic imputation, this procedure uses the evolving structural model to guide missing-value estimation, while the refined imputations provide increasingly informative data for structure learning. A subsequent multiple-imputation CAM pruning stage accounts for imputation uncertainty during edge selection. Empirical results on synthetic and real world data demonstrate that SCORE-EM improves causal ordering and graph recovery over competing missing-data baselines.