PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.18113v1cs.LGcs.AI

TL;DR

GNNs commonly assume fully observed node features, while standard missingness evaluations often overlook failures correlated across connected nodes. The paper formalizes graph-structured mask dependence, introduces a controlled mechanism, and proposes PEMix, which conditions a probabilistic feature model on global structure. PEMix remains robust across controlled and naturally occurring missingness, with particularly strong performance as missingness becomes severe.

  • Problem

    GNNs commonly assume fully observed features, while standard missingness protocols do not capture topology-shaped dependence that can leave propagation methods with too little observed information.

    Source: §1 · pp. 1–2, §3 · p. 4

  • Method

    The paper introduces Recursive Transmission as a controlled graph-structured missingness mechanism and PEMix, which conditions a probabilistic feature model on global structural representations before message passing.

    Source: §1 · p. 2, §3 · p. 4

  • Results

    PEMix improves robustness over propagation baselines across controlled graph-structured and real-world missingness, with particularly strong gains as severity increases.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results identify graph structure as a useful source of information for modeling incomplete node features, not only for prediction.

    Source: §6 · p. 10

    PEMix assumes diagonal mixture covariances and a fully observed graph, and evaluation is limited to node classification and forecasting.

    Source: §6 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

PEMix is proposed for graph-structured missingness, where connected nodes can lose features together and leave propagation-based methods with too little observed information. The paper introduces a controlled mechanism for this setting and reports improved robustness across controlled and real-world missingness, especially as severity increases.

1 INTRODUCTION

  • Existing graph-specific methods use topology to recover missing features, commonly by propagating observed values while minimizing Dirichlet energy.PCFI and FISF extend this principle with confidence-based and iterative propagation schemes.Source: §1 · p. 1
  • Common evaluations remove feature entries independently and uniformly, leaving unexplored how graph topology shapes missingness.Localized failures can make missingness indicators correlated across adjacent nodes, so equal global rates can produce different recovery difficulty.Source: §1 · pp. 1–2
  • The paper formalizes graph-structured mask dependence and introduces Recursive Transmission (RT), a controlled mechanism for it.RT models missingness that originates at a shared seed node and expands along graph edges.Source: §1 · p. 2, Figure 1 · p. 2
  • Graph-localized missingness creates a boundary bottleneck for standard propagation and challenges more sophisticated propagation methods.When missing-feature nodes cluster, too little observed information remains to propagate.Source: §1 · p. 2
  • PEMix improves robustness over propagation baselines across controlled graph-structured and real-world missingness, with particularly strong gains as severity increases.The method conditions a probabilistic feature model on global structural representations before message passing, without propagating observed values.Source: §1 · p. 2

2 LEARNING WITH MISSING NODE FEATURES

This section sets up prediction with incomplete node features and contrasts approaches that do and do not use graph topology during recovery. It distinguishes dependence of the missingness mask on data from dependence among mask entries, which standard MCAR/MAR/MNAR labels do not describe.

2 LEARNING WITH MISSING NODE FEATURES

  • In this formulation, the graph adjacency is fully observed and fixed during learning and inference, and MCAR means the mask is independent of data conditional on the realized graph.U-MCAR removes entries independently with a fixed probability; S-MCAR removes complete feature vectors for uniformly selected nodes.Source: §2 · pp. 2–4
  • With incomplete features, prediction requires handling missing information before or during prediction; the learner receives the graph, observed features, mask, and training-node labels.The complete-data model factorizes features, prediction given features, and the missingness mechanism, conditioned on the observed graph.Source: §2 · pp. 2–3
  • Feature-matrix methods fill missing entries using observed-value statistics or feature models, but do not use topology for feature recovery.Examples include mean or median replacement, GCNmf's Gaussian mixture, and GNN-MIM's concatenated missingness mask.Source: §2 · p. 3
  • Topology-aware methods such as Feature Propagation diffuse observed feature values across graph edges, while restoring observed entries during updates.PCFI adds confidence scores and channel-wise diffusion; FISF alternates propagation with repeated injection of observed features.Source: §2 · p. 3
  • Graph-based recovery depends on the spatial arrangement of observed entries, which standard MCAR/MAR/MNAR labels do not characterize.Two mechanisms can both be MCAR and have the same global missingness rate yet arrange missing entries differently over the graph.Source: §2 · p. 4

3 GRAPH-STRUCTURED MISSINGNESS

