Year: 2021

Abstract:
Graph Neural Networks (GNNs) have achieved state of the art performance in node classification, regression, and recommendation tasks. GNNs work well when high-quality and rich connectivity structure is available. However, this requirement is not satisfied in many real world graphs where the node degrees have power-law distributions as many nodes have either fewer or noisy connections. The extreme case of this situation is a node may have no neighbors at all, called Strict Cold Start (SCS) scenario. This forces the prediction models to rely completely on the node’s input features. We propose Cold Brew to address the SCS and noisy neighbor setting compared to pointwise and other graph-based models via a distillation approach. We introduce feature-contribution ratio (FCR), a metric to study the viability of using inductive GNNs to solve the SCS problem and to select the best architecture for SCS generalization. We experimentally show FCR disentangles the contributions of various components of graph datasets and demonstrate the superior performance of Cold Brew on several public benchmarks and proprietary e-commerce datasets. Our codes will be fully open-sourced upon acceptance.

text: Graph Neural Networks (GNNs) have achieved state of the art performance in node classification, regression, and recommendation tasks. GNNs work well when high-quality and rich connectivity structure is available. However, this requirement is not satisfied in many real world graphs where the node degrees have power-law distributions as many nodes have either fewer or noisy connections. The extreme case of this situation is a node may have no neighbors at all, called Strict Cold Start (SCS) scenario. This forces the prediction models to rely completely on the node’s input features. We propose Cold Brew to address the SCS and noisy neighbor setting compared to pointwise and other graph-based models via a distillation approach. We introduce feature-contribution ratio (FCR), a metric to study the viability of using inductive GNNs to solve the SCS problem and to select the best architecture for SCS generalization. We experimentally show FCR disentangles the contributions of various components of graph datasets and demonstrate the superior performance of Cold Brew on several public benchmarks and proprietary e-commerce datasets. Our codes will be fully open-sourced upon acceptance.

heading: 1 INTRODUCTION
text: Graph Neural Networks (GNNs) achieve state-of-the-art results across a wide range of tasks such as graph classification, node-classification, -regression, link prediction, and recommendation (Wu et al., 2020; Goyal & Ferrara, 2018; Kherad & Bidgoly, 2020; Shaikh et al., 2017; Silva et al., 2010; Zhang et al., 2019). GNNs rely on the principle of message passing to aggregate node features across multi-hop neighborhoods in order to learn aggregated representations. The success of modern GNN models relies on the presence of dense connections and high-quality neighborhoods. State-of-the-art GNNs (Kipf & Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017; Xu et al., 2018a; Wu et al., 2019; Klicpera et al., 2018) benefit from efficient message-passing frameworks developed to best leverage (deep) neighborhood information to learn node representations. Other methods like the spectral diffusion (Joachims, 2003; Chaudhuri et al., 2012; Zhang & Rohe, 2018; Wang et al., 2021) and label propagation (Huang et al., 2020a; Zhu, 2005) also require a non-empty and high-quality neighborhood per node to perform message passing. Even the inductive GNNs (e.g., Hamilton et al. (2017)) learn a function of the node feature and the node neighborhood, requiring the neighborhood to be present during the inference time.
Most of the large-scale real-world graphs are power-law in nature, with a majority of the nodes having very few connections (Hao et al., 2021; Ding et al., 2021; Lam et al., 2008; Lu et al., 2020). In Figure 1 we conceptually show the long-tail distribution of such a graph and also empirically show this characteristics on several public datasets. In many information retrieval and recommender systems applications, there is another ubiquitous challenge: the Strict Cold Start (SCS) (Li et al., 2019b; Ding et al., 2021), wherein some “nodes” will have no edges in the graph. For instance, in most of the public and proprietary datasets we used in the experimentation we have anywhere between 3% to 6% isolated nodes with no neighbors. In these cases, existing GNNs fail to perform due to sparsity or absence of neighborhood.
In this paper, we develop GNN models that can achieve truly inductive capabilities: one can learn effective node embeddings for “orphaned” nodes in a graph. This capability is
important to fully realize the potential of large-scale GNN models on modern, industrialsized datasets with very long tails and nodes with no neighbors in the graph. To this end,
Normalized Number of Nodes
101
102
103
104
No de
D eg
re es
cora citeseer pubmed arxiv chameleon
actor squirrel wisconsin cornell texas
tures, we develop a metric called Feature-Contribution Ratio (FCR) that disentangles the graph data into node features and the neighborhood structure. We then build submodules for each part and search for the best architecture. Besides selecting the optimal model architecture, we leverage FCR to provide a measure of importance of the node feature compared to the neighborhood structure, quantifying the difficulty of learning truly inductive GNNs. We summarize our key contributions as follows:
• To generalize better to tail and SCS nodes, we design the Cold Brew framework to distill a GNN teacher into an MLP student. We improve over GNN models by adding the node-wise Structural Embedding (SE) to the Cold Brew’s teacher GNN to strengthen the expressiveness of the teacher GNN model. We designed a novel mechanism for the MLP student to discover the “latent/virtual neighborhoods” when they are missing, and perform message passing as its teacher model does.
• We propose Feature-Contribution Ratio (FCR): a new metric for graph datasets that quantifies the contribution of node features w.r.t. the adjacency structure in the dataset for a specific downstream task. FCR indicates the difficulty in generalizing to tail and cold-start nodes in a given dataset. We also leverage FCR as a principled “screen process” to select the best model architecture for both the GNN teacher and the MLP student in Cold Brew.
• Through extensive experiments on several public datasets as well as a proprietary ecommerce graph dataset, we validate the effectiveness of Cold Brew in cold-start generalization. We further uncover the contribution ratio of node features in node prediction tasks with FCR.

