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

Enrico Chialà; Francesco Ferrini; Antonio Longa; Bruno Lepri; Filippo Maria Bianchi; Manfred Jaeger; Veronica Lachi

cs.LGOct 13, 2026

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

Authors: Enrico Chialà, Francesco Ferrini, Antonio Longa, Bruno Lepri, Filippo Maria Bianchi, Manfred Jaeger, Veronica Lachi

Organizations: University of Trento · Fondazione Bruno Kessler · UiT, The Arctic University of Norway · Aalborg University

Abstract

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.

Figures & tables

Figure 1: Conceptual comparison of missingness mechanisms. Left (U-MCAR): Feature entries are dropped independently and uniformly across the graph. Middle (S-MCAR): Entire feature vectors are missing for randomly sampled nodes, independent of connectivity. Right (Recursive Transmission, RT): Missingness originates at a shared seed node and expands recursively along graph edges, forming spatially correlated missing regions that challenge propagation-based recovery.

Figure 2: TADPOLE macro-F1 under RT, U-MCAR, and S-MCAR for FP, PCFI, and FISF. Curves show the mean and shaded bands indicate one standard deviation over five seeds. Complete macro-F1 and AUROC results are reported in Appendix C .

	RT				U-MCAR
Model	TADPOLE	GraphMSO	PEMS-BAY	Engrad	TADPOLE	GraphMSO	PEMS-BAY	Engrad
	Macro-F1 $\uparrow$	MAE $\downarrow$	MAE $\downarrow$	MAE $\downarrow$	Macro-F1 $\uparrow$	MAE $\downarrow$	MAE $\downarrow$	MAE $\downarrow$
GNN-Zero	0.7388	1.369627	4.294239	7.345723	0.7565	1.368397	4.059947	5.796827
GNN-Median	0.7015	1.369711	4.340867	7.317703	0.7398	1.368436	4.038923	5.859984
GNN-MI	0.7130	1.369657	4.251831	7.322302	0.7421	1.368595	4.079495	5.816402
FP	0.7254	1.371720	4.203665	6.515184	0.7473	1.370337	4.035542	5.504311

Table 1: Performance under controlled RT and U-MCAR, reported as trapezoidal AUC over

\mu

. Blue indicates the best model in each column, orange the second one, and green the third one. Full tables in Appendix D .

Model	AQI	PV-US	METR-LA
GNN-Zero	$20.1895\pm 0.2203$	$12.4871\pm 0.0151$	$6.5199\pm 0.0465$
GNN-Median	$19.7317\pm 0.2595$	$12.3410\pm 0.0289$	$6.6117\pm 0.0760$
GNN-MI	$19.9730\pm 0.1712$	$12.4844\pm 0.0337$	$6.5197\pm 0.0576$
FP	$18.9450\pm 0.0409$	$12.5251\pm 0.0290$	$6.5945\pm 0.0487$
PCFI	$19.5384\pm 0.0707$	$12.9281\pm 0.0698$	$6.6484\pm 0.0957$
FISF	$19.0586\pm 0.0778$	$12.5746\pm 0.0203$	$6.5991\pm 0.0721$

Table 2: Performance with naturally occurring missingness (test MAE, mean

\pm

std over five seeds; lower is better). Blue, orange, and green mark the three best models within each dataset.

Node regression
Dataset	Task	Metric	RDL	RDL-MIM	RDL-PEMix
rel-trial	study-adverse	MAE $\downarrow$	$44.470\pm 0.210$	$43.115\pm 0.155$	$\mathbf{42.840\pm 0.680}$
rel-trial	site-success	MAE $\downarrow$	$0.400\pm 0.020$	$\mathbf{0.375\pm 0.017}$	$0.391\pm 0.008$
rel-f1	driver-position	MAE $\downarrow$	$\mathbf{4.022\pm 0.120}$	$4.0271\pm 0.0389$	$4.208\pm 0.090$
Node classification
rel-trial	study-outcome	AUC $\uparrow$	$0.686\pm 0.010$	$0.6794\pm 0.0051$	$\mathbf{0.706\pm 0.010}$