The section formalizes graph-structured dependence within missingness masks and introduces Recursive Transmission (RT) as a controlled mechanism for producing localized missing regions. It shows why compact missing regions limit the observed information available to propagation-based recovery and reports lower average propagation performance under RT than under uniform protocols.

3.1 GRAPH-STRUCTURED DEPENDENCE WITHIN THE MISSINGNESS MASK

  • Graph-structured mask dependence concerns internal dependence in p(M | A) that varies with graph structure, distinct from dependence between the mask and data.The definition requires dependence conditional on A and different joint mask distributions for possible graphs when non-topological mechanism parameters are fixed.Source: §3.1 · p. 4

3.2 RECURSIVE-TRANSMISSION MCAR

  • RT allocates a fixed missingness budget across feature channels and grows each feature's missing region along graph edges from a shared source, with independent tie-breaking.The resulting regions can overlap while diverging across channels.Source: §3.2 · pp. 4–5
  • RT is a controlled stress test, not a generative model of all real-world missingness; it matches standard protocols in total missing entries to isolate graph-localized mask dependence.When source selection and tie-breaking are independent of X and Y conditional on A, RT is MCAR and satisfies the graph-structured dependence definition.Source: §3.2 · p. 5

3.3 WHY GRAPH-STRUCTURED MISSINGNESS IS DIFFICULT FOR PROPAGATION

  • 0.725 macro-F1 AUC averaged across FP, PCFI, and FISF under RT, versus 0.754 under U-MCAR and 0.751 under S-MCAR.Figure 2 shows mean curves and one-standard-deviation bands over five seeds.Source: Figure 2 · p. 6, §3.3 · p. 6
  • For compact connected missing regions, reconstructed values depend on only a limited number of observed inputs, unlike equally sized missing sets scattered across the graph.Only nodes on the observed boundary can directly inject observed information into the missing region.Source: §3.3 · pp. 5–6

4 PEMIX: STRUCTURE-CONDITIONED PROBABILISTIC IMPUTATION

PEMix conditions a probabilistic model of incomplete node features on fixed global structural representations before message passing. It carries conditional uncertainty into the first GNN layer and jointly optimizes the mixture and downstream GNN.

4 PEMIX: STRUCTURE-CONDITIONED PROBABILISTIC IMPUTATION

  • PEMix conditions a probabilistic feature model on fixed graph representations, giving structurally different nodes different mixture-component priors before observed features update them.In the experiments, the representations are standardized non-trivial Laplacian eigenvectors computed once from the fully observed graph.Source: §4 · pp. 6–7
  • PEMix retains uncertainty in missing-feature distributions and analytically marginalizes component-wise moments through the first message-passing layer.The positional encodings affect mixture responsibilities but are not concatenated to the downstream GNN representation; mixture parameters are jointly optimized with the GNN after EM initialization.Source: §4 · p. 7
  • PEMix has the same per-epoch complexity as GCNmf, up to a dominated O(nKq) term and a one-off partial eigendecomposition per graph.Source: §4 · p. 7

5 EXPERIMENTAL EVALUATION

Experiments find PEMix most advantageous under graph-structured missingness, while competitive under uniform random missingness and naturally occurring missingness. Ablations indicate that its gains come from conditioning the missing-feature distribution on structural information, not positional encodings alone.

Datasets and protocol

  • Controlled experiments inject RT and U-MCAR across four datasets, while native-missingness experiments evaluate forecasting datasets and six RelBench tasks.Controlled curves cover missingness rates from 0 to 0.99; table summaries use five-seed results except RelBench, which uses three seeds and ten epochs.Source: §5 · pp. 7–8

RQ1: Controlled missingness

  • Under RT, PEMix has the best AUC on TADPOLE, GraphMSO, and PEMS-BAY, and ranks third on Engrad; under U-MCAR, it ranks first on TADPOLE and GraphMSO, second on PEMS-BAY, and third on Engrad.Table 1 summarizes performance as trapezoidal AUC over missingness rates; higher is better for macro-F1 and lower for MAE.Source: §5 · p. 8, Table 1 · p. 8

RQ2: Naturally occurring missingness

  • With naturally occurring missingness, PEMix has the lowest MAE on AQI and METR-LA, ranks second on PV-US, and its relational adaptation is best on four of six RelBench tasks.Neighboring-node co-missingness exceeds the spatially independent range on all three forecasting datasets.Source: §5 · pp. 8–9, Table 2 · p. 8, Table 3 · p. 9

