  Missing data imputation (MDI) is crucial when dealing with tabular datasets
across various domains. Autoencoders can be trained to reconstruct missing
values, and graph autoencoders (GAE) can additionally consider similar patterns
in the dataset when imputing new values for a given instance. However,
previously proposed GAEs suffer from scalability issues, requiring the user to
define a similarity metric among patterns to build the graph connectivity
beforehand. In this paper, we leverage recent progress in latent graph
imputation to propose a novel EdGe Generation Graph AutoEncoder (EGG-GAE) for
missing data imputation that overcomes these two drawbacks. EGG-GAE works on
randomly sampled mini-batches of the input data (hence scaling to larger
datasets), and it automatically infers the best connectivity across the
mini-batch for each architecture layer. We also experiment with several
extensions, including an ensemble strategy for inference and the inclusion of
what we call prototype nodes, obtaining significant improvements, both in terms
of imputation error and final downstream accuracy, across multiple benchmarks
and baselines.