Table 3: RelBench results with naturally occurring missingness (mean

\pm

std over three seeds; ten epochs). RDL-PEMix denotes the relational adaptation of PEMix, while RDL-MIM is the missing-indicator adaptation of RDL. Bold marks the best mean within each task.

PE	Model	TADPOLE	PV-US
usage		Macro-F1 AUC $\uparrow$	MAE $\downarrow$
Mechanism	PEMix	0.8243	$\mathbf{12.0225\pm 0.0392}$
	FP + PE	0.7336	$12.4642\pm 0.0221$
	PCFI + PE	0.7474	$12.8643\pm 0.0454$
	FISF + PE	0.7573	$12.5981\pm 0.0443$
Downstream	GCNmf + PE	0.7211	$12.1421\pm 0.0145$

Table 4: Effect of PE on TADPOLE and PV-US. "Mechanism" denotes methods in which PE are used while handling missing features, whereas "Downstream" denotes variants where PE are concatenated only after missing-feature handling. We report macro-F1 AUC across missingness rates for TADPOLE (higher is better) and test MAE under natural missingness for PV-US (lower is better). PV-US results are means

\pm

std over five seeds.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Regime	Dataset	Domain	Source	Missing (%)
Controlled	TADPOLE	clinical	Zhu et al. (2019)	–
	GraphMSO	graph forecasting	Marisca et al. (2024)	–
	PEMS-BAY	traffic forecasting	Marisca et al. (2024)	–
	Engrad	forecasting	Marisca et al. (2024)	–
Native	AQI	air-quality forecasting	Marisca et al. (2024)	25.67
	PV-US	photovoltaic forecasting	Marisca et al. (2024)	54.02

Appendix

Table 5: Datasets used in the controlled and native-missingness experiments. Controlled datasets are originally complete and missingness is injected artificially. Native datasets contain missing values in the original data. For native datasets, we report the percentage of missing entries in the original data.

Dataset	All timestamps	Partial timestamps	Permutation null ( $95\%$ )
AQI	1.15	1.16	$[0.902,\,1.118]$
PV-US	1.03	1.21	$[0.999,\,1.001]$
METR-LA	1.04	4.03	$[0.997,\,1.003]$

Appendix

Table 6: Co-missingness ratio

HC_{\mathrm{miss}}

on datasets with naturally occurring missingness. Values above

1

indicate that neighboring nodes are missing together more often than under spatially independent missingness. The permutation null is the central

95\%

range over 999 node permutations, computed over all timestamps.

	Macro-F1			AUROC
$\mu$ (%)	RT	U-MCAR	S-MCAR	RT	U-MCAR	S-MCAR
0	$0.806\pm 0.065$	$0.806\pm 0.065$	$0.806\pm 0.065$	$0.929\pm 0.022$	$0.929\pm 0.022$	$0.929\pm 0.022$
10	$0.805\pm 0.022$	$0.836\pm 0.038$	$0.842\pm 0.028$	$0.932\pm 0.013$	$0.939\pm 0.016$	$0.939\pm 0.019$
20	$0.813\pm 0.035$	$0.808\pm 0.044$	$0.797\pm 0.038$	$0.941\pm 0.010$	$0.934\pm 0.021$	$0.932\pm 0.014$
30	$0.797\pm 0.034$	$0.798\pm 0.037$	$0.806\pm 0.065$	$0.935\pm 0.015$	$0.928\pm 0.016$	$0.924\pm 0.031$
40	$0.802\pm 0.054$	$0.784\pm 0.026$	$0.726\pm 0.086$	$0.926\pm 0.019$	$0.924\pm 0.013$	$0.897\pm 0.022$

Appendix

Table 7: Complete FP results on TADPOLE (five seeds). Higher macro-F1 and AUROC are better.

	Macro-F1			AUROC
