Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
Authors: Wenqing Zheng
Edward W Huang
Nikhil Rao
Sumeet Katariya
Zhangyang Wang
Karthik Subbian
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Networks
Cold Start
Knowledge Distillation

Abstract: 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.

Published as a conference paper at ICLR 2022
COLD BREW: DISTILLING GRAPH NODE REPRESEN- TATIONS WITH INCOMPLETE OR MISSING NEIGHBOR- HOODS
Wenqing Zheng, Edward W Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang,
Karthik Subbian
(wenqzhen, ewhuang, www.anggnikhilloaee... nikhilsr, waa.khiisskkttueeeee.. katsumee, wzhangwa, ksubbian aamboiaannaamzzz.ccmmm
ABSTRACT
Graph Neural Networks (GNNs) have achieved state-of-the-art performance node classification, regression, and recommendation tasks. GNNs work well when rich and high-quality connections are available. However, their effective- ness 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, called Strict Cold Start (SCS). SCS forces the predie- tion to rely completely on the node's own features. We propose Cold Brew, a teacher-student distillation approach 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 experi- mentally 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 several public benchmark and proprietary e-commerce datasets, where many nodes have ei- ther very few noisy connections. Our source code is available at https; //github. amazon http:/oowrreaarrcac/omaaaaaaeeee
INTRODUCTION
Graph Neural Networks (GNNs) achieve state-of- the-art results across a wide range of tasks such as graph classification, node classification. link predic-
HEAD
Mumber of neightors
tion, and recommendation (Wu et al. 2020 Goyal & Ferrara 2018 Kherad & Bidgoly 2020; Shaikh
TAIL
COLD
al. 2017 Silva et al.) 2010 Zhang al. (019).
Most modern GNNs rely on the principle of message passing aggregate each node's features from its
Number of nodes
(multi-hop) neighborhood (Kipf & Welling 2016
Veličković al.) 2017 Hamilton al.) 2017 Xu
104
Therefore, the success of GNNs relies on the pres- ence of dense and high-quality connections. Even inductive GNNs Hamilton et al. (017)) learn func- tion of the node feature and the node neighborhood, which requires the neighborhood to be present dur- ing inference.
et al. 20188| Wu et al. 2019 Klicpera et al. (2018).
Node Digroes
2.0
pusmed
sou
wiscorsin
camell
100"
chammlesn
tosts
202
Normalized Number of Nodes
Figure 1: Top: Graph nodes may have power-law ("long-tail") connectivity distribution, with large fraction nodes (yellow) having few to no neigh- bors. Bottom: Long-tal tail distributions in real-world datasets, making modern GNNs fail to generalize to the tail/cold-start nodes.
A practical barrier for widespread applicability of GNNs arises from the long-tail node-degree distribu- tion existing in many large-scale real-world graphs. Specifically, the node degree distribution is power law in nature, with majority of nodes having very
few connections (Hao et al. [02T]] Ding et al., 202I]] Lam et al. 2008 Lu et al. 2020). Figure (top)
illustrates long-tail distribution, accompanied with the statistics of several public datasets (bottom).

---

Published as a conference paper at ICLR 2022
Many information retrieval and recommendation applications face the scenario of Strict Cold Start (SCS) (Li et al. 2019b Ding et al. 202T). wherein some nodes have no edges connected. Predicting for these nodes admittedly even more challenging than the tail nodes in the graph. In these cases, existing GNNs fail to perform well due to the sparsity or absence of the neighborhood.
In this paper, we develop GNN models that have 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, industry-scall datasets with very long tails and many orphaned nodes. To this end, we adopt the teacher-student knowledge distillation procedure (Yang et al. 2021; Chen et al.) 2020b) and propose Cold Brew to distill the knowledge of a GNN teacher into multilayer perceptron (MI.P) student.
The Cold Brew framework addresses two key questions: (1) how we efficiently distill the teacher's knowledge for the sake of tail and cold-start generalization, and (2) how can a student make use of this knowledge. We answer these two questions by learning latent node-wis embedding using knowledge distillation, which both avoids "over-smoothness" (Oono & Suzuki, 2020) Li et al. 2018) NT & Machara 2019) and discovers latent neighborhoods. which are missing for the SCS nodes. Note that in contrast to traditional knowledge distillation (Hinton et al. (015). our aim is not to train simpler student model perform as well as the more complex teacher. Instead, we aim to train a student model that is better than the teacher in terms of generalizing to tail or SCS samples.
In addition, to help select the cold-start friendly model architectures, we develop a metric called Feature Contribution Ratio (FCR) that quantifies the contribution of node features with respect the adjacency structure in the dataset for specific downstream task. FCR indicates the difficulty level in generalizing to tail and cold-stan nodes and guides our principled selection of both teacher and student model architectures in Cold Brew. We summarize our key contributions as follows:
To generalize better to tail and SCS nodes, we design the Cold Brew knowledge distillation framework: we enhance the teacher GNN by appending the node-wise Structural Embedding (SE) to strengthen the teacher's ' expressiveness, and design a novel mechanism for the MLP student to rediscover the missing "latent/virtual neighborhoods," on which it can perform message passing.
We propose Feature Contribution Ratio (FCR), which quantifies the difficulty in generalizing to tail and cold-start nodes. We leverage FCR in a principled "screening process" to select the best model architectures for both the GNN teacher and the MLP student.
As the existing GNN studies only evaluate on the entire graph and do not explicitly evaluate head/tail/SCS,,
uncover the hidden differences of head/taiL/SCSS by creating bespoke train/test splits. Extensive experiments on public and proprietary e-commerce graph datasets validate the effectiveness of Cold Brew in tail and cold-start generalization.
1.1
PROBLEM SETUP
GNNs effectively learn node representations using two components in graph data: they process node features through distributed node-wise transformations and process adjacency structure through localized neighborhood aggregations. For the first component, GNNs apply shared feature trans- formations to all nodes regardless of the neighborhoods. For the second component, GNNs use cormuutationinvariiin aggregators to collect neighborhood information.
We take the node classification problem in the sequel for the sake of simplicity. All our proposed methods can be easily adapted to other cemi-supervised or unsupervised problem settings, which we show in Section 5 We denote the graph data of interest by & with node set V. | = N. Each node possesses a d dimensional feature and dout- dimensional label (either dout classes or continuous vector in the case of regression). Let X xdin and Y E R xdout be the matrices of node features and labels, respectively. Let Ag be the neighborhood of the i-th node, 0 < i < N. In large-scale graphs. [M,] is often small for a (possibly substantial) portion of nodes. We refer to these nodes as tail nodes. Some nodes may have [M]] = 0, and we refer to these extreme cold start cases as isolated nodes.
classical GNN learns representations for the 5th node at the 1th layer as a function of its representa- tion and its neighborhood's representations at the (I th layer: of S (fot 1) L beNs)
2

