Knowledge Graph Convolutional Networks for Recommender Systems

Introduction

With the advance of Internet technology, people can access a vast amount of online content, such as news (Zheng et al., 2018), movies (Diao et al., 2014), and commodities (Zhou et al., 2018). A notorious problem with online platforms is that the volume of items can be overwhelming to users. To alleviate the impact of information overloading, recommender systems (RS) is proposed to search for and recommend a small set of items to meet users’ personalized interests.

A traditional recommendation technique is collaborative filtering (CF), which assigns users and items ID-based representation vectors, then models their interactions by specific operation such as inner product (Wang et al., 2017b) or neural networks (He et al., 2017). However, CF-based methods usually suffer from sparsity of user-item interactions and the cold start problem. To address these limitations, researchers usually turn to feature-rich scenarios, where attributes of users and items are used to compensate for the sparsity and improve the performance of recommendation (Cheng et al., 2016; Wang et al., 2018a).

A few recent studies (Yu et al., 2014; Zhang et al., 2016; Zhao et al., 2017; Wang et al., 2018c; Huang et al., 2018; Wang et al., 2018b) have gone a step further than simply using attributes: They point out that attributes are not isolated but linked up with each other, which forms a knowledge graph (KG). Typically, a KG is a directed heterogeneous graph in which nodes correspond to entities (items or item attributes) and edges correspond to relations. Compared with KG-free methods, incorporating KG into recommendation benefits the results in three ways (Wang et al., 2018b): (1) The rich semantic relatedness among items in a KG can help explore their latent connections and improve the precision of results; (2) The various types of relations in a KG are helpful for extending a user’s interests reasonably and increasing the diversity of recommended items; (3) KG connects a user’s historically-liked and recommended items, thereby bringing explainability to recommender systems.

Despite the above benefits, utilizing KG in RS is rather challenging due to its high dimensionality and heterogeneity. One feasible way is to preprocess the KG by knowledge graph embedding (KGE) methods (Wang et al., 2017a), which map entities and relations to low-dimensional representation vectors (Zhang et al., 2016; Wang et al., 2018c; Huang et al., 2018). However, commonly-used KGE methods focus on modeling rigorous semantic relatedness (e.g., TransE (Bordes et al., 2013) and TransR (Lin et al., 2015) assume $head+relation=tail$), which are more suitable for in-graph applications such as KG completion and link prediction rather than recommendation. A more natural and intuitive way is to design a graph algorithm directly to exploit the KG structure (Yu et al., 2014; Zhao et al., 2017; Wang et al., 2018b). For example, PER (Yu et al., 2014) and FMG (Zhao et al., 2017) treat KG as a heterogeneous information network, and extract meta-path/meta-graph based latent features to represent the connectivity between users and items along different types of relation paths/graphs. However, PER and FMG rely heavily on manually designed meta-paths or meta-graphs, which are hardly to be optimal in reality. RippleNet (Wang et al., 2018b) is a memory-network-like model that propagates users’ potential preferences in the KG and explores their hierarchical interests. But note that the importance of relations is weakly characterized in RippleNet, because the embedding matrix of a relation $\bf R$ can hardly be trained to capture the sense of importance in the quadratic form ${\bf v}^{\top}{\bf R}{\bf h}$ ($\bf v$ and $\bf h$ are embedding vectors of two entities). In addition, the size of ripple set may go unpredictably with the increase of the size of KG, which incurs heavy computation and storage overhead.

In this paper, we investigate the problem of KG-aware recommendation. Our design objective is to automatically capture both high-order structure and semantic information in the KG. Inspired by graph convolutional networks (GCN)We will revisit GCN in related work. that try to generalize convolution to the graph domain, we propose Knowledge Graph Convolutional Networks (KGCN) for recommender systems. The key idea of KGCN is to aggregate and incorporate neighborhood information with bias when calculating the representation of a given entity in the KG. Such a design has two advantages: (1) Through the operation of neighborhood aggregation, the local proximity structure is successfully captured and stored in each entity. (2) Neighbors are weighted by scores dependent on the connecting relation and specific user, which characterizes both the semantic information of KG and users’ personalized interests in relations. Note that the size of an entity’s neighbors varies and may be prohibitively large in the worst case. Therefore, we sample a fixed-size neighborhood of each node as the receptive field, which makes the cost of KGCN predictable. The definition of neighborhood for a given entity can also be extended hierarchically to multiple hops away to model high-order entity dependencies and capture users’ potential long-distance interests.

