Cascade Dynamics Modeling with Attention-based Recurrent Neural Network

1 Introduction

The emergence of social media platform has revolutionized the dissemination of information via its great ease in information delivery, accessing and filtering. In social media, online content or a piece of information could reach a large number of people by being shared and reshared among them following their social relationship, and a cascade of resharing is developed during this process. Modeling and predicting such cascade dynamics is fundamental to understanding information propagation [Huang et al., 2012], launching campaign of viral marketing [Cheng et al., 2014], and popularity prediction [Shen et al., 2014].

Existing methods fall into two main paradigms according to whether they require a diffusion model. Conventional methods for cascade prediction generally assume that the underlying diffusion model is known a priori. Typical examples include discrete-time or continuous-time independent cascade model [Cheng et al., 2013; Gomez-Rodriguez et al., 2013], discrete-time or continuous-time linear threshold model [Kempe et al., 2003], and their variants with certain constraint confined by network structure [Gomez-Rodriguez et al., 2010]. The key of these models lies in how to estimate the interpersonal influence or parameters that are used to characterize the influence and susceptibility of individuals [Wang et al., 2015]. The estimation is achieved either by exploiting the structure of social network [Kossinets et al., 2008; Gomez-Rodriguez et al., 2013] or by maximizing the likelihood of observed cascades [Tang et al., 2013]. However, the effectiveness of these methods heavily depends on the hypothesis of the underlying diffusion model, which is hard to specify or verify in practice. Consequently, although these methods gains success at characterizing the diffusion process of information, they are inappropriate for cascade prediction.

Sequential models are proposed to circumvent the problem of cascade prediction, without requiring an explicit underlying diffusion model. Sequential models focus on modeling how the historical sharing behaviors in a cascade affect the future sharing behavior, i.e., the dependence among sharing behaviors in the same cascade. For example, Manavoglue et al. [Manavoglu et al., 2003] proposed a user behavior generation method based on maximum entropy and Markov mixture model. Recently, researchers found that Recurrent Neural Network (RNN) offers a convenient and effective tool for cascade modeling [Mikolov et al., 2010; Wang et al., 2017]. In particular, Du et al. [Du et al., 2016]

proposed a RNN framework to model and predict marked cascade, called RMTPP, where timing and mark information are embedded to parameterize the generation process of cascades. The benefits of sequence modeling are two-fold: 1) It avoids strong prior knowledge on diffusion model; 2) It is flexible to capture sequential dependence or memory effect in cascades.

Traditional implementation of RNN (e.g., LSTM and GRU) employ a chain structure to capture the memory effect. However, in the scenario of cascade prediction, each cascade generally corresponds to a diffusion tree, causing cross-dependence in cascade-one sharing behavior could be triggered by its non-immediate predecessor in the memory chain. As shown in Figure ??, the resharing behavior of u3 depends on the resharing behavior of u1 rather that the resharing behavior of its immediate predecessor u2. This crossdependence cannot be captured by chain-structured sequential models. For example, for standard RNNs and RNNs with LSTM, u3 either both depend on u1 and u2 or u3 does not depend on both of them, modulated by specific memory mechanism. Taken together, we lack an effective method to capture the cross-dependence in cascades.

In this paper, we propose an attention-based RNN to capture the cross-dependence in cascade. Furthermore, we introduce a coverage strategy [Tu et al., 2016] to combat the misallocation of attention caused by the memoryless of traditional attention mechanism. Our contributions are summarized as:

• We explore the cross-dependence problem existed in RNN when being applied to model cascade dynamics, and we propose an attention-based RNN to capture cross-dependence in cascade;
• We further introduce coverage in proprosed attenionbased RNN to adjust allocation of attention, allowing alignments to better reflect the structure of propagation;
• The learned alignments in the proposed models can reflect true diffusion structure and the proposed models consistently outperform competitive baselines in two cascade prediction tasks.

2 Models