heading: 1.1 PROBLEM SETUP
text: GNNs effectively learn the representations of two components in graph data: they process node features by distributed node-wise transformations and process adjacency structure by localized neighborhood aggregations. For the first component, GNNs apply shared feature transformations to all nodes regardless of the neighborhoods, while for the second component, GNNs use permutationinvariant aggregators to collect neighborhood information.
We take the node classification problem in this paper for ease of exposition, and the proposed method can be trivially adapted to semi-supervised/unsupervised settings. We denote the graph data of interest by G with node set V, |V| = N . Each node possesses a din−dimensional feature and a
dout−dimensional label (either dout classes or a continuous vector in the case of regression). Let X0 ∈ RN×din and Y ∈ RN×dout be the matrices of node features and labels, respectively. Let Ni be the neighborhood of node i ∈ [N ]. As is common with modern, large-scale graphs, |Ni| is small for several nodes in the graph, which we refer to as tail nodes. For a number of nodes, |Ni| = 0, and we refer to these nodes as cold-start nodes.
A traditional GNN learns representations for the ith node at the lth layer as a function of the node representation itself and its neighborhoods’ representations, at the (l − 1)th layer:
xli := f ( {xl−1i }, {x l−1 j }j∈Ni ) (1)
where f(·) is a general function that applies node-wise transformation on node xl−1i and aggregates information of its neighborhood {xl−1j }j∈Ni to obtain the final node representation. Given i’s input features x0i and its neighborhood Ni, one can use (1) to obtain its representation and predict yi, making these models inductive.
We are interested in improving the performance of these GNNs on a set of tail and cold-start nodes, whereNi for node i is either unreliable1 or absent. In these cases, applying (1) will yield a suboptimal node representation, since {xl−1j }j∈Ni will be unreliable or empty at inference time.

heading: 2 RELATED WORK
text: GNNs learn by aggregating neighborhood information to learn node representations (Kipf & Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017; Xu et al., 2018a; Wu et al., 2019; Klicpera et al., 2018). Inductive variants of GNNs such as GraphSAGE (Hamilton et al., 2017) require initial node features as well as the neighborhood information of each node to learn the representation. Most works on improving GNNs have focused on learning better aggregation functions, and methods that can work when the neighborhood is absent or noisy have not been sufficiently exploited, except two very recent or concurrent works (Hu et al., 2021; Zhang et al., 2021).
In the context of cold start, (Hao et al., 2021) and (Ding et al., 2021) employ a transfer learning approach. (Yang et al., 2021) proposes a knowledge distillation for GNN, while (Chen et al., 2020b) proposes a self-distillation approach. In all the above cases, the models need full knowledge of the neighbors of the cold-start nodes in question and do not address the case of noisy or missing neighborhoods. Another possible solution is to directly train an MLP that only take node features. (Hu et al., 2021) proposes to learn graph embeddings with only node-wise MLP, while using contrastive loss to regularize the graph structure.
Some previous works have studied the relation between node feature similarity and edge connections and studied their influence on the selection of appropriate graph models. (Pei et al., 2020) proposed the homophily metric that categorizes the graphs into assortative and disassortative classes. (Wang et al., 2021) dissected the feature propagation steps of linear GCNs from a perspective of continuous graph diffusion and analyzed why linear GCNs fail to benefit from more propagation steps. (Liu et al., 2020a) further studied the influence of homophily on model selection and proposed a non-local GNN.

heading: 3 STRICT COLD START GENERALIZATION
text: We now address the problem of generalization to the tail and cold-start nodes, where the neighborhood information is missing/noisy (Section 1). A naive baseline is to train an MLP to map node features to labels. However, such method disregards all graph information, and we show via our FeatureContribution Ratio and other experimental results that for most assortative graph datasets, the node-wise MLP approach is suboptimal.
The key idea of our framework is the following: the GNN maps node features into a d-dimensional embedding space, and since the number of nodes N is usually much bigger than the embedding dimensionality d, we end up with an overcomplete set for this space using the embeddings as the basis. This implies the possibility that any node representation can be cast as a linear combination of K N existing node representations. Our aim will be to train a student model that can accurately discover the combination of the best K existing node embeddings of a target isolated node. We call
1For example, a user with only one movie watched or an item with too few purchases.
this procedure latent/virtual neighborhood discovery, which is equivalent to using MLPs to “mimic” the node representations learned by the teacher GNN.
We adopt the knowledge distillation procedure (Yang et al., 2021; Chen et al., 2020b) to improve the quality of the learned embeddings for tail and cold-start nodes. We use a teacher GNN model to embed the nodes onto a low-dimensional manifold by utilizing the graph structure. Then, the job of the student is to learn a mapping from the node features to this manifold without knowledge of the graph that the teacher has. We further aim to let the student model generalize to SCS cases where the teacher model fails, beyond just mimicking the teacher as standard knowledge distillation does.

