{'fraction_non_alphanumeric': 0.03629515493922274, 'fraction_numerical': 0.010329281515722193, 'mean_word_length': 5.06576670128072, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DSKReG: Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN

In the information explosion era, recommender systems (RSs) are widely studied and applied to discover user-preferred information. A RS performs poorly when suffering from the cold-start issue, which can be alleviated if incorporating Knowledge Graphs (KGs) as side information. However, most existing works neglect the facts that node degrees in KGs are skewed and massive amount of interactions in KGs are recommendation-irrelevant. To address these problems, in this paper, we propose Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN (DSKReG) that learns the relevance distribution of connected items from KGs and samples suitable items for recommendation following this distribution. We devise a differentiable sampling strategy, which enables the selection of relevant items to be jointly optimized with the model training procedure. The experimental results demonstrate that our model outperforms state-of-the-art KG-based recommender systems. The code is available online at https://github.com/YuWang-1024/DSKReG.


INTRODUCTION
The crucial part in a recommender system is to characterize collaborative signals from user-item interactions, and recommend similar users with correlated items [7,14,23]. However, only leveraging user-item interactions spoils recommendation performance when the data suffers cold-start issues [12,22]. Therefore, existing works [1,19,22] propose to incorporate knowledge graphs (KGs) as side information [11], which afford additional semantics among items through intermediate entities, thus alleviating cold-start issues from item perspectives.
Leveraging the information from KGs requires the model aggregating relevant interactions among items for recommendation [5,22]. The successes of Graph Neural Networks (GNNs) [6,9,13,17,26] inspire the community designing novel methods for information aggregation. KGCN [20] is one of the pioneering work that adopts GCN [9] layers to aggregate entities in KGs to infer item embeddings. KGNN-LS [19] further extends this idea by assigning user-specific scores on interactions, thus characterizing personalized interests. KGAT [22] employs graph attention layers [17] to aggregate both item and user embeddings from KGs. Moreover, ATBRG [5] constructs sub-graphs from KGs and proposes a relation-aware graph attention layer to adaptively search relevant interactions.
Despite the effectiveness of existing methods, two limitations are still under-explored: 1) node degree skewness and 2) noisy interactions. Node degree skewness refers that the number of edges for nodes in KGs exhibits a power-law distribution [2]. On the one hand, due to large number of nodes with low degrees and insufficient neighbors, a multi-layer GNN aggregation is required to receive high-order information [22]. On the other hand, high-order aggregation for nodes with high degrees leads to exponential growth of their receptive field [29], thus suffering the over-smoothing problem [10,16]. The second limitation results from massive amount of recommendation-irrelevant interactions in KGs [5]. Existing methods infer item embeddings by aggregating all connected entities in KGs. However, directly aggregating those irrelevant entities has no contributions to the representation learning and even increases computational costs, which degrades the performance.
To address the limitations above, we propose a sampling-based relational GNN to extract recommendation-relevant information from KGs. First, we connect items in KGs according to their intermediate entities and create new relations, such as creating a co-director relation if two movies are connected by a common director. We illustrate this process in Figure 1(a). This relational graph construction is inspired by works in heterogeneous graph [24,27]. In this way, we could explicitly reveal the item relationships. Second, we adopt sampling-based aggregation of neighbors to avoid the exponential growth of neighbor size, thus alleviating the over-smoothing issue. Figure 1: A toy example reflecting the framework of DSKReG. a) We construct user-item graph according to users' collaborative interactions, and construct item-item graph by connecting high-order neighbor items. b) For the item 2 , we compute the relevance score vector 2 that consists of scores of neighbor items 1 and 3 . Afterwards, we apply Gumbel-Softmax over 2 to obtain an approximated one-hot encoderˆ2. The value ofˆ2 indicates that neighbor item 3 should be ignored. c) We apply attentive aggregation on relational graph guided by users' preferences.
However, it is rather challenging to devise a suitable sampling method. Most sampling-based GNNs in KG-based recommendation employ uniform sampling [18][19][20] of neighbors, which is unable to distinguish recommendation-relevant relations. Moreover, existing sampling strategies [6,25,31,33] are independent of the optimization process, which further hinder the end-to-end training manner. RippleNet [18] detachedly samples a fixed-size set of neighbors to infer item embeddings. KGPolicy [25] employs a disjoint reinforcement learning agents to discover high-quality negative examples in KGs. Both methods separate the sampling procedure from the training phase, resulting in a sub-optimal selection of neighbors.
Therefore, we propose a novel model, Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN (DSKReG). Given an item, we first compute relevance scores of connected items conditioned on their associated relations and node embeddings. Relevance scores are used to sample top-relevant neighbor items. As such, our model can distinguish the recommendationrelevant items among connected neighbors according to relation and item types. We also adopt Gumbel-Softmax reparameterization trick [8,28] into the sampling procedure, which approximates the sampling probability from a categorical distribution, thus enabling the sampling procedure to be differentiable. Therefore, the sampling component is optimized jointly with the training objective, thus enjoying an end-to-end fashion.
Our contributions are summarized as follows: 1) We compute relevance scores according to relation and item types for sampling, which can navigate model to select recommendation-relevant items. 2) We devise a differentiable sampling strategy to enable the model to refine the sampling procedure jointly with the model optimization. 3) We conduct experiments on three public datasets, and demonstrate the effectiveness of our model.

