STAR-GCN: Stacked and Reconstructed Graph Convolutional Networks for Recommender Systems

1 Introduction

Recommender systems, which analyze users' preference patterns to suggest potential targets, are indispensable in content providers, electronic retailers, web search engines, etc. The key mathematical problem underlying recommender systems is matrix completion [Cand`es and Recht, 2009]. Assume there are N users and M items, the recommendation algorithm aims to fill in the missing entries in the N ×M rating matrix given the existing entries.

The classical way to solve this problem is via Matrix Factorization (MF) [Koren et al., 2009], in which the rating scores are generated by functions over the latent factors or embeddings of users and items. Recent advancements in deep learning, especially Graph Convolutional Networks (GCN) [Defferrard et al., 2016; Bronstein et al., 2017; Kipf and Welling, 2017; Hamilton et al., 2017], have brought new ideas for tackling this essential artificial intelligence problem. GCN generalizes the definition of convolution from the regular grid to irregular grid, like graph structures. The GCN framework generates node representations by a localized parameter-sharing operator, known as graph aggregator [Hamilton et al., 2017; Zhang et al., 2018]. A graph aggregator calculates a node's representation by transforming and aggregating the features of its local neighborhoods. By stacking multiple graph aggregators and nonlinear functions, we build a deep neural network that can extract features across far reaches of a graph. Because the local neighborhood set can be viewed as the receptive field of a convolution kernel, this kind of neighborhood aggregation methods is named as graph convolution, which also have connections to spectral graph theory [Kipf and Welling, 2017].

Monti et al. [2017] proposed the first GCN-based method for recommender systems. In their approach, GCNwas used to aggregate information from two auxiliary user-user and item-item graphs. The latent factors of users and items were updated after each aggregation step, and a combined objective function of GCN and MF was used to train the model. After that, Berg et al. [2017] proposed the Graph Convolutional Matrix Completion (GC-MC) model. GC-MC directly characterized the relationship between users and items as a bipartite interaction graph. Two multi-link graph convolution layers were used to aggregate user features and item features. The ratings were estimated by predicting the edge labels. Thanks to the power of GCN in learning high-quality user and item representations, GC-MC has achieved state-of-the-art performance in several public recommendation benchmarks.

While being powerful, the GC-MC model has two significant limitations. To distinguish each node, the model uses one-hot vectors as node input. This makes the input dimensionality proportional to the total number of nodes and thus is not scalable to large graphs. Moreover, the model is unable to predict the ratings for new users or items that are not seen in the training phase because we cannot represent unknown nodes as one-hot vectors. The task of predicting ratings for new users or items is also known as the cold start problem.

In this paper, we propose a new architecture, STAcked and Reconstructed Graph Convolutional Networks (STAR-GCN), to solve these problems. Unlike GC-MC, STAR-GCN directly learns low-dimensional user and item embeddings as the input to the network in an end-to-end fashion. To improve the learned embeddings and also generalize the model to predict embeddings of unseen nodes for the cold start problem, STARGCN masks a part of or the whole user and item embeddings and reconstructs these masked embeddings with a block of graph encoder-decoder in the training phase. This technique is inspired by the recent success of the 'masked language model' in learning language embeddings [Devlin et al., 2018]. Moreover, we build a stack of encoder-decoder blocks in conjunction with intermediate task-specific supervision to enhance the final performance. During implementation, we find that training the GCN-based models for rating prediction faces the label leakage issue, which results in the overfitting problem and significantly degrades the final performance. To avoid the leakage issue, we provide a sample-and-remove training strategy and empirically demonstrate the effectiveness.

We conduct experiments over two tasks: transductive rating prediction and inductive rating prediction. The transductive rating prediction is generally used in traditional matrix completion tasks, i.e., all the testing users and items are observed in training data. The inductive rating prediction is a newly introduced task to evaluate different models' ability on the cold start problem. We ask new users to rate a few items or require new items to be rated by a few users. These data are only used in the inference step to elicit initial information about new users/items, which is similar to the ask-to-rate technique [Nadimi-Shahraki and Bahadorpour, 2014] for cold start. Experiments show that STAR-GCN achieves state-ofthe-art performance in four out of five real-world datasets in the transductive setting. In the inductive setting, our STARGCN consistently and significantly outperforms the baselines.

Our main contributions are: (1) we propose a new architecture for recommender systems to learn latent factors of users and items in both transductive and inductive settings; (2) we are the first to explicitly pinpoint a training label leakage issue when implementing GCN-based models in rating prediction tasks and propose a training strategy to avoid this issue, leading to substantial performance improvement; (3) our STAR-GCN models achieve state-of-the-art performance in four out of five real-world recommendation datasets in the transductive setting and significantly outperform other models in the inductive setting.

2 Preliminary

We denote vectors with bold lowercase letters, matrices with bold uppercase letters, and sets with calligraphy letters. We omit the bias variable of linear transformation for brevity.

2.1 Rating Prediction Tasks

GCN-based models treat the recommendation environment as an undirected bipartite graph G that contains two disjoint node sets, users U and items V. Suppose there are N users and M items, an edge value ri,j ∈ R represents an observed rating value from user ui to item vj. The rating set R may contain several ordinal rating levels, i.e., r ∈ {1, ..., R} = R. Each rating level indicates a link type in the bipartite graph. All the training rating pairs form a training graph, and they are included in a testing graph. Examples are shown in Figure 1. The goal of rating prediction is to predict the ratings a user would give to other items, given a small subset of observed

• (a) Transductive rating prediction (b) Inductive rating prediction

Figure 1: Two rating prediction tasks.

rating pairs. We focus on two types of rating prediction tasks: transductive rating prediction and inductive rating prediction. Figure 1 illustrates the difference between these two tasks.

Transductive Rating Prediction

Figure 1a shows an example, where users and items appearing in the testing graph are observed in the training graph. Prior collaborative filtering methods, like Matrix Factorization [Koren et al., 2009], primarily concentrate on this task.

Inductive Rating Prediction

Figure 1b illustrates an example of the inductive rating prediction task. u1 and v1 are two new nodes, which are not seen at the training time but appear in the testing rating pairs. Before making predictions, we access a few rated edges connected with these new nodes in the testing graph. Traditional collaborative filtering methods cannot solve this task without re-training the models. The standard way is to rely on content information to model the users' and items' preferences. The Collaborative Deep Learning (CDL) [Wang et al., 2015] model and DropoutNet [Volkovs et al., 2017] are two recent representative methods. The core idea of these two models is to use a deep neural network to learn effective features of the input node content.

Recent progress in deep learning on graphs, mainly the GCN models, can address the above two tasks by learning transductive and inductive node representations. STAR-GCN inherits the ability of GCN for both transductive and inductive learning. Compared with CDL and DropoutNet, our STARGCN not only takes account of the node's content information but also utilizes the structural information to learn the embeddings of new nodes. Thus, STAR-GCN can solve the cold start problem when the content information is unavailable, which is infeasible for CDL and DropoutNet.

2.2 Graph Convolutional Matrix Completion

In this subsection, we briefly revisit GC-MC [Berg et al., 2017]. Our STAR-GCN employs a similar graph aggregator to encode structural information. GC-MC uses a multi-link graph convolutional encoder to produce node representations. Each link type r is assigned with a specific transformation. The messages from items to user ui are computed as

Here, yrui is the aggregated output of a link type r. xvj ∈ Rdin is the initial vector of vj and din is the input dimension. Wra of size da × din is a link-specific weight matrix for rating level r, which transforms a vector of the dimension din to an hidden size da. cij is a normalized constant, computed as √|Nr(ui)||Nr(vj)| with Nr(·) denoting a set of neighbors connected by edge-value r. After computing the link specific messages, we sum the messages from total R types of links and pass the output to a non-linear function α(·). Finally, we employ a fully connected layer with parameter Wh of size dh × da and another non-linear activation to produce the final node vector hui for user ui. Messages from users to items are processed analogously with a separate set of parameters.

(c) Without reconstruction decoder

Figure 2: Model Architectures. x(0) is the initial node vector. h(ℓ) is the output of the ℓ-th graph encoder and ˆx(ℓ) is the output node vector of the ℓ-th decoder. Lt is a task specific loss and Lr is a reconstruction loss. (b) and (c) are two special cases of (a).

In the next step, the GC-MC model takes the computed user vector and item vector as the input to predict the rating value. See Berg et al. [2017] for more details. In the following, we do not distinguish user u and item v and call them as a node.

3 Our Models

The architecture of STAR-GCN is a multi-block graph encoder-decoder shown in Figure 2a. The multi-block architecture allows reassessment of initial estimates and features across the whole graph. In particular, each block contains two components: a graph encoder and a decoder. The graph encoder generates node representations by encoding semantic graph structures as well as input content features, and the decoder aims to recover the input node embeddings. For each block, we impose a task-specific loss after graph encoders and a node reconstruction loss after decoders.

