Beyond Correlation and Shared Spaces: Conditional and Adaptive Graph Imputation

A column-centric graph provides a natural representation for tabular imputation because its topology can be shared across rows, allowing the same structural information to support both in-sample and out-of-sample imputation. However, such graph-based formulations face two fundamental challenges: pairwise associations may not reflect direct conditional dependencies, and shared message transformations may overlook the heterogeneous representation spaces of different columns.This paper proposes CAGI (Conditional and Adaptive Graph Imputation) to address these challenges. CAGI constructs a conditional dependency graph by estimating latent correlations with a rank-based estimator and deriving a sparse graph from the resulting partial correlations, and performs column-adaptive graph diffusion through layer-wise source and target transformations. A theoretical analysis establishes when conditional neighborhoods provide sufficient information for reconstruction and when graph diffusion can preserve the information required by the Bayes-optimal imputation function. An excess-risk decomposition further characterizes the effects of information loss in diffusion and approximation error. Experiments on tabular imputation tasks demonstrate the effectiveness of CAGI.