Empirically, we apply KGCN to three datasets: MovieLens-20M (movie), Book-Crossing (book), and Last.FM (music). The experiment results show that KGCN achieves average AUC gains of $4.4\%$, $8.1\%$, and $6.2\%$ in movie, book, and music recommendations, respectively, compared with state-of-the-art baselines for recommendation.

Our contribution in this paper are summarized as follows:

We propose knowledge graph convolutional networks, an end-to-end framework that explores users’ preferences on the knowledge graph for recommender systems. By extending the receptive field of each entity in the KG, KGCN is able to capture users’ high-order personalized interests.

We conduct experiments on three real-world recommendation scenarios. The results demonstrate the efficacy of KGCN-LS over state-of-the-art baselines.

We release the code of KGCN and datasets (knowledge graphs) to researchers for validating the reported results and conducting further research. The code and the data are available at https://github.com/hwwang55/KGCN.

Related Work

Our method is conceptually inspired by GCN. In general, GCN can be categorized as spectral methods and non-spectral methods. Spectral methods represent graphs and perform convolution in the spectral space. For example, Bruna et al. (Bruna et al., 2014) define the convolution in Fourier domain and calculates the eigendecomposition of the graph Laplacian, Defferrard et al. (Defferrard et al., 2016) approximate the convolutional filters by Chebyshev expansion of the graph Laplacian, and Kipf et al. (Kipf and Welling, 2017) propose a convolutional architecture via a localized first-order approximation of spectral graph convolutions. In contrast, non-spectral methods operate on the original graph directly and define convolution for groups of nodes. To handle the neighborhoods with varying size and maintain the weight sharing property of CNN, researchers propose learning a weight matrix for each node degree (Duvenaud et al., 2015), extracting locally connected regions from graphs (Niepert et al., 2016), or sampling a fixed-size set of neighbors as the support size (Hamilton et al., 2017). Our work can be seen as a non-spectral method for a special type of graphs (i.e., knowledge graph).

Our method also connects to PinSage (Ying et al., 2018) and GAT (Velickovic et al., 2018). But note that both PinSage and GAT are designed for homogeneous graphs. The major difference between our work and the literature is that we offer a new perspective for recommender systems with the assistance of a heterogeneous knowledge graph.

Knowledge Graph Convolutional Networks

In this section, we introduce the proposed KGCN model. We first formulate the knowledge-graph-aware recommendation problem. Then we present the design of a single layer of KGCN. At last, we introduce the complete learning algorithm for KGCN, as well as its minibatach implementation.

Given the user-item interaction matrix $\bf Y$ as well as the knowledge graph $\mathcal{G}$, we aim to predict whether user $u$ has potential interest in item $v$ with which he has had no interaction before. Our goal is to learn a prediction function ${\hat{y}}_{uv}=\mathcal{F}(u,v|\Theta,\bf Y,\mathcal{G})$, where ${\hat{y}}_{uv}$ denotes the probability that user $u$ will engage with item $v$, and $\Theta$ denotes the model parameters of function $\mathcal{F}$.

2. KGCN Layer

To characterize the topological proximity structure of item $v$, we compute the linear combination of $v$’s neighborhood:

and $\bf e$ is the representation of entity $e$. User-relation scores act as personalized filters when computing an entity’s neighborhood representation, since we aggregate the neighbors with bias with respect to these user-specific scores.

In a real-world knowledge graph, the size of $\mathcal{N}(e)$ may vary significantly over all entities. To keep the computational pattern of each batch fixed and more efficient, we uniformly sample a fixed-size set of neighbors for each entity instead of using its full neighbors. Specifically, we compute the neighborhood representation of entity $v$ as ${\bf v}_{\mathcal{S}(v)}^{u}$, where $\mathcal{S}(v)\triangleq\{e\ |\ e\sim\mathcal{N}(v)\}$ and $|\mathcal{S}(v)|=K$ is a configurable constant.Technically, $\mathcal{S}(v)$ may contain duplicates if $\mathcal{N}(v)<K$. In KGCN, $\mathcal{S}(v)$ is also called the (single-layer) receptive field of entity $v$, as the final representation of $v$ is sensitive to these locations. Figure 1(a) gives an illustrative example of a two-layer receptive field for a given entity, where $K$ is set as $2$.

Sum aggregator takes the summation of two representation vectors, followed by a nonlinear transformation:

where $\bf W$ and $\bf b$ are transformation weight and bias, respectively, and $\sigma$ is the nonlinear function such ReLU.

Concat aggregator (Hamilton et al., 2017) concatenates the two representation vectors first before applying nonlinear transformation:

Neighbor aggregator (Velickovic et al., 2018) directly takes the neighborhood representation of entity $v$ as the output representation:

Aggregation is a key step in KGCN, because the representation of an item is bound up with its neighbors by aggregation. We will evaluate the three aggregators in experiments.

3. Learning Algorithm

Through a single KGCN layer, the final representation of an entity is dependent on itself as well as its immediate neighbors, which we name 1-order entity representation. It is natural to extend KGCN from one layer to multiple layers to reasonably explore users’ potential interests in a broader and deeper way. The technique is intuitive: Propagating the initial representation of each entity (0-order representation) to its neighbors leads to 1-order entity representation, then we can repeat this procedure, i.e., further propagating and aggregating 1-order representations to obtain 2-order ones. Generally speaking, the $h$-order representation of an entity is a mixture of initial representations of itself and its neighbors up to $h$ hops away. This is an important property for KGCN, which we will discuss in the next subsection.

Figure 1(b) illustrates the KGCN algorithm in one iteration, in which the entity representation ${\bf v}^{u}[h]$ and neighborhood representations (green nodes) of a given node are mixed to form its representation for the next iteration (blue node).

Note that Algorithm 1 traverses all possible user-item pairs (line 2). To make computation more efficient, we use a negative sampling strategy during training. The complete loss function is as follows:

where $\mathcal{J}$ is cross-entropy loss, $P$ is a negative sampling distribution, and $T^{u}$ is the number of negative samples for user $u$. In this paper, $T^{u}=|\{v:y_{uv}=1\}|$ and $P$ follows a uniform distribution. The last term is the L2-regularizer.

Experiments

In this section, we evaluate KGCN on three real-world scenarios: movie, book, and music recommendations.

We utilize the following three datasets in our experiments for movie, book, and music recommendation, respectively:

MovieLens-20Mhttps://grouplens.org/datasets/movielens/ is a widely used benchmark dataset in movie recommendations, which consists of approximately 20 million explicit ratings (ranging from 1 to 5) on the MovieLens website.

Book-Crossinghttp://www2.informatik.uni-freiburg.de/~cziegler/BX/ contains 1 million ratings (ranging from 0 to 10) of books in the Book-Crossing community.

Last.FMhttps://grouplens.org/datasets/hetrec-2011/ contains musician listening information from a set of 2 thousand users from Last.fm online music system.

Since the three datasets are explicit feedbacks, we transform them into implicit feedback where each entry is marked with 1 indicating that the user has rated the item positively, and sample an unwatched set marked as 0 for each user. The threshold of positive rating is 4 for MovieLens-20M, while no threshold is set for Book-Crossing and Last.FM due to their sparsity.

We use Microsoft Satorihttps://searchengineland.com/library/bing/bing-satori to construct the knowledge graph for each dataset. We first select a subset of triples from the whole KG with a confidence level greater than 0.9. Given the sub-KG, we collect Satori IDs of all valid movies/books/musicians by matching their names with tail of triples (head, film.film.name, tail), (head, book.book.title, tail), or (head, type.object.name, tail). Items with multiple matched or no matched entities are excluded for simplicity. We then match the item IDs with the head of all triples and select all well-matched triples from the sub-KG. The basic statistics of the three datasets are presented in Table 1.

