key: cord-0045619-i3a5jwck
authors: Jiang, Bo; Lu, Zhigang; Liu, Yuling; Li, Ning; Cui, Zelin
title: Social Recommendation in Heterogeneous Evolving Relation Network
date: 2020-05-26
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50371-0_41
sha: 0ca41b25ea8a197bd77f150a6933bb679095e066
doc_id: 45619
cord_uid: i3a5jwck

The appearance and growth of social networking brings an exponential growth of information. One of the main solutions proposed for this information overload problem are recommender systems, which provide personalized results. Most existing social recommendation approaches consider relation information to improve recommendation performance in the static context. However, relations are likely to evolve over time in the dynamic network. Therefore, temporal information is an essential ingredient to making social recommendation. In this paper, we propose a novel social recommendation model based on evolving relation network, named SoERec. The learned evolving relation network is a heterogeneous information network, where the strength of relation between users is a sum of the influence of all historical events. We incorporate temporally evolving relations into the recommendation algorithm. We empirically evaluate the proposed method on two widely-used datasets. Experimental results show that the proposed model outperforms the state-of-the-art social recommendation methods.

The last decades have witnessed the booming of social networking such as Twitter and Facebook. User-generated content such as text, images, and videos has been posted by users on these platforms. Social users is suffering from information overload. Fortunately, recommender systems provide a useful tool, which not only help users to select the relevant part of online information, but also discovery user preference and promote popular item, etc. Among existing techniques, collaborative filtering (CF) is a representative model, which attempt to utilize the available user-item rating data to make predictions about the users preferences. These approaches can be divided into two groups [1] : memory-based and model-based. Memory-based approaches [2, 8, 16] make predictions based on the similarities between users or items, while model-based approaches [3, 9] design a prediction model from rating data by using machine learning. Both memory-based and model-based CF approaches have two challenges: data sparsity and cold start, which greatly reduce their performance. In particular, matrix factorization based models [13, 19] have gained popularity in recent years due to their relatively high accuracy and personalized advice. Existing research works have contributed improvements in social recommendation tasks. However, these approaches only consider static social contextual information. In the real world, knowledge is often time-labeled and will change significantly over time. Figure 1 shows the entire social contextual information over time which can be derived from links on social networks. User Jack post message m 1 , which mention users Tom and Eric, at time point t 1 . Subsequently, user Jack post message m 2 , which mention user Eric again, at time point t 3 . Meanwhile, message m 2 is retweeted by user Ellen at time point t 5 . We observe that new social action is often influenced by historical related behaviors. In addition, historical behaviors have an impact on current action over time, and the impact strength decreases with time. On the other hand, we notice that the evolving relation network is very sparse, which greatly reduce the recommendation performance. In order to deal with data sparsity, we leverage network embedding technology, which has contributed improvements in many applications, such as link prediction, clustering, and visual.

In this work, we propose a novel social recommendation model based on evolving relation network, named SoERec, which leverages evolving relation network and network embedding technique. The proposed method explicitly models the strength of relations between pair of users learned from an evolving relation network. To efficiently learn heterogeneous relations, network embedding is employed to represent relation into a unified vector space. We conduct experiments on two widely-used datasets and the experimental results show that our proposed model outperforms the state-of-the-art recommendation methods.

The main contributions of this paper are as follows:

-We construct a dynamic, directed and weighted heterogeneous evolving network that contains multiple objects and links types from social network. Compared with static relation graph, the evolving graph can precisely measure the strength of relations. -We propose a novel social recommendation model by jointly embedding representations of fine-grained relations from historical events based on heterogeneous evolving network. -We conduct several analysis experiments with two real-world social network datasets, the experimental results demonstrate our proposed model outperforms state-of-the art comparison methods.

The rest of this paper is organized as follows. Section 2 formulates the problem of social recommendation. Section 3 proposes the method of social recommendation based on evolving relation network to recommend the candidate users. Section 4 presents experimental results of recommendation. Finally, Sect. 5 reviews the related work and Sect. 6 concludes.

