Modeling Scale-free Graphs with Hyperbolic Geometry for Knowledge-aware Recommendation

A KG is formally defined as a set of the knowledge triplets: $\{(e_{1},r,e_{2})|e_{1},e_{2}$ $\in$ $\mathcal{E}$, $r$ $\in$ $\mathcal{R}\}$, denoting that relation $r$ connects entity $e_{1}$ and $e_{2}$. $\mathcal{E}$ and $\mathcal{R}$ represent the set of entities and relations. The KG is used to provide external knowledge for items, e.g., (The Godfather, ActedBy, Marlon Brando). User-item interactions can be similarly represented as: $\{(u,r^{*},i)|u$ $\in$ $\mathcal{U}$, $i$ $\in$ $\mathcal{I}\}$. $\mathcal{U}$ and $\mathcal{I}$ denote the set of users and items, respectively, and $r^{*}$ generalizes all interaction types, e,g., browse, click, or purchase, as one relation between $u$ and $i$. The user-item interaction matrix $\boldsymbol{Y}\in\mathcal{R}^{|\mathcal{U}|\times|\mathcal{I}|}$ is defined according to user-item interaction, where $y_{u,i}$ $=$ $1$ indicates there is an observed interaction, otherwise $y_{u,i}$ $=$ $0$. Moreover, each item can be matched with an entity in the KG to elucidate alignments between items and entities (Wang et al., 2019a, 2020). Unifying user behaviors and item knowledge into the Unified Knowledge Graph (UKG), which essentially is a tripartite graph and can be defined as $\mathcal{G}$ $=$ $\{(h,r,t)|h,t$ $\in$ $\mathcal{E}^{\prime}$, $r$ $\in$ $\mathcal{R}^{\prime}\}$ where $\mathcal{E}^{\prime}$ $=$ $\mathcal{E}$ $\cup$ $\mathcal{U}$ and $\mathcal{R}^{\prime}$ $=$ $\mathcal{R}$ $\cup$$\{r^{*}\}$. For example, the UKG shown in Figure 2(a) unifies various relations as well as users, items, and entities in a graph for movie recommendation.

Notations. In this paper, we use the bold lowercase characters, bold uppercase characters and calligraphy characters to denote the vectors, matrices and sets, respectively. Non-bold characters are used to denote scalars or graph nodes.

Task description. Given the UKG, the recommendation task studied in this paper is to train a RS model estimating the probability $\hat{y}_{u,i}$ that user $u$ may adopt item $i$.

Hyperbolic geometry is a non-Euclidean geometry with a constant negative curvature measuring how a geometric object deviates from a flat plane (Robbin and Salamon, 2011). We adopt the Lorentz model, i.e., one typical equivalent model that well describes hyperbolic geometry, for its unique simplicity and numerical stability (Nickel and Kiela, 2018; Chami et al., 2019; Law et al., 2019; Liu et al., 2019).

Lorentzian manifold and tangent space. Let $\left<.,.\right>_{\mathbb{H}}$: $\mathbb{R}^{d}$ $\times$ $\mathbb{R}^{d}$ $\rightarrow$ $\mathbb{R}$ represent the Lorentzian inner product in the hyperbolic space:

For ease of presentation, the $d$-dimensional Lorentzian manifold is denoted by $\mathbb{H}^{d,c}$ with the negative curvature $-1/c$, and the Euclidean tangent space with $d$ dimensions centered at vector $\boldsymbol{x}$ $\in$ $\mathbb{H}^{d,c}$ is denoted by $\mathbb{T}_{\boldsymbol{x}}^{d,c}$. $\mathbb{T}_{\boldsymbol{x}}^{d,c}$ is a local, first-order approximation of the Lorentzian manifold at $\boldsymbol{x}$, which is useful to perform graph convolutional operations in the hyperbolic space (Chami et al., 2019).

Exponential and logarithmic mappings. Hyperbolic space and tangent space can be bridged by exponential and logarithmic mappings. Given $\boldsymbol{x}$, $\boldsymbol{y}$ $\in$ $\mathbb{H}^{d,c}$ ($\boldsymbol{x}$ $\neq$ $\boldsymbol{y}$), $\boldsymbol{z}$ $\in$ $\mathbb{T}_{\boldsymbol{x}}^{d,c}$ ($\boldsymbol{z}$ $\neq$ $\boldsymbol{0}$), the exponential mapping $\prod^{exp,c}_{\boldsymbol{x}}(\boldsymbol{z})$: $\mathbb{T}_{\boldsymbol{x}}^{d,c}$ $\rightarrow$ $\mathbb{H}^{d,c}$, maps $\boldsymbol{z}$ to the hyperbolic space; the reverse logarithmic mapping projects vectors back to the tangent space centered at $\boldsymbol{x}$, where $||\boldsymbol{z}||_{\mathbb{H}}$ $=$ $\sqrt{\left<\boldsymbol{z},\boldsymbol{z}\right>_{\mathbb{H}}}$ is the norm of $\boldsymbol{z}$:

In the following content, we introduce the proposed Lorentzian Knowledge-enhanced Graph Convolutional Networks (LKGR) in detail. Figure 2(b) illustrates the framework of the LKGR model. Generally, it consists of three components:

• •

  Encoding Layer. In practice, input embeddings may live in the Euclidean space or hyperbolic space. If they are in the Euclidean space, Encoding Layer first projects them to the hyperbolic space to make sure they are on the Lorentzian manifold.

• •

  Attentive Lorentzian Convolutional Layer. Aiming to accurately profile the latent representations of users and items, the Lorentzian Convolutional Layer respectively updates their embeddings based on their sampled ego-networks, e.g., Figures 2(b) (unsampled nodes are colored white). In the hyperbolic space, users and items propagate interactive signals back and forth, which actually simulates the collaborative filtering effect. To automatically learn the relative importance of information from the KG, we design Lorentzian Knowledge-aware Attention Mechanism, which enables the selective and biased information aggregation in the hyperbolic space. Furthermore, by stacking multiple attentive Lorentzian Convolutional Layers, LKGR can explicitly explore the high-order KG subgraphs to further extract distant knowledge.

• •

  Prediction Layer. To achieve the efficient estimation in the matching stage, our Prediction Layer directly collects the learned representations of users and items and outputs the matching score, by conducting the inner product in the hyperbolic space.

If input embeddings are in the Euclidean space, before inputting to the following layers, we first need to explicitly encode the Euclidean input onto the Lorentzian manifold. Let $\boldsymbol{x}_{\mathbb{E}}$ $\in$ $\mathbb{R}^{d-1}$ and $\boldsymbol{x}_{\mathbb{H}}$ $\in$ $\mathbb{H}^{d}$ denote Euclidean inputs and the transformed hyperbolic feature embedding, respectively. $\boldsymbol{x}_{\mathbb{H}}$ can be encoded as follows:

where $(0,\boldsymbol{x}_{\mathbb{E}})$ is a $d$-dimensional vector in (Euclidean) tangent space and vector $\boldsymbol{o}$ $=$ $\{\sqrt{c},0,\dots,0\}$ $\in$ $\mathbb{H}^{d,c}$ denotes the origin in $\mathbb{H}^{d,c}$. $\boldsymbol{o}$ is used as a reference vector to perform tangent space operations. In the context of LKGR, we set the curvature $-1/c$ as a trainable variable, which dynamically measures how hierarchical the embedding space is (Chami et al., 2019). Unless otherwise specified, we use $\boldsymbol{x}$ to denote $\boldsymbol{x_{\mathbb{H}}}$ in the following sections.

Encoding Layer enables our model to be compatible with upstream Euclidean inputs. To evaluate the holistic performance, e.g., recommendation accuracy, training time, of all proposed LKGR modules, in this paper, we initialize the node embeddings in the Euclidean space. Experimental details can be found in Section 4.3.

To evaluate the effectiveness of LKGR, we utilize the following three benchmarks for movie, book, and restaurant recommendations. In terms of the diversity in domain, size, and sparsity, all these three datasets are frequently evaluated in recent works (Wang et al., 2018; Wang et al., 2019c; Wang et al., 2019b; Wang et al., 2020).

