Many real-world dynamical systems consist of sparsely interacting components and hence exhibit an underlying graph structure as in logistical, epidemic, and traffic networks. Yet, because of their high dimensionality, their forecasting presents major computational challenges, which are often exacerbated by measurement noise or uncertainty. We propose to partly address this problem, focusing on computationally efficient and robust forecasting under network topology perturbation. The latter represents a singular aspect of network systems entailing specific challenges, such as break in synchronization and cascade failures, hence calling for tailored forecasting algorithms. Specifically, in the limit of large number of nodes, we uncover distinct noise regimes in which the underlying system is either predictable with arbitrary accuracy, predictable only up to a limited accuracy, or entirely unpredictable. Furthermore, we propose a network forecasting approach based on a probabilistic representation of the system under study, that leverages a Bayesian coreset approximation for efficient and robust dimensionality reduction. Numerical experiments demonstrate the competitiveness of the proposed method.