The input data is a collection of M cascades C = {Sm}Mm=1 . A cascade S = {(tk, uk)|uk ∈ U, tk ∈ [0,+∞) and k = 1, . . . ,N} is a sequence of resharing behaviors ascendingly ordered by time, where U refers to user set in cascade. The k-th resharing behavior is recorded as a tuple (tk, uk), referring to a pair of activation time and activated user. Let the history Hk be the list of activation time and activated user pairs up to the k-th resharing behavior. The objective of sequence modeling in cascade dynamics is to formulate the conditional probability of next resharing behavior p((tk+1, uk+1)|Hk).

2.1 Background

Firstly, we introduce RNN in cascade dynamics modeling. RNN is a feed-forward neural network, which can be used to generate a cascade by N -1 steps sequentially. At step k, we vectorize the k-th resharing behavior into xk as input. The input is fed into hidden units of RNN by nonlinear transformation f, jointly with the outputs from the last hidden units, updating the hidden state hk = RNN(xk, hk-1). The representation of hidden state hk can be considered as embedding of the k-th resharing behavior, and the output is trained to predict the next resharing behavior (tk+1, uk+1) given hk. In other words, we use RNN to maximize the likelihood of cascade,

The conditional probability p((tk+1, uk+1)|hk) can be decomposed into two parts, assuming that the activation time and activated user are conditionally independent with each other,

where g is a non-linear function. The output of softmax function is regarded as the transition proabilities to each possible next activated user. The function f(t; hk) refers to a temporal point process parameterized by hk. Based on sufficient observed cascades, RNN can find an optimal solution for the conditional probability of next resharing behavior in a huge functional space, avoiding the bias on diffusion model and the constraint of diffusion network. Thus, RNN offers us a promising and flexible method to capture the complex propagation patterns in cascade dynamics modeling.

2.2 CYAN-RNN

RNN suffers cross-dependence problem caused by treestructured propagation in cascade, as shown in Fig. ??. One possible solution is to construct a pooling layer above the hidden units at each step in order to build the direct dependence between the next resharing behavior and all previous resharing behaviors, i.e., p((tk+1, uk+1)|pooling(h1, . . . , hk)). The general way of pooling is to calculate a context vector

where the weight αk,i refers to the extent to which the kth resharing behavior depends on the i-th resharing behavior. Mean pooling and max pooling are two popular choices for setting weights which takes the mean or element-wise max value of all hidden states. However, these two methods still ignore the structure information in cascades. Thus we propose attention mechanism to implicitly model the structure information by automatically learning the pooling weights from the cascade data. Next we introduce the detail of attention mechanism.

Attention Mechanism

Attention mechanism is orginally used in neural machine translation (NMT). In the senario of attention-based NMT, the target words are translated by the words in source sequence and attention mechanism can automatically learn the alignment between source words and target words. For modeling cascade dynamics, we construct both source and target sequence from the observed cascade, restricting that the

(k +1)-th resharing behavior is the output of the k-th resharing behavior.

We propose a dynamic attention mechanism for CYANRNN. The proposed architecture is shown in Fig. 2. According to the architecture, we rewrite the conditional probability of next resharing behavior

The time distribution follows

where w is a scalar and W (t) , U (t) , Z (t) are parameter matrices. The expectation of Eq. (2) with respect to time t can be regarded as prediction of next activation time. The decoding state Tk for the k-th step in target sequence is computed by

where σ is a non-linear activation function, which can be either a tanh or a sigmoid function. The context vector sk is calculated by Eq. (1) where the alignment weights αk,. is updated by the context {h1, . . . , hk} and Tk-1. The weight αk,i is formalized as

where

scores the extent of the dependence between the i-th resharing behavior and the output at the k-th step, and W (a) ,U (a) are the parameter matrices. The implementation of attention mechanism is depicted in Fig. 3(a).

With the attention mechanism, the alignments αk,. can be directly updated through the cost function and exploit an expected representation sk over all historical resharing behaviors for each step k.

Coverage