Specifically, Book-Crossing³³3Book-Crossing: http://www2.informatik.uni-freiburg.de/~cziegler/BX/ (Book) is a dataset of book ratings (ranging from $0$ to $10$) extracted from the Book-Crossing community. MovieLens-20M (Movie) is a widely adopted benchmark for movie recommendation. It contains approximately 20 million explicit ratings (ranging from 1 to 5) on the MovieLens website. Dianping-Food (Restaurant) is a commercial dataset from Dianping.com that consists of over 10 million diverse interactions, e.g., clicking, saving, and purchasing, between about 2 million users and 1 thousand restaurants. The first two datasets are publicly accessible and the last one is contributed by Meituan-dianping Inc. (Wang et al., 2019b). Dataset statistics are summarized in Table 1.

To demonstrate the effectiveness of the proposed model, we compare LKGR with three types of state-of-the-art recommendation methods: CF-based methods (BPRMF, NFM), regularization-based methods (CKE and KGAT), and propagation-based methods (RippleNet, KGCN, KGNN-LS, CKAN), as follows.

• •

  BPRMF (Rendle et al., 2012) is a representative CF-based method that performs matrix factorization with implicit feedback, optimized by the Bayesian Personalized ranking optimization criterion.

• •

  NFM (He and Chua, 2017) is a state-of-the-art neural factorization machine model for recommendation.

• •

  CKE (Zhang et al., 2016) is a classical regularization-based method. CKE learns semantic embeddings using TransR (Lin et al., 2017) with structural, textual and visual information to subsume matrix factorization under a unified Bayesian framework.

• •

  KGAT (Wang et al., 2019a) is another representative regularization-based model that collectively refines user and item embeddings via an attentive embedding propagation layer. We use the pre-trained embeddings of users and items from BPRMF to initialize the model.

• •

  RippleNet (Wang et al., 2018) is a recent state-of-the-art propagation-based model. Aiming at enriching the users’ representations, RippleNet uses a memory-like network to propagate users’ preferences towards items by following paths in KGs.

• •

  KGCN (Wang et al., 2019c) is another state-of-the-art propagation-based method which extends spatial GCN approaches to the KG domain. By aggregating high-order neighbor information, both structure information and semantic information of the KG can be learned to capture users’ potential long-distance interests.

• •

  KGNN-LS (Wang et al., 2019b) is a state-of-the-art propagation-based method that applies graph neural network architecture to KGs with label smoothness regularization for recommendation.

• •

  CKAN (Wang et al., 2020) is the latest state-of-the-art propagation-based method which employs a heterogeneous propagation strategy to encode diverse information in KGs for recommendation.

To evaluate LKGR, we randomly divide each dataset 5 times into training, evaluation, and test sets with the ratio of 6:2:2. In the evaluation of Top-K recommendation task, we use the model learned from the training set to rank K items for each user in the test set with the highest predicted scores $\hat{y}_{i,j}$. We choose two widely-used evaluation protocols, i.e., Recall@K and NDCG@K. We optimize all models with Adam optimizer (Kingma and Ba, 2014) and adopt the default Xavier initializer (Glorot and Bengio, 2010) to initialize the model parameters.

We implement the LKGR model under Python 3.7 and Pytorch 1.4.0. The experiments are run on a Linux machine with 1 GTX-2080TI GPU, 4 Intel Xeon CPU (Skylake, IBRS), 16 GB of RAM. For all the baselines, we follow the official hyper-parameter settings from original papers or as default in corresponding codes. For methods lacking recommended settings, we apply a grid search for hyper-parameters. The learning rate, denoted by $\eta$, is tuned within {$10^{-3},5\times 10^{-2},10^{-2},5\times 10^{-1}$} and the coefficient of $L2$ normalization is tuned among {$10^{-6},10^{-5},10^{-4},10^{-3}$}. The embedding size is searched in {$8,16,32,64,128$}.

In this section, we study how time efficient our LKGR and baselines are. All methods are run on the same aforementioned running environment, and we use the default hyper-parameters that are reported in papers or official codes. We use BK, MV, and RT to denote Book, Movie, Restaurant, and report the results in Figure 4.

We can observe that: (1) as shown in Figure 4(a), compared to CF-based methods, i.e., BPRMF and NFM, LKGR requires more time for model training as it needs to explore the KG for information propagation; (2) compared to the remaining KG-based recommendation models, LKGR requires the analogous time cost of model training, which may dispel concerns of large computation overhead in the hyperbolic space. (3) Figure 4(b) visualizes the overall performances in terms of efficiency and accuracy among all models. As the upper-right corner of the figure means the ideal optimal performance, LKGR makes an excellent trade-off w.r.t efficiency and accuracy, especially on Movie and Restaurant datasets.