We briefly review the related works from two lines in this section: one on network embedding and the other on social recommendation. Network Embedding. Network embedding has been extensively studied to learn a low-dimensional vector representation for each node, and implicitly capture the meaningful topological proximity, and reveal semantic relations among nodes in recent years. The early-stage studies only focus on the embedding representation learning of network structure [14, 21, 24, 29] . Subsequently, network node incorporating the external information like the text content and label information can boost the quality of network embedding representation and improve the learning performance [4, 7, 20, 22, 23, 28] . Network embedding indeed can alleviate the data sparsity and improve the performance of node learning successfully. Therefore, this technique has been effectively applied, such as link prediction, personalized recommendation and community discovery.

Social Recommendation. Recommender systems are used as an efficient tool for dealing with the information overload problem. Various methods of social recommendation have been proposed from different perspectives in recent years including user-item rating matrix [15] , network structure [11] , trust relationship [5, 10, 18, 27] , individual and friends' preferences [6, 12] , social information [25] and combinations of different features [19, 26] . The above social recommendation methods are proposed based on collaborative filtering. These methods all focus on fitting the user-item rating matrix using low-rank approximations, and also use all kinds of social contextual information to make further predictions. Most of the studies that use both ratings and structure deal with static snapshots of networks, and they don't consider the dynamic changes occurring over users' relations. Incorporating temporally evolving relations into the analysis can offer useful insights about the changes in the recommendation task.

The intuition behind is that there are two basic accepted observations in a real world: (1) The current behavior of user is influenced by all his/her historical patterns. (2) A behavior with an earlier generation time has a smaller influence on the user's current behavior, while the one with a later generation time has a greater influence. Therefore, we first formally define the concept of Evolving Relation Network, as follows:

where N u is the set of vertices representing users, and N i is the set of vertices representing items, and E is the set of edges between the vertices. The types of edges can be divided into user-user and user-item relationships with temporal information. Hence, G is a dynamic, directed and weighted heterogeneous evolving network.

From the definition, we can see that each edge not only is an ordered pair from a node to another node, but also has a weight with time-dependent. In order to measure the strength of relations between two nodes objects in the heterogeneous evolving network G, we introduce the concept of evolving strength, which is formally defined as follows:

where ψ is an event type (e.g., post, mention, follow, etc.) and t is the timestamp of e. An event sequence Γ between two nodes is a list of events {e 1 , e 2 , · · · , e n }, ordered by their timestamps

An event corresponding to an edge. Thus, the strength of evolving relations denoted by F is the sum of individual event influence.

We formulate the problem of social recommendation as a ranking based task in this work, as follows:

Given a heterogeneous evolving network G at time t, and a target user u i , and a candidate set of items Ψ , we aim to generate a top K ranked list of items Ω ∈ Ψ for u i at time t + 1 according to the target user's preference inferred from historical feedbacks.

Let R ∈ R M ×N be the rating matrix with M users and N items. The (i, j)-th entry of the matrix is denoted by R ij that represent the rating of user i for item j. U ∈ R K×M and V ∈ R K×N be user and item latent feature matrices respectively, where K is the dimension of latent factors. The preference of i-th user is represented by vector U i ∈ R K×1 and the characteristic of j-th item is represented by vector V j ∈ R K×1 . The dot product of U and V can approximate the rating:R ≈ U T V j . Recommendation based on Probabilistic Matrix Factorization (PMF) [15] solve the following problem

can avoid overfitting, || · || F denotes the Frobenius norm of the matrix.

Incorporating the knowledge from present and historical behavior data can accurately measure the strength of influence, as shown Fig. 2 . In this work, we model the strength of relation between users as a sum of the influence of each event by multiplying a weight. The weight is calculated by a function, called decay function. Since the influence between users can't be less than zero in social networks, the weight ranges from 0 to 1 and decreases with the event's existing time. Thus, we formalize the decay function d ij (t) with timestamped information as follows:

where t is the current time, t i is the generation time of historical event, and λ is a parameter which controls the decay rate. Through the analyses in the following experiments in the paper, we set the parameter λ as 0.6. Based on the influence of historical events, we can measure the current strength of social relation between users as follows:

where I e(ψ,ti) is a parameter which controls the weight of different events. To simplify the model, we assume that the importance of any events is equal. 

The learned evolving relation network has three characteristics: (1) a weighted and directed graph; (2) a sparsity graph; (3) heterogeneous information network. In order to learn the evolving relation network, we employ large-scale information network embedding (LINE) [17] model to simultaneously retain the local and global structures of the network. In particular, we leverage the LINE model to learn users' embedded representations of the evolving relation network the firstorder proximity and the second-order proximity. As shown Fig. 3 , the detailed process is demonstrated as follows.

User Relation with First-Order Proximity. The first-order similarity can represent the relation by the directly connected edge between vertices. We model the joint probability distribution of users u i and u j as the first-order similarity p 1 (u i , u j ). The similarity can be defined as follows:

where − → u i ∈ R d is the low-dimensional vector representations of vertices u i . The empirical distribution between vertices u i and u j is defined as follows:

where W = (ui,uj )∈E w ij , and w ij is the relation strength of the edge (u i , u j ) measured by Eq. (3) . To preserve the first-order proximity in evolving relation network, we use the KL-divergence to minimize the joint probability distribution and the empirical probability distribution as follows:

User Relation with Second-Order Proximity. The second-order proximity assumes that vertices sharing many connections to other vertices are similar to each other. In this work, we assume that two users with similar neighbors have high similarity scores between them. Specifically, we consider each user vertex as a specific "ontext", and users with similar distributions over the "contexts" are assumed to be similar. Thus, each user vertex respectively plays two roles: the user vertex itself and the specific "context" of other user vertices. We introduce two vectors − → u i and − → u i , where − → u i is the representation of u i when it is treated as a vertex, and − → u i is the representation of u i when it is treated as a specific "context". For each directed user edge (u i , u j ), we firstly define the probability distribution of "context" u j generated by user vertex u i as follows:

where K is the number of user vertices or "contexts". The empirical distribution of "contexts" u j generated by user vertex u i is defined as:

where w ij is the weight of the edge (u i , u j ) as the same, and d i is the out-degree of vertex u i , i.e. d i = k∈N (i) w ik , with N (i) as the set of out-neighbors of u i . To preserve the second-order user relation, the following objective function is obtained by utilizing the KL-divergence:

Combining First-Order and Second-Order Proximities. To embed the evolving network by preserving both the first-order and second-order proximities, LINE model can minimize the objective functions O 1 and O 2 respectively, and learns two low-dimensional representations for each user vertex. Then, the two low-dimensional representations are concatenated as one low-dimensional feature vector to simultaneously preserve the local and global structures of evolving relation network. Finally, each user vertex u i is represented as − → U ∈ R d1+d2 .

Incorporating simultaneously user's explicit relation and implicit relation can boost the ability of social recommendation. As mentioned above, LINE model can learn users' embedded representations, where first-order proximity correspond to the strength of explicit relation and second-order proximity correspond to the strength of implicit relation. Hence, the fine-grained relation measure can better predict user ratings by also encoding both the first-order and second-order relationships among users.

After performing the LINE model, we can obtain users' embedded presentations. We then measure the fine-grained relations among users on the basis of the inner product of the presentations as follows:

where − → u i and − → u j denote the low-dimensional feature representations of users u i and u j , respectively. In this work, relation strength w ij can be viewed as a coarsegrained relation value between users u i and u j . Compared to coarse-grained measure, the fine-grained measure s ij is more informative, and can effectively distinguish the importance of recent and old events among users. In other words, the fine-grained measure can deduce the strength of latent relation based on neighborhood structures while two users have no explicit connections. The fact of matter is that user decision making is influenced by his/her own preferences and close friends in real-world situations. Specifically, on the one hand, users often have different preferences for different items. On the other hand, user are likely to accept their friends' recommendations. Thus, we assume that the final rating of user u i for item v j is a linear combination between the user's own preference and his/her friends' preferences, where the rating can be defined as follows:R

where S(u i ) is the set of most intimate friends of user u i . In the above equation, the first item corresponds to the prediction rating based on their own preferences, while the second item corresponds to the prediction rating based on the preferences of his/her friends, and η is a parameter that controls the relative weight between user's own preferences and friends' preferences. The ratings of users to items are generally represented by an ordered set, such as discrete values or continuous numbers within a certain range. In this work, without loss of generality, the differences in the users' individual rating scales can be considered by normalizing ratings with a function f (x): (12) where R max and R min represent the maximum and minimum ratings, respectively. f (x) values can be fell in the [0, 1] interval. Meanwhile, we use the logistic function g(x) = 1/(1 + e −x ) to limit the predicted ratingsR ij within the range of [0, 1]. Based on this, the task of social recommendation is likewise to minimize the predictive error. Hence, the objective function of the evolving relation embedding recommendation algorithm is formalized as:

where S(u i ) = {k|s ik ≥ } is the set of most intimate friends of user u i , and the parameter is the threshold of the close relation value.

We adopt stochastic gradient descent (SGD) to solve the local minimum solution of L, and learn the latent feature vectors U i and V j . The partial derivatives of the objective function L with respect to U i and V j are computed as:

where g (x) = e −x /(1 + e −x ) 2 is the derivative of the logistic function g(x).

In this section, we first describe experimental datasets and metrics. We then present the baselines and the experiments settings. Finally, we give the experimental results and analyze them.

To evaluate the proposed model, we use two real-world datasets for this task: Weibo and Last.fm.

Weibo Dataset 1 . The data is collected from Sina Weibo, which is the most popular microblogging platform in China. It includes basic information about messages (time, user ID, message ID etc.), mentions (user IDs appearing in messages), forwarding paths, and whether containing embedded URLs or event keywords. In addition, it also contains a snapshot of the following network of users (based on user IDs). Last.fm Dataset 2 . This dataset has been obtained from Last.fm online music system. Its users are interconnected in a social network generated from Last.fm "friend" relations. Each user has a list of most listened music artists, tag assignments, i.e. tuples [user, tag, artist] , and friend relations within the dataset social network. Each artist has a Last.fm URL and a picture URL. For two datasets, the user-user relations are constructed from following or bi-directional friendships between social network users, user-item relations are constructed from the user posting or listening behavior. The statistics of two datasets are summerized in Table 1 .

We use the mean absolute error (MAE), root mean square error (RMSE) and the average precision of top-K recommendation (Average P@K) to evaluate the performance of recommendation algorithms. According to their definition, a smaller MAE/RMSE or bigger Average P@K value means better performance. For each dataset, {40%, 80%} are selected randomly as training set and the rest as the test set. We will repeat the experiments 5 times and report the average performance.

In order to evaluate the effectiveness of our proposed recommendation algorithm, we select following recommendation algorithms as comparison methods:

-PMF [15] : The method adopts a probabilistic linear model with Gaussian distribution, and the recommendations are obtained only by relying on the rating matrix of users to items. -SoRec [11] : The method integrates social network structure and the useritem rating matrix based on probabilistic matrix factorization. However, the algorithm ignore the temporal changes of relations between users. -RSTE [10] : The model fuses the users' tastes and their trusted friends' favors together for the final predicted ratings. Similarly, the method doesn't consider the changes of trust relations over time.

-SocialMF [5] : The model integrates a trust propagation mechanism into PMF to improve the recommendation accuracy. However, the algorithm represents the feature vector of each user only by the feature vectors of his direct neighbors in the social network. -TrustMF [27] : The model proposes social collaborative filtering recommendations by integrating sparse rating data and social trust network. The algorithm can map users into low-dimensional truster feature space and trustee feature space, respectively. -SoDimRec [19] : The model adopts simultaneously the heterogeneity of social relations and weak dependency connections in the social network, and employs social dimensions to model social recommendation. The optimal experimental settings for each method were either determined by our experiments or were taken from the suggestions by previous works. The setting that were taken from previous works include: the learning rate η = 0.001; and the dimension of the latent vectors d = 100. All the regularization parameters for the latent vectors were set to be the same at 0.001.

Comparisons of Recommendation Model. We use different amounts of training data (40%, 80%) to test the algorithms. Comparison results are demonstrated in Table 2 , and we make the following observations: (1) Our proposed approach SoERec always outperforms baseline methods on both MAE and RMSE. The major reason is that the proposed framework exploits heterogeneity of social relations via time dimension and network embedding technique.

(2) Recommendation systems by exploiting social relations all perform better than the PMF method only by using user-item rating matrix in terms of both MAE and RMSE. (3) Among these relation-aware recommendation methods, leveraging more indirect relations method generally achieves better performance than only using direct connections methods. In a word, social relations play an important role in context-aware recommendations. Figure 4 summarizes the user recommendation performance for the state-of-the-art methods and the proposed model. Generally speaking, it can be shown from the figure that the average P@K value decreases gradually along with the increasing number of K. Besides, we can also observe on both datasets that: Firstly, the proposed method consistently perform better than baseline methods, indicating that the considering cross-time evolving graph embedding by SoERec model can be recommended the more appropriate users than recommendation models without considering time dimension. Secondly, trust-based algorithms (TrustMF, SocialMF and RSTE) consistently perform better than non-trust based benchmarks (SocRec, PMF). It is because trust-based algorithms can fully exploit the network structure, which tackles the incomplete, sparse and noisy problem. Finally, among the different recommendation methods, considering heterogeneous network (SocDimRec and SoERec) significantly performs better than the other methods.

In this paper, we propose a novel social recommendation model by incorporating cross-time heterogeneity network of relations. We construct an evolving heterogeneous relation network with timestamp information based on multiple objects and links types. The evolving graph can learn more accurate user relations.

We then use network embedding technique to encode the latent feature spaces of relations into the objective function. To demonstrate the effective of the proposed model, we construct extensive experiments. The experimental results reveal that our proposed method outperforms the state-of-the-art baseline methods.

Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions

Item-based top-n recommendation algorithms

Scalable recommendation with hierarchical poisson factorization

node2vec: scalable feature learning for networks

A matrix factorization technique with trust propagation for recommendation in social networks

Social contextual recommendation

Semi-supervised classification with graph convolutional networks

Amazon. com recommendations: item-to-item collaborative filtering

Eigenrank: a ranking-oriented approach to collaborative filtering

Learning to recommend with social trust ensemble

SoRec: social recommendation using probabilistic matrix factorization

Recommender systems with social regularization

Probabilistic matrix factorization

Asymmetric transitivity preserving graph embedding

Probabilistic matrix factorization

Item-based collaborative filtering recommendation algorithms

Line: large-scale information network embedding

mTrust: discerning multi-faceted trust in a connected world

Recommendation with social dimensions

Cane: context-aware network embedding for relation modeling

Community-enhanced network representation learning for network analysis

Max-margin deepwalk: discriminative learning of network representation

Transnet: translation-based network representation learning for social relation extraction

Structural deep network embedding

Collaborative filtering with social exposure: a modular approach to social recommendation

Social recommendation with strong and weak ties

Social collaborative filtering by trust

Network representation learning with rich text information

Overlapping community detection at scale: a nonnegative matrix factorization approach