# When Missingness Follows the Graph: Beyond Feature Propagation for Missing Features

arXiv: https://arxiv.org/abs/2610.18113 · HTML: https://mlsanity.com/paper/2610.18113/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 15 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 10 of 10)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [RelBench: A Benchmark for Deep Learning on Relational Databases](https://mlsanity.com/paper/2407.20060/) (2024)
- [On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features](https://mlsanity.com/paper/2111.12128/) (2021)
- [Graph Convolutional Networks for Graphs Containing Missing Features](https://mlsanity.com/paper/2007.04583/) (2020)
- [Graph-based Forecasting with Missing Data through Spatiotemporal Downsampling](https://mlsanity.com/paper/2402.10634/) (2024)
- [Confidence-Based Feature Imputation for Graphs with Partially Known Features](https://mlsanity.com/paper/2305.16618/) (2023)
- [Multi-hop Convolutions on Weighted Graphs](https://mlsanity.com/paper/1911.04978/) (2019)
- [Rethinking GNNs and Missing Features: Challenges, Evaluation and a Robust Solution](https://mlsanity.com/paper/2601.04855/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) commonly assume that node features are fully observed, despite missing features being pervasive in real-world applications. By leveraging the dependence between node features and graph structure, existing graph-specific methods handle missingness by propagating observed feature values along graph edges. However, these methods have mainly been evaluated in overly optimistic settings, where feature entries are removed independently and uniformly across the graph. This overlooks realistic scenarios in which missingness propagates among connected nodes, as can occur during localized sensing failures in sensor networks. We formalize this complementary notion as graph-structured mask dependence, where the joint distribution of missingness indicators is shaped by the graph, and introduce a controlled mechanism that instantiates this setting. We study propagation-based methods theoretically and empirically in this setting, showing that their effectiveness changes substantially compared with the uniformly random regime. Motivated by this limitation, we propose PEMix, designed to remain effective under challenging graph-structured missingness. Rather than propagating observed values, PEMix uses global structural representations to condition a probabilistic model of incomplete node features before message passing. Experiments under controlled graph-structured missingness and naturally occurring missingness show that PEMix remains robust across complex missingness regimes, with particularly strong performance as missingness becomes severe.