Missingness that spreads along edges: structure-conditioned imputation lifts TADPOLE macro-F1 from 0.75 to 0.82

Handling missing features now depends not only on the global missingness rate but on whether missing entries cluster into connected regions along graph edges. Earlier evaluation protocols removed feature entries independently and uniformly, or dropped complete node feature vectors for independently selected nodes, leaving the mask independent of graph structure. On TADPOLE at matched missingness rates, averaging the macro-F1 curve area of the propagation methods FP, PCFI and FISF gives a lower value under edge-spreading missingness than under uniform random missingness or whole-row random missingness.

PEMix does not diffuse observed values into missing nodes; it first uses a global structural representation of the graph to set each node's mixture-component responsibilities, then updates them with that node's observed coordinates to obtain a conditional distribution over the missing coordinates. Propagation methods treat missing values as quantities to be filled by diffusion along edges, whereas PEMix applies structural information to the missing-feature distribution before message passing. Across TADPOLE, GraphMSO, PEMS-BAY and Engrad, compared by curve area over missingness rates, PEMix reaches the best value on three of the four datasets under edge-spreading missingness and stays competitive under uniform random missingness.

The gain comes from structural conditioning itself, not merely from giving the model access to positional encodings. Handing the same positional encodings to propagation methods, or concatenating them only downstream, does not reproduce PEMix's performance. On TADPOLE, zeroing PEMix's positional encodings while keeping every other setting identical drops the macro-F1 curve area from 0.8243 to 0.7330, with the gap widening as missingness grows.

The report covers graph learning with missing node features: the graph structure itself is fully observed and missingness affects only node features, with evaluation limited to node classification and forecasting. Controlled experiments compare curve areas over missingness rates on TADPOLE, GraphMSO, PEMS-BAY and Engrad, while naturally missing experiments cover AQI, PV-US, METR-LA and relational tasks on RelBench. It suits researchers and engineers working with clustered missing features in sensor, traffic or relational data.

PEMix assumes diagonal mixture covariances and a fully observed graph, and its evaluation is limited to node classification and forecasting. The edge-spreading mechanism is positioned as a controlled stress test rather than a generative model of all real-world missingness, and the naturally missing experiments impose no such mechanism. Broader analyses of structural encodings, temporal modeling and other downstream tasks are left for future work.