$\mu$ (%)	RT	U-MCAR	S-MCAR	RT	U-MCAR	S-MCAR
0	$0.796\pm 0.054$	$0.796\pm 0.054$	$0.796\pm 0.054$	$0.927\pm 0.016$	$0.927\pm 0.016$	$0.927\pm 0.016$
10	$0.795\pm 0.020$	$0.810\pm 0.046$	$0.818\pm 0.038$	$0.928\pm 0.008$	$0.936\pm 0.023$	$0.938\pm 0.015$
20	$0.825\pm 0.032$	$0.811\pm 0.038$	$0.833\pm 0.021$	$0.940\pm 0.018$	$0.938\pm 0.020$	$0.940\pm 0.013$
30	$0.810\pm 0.019$	$0.813\pm 0.043$	$0.797\pm 0.036$	$0.938\pm 0.017$	$0.934\pm 0.021$	$0.928\pm 0.022$
40	$0.805\pm 0.047$	$0.804\pm 0.028$	$0.822\pm 0.047$	$0.929\pm 0.016$	$0.933\pm 0.011$	$0.929\pm 0.016$

Appendix

Table 8: Complete PCFI results on TADPOLE (five seeds). Higher macro-F1 and AUROC are better.

	Macro-F1			AUROC
$\mu$ (%)	RT	U-MCAR	S-MCAR	RT	U-MCAR	S-MCAR
0	$0.806\pm 0.040$	$0.806\pm 0.040$	$0.806\pm 0.040$	$0.930\pm 0.016$	$0.930\pm 0.016$	$0.930\pm 0.016$
10	$0.802\pm 0.013$	$0.825\pm 0.058$	$0.833\pm 0.021$	$0.932\pm 0.015$	$0.939\pm 0.019$	$0.940\pm 0.014$
20	$0.809\pm 0.041$	$0.811\pm 0.036$	$0.805\pm 0.042$	$0.940\pm 0.009$	$0.932\pm 0.017$	$0.934\pm 0.012$
30	$0.784\pm 0.055$	$0.795\pm 0.045$	$0.812\pm 0.069$	$0.930\pm 0.018$	$0.930\pm 0.016$	$0.924\pm 0.028$
40	$0.808\pm 0.049$	$0.790\pm 0.045$	$0.828\pm 0.032$	$0.932\pm 0.013$	$0.933\pm 0.014$	$0.928\pm 0.010$

Appendix

Table 9: Complete FISF results on TADPOLE (five seeds). Higher macro-F1 and AUROC are better.

Mechanism	Method	Hidden	Dropout	LR	Max epochs	Patience
RT	GNN-Zero	128	0.5	0.01	500	50
RT	GNN-Median	128	0.5	0.01	500	50
RT	GNN-MI	128	0.5	0.01	500	50
RT	GNN-MIM	128	0.5	0.01	500	50
RT	FP	64	0.5	0.01	1000	40
RT	PCFI	64	0.5	0.01	1000	40

Appendix

Table 26: Hyperparameter configurations selected for TADPOLE. Hyperparameters are selected separately for RT and U-MCAR using validation performance, and the selected configuration is then kept fixed across all missingness rates within each mechanism.

Mechanism	Method	Hidden	Dropout	LR	Max epochs	Patience
RT	GNN-Zero	128	0.5	0.001	500	50
RT	GNN-Median	128	0.3	0.001	500	50
RT	GNN-MI	128	0.5	0.001	500	50
RT	GNN-MIM	128	0.3	0.001	500	50
RT	FP	64	0.3	0.001	1000	40
RT	PCFI	64	0.5	0.001	1000	40

Appendix

Table 27: Hyperparameter configurations selected for EngRAD. Hyperparameters are selected separately for RT and U-MCAR using validation performance, and the selected configuration is then kept fixed across all missingness rates within each mechanism.

Mechanism	Method	Hidden	Dropout	LR	Max epochs	Patience
RT	GNN-Zero	128	0.5	0.003	500	50
RT	GNN-Median	128	0.5	0.01	500	50
RT	GNN-MI	128	0.5	0.003	500	50
RT	GNN-MIM	128	0.1	0.003	500	50
RT	FP	64	0.5	0.01	1000	40
RT	PCFI	64	0.5	0.01	1000	40

Appendix

Table 28: Hyperparameter configurations selected for GraphMSO. Hyperparameters are selected separately for RT and U-MCAR using validation performance, and the selected configuration is then kept fixed across all missingness rates within each mechanism.

Mechanism	Method	Hidden	Dropout	LR	Max epochs	Patience
RT	GNN-Zero	128	0	0.001	500	50
RT	GNN-Median	128	0	0.003	500	50
RT	GNN-MI	128	0.3	0.001	500	50
RT	GNN-MIM	128	0	0.001	500	50
RT	FP	64	0.3	0.003	1000	40
RT	PCFI	64	0.1	0.003	1000	40