heading: 3.1 THE TEACHER MODEL OF COLD BREW: STRUCTURAL EMBEDDING GNN
text: Consider a graph G. For a Graph Convolutional Network with L layers, the l-th layer transformation can be written as2: X(l+1) = σ(ÃX(l)W(l)), where Ã is the normalized adjacency matrix, Ã = D−1/2AD−1/2, D is the diagonal degree matrix and A is the adjacency matrix. X(l) ∈ RN×d1 is the node representations in the l-th layer, W(l) ∈ Rd1×d2 is the feature transformation matrix, where the values of d1/d2 depend on layer l: (d1, d2) = (din, dhidden) for l = 0, (dhidden, dhidden) for 1 ≤ l ≤ L− 2, and (dhidden, nclasses) for l = L− 1. σ(·) = is the nonlinear functions applied to each layer, (e.g. ReLU). Norm(·) refers to an optional batch or layer normalization.
GNNs typically suffer from oversmoothing (Oono & Suzuki, 2020; Li et al., 2018; NT & Maehara, 2019), making all the node representations similar to each other. This is harmful not only for the GNN itself, but also to the student model that looks to mimic the GNN. Inspired by the positional encoding in Transformers (Vaswani et al., 2017), we train the teacher GNN to additionally learn a set of node embeddings which we term the Structural Embedding (SE). SE learns to incorporate additional information (such as node labels in the case of semi supervised learning) through gradient backpropagation. The existence of SE avoids the oversmoothing issue in GNNs: the transformations applied to different nodes are no longer the same for each nodes, since the SE of each node is different, which is part of the feature transformation function. Note that this could be of independent interest to practitioners who train and study GNNs.
Specifically, for each layer l, 0 ≤ l ≤ L − 1, the Structural Embedding is a learnable matrix E(l), and the SE-GNN layer forward pass can be written as:
X(l+1) = σ ( Ã ( X(l)W(l) + E(l) )) ,X(l) ∈ RN×d1 ,W(l) ∈ Rd1×d2 ,E(l) ∈ RN×d2 (2)
Remark 1: Note that SE is not the same as the bias term in traditional feature transformation X(l+1) = σ ( Ã ( X(l)W(l) + b(l) )) , where for the bias b ∈ RN×d2 the rows are copied/shared
across all nodes. In contrast, we have a different structural embedding for every node.
2Compared to Equation (1), multiplication by Ã plays the role of aggregating both {xi} and {xj}i∈Ni .
Remark 2: SE is also unlike traditional label propagation (LP) (Iscen et al., 2019; Wang & Leskovec, 2020; Huang et al., 2020b). LP encodes label information through iterating E(t+1) = (1− α)G + αÃE(t), where G is a one-hot encoding of ground truth for training node classes and zeros for test nodes, and 0 < α < 1 is the portion of mixture at each iteration.
SE-GNN enables node i to learn to encode the self and neighbors’ label information3 into its own node embedding through Ã. We use the Graph Convolutional Networks (Kipf & Welling, 2016), combined with other building blocks proposed in recent literature including: (1) initial/dense/jumping connections; and (2) batch/pair/node/group normalization, as the backbone of Cold Brew’s teacher GNN. More details are described in Appendix A. We also apply a regularization term to the loss function, yielding the following loss function:
loss = CE(X (L) train,Ytrain) + η‖E‖ 2 2 (3)
where X(L)train is the model’s embedding at the L-th layer, which is exactly the model’s output, CE(X
(L) train,Ytrain) is the Cross Entropy between the model output X (L) train and the ground truth
Y on the training set, and η is the coefficient (grid-searched for different datasets in practice). The Cross-Entropy loss can be replaced by any other appropriate loss depending on the task.