STAR-GCN supports two different types of combinations between two consecutive blocks, by stacking or by recurrence. The main difference is whether to share parameters among blocks or not. By stacking, we consecutively place multiple encoder-decoder blocks with separate sets of parameters. By recurrence, we unfold a single encoder-decoder block, so the same set of parameters are shared across all the blocks, which curtails the total memory usage. Besides, our STAR-GCN is a general framework, which can be simplified to some individual cases, as shown in Figure 2b and 2c. Empirical studies on two combinations and the simplified models are in Table 3.

3.1 Input Node Representations

To make the network scalable to large graphs, we use an embedding lookup table Xe ∈ Rde×|M+N| to map each node to a low-dimensional vector xe ∈ Rde , where de ≪ |M +N|. Xe is trained end-to-end along with the network. However, naively replacing the one-hot vectors with embeddings, fails to tackle the cold start problem because we cannot set the embeddings of nodes that are not seen in the training phase.

So, to generalize the embedding learning technique to new nodes and preserve the high prediction accuracy, we take an approach of masking some percentage of the input nodes at random and then reconstructing the clean node embeddings. Like Devlin et al. [2018], in each training batch, we mask Pm percentage, say 20%, of the whole input nodes at random. Then we reconstruct these masked embeddings. For the masked nodes, they perform the following choices: (1) with probability pz, we set the node embeddings to be zero; and (2) with the remaining probability, we keep the node unchanged.

Training with the masked embedding mechanism has two advantages. First, it can learn embeddings for nodes that are not observed in the training phase. In a cold start scenario, we initialize the embeddings of new nodes to be zero and gradually refine the estimated embeddings by multiple blocks of GCN encoder-decoders. For instance, the first block predicts the embedding of the new node by leveraging the neighborhood data (or node attributes, if available). Then the predicted embedding is fed to the second block to predict ratings and a refined embedding. The rating and embedding prediction losses are jointly optimized. Thus, STAR-GCN can solve the cold-start issue by iteratively refining the embeddings and is fundamentally different from GC-MC. Second, STAR-GCN leads to improvement in the transductive setting. In the training phase, part of the node embeddings are masked and the network is asked to reconstruct these masked embeddings, which requires the network to encode the relationships between users and items effectively. Thus, the reconstruction loss acts as a multi-task regularizer that improves the performance of the primary rating prediction task.

When external node features are available, they are first processed via a separate network and then concatenated with the node embeddings. The feature vector f is mapped to a fixed size vector xf ∈ Rdf using a two-layer feedforward neural network, i.e., xf = W2α(W1f), where both layers have an output dimension df . Now the input node vector x becomes [xe; xf ] and the input dimension din = de + df rather than xe when the content information is not available.

3.2 Graph Encoder and Decoder

The graph encoder transforms an input node vector x ∈ Rdin into hidden state h of size dh by aggregating neighboring information of different rating levels, i.e., h = Enc(x). We choose the encoder to be the multi-link GCN aggregator in GC-MC, which is formulated in Eq.(1). A decoder maps the structural-encoded node representation h to a din-dimensional reconstructed embedding vector ˆx, i.e., ˆx = Dec(h). We Figure 3: The graph aggregation operator for u1 and v1 when predicting the rating value between u1 and v1. The dash circles include the nodes and edges to be aggregated. The links in bold lines are the sampled edges (rating pairs) to be trained. (a) illustrates the leakage issue. (b) gives a solution by removing the sampled edges.

use a two-layer feedforward neural network as a decoder, i.e., ˆx =W4α(W3h), where the output dimensions are both din. STAR-GCN is a general framework with a stack of GCN encoder-decoder blocks. Any variant of GCNs, e.g., GraphSAGE [Hamilton et al., 2017] and GAT [Veliˇckovi´c et al., 2018], can be used as an encoder or decoder in STAR-GCN. Our graph encoder-decoder is different from the graph autoencoder model [Kipf and Welling, 2016] mainly in the role of the decoder. Our decoder is to recover the initial input node vectors, while their decoder is a task-specific classifier to produce predictions. Another difference is that our graph aggregator considers different link types [Schlichtkrull et al., 2018], whereas their aggregator only models single link type.

3.3 Loss

Suppose there are L blocks, the loss function is expressed as

where L(ℓ) t is a supervised task-specific loss, i,e., the rating prediction loss, and L(ℓ) r is a reconstruction loss from the ℓ-th block. λ(ℓ) is a constant weighting factor. In the following description, we omit the layer superscript for brevity.

Suppose we have a batch of sampled edges Eb and two sets of masked nodes Um and Vm, the specific losses are

For the rating prediction loss, ui and vj are generated by linear transforms with the output of a graph encoder, i.e, ui = Wu r hui and vj =Wv r hvj with user or item-specific matrix parameters Wu r , Wv r ∈ Rdr×do . We train the overall models end-to-end with backpropagation.

During the inference period, a L-block STAR-GCN can produce L predictions. Generally, we take the prediction from the last block as a final result.

3.4 Training by Avoiding a Leakage Issue

When training the GCN-based models for rating prediction, we discover a training label leakage issue. The ground-truth training labels are involved in the model input, which significantly degrades the testing prediction performance. Specifically, suppose we have a training input x and a label y, the model should be trained as y = fθ(x). However, if the training label leakage occurs, the model becomes y = fθ(x, y) resulting in an overfitting problem. The label leakage problem is a GCN specific issue because of the neighborhood aggregation operator. The user-item rating values in the training set are used to construct edges of the bipartite graph. Thus, when we utilize the neighboring data to update a node's representation, the rating values, which we need to predict, are included in the graph structure. This causes the label leakage issue. As in Figure 3a, y is the edge value 4 between u1 and v1, which is taken as the input to a graph aggregator.

To avoid the leakage issue, we provide a sample-and-remove training strategy. At each iteration, we sample a fixed size batch of rating pairs and remove the sampled pairs (edges) from the training graph before we start training the model. As in Figure 3b, the sampled edges with bold links are removed from the graph when we aggregate neighbors. After avoiding this leakage issue, the network shows a substantial boost in performance. The compared results of the leakage issue are given in Table 3.

4 Experiments

We conduct extensive experiments on five popular recommendation benchmarks for the transductive and inductive rating prediction tasks. The datasets are summarized in Table 1. Flixster and Douban are preprocessed and provided by Monti et al. [2017]. The user and item features are the adjacency vectors of the respective user-user and item-item graphs. The MovieLens 1 datasets contain different scales of rating pairs, i.e., 100 thousand, 1 million, and 10 million. We denote them as ML-100K, ML-1M, and ML-10M. For user features, we take the age as a scalar and the gender as a binary numerical value, and the occupation as a one-hot encoding vector. For movie features, we concatenate the title name, release year, and onehot encoded genres. We process title names by averaging the off-the-shelf 300-dimensional GloVe CommonCrawl word vector [Pennington et al., 2014] of each word.

We take the commonly adopted Root Mean Squared Error (RMSE) metric to evaluate the prediction accuracy between the ground truth ri and the predicted rating ˆ ri ,

1 Movielens [Harper and Konstan, 2016]: https://grouplens.org/ datasets/movielens/

4.1 Model Architecture and Implementation Details

We test the overall network design with different sets of hyperparameters using the validation sets. We regard Flixtser, Douban, and ML-100K as small datasets and ML-1M and ML-10M as large datasets. After tuning the hyperparameters, we roughly apply two sets of hyperparameters, one for small datasets and the other for large datasets. In all models, we choose the non-linear function α(·) as a LeakyReLU activation with the negative slope equals to 0.1. For the input vectors, we set the dimension of node embeddings de to be 32 for small datasets and 64 for large datasets. When incorporating features, we take the projection dimension df to be 8 for small datasets and 32 for large datasets. Regarding the masking mechanism, for transductive prediction, we randomly select Pm=10% of the nodes for reconstruction and set pz=0. For inductive prediction, we uniformly choose Pm=40% nodes and mask them to be zero, i.e., pz=1, to approximate the testing data distribution. For encoders, the hidden size da sets to be 250. The dimension of the output layer dh sets to be 75. We apply a dropout layer to the input of a GCN layer with a dropout rate of 0.5 for small datasets and 0.3 for large datasets. For decoders, all the hidden sizes are fixed as the node input dimension, i.e., din. When predicting ratings, we set the projection size dr to be 64.

We train the STAR-GCN models with Adam [Kingma and Ba, 2015] optimizer and use the validation set to perform learning rate decay scheduler. The initial learning rate is set to be 0.002 and gradually decreases to be 0.0005 with the decay rate of 0.5 each time the validation RMSE score does not fall in a window of 100 iterations, and the early stopping occurs for 150 iterations. The gradient normalization value clips to be no larger than 1.0. The training batch size is fixed to be 10K for small datasets, 100K for ML-1M, and 500K for ML-10M. We train the model three times with different random seeds, except for ML-10M training two times, and report the average test RMSE scores along with the standard deviation.

4.2 Transductive Rating Prediction

