ColdExpand: Semi-Supervised Graph Learning in Cold Start
Authors: Il-Jae Kwon
Kyoung-Woon On
Dong-Geon Lee
Byoung-Tak Zhang
Venue:  (2021)
Keywords: Graph Neural Networks
Cold Start
Semi-supervised Learning

Abstract: Most real-world graphs are dynamic and eventually face the cold start problem. A fundamental question is how the new cold nodes acquire initial information in order to be adapted into the existing graph. Here  we postulates the cold start problem as a fundamental issue in graph learning and propose a new learning setting, "``Expanded Semi-supervised Learning." In expanded semi-supervised learning we extend the original semi-supervised learning setting even to new cold nodes that are disconnected from the graph. To this end, we propose ColdExpand model that classifies the cold nodes based on link prediction with multiple goals to tackle. We experimentally prove that by adding additional goal to existing link prediction method,  our method outperforms the baseline in both expanded semi-supervised link prediction (at most 24\%) and node classification tasks (at most 15%). To the best of our knowledge this is the first study to address expansion of semi-supervised learning to unseen nodes.

Under review as a conference paper at ICLR 2021
COLDEXPAND: SEMI-SUPERVISED GRAPH LEARNING IN COLD START
Anonymous authors Paper under double-blind review
ABSTRACT
Most real-world graphs are dynamic and eventually face the cold start problem. A fundamental question is how the new cold nodes acquire initial information order to be adapted into the existing graph. Here we postulates the cold start prob- lem as a fundamental issue in graph learning and propose a new learning setting, "Expanded Semi-supervised Learning." In expanded semi-supervised learning we extend the original cemi-supervised learning setting even to new cold nodes that are disconnected from the graph. To this end, propose ColdExpand model that classifies the cold nodes based on link prediction with multiple goals to tackle. We experimentally prove that by adding additional goal to existing link prediction method, our method outperforms the baseline in both expanded semi-supervised link prediction (at most 24%) and node classification tasks (at most 15%). To the best of our knowledge this is the first study to address expansion of semi- supervised learning to unseen nodes.
INTRODUCTION
Graph-based semi-supervised learning has attracted much attention thanks to its applicability to real-world problems. For example, a social network is graph-structured data in which people in the network are considered to be nodes and relationships between people considered to be edges: two people are friends or sharing posts, etc. With this structural information, we can infer some unknown attributes of person (node) based on the information of people he is connected (i.e., semi-supervised node classification). In the case of retail applications, customers and products can be viewed as heterogeneous nodes and edges between customers and products can represent rela- tionships between the customers and the purchased products. Such graph can be used to represent spending habits of each customer and we can recommend a product to a user by inferring the likeli- hood of connection between the user and the product (i.e., semi-supervised link prediction).
Recent progress on Graph Neural Networks (GNN) (Bruna et al., 2013 Kipt & Welling 2016a Gilmer et al. 2017 Veličković et al.) 20188] Tia et al., 2019) allows us to effectively utilize the pressive power of the graph-structured data and to solve various graph related tasks. Early GNN methods tackled semi-supervised node classification task, task lahel all nodes within the graph when only a small subset of nodes is labeled, achieving a satisfactory performance (Zhou et al. 2004). Link prediction another graph-related task that was covered comparatively less than other tasks in the field of GNNs. In the link prediction task, the goal is to estimate the likelihood of con- nection between two nodes given node feature data and topological structure data. Link prediction can be used in recommendation tasks (Chen et al., 22005; Sarwar et al. 2001 Lika et al. 2014 Li &
Chen 2013 Berg al. 2017) or graph completion tasks (Kazemi & Poole 2018 Zhang & Chen 2018 Most of the work on semi-supervised graph learning and link prediction assumes a static graph, that is, the structural information at least "partially" observable terms of nodes.
In the real world, however, new users or items can be added (as nodes) without any topological information (Gope & Jain 2017). This is also referred as the cold start problem when a new node is presented to existing graph without single edge. In contrast to the warm start case, in which at least some topological information is provided, the cold start problem is an extreme case where there isn't 't any topological information refer. In this setting, previous supervipe learning algorithms can not propagate information to the cold nodes. Even though the cold start problem is an extreme setting, it is inevitable problem that occurs often in the real world data.

---

Under review as a conference paper at ICLR 2021
Figure I: Left: Original Semi-supervised Learning, Right: Expanded Semi-supervised Learning. Nodes with solid lines are labeled nodes and other nodes with dot lines are unlabeled nodes. Ex- panded supervise learning extends the original semi-supervised learning even to new nodes that are disconnected from the graph. By adding unseen cold nodes to the training we can not only expand learning cold nodes but also node features of cold nodes better approximate the marginal distribution of the original graph data.
In this paper, we postulates the cold start problem as a fundamental issue in graph learning and propose new learning setting, expanded semi-supervised learning. In expanded semi-supervised learning we extend the original semi-supervised learning setting even to new cold nodes that are disconnected from the graph as shown in Figure To this end, we suggest the ColdExpand method, the method that uses multi-task learning strategy to alleviate the cold start problem that typical graph learning methods face. We experimentally prove that by adding an additional goal to the existing link prediction method, performance
the link prediction task is enhanced in every benchmark dataset and at most by 24%. We also prove that our method can expand semi-supervised node classification even to unseen, cold nodes. To the best of our knowledge, this is the first study expand semi- supervised learning methods to unseen nodes. In the next section, we briefly introduce related works. In Section we define problem definition. Finally, in Section 4 we propose ColdExpand model followed by our experimental environments along with corresponding results.
2 RELATED WORK
2.1 SEMI-SUPERVISED NODE CLASSIFICATION
Semi-supervised learning is combination of unsupervised learning and supervised learning where true labels are only partially given. Semi-supervised learning algorithms aim to improve the model's performance by using unlabeled data points top of labeled ones to approximate the underly- ing marginal data distribution (Van Engelen & Hoos 2020). One of the most popular fields of semi-supervised learning graph based semiisupervised node classification where all nodes should be classified when only a few node labels are given. In order to smooth the given subset la- bels throughout the graph, various methods have been studied to effectively represent nodes. Deep Walk (Perozzi et al.] 2014), LINE (Tang et al. 2015), node2vec (Grover & Leskoved) (016) were early deep-learning- based methods targeting the node classification task by learning latent repre- sentations from truncated random walks. However, these models fail to share parameters between nodes causing learning be inefficient. Kipf & Welling (2016a) introduced Graph Convolutional Networks (GCN) which use an efficient layer-wise propagation rule by approximating the first-order of spectral graph convolution. By limiting the spectral convolution to the first-order, GCNs not only lightened computation cost of the operation but also alleviated the over-fitting problem that previ- ous spectral methods had. Commonly, GCN model is formed from stacked convolutional layers; the number of which decides how many hops of neighbors to consider for the convolution opera- tion. Gilmer et al.) (2017) presented Message Passing Neural Networks (MPNN) as a general form of spatial convolution operation and treated GCN specific kind of message passing process. In MPNNs, information between nodes delivered directly by edges without visiting any spectral domains.
2

---

Under review as a conference paper at ICLR 2021
2.2 LINK PREDICTION
Links in graph-structured data appeal important interactions between nodes that may not be rep- resented solely by node attributes. To this end, link prediction is an important task in order to ef- fectively utilize graph data. In the link prediction task, we aim to predict whether an edge exists between two nodes from the same graph. Predicting the existence of links between nodes is useful for many applications including recommendation systems and graph completion tasks.
On a high level, link prediction methods can be separated into similarity -bssdd and learning- -based methods. Similarity-based link prediction is the simplest way to predict the link by assigning a similarity score Szy between two nodes y. Common Neighbors (Marchette & Priebe 2008),
Salton Index. Jaccard Index (Leydesdorfi 2008), Sorensen Index, Hub Promoted Index, Hub De- pressed Index (Zhou et al.] 2009), Leicht-Holme- Holme-Newmann Newman Index (LHNI) (Leicht et al.] (2066) each
define similarity scores by using the overlapping set of neighhoring nodes between two nodes. While the former neighborhood-basee methods focus on somewhat local similarity, other similarity-based methods consider global similarity by taking into account higher order links. Katz Index (Katz) 1953) considers the ensemble of all paths between two nodes summed with quadratic weight ac- cording to the distance of each path. SimRank (Jeh & Widom, 2002) also uses random walk process but measures how soon two random walkers from the two different nodes meet. However, when a cold node is introduced, the required structural information needed for previous similarity- ap- proaches is missing, thus making them impossible to applied in cold start situations (Wang et al., 2016).
On the other hand, learning- based methods formulate link prediction as binary classification prob- lem given feature embedding vectors of two nodes; if an edge exists between the two nodes a positive label is given and vice versa. Kipl & Welling (2016b) introduced the graph auto-encoder (GAE), an unsupervised learning technique, which aims to reconstruct the original adjacency matrix. As variant of GAE, variational graph auto auto-encoders (VGAE) additionally train a separate GCN module resulting in the logarithm of the variant matrix, log(o²). Additional Kullback-Leibler divergence loss between the distribution of encoder and decoder is added to the original reconstruction loss. Pan al. (2099) further improved upon GAFS by applying adversarial training to regularize the latent node embedding matrix Z to match a prior distribution of the original node feature matrix X. A simple MLP-based discriminator D) was used for adversarial learning between the real distribu- tion of G (X, A} and the latent node matrix Z. Unlike similarity- based methods, learning- based methods can be applied to cold start problems since they make use of node feature information along with topological structure information.
2.3 COLD START PROBLEM
The cold start problem is a common problem in real-world graph-structured data where new nodes may be added to an existing graph. Most work tackling the cold start problem focuses on solving the recommendation problem in a cold start setting. Recommendation systems are widely used in the real world applications such as friend recommendation, movie recommendation and purchase recommendation. In the recommendation problem, the task is to predict recommendation links from heterogeneous graph containing two types of graphs; user-user social graph and user-item rating graph. Users are involved in both types of graphs to connect the two types of graphs into a sin- gle heterogeneous graph. The collaborative filtering (CF) method is one of the traditional methods where a rating is predicted based on similarities between users or items. In short, the CF method makes recommendations based on ratings given by other users in the social graph. Saawar et al. (001) introduced an item- -bsed CF method, which computes item--ite similarities, and proved it outperforms other user- based collaborative filtering recommendation methods. Efforts to make use of CF for recommendation systems in the cold start scenario have been made. [Lika et al.) (2014) approached the cold user problem by exploiting CF followed by hard-clustering of users based on their attributes. Once the cluster of the new user has been decided, CF is only applied to members of the same cluster. [erg et al. (017) formulated the matrix completion task of recommendation systems link prediction problem by viewing the user-item graph as bipartite interaction graph. However, they instead used a warm start setting where at least one rating for a user is given which is not precisely cold start assumption.
3

---

Under review as a conference paper at ICLR 2021
3 PROBLEM DEFINITION
A graph G is denoted as a pair (V,E) with == (ei, ..., ) the set of nodes (vertices), and & E V V the set of edges. Each node v; is associated with feature vector æ; Rf, To make notation more compact, the set of node feature vectors of graph G is denoted as a matrix X = [21, Ø2, .IN]' NNF. Additionally, a graph has an N-by-N adjacency matrix A where A represents the existence of an edge between eú and bj and degree matrix D, a diagonal matrix which contains information about the degree of each node.
In the cold start setting, we will call those nodes that are newly introduced without any link from the existing graph cold nodes and let them be denoted by uf. the same manner, existing nodes in the graph are denoted vf. Then, X. only contains feature vectors of existing nodes Tis oi, 22 ....... IN,_ and X. contains feature vectors of cold nodes zúj +f, and Ne are the number of existing nodes and cold nodes, respectively.
where No
In our problem setting, we assume that new nodes are added to the existing graph and need to find possible links between new nodes and existing nodes followed by a node classification to figure out the hidden attributes of new nodes. Our problem definition is as follows: Given existing graph, G (Ve, A), and cold nodes Xe, find out all possible links between cold nodes X, and existing nodes Xe, then predict the class of cold nodes X..
4 METHOD
Here we present our method, the ColdExpand, that compensates the lack of topological information from the cold nodes by adding an additional task of supersupe node classification deep autoencoding principle in the stage of edge reconstruction.
4.1 LINK PREDICTION OF COLD NODES
Predicting possible edges of cold nodes is an important sub-goal for expanding a semi-supervised learning but is by itself still a difficult task because the only clue the new node provides is its own node features. As mentioned in Section 2.2 traditional not applicable in the cold start setting since no neighboring nodes the cold node are known. On the other hand, learning-basse -baeed link prediction algorithms (Passino et al. 2019 Kipf & Welling, 2016b] Pan et af.] 2019) can be applied in the cold start setting by computing similarity scores between two embedded node feature vectors followed by binary classification layer. Still, while embeddings of the existing nodes are conditioned on both the node feature and the features of neighboring nodes, embeddings of the cold nodes refer only to their own node features without any help from the topological structure of the graph resulting in isolated learning.
semilarrty-basee link prediction methods are
x = GNN eneoder (xt, (xx)))
x enceder (zf, {0])
when (z;)) is a set of neighboring nodes of node I; and weights of the GNN GNNenroder are shared between the two. This hinders traditional GNN encoders from generalizing their training to the cold nodes. In order to make a common goal that can be accomplished by both existing nodes xº and cold nodes rº, we train the GCN Encoder with an additional node classification goal as given by the following equation.
Liotal
Llink Letassi ficationn
(3)
4.2 COLDEXPAND
Figure illustrates the overall structure of our ColdExpand model. Our model is composed of two parts; first, the GCN module for link prediction on the cold nodes and, secondly, the GCN module for classification on the cold nodes. We denote the first GCN module GCN Encoder and the second GCN module as GCN Classifier. In the GCN Encoder, graph G and cold node of are given as input. We use two basic GCN layers suggested in (Kipf & Welling 2016a) for encoder to get the embedded node vector Z. In order to predict any possible links of the cold node v", we feed this embedded node vector Z to inner product decoder which is similar to previous link prediction
4

---

Under review as a conference paper at ICLR 2021
Reconstruction loss (yyeom)
Cold Node
GCNi
Z
Inner Product Decoder
GCNclasffer
Node Classification
Original Graph (Y.4
Classification (Lts)
Figure 2: Computational graph for the ColdExpand model
methods (Passino et al. 2019 Kipf & Welling 2016b Pan et al. 2019). Along with original edges, predicted links are then fed the GCN Classifier for node classification.
One GCN layer can be written as follows:
M -
(4)
where À is an adjacency matrix of graph G with additional self connections and H is the degree matrix of Å. è is a weight matrix for GCN module. Using the basic 2-layer GCN module, the embedding node matrix for all existing nodes X, and cold nodes X, represented follows:
g(Zel( (X,, Acc)) = M ((RELU(M Ace, θ1), 02)
(5)
(Xe, Ace)) ReLU(X,0))e
(6)
where θ is weight matrix for the first-layer GCN and θ2 for the second.
p(A = 2g) 22
(7)
The inner product decoder computes the sigmoid of the inner product between two embedded node vectors. Acc indicates possible edges between the existing nodes and the cold nodes. The probability
of existence of link between existing nodes xς and cold nodes æ is defined as follows:
Once the probabilities of links have been computed, new hard links for the cold nodes can be added.
Acc 1, if p( = 1 25) >
(8)
0,
otherwise
where & is a hyperparameter which a threshold for hard links. During the experiment & was set to 0.5.
Aee
Aec
Á
Age
Acc
Arc can be obtained in same manner. Then the new Á is fed to the GCN Classifier for node clas- sification on the cold nodes. In order to maintain a continuous gradient along the model, we use the convolution operation with edge weights. Weights of all additional edges Aec. Ace are determined by the probability score of the edge, p(A = 1) while all the other weights for existing edges are fixed to 1.
(10) only use Y. for class prediction on cold nodes. For optimization, we use two losses for multi-task learning. The first loss is a link reconstruction loss from the link prediction part of the model and the second loss is node classification loss from GCN Classifier.
= softmax (GCNClassfeer (X, A))
Lisson
E2( (x.A)) [log p(Aecl (2) + log p(Aco) Z)]
(11)
Lets =
Σ y log 0
(12)
J-EÝ.
Liotal
Lrooon XLels
(13)
Finally, the total loss is represented as weighted sum of the two losses. is a hyperparameter for training.
5

---

Under review as a conference paper at ICLR 2021
Table 1: Dataset
Name
Nodes
Edges
Classes
Cold Nodes
Cora
3,327
4,732
6
332
CiteSeer
2,708
5,429
270
PubMed
19,717
44,338
3
1971
EXPERIMENT
5.1 DATASET
In order to evaluate the performance of graph learning in the cold start setting, we first select 10% of randomly shuffled nodes as a test set of cold nodes. Then we create positive edge samples of the set of cold nodes by parsing all links in and out of the cold nodes and every other non-links become negative samples. Whole positive and negative edge samples are used as test sets for the cold start link prediction task and are hidden in the training stage along with the class labels of cold nodes. This process is done in 10-fold cross-validation on all nodes the dataset. of the nodes were masked as validation set and another 10% of the nodes as training set. During training we choose the same amount of negative edge samples as positive edge samples. At last, in the training period edges of 20% of nodes were masked. For semi-supervised node classification only 10% of the labels of the nodes were given.
similar fashion, 5%
5.2 BASELINE
Since there are many prior works for cold start graph learning tasks, we created some baselines to prove the benefits of our model.
5.2. EXPANDED SEMI-SUPERVISED LINK PREDICTION
We used learning-batt based link prediction algorithms GAE, VGAE (iipf & Welling 2016b) and ARGA (Pan et al. 2019) to compare the performance of link generation for cold nodes. For fair comparison we have restricted the number of edges used in training to 10%. Then each link pre- diction method was trained with the ColdExpand method by adding an additional task of node classification with loss function as given in Equation 13
5.2.2 EXPANDED SEMI-SUPERVISED NODE CLASSIFICATION
The simplest baseline for semi-super node classification is a linear model that only considers node attributes of the graph. The number of labels that the model can see was restricted for fair comparison.
E = MLP(X.), 9 softmax(E)
(14)
The other baselines are vanilla GNNs which are trained on the existing graph and used to predict the labels of the cold nodes. In this setting, the same number of labels for existing nodes are provided during training.
E GNN(N,, A), softmax(E)
(15)
There are several training strategies for our ColdExpand model. In the ColdExpand-Freet model, first part of the model, the GCN Encoder, is pre-trained with multi-task goal under fixed Once pre-training is completed, weights of the GCN Encoder are frozen and training on the GCN Classifier takes place. Unlike the ColdExpand-FF Freeze model, the ColdExpand- ManExxapnn-nffreeee model updates the weights of the GCN Encoder along with the GCN Classifier. For the ColdExpand models, we choose the best setting among several choices of X. To demonstrate the advantage of adding an additional task, we also tested with ColdExpand CLS which shares the same model architecture but only uses Læs for optimization. Each test was done with various convolutional GNN methods including GCN, GGa (Hamilton et al. 2017), and GAT' (Veličković et al. 2017

---

Under review as a conference paper at ICLR 2021
5.3 RESULTS
5.3.
RESULTS OF LINK PREDICTION ON COLD NODES
Algorithm
Cora
CiteSeer
PubMed
GAE
0.625 = 0.017
0.678
0.029
0.809 + 0.007
GAE (ColdExpand)
0.813 + 0.021
0.854 0.019
0.907 + 0.006
VGAE
0.655 = 0.020
0.651
0.016
0.779 + 0.030
VGAE (ColdExpand)
0.643 + 0.034
0.676 + 0.058
0.836 + 0.031
ARGA
0.639 = 0.018
0.679 + 0.021
0.858 = 0.016
ARGA (ColdExpand)
0.784 = 0.024
0.824 0.024
0.881 + 0.006
Table Results of link prediction on cold nodes in area under the ROC curve (AUC) scores. Bold score indicated the best AUC score. In every methods, adding our learning strategy generally in- creased performance.
Table 2 illustrates the results of expanded semi-supervised link prediction on cold nodes in area under the ROC' curve (AUC) scores for each benchmark and dataset. Training with our ColdExpand strategy, ColdExpand encoders outperform most dearning-based algorithms in recon- structing the links of the cold nodes. Especially in the Cora and CiteSeer datasets which have enough number of classes, gin. In PubMed, where there are only classes of labels, our model achieves 5.7% higher AUC score. With the additional training goal, model definitely outperforms traditional link prediction methods on predicting the possible links of the cold nodes and training is more beneficial when there enough number classes.
model improves the performance (at most 24%) by large mar-
5.3.2 RESULTS OF SEMI-SUPERVISED NODE CLASSIFICATION ON COLD NODES
Algorithm
Cora
CiteSeer
PubMed
Linear Function
0.644 + 0.025
0.650 + 0.021
0.838 + 0.011
GCN
Vanilla GCN
0.690 0.023
0.656 + 0.024
0.836 0.006
ColdEXpand-CLS
0.445 + 0.153
0.609 + 0.082
0.768 + 0.028
HadEExpand-Freen
0.760 0.015
0.688 + 0.026
0.852
0.007
ColdExpand Unfreezee
0.792 + 0.029
0.710 = 0.020
0.835 = 0.010
GraphSAGE
Vanilla GraphS
0,545 + 0.058
0.596 + 0.071
0,801 + 0.011
ColdExpand-CLS
0,444 + 0.148
0.575 0.082
0.771 0.017
ColdExpand-Frees Freeze
0.746 + 0.032
0.683 + 0.023
0.817 + 0.009
ColdExpand ColdExpand-Unfrrezze Unfreeze
0.791 0.029
0.711 + 0.018
0.816 0.009
GAT
Vanilla GAT ColdExpand CLS
0.534 + 0.040
0.630 = 0.024
0.796 + 0.016
0.490 0.126
0.571 = 0.122
0.764 = 0.022
ColdExpand-Freed Freeze
0.638 + 0.049
0.634 + 0.030
0.821 + 0.008
ColdExpand- Unfreeze
0.686 0.028
0.673 + 0.021
0.817 0.011
Table 3: Experimental results on node classification task in comparison to various other models. Bold score indicated the best accuracy score. Our model outperformed existing GNN methods in every dataset.
shows experimental results on the expanded semi-supervised node classification task in com- parison to various other models. In order to test how inductive learning methods perform in the cold start setting, we tested with vanilla GCN, GraphSAGE, GAT methods by using the weights learned from con-cold start settings to classify cold nodes. On every dataset, our ColdExpand method per- formed better than traditional inductive GNN methods in the cold start setting. This is due to the

---

Under review as a conference paper at ICLR 2021
fundamental limitation that inductive learning methods have that they exclude cold nodes during training but rather test each node independently. In contrast, our ColdExpand model uses a multi- task strategy incorporate cold nodes into the existing graph and furthermore include them in training. The linear function model which does not consider topological structure of a graph, gen- erally performed poorly. However for PubMed, which has only three classes of labels, the linear function model showed performance close to our model. On other dataset, our ColdExpand model outperformed linear and vanilla GNN models by a big gap in performance: Cora (15%), CiteSeer (8%).
Algorithm
Cora
CiteSeer
PubMed
Edges per node
1.42
2.00
2.25
ColdExpand-CISS
5.96
6.30
8.23
ColdExpand-Unffe Unfreeee
5.12
4.63
6.73
Decreased edges (%) 14.1%
26.5%
18.3%
Table 4: Average number of generated edges for each cold node by different training strate- gies. Edges per node represents ground truth number of edges per each node. By using additional link prediction loss, ColdExpand- -entread-UUnfreeee Unfreeze decreased most 26.5% of new edges compared to ColdExpand-CC CLLS which is closer to the ground truth amount.
Another notable result from the experiment number of additional edges each GCN Encoder generates. In case of ColdExpand- the number of the additional edges tends to explode, generating much more edges between cold nodes and existing nodes. On the other hand, other ColdExpand models generated relatively fewer edges (Table using the link prediction loss regularizer for the GCN Encoder.
where classification loss was solely used for optimization,
Results show that in general, BaldExpand-Unfreees model works better than ColdExpand-Frees Freeze model. While traditional link prediction methods focus on reconstructing 1-hop links. Klicpera al. (209)) found that diffusion of graph. considering neighbors from multiple hops, improves semi- supervised learning without over-smoothing problem. This indicates that one-hop link prediction may not be the best solution for classifying the nodes. By training GCN Encoder during the stage of node classification we can find such links that can improve node classification that traditional link prediction methods could not find. In contrast, PubMed is a large graph with many nodes which degrades the effect of noisy connections.
5.3.3 ABLATION STUDY
Cora
CiteSeer
PubMed
09
GAE-CE -GA
-GAECE SAE
GAECCE -GAE
0.5
0.88
08
0.75
0.4
07
0.5
06
0.8
05
A
Figure 3: Link prediction results for different A. GAE-CE represents results using ColdExpand strat- egy. We added results of GAE which is invariant to À for comparison.
Figure 3 illustrates trend of the results cold start link prediction with varying hyperparameter, X, which decides the amount of additional classification loss to be considered. Each dataset has different property resulting in different optimal X. From the trend can easily figure that
8

---

Under review as a conference paper at ICLR 2021
adding additional task benefits cold start link prediction. This approach was more effective when there were enough distinct classes to map nodes to.
CONCLUSION
In this paper, we draw attention to new task Expanded Supervisde Learning which is task to extend semi-supervised learning even to cold nodes. Even though the cold start enviromment is an extreme situation, most real-world applications must face it. We proposed the ColdExpand method which uses multi-task strategy overcome the lack of topological information from cold nodes.
Our new task can be applied in many categories of machine learning. For example, community detection is task of discovering overlapping groups of nodes, also referred to communities, that share similar properties from the network graph. While most works on community detection only focused on static social networks (Leskovec & Mcauley) 2012 Chen et al. 2017 Li et al., 2019] Jia et al. 2019), is critical that learning can be propagated even to new users. Our method can used to categorize and adapt new user an existing community. In addition, solving the cold start problem in graphs is an important stepping stone for incremental learning. Incremental learning (Joshi Kulkarni 2012) a learning policy that extends its existing model as new samples are dynamically added. Graphs that can grow incrementally can be used to broaden the knowledge in cognitive models that rely on topological structure such as Adaptive Resonance Theory (Carpenter & Grossberg 2010) or the Neural Gas model (Fritzke 1995).
REFERENCES
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint arXiv: /00i::/700.0206000 02263,, 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv:1312.6203 2013.
Gail A Carpenter and Stephen Grossberg. Adaptive resonance theory, 2010.
Hsinchun Chen, Xin Li, and Zan Huang. Link prediction approach to collaborative filtering. In Proceedings of the 5th ACM/IEEE CS Joint Conference on Digital Libraries (JCDL '05). pp. 141- 142. IEEE, 2005.
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks. arXiv preprini arXiv: 170.008055 2017.
Bernd Fritzke. A growing neural gas network learns topologies. In Advances in neural information processing systems, pp. 625-632. 1995.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint 17X1v:100..01212, 2017.
Jyotirmoy Gope and Sanjay Kumar Jain, A survey on solving cold start problem in recommender systems. In 2017 International Conference on Computing. Communication and Automation (IC- CCA). pp. 133-138. IEEE, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Glen Jeh and Jennifer Widom. Simrank: measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference Knowledge discovery and data mining, pp.
2002.
Yuting Jia, Qinqin Zhang, Weinan Zhang, and Xinbing Wang. Communitygan: Community detec- tion with generative adversarial nets. In The World Wide Web Conference, pp. 784-794, 2019.

---

Under review as a conference paper at ICLR 2021
Prachi Joshi and Parag Kulkarni. Incremental learning: Areas and methods-a survey. International Journal of Data Mining & Knowledge Management Process, 2(5):43, 2012.
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43, 1953.
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Advances neural information processing systems, pp. 4284-4295, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609, 2016a.
Thomas N Kipf and Max Welling. 161 2016b.
Variational graph auto-encoders.
arXiv preprint
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn ing. In Advances in Neural Information Processing Systems, pp. 13354-13366, 2019.
Elizabeth A Leicht, Petter Holme, and Mark EJ Newman. Vertex similarity in networks. Physical Review E, 73(2):026120 2006.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. In Advances in neural information processing systems, pp. 539-547, 2012.
Loet Leydesdorff. On the normalization and visualization of author co-citation data: Salton's cosine versus the jaccard index. Journal of the American Society for Information Science and Technol- ogy, (9(11)77--88 85, 2008
Pei-Zhen Li, Ling Huang, Chang-Dong Wang, and Jian-Huang Lai. Edmot: An edge enhancement approach for motif-awan community detection. In Proceedings of the 25th ACM SIGKDD Inter- national Conference on Knowledge Discovery & Data Mining, pp. 487,487, 2019.
Xin Li and Hsinchun Chen. Recommendation link prediction in bipartite graphs: A graph kernel- based machine learning approach. Decision Support Systems, 54(2):880-800, 2013.
Blerina Lika, Kostas Kolomvatsos, and Stathes Hadjjefthymiades. Facing the cold start problem in recommender systems. Expert Systems with Applications, 41(4):2065-207) 2014.
David J Marchette and Carey Priebe. Predicting unobserved links in incompletely observed net- works. Computational Statistics & Data Analysis, 52(3):1373-138 2008.
Shirui Pan, Ruiqi Hu, Sai-fu Fung, Guodong Long, Jing Jiang, and Chengqi Zhang. Learning graph embedding with adversarial training methods. IEEE Transactions on Cybernetics, 50(6):2475- 2487, 2019.
Francesco Sanna Passino, Anna Bertiger, Joshua C Neil, and Nicholas A Heard. Link prediction in dynamic networks using random dot product graphs. arXiv preprint arXiv: 1912. 2019.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web, pp. 285 295, 2001.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference world wide web, pp. 1067-1077 2015.
Jesper E Van Engelen and Holger H Hoos. A survey semi-supervised learning. Machine Learn- ing, 109(2):373-44)) 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: /7/0. 10903, 2017.
10