In the proposed attention-based model, a majority of "attention" is dominated by a handful of influentials. It indicates that most of users are directly motivated by those influentials in cascade. However, it is generally assumed that users are actually triggered by chronologically adjacent users in cascade [Kossinets et al., 2008]. Therefore we propose coverage to adjust the misallocation of attention, leading the alignments to better reflect the true structure of propagation.

The misallocation of attention is caused by memoryless characteristic in attention mechanism. Inspired by linguistic coverage model, we formulate the general form of coverage in cascade dynamics modeling, keeping historical alignments so as to release misallocation of attention. The k-th step of coverage is defined as

Remarkably, as the increasing context and alignments, Vk,k and αk,k have no corresponding values in Vk-1,. and αk-1,.. Instead we fill up with zeros in our work. At step k, the k-th coverage serves an additional input to the attention mechanism, providing complementary information about how likely the dependence of resharing behaviors has already been explored in the past. The rewritten alignment calculation in Eq. (5) with coverage can be formalized 1 as

where W (a) ,U (a) and Z (a) are parameter matrices. We assume that the alignments would focus more on recent resharing behaviors. The assumption will be validated in section 4.

2.3 Length of Dependence

In practice, a cascade may last for a long time and the propagation length would be huge, causing an extreme computation cost when applying dynamic attention mechanism proposed in CYAN-RNN. According to the observation that users' interests concentrated more on recent resharing behaviors, we consider a hyper-parameter, length of dependence l, limiting the size of alignments so that the output can only depend on last l resharing behaviors.

3 Optimization

In this section, we introduce the learning process of our proposed models. Given a collection of cascades C = {Sm}Mm=1 , we suppose that each cascade is independent on each other. As a result, the logarithmic likelihood of a set of cascades is the sum of logarithmic likelihood of individual cascade. In this way, the negative logarithmic likelihood of the set of cascades can be estimated as

and we can learn parameters of the proposed model by minimizing the negative logarithmic likelihood argminθ L(C), where θ is the parameter set in the model. We exploit backpropagation through time (BPTT) for training. In each training iteration, we vectorize resharing behaviors as inputs, including user embedding and temporal features. The embedding matrix of users is learned along with the training process. The temporal features are assembled by logarithm time interval log(tk - tk-1) and discretization of numerical attributes on year, month, day, week, hour, mininute and second. We adopt GRU [Chung et al., 2014] to encode the k-th inputs to hk. We apply stochastic gradient descent (SGD) with minibatch and the parameters are updated by Adam [Kingma and Adam, 2015]. To speed up the convergence, we use orthogonal initialization method [Henaff et al., 2016] in training process. We also employ early stopping method [Prechelt, 1998] to prevent overfitting.

4 Experiments

In experiments, we compare our CYAN-RNN to the stateof-the-art modeling methods of cascade prediction on both synthetic and real data. The results show that CYAN-RNN performs the best in modeling cascade dynamics. Moreover, we adjust the learned alignments to the underlying social network on synthetic data, demonstrating the capability of our proposed model in network inference.

1 If we use the last coverage Vk-1,. instead of Vk,. to update ek,. at step k, we will lose certain coverage information and cause unbalanced calculation on k-th resharing behavior. This is proved by our preliminary experiments.

4.1 Baselines

Previous methods can seldom predict next propagations completely including both next activated users and activation time. To better illustrate the performance of our proposed model, we conduct experiments on two separated tasks, i.e., next activated user prediction task and next activation time prediction task. The choosen baseline models have at least one of the prediction abilities on these two prediction tasks.

• RMTPP [Du et al., 2016]: Recurrent marked temporal point process (RMTPP) is a method which can model both the next activated user and the next activation time based on RNN.
• CT Bernoulli and CT Jaccard models [Goyal et al., 2010]: They are continuous time propagation models. The propagation probabilities between two users are defined by Bernoulli or Jaccard distribution and the probabilities are decayed over time. The two models can be used to predict next activated users.
• MC-1 Model: The markov chain model is a classic sequence modeling method, depicting the generation of activated users. Here we compare with markov chain with one-order dependency.
• Poisson process model [Vere-Jones, 1988]: It is a stochastic point process model, depicting the time consuming from one resharing behavior to another. The intensity function is parameterized by a constant.
• Hawkes process model [Hawkes, 1971]: It is a stochastic point process model where the intensity function is parameterized by