heading: 3.2 THE STUDENT MLP MODEL OF COLD BREW
text: We design the student to be composed of two MLP modules. Given a target node, the first MLP module imitates the node embeddings generated by the GNN teacher. Next, given any node, we find a set of virtual neighbors of that node from the graph. Finally, the second MLP attends to both the target node and the virtual neighborhood and transforms them into the embeddings of interest.
Suppose we would like to obtain the embedding of an potentially isolated target node i, given only its feature xi. From the teacher GNN, at each layer l, we have access to two sets of node embeddings: X(l)W(l) and E(l). Denote Ē as the desired embeddings that the teacher GNN pass over to the student MLP. We offer two options for Ē: it can be the final output of the teacher GNN, in this case, Ē ∈ RN×dout := X(L), or optionally, it can be the concatenation of all intermediate results of the teacher GNN, similar to (Romero et al., 2014): Ē ∈ RN×(dhidden∗(L−1)+dout) := X(L) ⋃L−1 l=0 (E (l) + X(l)W(l)), where ⋃
is the concatenation of matrices at the feature dimension (second dimension). Ē acts as the target for the first MLP module and the input to the second MLP module.
The first MLP learns a mapping from the input node features X(0) to Ē, that is ξ1 : x (0) i → ei for node i, ei = Ē[i, :]. Then, we discover the virtual neighborhood by applying an attention-based aggregation of the existing embeddings in the graph, before linearly combining them:
ẽi = softmax(ΘK(eiĒ >))Ē (4)
where ΘK(·) is the top-K hard thresholding operator: for z ∈ R1×N : [ΘK(z)]j = zj if zj is among the top-K largest elements of z, and ΘK(z)j = −∞ otherwise. Finally, the second MLP learns a mapping ξ2 : [xi, ei]→ yi, where yi = Y[i, :] is the ground truth for node i.
Equation (4) first selects K nodes from the N nodes that the teacher GNN was trained on via the hard thresholding operator. ẽj is then a linear combination of K node 4 embeddings. Thus, every sample whether or not seen previously while training the GNN can be represented as a linear combination of these representations. The MLP ξ2(·) maps this representation to the final target of interest. Thus, we decompose every node embedding as a linear combination of an (overcomplete) basis.
The training of ξ1(·) is by minimizing the mean squared error over the non-isolated node in the graph (mimicing the teacher’s embeddings), and the training of ξ2(·) is by minimizing the cross entropy (for node classification task) or mean squared error (for node regression task) on the training split of the tail and isolated part of the graph. An illustration of SE-MLP’s inference procedure for the isolated nodes is shown in Fig. 2. When the number of nodes is large, the ranking procedure involved in ΘK(·) can be pre-computed after training the first part and before training the second part.
3This will be inferred in the case of labels missing. 4We abuse terminology here since E contains node and structural embeddings from multiple layers

heading: 3.3 MODEL INTERPRETATION FROM A LABEL SMOOTHING PERSPECTIVE
text: We cite Theorem 1 in (Wang & Leskovec, 2020): Suppose that the latent ground-truth mapping from node features to node labels is differentiable and L-Lipschitz. If the edge weights aij approximately smooth xi over its immediate neighbors with error i, i.e., xi = 1dii Σj∈Naijxj + i, then the aij also approximately smooth yi to bound within error |yi− 1dii Σj∈Niaijyj | ≤ L|| ||2 + o(maxj∈Ni(||xj − xi||2)), where o(·) denotes a higher order infinitesimal.
This theorem indicates that the errors of the label predictions are determined by the difference of the features after neighborhood aggregation: if i is large, then the error in the label prediction is also large, and vice versa. However, with structural embedding, each node i also learns an independent embedding Ē[:, i] during the aggregation, which changes 1dii Σj∈Naijxj + i into 1 dii
Σj∈Naijxj + Ē[:, i]+ i. Deduced from this theorem, the structural embedding Ē is important for the teacher model: it allows higher flexibility and expressiveness in learning the residual difference between nodes, and hence the error i can be are lowered if Ē is properly learned.
From this theorem, one can also see the necessity of introducing neighborhood aggregations like the Cold Brew’s student model. If one directly applies MLP models without neighborhood aggregation, the i turns out to be non-negligible, leading to higher losses in the label predictions. However, Cold Brew introduced the neighborhood aggregation mechanism, so that the second part of the student MLP takes over the aggregation of neighborhood generated by the first MLP. Therefore, Cold Brew eliminates the above residual error even in the absence of the actual neighborhood.