Appendix

Table 29: Hyperparameter configurations selected for PEMS-BAY. Hyperparameters are selected separately for RT and U-MCAR using validation performance, and the selected configuration is then kept fixed across all missingness rates within each mechanism.

Method	Hidden	Dropout	LR	Max epochs	Patience
GNN-Zero	128	0.1	0.01	500	50
GNN-Median	128	0.3	0.01	500	50
GNN-MI	128	0.5	0.01	500	50
GNN-MIM	128	0.5	0.01	500	50
FP	64	0.3	0.001	1000	40
PCFI	64	0.5	0.003	1000	40

Appendix

Table 30: Hyperparameter configurations selected for AQI under natural missingness. Configurations are selected using validation MAE; no additional missingness is injected. GMM settings are reported separately.

Method	Hidden	Dropout	LR	Max epochs	Patience
GNN-Zero	128	0.5	0.003	500	50
GNN-Median	128	0	0.003	500	50
GNN-MI	128	0.3	0.003	500	50
GNN-MIM	128	0.5	0.001	500	50
FP	64	0.3	0.003	1000	40
PCFI	64	0.5	0.003	1000	40

Appendix

Table 31: Hyperparameter configurations selected for PV-US under natural missingness. Configurations are selected using validation MAE; no additional missingness is injected. GMM settings are reported separately.

Method	Hidden	Dropout	LR	Max epochs	Patience
GNN-Zero	128	0	0.001	500	50
GNN-Median	128	0.1	0.001	500	50
GNN-MI	128	0	0.001	500	50
GNN-MIM	128	0.3	0.003	500	50
FP	64	0	0.003	1000	40
PCFI	64	0	0.003	1000	40

Appendix

Table 32: Hyperparameter configurations selected for METR-LA under natural missingness. Configurations are selected using validation MAE; no additional missingness is injected. GMM settings are reported separately.

Mechanism	Method	$K$	$q$	Likelihood
RT	GCNmf	5	0	legacy
RT	PEMix	8	16	gaussian
U-MCAR	GCNmf	5	0	legacy
U-MCAR	PEMix	5	8	gaussian

Appendix

Table 33: GMM settings selected for EngRAD.

K

is the number of mixture components and

q

