  Graph Neural Networks (GNNs) have achieved state-of-the-art performance in
node classification, regression, and recommendation tasks. GNNs work well when
rich and high-quality connections are available. However, their effectiveness
is often jeopardized in many real-world graphs in which node degrees have
power-law distributions. The extreme case of this situation, where a node may
have no neighbors, is called Strict Cold Start (SCS). SCS forces the prediction
to rely completely on the node's own features. We propose Cold Brew, a
teacher-student distillation approach to address the SCS and noisy-neighbor
challenges for GNNs. We also introduce feature contribution ratio (FCR), a
metric to quantify the behavior of inductive GNNs to solve SCS. We
experimentally show that FCR disentangles the contributions of different graph
data components and helps select the best architecture for SCS generalization.
We further demonstrate the superior performance of Cold Brew on several public
benchmark and proprietary e-commerce datasets, where many nodes have either
very few or noisy connections. Our source code is available at
https://github.com/amazon-research/gnn-tail-generalization.
