Feature Imputation via Relational Graph Propagation

274 concepts178 papers1 proposal

When dealing with incomplete datasets, traditional machine learning approaches typically treat each data point as an isolated entity. Standard imputation methods—such as mean substitution, matrix factorization, or generative autoencoders—look inward, attempting to reconstruct missing values solely from the remaining observed features of that specific sample or via global dataset statistics.

However, real-world data rarely exists in a vacuum. Entities share intrinsic relationships, whether they are users in a social network, genes in a biological pathway, or tabular records with shared statistical profiles.

Graph-based feature imputation shifts the paradigm from individual reconstruction to relational recovery. By representing data points as nodes in a connected network, missing features can be treated as an unobserved, continuous signal distributed across a graph. Instead of guessing a missing value in isolation, models can "borrow" information from topological neighbors. This approach works because it leverages homophily—the principle that connected or structurally similar nodes share similar characteristics.


From Tables to Topology: Constructing the Graph

To impute features using a graph, we first need a graph. In domains like social networks or citation webs, the topology is inherent. But for tabular, multi-view, or multi-modal data, the network structure must be inferred.

A common strategy is to construct a $k$-nearest neighbor ($k$-NN) graph based on feature similarity. As shown by Daeho Um et al. in Propagate and Inject: Revisiting Propagation-Based Feature Imputation for Graphs with Partially Observed Features, transforming standard tabular datasets into $k$-NN graphs allows relational propagation mechanisms to outperform specialized tabular imputation models. Similarly, Zihao Li et al. demonstrate in Multi-view GCN for loan default risk prediction that treating financial applications as nodes in a similarity graph allows models to overcome severe data sparsity by aggregating information from similar borrowers.

Isolated Tabular Rows               Similarity Graph Construction
   [X, ?, Z]  [X, Y, ?]                  [Node A: X, ?, Z]
                                               /       \
   [?, Y, Z]  [X, Y, Z]          [Node B: ?, Y, Z] --- [Node C: X, Y, Z]

In multi-view scenarios—where samples are captured across different modalities (e.g., text and images) and entire views might be missing—the graph structure acts as a bridge. Models can transfer the well-defined adjacency structure of a complete view to guide the feature reconstruction of an incomplete view. Guoqing Chao et al. leverage this in Incomplete Contrastive Multi-View Clustering with High-Confidence Guiding, using a graph convolutional network (GCN) to propagate features across transferred relationships.

Rather than reconstructing high-dimensional raw features directly, single author Shuping Zhao demonstrates in High-Confident Local Structure Guided Consensus Graph Learning For Incomplete Multi-view Clustering that completing the underlying affinity or relationship graph directly from shared cross-view information provides a more stable and effective proxy for downstream tasks than raw feature synthesis.


The Propagation Mechanism: How Information Flows

Once the graph structure is established, the missing values are filled through a process of message passing or diffusion.

Graph Convolutional Networks (GCNs) serve as the primary engine for this propagation. In a standard graph convolution, a node's representation is updated by aggregating the feature vectors of its immediate neighbors. As Le Wu et al. explain in Joint Item Recommendation and Attribute Inference: An Adaptive Graph Convolutional Network Approach, this operation acts as a spatial smoothing filter. The network propagates strong signals from feature-rich neighborhoods into feature-deficient nodes, effectively smoothing out the gaps caused by missing metadata.

To ensure that this smoothing process yields realistic and mathematically consistent features, frameworks often introduce global constraints. For instance, Chengxiang Lei et al. in Self-supervised Guided Hypergraph Feature Propagation for Semi-supervised Classification with Missing Node Features enforce the minimization of Dirichlet energy across the graph.

Minimizing Dirichlet energy mathematically prevents abrupt, noisy jumps in feature values between connected nodes. It forces the imputed attributes to vary smoothly across the topology, preserving the local geometric consistency of the data space even when up to 99% of the initial attributes are missing.


The Masking Trick: Forcing Neighborhood Reliance

A naive neural network trained to reconstruct features might simply learn an identity mapping—copying the observed features of a node and failing to learn how to utilize the surrounding graph structure. To prevent this, graph imputation models employ a critical architectural constraint: target masking.

Input Node (Target Masked)               Neighbor Nodes (Observed)
     [ ?,  ?,  ? ] <=================== [ X=1.2, Y=0.5, Z=9.1 ]
                           Message      [ X=1.1, Y=0.6, Z=8.9 ]
                          Passing       [ X=1.3, Y=0.4, Z=9.0 ]
                             ||
                             \/
               Imputed Output: [ X=1.2, Y=0.5, Z=9.0 ]

As implemented by Andrea Cini et al. in Filling the G_ap_s: Multivariate Time Series Imputation by Graph Neural Networks, the target node’s own features are explicitly masked out during the aggregation phase. By denying the model access to the node's existing features, the network is forced to rely entirely on the neighborhood topology to synthesize the missing values.

Indro Spinelli et al. utilize a similar constraint in Missing data imputation with adversarially-trained graph convolutional networks. By combining this neighborhood-aware architectural constraint with an adversarial loss (WGAN-GP), the generator learns to produce imputed values that are indistinguishable from real distributions, purely by interpolating context from adjacent nodes.


Beyond Simple Graphs: Multi-Relational and Cross-Channel Imputation

The power of relational imputation extends beyond simple, homogeneous graphs. Recent variations adapt this mechanism to handle complex data structures like knowledge graphs, multi-modal systems, and irregular time series.

Multi-Relational Offsets

In a knowledge graph, edges have different meanings (e.g., "born_in" vs. "employed_by"). Imputing numerical attributes requires accounting for these specific semantics. In Node Attribute Completion in Knowledge Graphs with Multi-Relational Propagation, Alberto García-Durán et al. introduce relation-specific offsets. Instead of directly copying a neighbor's value, the model treats edges as mathematical functions that transform attributes across different entity types, allowing for precise numerical estimation based on the link type.

Cross-Channel Time Series Recovery

In multivariate time series, sensors often experience asynchronous dropouts. Single author Zhangyi Hu demonstrates in IMTS is Worth Time $\times$ Channel Patches: Visual Masked Autoencoders for Irregular Multivariate Time Series Prediction that cross-channel dependencies can be modeled as a latent graph. When one sensor goes offline, graph-based message passing across correlated channels supplements the missing temporal windows, capturing inter-sensor dynamics to recover the lost signal.

Biological Denoising

In single-cell genomics, technical limitations often cause "dropouts" where gene expressions falsely read as zero. Tianxiang Liu et al. in scDFN: Enhancing single-cell RNA-seq Clustering with Deep Fusion Networks and Yuansong Zeng et al. in Imputing spatial transcriptomics through gene network constructed from protein language model demonstrate that mapping cells or genes to functional biological networks allows models to denoise sparse measurements. Propagating signals across these networks effectively reconstructs true expression levels by leveraging known functional relationships.

Summary

Graph-based feature imputation works because it reframes data recovery as a collective, topological problem rather than an isolated, row-by-row estimation. By structuring data as networks, applying message passing with smoothness constraints, and utilizing target masking, these models turn relational context into a powerful mathematical engine for data reconstruction.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 175 papers
  2. Version 1 · 2026-10-04 · 289 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_feature_imputation_1ac38400,
  title = {graph-based feature imputation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-feature-imputation/rdr_1ac38400fb6a4dd68d1aee6fd8f6acb6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_graph_based_feature_imputation_1ac38400_v2,
  title = {graph-based feature imputation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-feature-imputation/rdr_1ac38400fb6a4dd68d1aee6fd8f6acb6/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake