Rethinking GNNs and Missing Features: Challenges, Evaluation and a Robust Solution

Handling missing node features is a key challenge for deploying Graph Neural Networks (GNNs) in real-world domains such as healthcare and sensor networks. Existing studies mostly address relatively benign scenarios, namely benchmark datasets with (a) high-dimensional but sparse node features and (b) incomplete data generated under Missing Completely At Random (MCAR) mechanisms. For (a), we theoretically prove that high sparsity substantially limits the information loss caused by missingness, making all models appear robust and preventing a meaningful comparison of their performance. To overcome this limitation, we introduce one synthetic and three real-world datasets with dense, semantically meaningful features. For (b), we move beyond MCAR and design evaluation protocols with more realistic missingness mechanisms. Moreover, we provide a theoretical background to state explicit assumptions on the missingness process and analyze their implications for different methods. Building on this analysis, we show that a simple baseline adapted to the graph domain is competitive with respect to specialized architectures across diverse datasets and missingness regimes.

Many real-world applications, from hospitals to sensor networks, use AI that learns from connected data, such as networks of patients or devices. But measurements often go missing, and dozens of methods have been proposed to handle this. Existing evaluations suggest they all work equally well. We show that this apparent success is an illusion. The standard test datasets already have most values missing by design, so adding more missingness barely changes anything, a fact we also prove mathematically. We then introduce new datasets with dense, meaningful measurements (air quality, electrical grids, Alzheimer's patients) and realistic patterns of missing data, such as patients hiding sensitive information. Under these harder conditions, many state-of-the-art methods fail. We propose a remarkably simple fix: tell the AI which values are missing by attaching a "missing-or-not" tag to each one. This lightweight approach matches or beats much more complex methods across realistic scenarios, including large real-world databases, and calls for more honest evaluation of AI in critical settings like healthcare.