  Encoder-decoder deep neural networks have been increasingly studied for
multi-horizon time series forecasting, especially in real-world applications.
However, to forecast accurately, these sophisticated models typically rely on a
large number of time series examples with substantial history. A rapidly
growing topic of interest is forecasting time series which lack sufficient
historical data -- often referred to as the ``cold start'' problem. In this
paper, we introduce a novel yet simple method to address this problem by
leveraging graph neural networks (GNNs) as a data augmentation for enhancing
the encoder used by such forecasters. These GNN-based features can capture
complex inter-series relationships, and their generation process can be
optimized end-to-end with the forecasting task. We show that our architecture
can use either data-driven or domain knowledge-defined graphs, scaling to
incorporate information from multiple very large graphs with millions of nodes.
In our target application of demand forecasting for a large e-commerce
retailer, we demonstrate on both a small dataset of 100K products and a large
dataset with over 2 million products that our method improves overall
performance over competitive baseline models. More importantly, we show that it
brings substantially more gains to ``cold start'' products such as those newly
launched or recently out-of-stock.
