Kernel and linear regression have been recently explored in the prediction of graph signals as the output, given arbitrary input signals that are agnostic to the graph. In many real-world problems, the graph expands over time as new nodes get introduced. Keeping this premise in mind, we propose a method to recursively obtain the optimal prediction or regression coefficients for the recently proposed Linear Regression over Graphs (LRG), as the graph expands with incoming nodes. This comes as a natural consequence of the structure of the regression problem, and obviates the need to solve a new regression problem each time a new node is added. Experiments with real-world graph signals show that our approach results in a good prediction performance which tends to be close to that obtained from knowing the entire graph apriori.