acceptodds
Under review as a conference paper at ICLR 2027

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

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 propa- gates 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 con- dition 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Missing Node Features, Feature Propagation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_RoDtOpenReview ↗
Rating
2(−1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper examines settings in which missing features are concentrated in connected regions of a graph. It introduces a controlled masking procedure and proposes PEMix, which conditions a probabilistic feature model on structural encodings before message passing. Experiments with both synthetic and naturally occurring missingness show performance improvements in several settings.

Critical strengths

1.The paper addresses a relevant issue in the evaluation of methods for handling missing features and clearly explains why clustered missingness can pose challenges for feature propagation. 2.The matched ablation study provides convincing evidence for the benefits of structural conditioning on TADPOLE.

Critical weaknesses

1.The performance gains vary across datasets, and it remains unclear which properties of the graph or missingness pattern influence the effectiveness of PEMix. 2.The proposed masking procedure captures a relatively specific pattern of missingness, leaving its coverage of other graph-structured missingness patterns unclear.

Questions for authors

1.Does PEMix remain effective under other forms of graph-structured missingness? 2.What factors account for the variation in performance across datasets, particularly in cases where propagation-based methods perform better?

4 comments
AuthorsOpenReview ↗

Response to W1–W2 and Q1–Q2.

Thank you for your detailed review and your valuable time. Below, we address your concerns.


W2/Q1: Effectiveness with other structural missingness

RT captures realistic scenarios, such as localized failures in sensor or communication networks. However, we agree that other realistic graph-dependent missingness patterns are not covered by RT. We have now included in the paper another realistic graph-structured missingness scenario, based on the Ising model [1]. The Ising model uses two parameters: the first controls how strongly the same feature tends to be missing at neighboring nodes, while the second controls how strongly different features tend to be missing together within a node. Unlike RT, there is no shared source node, and multiple missing regions can form. We verified on TADPOLE that Ising masks exhibit different spatial correlations compared with RT (Table 52). Importantly, PEMix does not assume RT or any specific missingness geometry. Results under the new Ising mechanism, evaluated at the same missingness rates as RT. Consistently with the RT results, PEMix achieves the best AUC under the Ising setting on five of the six datasets, across classification and forecasting tasks (Table 53). A detailed description of the Ising mechanism and further experimental details are provided in Appendix G.

[1] Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press.


W1/Q2: Factors behind the variation across datasets.

We investigate the factors behind dataset-dependent performance in Appendix H. PEMix relies on the assumption that node features and structural position are dependent. In that case, PE provides useful information about node features and we expect larger gains when this dependence is stronger. To quantify this relationship, we train an MLP to predict node features from PE, measuring predictability S as the relative reduction in squared prediction error compared to predicting the training mean. As shown in Figure 6, higher predictability is associated with larger PEMix gains: Electric (S≈0.35S \approx 0.35), TADPOLE (S≈0.17S \approx 0.17), and Tolokers (S≈0.11S \approx 0.11) achieve improvements of 10.9%, 10.4%, and 4.9%, respectively, over the strongest competitors under RT. Conversely, EngRAD and GraphMSO have near-zero predictability, explaining why structural conditioning provides little additional benefit. This is due to the particular nature of these two datasets, originally designed for spatio-temporal forecasting, where the features are seasonal time series. The graph topology describes which time series are related, but there is no static information that distinguishes and characterizes the nodes, nor do these have a specific role in the graph. The graph, thus, provides only relational information, which is already well captured by a propagation-based method. The limited or negative gains of PEMix on these datasets are therefore consistent with its underlying assumption. These results suggest that the strength of the relationship between structural position and node features is an important factor explaining performance variation across datasets. PEMix is expected to provide larger benefits when this relationship is strong, particularly under graph-structured missingness.


We thank the reviewer again for their constructive feedback, which helped us strengthen the experimental evaluation and clarify the conditions under which PEMix is most effective. Please let us know if our responses address your concerns or if further clarification would be helpful.

Thank you for the detailed response and the additional experiments. The Ising-model results provide further evidence on PEMix under a different graph-structured missingness pattern, while the analysis of PE predictability offers a possible explanation for the variation across datasets. I appreciate the clearer discussion of the method’s assumptions and the conditions under which it may be most useful.

Thank you for your follow-up and for acknowledging our additional analyses. We are glad that the Ising-model experiments and the PE predictability analysis helped clarify how PEMix behaves under different graph-structured missingness patterns, and under which conditions it is most effective.

We sincerely appreciate your review. Your comments directly led to these additions, and we believe they have made the paper more complete, both in the range of missingness mechanisms it covers and in how clearly it states the method’s assumptions. If you feel the paper has been strengthened as a result, we would be grateful if you would consider taking this into account in your final evaluation.

Thank you again for your time and engagement during the discussion.

Dear Reviewer,,

We noticed that the rating was recently changed from 3 to 2. Given your latest comment, which indicated that our additional experiments and analyses addressed your questions, we wondered whether this change might have been unintentional. Could you kindly confirm whether the updated rating reflects your intended assessment?

Thank you again for your time and engagement.

Reviewer_SSYnOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates graph learning with structured missing node features, arguing that conventional independent masking protocols overlook spatially correlated missingness. The authors formalize graph-structured mask dependence and introduce Recursive Transmission (RT) to simulate localized missing regions. They theoretically characterize a boundary bottleneck in feature propagation and propose PEMix, which conditions a probabilistic feature model on graph structural representations rather than propagating observed values. Experiments across controlled and naturally occurring missingness demonstrate its effectiveness, particularly under severe missingness.

Critical strengths
  1. The paper presents a well-motivated and meaningful perspective on missing node features. Distinguishing dependencies within missingness masks from conventional MCAR/MAR/MNAR assumptions is interesting and practically relevant. More importantly, the authors connect this problem to a concrete limitation of feature propagation through a theoretical analysis, providing a clear motivation for the proposed approach.

  2. The experimental evaluation is comprehensive and thoughtfully designed. The authors consider multiple missingness mechanisms, varying missingness severity, naturally incomplete datasets, and relational learning tasks. I particularly appreciate the comparisons involving positional encodings and the matched ablation in Appendix F.1, which help distinguish the proposed structural conditioning mechanism from simply providing additional structural features. These results provide meaningful support for the contribution.

Critical weaknesses
  1. The representativeness of the proposed RT mechanism remains somewhat uncertain. Its shared-seed and recursive expansion design deliberately produces localized missing regions, which are challenging for propagation-based methods. Although the experiments on naturally occurring missingness strengthen the motivation, the relationship between RT and the broader range of realistic graph-dependent missingness patterns is not fully established.

  2. The theoretical analysis provides a useful explanation of the boundary bottleneck, but its scope is relatively limited. Proposition 2 characterizes fixed linear feature propagation, and the rank bound does not directly establish reconstruction error or extend to more sophisticated recovery methods. The connection between this theoretical limitation and PEMix's empirical advantages could be further clarified.

Questions for authors
  1. How representative is the shared-seed RT mechanism of naturally occurring graph-structured missingness? Would the main conclusions remain consistent under alternative spatially correlated masking patterns with less concentrated missing regions?

  2. Proposition 2 bounds the rank of the propagation map by the observed boundary size. Could the authors provide more direct evidence connecting boundary size to recovery degradation under RT, particularly for PCFI and FISF?

  3. Appendix F.1 provides a useful matched ablation on TADPOLE. Could the authors clarify whether the benefits of structural conditioning persist in the same controlled comparison on forecasting or naturally incomplete datasets?

  4. Since PEMix relies on structural representations to inform feature distributions, how does its effectiveness depend on the strength of the relationship between graph topology and node features? Clarifying this relationship would help identify when the proposed mechanism is most beneficial.

Overall, I find this paper interesting and well motivated, with a coherent connection between its problem formulation, theoretical analysis, and proposed method. The experimental evaluation is substantial and supports the practical value of the approach. While the generality of the missingness mechanism and the scope of the theoretical justification could be further clarified, I consider the proposed perspective and its empirical findings meaningful contributions. I would be interested in discussing these points further with the authors.

2 comments
AuthorsOpenReview ↗

Response to W1–W2 and Q1–Q4: Additional Experiments and Theoretical Analysis

We thank the reviewer for their careful reading and constructive suggestions, which helped us strengthen the paper.


W1/Q1: Other topology-dependent missingness mechanisms

RT captures realistic scenarios, such as localized failures in sensor or communication networks. However, we agree that other realistic graph-dependent missingness patterns are not covered by RT. We have now included in the paper another realistic graph-structured missingness scenario, based on the Ising model [1]. The Ising model uses two parameters: the first controls how strongly the same feature tends to be missing at neighboring nodes, while the second controls how strongly different features tend to be missing together within a node. Unlike RT, there is no shared source node, and multiple missing regions can form. We verified on TADPOLE that Ising masks exhibit different spatial correlations compared with RT (Table 52).

Importantly, PEMix does not assume RT or any specific missingness geometry. Results under the new Ising mechanism, evaluated at the same missingness rates as RT. Consistently with the RT results, PEMix achieves the best AUC under the Ising setting on five of the six datasets, across classification and forecasting tasks (Table 53). A detailed description of the Ising mechanism and further experimental details are provided in Appendix G.

[1] Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press.


W2/Q2: Theoretical analysis

Following your suggestion, we have extended the theoretical analysis in Appendix A.3 in two directions.

First, our new Proposition 3 extends the rank bound beyond FP to the propagation steps of PCFI and FISF, while the new Corollary 2 derives a lower bound on the expected squared reconstruction error. Second, we provide direct empirical evidence connecting boundary size to reconstruction error. On Electric, at 50% missingness, RT leaves only 86 observed boundary nodes, compared with 608 under U-MCAR. This greater boundary coverage reduces the normalized reconstruction MAE by 37% for PCFI, 30% for FISF, and 33% for FP. By progressively replacing RT-masked nodes with randomly selected ones while keeping the missingness rate fixed, we observe decreasing reconstruction error as the boundary grows (Figure 3). These results directly support the proposed boundary bottleneck: RT limits how much propagation mechanisms can recover missingness.


Q3: Ablations on additional Datasets

We have extended our ablation analysis on PEMS-BAY (forecasting under injected missingness) and AQI (naturally incomplete forecasting). Results averaged over five seeds show that removing PE increases test MAE on PEMS-BAY from 3.675/3.823/3.9363.675/3.823/3.936 to 3.752/3.904/4.2343.752/3.904/4.234 at 20/50/80% missingness, respectively, and from 18.75718.757 to 18.84618.846 on AQI. These results confirm that the benefits of structural conditioning extend beyond TADPOLE. More details are provided in Appendix F.1.


Q4. Dependence on the structure–feature relationship.

PEMix relies on structural representations to inform the distribution of missing features. To quantify this relationship, we trained an MLP to predict node features from PE, measuring predictability S as the relative reduction in squared prediction error compared to predicting the training mean. This quantifies how much information structural position provides about node features. Further experimental details and complete results are reported in Appendix H. As shown in Figure 6, higher predictability is associated with larger PEMix gains. On Electric (S≈0.35S \approx 0.35), TADPOLE (S≈0.17S \approx 0.17), and Tolokers (S≈0.11S \approx 0.11), PEMix improves over the strongest competing methods by 10.9%, 10.4%, and 4.9%, respectively, under RT. Conversely, on EngRAD and GraphMSO, where predictability is nearly zero, PEMix shows limited or no advantage.


We thank the reviewer again for their constructive feedback, which helped us strengthen both the theoretical analysis and the experimental evaluation of our work. Please let us know if our responses address your concerns or if further clarification would be helpful.

Dear Reviewer,

As the discussion period closes in a few days, we wanted to kindly follow up on our response above. As you mentioned being interested in discussing these points further, we would be happy to address any remaining questions or concerns.

Thank you again for your thoughtful feedback.

Reviewer_g7T3OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies graph-structured missingness, where connected nodes tend to have missing features together. It introduces Recursive Transmission (RT) to simulate this missingness and analyzes why existing feature propagation methods may struggle in such settings. To address this problem, the paper proposes PEMix, which combines Laplacian positional encodings with a Gaussian mixture model to handle missing node features. Experiments are conducted on node classification, forecasting, and relational learning datasets under both simulated and naturally occurring missingness.

Critical strengths
  1. Important problem setting. The paper studies graph-structured missingness, where connected nodes may lose their features together. This is a meaningful problem because existing methods are mainly evaluated under random missingness. The proposed RT mechanism provides a useful way to study this problem.
  2. Clear motivation and theoretical analysis. The paper provides a theoretical explanation of why feature propagation can struggle with graph-structured missingness. PEMix is designed to address this problem, and the results on TADPOLE and PEMS-BAY show clear improvements.
Critical weaknesses
  1. Limited evaluation on standard graph datasets. Although the paper focuses on missing node features in graphs, most experiments are conducted on time-series forecasting or relational datasets. Only one dataset, TADPOLE, is used for standard node classification. Common graph benchmarks such as Cora, CiteSeer, and PubMed are not included. This makes it difficult to evaluate whether the proposed method works well on general graph learning tasks.
  2. Limited methodological novelty and inconsistent improvements. PEMix mainly extends the existing GCNmf method by adding Laplacian positional encodings to its Gaussian mixture model. The methodological novelty therefore appears limited. Moreover, the improvements are very small on GraphMSO, and PEMix performs worse than propagation-based methods on EngRAD. These results raise concerns about the general effectiveness of the proposed method.
Questions for authors
  1. Clarification: Why are common graph node classification benchmarks, such as Cora, CiteSeer, and PubMed, not included in the experiments? Is there any specific reason these datasets are not suitable for the proposed method?
  2. Additional evidence: Can the authors provide experimental results on standard graph benchmarks under RT missingness? These results would help determine whether PEMix is effective beyond the datasets currently evaluated and could significantly affect my assessment.
  3. Clarification: Why does PEMix show only a very small improvement on GraphMSO and perform worse than propagation-based methods on EngRAD? Under what graph conditions is PEMix expected to work better than feature propagation?
3 comments
AuthorsOpenReview ↗

Response to W1, W2, and Q1–Q3

We thank the reviewer for their careful reading and constructive suggestions.


W1/Q1/Q2: Use of Cora, Citeseer and PubMed and additional evidence on node classification dataset.

Following your suggestion, we included additional node classification datasets. However, we decided not to use Cora, Citeseer, and PubMed for the reason below.

  1. Common Benchmarks and dataset selection. The exclusion of Cora, CiteSeer, and PubMed was a deliberate choice motivated by [1], who showed both theoretically and empirically that the highly sparse bag-of-words features in these datasets make them poorly suited for evaluating robustness to missing features. We therefore prioritized datasets that provide a more meaningful evaluation under challenging missingness regimes. Specifically, we selected datasets with raw features rather than embeddings, sourced from standard graph benchmarks, spatio-temporal networks, or relational databases modeled as graphs. We have added an explanation of our benchmark selection in the Introduction and Section 5.
  2. Additional node classification datasets. We further extended our node classification evaluation with two datasets that respect the properties identified in Ferrini et al.[1], namely Tolokers [2] and Electric [1]. The results on these new datasets remain consistent with our original findings, PEMix ranks first on both datasets under RT and U-MCAR missingness mechanisms (added to Table 1 and Appendix D in the revised manuscript).

[1] Ferrini et al., Rethinking GNNs and Missing Features: Challenges, Evaluation and a Robust Solution, ICML 2026
[2] Platonov et al., A Critical Look at the Evaluation of GNNs under Heterophily: Are We Really Making Progress?, ICLR 2023


W2: Limited novelty

The novelty and contributions of our work extend beyond using PE inside the GMM of GCNmf.

  • First, we introduce and, for the first time, formalize graph-structured mask dependence, a previously overlooked dimension of missingness.
  • Second, we theoretically and empirically demonstrate the limitations of state-of-the-art propagation-based methods under this realistic missingness setting.
  • Third, we propose PEMix, a new model that introduces a different way of leveraging graph structure: rather than propagating observed features, it uses structural information to condition the missing-feature distribution. Our ablations (Section 5, Table 4; Appendix F.1, Figure 4) confirm that this conditioning mechanism is key to the observed improvements, which cannot, thus, be simply attributed to the PEs.

Q3. Low performance on GraphMSO and EngRAD, and when PEMix should outperform propagation.

This is a good point, thanks!

PEMix relies on the assumption that node features and structural position are dependent, so that PE provides useful information about node features. We therefore expect larger gains of PEMix when this dependence is stronger. We added this important discussion in Section 4 and appendix H.

To measure this in a quantifiable way, we trained an MLP to predict node features from PE (details in Appendix H). We computed predictability SS as the relative reduction in squared prediction error compared to a baseline that always predicts the training mean. This normalized score allows comparisons across datasets with different feature scales, with values close to zero indicating that PE does not provide predictive information about node features. As shown in the new Figure 6, predictability is nearly zero on EngRAD (S≈0.003S \approx 0.003) and GraphMSO (S≈0S \approx 0), indicating that structural position does not provide information about their node features. This is due to the particular nature of these two datasets, originally designed for spatio-temporal forecasting, where the features are seasonal time series. The graph topology describes which time series are related, but there is no static information that distinguishes and characterizes the nodes, nor do these have a specific role in the graph. The graph, thus, provides only relational information, which is already well captured by a propagation-based method. The limited or negative gains of PEMix on these datasets are therefore consistent with its underlying assumption. Conversely, predictability is substantially higher on TADPOLE (S≈0.17S \approx 0.17), Electric (S≈0.35S \approx 0.35), and Tolokers (S≈0.11S \approx 0.11), where PEMix achieves gains of 10.4%, 10.9%, and 4.9%, respectively, over the strongest competing methods under RT. These results indicate that PEMix is most beneficial on graphs where nodes have distinct roles in the graph and structural position is informative about node features, while its advantage is expected to diminish when this relationship is weak. We thank the reviewer for the comment, which helped in making our paper more rigorous.


Thank you again. Please let us know if our answers address your concerns, or whether we can provide further clarifications

Dear Reviewer,

As the discussion period closes in a few days, we wanted to kindly follow up on our response. We would be glad to know whether it addresses your concerns, or whether there is anything else we can clarify in the remaining time.

Thank you again for your time.

I thank the authors for their detailed responses and additional experiments. However, my main concerns remain insufficiently addressed. Therefore, I maintain my original rating.

Comments on the paper

4 comments

Yes, my initial evaluation was that this article should be weakly accepted. However, when I saw the comments of the reviewer g7T3, I thought that some of the problems he raised had not been solved. So I lowered my score.

Thanks to the AC for his attention to the problem.

AuthorsOpenReview ↗

Summary of Rebuttal and Key Improvements

Dear Reviewers and Area Chairs,

We sincerely thank the reviewers for their constructive feedback, which helped us substantially strengthen our paper. We would like to briefly summarize the main improvements:

  • Additional node classification experiments (g7T3). Following the reviewer's suggestion, we expanded our evaluation with two additional node classification benchmarks, Tolokers and Electric, where PEMix outperforms all competing methods under both RT and U-MCAR missingness. We also clarified why Cora, CiteSeer, and PubMed are not suited for evaluating missing-feature robustness, as previously demonstrated by Ferrini et al. (ICML 2026).
  • Novelty and performance variability (g7T3, RoDt). We clarified that our contributions extend beyond incorporating positional encodings: we formalize graph-structured mask dependence, theoretically characterize the limitations of feature propagation, and propose a different approach based on structural conditioning. We also introduced a quantitative analysis of PE-to-feature predictability, which helps explain when PEMix outperforms propagation-based methods, including its small gain on GraphMSO and its lower performance on EngRAD.
  • Generality, theoretical analysis, and ablations (SSYn, RoDt). We introduced an alternative Ising-based missingness mechanism, under which PEMix achieves the best AUC on five of six datasets. We also extended our theoretical results to additional propagation methods, derived a lower bound on the reconstruction error, provided direct experimental evidence of the boundary bottleneck, and expanded our ablations to PEMS-BAY and AQI.

We particularly appreciate that Reviewer SSYn recognized the "coherent connection between its problem formulation, theoretical analysis, and proposed method", describing the experimental evaluation as "substantial" and our findings as "meaningful contributions".

We also appreciate Reviewer RoDt's explicit acknowledgment that the new Ising experiments "provide further evidence" and that our predictability analysis "offers a possible explanation for the variation across datasets", alongside their appreciation of the clearer discussion of the method's assumptions. This makes the subsequent unexplained score reduction particularly surprising. Despite our requests for clarification, no explanation has been provided, and we hope this was simply an unintended change.

We believe these additions have substantially strengthened both the theoretical and empirical contributions of our work, and we hope they will be carefully considered in the final assessment.

Thank you again for your time and consideration.

The Authors

Yes, my initial evaluation was that this article should be weakly accepted. However, when I saw the comments of the reviewer g7T3, I thought that some of the problems he raised had not been solved. So I lowered my score.

Thanks to the AC for his attention to the problem.

I have provided the explanation.

Dear Reviewer,

Thank you for clarifying your reasoning and confirming that your initial assessment was a weak accept.

While we fully respect the discussion among reviewers, we believe that such a score reduction should have been accompanied by an explanation, particularly since your only previous feedback on our rebuttal was positive and explicitly acknowledged our additional contributions.

We would also like to emphasize that we directly addressed Reviewer g7T3's concerns through additional node classification experiments, clarification of our methodological contributions, and a quantitative analysis explaining performance variability. As Reviewer g7T3 has not responded to these additions, we hope the AC will carefully consider this new evidence when assessing whether the original concerns remain valid.

Thank you again for your time and consideration.

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.