---

Under review as a conference paper at ICLR 2021
Petar Veličkovié, William Fedus, William L Hamilton, Pietro Liô, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations. 2018.
Zhiqiang Wang, Jiye Liang, Ru Li, and Yuhua Qian. An approach to cold-start link prediction: Es- tablishing connections between non-topological and topological information. IEEE Transactions on Knowledge and Data Engineering, 28(1 11:17787772287, 2016.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5 (175,,,,, 2018.
Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learn- ing with local and global consistency. In Advances in neural information processing systems, pp- 321-328, 2004.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71(4):623-630 2009.


Reviews:
[{"review_id": "trEhEjHVDlV", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\n \nThis paper presents a model called ColdExpand that addresses learning tasks related to attributed graphs. Authors argue that this model is the first model able to deal with the cold-start problem, i.e. new nodes with no structure information, which explains its name. However I think they totally miss part of the recent literature on inductive approaches. ColdExpand addresses the new node issue by using an architecture that combines a deep auto-encoder and a GNN classifier. Experiments show that ColdExpand is better for both link prediction and node classification, but (again) it is not compared to more appropriate baselines.\n\n\n##########################################################################\n\nReasons for score: \n\nI vote for rejection because of two reasons. First, I think the cold-start problem presented in this paper can be solved by using inductive approaches that has already been developed. I guess that \"inductive\" can be understood in different ways, but previous works are able to deal with new nodes that are described by attributes only (see, for instance, G2G [1] and IDNE [2]).\nSecond, the model looks really incremental with a simple concatenation of AE and GNN. The semi-supervised task is not clearly described (it looks as if the whole dataset is labelled). As a minor remark, I find that evaluating the model on a unique data type (here, scientific networks) shed a bad light on the ability to generalize on diverse datasets.\n\n[1] Aleksandar Bojchevski, Stephan Günnemann (2018), Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking, ICLR 2018\n\n[2] R. Brochier, A. Guille and J. Velcin (2020), Inductive Document Network Embedding with Topic-Word Attention, ECIR 2020\n \n##########################################################################Pros: \n\n \n1. The model addresses the more realistic task of inductive prediction, in contrast to transductive approaches.\n2. The paper is reasonnably written.\n \n##########################################################################\n\nCons: \n\n \n1. Litterature on inductive approaches is missing (see above).\n2. Model looks really incremental \n3. It is not compared to inductive models \n\n \n##########################################################################\n\nQuestions during rebuttal period: \n \nPlease clarify the novelty of the cold-start problem addressed in this paper and the usual inductive task as addressed in [1] and [2]. Besides I would like to know why it is a semi-supervised setting.\n\n \n#########################################################################\n\nI guess A should be mentioned in Eq. (5).\n\nThe authors should check the references (e.g., Velickovic et al. has been published at ICLR 2018).\n\nSome typos: \n\n\"in a log of variant matrix\"\n\"different hyperparameter\"\n\n######\n\nUpdate: after reading the other reviews and author response, I decided to increase my grade to 6.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "WspNEeSVmG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Clarity : Eqn(5) and (6) introduce symbols $\\theta_1$ and $\\theta_2$ whose meaning is unclear. Eqn(6) requires more clarity as it is important to understand how intermediate embeddings for cold nodes are being generated. \nOverall the problem motivation and related work section is well described\n\nNovelty:  The proposed model is created by clubbing together GCN model for node classification and GAE model  for link prediction. The loss function is a weighted combination of the two. Lacks sufficient novelty\nImpact: The paper clubs together two earlier well known models and makes no additional theoretical contributions. \n\nCorrectness: The link recommendation test sets have the same no. of positive and negative ratio. This scenario is highly unlikely in a real-world setting. A more skewed dataset would throw off the performance metrics significantly. \nAUC scores are reported. AP/RR/Accuracy values should be explored as well. While I agree AUC is well prevalent in community, Precision captures the sensitivity in ranking much better in link prediction.\n\nMaybe I missed the code, can the reviewer point out to it?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JNjjE1x3edi", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n \nThe paper proposes a new task in Graph Learning. Basically, the idea is the following: suppose we have a node classification model trained on a Graph G, suppose we have a new node (not present in G) and we want to classify it. Given that the new node has no connections with G’s other nodes we cannot leverage any structural information to run the classifier. This is an issue that authors present it as cold-start in semi-supervised graph learning. The solution, even if simple, is very effective and for this reason even more interesting. Basically, they start with a retrieval step (they call it link prediction) that is trained using a link reconstruction loss and it’s based on dot-product to make the link prediction phase scalable. After those links are reconstructed they run a node classification step (based on GCN, GraphSAGE, or GAT) on G plus the new node and the predicted links.  The results obtained in the experiments are really encouraging with improvements ranging from 15 to 25% over a baseline that does not consider the link prediction phase.\n##########################################################################\nReasons for score: \n \nOverall, I vote for accepting. I consider this as a non-trivial step forward towards using Graph Learning on recommendation problems and node classification problems. There are many applications of Graph Learning where the technique presented in this paper can be of help. Consider, for instance, all the words relying on GNNs to do fake news detection based on a semi-supervised technique. All of those methods fail in the case a new document (node) has no explicit connections to the graph. This method would solve that issue. \n \n##########################################################################Pros: \n \n1. The paper tackles a problem that is, in my opinion, very important and, so far, overlooked: cold-start node prediction using graph learning.\n2. The technique presented in the paper is simple, which I consider a plus. It works and it’s simple.\n3. The experiments show a great improvement over the baseline\n \n##########################################################################\nCons: \n \n1. One big limitation of this work, that is in my opinion under explored is that it is based on the assumption that links depend on the content/features of the nodes. In some cases this assumption might not hold true. I would like authors to discuss on this point.\n2. I am not sure how the link prediction phase could be made scalable. As it is defined now it is an O(n^2) step. Or better, I have some ideas but I’d like authors to discuss this.\n3. Why you pick a threshold of .5 in equation (8) Shouldn’t this be an hyperparam?\n \n##########################################################################\nQuestions during rebuttal period: \n \nPlease address and clarify the cons above \n \n#########################################################################\nSome minor issues \n(1) There is an inconsistency in the notation for M in equation (4) and M in equation (5). In equation (4) M takes 3 parameters, while in (5) it takes 2. Please clarify.\n(2) Why you speak about cold nodes X_c instead of  cold node? Up until now it looked like you only used one node at a time. Please clarify.\n(3) What is q() in equations (5) and (6)?\n(4) In Figure 3, what is the black line under the blue curve? It’s not written anywhere.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "H9AliD9OxX3", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n========\nThis paper is about the cold-start problem for representation learning on dynamics graphs. More specifically, the proposed method (ColdExpand) uses convolutional networks and multi-task learning (node classification loss and link prediction loss) to learn embeddings for new unseen nodes in the graph, i.e., nodes that we only know their features and not their connectivity to the existing graph. Such a problem is useful for applications of the link prediction problem and more specifically, recommendation tasks or graph completion tasks. The authors test their technique using three benchmark datasets (Cora, CiteSeer and PubMed) and by using building blocks of existing works they create some baselines to compare. They claim to be the first study for semi-supervised learning to unseen nodes. However, there are a couple of works in this field already, as for example the GraphSAGE model that they cite in this paper (see below for more). \n\nReasons for score\n================\nOverall, the paper is about an interesting problem (cold-start for representation learning on dynamic graphs). However, the proposed methods has limited novelty by using known building blocks from the literature. Also, the experimental setup and the results are not very convincing. Results on more datasets, more comparison methods and a different setup will strengthen the paper.\n\n\nStrengths\n========\n- The problem of representation learning in dynamic graphs for unseen nodes is interesting and has attracted the attention of researchers in the field in the last years. In this paper, the authors propose a semi-supervised learning for the link prediction for unseen nodes.\n- The proposed method that uses a multi-task learning strategy by combining a loss for link reconstruction and a loss for node classification is reasonable, has been well motivated in the paper, despite the limited novelty.\n- Overall the paper is well-written and has a nice flow. \n\n\nWeaknesses\n===========\n- The authors claim that this is the first work on semi-supervised learning for unseen nodes. However, there are a couple of methods already in this field. Other methods include: GraphSAGE (already in the references of the paper), PinSAGE [1], HAN [2] and DynRep [3]. The authors should consider to add these methods in the comparison, and also in related work subsection 2.3.\n- Figure 1 is not useful and takes a lot of space, the authors could use the space to expand their experiments.\n- In subsection 4.2 there are some parameters that are never described, as for example \\Theta.  In equation 4, M(,,) takes 3 arguments, but later it is used with only two. In general there are some inconsistencies in the notation and the equations in terms of the definition/description of some of the parameters. It needs careful check.\n- The experimentation is limited. The authors use three datasets and they apply some preprocessing in order to use some nodes/edges as unseen. It would be nice if the authors can add these numbers in Table 1. \n- It would be interesting to see results for the GCN, GraphSAGE and GAT in the link prediction task. An aggregation of the node embeddings from the nodes that create an edge can be used to compute an edge embedding (as it is already done in the literature).\n- It could be interesting to add an experiment with a more realistic imbalance in the dataset (more negative edges, and less positive ones).\n- In Figure 3, it is not obvious what the light blue and dark blue lines represent. I would suggest to add the x-axis, y-axis and labels in the figure and remove them from the caption if there is no space.\n- Overall, more datasets (e.g., Reddit, PPI) and more comparison methods (e.g., GraphSAGE (for link prediction), HAN, DynRep) will make the results more convincing and insightful.\n- There is no comment on the scalability/runtime of the proposed method.\n- The results in some cases are very close, it would be better if the authors could test for statistical significance and report the scores.\n\n\n[1] Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W.L. and Leskovec, J., 2018, July. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 974-983).\n\n[2] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019. Heterogeneous Graph Attention Network. In <i>The World Wide Web Conference</i> (<i>WWW '19</i>). Association for Computing Machinery, New York, NY, USA, 2022–2032. DOI:https://doi.org/10.1145/3308558.3313562 \n\n[3] Trivedi, Rakshit, Farajtabar, Mehrdad, Biswal, Prasenjeet, and Zha, Hongyuan.. \"DyRep: Learning Representations over Dynamic Graphs\". International Conference on Learning Representations (). Country unknown/Code not available. https://par.nsf.gov/biblio/10099025.\n\n\nQuestions during rebuttal\n=====================\n- Please address and clarify the suggestions mentioned in the weaknesses above.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the paper is addressing an interesting problem (cold-start for representation learning on dynamic graphs). However, the proposed methods can be improved by proposing more novel ideas. At the moment, the proposed methods is a combination of GCN model for node classification and GAE model for link prediction. In this case, some analysis or theoretical justification may make the paper more interesting. Furthermore, the reviewers think the experiments can be improved. For instance, results on more datasets, more comparison methods and a different setup will strengthen the paper. 
Decision: Reject