Neural Framework for Joint Evolution Modeling of User Feedback and Social Links in Dynamic Social Networks

1 Introduction

Over the last years, social network services (SNSs) have become one of the most important and popular tools for users to communicate, share, and deliver information. The available information from SNSs (e.g., user attributes and preferences) and related resources (e.g., user purchase logs) allow in-depth understanding and modeling of user behaviors, thereby potentially benefiting certain important applications, such as recommendation systems, link prediction, and so forth.

In SNSs, giving feedback about items consumed by users and creating social links with others are two pivotal types of user behaviors that have been individually studied by many previous works [Mnih and Salakhutdinov, 2008; Salakhutdinov et al., 2007; Liben-Nowell and Kleinberg, 2007]. However, social scientists have demonstrated that the two core behaviors in SNSs, i.e., user feedback and social links, are not independent of each other [Crandall et al., 2008]. Specifically, future user preferences are affected by their social influences, such as word of mouth. Moreover, users who share similar consumption preferences have a high likelihood to associate with one another. This phenomenon is called the homophily effect. To address these observations, most of the prior studies utilized only one of the two behaviors to boost the prediction of another behavior [Jamali and Ester, 2010; Tang et al., 2013]. Only a few works attempted the joint modeling of the two user behaviors, which enhances the predictions of user behaviors [Wu et al., 2016; Jamali et al., 2011].

∗Corresponding author.

In the real world, social networks evolve over time, and user preferences are likewise dynamic. In addition, item attributes often change as well, as a function of user inclinations and other factors [Wu et al., 2017a]. These time-evolving aspects make the effective and comprehensive modeling of user behavior increasingly challenging. Most previous works jointly modeled user feedback and social link behaviors, with the assumption of static social networks, or considered only a partial integration of the three dynamic aspects [Yang et al., 2011; Wu et al., 2017b]. To address these issues, we propose to jointly model the temporal evolution of user feedback and social link behaviors via capturing the dynamic user preferences, dynamic item attributes and time-evolving social networks. We introduce a social network embedding framework to explore how social influences and the homphily effect impact future user feedback and social linking behaviors.

Recently, neural networks (NN) have achieved remarkable successes in computer vision, speech recognition, and text processing. NNs have been then applied by many studies to model user feedback or social links and have shown promising results. However, the number of NN-based approaches that jointly model the two user behaviors and benefit both tasks of user feedback and social link prediction, is limited.

In this paper, we present a novel NN-based model to jointly learn the two user behaviors by considering the three aforementioned dynamic aspects in SNS. The main contributions of this paper are as follows:

• We propose Neural Joint Modeling (NJM), a novel deep learning based architecture to model the evolution of user feedback and social links in dynamic social networks by

considering dynamic user preferences, dynamic item attributes, and time-evolving social networks. This work is the first one based on deep learning that jointly models the evolution of the two user behaviors.

• We leverage expressive NNs to thoroughly study the highlevel nonlinear interactions between user historical preference and social influence as well as between user social structure and the homophily effect.
• We conduct extensive experiments on two real-world datasets, and the experimental results illustrate that our model achieves a promising effectiveness in recommendation and social link prediction compared with state-of-theart methods.

2 RelatedWork

We first summarize the general approaches for separately modeling user feedback and predicting social links. Then we introduce the joint modeling of these two user behaviors.

User feedback is mainly affected by user preferences and item attributes, which can be modeled by Collaborative Filtering (CF). One of the most traditional CF techniques is matrix factorization (MF) [Mnih and Salakhutdinov, 2008]. Since user preferences and item attributes generally change over time certain MF models consider temporal dynamics by creating handcrafted features [Koren, 2010; Xiong et al., 2010]. However, with such an approach, they cannot capture complex temporal patterns [Wu et al., 2017a]. Recently, deep learning-based techniques have been widely leveraged for MF in modeling user feedback in static networks [He et al., 2017; Zheng et al., 2016]. By contrast, [Wu et al., 2017a] proposed recurrent recommender network that can model the dynamics of users and items. Based on the social influence theory, many studies integrated the context of user friendship with feedback data in static social networks [Jamali and Ester, 2010; Deng et al., 2017].

The problem of link prediction viewed as computing the node proximityis to predict potential new links on the basis of partially observed connections in a social network. Early approaches predicted possible links only in static networks [Liben-Nowell and Kleinberg, 2007]. With the availability of temporal information in social networks, other scholars analyzed the patterns of the evolution of networks [Zhu et al., 2016; Sarkar et al., 2012; Yu et al., 2017]. A few deep learning based models have been used for the link prediction problem recently. For example, [Kipf and Welling, 2016] devised variational graph autoencoder to learn meaningful latent embeddings on the link prediction task. [Liao et al., 2017] leveraged attributed social network embedding for link prediction. [Zhang and Chen, 2017] proposed a nextgeneration link prediction method, called Weisfeiler-Lehman Neural Machine. To utilize the homophily effect, [Tang et al., 2013] proposed to exploit user preferences on items for link prediction.

[Jamali et al., 2011] analyzed the temporal dynamics of social networks by using bidirectional effects, but that work cannot be used for personalized recommendation. [Yang et al., 2011] jointly modeled the two user behaviors by using a unified framework that assumes a static representation of social networks. [Wu et al., 2017b] proposed a model that captures the temporal dynamics of the two user behaviors yet it assumes item attributes to be static. Nevertheless, no existing work has explored the idea of taking into account all the three aforementioned dynamic aspects to jointly learn the two kinds of user behaviors.

To the best of our knowledge, our model is the first one based on deep learning that jointly models the evolution of the two user behaviors and considers dynamic item attributes, dynamic user preferences, and time-dependent social links.

3 The ProposedModel

3.1 ProblemDefinition

A social network has a set of users U = {u1, u2, ..., uN} and a set of items V = {v1, v2, ..., vM}. Users consume items and create links with others over time. The feedback data on items expressed by users at time t are described in a feedback matrix Ct ∈ RN×M . Cta,i denotes the rating of user ua on item vi at time t. On the other hand, social links built by users are given in a link matrix St ∈ RN×N . Sta,b = 1 means that user ua forms a link with user ub at time t. We use a, b to represent users and i, j to denote items.

Given two matrix sequences: a feedback matrix sequence C = [C1 , C2 , ..., CT ] and a social link matrix sequence S = [S1 ,S2 , ..., ST ], the tasks of our model are to: (1) quantify the social influence in user feedback behavior and homophily effect in social link behavior; (2) depict the dynamic states of items; and (3) predict each user's new feedback and social link behaviors at the next time.

3.2 Overall Framework

To solve the tasks mentioned above, we propose a framework that comprises twomodules: (1) user feedbackmodel (Fig. 1, left) which captures user dynamic preferences by quantifying historical user preferences and social influences, and which uses LSTM to learn the dynamic states of items; (2) social link model (Fig. 1, right) which considers the homophily effect when predicting social links. The two modules are jointly trained to achieve superior prediction performance.

Given the dimension of the latent space as D, we propose two time-dependent embeddings (1) uta , which is called latent preference embedding and describes the latent preference of user ua on items at time t and (2) pta , which is called latent link embedding and represents the latent structure of user ua at time t. Moreover, we denote U t = {uta } ∈ RN×D and P t = {pta } ∈ RN×D . The one-hot vector is employed for user ID, as shown at the bottom of Fig. 1.

3.3 User FeedbackModel

User feedback is determined by user preferences and item attributes. In following, we introduce the user preference and item attribute parts of this model.

User Preference

The new preferences of each user are affected by their historical preferences and social influences.

Impact Factors of User Preference. uta represents the timedependent latent preference of user ua at time t. On the other hand, we propose qta , which is called latent influence embedding and describes the time-dependent latent influence of user ua on other users at time t. Consequently, we have Qt = {qta } ∈ RN×D .

In most previous works [Wu et al., 2017b], time-dependent latent preference and time-dependent latent influence were considered equal. In our work, we argue that both terms do not describe the same concept because users may exaggerate or diminish their specific tastes and characters due to some reasons. For example, an introverted user may perform actively in SNSs as he might want to appear outgoing; meanwhile, another user may hide his preferences on some features, such as crime movies, to protect his privacy. Therefore, we propose an effective strategy to correlate uta and qta here.

We use the recommendation transformation factor matrix, denoted as T ∈ RN×D , to describe the change from users' preferences to users' influences on other users. Each row in T reflects the extent to which the corresponding user exaggerates or diminishes each feature. Furthermore, users' trust degrees on others vary. Therefore, we propose f t-1 a to denote the vector of the trust score of user ua on his friends at time t-1. Specifically, the b-th element in f t-1 a is user ua's trust score in user ub at time t-1. Besides, let N t a denote the set of linked users of ua till time t and I ta denote the friend indicator vector. I tab equals 1 if b ∈ N t a , otherwise it equals 0. Here, one rational way to set f t-1 a is to use the node proximity between the user and his friends: I t-1 a ◦(pt-1 a (P t-1 )T ), where ◦ denotes the Hadamard product operation. In addition, we need to standardize the product to ensure the trust scores sum of 1. Thus, we employ ˜ qt-1 a to represent the time-dependent latent influence of friendship on user ua:

where τ represents the standardization function.

Integrating Impact Factors of User Preference. To predict the new preferences of user ua at time t, we need to integrate the user preference embedding ut-1 a and the latent influence of friendship on user ua, ˜ qt-1 a . In [Wu et al., 2017b], the author implemented this idea by linear combination. Inspired by [He et al., 2017], we believe that the simple linear combination of ut-1 a and ˜ qt-1 a will limit the representation capability of the model.

A standard Multi-Layer Perceptron (MLP) is adopted in our model to identify the nonlinear interaction between ut-1 a and ˜ qt-1 a . The output of the user preference hidden layer is the latent preference prediction vector of user a at time t, ˆuta . And we obtain ˆU t = {ˆuta } ∈ RN×D .

The MLP model under the user feedback model is defined as:

where nf denotes the number of feedback hidden layers, and WL, bL denote the weight matrix and bias vector. No social influence is present at time 1; thus, we set z1 a1 = φf1 (u1a , 0).

Item Attribute

In our model, we suppose that the item attributes change over time (e.g., a restaurant serves different food in different seasons). We utilize the LSTM recurrent NNs to determine the inherent item dynamics instead of the states of items. This technique can help address the vanishing gradient problem and enables us to incorporate past observations and predict future trajectories in an integrated manner. We use vt i to denote the latent attributes embedding of item vi at time t. In addition, we use a nonparametric model to learn the inherent item dynamics. Then, we can extrapolate the future behaviors of the items. Here, our model learns only the dynamics of items and not their states.

The parameters of an item are dependent on its popularity and the users who have consumed it. Accordingly, the input of the item attribute model are items with ratings from users at a previous time. Then, we use a transformation matrix to learn how to project this information into an embedding space, and obtain the item latent vector yt i , which serves as the input to the LSTM. The output of the item attribute part vt i is the latent attribute embedding of item vi at time t: vt i = LSTM(vt-1 i , yt i ).

Objective

The output of the user preference part and the item attribute part serves as the input of the recommendation output layer. The states of user ua and item vi change with time, but we assume that some components of them still remain stationary, such as the item genre or user gender. Thus, we propose the dynamic vectors ˆuta and vt i with stationary components ua and vi: ˆ rtai = sigmoid(< ˆuta , ¯ vt i > + < ua, vi >), where <,> denotes the inner product operation and ¯ vt i is the affine function of vt i . The loss function of user feedback model is defined as follows:

3.4 Social LinkModel

The construction of a social link is mainly determined by two factors. First, users who share similar consumption preferences have a high probability to form a link connection. This phenomenon is called homophily effect. Second, users who have high node proximity are highly likely to be associated with one other and make friends.

Hence, given the latent link embeddings and latent preference embeddings, this model aims to estimate the timedependent pairwise link probability of nodes. We use the softmax function to define the conditional link probability of user ub on ua at time t:

where g is the function that map nodes ua and ub to their estimated link score.

Furthermore, we maximize the likelihood function for the global social link modeling:

When predicting user ua's link probability at time t, an intuitive method to combine the homophily effect and node proximity involves first measuring the similarity of user preference and user link embeddings between user ua and others directly and then integrating the two similarities via linear addition [Wu et al., 2017b].

where ˆ sta is the link probability vector of ua at time t, σ is the linear addition function.

However, this simple method ignores the nonlinear relationship among the heterogeneous factors. In the social link model, we explore the nonlinear interaction between the homophily effect and node proximity, which lets a deep NN to learn the complex interactions between the two factors.

Input Layer. Two components ut-1 a and pt-1 a serve as the input of this layer. One component captures the latent information of the user preference, and the other component represents the latent structure of user ua.

Hidden Layer. After feeding ut-1 a and pt-1 a to the multilayer NN, we obtain htak from the output of the last hidden layer. htak represents the abstract embedding, which bridges the preference information and social structure information of user ua.

where ns represents the number of link hidden layers and φs denotes the activation function. The homophily effect is absent at time 1, so we set h1a1 = φs1 (0, p1a ).

Output Layer. In this layer, the output of the last hidden layer is transformed into a probability vector ˆ sta , which is the link probability of ua at time t.

We denote the time-dependent user neighborhood embedding of user ua at time t as eta and assume that eta is evolved from user abstract embedding htak . In addition, We denote Et = {eta } ∈ RN×D . Therefore, the regularization of this evolution is defined as:

To be detailed, we obtain

which can be fed into Eq. 4.

Predicting all the missing links in social networks is computationally inefficient. To address this issue, we apply negative sampling procedure [Jamali et al., 2011]. Thus, we minimize the cross-entropy loss function defined as

where Z + ⊂ Z denotes the set of positive link interactions in Z, and Z - ⊂ Z denotes the set of negative interactions in Z.

3.5 Joint Training

To penalize large deviations of user embedding over time, we obtain

The whole loss function of our framework is defined as

Algorithm 1 Joint training of our model

• Input: latent dimension D, the number of timestamps T, batch size B, the feedback sequence C, the social link sequence S

Output: All parameters in our framework θ that minimize the total loss L

1: repeat

• 2: Sample a batch of (ua, vi, Cai = {C1 ai , ..., CT ai }, C∗i = {C1 ∗i , ..., CT ∗i }, Na = {N 1 a , ..., N T a }, Za ⊂ Z) of size B
• 3: for t ← 1 to T do
• 4: Accumulate feedback prediction loss Lu by Eq. 3
• 5: Accumulate link prediction loss Ls by Eq. 10
• 6: Accumulate evolution smoothness loss Lr by Eq. 11
• 7: end for
• 8: Accumulate the total loss L by Eq. 12
• 9: Take a gradient step to optimize L
• 10: until L converges or is sufficiently small
• 11: return θ

where λ is the trade-off parameter between user feedback prediction loss and social link prediction loss. β regularizes the evolution of user embeddings over time.

We implement our neural framework with TensorFlow to jointly train the multiple optimization objectives in Eq. 12 by performing stochastic gradient descent with mini-batch Adam. Algorithm 1 illustrates the SGD-based joint training procedure of our model.

Our model has two variants. If we do not minimize the social link prediction loss, then the degenerated model NJMF can be used to make direct user feedback prediction. If we disregard the optimization of user feedback prediction loss, then we can use the degenerated model NJM-L to make a direct social link prediction.

4 Experiments

In this section, we describe the two-fold experiments for feedback prediction and link prediction. The source code is available at https://github.com/NJMCODE2018/NJM.

4.1 Experimental Setting

We evaluate our model on two benchmark datasets, i.e., the who-trust-whom online product sharing dataset Epinions and the location based social networking dataset Gowalla. In the data preparation procedure, we filter out users with less than two feedback records and two social link records. Table 1 shows the basic statics of the two datasets after filtering. During data splitting, we use the data up to time T as the training data and the new behaviors in T+1 as the test data. Without loss of generality, we normalize the user feedback ratings into the interval [0,1].

4.2 Feedback Prediction

Compared Algorithm. We compare our model with the following feedback prediction algorithms: PMF [Mnih and Salakhutdinov, 2008], TimeSVD++ [Koren, 2010], RRN [Wu et al., 2017a], NCF [He et al., 2017], FIP [Yang et al., 2011], ELJP [Wu et al., 2017b]. FIP and ELJP are joint training methods. We analyze all algorithms by measuring the accuracy of feedback prediction based on root mean-square error (RMSE) and we report the results with different numbers of dimensions. For fair comparison, we choose the best results of all algorithms to represent the best performances.