OUR APPROACH
In this section, we first formulate the problem of knowledge-aware recommendation. Then, we propose the DSKReG framework, which is shown in Figure 1.

Problem Definition
The objective of knowledge-aware recommendation is to predict whether user has interest in item given historical interactions and the KG. Formally, the historical interactions from a set of users U with the set of items V are represented as a user-item bipartite graph G Y = {( , , )| ∈ U, ∈ V}, where = 1 denotes that the user is interacted with the item through clicking, purchasing, and etc. The KG consists of item related properties, such as genres, directors, and casts for movies. We format the KG as a directed heterogeneous graph G K = {(ℎ, , )|ℎ, ∈ E, ∈ R}, such as (James Cameron, isdirectorof, Titanic), where E and R denote the set of entities and relations respectively. Thus, the knowledge-aware recommendation task can be formalized as follows: whereˆis the prediction of user's interest in item , and F is the learned prediction function with weights Θ.

Relational Neighborhood Construction
The node degree skewness limits the pool of available neighbor items for items with scarce connections in a KG. We propose "cointeract" patterns to build up higher order item-item relationships for shortening the path distance between correlated items. Intuitively, those co-interact patterns are important for the recommendation. For example, a user might be interested in books written by the same author. We extract co-interact patterns from input KG G K and construct an item-item co-interact undirected graph G co with a new set of co-relations, which is defined as follows: where ′ denotes the new "co-" relationship. Following the navigation of these relations, we connect items that have co-interact patterns and construct the item-item graph as shown in Figure 1(a).
In this way, we can connect high-order neighbors directly and avoid exponential growth of the receptive field. We unify both user-item bipartite graph G Y and item-item co-interact graph G co into one single graph denoted as relational graph. Thus, we can consider all these relations between users and items for subsequent tasks.

Differentiable Sampling
Here, we introduce the proposed differentiable sampling for neighbors selection. We only illustrate it from item's perspective because it is the same process for users. The relevance of co-interact relationships to recommendation varies across users. For example, same genre has more impacts than co-director. Moreover, co-interact relationships are imbalanced. For example, item-item pairs of codirector are much less than the ones of the same category. This brings up an issue that highly relevant neighbors diminish when the pool of potential neighbors is large. The uniform sampling technique adopted by existing works [19,20] still fails to tackle this issue. In order to filter out the noise and retain the truly relevant information, we introduce the relation-aware sampling method that assigns weights from relation perspective, as shown in Figure 1(b). The sampling procedure first defines a novel relation-aware relevance score distribution for each item and then samples from it. The relation-aware relevance score distribution of an item on its co-related neighbors N ( ) is defined as follows: where ( , = 1|w, ) denotes the plausibility of item being relevant to the target item ; w ∈ R and ∈ R are the learnable weight and bias; r ∈ R and e ∈ R are embeddings of relation and neighbor item respectively, and is the dimension of embeddings. The co-relation and neighbor item together determine its neighbor relevance probability, which emphasizes the necessity of relation-awareness in relevance calculation for the sampling. We apply the same relevance calculation process to users. Given the calculated relevance distribution, we thus only select top-most relevant items. Selection procedure of previous works [5] is independent of optimization. In other words, the recommendation performance is highly contingent on the result of selection procedure. To make this procedure differentiable and joint with optimization process, we apply the Gumbel-Softmax reparameterization trick. Given a Gumbel noise g ∼ (0, 1), we can draw a soft categorical sample with the following equation: where p ∈ R consists of relevance score ( , ) for all the neighbors ∈ N ( ) defined in Eq. (3), and is the annealing temperature. It has been proved [8,28] thatŷ i is approximate to a one-hot encoder as goes to 0. We repeat the above procedure for times and sum the approximated one-hot encoders. At each time, the relevance score in p of selected items will be set as 0. In this way, we can obtain a -hot vector representing the top-relevant items selected for subsequent learning procedures.

Preference Aware Aggregation
Besides the factor of relations, we should also consider user preference in the top-neighbor messages propagation process. As users might have different preferences towards various relations, we take the relations into account in the aggregation. The aggregation procedure, as shown in Figure 1 where is the -th position value in the -hot vector of the item obtained from sampling procedure, which indicates whether the item is selected as a neighbor of item . The e ∈ R is user's embedding. For users, we obtain the inferred user embeddingî n a similar procedure, but the attentions are calculated using the connected item embeddings.

Prediction and Optimization
We use the dot-product to generate the preference score of user to item with the inferred user/item embeddingsê andê , respectively. The prediction is calculated as follows: We use the pairwise BPR loss [15] to optimize top-recommendation, which is defined as follows: where D is a set of triplets, each of them is composed of user , an interacted item and one sampled negative item from items that user never interacts with.

EXPERIMENTS
In this section, we introduce the experimental settings and compare our model with state-of-the-art methods on three common benchmark recommendation datasets. Then, we perform the ablation study and discuss effects of the model's components.

Experimental Settings
Datasets. To evaluate the effectiveness of our model, we perform experiments on three benchmark datasets: Last.FM, BookCrossing and MovieLens-Sub. Last.FM is a set of online listening information from Last.fm website. BookCrossing contains users' ratings of books. MovieLens-Sub comes from a widely used benchmark dataset: MovieLens-1M, which contains users' ratings of movies from MovieLens website. Table 2 provides detail empirical statistics of these datasets. We define the density of a dataset as the division of the number of ratings by the number of users, which indicates the average number of ratings per user. During the empirical study of these datasets, we found the density of original MovieLens-1M is 62.4, which is extremely large compared to other datasets. To make the dataset fit the cold-start scenario, we only randomly chose 10% of all ratings to construct MovieLens-Sub. Baselines. We compare our model with state-of-the-art methods: KGAT [22], KGNN-LS [19], RippleNet [18] and knowledge embedding based method CFKG [1].

Results
To evaluate top-recommendation and preference ranking performance, we use three standard metrics: Recall, Precision, and NDCG.  For each dataset, we randomly sample a subset of users for evaluation. Then, we rank the users' preference scores over all items except training items. Finally, we compute the Recall, Precision, and NDCG on top 5, top 10, and top 20 items, respectively. As Table 1 shows, our model outperforms state-of-the-art methods significantly in most cases. Compared to the strongest baseline model, we manage to improve the performance by 7.73%, 6.2%, and 9.03% on Last.FM on average for Recall, Precision, and NDCG respectively. Similarly, we outperform the best baseline model by 9.43%, 4.97%, and 19.83% on BookCrossing. On the MovieLens-Sub dataset, we improve the performance by 11.47%, 15.60%, and 45.47% respectively. These results indicate the effectiveness of our model. Surprisingly, our model improve the NDCG by a significant margin. Specifically, we improve the NDCG@20 by 14.2%, 32.0%, and 37.5% on three datasets respectively. Since NDCG measures the recommendation quality taking position significance and the number of items into account, these results demonstrate the superiority of our model in recommendation.

Ablation Study
In this section, we perform the ablation study to better understand effects of different components of our model.
The Effect of Relation-aware Sampling. To examine the effect of relation-aware sampling, we compare our model with different sampling strategies. As shown in Figure 2, uniform indicates we randomly select neighbors for each item; L2 means we use the 2-norm of difference between relation and neighbor item embeddings as the categorical sampling distribution; Inner represents that we use the inner product between relation and item embeddings as sampling probability; We denote the differentiable sampling method using Gumbel-Softmax as GS. The experimental results indicate that the GS outperforms the others on Last.FM and MovieLens-Sub.
On BookCrossing, models using L2 distance and Inner product metrics can achieve comparable results with GS. The possible reason is that relations among items in this dataset are relatively simple. As shown in Table 2, BookCrossing has smaller number of relations in the original KG dataset than that in Last.FM, and smaller number of triples than that in MovieLens-Sub. The L2 distance and Inner product metric are sufficient to model the item relations. However, in dealing with complex item relations, GS significantly outperforms the other metrics.
The Effect of Sampling Size. To examine the effectiveness of neighbor size, we perform experiments with different , which is the size of the neighborhood after sampling. As shown in Figure 3, the best neighbor size is 8 for Last.FM, BookCrossing, and MovieLens-Sub. This indicates that only a small portion of items are relevant.
Our model can correctly select this valuable information for aggregation, which enables our model to achieve the best performance with only eight neighbors.

CONCLUSION
In this paper, we proposed a novel framework DSKReG to alleviate the node degree skewness and noisy interactions limitations when tackling KG-based recommendation. DSKReG is a sampling-based relational GNN, which extracts recommendation-relevant information from KGs. We devised a differentiable sampling strategy for DSKReG, which is jointly optimized with the model to learn how to select top-relevant items for aggregation. We conducted experiments on three public dataset to demonstrate the effectiveness of DSKReG in improving the recommendation performance.