MEDUSA: Graph-Conditioned Flow Matching for Missing Modalities in EHRs

Electronic health records (EHRs) are inherently multimodal, yet complete records are often unavailable because entire modalities may be missing. Existing approaches either reconstruct missing information or adapt prediction models to incomplete inputs, while graph based methods exploit relationships among patients but typically rely on deterministic message passing. We introduce MEDUSA, a graph conditioned generative framework that combines patient similarity with flow matching to impute missing modality representations. MEDUSA constructs a patient graph from observed modalities and learns a separate flow model for each maskable modality, allowing information from related patients to guide generation. Training follows an expectation maximization (EM) inspired alternating procedure that fits the generative models and jointly optimizes downstream prediction. Across multiple EHR prediction tasks, MEDUSA achieves strong predictive performance, particularly at higher missingness. Its imputations also better preserve the patient similarity structure of fully observed data than competing methods. These results show that combining relational structure with generative imputation is effective for learning from incomplete multimodal EHRs.