heading: 4 MODEL SELECTION AND GRAPH COMPONENT DISENTANGLEMENT WITH FEATURE-CONTRIBUTION RATIO
text: We now discuss Feature Contribution Ratio (FCR): a metric to quantify the difficulty of learning representations under the truly inductive cold start case, and a hyperparameter optimization approach to select the best suitable model architecture that helps tail and cold start generalization.
As conceptually illustrated in Figure 2, there are four atomic components contributing to the learned embedding of node i in the graph: 1. the label of i (self-label); 2. the label of neighbors of i (neighborlabels); 3. the features of i (self-feature); 4. the features of neighbors of i (neighbor-features). To quantize the SCS generalization difficulty, we divide these four components into two submodules to disentangle the contributions of the node features with respect to the adjacency structure of the graph dataset, and quantize it based on the assumption that the SCS generalization difficulty is propotional to the contribution ratio of the node features.
We posit that a submodule that learns accurate node representations must include the node’s (self) label, so that training can be performed via backpropagation. What remains is to use the label with other atomic components to construct two specialized models that each make use of only the node features or the adjacency structure. For the first submodule, we build an MLP that maps the selffeatures to self-labels, ignoring any neighborhood information present in the dataset. For the second submodule, we adopt a Label Propagation (LP) method (Huang et al., 2020a)5 to learn representations from self- and neighbor-labels. This model ignores any node feature information.
With the above two submodules, we introduce the Feature-Contribution Ratio (FCR) that characterizes the relative importance of the node features and the graph structure. Specifically, for graph dataset G, we define the contribution of a submodule to be the residual performance of the submodule compared to a full-fledged GNN (e.g., Equation (1)) using both the node feature as well as the adjacency structure. Denote zMLP , zLP , and zGNN as the performance of the MLP submodule, LP submodule, and the full GNN on the test set, respectively. If zMLP zGNN , then FCR(G) is small and the graph structure is important, and noisy or missing neighborhood information will hurt model performance. Based on this intuition, we build SCR as:
δMLP =zGNN − zMLP , δLP = zGNN − zLP (5a)
FCR(G) =
{ δLP
δMLP+δLP × 100% zMLP ≤ zGNN 1 + |δMLP ||δMLP |+δLP × 100% zMLP > zGNN (5b)
5We ignore the node features and use the label logits as explained in (Huang et al., 2020a).
Interpreting FCR values. For a particular graph G, if 0% ≤ FCR(G) < 50%, it means zGNN > zLP > zMLP , and the neighborhood information in G is mainly responsible for the GNN achieving good performance. If 50% ≤ FCR(G) < 100%, then zGNN > zMLP > zLP , the node features contribute more to the GNN’s performance. If FCR(G) ≥ 100%, then zMLP > zGNN > zLP , and the node aggregation in GNNs can actually lead to reduced performance compared to pointwise models. This case usually happens for some disassortative graphs (the majority of neighborhoods hold different labels than the center node), e.g. as observed by (Liu et al., 2020a) .
Integrate FCR as a tool to design teacher and student models. For some graph datasets and models, the SCS generalization can be challenging without neighborhood information (i.e, zGNN > zLP > zMLP ). We hence consider FCR as a principled “screening process” to select model architectures for both teacher and student, that own the best inductive bias for SCS generalization.
To achieve this, during the computation of FCR, we perform exhaustive grid search of the architectures (residual connection types, normalization, hidden layers, etc.) for the MLP, LP, and GNN modules, and pick the best-performing variant. Detailed definition of the search space can be found in Appendix A. We treat this grid search procedure as a special case of architecture selection and hyperparameter optimization for Cold Brew. We observe that FCR is able to identify the GNN and MLP architectures that are particularly friendly for SCS generalization, improving our method design.
In experiments, we observe that different model configurations are favored by different datasets, and we use the found optimal teacher GNN and student MLP architectures to perform Cold Brew. More detailed discussions will be presented in section 5.3

heading: 5 EXPERIMENTS AND DISCUSSION
text: In this section, we first evaluate the FCR for several commonly used graph datasets to ascertain how well GNNs trained on them can generalize to tail and cold-start nodes. We also compare it to the the graph homophiliy metric β proposed in (Pei et al., 2020). Next, we apply Cold Brew to these datasets and compare its generalization ability to baseline graph-based as well as purely pointwise models on these datasets. We also show results on proprietary industry datasets.

heading: 5.1 DATASETS AND SPLITS
text: We first detail the datasets used in this paper. We perform studies on several open-source datasets, together with four proprietary datasets. The proprietary E-commerce datasets, E-comm 1/2/3/4, refers to graphs subsampled from anonymized logs of an e-commerce store. They are sampled so as to not reflect the actual raw traffic distributions, and results are provided with respect to a baseline model for these datasets. The different datasets refer to different product subsets, and the labels indicate product categories that we wish to determine. Node features are text embeddings obtained from a fine-tuned BERT model. We show FCR values for the public datasets and exhaustively evaluate the proposed Cold Brew as well as several baselines for five public datasets and the proprietary datasets. The statistics of the datasets are summarized in Table 1.
We create specific training and test splits of the datasets in order to specifically study the generalization ability of Cold Brew to tail and cold-start nodes. In the following tables, the head data corresponds to the top 10% highest degree nodes in the graph, and the subgraph that they induce. The tail data corresponds to the 10% nodes in the graph with lowest (non-zero) degree, and the subgraph that they induce. All the zero degree nodes are in the isolation data. For datasets that don’t have isolated nodes, we manually remove edges from 10% lowest degree nodes. The Overall data refers to the training/test splits without distinguishing head/tail/isolation.

heading: 5.2 FCR EVALUATION
text: In Table 2, the top half presented the FCR results together with the homophily metric β in (Pei et al., 2020) (Equation 6). The below half uncovered the different prediction quality for the head and the tail nodes. As can be seen from the table, as an indicator of the tail generalization difficulty, FCR differs among datasets, and is negatively correlated with the homophily metric (with pearson correlation coefficient -0.76). The high absolute correlation value and its negative sign indicate that the more similar the nodes are to their neighborhoods, the more difficult it is to generalize with MLP based models. The evaluations on more datasets (including the datasets where FCR > 100%) are presented in Appendix B.
β(G) = 1|V| ∑ v∈V the number of v’s direct neighbors that have the same labels as v the number of v’s directly connected neighbors × 100% (6)

heading: 5.3 EXPERIMENTAL RESULTS ON TAIL GENERALIZATION WITH COLD-BREW
text: In Table 3, we present the performances of the Cold Brew together with baselines on the tail and the isolation splits, across several different datasets. All models in the table are trained on the overall training subset, and are evaluated on the hold-out test subsets of tail and isolation splits (discussed in section 5.1). The GCN refers to the the best configuration found through FCR-guided grid search (check Appendix A for details), without Structural Embedding. Correspondingly, GCN + SE refers to the best FCR-guided configuration with Structural Embedding, which is the default teacher model of Cold Brew. GraphSAGE refers to (Hamilton et al., 2017), Simple MLP refers to a simple node-wise MLP that has two hidden layers with 128 hidden dimensions, and GraphMLP refers to (Hu et al., 2021). The results for E-commerce datasets are presented as relative improvements to the baseline (each value is the difference w.r.t. the value of the GCN 2 layers on same dataset of the same split), and we do not disclose the absolute numbers due to proprietary reasons.
As shown in Table 3, Cold Brew’s student MLP improves accuracy on isolated nodes by up to +11% on the E-commerce datasets and +2.4% on open source datasets. Cold Brew’s student model handles isolated nodes much better, and it teacher GNN also achieves better performance in the tail split, compared to all other models. Especially, when compared with GraphMLP, Cold Brew’s student MLP shows consistently better performance in most datasets. This can be explained from their different mechanisms: GraphMLP encodes graph knowledge implicitly in the learned weights, while Cold Brew explicitly attends to neighborhoods, even when it is absent. More detailed comparisons can be found in Appendix B.
Splits Models Datasets
Cora Citeseer Pubmed E-comm1
Isolation
GCN 2 layers 58.02 47.09 71.50 − TailGCN 62.04 51.87 72.10 +3.14 Meta-Tail2Vec 61.16 50.46 71.80 +2.80 Cold Brew’s MLP 69.62 53.17 72.33 +7.56
Table 5: Node classification accuracies with other baselines.
We also compared the link prediction tasks to justify the performance under recommendation system settings, and the results are shown in Table 4. The comparison is done over the isolation splits, where the ground truth edges are manually removed, and the models are asked to recover these edges. The baseline model shown in tables are TailGCN (Vetter et al., 1991), Meta-Tail2Vec (Liu et al., 2020b). A comparison over these models on the node classification on the isolation split is provided in Table 5. As observed from the table, cold brew outperformed TailGCN and Meta-Tail2Vec on the isolation split, since both TailGCN and Meta-Tail2Vec explicitely are not zero-shot methods and require explicit neighborhood nodes, hence their performance degrade when the neighborhood is empty and padded by zeros vectors.
There are other interesting observations. First, if the FCR is high (such as Pubmed), then for this dataset the MLP-type models tend to outperform GNN-type models in all splits. Regardless of FCR, for almost all datasets, the MLP-type models outperform the GNN-type models on the isolation split, and a few on the tail split, while the GNN-type models are superior in other splits. Second, the proposed structural embeddings imply a tantalizing potential to alleviate the over-smoothness (Oono & Suzuki, 2020; Li et al., 2018; NT & Maehara, 2019) and bottleneck (Alon & Yahav, 2020) issues observed in deep GCN models. As shown in table Table 6, Cold Brew’s GCN (GCN + SE) significantly outperformed the traditional GCN on 64 layers: the former has 34% test accuracy higher on Cora, 23% higher on Citeseer and similar on others.
Indeed, the improvement over isolation and tail splits (especially the isolation split) comes with a cost: we observed a performance drop for the student MLP model on the head and several other datasets’ tail splits, compared with the naive GCN model. The full performance on other splits are listed in the appendix as a reference. However, the cold-brew specifically targets at the challenging strict cold start issues, as a new compelling alternative for in these cases. Meanwhile in the non-cold-start cases, the traditional GCN models can still be used to obtain good performance. Note that, even on the head splits, the proposed GNN teacher model of Cold Brew still outperformed traditional GNN models. We hence consider as promising future work to adaptively switch between using Cold Brew teacher and student models, based on the current node connectivity degree and tailedness.

heading: 6 CONCLUSION
text: In this paper, we studied the problem of generalizing GNNs to the tail and strict cold start nodes, whose neighborhood information is noisy or missing. We proposed a teacher-student knowledge distillation procedure to better generalize to the isolated nodes. We added an independent set of structural embeddings in GNN layers to to alleviate node over-smoothness, and also proposed a virtual neighbor discovery step for the student model to attend to estimated neighborhood nodes. We additionally established FCR, a metric for quantifying the difficulty of truly inductive representation learning, to optimize our method design. Experiments demonstrated the consistently superior performance of our proposed framework, on several common benchmarks as well as proprietary datasets.

heading: 7 REPRODUCIBILITY CHECKLIST
text: To ensure reproducibility, we use the Machine Learning Reproducibility Checklist v2.0, Apr. 7 2020 (Pineau et al., 2021).
• For all models and algorithms presented, – A clear description of the mathematical settings, algorithm, and/or model. We
clearly describe all of the settings, formulations, and algorithms in Section 5. – A clear explanation of any assumptions. We do not make assumptions. – An analysis of the complexity (time, space, sample size) of any algorithm. We do
not make the analysis. • For all datasets used, check if you include:
– The relevant statistics, such as number of examples. We use widely adopted public graph datasets in Section 5. We provide all the related statistics in Appendix 5.
– The details of train/validation/test splits. We give this information in section 5. – For new data collected,a complete description of the data collection process, such
as instructions to annotators and methods for quality control. We do not collect or release new datasets.
• For all reported experimental results, check if you include: – The range of hyper-parameters considered, method to select the best hyper-
parameter configuration, and specification of all hyper-parameters used to generate results. We provide all details of the hyper-parameter tuning in Section 5.
– The exact number of training and evaluation runs. Ten independent repetitions are conducted for each experiments.
– A clear definition of the specific measure or statistics used to report results. We use the classification accuracy on test-set, which is defined in Section 5.
– A description of results with central tendency (e.g. mean) & variation (e.g. error bars). We report mean for all experiments, as indicated in Section 5.
– The average runtime for each result, or estimated energy cost. We do not report the running time or energy cost.

heading: A SEARCH SPACE DETAILS
text: In the computation of FCR, we include a search space of model hyperparameters for GNN, MLP and LP, in order to find the best suitable configurations for distillation.
For GNN model, we take GCN as a backbone and performed grid search over the number of hidden layers, whether it has structural embedding or not, the type of residual connection, and the type of normalization. For the number of hidden layers, we considered 2, 4, 8, 16, 32, and 64. For the types of residual connections, we include: (1) connecting to the last layer (Li et al., 2019a; 2018), (2) initial connection connecting to the initial layer (Chen et al., 2020a; Klicpera et al., 2018; Zhang et al., 2020), (3) dense connection connecting to all the preceding layers (Li et al., 2019a; 2018; 2020; Luan et al., 2019), and (4) jumping connection combining all all the preceding layers only at the final graph convolutional layer (Xu et al., 2018b; Liu et al., 2020b). For the types of normalizations, we grid search over: batch normalization (BatchNorm) (Ioffe & Szegedy, 2015), pair normalization (PairNorm) (Zhao & Akoglu, 2019), node normalization (NodeNorm) (Zhou et al., 2020b), mean normalization (MeanNorm) (Yang et al., 2020), and differentiable group normalization (GroupNorm) (Zhou et al., 2020a). For types of graph dropout methods, we include Dropout (Srivastava et al., 2014), DropEdge (Rong et al., 2020), DropNode (Huang et al., 2020c), and LADIES (Zou et al., 2019).
For the architecture design for Cold Brew’s MLP, we conducted hyperparameter search over the number of hidden layers, the existence of residual connection, the hidden dimensions, and the optimizers.
The number of hidden layers is searched over (2, 8, 16, 32). The number of hidden dimensions is searched over (128, 256). The optimizer is searched over (Adam(lr=0.001) Adam(lr=0.005), Adam(lr=0.02), SGD(lr=0.005))
For the Label Propagation, we conducted hyperparameter search over number of propagations, propagation matrix type, and the mixing coefficient α (Huang et al., 2020a). The number of propagations is searched over (10, 20, 50, 100, 200). The propagation matrix type is searched over adjacency matrix or normalized Laplacian matrix. The mixing coefficient α is searched over (0.01, 0.1, 0.5, 0.9, 0.99).
The best GCN, MLP, and LP configurations are reported in Tables 7, 8, and 9, respectively.

heading: B THE PERFORMANCE ON ALL SPLITS OF THE DATA
text: The performance evaluations on all splits are listed in Table 10. The FCR evaluation on more datasets are presented in Fig 11.
C VISUALIZING THE LEARNED EMBEDDINGS
Figure 3 visualizes the last-layer embeddings of different models after t-SNE dimensionality reduction. In the figure, colors denotes node labels and all nodes are marked as dots, with isolation subset nodes additionally marked with ‘x’s and the tail subset additionally marked with triangles. Although the GCN model did a decent job in separating different classes, a significant portion of the tail and isolation nodes fall into wrong class clusters. Cold Brew’s MLP is much better discriminative in the tail and isolation splits.
Table 10: The performance comparisons on different splits of different datasets.
Splits Metrics/Models Open-Source Datasets Proprietary Datasets
Cora Citeseer Pubmed Arxiv Chameleon E-comm1 E-comm2 E-comm3 E-comm4
Isolation
GNNs GCN 2 layers 58.02 47.09 71.50 44.51 57.28 − − − −GraphSAGE 66.02 51.46 69.87 47.32 59.83 +3.89 +4.81 +5.24 +0.52 MLPs Simple MLP 68.40 53.26 65.84 51.03 60.76 +5.89 +9.85 +5.83 +6.42GraphMLP 65.00 52.82 71.22 51.10 63.54 +6.27 +9.46 +5.99 +7.37 Cold Brew GCN + SE 2 layers 58.37 47.78 73.85 45.20 60.13 +0.27 +0.76 -0.50 +1.22Student MLP 69.62 53.17 72.33 52.36 62.28 +7.56 +11.09 +5.64 +9.05
Tail
GNNs GCN 2 layers 84.54 56.51 74.95 67.74 58.33 − − − −GraphSAGE 82.82 52.77 73.07 63.23 61.26 -3.82 -3.07 -2.87 -6.42
MLPs Simple MLP 70.76 54.85 67.21 52.14 50.12 -0.37 +1.74 -0.13 -0.45GraphMLP 70.09 55.56 71.45 52.40 52.84 -0.33 +1.64 +1.27 +0.80 Cold Brew GCN + SE 2 layers 84.66 56.32 75.33 68.11 60.80 +0.85 +0.44 -0.60 +1.10Student MLP 71.80 54.88 72.54 53.24 51.36 +0.32 +3.09 -0.18 +2.09
Head
GNNs GCN 2 layers 88.68 80.37 85.79 73.35 67.49 − − − −GraphSAGE 87.75 74.81 86.94 70.85 62.08 -4.26 -4.17 -3.50 -7.46
MLPs Simple MLP 74.33 72.00 89.00 56.34 60.82 -16.74 -18.10 -16.73 -16.51GraphMLP 72.45 69.83 89.00 56.65 62.44 -15.96 -18.08 -15.33 -15.41 Cold Brew GCN + SE 2 layers 89.39 80.76 87.83 74.01 70.56 +1.11 +0.47 -0.39 +1.28Student MLP 74.53 72.33 90.33 57.41 61.28 -15.28 -17.42 -17.02 -15.41
Overall
GNNs GCN 2 layers 84.89 70.38 78.18 71.50 59.30 − − − −GraphSAGE 80.90 66.21 76.73 68.33 70.02 -3.09 -3.86 -2.58 -5.48
MLPs Simple MLP 69.02 56.59 73.51 54.89 58.65 -12.69 -12.86 -12.68 -13.16GraphMLP 71.87 68.22 82.03 53.81 57.67 -12.26 -12.01 -10.80 -11.41 Cold Brew GCN + SE 2 layers 86.96 72.44 79.03 71.92 68.51 +0.65 -0.24 -0.77 +1.43Student MLP 72.36 67.54 82.00 54.94 59.07 -11.25 -11.51 -11.55 -11.21
Cora Citeseer Pubmed Arxiv Cham. Squ. Actor Cornell Texas Wisconsin GNN 86.96 72.44 75.96 71.54 68.51 31.95 59.79 65.1 61.08 81.62 MLP 69.02 56.59 73.51 54.89 58.65 38.51 37.93 86.26 83.33 85.42 Label Propagation 78.18 45.00 67.8 68.26 41.01 22.85 29.69 32.06 52.08 40.62 FCR % 32.86 % 63.39 % 76.91% 16.45% 73.61% 141.91% 57.93% 139.04% 171.2 % 108.48 % β(G) % 83% 71% 79% 68% 25% 22% 24% 11% 6% 16%
head− tail(GNN) 4.44 23.98 11.71 5.9 0.24 -6.51 2.22 -4.37 -11.26 -33.92 head− isolation(GNN) 31.01 33.09 15.21 28.81 1.55 -4.85 22.61 -18.68 -24.62 -29.23
Table 11: Above half: FCR and its components, β metric are added as a reference; below half: the performance difference of GNN on the head/tail and head/isolation splits.

Review summaries:
The paper proposes Cold Brew to distill the knowledge of a GNN teacher into an MLP student to handle the tail and cold start generalization problem by using the head part of the graph to guide the discovery of the latent neighborhoods of tail and isolation nodes. The paper also proposes a new metric to measure the contribution ratio of node features w.r.t. the adjacency structure. The experiments on several public datasets and a proprietary e-commerce graph show the effectiveness of the proposed method.

Many real-world graphs have power-law distributions of node degrees and learning the representations of nodes with few or even no connections may only depend on their attributes. This paper studies the problem of learning good representations of such nodes using inductive GNNs. It proposes a new method to generalize GNNs better for tail nodes compared to pointwise and graph-based models using a distillation approach. A metric, feature contribution ratio, has been proposed in quantifying the contribution of nodes' features in predicting labels. Experiments on several graph datasets demonstrate the effectiveness of the proposed method especially in learning better representations of the tail and isolated nodes.

This paper proposes Cold Brew, a new method for learning cold start node embeddings in graphs. Cold Brew leverages teacher-student framework (knowledge distillation) to handle nodes without neighbors by transferring knowledge of teacher network (learned from head nodes) to student network (for tail or isolated nodes). Experiments are conducted to show that the proposed method outperforms some baseline methods. 

The work focuses on a very practical problem of strict cold start(SCS) recommendations which is a highly prevalent and relevant problem. The author’s main contribution to address the SCS is to use GNN with knowledge distillation – this proposed solution does not have to rely exclusively on the node features. The authors also define an FCR (feature contribution ratio) that can help determine the ideal network architecture – FCR can optimize the model selection which significantly affects the quality of overall system performance.