Rethinking GNNs and Missing Features: Challenges, Evaluation and a Robust Solution
1University of Trento · 2UiT, The Arctic University of Norway · 3Fondazione Bruno Kessler · 4AIST · 5Aalborg University
Proceedings of the 43rd International Conference on Machine Learning (ICML), Seoul, South Korea · PMLR 306 · 2026
In one sentence. This work replaces overly benign evaluation of GNNs with missing node features with dense-feature datasets and realistic missingness protocols, and proposes GNNmim as a lightweight, broadly robust baseline.
Problem
Graph neural networks deployed in healthcare, sensor networks, recommender systems, and relational data often receive incomplete node attributes. Prior missing-feature and incomplete-graph evaluations mainly delete entries uniformly at random from sparse bag-of-words benchmarks such as Cora, Citeseer, and PubMed. The paper shows theoretically and empirically that feature sparsity can make these benchmarks appear robust until extreme missingness, obscuring differences between methods and overlooking Missing Not At Random (MNAR) processes and train–test shifts.
Main contributions
- An information-theoretic bound connects feature sparsity to the information loss induced by missingness.
- One synthetic and three real-world dense-feature datasets provide more discriminating GNN robustness tests.
- Five protocols cover uniform, structured, and label-dependent MCAR plus feature- and class-dependent MNAR, including distribution shifts.
- GNNmim adapts the Missing Indicator Method to GNN node-level learning and is evaluated on naturally incomplete RelBench databases.
Method
GNNmim zero-fills unobserved entries, concatenates every node’s feature vector with its binary missingness mask, and passes that representation to an otherwise standard GNN. Unlike learned or iterative imputation, this exposes the missingness pattern directly and does not require feature-MAR or label-MAR assumptions. The GNN layer type is selected on validation data.
Experimental setting
- Tasks
- Transductive node classification; inductive analysis; RelBench node classification and regression.
- Datasets
- Cora, Citeseer, PubMed; Synthetic, Air, Electric, TADPOLE; Rel-Event, Rel-Trial, Rel-Arxiv, Rel-F1.
- Metrics
- F1 score, area under the F1–missingness curve, ROC-AUC, and mean absolute error (MAE).
- Baselines
- GNNzero, GNNmedian, GNNmi, GCNmf, GOODIE, GSPN, PCFI, Feature Propagation, FairAC, MICE+GNN, MLP+MIM, XGBoost, and RDL.
Key results
On sparse citation benchmarks, models degrade mainly beyond 85–90% missingness; the dense-feature datasets expose failures much earlier. Across controlled mechanisms and shifts, GNNmim remains competitive. On naturally incomplete RelBench data, adding MIM improves RDL on every dataset with non-negligible missingness, with comparable runtime.
| Dataset / task | Metric | RDLmim | RDL baseline | Difference |
|---|---|---|---|---|
| Rel-Event / user-attendance | MAE ↓ | 0.2553 ± 0.0018 | 0.2628 ± 0.0020 | −0.0075 |
| Rel-Trial / site-success | MAE ↓ | 0.3746 ± 0.0170 | 0.4235 ± 0.0096 | −0.0489 |
| Rel-F1 / driver-top3 | ROC-AUC ↑ | 0.768 ± 0.004 | 0.755 ± 0.006 | +0.013 |
When this work is relevant
This paper is relevant when selecting methods for GNNs with incomplete node attributes, designing MCAR or MNAR robustness benchmarks, studying missingness distribution shift, or handling naturally missing clinical, environmental-sensor, electrical-grid, and relational-database features.
Limitations
The study covers node-level classification and regression with missing node features. It does not evaluate link prediction or graph classification, and assumes the graph structure and training labels are observed; missing edges, uncertain topology, and missing labels remain outside its scope. The authors also identify the need for larger benchmarks designed specifically for missing features.
Citation
Persistent identifiers: arXiv:2601.04855 · https://doi.org/10.48550/arXiv.2601.04855