Performance Comparison. We observe from Figure 2 that NCF generates better results than MF based methods, and this comparison shows that applying deep learning methods on learning nonlinear interactions between users and items is effective. The experimental results show that our model achieves promising prediction effectiveness, yielding 7.4% and 9.1% improvements on Epinions and Gowalla data, respectively, over the best baselines. These results demonstrate that the neural structures of our model can accurately capture the dynamic user preferences with social influence and dynamic item attributes. Specifically, NJM performs better than NJM-F, which explains the benefits of jointly training the perspectives in feedback prediction.

4.3 Link Prediction

Compared Algorithm. Next, we quantitatively compare the proposed method with all the following link prediction algorithms: AA [Liben-Nowell and Kleinberg, 2007], Node2Vec [Grover and Leskovec, 2016], SNE [Liao et al., 2017], FIP [Yang et al., 2011], ELJP [Wu et al., 2017b]. We use feedback records as the attributes of users and items in SNE. For convenient calculation, we follow the same procedure as one applied by [Wu et al., 2017b] to process link prediction: for a test user ua, we randomly sample 100 negative users that do not link to user ua untill time t. Then, we mix these negative users and those positive linked users to select top K potential linked users as the link prediction results. We adopt three widely-used metrics: precision@K, recall@K, and F1. Here, we set K = 5 in the evaluation.

Performance Comparison. From the prediction results displayed in Figure 3, we observe that ELJP shows great performance. This proves that leveraging the homophily effect boosts social link prediction. Our model also has the best predictive power among all the proposed models on the Epinions dataset, which incorporates social network information and user feedback. This finding illustrates that exploring the high-level interactions between node proximity and the homophily effect is helpful. Moreover, our model exhibits better performance than NJM-P, and this result shows the power of jointly training for link prediction. The evaluation of different approaches on Gowalla shows similar performance and is not presented here due to space limitation.

4.4 Parameter Exploration

We set β 0.01 in Epinions data and 0.1 in Gowalla data. In addition, we explore how parameter differences influence the performance of our model through an in-depth analysis.

Neural Architectures. We apply different architectures of hidden layers in the user feedback and social link models in our framework to evaluate the model performance. We follow a tower pattern, where each successive layer has half the number of neurons of the lower layer. For example, if the number of latent dimensions is 10 and the number of hidden layers is 3, then the sizes of the layers are 40 → 20 → 10. We evaluate the performance of the two models by varying the number of hidden layers from 0 to 3 with the number of latent dimensions D = 10. Table 2 demonstrates the prediction performance with different numbers of hidden layers in the two models. We find that 2 is the best number of hidden layers in both the models, considering the cost of training time and prediction results. Due to space limitations and the fact that the results on Gowalla data have similar performance, we only report the experimental results on Epinions data here.

Trade-off Parameter λ. λ is the trade-off parameter between user feedback prediction loss and social link prediction loss.

We set λ 0.1 in Epinions data and 1 in Gowalla data, in view of the balance of the two prediction tasks.

Recommendation Transformation Factor. We also investigate the effect of the recommendation transformation factor matrix T on feedback prediction. When the recommendation transformation factor is not considered, it means that T is fixed to be an all 1's matrix and untrainable. Figure 4 shows that the performance of NJMwith trainable T is superior over the one with untrainable T on the two datasets. This demonstrates the usefulness of the proposed recommendation transformation factor matrix.

5 Conclusion

In this work, we propose a general end-to-end neural framework for modeling the evolution of user feedback and social links in dynamic social networks. We leverage sophisticated NNs to describe dynamic user preferences, dynamic item attributes, and time-evolving social links in a unified manner. We then obtain insights into the formation of the two user behaviors with social influence and the homophily effect using deep NNs. The experimental evaluation demonstrates the effectiveness of the introduced model.

People tend to form various communities according to their social relations, and these communities should have different contributions to the formation of user preferences, which is called the community effect. An interesting future work is the modeling of user feedback with social influence and the community effect. Our future work is thus to investigate this problem by expanding our model.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China under Grant No. U1636116, 11431006, 61772289, Research Fund for International Young Scientists under Grant No. 61650110510 and 61750110530, The Ministry of education of Humanities and Social Science project under grant No. 16YJC790123.