RQ3: Positional encodings

  • Providing positional encodings alone does not reproduce PEMix’s performance; conditioning the missing-feature distribution on structural information is associated with its gains.Adding positional encodings to propagation mechanisms leaves a substantial gap, while downstream-only positional encodings improve TADPOLE but remain below PEMix.Source: §5 · p. 9, Table 4 · p. 9

6 CONCLUSION

The paper studies graph-structured missingness and proposes PEMix, which is particularly effective when missing observations are graph-localized. RT is MCAR relative to data under the stated conditions, while its mask can depend on graph topology in a non-degenerate regime.

6 CONCLUSION

  • PEMix conditions a probabilistic model of incomplete node features on global structural representations and is particularly effective for graph-localized missingness while remaining competitive under standard missingness.Ablations attribute its gains to structural conditioning rather than access to positional encodings alone; the evaluation is limited to node classification and forecasting, and assumes diagonal mixture covariances and a fully observed graph.Source: §6 · pp. 9–10

A.1 RT IS GRAPH-STRUCTURED MCAR

  • RT is MCAR when source selection and tie-breaking are independent of features and labels conditional on the adjacency matrix.The recursion uses adjacency and randomization variables, so mask dependence does not imply dependence on the data under this condition.Source: §A.1 · p. 12
  • RT’s mask is graph-structured under non-degeneracy and graph-support conditions, including connected undirected graphs, full-support source selection, and an intermediate channel budget.The complete-graph versus star comparison changes the conditional mask distribution when source law, budgets, and tie-breaking are held fixed.Source: §A.1 · p. 12

A.2 BOUNDARY BOTTLENECK FOR FEATURE PROPAGATION

For fixed linear, channel-wise propagation, the converged recovery map is constrained by the observed boundary of the missing region. The result does not automatically extend to nonlinear or cross-channel recovery.

A.2 BOUNDARY BOTTLENECK FOR FEATURE PROPAGATION

  • Under the spectral-radius condition, the propagation iteration converges to the unique fixed point BxO.The initial-condition term vanishes and the limit is (I − T)^−1 CxO.Source: §A.2 · pp. 12–13
  • Only observed boundary coordinates can influence the limit, and the recovery map has rank at most the number of observed boundary nodes.The rank bound follows because B has rank equal to C and C has at most |∂OM| nonzero columns.Source: §A.2 · p. 13
  • The boundary-rank result applies to fixed linear, channel-wise propagation, not automatically to nonlinear or cross-channel recovery.A low-rank recovery map alone does not imply positive error for every graph signal.Source: §A.2 · p. 13

B DATASETS AND EVALUATION PROTOCOL

The evaluation uses static graph samples and preserves chronological splits to prevent leakage. A co-missingness analysis finds that naturally missing values are more clustered across neighboring nodes than expected under spatial independence.

B DATASETS AND EVALUATION PROTOCOL

  • Forecasting prediction times become independent static graph samples using past measurements as features and subsequent measurements as targets, with chronological splits and training-only standardization statistics.Artificial masks are applied before windowing, naturally missing values are preserved, and missing targets are excluded from loss and evaluation.Source: B DATASETS AND EVALUATION PROTOCOL · p. 13, Table 5 · p. 13

B.1 SPATIAL ORGANIZATION OF MISSINGNESS IN REAL-WORLD DATASETS

  • HCmiss compares the fraction of edges with two missing endpoints against the spatial-independence expectation; values above 1 indicate excess neighboring-node co-missingness.The analysis uses all timestamps and partial timestamps, with a 999-permutation null range preserving temporal missingness trajectories and per-time missing-node counts.Source: §B.1 · p. 14, Table 6 · p. 14
  • On all three datasets, observed co-missingness exceeds the permutation-null range; over partial timestamps, HCmiss is 4.03 on METR-LA, 1.21 on PV-US, and 1.16 on AQI.The excess over all timestamps is largest on AQI.Source: §B.1 · p. 14, Table 6 · p. 14

C PROPAGATION CONTROLS ON TADPOLE

The propagation-control tables provide complete macro-F1 and classification-AUROC results, while integrated curve areas summarize performance across missingness rates.