where λ0 is the base rate. We set σ = 1 in our experiments.

4.2 Synthetic Data and Results Anlaysis

The goal of the experiments on synthetic data is to validate the effectiveness of our proposed models in cascade prediction tasks under different underlying network structure and different diffusion models.

Data generation. The data generation consists of two parts: network generation and cascade generation. We use Kroneck generator [Leskovec and Faloutsos, 2007] to construct two types of networks with directed edges: 1) the CorePeriphery (CP) network [Leskovec et al., 2008] (Kroneck parameter matrix [0.962, 0.535; 0.535, 0.107]), mimicking realworld social networks; 2) the Erd˝os-R´enyi random (Random) network ([0.5, 0.5; 0.5, 0.5]). In terms of cascade, we randomly choose a root user as the source of the cascade and set its activation time as zero. For each activated user, the activation time of its neighbors is sampled from a certain time distribution. The generation process is repeated in the breadth-first fashion on the network until the overall time exceeds T or no user is activated. We choose two time distributions for sampling: 1) mixed exponential (Exp) distributions, controlled by rate parameters in [0.01, 10]; 2) mixed Rayleigh (Ray) distribution, controlled by scale parameters in [0.01, 10]. In our experiments, we set the total number of users |U| = 32 and the latest time T = 100.

At the end, four datasets are generated by different combinations of network generators and propagation time distributions, denoted by (CP, Exp), (CP, Ray), (Random, Exp) and (Random, Ray). We generate 20,000 cascades in each dataset, and we randomly pick up 80% of cascades for training and the rest for validation and test by an even split.

Evaluation results. We regard the prediction task on next activated user as a ranking problem with users' transition probabilities as their scores. The prediction performance is evaluated by Accuracy on top k (Acc@k) and Mean Reciprocal Rank (MRR). The larger values in Acc@k and MRR indicate the better performance. In terms of time prediction, we use Root Mean Square Error (RMSE) between the estimated time and the ground truth. A good model should have small values in RMSE.

We first compare the prediction results on next activated user prediction task, shown in Fig. 4(a)∼ 4(d). As we can see, CYAN-RNN and CYAN-RNN(cov) perform consistently and significantly better than other baselines on Acc@1, Acc@5 and MRR in all datasets. The results indicate that our proposed methods can better predict next activated user. It is interesting to see that RMTPP has lower accuracy and MRR values than CT Bern and CT Jac in some cases, while CYANRNN and CYAN-RNN(cov) consistently performs the best. It clearly demonstrates that the proposed attention mechanism has the ability to directly capture past propagation information, which may be "forgotten" by sequential transitions in RNN, i.e., cross-dependence problem in cascade dynamics. Fig. 4(e) compares the predictive results on RMSE. We can observe that Poisson and Hawkes processes have the lowest performance, with errors larger than 2 hours. Meanwhile, the RMSE values of RMTPP and CYAN-RNN are equivalently good, while our CYAN-RNN(cov) can perform slightly better than RMTPP and CYAN-RNN. Moreover, we can observe that CYAN-RNN(cov) consistently performs better than CYAN-RNN in the two prediction tasks, implying that the coverage can release the misallocation of attention. Next we will explore how the coverage can help to boost predictive performance and better reflect the structure of propagation.

Evaluation on propagation structure. We expect to check if coverage can release the misallocation problem mentioned in section 2.2. Fig. 5(a) and 5(b) show the results. Each row in the figure corresponds to the next activated user, with its grids indicating the alignments related to already activated users. The brighter grid refers to the larger alignment. From the figure we can tell which positions in the past propagation are considered more important when predicting the next. Comparing to the alignments in CYAN-RNN, we can see that the alignments in CYAN-RNN(cov) concentrate more on unfollowed resharing behaviors, which helps to release misallocation problem.