All the datasets are used for transductive rating prediction evaluations, where the users and items are all observed in the training dataset. For fair comparison, we strictly follow the experimental setup of Berg et al. [2017]. For Douban and Flixster, we use the split test set provided by Monti et al. [2017] with 10% of rating pairs as the testing set. For ML-100K, we use the first of the five provided data split with 20% for testing. For ML-1M and ML-10M, we randomly split the edges with 10% for testing. In the transductive setting, we perform a thorough comparison of STAR-GCN with multiple baselines and state-of-the-art models listed in Table 2. Baseline Results are taken from Berg et al. [2017]. We also conduct comprehensive ablation analysis in Table 3.

Table 2 summarizes all results of the baselines and our STAR-GCN. The baseline scores are directly taken from Monti et al. [2017] and Berg et al. [2017]. The results of STAR-GCN are produced by different variant models with a total of two graph convolutional layers, labeled as either '1b2l' or '2b1l' in Table 3. '1b2l' denotes a model with one block of encoderdecoder and each encoder includes a two-layer GCN, as in Figure 2b. In contrast, '2b1l' indicates a model with two encoder-decoder blocks and each encoder contains a one-layer GCN, as in Figure 2a. In particular, '1b2l (- rec.)' indicates the model only has an encoder without the reconstruction module, as in Figure 2c. The reported RMSE scores for STAR-GCN in Table 2 is the best results of different STAR-GCN models listed in Table 3. We note that the proposed STAR-GCN architecture achieves the state-of-the-art results on four out of five datasets. We have the following findings from Table 3.

Effect of removing sampled training edges within minibatches. Comparing the results of '1b2l (- rec. - rm.)' and '1b2l (- rec.)', we see a significant decrease in the testing RMSE scores after removing the sampled user-item pairs from the bipartite graph in each training batch. This proves the effectiveness of our sample-remove training strategy to avoid the training data leakage issue.

Effect of reconstructing masked nodes. Comparison of the results of the models labeled '- rec.' with the models having no such label indicates that the models possessing the reconstruction module consistently beat the models without reconstruction utilizing the same total number of graph encoders, which proves that our reconstruction mechanism is beneficial to the final prediction performance.

Effect of the recurrent structure. Comparing the results of '2b1l (recurrent)' and '2b1l', we see that the recurrent structure can achieve competitive results with fewer parameters.

Effect of incorporating features. By comparing the results from the same models with and without features, we note that combining external node features does not always produce better performance.

4.3 Inductive Rating Prediction

We conduct inductive rating prediction experiments on three datasets, Douban, ML-100K, and ML-1M. For each dataset, we keep 20% of user (or item) nodes as the testing nodes and remove them from the training graph. Then, we choose a fraction of ratings linked with the testing nodes as the edges that are observed in the testing phase. Ratings that are not chosen by this step are kept as the testing data. The predictor never sees these 20% nodes and needs to rely on the observed links (together with the node features, if available) to predict ratings. We conduct experiments on three different fractions, 50%, 30%, and 10%, which means that there are 50%, 30%, and 10% ratings linked with new nodes available to the predictor in the testing phase. Intuitively, the more edges we access, the more information we have, and the better the performance will be. We implement two baseline models, CDL [Wang et al., 2015] and DropoutNet [Volkovs et al., 2017], and compare some variants of our STAR-GCN architecture. We use the '2b1l' versions of STAR-GCN in this task.

The testing RMSE scores are listed in Table 4. We find a worse performance tendency when the predictor accesses fewer neighboring edges for the new users/items in the testing phase. We show that our STAR-GCN model produces significantly better results than two baselines. Moreover, comparing the results of the models with and without reconstruction modules, we find that the reconstruction mechanism plays a crucial role in improving the final performance. An interesting observation is that incorporating content information for new nodes is not always beneficial to the final results. The reason may be that our reconstructed node embeddings have already contained enough information for accurate predictions, which proves that our STAR-GCN can effectively solve the cold start problem using structural information.

5 Conclusion and FutureWork

We introduce a new GCN-based architecture, which achieves the state-of-the-art results on transductive and inductive rating prediction tasks. Our architecture is generic and can be used in other applications, such as abnormal behavior detection, spatiotemporal forecasting [Shi and Yeung, 2018; Zhao et al., 2016], and so on [Chan and King, 2018; Gao et al., 2018]. Besides, we discover a training label leakage issue when implementing GCN-based models for rating prediction tasks. The discovery should serve as a reminder of later research. In the future, we plan to integrate ranking algorithms [Su et al., 2017] for other recommendation tasks.

Acknowledgements

The work described in this paper was partially supported by the Research Grants Council of the Hong Kong Special Administrative Region, China (No. CUHK 14208815 of the General Research Fund) and CUHK 7010445 Meitu (China) Limited.