AttriReBoost: A Gradient-Free Propagation Optimization Method for Cold-Start Mitigation in Attribute Missing Graphs

In real-world graphs, node attributes are often incomplete due to acquisition costs or privacy restrictions, reducing representation quality and harming downstream predictions in graph neural networks (GNNs). A common remedy is feature-propagation-based imputation. However, cold-start effects arising from attribute resetting and low-degree nodes impede effective propagation and convergence in these methods. To address these challenges, we propose AttriReBoost (ARB), a propagation-based method that mitigates cold-start issues in attribute-missing graphs. ARB enhances global feature propagation (FP) by redefining initial boundary conditions and strategically integrating virtual edges, thereby improving node connectivity and ensuring stable and efficient convergence. The method supports gradient-free attribute reconstruction with low computational overhead, and we provide a rigorous convergence analysis. Extensive experiments on several real-world benchmark datasets demonstrate the effectiveness of ARB, achieving an average accuracy improvement of 5.11% over state-of-the-art methods. In addition, ARB exhibits remarkable computational efficiency, processing a large-scale graph with 2.44 million nodes in just 16 s on a single GPU. Our code is available at https://github.com/limengran98/ARB.