In this section, we first conduct a comprehensive ablation study to evaluate the effectiveness of all model components. Then we discuss how key hyper-parameters affect the recommendation performance. We use R@20 and N@20 to denote recall@20 and NGCG@20.

Impact of interactive signal propagation. To investigate the impact of information propagation and aggregation of interactive signal in LKGR, we set a variant model, denoted by LKGR${}_{\rm w/o\ IS}$, which disables the information passing between users and items in our proposed Equations (6) and (7), so that items receive information only from KG entities. Based on the results reported in Table 3, without information propagation between users and items, the performance of Top-K recommendation drops dramatically, which demonstrates that learning historical interactive information for users and items is essential for the performance improvement.

Impact of knowledge extraction. Similarly, we set another variant LKGR${}_{\rm w/o\ KE}$ to study the influence of knowledge extraction, by cutting the KG information propagation to items (formulated in Equations (7) and (14)). As shown in Table 3, purely relying on the user-item interaction modeling is not enough to boost performance; thus integrating KGs in recommendation is also very important.

Impact of hyperbolic geometry. We verify the impact of the hyperbolic geometry by replacing all hyperbolic operations into Euclidean space and retaining the computation logic of LKGR. We denote the variant as LKGR${}_{\rm w/o\ HG}$. As shown in Table 3, even with adequate information propagation from user-item interactions and KGs, directly modeling these two data sources in Euclidean space brings about large performance decay on Top-K recommendation task. For example, by removing the hyperbolic geometry, LKGR${}_{\rm w/o\ HG}$ produces worse listwise ranking results on all three benchmarks: 14.45% (8.11$\rightarrow$9.48), 11.73% (22.19$\rightarrow$25.14), and 14.02% (21.47$\rightarrow$24.97) of Recall for Top-20 recommendation, respectively. To conclude, with all other essential components, embedding graph nodes on the Lorentzian manifold is substantial to LKGR, and modeling the scale-free graphs in the hyperbolic space can learn better representation for recommendation.

Impact of Lorentzian Knowledge-aware Attention mechanism. We also examine the impact of our proposed attention mechanism. For comparison, we use a variant that set $\pi(h,r,t)=1$ to make equal contribution for computing $\boldsymbol{s}_{\mathcal{N}(\cdot)}$, termed by LKGR${}_{\rm w/o\ LKA}$. As shown in Table 3, disabling our attention mechanism leads to the decreased Recall@20 by 11.92% (8.35$\rightarrow$9.48), 4.77% (23.94$\rightarrow$25.14), and 7.21% (23.17$\rightarrow$24.97). This proves that Lorentzian Knowledge-aware Attention mechanism is also effective, as it adaptively measures the importance weights for different nodes on the Lorentzian manifold and enables more coherent embedding aggregation.

Due to the space limit, we only report the effect of some key hyper-parameters on the model performance.

Effect of Lorentzian aggregators. To explore the influence of aggregating neighbor information on the Lorentzian manifold, we conduct experiments over different selections of Lorentzian aggregators $f(\cdot)$. Based on the Recall and NDCG metrics, we observe that in Table 4 sum aggregator, i.e., $f_{sum}(\cdot)$, is superior on datasets of Book and Movie. For the Restaurant dataset, $f_{concat}(\cdot)$ is much more suitable. This is because sum and concat aggregators are capable of retaining external neighbor information as well as the internal information when comparing to $f_{neighbor}(\cdot)$.

Effect of KG propagation depth $L$. We verify how the propagation depth affects the performance by varying $L$ from 0 to 3. Depth 0 means no local information aggregation from KG. As shown in Table 5, we notice that LKGR achieves the best performance when $L$ is 1, 2, and 1 for Book, Movie, and Restaurant. In addition to the over-smoothing issue that we explain in Section 3.4.4, another possible reason is: when long-distance propagation introduces distant knowledge, it may also bring about irrelevant information, especially when the dataset is large and dense. Thus, preserving an appropriate depth in the high-order information propagation enables maximized performance over different recommendation benchmarks adaptively.