C PROPAGATION CONTROLS ON TADPOLE

  • Tables 7–9 provide complete macro-F1 and classification-AUROC results for Figure 2.Reported results are mean ± standard deviation over five seeds.Source: C PROPAGATION CONTROLS ON TADPOLE · p. 15
  • 0.7252, 0.7543, and 0.7508 are the macro-F1 curve areas under RT, U-MCAR, and S-MCAR, respectively.Areas integrate the mean curves over [0, 0.99] without normalization.Source: C PROPAGATION CONTROLS ON TADPOLE · p. 15
  • 0.8855, 0.8958, and 0.8963 are the classification-AUROC curve areas under RT, U-MCAR, and S-MCAR, respectively.These curve areas are distinct from classification AUROC at a particular missingness rate.Source: C PROPAGATION CONTROLS ON TADPOLE · p. 15

D COMPLETE RESULTS UNDER CONTROLLED MISSINGNESS

The controlled-missingness appendix provides complete results across TADPOLE and three forecasting datasets, with results divided by missingness range and summarized by trapezoidal AUC.

D COMPLETE RESULTS UNDER CONTROLLED MISSINGNESS

E IMPLEMENTATION AND REPRODUCIBILITY DETAILS

The appendix documents reproducibility choices and computational costs, then reports ablations testing structural conditioning, positional-encoding controls, and joint mixture optimization.

E IMPLEMENTATION AND REPRODUCIBILITY DETAILS

  • The appendix specifies diagonal covariances, validation-only model selection, and separate configuration selection for controlled versus naturally occurring missingness.For natural missingness, no additional missingness is injected and configurations are selected by validation MAE; the diagonal covariance assumption is PEMIX’s main modelling limitation.Source: E IMPLEMENTATION AND REPRODUCIBILITY… · p. 21

E.1 COMPUTATIONAL COMPLEXITY

  • PEMIX has the same per-epoch complexity as GCNmf: its additional O(nKq) responsibility cost is dominated when q ≤ dh.PEMIX handles missing features inside the forward pass and requires one sparse partial eigendecomposition per graph, independent of the mask.Source: §E.1 · p. 26

F ABLATIONS

  • The ablation appendix includes matched PE-conditioning, PE-only, and joint-GMM-optimization controls, plus complete per-level positional-encoding results on TADPOLE.It also includes an MLP PE-only control to separate PE information from message passing.Source: F ABLATIONS · p. 27

F.2 PE-ONLY CONTROLS

  • The PE-only GCN and MLP controls score 0.295 ± 0.092 and 0.254 ± 0.027 macro-F1, below PEMix at every missingness level, including 0.822 ± 0.047 at μ = 0.99.Neither control receives node features, so its score does not depend on μ.Source: §F.2 · p. 27

F.1 MATCHED STRUCTURAL-CONDITIONING ABLATION

  • Removing PE conditioning lowers TADPOLE AUC from 0.8243 to 0.7330; the gap grows from μ = 0.6 onwards, reaching 0.49.The matched models share masks, splits, optimization settings, and the probabilistic first layer, and coincide at μ = 0.Source: §F.1 · p. 27, Figure 3 · p. 28

F.3 EFFECT OF JOINT GMM OPTIMISATION

  • Jointly optimizing the mixture improves EngRAD forecasting performance over a frozen GMM at 20%, 50%, and 80% missingness under RT.The comparison uses five seeds; the frozen variant fixes mixture means, variances, and weights after EM initialization.Source: §F.3 · p. 27, Table 40 · p. 28

F.4 POSITIONAL-ENCODING ABLATION: COMPLETE RESULTS ON TADPOLE

The positional-encoding ablation tables report TADPOLE macro-F1 under RT across missingness rates, distinguishing PE use in the mechanism from downstream concatenation.

F.4 POSITIONAL-ENCODING ABLATION: COMPLETE RESULTS ON TADPOLE

  • Tables 41–42 report TADPOLE macro-F1 under RT for every model in Table 4, with means and standard deviations over five seeds.The tables divide missingness rates into 0–50% and 60–99%, with trapezoidal AUC in the continuation.Source: §F.4 · p. 28, Table 41 · p. 29, Table 42 · p. 29
  • The “Mechanism” variant uses PE while handling missing features, whereas “Downstream” concatenates PE after missing-feature handling.For GCNmf + PE (downstream), PE cannot affect the mixture responsibilities.Source: §F.4 · p. 28, Table 41 · p. 29, Table 42 · p. 29

Related papers

Loading 2610.18113v1…