Moreover, we wonder if the learned alignments are homologous with true propagation structure. Thus we attempt to infer the underlying network from the alignments. For uk we take the user with largest alignment as its activation user and mark them as a pair. All the pairs are accumulated in a useruser matrix. We conduct binarization on the matrix through a threshold, thus providing a 0-1 matrix which serves as the adjacency matrix of inferred network. The visualization of network inference is depicted in Fig. 6(a)∼ 6(d). High accuracy of network inference is achieved by CYAN-RNN and CYAN-RNN(cov) in both CP network and Random network. The results indicate that our proposed alignment mechanism can be natrually used in inferring hidden propagation structure, which may have some potential applications in practice, e.g., advertisement and recommendation.

4.3 Real Data and Result Analysis

Experimental setup. The real data is from Sina Weibo, a Chinese microblog website. The data is from June 1st, 2016 to June 30th, 2016. We choose the records on June 1st and extract users whose posting counts are in the range of (100, 200]. Then we filtered all the posts by those users in 30 days and extract their cascades. We drop the cascades with size larger than 1,000, as the large cascade rarely occurrs in practice and may dominate the training process. Finally, the processed data contains 2,964 users and 596,088 cascades. We use 536,240 sequences for training, 29,758 for validation and 30,005 for testing.

Prediction results. The results are shown in Fig. 4(f) and 4(g). The hyper-parameters of CYAN-RNN and CYANRNN(cov) are set as follows: learning rate is 0.0001; hidden layer size of encoder is 20; hidden layer size of decoder is 10; length of dependence is 200; coverage size is 10; and batch size is 128. We have no social networks in extracted real data, so we cannot compare our proposed models with CT Bern and CT Jac. CYAN-RNN and CYAN-RNN(cov) outperform other baselines with higher MRR values on next activated user prediction task and lower RMSE values on next activation time prediction task. Comparing to RMTPP, CYAN-RNN(cov) achieves 6.25%, 5.48% and 3.90% relative increase on Acc@1, Acc@5 and MRR respectively, and reduces 0.78% relative errors on RMSE. Comparing to CYANRNN, CYAN-RNN(cov) achieves 4.62%, 2.67% and 1.27% relative increase on Acc@1, Acc@5 and MRR respectively, and reduces 0.33% relative errors on RMSE.

5 Conclusion

In this paper, we present the cascade dynamics modeling with attention-based RNN. As we know, it is a prior attempt on cascade dynamics modeling based on RNN. Different from traditional modeling methods, RNN is a convenient and effective tool for cascade modeling, avoiding strong prior knowledge on diffusion model and being flexible to capture complex dependence in cascades. However, RNN suffers cross-dependence problem when applying in cascade dynamics modeling. Thus we propose to an attention-based RNN to capture the cross-dependence in cascade. Furthermore, we introduce a coverage strategy to combat the misallocation of attention caused by memoryless of traditional attention mechanism, leading the alignments to better reflect the true structure of propagation.

We evaluate the effectiveness of our proposed models on both synthetic and real datasets. Experimental results demonstrate that our proposed models can consistently outperform state-of-the-art modeling methods at both next activated user prediction task and next activation time prediction task. Addtionallly, CYAN-RNN(cov) performs consistently best on both synthetic and real datasets, implying that the coverage can release the misallocation of attention. Besides, we conduct experiments to explore alignment quality on network inference. The results show that the alignments from our proposed models can reflect true propagation structure, which may have some potential applications in practice, e.g., advertisement and recommendation.

Acknowledgments

This work was funded by the National Basic Research Program of China under grant numbers 2013CB329606 and 2014CB340401, and the National Natural Science Foundation of China under grant numbers 61472400, 61425016, and 61433014. Shenghua Liu is also funded by the Beijing NSF No. 4172059. Huawei Shen is also funded by Youth Innovation Promotion Association CAS.