---

Published as a conference paper at ICLR 2022
where f()) is general function that applies node-wise transformation on node x!- and aggregates information of its neighborhood {2)) (n/-") "5="jex;; JjeN; to obtain the final node representation. Given i's input features x and its neighborhood Nr, one can use T to obtain its representation and predict y/, making these models inductive.
We are interested in improving the performance of these GNNs on set of tail and cold-start nodes, where N₁ for node i is either unreliable or absent. In these cases, applying (I) will yield a suboptimal node representation, since { [e)=")ee, JJEA, will be unreliable or empty at inference time.
2
RELATED WORK
GNNs learn by aggregating neighborhood information to learn node representations (Kipf & Welling
2016
Veličković et al. 2017; Hamilton et al.) 2017 Xu et al. 2018a Wu et al. 2019; Klicpera et al.
Inductive variants of GNNs such as GraphSAGE: (Hamilton et al.; (017) 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 recent concurrent works (Hu et al. 2021 Zhang et al. 202I).
2018
In the context of cold start, (Hao et al., 2021 and (Ding et al. 2021 employ a transfer learning approach. (Yang et al. (021)) proposes a knowledge distillation approach for GNN, while (Chen 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 to directly train an MLP that only takes node features. (Hu et al. (02II) 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 how that influences the selection of appropriate graph models. (Pei et al. 2020) proposed the homophily metric that categorizes graphs into assortative and disassortative classes. (Wang et al.. 2021) dissected the feature propagation steps of linear GCNs from 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 model selection and proposed a non-local GNN.
STRICT COLD START GENERALIZATION
We now address the problem of generalization to the tail and cold-start nodes, where the neighborhood information missing/noisy (Section [T. A naive baseline is to train an MLP map node features to labels. However, such method would disregard all graph information, and we show via our Feature Contribution 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 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 linear combination of K < N existing node representations. Our aim will be to train student model that can accurately discover the combination of the best K existing node embeddings of a target isolated node. We call 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 teacher GNN model to embed the nodes onto a low-dimensional manifold by utilizing the graph structure. Then, the goal of the student is to learn 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.
For example, a user with only one movie watched item with too few purchases.
3

---

Published as a conference paper at ICLR 2022
Cold Start Setting
Cold Brew Architecture
Self-Label Node
Meighbor Labals Node:
Node Feature
Node Tralum
MIP1:
Predietion
Adjecency Stuccare
Normal Case Cold Start Case
x al alEjan 9pz(W))
L GCN layers
Graph embeddsings from teacher
Latent
Neighbers
Node feature
MLP2:
Aicoonic Stratuure
Target
Agprogated fcatures
Target
(Estinate))
3. Self-Foature of Node i 4. Neighbor Foaturrrr-- of Node
(a) The teacher-student knowledge distillation of the Cold Brew framework under cold-start setting.
(b) Four GNN atomic components in deciding GNN's output, which are used for FCR analysis.
Figure 2: (a): The proposed Cold Brew framework. In normal case (left upper). GNN relies on both node feature and adjacency structure to make prediction. In cold start case (left lower) when the adjacency structure is missing, the cold brew student model first estimate the adjacency structure, then use both node fcature and adjacency structure to make prediction. The "SE" (right) is the structural embedding learned by Cold Brew's teacher GNN. (b): Four atomic components deciding the GNN embeddings of node i. Our proposed FCR metric disentangles them into two models: the MLP that only considers Part and Part 3, and label propagation that only considers Part I and Part 2.
3.1 THE TEACHER MODEL OF COLD BREW: STRUCTURAL EMBEDDING GNN
Consider graph G. For a Graph Convolutional Network with layers, the 1-th layer transformation o (O))). where Á is the normalized adjacency matrix, A D-1/2AD 1/2 D is the diagonal degree matrix, and A the adjacency matrix. X E R Nxx is the node representations in the I-th layer, W(!)) E RR xd2 is the feature transformation matrix, where the values of d1 d2 depend on layer I: (d1, d2) = (din, dhidden) for / = O. (driddens dhsdden) for (-)) = is the nonlinear functions applied to each layer, (c.g., ReLU). N Norm(-) refers to an optional batch or layer normalization.
can be written as x (I+1)
1 < I L 2, and (dhidden Teclasses) for | L
GNNs typically suffer from oversmoothing (Oono & Suzuki 2020 Li et al., 2018 NT & Maehara 2019), i.e., node representations become too similar each other. Inspired by the positional encoding in Transformers (Vaswani et al., (2017). we train the teacher GNN to learn an additional set of node embeddings that can be appended, which we term the Structural Embedding (SE). SE learns to incorporate extra information besides original node features (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 every node since the SE each node different and participates in the feature transformation. This can be of independent interest to GNN researchers.
Specifically, for each layer 0 < 1. 5 I, 1, the Structural Embedding takes the form of a learnable matrix E() and the SE-GNN layer forward pass can be written as:
x (1+1) = a Á x ( + E")) x()
Nxd: ( Rddidd E Nxda
Remark 1: Note that SE is not the same as the bias term in traditional feature transformation ((+1) a (Ax()(()) b()) in the bias b Nxd, the rows copied/shared across all nodes. In contrast, we have a different structural embedding for every node.
Remark 2: SE is also unlike traditional label propagation (LP) (Iscen et al. 2019 Wang & Leskoved 2020 Huang et al. 2020b). LP encodes label information through iterating E(F+1) (1 - a G + A where G is a one-hot encoding of ground truth for training node classes and zeros for test nodes, and 0 < < is the portion of mixture at each iteration.
Compared Equation multiplication by À plays the role of aggregating both {..} and { hex.
4

---

Published as a conference paper at ICLR 2022
SE-GNN enables node i to learn to encode the self and neighbors' label information into its node embedding through A. We use the Graph Convolutional Networks (Kipf & Welling 2016). combined with other building blocks proposed in recent litcrature including: (I) initaa/dense/jumping
connections, and (2) hatch/pair/node/grooi normalization as the backbone of Cold Brew's teacher
GNN. More details are described in Appendix [
We also apply a regularization term to the loss
function, yielding the following loss function:
loss = C (L)
train ttrain) + +7 E
(3)
where X X is the model's s embedding at the I-th layer, C train: train) is the Cross Entropy frain
(L)
loss between the model output x and the ground truth Y on the training set, and 1 is a regularization coefficient (grid-searched for different datasets in practice). The Cross- Cross-Entropy loss can be replaced by any other appropriate loss depending on the task.
3.2 THE STUDENT MLP MODEL OF COLD BREW
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, second MLP attends to both the target node and the virtual neighborhood and transforms them into the embeddings of interest.
Suppose we would like obtain the embedding of a potentially isolated target node given only its feature X,. From the teacher GNN, at each layer I, we have access to two sets of node embeddings: x (!)) and E Denote as the embeddings that the teacher GNN passes over to the student MLPs. We offer two options for E: it can be the final output of the teacher GNN (in this case, E E TR N xxgue x()),, it can be the concatenation of all intermediate results of the teacher GNN, similar to (Romero al. 2014): E R Nx (dasdden ([=-))douu) (1) U (E(!) + x W()), where V is the concatenation of matrices at the feature dimension (second dimension). E acts the target for the first MI. and also the input to the second MI..
The first MLP learns a mapping from the input node features X (9) to E, i.c., for node é, = (x. ())) where é; is trained with supervised learning to reproduce Elt, Then, discover the virtual neighborhood by applying an attention-based aggregation of the existing embeddings in the graph before linearly combining them:
é, s0ftmar(Ox( ))E
(4)
where θx ()) is the top- K hard thresholding operator: for E II [Ox (2)l, = 2j if žj is among the top-K K largest elements of 2, and θ xx)) -o otherwise. Finally, the second MLP learns mapping & [x,, e.] + ys. where y, = Yli. :] is the ground truth for node i.
Equation first selects nodes from the N nodes that the teacher GNN was trained on via the hard thresholding operator. é, is then linear combination of K node 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 (.).) 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 (-) occurs by minimizing the mean squared error over the non-isolated nodes in the graph (mimicking the teacher's embeddings), and the training of (2(+) occurs by minimizing the cross entropy (for the node classification task) or mean squared error (for the 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 shown in Figure 2 When the number of nodes large, the ranking procedure involved in Ox (-) can be precomputed after training the first part and before training the second part.
3.3 MODEL INTERPRETATION FROM LABEL SMOOTHING PERSPECTIVE
We quote Theorem in (Wagg& & Leskovec 2020): Suppose that the latent ground-truth mapping from node features to node labels differentiable and L-LLischitzz If the edge weights asj approximately
"This will he inferred in the case of missing labels. We abuse terminology here since E contains node and structural embeddings from multiple layers.
5

---

Published as a conference paper at ICLR 2022
smooth x, over its immediate neighbors with ervor e,, L..,, x, 2. EjENOiJX; t then the asj also di approximately smooth y/ to bound within error 1y; 1 MeN, I Ll|e|l2 + o(maxjeN; (||x;
x; %a]12), where ol-) denotes 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 c, is large, then the error in the label prediction is also large, and vice versa. However, with structural embeddings, each node also learns an independent embedding El;, i] during the aggregation, which changes J
e into di Eje + E(:, 1] + G. 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 E, can be lowered if E is properly learned.
ā.e LjeNaujj;;
From this theorem, one can also see the necessity of introducing neighborhood aggregations like that of the Cold Brew student model. If one directly applies MLP models without neighborhood aggregation, the e, turns out to be non-negligible, leading to higher losses in the label predictions. However, Cold Brew introduces 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.
4 MODEL SELECTION AND GRAPH COMPONENT DISENTANGLEMENT WITH FEATURE CONTRIBUTION RATIO
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 (neighbor- labels); 3. the features of i (sature 4. the features of neighbors of i (neighbor-features) To quantize the SCS generalization difficulty, we first 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. Then, we quantize it based on the assumption that the SCS generalization difficulty is proportional 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 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 self- features 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. 22000a 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. define the contribution of submodule to be the residual performance of the submodule compared to a full-fledged GNN (e.g., Equation (T) using both the node feature as well as the adjacency structure. Denote LP, ALP, and EGNN as the performance of the MLP submodule, LP submodule, and the full GNN on the test set, respectively. If ZMLP < EGNN. 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:
8MPP EGNNN ZMLP: SLP EGNN ZLP
(Sa)
PLP x 100%
ZMLP S NGNN
FCR(G) 1+ BALLP--HEP
SMEP+5LP [0MPll
(5h)
x 100%
ZMLP > ZONN
Interpreting FCR values. For a particular graph G. 0f < FCR(() < 50%, it means AGNN > ZLP > EMLP, and the neighborhood information in G is mainly responsible for the GNN achieving good performance. If 50% < FCR(G)) < 100%, then EGNN > 2MLP > 2LP, and the node features contribute more to the GNN's performance. If FCR(G) 2 100%, then ZMLP EGNN >
We ignore the node features and use the label logits as explained in (Huang al. 2020a).

---

Published as a conference paper at ICLR 2022
2LP, and the node aggregation in GNNs can actually lead to reduced performance compared to pointwise models. This case usually happens for some disassortative graphs, where the majority of neighborhoods hold labels different from that of the center nodes (c.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., 2GNN ALP > 2MLP). 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 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 [ 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 MI. 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 are presented in section 5.3
5 EXPERIMENTS AND DISCUSSION
In this section, we first evaluate FCR by training GNNs on several commonly used graph datasets and observing how well they generalize tail and cold-start nodes. We also compare to the graph homophiliy metric 3 proposed in (Pei et al.) 2020). Next, we apply Cold Brew to these datasets and compare its generalization ability to baseline graph-based and pointwise MLP models these datasets. We also show results on proprietary industry datasets.
5.1 DATASETS AND SPLITS
We perform experiments on five open-source datasets and four proprietary datasets. The proprietary e-commerce datasets, "E-comm 1/2/3/4", refer 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 provided with respect to a baseline model for these datasets. The different number suffixes refer to different product subsets, and the labels indicate product categories that we wish to predict. Node features text embeddings obtained from fine-tuned BERT model. We show FCR values for the public datasets. The statistics of the datasets are summarized in Table
We create training and test splits of the data 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-degres nodes in the graph and the subgraph that they induce. We take the data that corresponds to the bottom 10% of the degree distribution, and artifically remove all the edges emanating from these nodes. We then refer to this set of nodes as the isolation data. The tail data corresponds the 10% nodes in the remaining graph with lowest (non-zero) degree and the subgraph that they induce. All the zero-degree nodes are in the isolation data. The Overall data refers to the training/test splits without distinguishing head/tail/isolatin..
Cora Citeseer Pubmed
Arxiv
Chameleon E c-mmml | E-comm2
E-comm3
E-comm4
Num. of Nodes
2708
3327
19717
169343
2277
4918
29352
319482
793194
Num. of Edges
13264
12431
108365
2315598
65019
104753
1415646
8689910
22368070
Max Degree
169
100
172
13161
733
277
1721
4925
12452
Mean Degree
4.90
3.74
5.50
13.67
28.55
21.30
48.23
27.20
28.19
Median Degree
4
3
6
13
10
21
15
14
Isolated Nodes
3%
3%
3%
3%
6%
5%
5%
6%
Table 1: The statistics of datasets selected for evaluation.
5.2 FCR EVALUATION
In Table 2 the top part presents the FCR results together with the homophily metric / from (Pei et al.,
2020) (Equation 6). The bottom part shows the prediction accuracies for the head and the tail nodes.
7

---

Published as a conference paper at ICLR 2022
As can be seen from the table, FCR differs among datasets and is negatively correlated with the homophily metric (with Pearson correlation coefficient coefficient-O.76.. -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. FCR is thus an indicator of the tail generalization difficulty. Evaluations on more datasets (including the datasets where FCR > 100%) are presented in Appendix
the number of v's direct neighbors that have the same labels as v x 100%
((G)
(6)
I
the number of v's directly connected neighbors
EE
Com
Citescer
Puhmed
Arxiv
Chameleon
ONN MLP
86.96
72.44
75.96
71.34
68.51
69.02
56.59
73.51
54.89
58.65
Label Propagation
67.8
68.26
11.01
FCR
32.96 %
63.39 4
76.91%
16.45%
73.61%
3(57 %
83%
71%
79%
68%
25%
23.88
11.71
33
0.24
lnsod
(GN
31.01
33.09
15:21
28.81
1.55
Table 2: Top part: FCR and its components. The 3 metric added as reference. Bottom part: the performance difference of GNN on the head/tail and head/isolation splits. Here, the "tail/isolation" means the 10% least connected, and isolated nodes in the graph.
5.3 EXPERIMENTAL RESULTS ON TAIL GENERALIZATION WITH COLD BREW
In Table 3 we present the performance of Cold Brew together with baselines on the tail and the
isolation splits, across several different datasets. All the models in the table are evaluated on the
training data, and are evaluated on the tail or isolation splits discussed in section 5. In Table 3 GCN refers to the the best configuration found through FCR- -CR-guided grid search (check Appendix B 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 simple node-wise MLP that has two hidden layers with 128 hidden dimensions, and GruphMLP refers to (Hu et al., 202T}. The results for the e-commerce datasets presented relative improvements to the bascline (each value is the difference with respect to the value of the GCN layers on same datasct of the same split). We do not disclose the absolute numbers due proprietary reasons.
As shown in Table 3 Cold Brew's student MLP improves accuracy isolated nodes by up to +1 1119 1% on the e-commerce datasets and +2.4% on the open-source datasets. Cold Brew's 's student model handles isolated nodes better, and the teacher GNN also achieves better performance on the tail split compared to all other models. Especially when compared with GraphMLP. Cold Brew's student MLP consistently performs better. 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 they are absent. More detailed comparisons can be found in Appendix C
Splix
Marroo/Meeiis
Open Sonrce Dolasets
Proprietary Datasets
Comn
Chirnoer
Pubrrol
Arcic
Chomelonn
Eecemn
Frormm!
Focemme4
GUN 2 byers
20.00
47.09
71.511
41.51
Gasp&SAGE
69.37
47.32
39:53
+3.59
+4.81
43.24
+0.52
Iestation
MLPs
Sinple MLP
GraphMLP
65.34
71.22
51.10
$1.00
03.51
60.76
+9.46
+5.99
45.83
+7.37
Culd Brew
OCN- + SF. byye
Sudtam MLP
09.62
58.17
$3.17
47.78
73,85
72.35
$2.36
45.20
62.25
60.13
+0.27
+7.56
-11.09
+0.76
+3.64
.0.50
+1.20
+8.15
leyers
14.95
67.74
56.33
GaspoSAGE
62.82
73.07
63.23
61.26
3.07
2.87
6642
MLPx
Simple MILP
GraptDLLP
70.09
53.56
67.21
71.45
$2.40
$2.54
50.12
-0.33
+1.64
+1.37
-0:13
+0.50
-1.55
Cold Brew
OCN + SE layen
Student MLP
71.80
84.66
54.38
56.32
75.33
72.56
68.11
53.24
68.80
51.50
+0.85
+0.52
+3.09
+0.44
.0.60
-0.18
+1.10
+2.09
Table 3: The performance comparisons on the isolation and tail splits of different datasets. The full comparisons on pead/tal/isollaiio/vveraa data are the Appendix GCN+SE layers Cold Brew's teacher model. Cold Brew outperforms GNN and other MLP baselines, and achieves the best performance on the isolation splits as well as some tail splits.
8

---

Published as a conference paper at ICLR 2022
Dulasets
Datasels
Sptes
Models
Splis
Models
Curs
Ciiseer
Polenal
Excumi
Coea
Clieserr
Puhmee
E-cmml
GCN layess
34.10
50.41
$1.52
GCN 2 lagers
58,02
47,09
71.50
Iolution
16.11
51.19
-2.18
Isolation
THKOUN
51.87
Nez
36.92
50.90
$1.62
-2.34
Mets-Tail
66.16
90.46
71.80
+2.00
Cold Brew's MLP
44.59
55.14
$4.82
+5.39
Cold Beew's MLP
69.62
$3.17
72.33
+7.56
Table 4: Link prediction Mean Reciprocal Table 5: Node classification accuracies with
Ranks (MRR) on the isolation data. Note that other haselines specifically created to generalize Cold Brew outperforms baselines specifically to the tail. Cold Brew outperforms these meth- built for generalizing to the tail.
ods when edge data is absent in the graph.
We also evaluated the link prediction performance by replacing the node classification loss with the link prediction loss. On the manually created isolation split, the model is asked to recover the ground truth edges which are manually removed. The results are shown in Table 4 The baseline models shown in table are TailGCN (Vetter et al. 1991) and over these models on the node classification on the isolation split provided Table S As observed from the table 4 [nd Cold Brew outperformed TailGCN and Meta-Tain Vei explicitly are not zero-shot methods and require explicit
(Liu et al. 2020b). A comparison
on the isolation split,
since both TailGCN and neighborhood nodes, hence their performance degrades when the neighborhood is empty and padded by zero vectors.
The full performance on other splits are listed in Table in the appendix as a reference. The results across all splits in Table [10] evidence for a few phenomena, for example, the high FCR means that the graph structure does not add too much information for the task at hand. and that GNN type models tend to perform better on the head while MLP type models tend to perform better on the tail/isolation splits. On the other hand, the proposed Structural Embeddings imply a potential to
alleviate the werrssmothhesss (Oono & Suzuki, 2020 Li et al. 2018 NT & Machara 2019) and bottleneck (Alon & Yahav| 2020) issues observed in deep GCN models. As shown in table T Cold Brew's '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.
Finally, 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. However, Cold Brew specifically targets the challenging strict cold start issues, as 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.
Syliss
Monicu/Midela
Open Dutusets
Proprictary Duluseis
Clicseer
Pubmeed
Arsis
Chaneleus
E-comnl
E-coun2
E-comm]
E-coman4
Ovaall
GCN layees GCN SE layers
74,33
40.06
23,66
46.80
78.12
63
69.28
65.53
59.88
5K.14
-1.71
5.09
-2.92
6.39
-3.29
6.13
-0.86
3.57
Head
GCN 64 beyens
GCN + SE 64 layers
$7.38
46.46
40.84
71.18
85.80
86.81
71.36
67.53
67.16
69,3
-1.78
-5.00
-6.24
-2.17
-6.05
-2.79
.0.3
-3.16
Tail
GCN layers
byyes
79.56
71.80
74.85
61.73
$6.43
-3,8
-1.14
64 loyors
Table 6: The comparisons of Cold Brew's GCN and the traditional GCN for deep layers. When the number of layers is large. Cold Brew's GCN retains good performance while the traditional GCN without SE suffers from the "over-smoothess" and degrades. Even with shallow layers, Cold Brew's GCN is better than traditional GCN.
6 CONCLUSION
In this paper, we studied the problem of generalizing GNNs to the tail and strict cold start nodes, whose neighborhood information is either sparse/noisy or completely missing. We proposed teacher- student knowledge distillation procedure to better generalize to the isolated nodes. We added an independent set of structural embeddings in GNN layers to alleviate node over-smoothness, and also proposed a virtual neighbor discovery step for the student model to attend to latent neighborhoods. We additionally present the FCR metric to quantify the difficulty of truly inductive representation learning and to optimize our model architecture design. Experiments demonstrated the consistently superior performance of our proposed framework on both public benchmarks and proprietary datasets.
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05200 2020.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. arXiv preprint 1rXXi:2007.021333 2020a.
Yuzhao Chen, Yatao Bian, Xi Xiao, Yu Rong, Tingyang Xu, and Junzhou Huang. On self-distilling graph neural network. arXiv preprint arXiv:201 1.02255, 2020b.
Hao Ding, Yifei Ma, Anoop Deoras, Yuyang Wang, and Hao Wang. Zero-shot recommender systems. arXiv preprint (iti::2005.08111 2021.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey, Knowledge- Based Systems, 151:78-94, 2018.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs.
arXiv preprint 1706:
2017.
Bowen Hao, Jing Zhang, Hongzhi Yin, Cuiping Li, and Hong Chen. Pre-training graph neural net- works for cold-start users and items representation. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 265-273, 2021.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.028 002531, 2015.
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mip: Node classification without message passing in graph. arXiv preprint arXiv: 10650 2021.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propa- gation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010.. 13993, 2020a.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propa- gation and simple models out-perfonms graph neural networks. arXiv preprint arXiv:2010.1399 13999 2020b.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over-smoothing for general graph convolutional networks. arXiv e-prints, pp. arXiv-2008, 2020c.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ICML, 2015.
Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. Label propagation for deep semi- supervised learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5070-501 0009-577922000 2019.
Mahdi Kherad and Amir Jalaly Bidgoly. Recommendation system using a deep learning and graph analysis approach. arXiv preprint arXiv:2004.08100, 2020.
Thomas Kipf and Max Welling. Semi-supervins classification with graph convolutional networks. arXiv preprint arXiv: 1609.00009 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arX.v:1810.05997,, 2018.
Xuan Nhat Lam, Thuc Vu, Trong Due Le, and Anh Duc Duong. Addressing cold-start problem in recommendation systems. Proceedings of the 2nd international conference on Ubiquitous information management and communication, pp. 208-20 00--211, 1, 2008
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9267-9276, 2019a.
10

---

Published as a conference paper at ICLR 2022
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, arXiv preprint arXiv:2006.07739 2020.
Jingjing Li, Mengmeng Jing, Ke Lu, Lei Zhu, Yang Yang, and Zi Huang. From zero-shot learning to cold-start recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4189-4196, 2019b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. arXiv preprint arXiv:2005. /46/2, 2020a.
Zemin Liu, Wentao Zhang, Yuan Fang, Xinming Zhang, and Steven CH Hoi. Towards locality- meta-lcarning of tail node embeddings on networks. In Proceedings of the 29th ACM International Conference on Information Knowledge Management, pp. 975 984, 2020b.
Yuanfu Lu, Yuan Fang, and Chuan Shi. Meta-learning on heterogeneous information networks for cold-start recommendation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1563-1573, 2020.
Sitao Luan, Mingde Zhao, Xiao Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. arXiv preprint arXiv:1906.02174. 0229900002114, 2019.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 19t.::99000055500 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chual Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002. 02000070.022..... 2020.
Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio. Fitnets: Hints for thin deep nets. arXiv preprint arXiv:1412.65500 2014.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations. https://openreview. nei/forum, 2020.
Shakila Shaikh, Sheetal Rathi, and Prachi Janrao. Recommendation system in e-commerce websites: A graph based approached. In 2017 IEEE 7th International Advance Computing Conference (IACC), pp. 931-934 IEEE, 2017.
Nitai B Silva, Ren Tsang, George DC Cavalcanti, and Jyh Tsang. A graph-based friend recommen- dation system using genetic algorithm. In IEEE congress evolutionary computation, pp. 1-7. IEEE, 2010.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov: Dropout: a simple way to prevent neural networks from overfitting The journal of machine learning research, 15(1):1929-1958 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998--0088 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 2017.
T Vetter, A Engel, T Biro, and U Mosel. production in nucleon-nucleon collisions. Physics Letters B, 263(2):153-156, 1991.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propaga- tion. arXiv preprint arXiv:200..06755, 2020.
11

---

Published as a conference paper at ICLR 2022
Yifei Wang. Yisen Wang, Jiansheng Yang. and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. arXiv preprint arXiv:2102.10739, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871 PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 32(1 :::4 1::4:44244 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint drXiv:1810.00826, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pp. 1453-5462. PMLR, 2018b.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting "over-smoothing" in deep gens. arXiv preprint arXiv:2003.13666 2020.
Cheng Yang, Jiawei Liu, and Chuan Shi. Extract the knowledge of graph neural networks and go beyond it: An effective knowledge distillation framework. In Proceedings of the Web Conference 2021, pp. 1227-1237, 2021.
Hongwei Zhang. Tijin Yan, Zenjun Xie, Yuanqing Xia, and Yuan Zhang. Revisiting graph convolu- tional network on supervisd node classification from an optimization perspective. arXiv preprint arXiv:2009. 11469, 2020.
Jiani Zhang, Xingjian Shi, Shenglin Zhao, and Irwin King. Star-gen: Stacked and reconstructed graph convolutional networks for recommender systems, arXiv preprint 1905. 2019.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mlps new tricks via distillation. arXiv preprint drXIv:2110008827, 2021.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint arXiv: 12223, 2019.
Kaixiong Zhou, Xiao Huang. Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. Advances in Neural Information Processing Systems, 33, 2020a.
Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation graph convolutional networks. arXiv preprint arXiv:2006.07107. 2020b.
Difan Zou, Ziniu Hu, Yewen Wang. Song Jiang, Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL 9lba4a4478a6 020.00aaea
A MORE ILLUSTRATIONS
The more detailed inference procedures for GNN and Cold Brew illustrated in Figure
12

---

Published as a conference paper at ICLR 2022
Graph
GNN Inference
node
Embocding
emzedding
MLP #1
node feature
Entedkling
Virtual Neighboroood Embudding
MLP
node feature
Entredking
Figure 3: Inference procedure illustration for GNN and Cold Brew.
B SEARCH SPACE DETAILS
In computing FCR, we include a search space of model hyperparameters for GNN, MLP, and LP in order find the best suitable configurations for distillation.
For the GNN model, take GCN backbone and performed grid search over the number of hidden layers, whether it has the structural embedding, the type of residual connection, and the type of normalization. For the number of hidden layers, considered 2, 8, 16, 32, and 64. For the types of residual connections, we include: (1) connection to the last layer (Li et al. 2019a) 2018), (2) initial connection the initial layer (Chen al. 2020a Klicpera et 2018 Zhang al. 2020)). (3) dense connection to all preceding layers (Li et al. 2019a 2018 2020 Luan et al. 2019). 9), and (4) jumping connection combining all the preceding layers only at the final graph convolutional layer (Xu et al., 2018b; Liu et al.) (020b). For the types of normalizations, we grid search over batch normalization (BatchNorm) (loffe & Szegedy 2015), pair normalization (PairNorm) (Zhao Akoglu 2019). node normalization (NodeNorm) (Zhou et al. 2020b), mean normalization (MeanNorm) (Yang ct al. 2020), and differentiable group normalization (GroupNorm) (Zhou et al. 2020a)). For types of graph dropout methods, include Dropout (Srivastava et al. 2014). DropEdge (Rong et al. 2020 DropNode (Huang et al. 2020c), and LADIES (Zou et al. (201)).
For architecture design for Cold Brew's MLP, we conducted hyperparameter search over the num- ber of hidden layers, the existence of residual connection, the hidden dimensions, and the optimizers. The number hidden layers is searched over 2, 8, 16, and 32. The number hidden dimensions is searched over 128 and 256. The optimizer is searched over (Adam(1==0.001) Adam(Ir=0.005), Adam(Ir=0.02), SGD(I=00005))
For Label Propagation, we conducted hyperparameter search over the number propagations, the propagation matrix type, and the mixing coefficient (Huang et al.) 2020a). The number of propagations searched over 10, 20, 50, 100, and 200. The propagation matrix type is searched over adjacency matrix and normalized Laplacian matrix. The mixing coefficient is searched over 0.01, 0.1, 0.5, 0.9, and 0.99.
The best GCN, MLP, and LP configurations are reported in Tables
and respectively.
C THE PERFORMANCE ON ALL SPLITS OF THE DATA
The performance evaluations on all splits are listed Table 10 The FCR evaluation on more datasets presented in Figure 11 We hypothesize that high FCR means that the graph does not add
13

---

Published as a conference paper at ICLR 2022
Best GCN
Dataset
layers
whether
residnal type
nonmalization type
Corn
2 Layer
has structural embedding
no residual
PairNorm
layer
structural embedding
residual
PairNarm
Puhmed
16 layer
has structural embedding
initial connection
GropNorm
layer
embedding
initial connection
GroupNorm
Chameleon
layer
has structural embbddding
initial connection
BatchNorm
Table 7:
Best GCN configurations.
Best MLP
Dataset
hidden layers
residual connection
hidden dimensions
optimizer
Cora
layer
no residual
128
(0000
Citeseer
layer
residual
128
Adam/le=0.001)
Pubmed
layer
nu residual
256
Adam(1=0.02)
layer
Chamelcon
layer
no residuall
256
Adam(1=00.001)
Table 8: Best MLP configurations.
too much information for the task hand. We indeed see evidence for this hypothesis Table where for the Pubmed dataset (FCR = 77%), the MLP-type models tend to outperform GNN-type models in all splits On the other hand, regardless FCR, for almost all datasets, the MLP-type models outperform the GNN-type models the isolation split, and few on the tail split, while the GNN-type models are superior in other splits.
D VISUALIZING THE LEARNED EMBEDDINGS
Figure 4 visualizes the last-layer embeddings of different models after I-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 decent job in separating different classes, significant portion of the tail and isolation nodes fall into wrong class clusters. Cold Brew's MLP is more discriminative the tail and isolation splits.
14

---

Published as a conference paper at ICLR 2022
Best LP
Dataset
number of propagations
propagation matrix type
mixing coefficient
Laplacian
Citeseer
100
Laplacian matrix
0.01
Pubmed
Adjacency matrix
0.5
Arxiv
100
Laplacian matrix
0.5
Chameleon
50
Luplacion matrix
0.1
Table 9: Best Label Propagation configurations.
Splix
Metrics/Musille
Open-Source Datasets
Proprictary Datasets
Cora
Cheseer
Pubmed
Ardi
Chameleon
commi
E comm2
comma
E: comme
GNNs
GCN layers
GrapeS
66.02
58.02
51.46
47.09
69.87
71.50
41.82
64.51
99.83
57.08
+3.89
+4.81
+5.24
+0.52
Iesotioon
MLPs
Simple MLP
GraphMLP
65.00
68.40
3282
53.26
65.84
71.22
$1.10
$1.03
63.54
60.76
+5.89
+6.27
+9.46
19:35
+5.99
+5.83
+7.37
16.42
Coid Brew
loyors
+11.09
+0.6
layers
ACIF
42.77
73.07
-3.07
Simple
GraphMPP
70.09
75.33
GNNs
AGG
80.37
R5.79
70.85
73.35
-7.46
Head
MI. Ps
Simple MLP
GraphMLP
72.45
24.35
69.83
72.00
89.00
89.00
56.65
56,
62.44
-15.95
-16.44
-18.08
-18.10
-15.33
-16.73
-1541
16.51
Cold Brew
GCN SE layas
Student ML.
$9.39
74.53
30.76
72:33
90.33
87.83
$7.41
74,01
61.28
70.56
-15.28
+1.11
-17.42
+0.47
-17.02
.0.39
-15.4
+1.28
GNNs
GCN layers
Graphi AGE
$0.50
$4.89
66.21
70.38
76,73
73.15
71,50
33
70:02
$9.30
-3.09
-3.86
-2.58
-5488
Overall
MI.N Ps
Sinple ML P
GuyhMLP
69.02
71.57
66.22
$6.59
73.51
82.03
53.81
$4.89
$7.67
58.65
-12.26
-12.69
-12.86
-12.01
-12.68
-10.80
-11.41
-13.16
Cold Brew
CCN SE laaress
Student MLL
86.96
72:36
72.44
67.54
79.03
$2.00
71.92
54.94
59,07
68.51
+0.65
11.25
11.31
0.24
11.55
0.27
+1.43
11:21
Table 10: The performance comparisons all splits of different datasets.
Cora
Citeseer
Pubmed
Andiv
Cham.
Squ.
Acter
Comeel
Teaas
Wiscomsin
GNN
86.96
72.44
75.06
71.34
68.31
31.95
59.79
65.1
61.88
$1.67
MLP
69.02
56.59
73.51
54.89
58.65
58.51
57.93
86.36
83.33
85.42
Label Propagation
78.18
45.00
67.8
68.26
11.01
22.85
29.69
32.05
$2.08
40.62
838
79%
25R
225
11%
6%
16%
bond
4.24
2339%
11.71
39
0.24
4531
2.23
2.37
-11.6
-1592
Acad
Esolotion CNN)
31.01
33.09
15.21
29.81
1.55
-485
22.61
18.68
22.62
-29.3
Table 11: Top part: FCR and its components. The 3 metric is added as a reference. Bottom part: the performance difference of GNN on the head/tail and head/isolation splits.
15

---

Published as a conference paper at ICLR 2022
Figure 4: Top two subfigures: the last-layer embeddings of GCN and Simple ML.. Bottom two subfigures: the last-layer embeddings of GraphMLP and Cold Brew's student MLP. All embeddings projected to 2D with t-SNE. Cold Brew's 's MLP has the fewest isolated nodes that are misplaced into wrong clusters.
16


Reviews:
[{"review_id": "wq9DKpQWTf6", "reviewer": "Reviewer_kTEC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength \n\n1 - Propose a knowledge-distillation based technique for learning cold start node representation.  \n\n2 - The problem is relatively new and interesting. \n\n3 - Presentation is overall good.\n\nWeakness\n\n1 - The novelty of proposed model is not significant. \n\n2 - Experiments could be improved.    \n\n3 - Lacks related work discussion.\n\nDetailed Review\n\nIt is interesting to develop new method for GNN to handle nodes without neighbors. The proposed knowledge distillation framework seems reasonable for me. Besides, FCR metric is proposed to measure the importance of node feature and graph structure. The proposed method works well for node classification task in several datasets. Following are some issues.\n\nThe novelty of proposed method is not significant as it follows general teacher-student network and combines both neighbor aggregator and structure embedding to learn node embeddings. These parts are borrowed from existing techniques. It would be better to discuss model contribution. In addition, the current manuscript only studies node classification task while it is also possible to study link prediction task over cold-start nodes (e.g., tail nodes). Moreover, there are some existing works studying tail node representation learning that should be discussed or compared, such as:\n\nTowards locality-aware meta-learning of tail node embeddings on networks, CIKM'21\n\nTail-GNN: Tail-Node Graph Neural Networks, KDD'21\n\nMinor issues exist, such as typo. For example, the first sentence of section 3.2 should be: to integrate the knowledge of GNN teacher.\n\n--\nUpdate after rebuttal: The authors addressed some of my concerns in experiments. The novelty is still incremental for me. I change my score to borderline above. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "This work studies an interesting problem. The proposed method is reasonable for solving the problem. The novelty is not significant. In addition, experiments could be improved. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rqgqeaupZPJ", "reviewer": "Reviewer_svEE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method to adopt GNN with knowledge distillation to solve SCS problem relies on well-known concepts and previous works, but the learnable Structural Embedding and model selection methodology is novel in contribution and can also have practical adoption for industry applications. The proposed solution is technically sound and is well supported by the extensive evaluation presented. Overall, the paper is easy to follow, and the motivations are also well justified.\n\nThe experimental settings and the data preparation are well documented, the authors have performed extensive empirical studies against multiple public datasets and several baseline methods to show their proposed method’s efficacy. The studies consistently show the proposed Cold Brew solution to solve the SCS problem results in significant improvement – especially for the tail & isolation splits.\n\nIt should be noted that the focus is primarily on graph-based solutions for solving the SCS problem, which is not the only possible setup. Also, the evaluation and problem formulations are mainly focused on node label prediction (accuracy metric), it would have been interesting to see some metrics like hit-rate (especially for tail & isolated splits of e-commerce datasets) – for ranked recall generation(link-injection) using node representations learned from SCS for a cold-start item which is crucial for generating recommendation. \n\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "Overall , I think the paper studies an important and interesting problem and presents a good solution which is theoretically sound. It however could try to cover more broader and crucial task especially w.r.t cold-start recommendations . ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VvKm-ZxAlJ", "reviewer": "Reviewer_YxwQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is well-organized. Paying more attention to tail nodes and/or nodes with fewer neighbors is important and has been neglected in a lot of previous studies on GNN. It is also of practical value, e.g., cold start in the recommendation system. Using knowledge distill to learn a transformation from both structures and attributes to attribute is an interesting idea to solve this problem. Experimental results on several graphs demonstrate the effectiveness of the proposed method.\n\nMy major concerns are as follows:\n- There are some previous studies on tail node representation learning, e.g. [1] and [2]. I suggest that the authors discuss these studies and compare the experimental result with these methods.\n- What's the reason for minimizing the structural embedding E in the loss function (Eq (3))? Since E represents the node-wise representation with label information, it is not intuitively clear why this embedding should be as small as possible.\n- The experimental studies only validate the performance using GCN. I wonder if the performance will be influenced by different GNN. For example, GraphSage uses a sampling strategy to aggregate embedding, and intuitively this may mitigate the impact of imbalanced distribution or noisy structural information.\n- Since label information has been incorporated into the embedding (with the structural embedding E), the ratio of labeled nodes may influence the performance. Could you give some empirical or theoretical analysis of this possible relationship between the performance and ratio of labels?\n\nI also have some minor comments:\n- Title: The title contains the terms incomplete or missing, but the main content discusses a more general case including tail nodes, isolated nodes, and nodes with (maybe) incomplete or missing neighborhoods. Please make the title and content consistent.\n- Notation z has been used as some element under Eq (4) and performance of models in Eq (5).\n- Typo on Page 4: this *motivate* us to strengthen..\n- The information in Figure 1 top is clear but the way to show the graph (the grey nodes) on such a coordinate is misleading.\n\n[1] Tail-GNN: Tail-Node Graph Neural Networks, KDD 2021\n[2] Towards Locality-Aware Meta-Learning of Tail Node Embeddings on Networks, CIKM 2020", "summary_of_the_paper": "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\nmodels 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.", "summary_of_the_review": "This paper studies an interesting and practical problem of learning better representations for tail and isolated nodes. Making use of a distilling approach, the combined information of both structures and attributes can be learned to generalize in nodes with less or even no structural information. Some weakness of the paper includes missing baselines, comparison to other GNNs, and deeper investigation of the label information.\n-------------------------------\nI appreciate the responses from the authors that addressed most of my concerns. I updated my rating.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HTDOSA9S4_b", "reviewer": "Reviewer_cztX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper is well-motivated. The problem studied in this paper is important for the graph domain.\n2. The proposed knowledge distillation method sounds interesting and novel.\n3. The paper proposes the feature-contribution ratio to guide the selection of model architectures.\n\nWeaknesses:\n1. The authors claim that the related works about cold start do not address the case of noisy or missing neighborhoods. However, the paper also focuses on the general cold-start problem and does not address the noisy or missing neighborhoods. I did not find any discussion or designed strategy to handle the noisy or missing neighborhoods explicitly.\n\n2. It is not clear why the structural embedding can encode the label information.\n\n3. The assumption behind the proposed knowledge distillation method is not clear. Can I suppose that the paper has an implicit assumption that is \"the nodes with similar features should have similar neighborhoods\"? Because the student is to learn a mapping from the node features to $\\overline{E}$ that is learned graph structure.\n\n4. The authors claim that the MLP student will behave like the GNN teacher but generalize better to tail and cold-start nodes. But as Table 3 shown, GCN+SE outperforms the student MLP in the tail scenario, and the results need more explanation and discussion.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper provides an interesting and novel solution for the critical cold-start problem. However, several claims are not well-explained or well-supported.\n\nThe authors addressed most of my concerns, I would like to update my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper studies an important and interesting problem and presents a good solution which is theoretically sound. The paper can be further improved by looking into more applications such as cold-start recommendations.
Decision: Accept (Poster)