Adaptive Prototype-Guided Personalized Propagation for Heterophilic Graphs With Missing Data

Graph neural networks (GNNs) have achieved strong results on homophilic graphs with complete node attributes, yet their performance significantly deteriorates when faced with the combined challenges of heterophily and feature missingness. Heterophily introduces semantic inconsistency in neighborhoods, while feature missingness obscures node identity, which together constitute a complex problem we define as the heterophily-missing coupling (HMC). Under HMC, information exchanged between nodes becomes less reliable, and the usual assumptions that support message propagation no longer hold. To address this, we propose a novel adaptive prototype-guided personalized propagation (APP) framework. Specifically, it first leverages semantic rectification via prototypes (SRPs) to align neighborhood information with prototype semantics, reducing noise from inconsistent neighbors. Subsequently, personalized virtual propagation (PVP) builds upon this by clustering to construct prototype-aligned virtual edges, enabling effective feature imputation through minimizing Dirichlet energy across both real and virtual graphs. Finally, adaptive representation synergy (ARS) consolidates the propagated and imputed features by employing prototype-guided confidence weighting and enhancing representation quality via a contrastive training objective. Extensive experiments on multiple benchmark datasets demonstrate that APP consistently improves node classification performance on heterophilic graphs with missing features, achieving up to 11.22% improvement over state-of-the-art baselines while significantly reducing imputation error. The implementation is publicly available at https://github.com/limengran98/APP.