is the PE dimension; GCNmf does not use PE (

q=0

Mechanism	Method	$K$	$q$	Likelihood
RT	GCNmf	5	0	legacy
RT	PEMix	3	16	gaussian
U-MCAR	GCNmf	5	0	gaussian
U-MCAR	PEMix	2	8	gaussian

Appendix

Table 34: GMM settings selected for GraphMSO.

K

is the number of mixture components and

q

is the PE dimension; GCNmf does not use PE (

q=0

Mechanism	Method	$K$	$q$	Likelihood
RT	GCNmf	5	0	legacy
RT	PEMix	5	16	gaussian
U-MCAR	GCNmf	5	0	legacy
U-MCAR	PEMix	5	8	gaussian

Appendix

Table 35: GMM settings selected for PEMS-BAY.

K

is the number of mixture components and

q

is the PE dimension; GCNmf does not use PE (

q=0

Method	$K$	$q$	Likelihood
GCNmf	5	0	legacy
PEMix	5	8	gaussian

Appendix

Table 36: GMM settings selected for AQI.

K

is the number of mixture components and

q

is the PE dimension; GCNmf does not use PE (

q=0

Method	$K$	$q$	Likelihood
GCNmf	5	0	gaussian
PEMix	3	4	gaussian

Appendix

Table 37: GMM settings selected for PV-US.

K

is the number of mixture components and

q

is the PE dimension; GCNmf does not use PE (

q=0

Method	$K$	$q$	Likelihood
GCNmf	5	0	gaussian
PEMix	5	16	gaussian

Appendix

Table 38: GMM settings selected for METR-LA.

K

is the number of mixture components and

q

is the PE dimension; GCNmf does not use PE (

q=0

Method	Mask-dependent one-off	Per epoch	Extra memory
GNN-Zero / Mean	$O(nd)$	$\mathcal{C}_{\mathrm{B}}(d)$	–
GNN-Median	$O(nd)^{\dagger}$	$\mathcal{C}_{\mathrm{B}}(d)$	–
GNN-MIM	$O(nd)$	$\mathcal{C}_{\mathrm{B}}(d)+O(ndh)$	$O(nd)$
FP	$O(T_{\mathrm{FP}}\,dm)$	$\mathcal{C}_{\mathrm{B}}(d)$	$O(nd)$
PCFI	$O(T_{\mathrm{PC}}\,dm+nd^{2})^{\ddagger}$	$\mathcal{C}_{\mathrm{B}}(d)$	$O(dm+d^{2})^{\ddagger}$
FISF	$O((T_{1}+\rho T_{2})\,dm)^{\ddagger}$	$\mathcal{C}_{\mathrm{B}}(d)$	$O(dm)^{\ddagger}$

Appendix

Table 39: Computational cost per input graph. Mask-dependent costs are recomputed for every missingness pattern.

\dagger

O(nd\log n)

with sorting.

\ddagger

: implementation-dependent (see text).

Figure 3: Matched ablation between PEMix and the same probabilistic recovery model without PE conditioning, obtained by setting the positional encodings to zero. The models share masks, splits, optimization settings, and the probabilistic first layer; at $\mu=0$ they coincide exactly. Mean $\pm$ standard deviation over five seeds.

Missing rate	Joint GMM	Frozen GMM
$20\%$	$\mathbf{6.1751\pm 0.0635}$	$6.287\pm 0.086$
$50\%$	$\mathbf{7.1536\pm 0.0951}$	$7.364\pm 0.113$
$80\%$	$\mathbf{8.3722\pm 0.0844}$	$8.523\pm 0.080$

Appendix

Table 40: Effect of jointly optimising the GMM on EngRAD under RT . Values are mean

\pm

standard deviation over five seeds. Lower is better.

Explore similar work

Pattern-Aware Graph Neural Networks for Handling Missing Data
Jul 9, 2026Minett Tran, Taehee JeongGraph Neural Networks Learning with Missing Data
San Jose State University
Robust Graph Clustering Network for Multiple Missing Data
Sep 25, 2026Keyuan Qiu, Renda Han, Zhen Tang +6Graph Clustering Incomplete Data Imputation
Northeastern University · University of Chinese Academy of Sciences · Northeast Normal University +2
Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks
Jun 2, 2026Anubha Goel, Juho KanniainenGraph Structure Learning Graph Neural Networks
Computing Science/Financial Computing and Data Analytics Group, Tampere University, Tampere, 33720, Finland

Jul 9, 2026J/K move · Enter open · S save

Pattern-Aware Graph Neural Networks for Handling Missing Data

Minett Tran, Taehee Jeong

San Jose State University

Graph Neural Networks Learning with Missing Data Tabular Classification

Open paper AskPDF arXiv

Missing data is ubiquitous in real-world datasets. Traditional methods either discard incomplete samples or apply imputation techniques that ignore potentially informative missingness patterns, implicitly assuming that missingness occurs randomly. However, missingness patterns might provide additional information. We propose pattern-aware graph neural networks that explicitly encode which features are missing alongside observed values. We used four encoding strategies -- learned embeddings, frozen random embeddings, statistical features, and hierarchical representations -- across seven UCI datasets with naturally occurring missingness. Our Pattern-aware methods achieve substantial improvements over baselines, with an average improvement of 17% in balanced accuracy and 22% in F1-macro across all datasets. The benefits vary significantly by dataset: annealing shows dramatic improvement (+80% balanced accuracy), while hepatitis and soybean show minimal gains (+4--5%). Notably, even simple random pattern embeddings perform comparably to learned embeddings (0.650 vs 0.663 balanced accuracy), suggesting that distinguishing between patterns may be more important than task-specific optimization. Our ablation study reveals that attention mechanisms, while helpful, are not critical when pattern information is available -- simple mean aggregation with pattern awareness achieves 0.640 balanced accuracy compared to 0.645 for attention-based variants.

Abstract

Explore similar work

Pattern-Aware Graph Neural Networks for Handling Missing Data

Robust Graph Clustering Network for Multiple Missing Data

Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks