Continuous-Time Graph Learning for Cascade Popularity Prediction

1 Introduction

The information propagation, aka the information cascade, is ubiquitous on online social networks, which records human behaviors in posting and accessing information. For example, on Twitter, a tweet posted by a user may disseminate to other users, and such retweeting behaviors between users can be denoted as an information cascade. Predicting the popularity of such information cascades could help people understand the information propagation better and is crucial for numerous applications such as viral marketing [Leskovec et al., 2007], scientific impact qualification [Guo and Suo, 2014] and item recommendation [Wu et al., 2019].

Up to now, lots of attempts have been made on this problem. In the early stage, researchers extracted manual features to represent a cascade [Cheng et al., 2014; Szab´o and Huberman, 2010]. However, these methods are based on hand-designed features with a relatively large number of human efforts and may lose useful information during the diffusion behavior of a cascade. Different from feature-based methods, some researchers considered the cascade as a diffusion sequence and employed sequential models like recurrent neural networks to capture the evolution pattern of cascades [Liao et al., 2019; Cao et al., 2017; Yang et al., 2019], while the structural information within the cascade has not been fully exploited yet. Recently, graph representation learning methods were introduced to further improve the prediction performance [Li et al., 2017; Chen et al., 2019b; Chen et al., 2019a; Xu et al., 2021; Tang et al., 2021]. These methods utilized the social network and cascade graph to learn the structural and temporal information within each cascade.

∗Corresponding Author

Although insightful, most of the existing methods solely predict the popularity of each cascade within its own sequence, see Figure 1 (b). We argue that there are two essential factors that are not well considered by previous methods. Firstly, different cascades can be correlated with each other because of the shared users or similar semantics. For example, in Figure 1 (b), we aim to predict the popularity of cascade c1 and existing methods can only learn from the propagation sequence of c1 itself. However, if we additionally consider cascade c2, we can find that both c1 and c2 contain user u2 which seems to be a popular user with many retweets, and this is helpful for predicting the popularity of c1. Secondly, the states of users are often evolving in a continuous manner (e.g., a user is likely to gradually change his interests according to the information he/she received from the social network at different times), which cannot be captured by existing methods either.

To tackle the above issues, we propose a Continuous-Time graph learning method for Cascade Popularity prediction, namely CTCP. To model the correlation between cascades, we first combine all cascades into a dynamic diffusion graph as shown in Figure 1 (c), which can be considered as a universal sequence of diffusion behaviors (i.e, user-cascade and user-user interactions). Then, we propose an evolution learning module to chronologically learn on each diffusion behavior by maintaining a dynamic representation for each user and cascade that evolves continuously as the diffusion behavior happens. When a diffusion behavior happens, this module first encodes the information of a diffusion behavior into a message and then fuses the dynamic representations of related users and cascades with the generated message. Next, a cascade representation learning model is proposed to generate the static and dynamic cascade embeddings by aggregating user representations from both temporal and structural perspectives. Based on the generated embeddings, the prediction module finally computes the cascade popularity. The main contributions of the paper are summarized as follows.

• Different from previous methods that only learn from the own sequence of each cascade, we propose a continuous-time graph learning method to explore the correlations of different cascades by a dynamic diffusion graph and explicitly learn the dynamic preferences of users in the network.
• We maintain dynamic representations for users and cascades and design an evolution learning module to encode the information of a diffusion behavior into a message and continuously update the dynamic representations by fusing the previous dynamic representations with the message in a recurrent manner.
• A cascade representation learning module is proposed to capture the temporal and structural information of a cascade, which leverages the sequence and graph structure to aggregate representations of users.

2 RelatedWork

2.1 Cascade Popularity Prediction

The cascade popularity prediction problem aims at predicting the future size of an information cascade. Many efforts have been paid to this problem. In the early stage, researchers represented a cascade as some handcrafted features such as content features and user attributes [Cheng et al., 2014; Szab´o and Huberman, 2010]. However, these methods need a relatively large number of human labor to design or select and have limited generalization ability.

Different from the feature-based methods, some researchers considered the cascade as a diffusion sequence of users and employed the sequence-based model to learn the evolution pattern of a cascade [Liao et al., 2019; Cao et al., 2017; Yang et al., 2019]. For example, Cao et al.[2017] utilized the Gated Recurrent Unit (GRU) to learn a path-level representation and aggregate path representation into cascade representation by different learnable weights. Though the sequence-based methods achieve considerable performance, the structural information of cascades is not well explored.

To fully utilize the temporal and structural information within cascades, some graph-based methods have been proposed [Li et al., 2017; Chen et al., 2019b; Chen et al., 2019a; Xu et al., 2021; Tang et al., 2021], which modeled a single cascade as a graph evolving with time and leveraged the graph representation learning method to learn cascade representations from cascade graphs. However, these methods predict the popularity of each cascade separately and thus neglect the correlation between cascades. Some recent methods model the evolution of multiple cascades by considering it as a sequence of graph snapshots sampled at regularly-spaced times [Wang et al., 2021; Sun et al., 2022], but these methods discrete the continuous timestamps into several regularly-spaced time steps and thus can not model the continuous evolution of user preferences. Moreover, these methods may have high memory overhead, because it needs to load a whole graph snapshot at one time.

In summary, although insightful, existing methods have not well addressed the issues of correlation between cascades and the dynamic evolution of user preferences.

2.2 Graph Representation Learning

In recent years, the Graph Neural Network (GNN) has achieved superior performance on graph representation learning. To be better in accordance with real-world scenarios, some researchers have further designed heterogeneous GNNs and dynamic GNNs [Kazemi et al., 2020; Wang et al., 2020; Huang et al., 2021]. For example, Schlichtkrull et al.[2018] focused on the relation learning in knowledge graphs. Wang et al.[2019] and Hu et al.[2020] studied heterogeneous graphs based on meta-paths and the attention mechanism. Some researchers [Pareja et al., 2020; Sankar et al., 2020] treated a dynamic graph as a sequence of snapshots, while others [Xu et al., 2020; Chang et al., 2020; Rossi et al., 2020] modeled each dynamic graph as a temporal graph or a sequence of events.

In this paper, we investigate the correlation between cascades and the dynamic user preferences by considering the evolution of cascades as a continuous-time graph.

3 ProblemFormulation

Cascade. Given a set of users U, a cascade c records the diffusion process of a message m among the users U. Specifically, we use a chronological sequence gc (t) =

{(uci , vc i , tci )}i=1,...,|gc (t)| to represent the growth process of cascade c until time t, where (uci , vc i , tci ) indicates that vc i forwards the message m from uci (or we can say that vi participates in cascade c through ui). In addition, we use (uc0 , tc0 ) to denote that uc0 publishes the message m at tc0 (or we can say that uc0 begins cascade c at tc0 ).

Diffusion Graph. Based on the above definitions, we use the diffusion graph G td = {(ui, vi, ci, ti)|ti < t} to denote the diffusion process of all cascades until t. Here (ui, vi, ci, ti) is a diffusion behavior representing that vi participates in cascade ci through ui at ti. The diffusion graph G td can be considered as a chronological sequence of diffusion behaviors as shown in Figure 1 (c).

Cascade Prediction. Given a cascade c begins at tc0 , after observing it for time to, we want to predict its incremental popularity ∆Pc = |gc (tc0 + tp)| - |gc (tc0 + to)| from tc0 + to to tc0 + tp, where tp >> to is the prediction time.

Most of the previous methods consider the task as a single cascade prediction problem, that is, learning a function f : gc (tc0 + to) → ∆Pc that predicts the incremental popularity of a cascade only based on its own historical observation. However, the collaborative signals between the cascades are ignored, which motivates us to design our new method to consider other cascades when predicting the incremental popularity of a cascade. Specifically, we learn a function f : gc (tc0 + to) ×Gtc0+to d → ∆Pc which not only considers the information of a single cascade but also takes the historical diffusion on the social network into account.

4 Methodology

As shown in Figure 2, we first consider all cascades into a chronological sequence of diffusion behaviors (i.e., the diffusion graph). Then we learn on each diffusion behavior sequentially, where we maintain continuously evolving representations for cascades and users to explore the dynamic preference of users and the correlation between cascades. During the sequential learning process, whenever the observation time to + tc0 of a cascade c is reached, we predict its incremental popularity ∆Pc.

Specifically, our method consists of three components: 1) Evolution learning module maintains dynamic states (i.e., the dynamic representation) for users and cascades, which models cascades in diffusion behavior level (micro). 2) Cascade representation learning module generates the embeddings of cascades by aggregating user representations from different perspectives, which models cascades in a diffusion structure level (macro). 3) Prediction module gives the prediction of the incremental popularity of cascades.

4.1 Evolution LearningModule

Dynamic States. We first introduce the dynamic states for users and cascades. From the perspective of information diffusion, there are two roles of a user: originator and receiver. For example, in a diffusion behavior (u, v, c, t), user u acts as the originator of the message, and user v acts as the receiver of the message. Thus, we maintain two types of dynamic states sou (t) and sru (t) for a user to describe his originator role and receiver role respectively. Besides, we maintain a dynamic state sc(t) for every cascade c to memorize its diffusion history, which can help users get information from previous participating users in the cascade. The above dynamic states are initialized to zero vectors and learned from the global diffusion behavior sequence.

Dynamic State Learning. When a diffusion behavior (u, v, c, t) happens, the dynamic states of the corresponding users and cascade should be updated. Naturally, the behaviors of a user (cascade) can be considered as a sequence and sequential models like the recurrent neural network can be employed to learn dynamic states from the sequence of a user (cascade). In addition to the own behaviors of a user (cascade), there are also global dependencies needed to be considered. For example, when a user u participates in a diffusion behavior (u, v, c, t), he may also be influenced by the users who previously participated in the cascade c. To this end, we employ a recurrent neural network fr(·) to update the dynamic states of users and cascades globally. Specifically, when a diffusion behavior (u, v, c, t) happens, we update the states of u, v, c by fr(·). The updating process consists of two steps: interaction encoding and state updating. In the interaction encoding, we encode the information of diffusion behavior (u, v, c, t) and generate message mu(t), mv(t), mc(t) for u, v and c to guide the subsequent state updating process. Assuming the state of u before t is sou (t-), we generate message representation for user u by the following mechanism,

where || is the concatenation operation, ∆tu is the time interval since the last updating of users u (i.e., ∆tu = t - t-u and t-u is the last time where u was updated), and f tu is the temporal feature learned from a series of cosine basis functions.

After generating the message representation, we fuse the old dynamic state sou (t-) with the message representation mu(t) to get the updated states sou (t) by GRU [Cho et al.,

The updating process of user v and cascade c is the same as user u in addition to different learnable parameters.

4.2 Cascade Representation LearningModule

In this module, we generate embeddings for cascades by aggregating representations of participating users. Specifically, we learn the temporal and structural characteristics of a cascade by leveraging the diffusion sequence and cascade graph to aggregate representations of users respectively. Besides the dynamic states sou (t) and sru (t) of users, we also introduce the static state su to represent the static preference of a user u. The static state is initialized randomly and learnable during the training process.

Temporal Learning. Given a cascade c, we organize it as a diffusion sequence of users Uc =

(u1, t1), (u2, t2), ..., (un, tn) where (ui, ti) indicates that user ui participate in the cascade c at ti after the publication of the cascade. The target of this module is to learn the temporal pattern from the diffusion sequence such as the shortterm outbreak of user participation. The direct way to learn the temporal pattern is feeding participating users' representations sequentially into a recurrent neural network, however, it may neglect the time information in the diffusion sequence since it can not distinguish users participating at different times. Inspired by the position embedding technics [Vaswani et al., 2017], we divide the observation time to into nt slots [0, t0 nt ), [ t0 nt , 2 t0 nt )..., [(nt - 1) t0 nt , to) and preserve a learnable embedding eti for every time interval [i t0 nt , (i + 1) t0 nt ) to distinguish users that participate in the cascade at different time. Besides, we also introduce another learnable parameter ep to strengthen the path information, where epi is a position embedding for the ith participating users. We get the user embedding zsui by first adding these two embeddings to the states of users and then feeding the sequence of user embeddings to the Long Short-Term Memory (LSTM) [Hochreiter and Schmidhuber, 1997] to get the cascade temporal embedding hsc,t , that is,

where [ti] is the time slot that ti belongs to, i.e, [ti] ∗ t0 nt ≤ ti < ([ti] + 1) ∗ t0 nt . Here the superscript of hsc,t means it is the static temporal representation and we also generate a dynamic temporal representation hdc,t by the above equation except using different LSTM parameters and user representations (i.e., dynamic states).

Structural Learning. Besides the order and time interval of participating users, the cascade graph also plays an important role in popularity prediction. For example, a deeper cascade may get more popularity since it influences the users who are far away from the original user [Cheng et al., 2014]. The cascade graph can be considered as a directed acyclic graph (DAG) with a root node (the user who posts the message), where a path from the root node to other nodes represents a diffusion process of a message in the social network. Though graph neural networks like GCN can learn graph structure, it may be difficult to model deep cascade paths [Tang et al., 2021]. Inspired by [Tai et al., 2015; Ducci et al., 2020], we employ a modified LSTM and aggregate representations of users on the cascade graph along the direction of information flow. Formally, let S(u) and T (u) be the users that u receives messages from and sends messages to, i.e., there are edges pointing from S(u) to u and u to T (u). Then we employ the following mechanism to propagate the information from root nodes to leaf nodes.

After propagating the information in the graph, we sum the leaf nodes' representations to get the cascade embedding hsc,↑ = ∑ hsleaf,↑ . Besides, we reverse the edge direction of the cascade graph and generate another cascade representation hsc↓ from leaf to root. Finally, we concatenate the hsc,↑ and hsc,↓ and feed it to an MLP to get the final structural representation hsc,s . Here the superscript of hsc,s represents the static structural embedding of the cascade as in the temporal learning module. We also generate the dynamic representation hdc,s by the same mechanism in Equation (6) except using different parameters and user representations.

Embedding Fusion. In this module, we fuse the temporal embedding and structural embedding into a cascade embedding. For static embedding hsc,t and hsc,s , we get the merged embedding hsc by concatenating them and then feed it into an MLP. The merge process of the dynamic embedding is slightly different from that of the static, where we split the participating users into two parts: the users u and v participating in the last diffusion (u, v, c, t) of a cascade c and others. The last two users u, v's dynamic states are used to merge with the dynamic cascade state sc(t) and the others are used to generate the temporal and structural embedding hdc,t and hdc,s . The reason for this is that the last two users' dynamic states are updated from sou (t-), srv (t-) to sou (t), srv (t) by the updater in (3) and this make the gradients can be propagated back to the updater through them, which makes them different from the dynamic states of other users. Formally, the merge process of the dynamic representation can be represented as

where tco is the publication time of c and eg is another position embedding for publication time like Equation (5).

4.3 PredictionModule

In this module, we give the prediction of incremental popularity by merging the prediction result from static embedding hsc and dynamic embedding hdc .

where the fstatic(·) and fdynamic(·) are two MLP functions and λ is a hyperparameter to control the weight of static result and dynamic result.

We use the Mean Squared Logarithmic Error (MSLE) as the loss function, which can be formulated as follows,

where n is the number of training cascades.

5 Experiments

In this section, we conduct experiments on three datasets to evaluate the effectiveness of our approach.

5.1 Descriptions of Datasets

We use three real-world datasets in the experiments, including the cascades in social platforms (Twitter and Weibo) and academic networks (APS).

• Twitter [Weng et al., 2013] contains the tweets published between Mar 24 and Apr 25, 2012 on Twitter and their retweets during this period. Every cascade in this dataset represents the diffusion process of a hashtag.
• Weibo [Cao et al., 2017] was collected on Sina Weibo which is one of the most popular Chinese microblog platform. It contains posts published on July 1st,2016 and their retweets during this period. Every cascade in this dataset represents the diffusion process of a post.
• APS 1 contains papers published on American Physical Society (APS) journals and their citation relationships before 2017. Every cascade in this dataset represents the process of obtaining citations for a paper. Following previous works [Cao et al., 2017], transformation and preprocessing are taken to make paper citation prediction analogy to the retweet prediction.

Following Xu et al.[2021], we randomly select 70%, 15% and 15% of the cascades for training, validating and testing. For data preprocessing, we set the observation window of a cascade to 2 days, 1 hour and 5 years on Twitter, Weibo and APS. For Weibo and Twitter, we predict cascades' popularity at the end of the dataset, while we predict cacades' popularity 20 years after its publication for APS. The cascades whose observed popularity |c(tc0 + to)| is less than 10 are discarded and for cascades whose |c(tc0 +to)| is more than 100, we only select the first 100 participants. Moreover, to ensure that there are adequate times for cascades to accumulate popularity and to avoid the effect of diurnal rhythm [Cao et al., 2017], we select the cascades published before April 4th, published between 8:00 and 18:00, and published before 1997 on Twitter, Weibo and APS, respectively. The above preprocessing process also follows previous methods [Xu et al., 2021; Cao et al., 2017]. Table 1 shows the statistics of the datasets.

5.2 Baselines

We compare our method with the following baselines, where the first two methods (i.e., XGBoost and MLP) additionally need hand-designed features (see details in Section 5.4):

• XGBoost belongs to the gradient boosting algorithm, which is a widely used machine learning method [Chen and Guestrin, 2016].
• MLP uses the multilayer perceptron to compute on the features of each cascade.
• DeepHawkes [Cao et al., 2017] treats each cascade as multiple diffusion paths of users and learns sequential information of cascades through the GRU.
• DFTC [Liao et al., 2019] considers each cascade as a popularity count sequence and uses the Convolutional Neural Network (CNN), LSTM and attention mechanism to learn the cascade representation.

1 https://journals.aps.org/datasets

• MS-HGAT [Sun et al., 2022] builds a sequence of regularly-sampled hypergraphs that contain multiple cascades and users, and then learns on hypergraphs for computing the representations of cascades.
• CasCN [Chen et al., 2019b] treats each cascade as a graph sequence and uses the GNN and LSTM to learn cascade representations.
• TempCas [Tang et al., 2021] additionally designs a sequence modeling method to capture macroscopic temporal patterns apart from learning on the cascade graph.
• CasFlow [Xu et al., 2021] is the state-of-the-art method for cascade prediction, which first learns users' representations from the social network and the cascade graph and then employs the GRU and Variational AutoEncoder (VAE) to get representations of cascades.

5.3 EvaluationMetrics

We choose four widely used metrics to evaluate the performance of the compared methods, including Mean Squared Logarithmic Error (MSLE), Mean Absolute Logarithmic Error (MALE), Mean Absolute Percentage Error (MAPE) and Pearson Correlation Coefficient (PCC). Among these metrics, MSLE, MAPE and MALE evaluate the prediction error between the predicted value and the ground truth from different aspects and PCC measures the correlation between predicted value and the ground truth.

5.4 Experimental Settings

For XGBoost and MLP, we follow Cheng et al.[2014] and extract five types of features (i.e., edge number, max depth, average depth, breath of cascade graph, and publication time of the cascade) as the hand-designed cascade features. We set the dimension of dynamic states of users and cascades, as well as the cascade embedding to 64. The dimension of position embedding is set to 16. The time slot number nt is set to 20 and the fusion weight λ is 0.1. For training, we adopt the Adam optimizer and use the early stopping strategy with a patience of 15. The learning rate and batch size are set to 0.0001 and 50. Our code can be found at https://github.com/ lxd99/CTCP.

5.5 Performance Comparison

Table 2 reports the performance of different methods, and some conclusions can be summarized as follows.

Among the three groups of methods, feature-based models perform the worst among all baselines, which reveals that there are complex evolution patterns of the cascade size that can not be captured by the hand-designed features. Moreover, graph-based models show better performance than sequencebased models, implying the necessity of exploiting the structural and temporal information carried in the cascade graph.

CTCP achieves significant performance improvement w.r.t. the state-of-the-art baseline (i.e., CasFlow) on Twitter and APS, demonstrating the effectiveness of the proposed method. This improvement may be due to the fact that we learn the dynamic representations of cascades and users collaboratively, which can capture the correlation between cascades and the dynamic user preferences outside of a single cascade. The insignificant improvement of CTCP on Weibo may be due to the short time period of Weibo (1 day compared to 1 month and more than 100 years on Twitter and APS respectively) and the preferences of users may not evolve during such a short period, which makes CTCP have no advantages over CasFlow. Additionally, modeling multiple cascades via the sequence of graph snapshots like MS-HGAT does not achieve considerable performance. Because the diffusion behaviors within a snapshot are thought to happen at the same time which will lose fine-grained temporal information. Moreover, MS-HGAT needs to load the snapshot into memory at one time, which makes it can only run on the smallest dataset (i.e., Twitter).

5.6 Sensitivity to Publication Time

To explore the sensitivity of different models to the publication time of cascades, we plot models' performance on cascades with different publication times on Twitter and APS. Specifically, we divide the cascade into five groups according to their publication time: cascade whose publication time is at the 0th to 20th, 20th to 40th, 40th to 60th, 60th to 80th and 80th to 100th percentile, and plot the best five models' performance. From Figure 3, we can observe that CTCP can achieve considerable performance on different cascades consistently. Besides, as time goes on, the performance of CTCP consistently improves on these two datasets. This is because the evolution learning module of CTCP keeps updating the dynamic states of users and as time goes on more and more user behaviors are observed, which provides richer information to model the preference of users. Other models only learn from the own diffusion process of cascades and can not learn this dependency.

5.7 Ablation Study

We compare CTCP with the following variations on Twitter and APS to investigate the contribution of submodules to the prediction performance.

• w/o EL removes the evolution learning module.
• w/o SE removes the static representation of users.
• w/o SL: removes the structural learning module in the cascade embedding learning process.

From Figure 4, we can observe that: Firstly the performance of w/o EL and w/o SE varies on APS and Twitter, for example, w/o SE achieves the best performance on Twitter and the worst performance on APS. This indicates that the growth of the cascade size is controlled by multiple factors and it is necessary to consider the dynamic preference and static preference of users simultaneously. Secondly, the structural learning module utilizes the cascade graph to generate the cascade embedding which helps improve the prediction performance by capturing the evolution pattern of a cascade at a macro level.

5.8 Cascade Representations Projection

To confirm the effectiveness of the learned cascade representations, we project the cascade representations of CTCP and CasFlow on Twitter into a two-dimensional space, using tNSE [van der Maaten and Hinton, 2008]. Results are represented in Figure 5. Remarkably, we find that the learned representations of CTCP can capture the evolution pattern of cascade popularity, suggested by the fact that from right-top to left-bottom the node color of CTCP changes from red to dark blue continuously in Figure 5 (a). While for CasFlow, nodes with different colors are mixed. This may be because CTCP models the correlation of cascades while CasFlow does not, which can help the model capture the collaborative signals between cascades and learn a better cascade representation.

6 Conclusion

In this paper, we studied the problem of cascade popularity prediction and pointed out two factors that are not considered well in the existing methods, i.e., the correlation between cascades and the dynamic preferences of users. Different from previous methods that independently learn from each cascade, our method first combines all cascades into a diffusion graph to explore the correlations between cascades. To model the dynamic preferences of users, an evolution learning module was proposed to learn on the diffusion graph chronologically, which maintains dynamic states for users and cascades, and the states are updated continuously once a diffusion behavior happens. Moreover, a cascade representation learning module was proposed to explore the structural and temporal information within a cascade by aggregating representations of users into a cascade embedding. Extensive experimental results on three real-world datasets demonstrated the effectiveness of the proposed method.

Acknowledgements

The authors would like to thank the anonymous reviewers for their constructive comments on this research. This work was supported by the National Key R&D Program of China (2021YFB2104802) and the National Natural Science Foundation of China (62272023).