2. Baselines

We compare the proposed KGCN with the following baselines, in which the first two baselines are KG-free while the rest are all KG-aware methods. Hyper-parameter settings for baselines are introduced in the next subsection.

SVD (Koren, 2008) is a classic CF-based model using inner product to model user-item interactions.We have tried NCF (He et al., 2017), i.e., replacing inner product with neural networks, but the result is inferior to SVD. Since SVD and NCF are similar, we only present the better one here.

LibFM (Rendle, 2012) is a feature-based factorization model in CTR scenarios. We concatenate user ID and item ID as input for LibFM.

LibFM + TransE extends LibFM by attaching an entity representation learned by TransE (Bordes et al., 2013) to each user-item pair.

PER (Yu et al., 2014) treats the KG as heterogeneous information networks and extracts meta-path based features to represent the connectivity between users and items.

CKE (Zhang et al., 2016) combines CF with structural, textual, and visual knowledge in a unified framework for recommendation. We implement CKE as CF plus a structural knowledge module in this paper.

RippleNet (Wang et al., 2018b) is a memory-network-like approach that propagates users’ preferences on the KG for recommendation.

3. Experiments Setup

In KGCN, we set functions $g$ and $f$ as inner product, $\sigma$ as ReLU for non-last-layer aggregator and $tanh$ for last-layer aggregator. Other hyper-parameter settings are provided in Table 1. The hyper-parameters are determined by optimizing $AUC$ on a validation set. For each dataset, the ratio of training, evaluation, and test set is $6:2:2$. Each experiment is repeated $3$ times, and the average performance is reported. We evaluate our method in two experiment scenarios: (1) In click-through rate (CTR) prediction, we apply the trained model to predict each interaction in the test set. We use $AUC$ and $F1$ to evaluate CTR prediction. (2) In top-$K$ recommendation, we use the trained model to select $K$ items with highest predicted click probability for each user in the test set, and choose $Recall@K$ to evaluate the recommended sets. All trainable parameters are optimized by Adam algorithm. The code of KGCN-LS is implemented under Python 3.6, TensorFlow 1.12.0, and NumPy 1.14.3.

The hyper-parameter settings for baselines are as follows. For SVD, we use the unbiased version (i.e., the predicted rating is modeled as $r_{pq}={\bf p}^{\top}{\bf q}$). The dimension and learning rate for the four datasets are set as: $d=8$, $\eta=0.5$ for MovieLens-20M, Book-Crossing; $d=8$, $\eta=0.1$ for Last.FM. For LibFM, the dimension is $\{1,1,8\}$ and the number of training epochs is $50$. The dimension of TransE is $32$. For PER, we use manually designed user-item-attribute-item paths as features (i.e., “user-movie-director-movie”, “user-movie-genre-movie”, and “user-movie-star-movie” for MovieLens-20M; “user-book-author-book” and “user-book-genre-book” for Book-Crossing, “user-musician-date_of_birth-musician” (date of birth is discretized), “user-musician-country-musician”, and “user-musician-genre-musician” for Last.FM). For CKE, the dimension of the three datasets are $64$, $128$, $64$. The training weight for KG part is $0.1$ for all datasets. The learning rate are the same as in SVD. For RippleNet, $d=8$, $H=2$, $\lambda_{1}=10^{-6}$, $\lambda_{2}=0.01$, $\eta=0.01$ for MovieLens-20M; $d=16$, $H=3$, $\lambda_{1}=10^{-5}$, $\lambda_{2}=0.02$, $\eta=0.005$ for Last.FM. Other hyper-parameters are the same as reported in their original papers or as default in their codes.

4. Results

The results of CTR prediction and top-$K$ recommendation are presented in Table 2 and Figure 2, respectively (SVD, LibFM and other variants of KGCN are not plotted in Figure 2 for clarity). We have the following observations:

In general, we find that the improvements of KGCN on book and music are higher than movie. This demonstrates that KGCN can well address sparse scenarios, since Book-Crossing and Last.FM are much sparser than MovieLens-20M.

The performance of KG-free baselines, SVD and LibFM, are actually better than the two KG-aware baselines PER and CKE, which indicates that PER and CKE cannot make full use of the KG with manually designed meta-paths and TransR-like regularization.

LibFM + TransE is better than LibFM in most cases, which demonstrates that the introduction of KG is helpful for recommendation in general.

PER performs worst among all baselines, since it is hard to define optimal meta-paths in reality.

RippleNet shows strong performance compared with other baselines. Note that RippleNet also uses multi-hop neighborhood structure, which interestingly shows that capturing proximity information in the KG is essential for recommendation.

The last four rows in Table 2 summarize the performance of KGCN variants. The first three (sum, concat, neighbor) correspond to different aggregators introduced in the preceding section, while the last variant KGCN-avg is a reduced case of KGCN-sum where neighborhood representations are directly averaged without user-relation scores (i.e., ${\bf v}_{\mathcal{N}(v)}^{u}=\sum_{e\in\mathcal{N}(v)}{\bf e}$ instead of Eq. (2)). Therefore, KGCN-avg is used to examine the efficacy of the “attention mechanism”. From the results we find that:

KGCN outperforms all baselines by a significant margin, while their performances are slightly distinct: KGCN-sum performs best in general, while the performance of KGCN-neighbor shows a clear gap on Book-Crossing and Last.FM. This may be because the neighbor aggregator uses the neighborhood representation only, thus losing useful information from the entity itself.

KGCN-avg performs worse than KGCN-sum, especially in Book-Crossing and Last.FM where interactions are sparse. This demonstrates that capturing users’ personalized preferences and semantic information of the KG do benefit the recommendation.

We vary the size of sampled neighbor $K$ to investigate the efficacy of usage of the KG. From Table 3 we observe that KGCN achieves the best performance when $K=4$ or $8$. This is because a too small $K$ does not have enough capacity to incorporate neighborhood information, while a too large $K$ is prone to be misled by noises.

4.2. Impact of depth of receptive field.

We investigate the influence of depth of receptive field in KGCN by varying $H$ from 1 to 4. The results are shown in Table 4, which demonstrate that KGCN is more sensitive to $H$ compared to $K$. We observe the occurrence of serious model collapse when $H=3$ or $4$, as a larger $H$ brings massive noises to the model. This is also in accordance with our intuition, since a too long relation-chain makes little sense when inferring inter-item similarities. An $H$ of 1 or 2 is enough for real cases according to the experiment results.

4.3. Impact of dimension of embedding.

Lastly, we examine the influence of dimension of embedding $d$ on performance of KGCN. The result in Table 5 is rather intuitive: Increasing $d$ initially can boost the performance since a larger $d$ can encode more information of users and entities, while a too large $d$ adversely suffers from overfitting.

Conclusions and Future Work

This paper proposes knowledge graph convolutional networks for recommender systems. KGCN extends non-spectral GCN approaches to the knowledge graph by aggregating neighborhood information selectively and biasedly, which is able to learn both structure information and semantic information of the KG as well as users’ personalized and potential interests. We also implement the proposed method in a minibatch fashion, which is able to operate on large datasets and knowledge graphs. Through extensive experiments on real-world datasets, KGCN is shown to consistently outperform state-of-the-art baselines in movie, book, and music recommendation.

We point out three avenues for future work. (1) In this work we uniformly sample from the neighbors of an entity to construct its receptive field. Exploring a non-uniform sampler (e.g., importance sampling) is an important direction of future work. (2) This paper (and all literature) focuses on modeling item-end KGs. An interesting direction of future work is to investigate whether leveraging user-end KGs is useful in improving the performance of recommendation. (3) Designing an algorithm to well combine KGs at the two ends is also a promising direction.

References