2330Modelling Online Comment Threads from their Start

Rachel Krohn     Tim Weninger
Department of Computer Science and Engineering

University of Notre Dame

Notre Dame, IN, USA

The social Web is a widely used platform for online discussion. Across social media, users can start discussions by posting a topical image, url, or message. Upon seeing this initial post, other users may add their own comments to the post, or to another user's comment. The resulting online discourse produces a comment thread, which constitutes an enormous portion of modern online communication. Comment threads are often viewed as trees: nodes represent the post and its comments, while directed edges represent reply-to relationships. The goal of the present work is to predict the size and shape of these comment threads. Existing models do this by observing the first several comments and then fitting a predictive model. However, most comment threads are relatively small, and waiting for data to materialize runs counter to the goal of the prediction task. We therefore introduce the Comment Thread Prediction Model (CTPM) that accurately predicts the size and shape of a comment thread using only the text of the initial post, allowing for the prediction of new posts without observable comments. We find that the CTPM significantly outperforms existing models and competitive baselines on thousands of Reddit discussions from nine varied subreddits, particularly for new posts.

Discussion Threads, Online Social Media, Hawkes Process, Parameter Inference, node2vec, Reddit

§ INTRODUCTION

Online forums are an important source for discussion and information sharing. Commentary on social media posts color the presentation of the content and allow the content consumer to ask questions, engage in debate, or otherwise contribute to discussion on the topic. The nature of online social commentary has been widely studied across various contexts. Research in cyber-bullying and hate speech seeks to understand and reduce anti-social behavior, political and social scientists seek to glean public opinion from social commentary, and data scientists seek to use the structure of discussions as a way to organize information. The vast amount of publicly available, born-digital, human-generated discussion stands to significantly contribute to our understanding of information, knowledge, and social order.

Online discussions take many forms. Some communication, like emails and texts, allow a group of individuals to privately share information in a linear fashion. Social networks, however, often exhibit non-linear, public discussions between thousands of users simultaneously. Cascades of Twitter and Facebook posts have received significant attention due to their enormous popularity [1]. Typical research in these topics seeks to simulate the spread of a news article, video, or meme, and has recently been re-invigorated due to a renewed interest in the spread of misinformation. Understanding resharing and retweeting behavior is an important topic, but little attention has been given to predicting the shape of the discussion threads that accompany these social posts.

This is an extremely difficult task - it may not be possible to make accurate predictions at all [2, 3, 4]. The distribution of comment thread sizes has a very long tail, further complicating the prediction task [5].

Each online social system is slightly different, but generally discussion threads are attached to a post. Each post has a headline or title, a timestamp, and a poster (, the user who submitted the post to the system), along with an associated discussion thread. The thread itself may have one or more top-level comments that express some topically relevant fact or opinion. Each top-level comment may motivate further discussion in the form of children, grandchildren, etc. comments. In this way, a discussion thread resembles a tree, where the post itself is the root and the comments and replies represent the various branches and leaves of the tree.

Present Work. The primary goal of the present work is to predict the shape and size of these discussions. We also endeavour to accurately predict all sizes of comment threads, and to make predictions for new posts without comments.

We focus primarily on Reddit, but the dynamics that create discussion threads appear in many domains. However, the driving mechanisms can rely heavily on the underlying social network, like on Facebook and Twitter. Online discussion boards like Reddit, Digg, and YouTube are significantly different because no social network exists. Instead, any user may access and contribute to any discussion[6].

Popularity prediction models have been established using the Hawkes process [7], linear regression [8], deep reinforcement learning [9], or entity linking and LSTMs [10]. Generally speaking, the methodology of these studies watches the first several hours of a thread (or Twitter cascade) and then constructs a model to predict the remainder of the thread. The first several hours are critical because early attention is strongly correlated to high popularity [4]. Instead, we ask a more difficult question: Can final cascade size and shape be predicted when none or only a few comments are available?

To answer this question, we introduce the Comment Thread Prediction Model (CTPM) that uses the mechanics of graph representation learning algorithms like node2vec [11] to fit the parameters of a Hawkes process.

Main Findings.
Exhaustive experiments over millions of comments show CTPM is able to 1) quickly learn complex, human-interpretable parameters, and 2) accurately predict the size and shape of online discussion threads from only the post title and the submitting user, before comments are present.

§ PRELIMINARIES

Before we introduce the CTPM, this section presents several foundational concepts.

Point processes are a sequence of discrete, inter-dependent, points within a continuous space. Temporal point processes, therefore, are discrete events that occur in a continuous time. Stochastic events, like earthquakes and stock market volatility, can be modelled by point processes, which are typically defined as follows.

Let $T_1$, $T_2$, $\ldots$ be discrete event times, where the $i^\textrm{th}$ event is typically represented as $T_i$. Let $N_t$ be the count of events that occurred up to time $t$.

Let $\tau$ be a sequence of exponential random variables defined by parameter $\lambda$; then, $T_n=\sum_1^n{\tau_i}$. Typically, the values of $\tau_1$, $\tau_2$, $\ldots$ are called the inter-arrival times for a sequence of random events, and are governed by the rate represented by $\lambda$. Because $\tau$ is a sequence of exponential random variables, we call this a Poisson point process with a probability density function of $\tau$ w.r.t $t$ of $\lambda e^{-\lambda t}$.

Simply put, the rate parameter $\lambda$ indicates that events arrive at an average rate of $\lambda$ per unit time. However, $\lambda$ need not be a constant value. Instead, we may wish to define $\lambda^{(t)}$ where the rate parameter changes with $t$. These cases are called non-homogeneous Poisson point processes, and they are commonly found when one event increases the likelihood that another will occur, as in the case of aftershocks following earthquakes. One of the most well-known of these self-exciting processes is called the Hawkes process, which takes the following form:

$$\lambda^{(t)} = h(t) + n_b\sum_{i:t>\tau_i}\phi\left(t-\tau_i\right)$$

where $h$ is the base intensity, $\phi$ is a memory kernel, and $t>\tau_i$ is all of those events that occurred before $t$. This process is called self-exciting because the probability of a new event at time $t$ increases after an event at time $\tau_i$ by the kernel $\phi(t-\tau_i)$.

By analogy, events in a Hawkes process consist of two types: `immigrants' which are those events that occur without a preceding/parent event, and `offspring' which are those events that are produced by some previous event. These dynamics create many `family-trees' where immigrants are generated with a rate of $h$, and the branching factor $n_b$ regulates the number of offspring per parent event. Each offspring $T_i$ is generated after $\tau_i$ and can themselves generate offspring with rate $n_b\phi(t-\tau_i)$.

Example of a Hawkes branching process. The red node (far left) represents a social media post. Green and blue nodes represent `immigrant' and 'offspring' events respectively. Each event is generated at $\tau_i$. Immigrant events are sampled from $h(t)$, and offspring events are sampled with intensity $\phi(t-\tau_i)$ and have a branching factor of $n_b$. This Hawkes process model is a natural representation of a discussion cascade. Adapted with permission from Medvedev et al. [7]

Applying this analogy to comments in online discussion forums, Medvedev et al. defined a root node as a social media post, and `immigrants' as top-level comments, which can each have reply-comment `offspring' [7]. The example in Fig. <ref> illustrates a small discussion cascade. The Hawkes process is particularly well-suited to the modelling of discussion threads, and has been previously used to predict the final retweet cascade size and shape [12, 13] based on user history [14], circadian rhythms [15], or other user properties [16].

What remains is to define the functional forms of $h$ and $\phi$. Previously, Medvedev et al. demonstrated, based on an examination of common Reddit response times, that $h$ is best articulated as a Weibull distribution $(a,b,\alpha)$ and $\phi$ is represented by the lognormal distribution $(\mu,\sigma)$ [7]. These distributions hold regardless of the level or age of the comments. With these forms defined, the model parameters $a, b,\alpha,\mu,\sigma$ and the branching factor $n_b$ can be estimated using well defined log-likelihood functions [17] and an optimization algorithm like BFGS.

Unfortunately, this parameter estimation assumes the existence of data in the form of an existing comment thread: a minimum of 10 observed comments are required to fit parameters, and both root-level and comment replies must be present. Therefore, these models typically estimate the parameters from the first hours of a discussion thread to predict the remainder. Posts without comments cannot be predicted.

Our goal is to estimate $a,b,\alpha,\mu,\sigma, \textrm{and } n_b$ without an existing comment thread. Hence, our inference algorithm provides the ability to simulate discussions, and predict their popularity, from their very beginning.

§ COMMENT THREAD PREDICTION MODEL

Predicting the shape and size of a discussion thread or any event cascade is extremely challenging, but this task provides a rich avenue for compelling questions:

* Can discussion threads be predicted using only post features?

* Can we infer model parameters of a discussion thread that does not yet have discussion?

* How much do the early dynamics of a discussion help improve the model?

Cascade size distribution for training and testing data from Reddit. Existing models require at least 10 comments before they can generate predictions; however, we observe that the vast majority of cascades are less than 10 comments.

Typically, models simulate cascades by fitting parameters to early data, but most posts generate little discussion. Data from Reddit discussion threads, shown in Fig. <ref> and described in more detail below, illustrates that most cascades fizzle out after a few comments, although the shape of this distribution depends on the community. This further stresses the need for our cascade prediction model if we wish to predict the vast majority of cascades.

The abundance of small discussions makes existing models impractical for application to a wider set of posts. Instead of depending on observed discussion comments, we rely on parameters fit to previous similar discussions and infer new parameters based on this history.

We show that this kind of parameter-transfer works reasonably well, though it is important to recognize some of the assumptions that we make in this approach. First, we implicitly assume that the discussion contributed to a post is correlated with features of the post like the title, submitting-user, and community (, subreddit). This can be a difficult assumption to make because identical content is known to receive drastically different attention [18]. Second, we assume that similar posts should receive similar discussion. This can also be a difficult assumption because of the apparent disconnect between social media popularity and user-preference [3].

In the remainder of this section we describe the Comment Thread Prediction Model (CTPM). Our primary contribution is in the parameter inference for posts with few or no observed comments. For this difficult task the CTPM simulates comment cascades attached to new Reddit posts, before comments are present. Source code, data, and evaluation scripts are available on Github[<https://github.com/rkrohn/redditmodel>]. The CTPM contains three primary steps:

An overview of CTPM is shown in Fig. <ref>, which contains three steps:

Overall system diagram.

* Preprocess the online discussion threads from Reddit

* Construct a graph of social media posts

* Perform parameter inference for new discussion threads from the post graph

The preprocessing step prepares the training data. For each post in the training set, Hawkes model parameters are fit to existing, completed discussion threads. Next, we construct a similarity network, among all posts in the training set, that connects posts based on their titles and authors. These two steps only need to be performed once, after which the fitted training parameters and post graph can be used to simulate any number of unknown posts from the same community.

To simulate a discussion thread for a new post, the model first uses a modified node2vec process to infer simulation parameters from training data history, based on the position of the new post within the established post graph. Simulation parameters are fed into the Hawkes model defined earlier, which uses six parameters to generate a full comment thread, including tree structure and comment timestamps. If we wish to use partial observations of a discussion thread, we also include an optional parameter refitting step before simulating the comment tree.

Finally, we simulate the discussion thread discuss accuracy in the proceeding section.

Step 1: Preprocessing.
For a given Reddit post, the training data set will contain only posts from the same subreddit; these training posts are generally taken from the time immediately preceding the test set. Formally, for a set of $n$ test posts $p_0, p_1, p_2, ... p_n$, where $p_i$ is the $i^\textrm{th}$ post chronologically and $p_0$ is the first test post, the training set is defined as $p_{-m}, p_{-m+1}, ... p_{-1}$, or the set of $m$ posts immediately preceding $u_0$ chronologically.

Recall that the Hawkes model used in the present work involves two different distributions. Following the empirical observations of previous work, the Weibull distribution is used to model the dynamics of top-level comments, , comments that are in reply to the post, and produces parameters $a,b, \textrm{ and } \alpha$. The lognormal distribution is used to model the dynamics of comments that are made in reply to other comments and produces parameters $\mu$, and $\sigma$. Finally, recall the branching factor $n_b$, which controls the number of children for each comment [7].

Together, the six parameters $a, b,\alpha,\mu,\sigma, \textrm{and } n_b$ characterize the structure, size, and temporal dynamics of a complete discussion cascade. For each post in the training set, we fit all six model parameters using the L-BFGS-B optimizer where parameters are constrained to be positive [19].

Step 2: Constructing the Post Graph.
Next, we create a graph of social media posts as follows. Let $G_{\textrm{sr}}=(V,E)$ be an undirected weighted graph with posts $p\in V$ contributed to a particular subreddit representing the graph's vertices having properties user, title and Hawkes parameters fitted from the previous step $p_a$, $p_b$, $p_\alpha$, $p_\mu$, $p_\sigma$, $p_{n_b}$.

Weighted edges between posts $(u, v, w)\in E$ are constructed in the following way. Popular users tend to post popular content[20], so posts submitted by the same user are connected $(u, v, 1)$ $|$ $\forall_{u,v} \textrm{ author}(u) = \textrm{author}(v) \wedge u\ne v$. In addition, we also consider the text of the post title. Each title is tokenized and case-normalized into one or more tokens. Edges are created among posts with overlapping titles and weighted according to their overlap $(u, v, \mathcal{J}(\textrm{title}(u), \textrm{title}(v))$ $|$ $\forall_{u,v} \textrm{ } u\ne v$ where $\mathcal{J} \in [0,1]$ is defined to be the Jaccard coefficient of the tokens in the post's titles. Posts with more similar titles will receive a higher weight and identical titles will receive a weight of 1. Edge weights are additive and will therefore always be between 0 and 2.

Because the number of possible post pairs is very large, $|V|*(|V|-1)$, we limit the scope of the graph by only taking the top-$n$ edges with the largest weight for each node in the graph. Because node2vec only performs $r$ random walks per node, limiting to the top-$n$ edges for $n > r$ does not cause significant information loss. The top-$n$ filter is applied to each node without considering neighbor nodes, ie, each node is guaranteed to have at least the $n$ incident edges with the highest weights included in the graph, but may have more depending on the top-$n$ edges of other nodes. Even in the worst-case, this top-$n$ criteria limits the total edges in the graph to $|V|*n$.

The post graph is constructed for each subreddit and connects existing training posts. A new post $x$ having a submitting user and a title can be connected into the graph creating $G^*_\textrm{sr}$. This version of the graph, containing all training posts and one new post, is then used to infer parameters to predict the discussion cascade for $x$. A new version of $G^*_\textrm{sr}$, based on the same base graph $G_{\textrm{sr}}$, is created for each new post $x$, so that $G^*_\textrm{sr}$ always contains exactly one unknown post $x$.

Step 3: Parameter Inference.
At this point, $G^*_\textrm{sr}$ consists of many nodes representing social media posts and discussion cascades that have been fit to the Hawkes model discussion earlier. As a result, each node is labeled with parameters $p_a$, $p_b$, $p_\alpha$, $p_\mu$, $p_\sigma$, $p_{n_b}$, except the new post $x$ whose parameters cannot be fitted from the empty or very small discussion cascade. By assuming that similar posts will have similar discussion threads, and by wiring $G^*_\textrm{sr}$ according to that assumption, we can use the new node's position in the graph to infer model parameters for the new post $x$.

An ideal choice for network-based parameter inference can be found in graph-based representation learning algorithms like LINE [21], DeepWalk [22], and node2vec [11]. Based on the “you shall be known by the company you keep” principle frequently cited in text-based representation learning systems like word2vec [23], the goal of graph representation learning systems is to learn a vector-representation (called an embedding) of each node based on the embeddings of the node's neighborhood.

Because graphs are easily represented as matrices, there are many classic systems for unsupervised feature learning. Traditional dimensionality reductions like PCA are available, but are computationally intractable on large real-world graphs. Graph representation learning, on the other hand, is iterative, easily distributed and therefore much more scalable.

Graph representation systems utilize a $d$-dimensional vector where the number of dimensions $d$ is defined by the user. Typically, $d$ is 200-500, and vector values are randomly initialized. Despite these random starting points, after optimization, the feature vectors of any two close neighbors tend to converge to similar values as defined by the objective function. However, a single feature vector, when removed from the context of the set, contains no meaningful information; the vectors can only be used for similarity comparisons between objects, and do not describe or capture the characteristics of the object itself.

Recent work reconsiders graph representation as a matrix factorization problem and unifies DeepWalk, LINE, node2vec, etc. into a matrix factorization task[24]. This shared representation reconsiders the differences between the approaches to be differences in the transition probabilities for random walks over the graph. Still, the learned representations are not meaningful outside of their relative distance in a vector-space.

Post graph with parameter embeddings for node2vec parameter inference. Each node's embedding represents the model parameters $a, b, \alpha, \mu, \sigma, n_b$.

Graph representation learning systems appear to be a convenient solution to our parameter inference problem, but a few modifications are necessary. Instead of initializing the node embeddings to $d=$ 200-500 random values, we set the embedding dimension $d = 6$ (the number of parameters in the Hawkes model) and initialize the embeddings to the fitted parameter values. In other words, the embedding of each node $u\in V$ is $u_{[a,b,\alpha,\mu,\sigma,n_b]}$, which is set to the Hawkes parameters fitted based on $u$'s discussion cascade. The graph snippet in Fig. <ref> illustrates the embeddings for each node. Unlike in node2vec, etc. where the embeddings are only meaningful relative to other embeddings, these embeddings actually represent parameters of the Hawkes model.

A new post $x$, which does not yet have an extensive discussion thread, is given an initial embedding. The initial embeddings of node2vec are random and range from -0.5 to 0.5; however, Hawkes parameters have their own range depending on their function. We set the initial embedding of $x$ to $(1, 2, 0.75, 0.15, 1.5, 0.05)$. These specific values occur frequently in the set of fitted parameters and, like the median cascade in our data set, these values tend to generate very small discussion cascades.

Stochastic Gradient Descent (SGD) is used to optimize the parameters and, like in node2vec, the gradients are estimated using backpropagation. The learning rate $r$ starts at $0.0001$ and decreases as the number of iterations increases [22, 11].

At this point, the optimizer typically runs and adjusts each node's embedding according to the loss function. Our case is different. The parameters of each training post were fitted previously by the Hawkes process, so these values should be resistant to significant change. And their resistance to change should be based on the performance of the Hawkes-optimizer. If the log-likelihood of the Hawkes-parameters of some post was very high, then there is little reason to update the post's embedding. On the other hand, if a post's Hawkes-parameters were under-fit (or not fit at all in the case of a new post $x$), then it's embedding may benefit from larger updates. We therefore define a node-specific learning rate $r_u$ as follows:

\begin{equation} \label{eq:rate}
r_u = \left(1-g_u\right) r \left(1-\frac{k}{K+1}\right)
\end{equation}

where $k$ is the current iteration out of $K$ total iterations such that $1-\frac{k}{K+1}$ is a percent of training complete, $r$ is the base learning rate, and $g_u$ is the goodness of fit score from the Hawkes process for node $u$, normalized between [0.45,0.85]. In rare cases where the Hawkes-optimizer failed to converge, $g_u$ is set to 0.95. Let $g_x=0$. The inverse of this normalized goodness of fit score allows the parameters to be adjusted where needed and remain consistent where learning is not needed.

Mean final comment thread size (in number of comments) as a function of observation time for the /r/worldnews/ subreddit. Each line represents a minimum thread size at each point of observation, , the mean final comment thread size for posts with 10 or more observed comments (line indicated by ) in the first half hour is approximately 1,100 comments.

Using the fitted parameter embeddings and the fine-tuned SGD optimizer, the node2vec algorithm is applied to $G_\textrm{sr}^*$, which contains all training posts and one new post. Once node2vec finishes all walks and updates, the final embedding values of the unknown post represent inferred parameters for the Hawkes model. These parameters indicate the predicted comment dynamics of the post, based only on the post title, submitting author, and the subreddit training data. No observed comments are required for this inference step, allowing the CTPM to obtain parameters for new posts.

§.§ Partial Fit to Refine Parameters

In some cases, it may be useful to wait to gather some data before making a prediction. A post with very few comments after a few hours is unlikely to receive many more. Conversely, a post that garnered lots of immediate attention and has a large comment thread is likely to receive more comments and further attention [4, 25]. Fig. <ref> illustrates this dynamic for comment threads in the /r/worldnews/ subreddit. We observe that initial comment velocity is highly predictive of the final comment thread size. For example, if a post in the /r/worldnews/ subreddit receives 5 or more comments in the first half-hour, the final cascade will, on average, consist of 90.53 comments; if the post has fewer than 5 comments in the same period, the final cascade will, on average, only contain 5.07 comments.

When a partial cascade is observed, then we can use this important additional information to improve our prediction of the final discussion cascade.

In these cases, we apply the same Hawkes parameter fit procedure that was used for training data preprocessing, but slightly modify it to take the inferred parameters into account. First, the optimizer is initialized using the parameters inferred from Step 3. Second, we limit the number of iterations for the Hawkes-optimizer to the number of comments observed. This simple heuristic gives more weight to cascades with more observations. Observed activity is a better predictor of future comment tree growth, but only once there is enough information to perform an accurate fit. Overall, as more comments are observed, the refined parameters approach the `true' fitted parameters of the complete ground-truth cascade.

§.§ Cascade Prediction

The Hawkes parameters $a, b, \alpha, \mu, \sigma, n_b$ are fitted with Steps 1-3 above and refined if partial cascades are available. From these parameters we simulate the discussion cascade.

There are three key steps that need to be considered when simulating a discussion cascade. The first is to estimate how many `immigrant' events exist in the cascade. Let $T$ be a predetermined cutoff time $t\in[0,T]$. We simulate immigrant arrival times $\tau<T$ as the cumulative sums of $n$ random variables $\tau_1, \tau_2, \ldots \tau_n$ at a rate of $h(t)$.

Recall that we modelled immigrant events as a Weibull distribution with parameters $a, b, \alpha$. Thus

$$h(t) = \left( a\frac{\alpha}{b}\right)  \left(\frac{t}{b}\right)^{\alpha-1} \exp\left(-\left(t/b\right)^\alpha\right)$$

and $\tau$ is sampled from $h(t)$ with the thinning algorithm.

Next, for each $\tau_i<t$ we simulate `offspring' births at a rate of $n_b\phi(t-\tau_i)$. Again recall that we modelled offspring events as a lognormal distribution with parameters $\mu, \sigma$. Thus,

$$\phi(t-\tau_i) = \frac{1}{\sigma (t-\tau_i) \sqrt{2\pi}} \exp\left( -\frac{\left(\log (t-\tau_i) - \mu\right)^2 }{2\sigma^2}\right)$$

and additional events $\tau$ are sampled from $n_b\sum_{i:t>t_i}\phi\left(t-\tau_i\right)$ with the Thinning algorithm.

Finally, each offspring event may generate additional offspring. So this process iterates until $t>T$ or $n>N$, where $N$ is the maximum number of events allowed. For $n_b<1$ this process will likely die out on its own.

If there exists a partial cascade, then we initialize values for $\tau$ according to the observed data and set $t$ to the time of the most recent comment, or the last time observed. In this case, additional root-level comments may be simulated, and comment replies are generated for both observed and simulated comments.

This produces a simulation of a full discussion thread, including comment timestamps and a tree structure (as illustrated in Fig. <ref>). Note that the simulation does not generate text content or assign comment-authors.

§ METHODOLOGY

In this section, we describe the training and testing procedures used to evaluate the Comment Thread Prediction Model (CTPM) introduced in the present work. To this end, we first introduce a large dataset from Reddit, describe the details of 5 different testing scenarios, and compare our results with 4 other state of the art and baseline models.

Days covered by train and test sets for each subreddit. Testing data begins on December 1, 2017 and moves forward until 1000 posts are retrieved; training data ends on November 30, 2017 and moves backward in time until 10000 posts are retrieved.

test posts         3ctrain posts

subreddit          1000          1000      5000     10000

aww                   1            2         6        10

changemyview          22           21        110      234

explainlikeimfive     3            3         13       28

IAmA                  31           25        131      249

nottheonion           11            10        48       94

science               11            10        51       97

Showerthoughts        1            1         4        9

sports                4            4         18       39

worldnews             2            2         7        13

To evaluate the CTPM, we apply it to real-world posts on Reddit. Nine subreddits of varying size and popularity were selected as the source of data: /r/aww/, /r/changemyview/, /r/explainlikeimfive/, /r/IAmA/, /r/nottheonion/, /r/science/, /r/Showerthoughts/, /r/sports/, and /r/worldnews/. For each subreddit, we test our model on the first 1000 posts of December 2017. The size of the training set varies, but is always taken as the $m$ posts immediately preceding the first test post; in this way, the training data ends at November 2017, and covers as many previous days as are required to reach the desired training set size.

Table <ref> lists the number of days covered by each testing and training set. For example, in the /r/aww/ subreddit, 1000 posts were captured within 1 day starting at December 1, 2017; training sets of 1,000, 5,000, and 10,000 posts were found by scraping the /r/aww/ backwards in time for 2, 6, and 10 days respectively.

As shown in Fig. <ref>, most comment threads receive few comments; in fact, more than 83% of all comment threads in our test data set have fewer than 10 comments. The distribution does vary by subreddit, however: only 55.6% of /r/changemyview/ posts have fewer than 10 comments, while 97.3% of /r/sports/ posts meet this criteria. The frequency of small threads supports the need for a model that can accurately predict all sizes of cascades.

Model Comparison.
To demonstrate the effectiveness of our model, we compare results against four alternative models:

* Hawkes model of discussion trees [7]. Uses the same parameter fit and tree simulation as our model, but requires at least 10 observed comments to estimate parameters.

* Random cascade baseline. Draws an existing cascade from the training dataset at random. Does not take observed comments into account.

* Random simulation baseline. Draws fitted parameters from the training dataset at random and simulates a cascade using these parameters, including observed comments in the simulated thread.

* Average simulation baseline. Take the average of all fitted parameters in the training dataset and use these parameters to simulate a cascade, including observed comments in the simulated thread.

The Hawkes model does not make use of any training data, and instead relies solely on observed comments to predict future thread growth. This means that the model is incapable of making a prediction for new posts without comments. In general, we observed that 10 comments are needed before the model will return any fitted parameters; so, we begin the evaluation of this model when the cascade has at least 10 comments. This means the Hawkes model cannot simulate new posts, or posts that never receive 10 comments.

The remaining random and average baseline models utilize the same training data set as our Comment Thread Prediction Model, but only to draw parameters from this set. Observed cascade behavior does not contribute to the prediction, beyond serving as a starting point for the simulated comments. Because most cascades are small, these random predictors are actually formidable comparisons.

Evaluation Metrics.
We evaluate the various models by (1) selecting a test post $u$, (2) using each model to simulate a full cascade $u^\ast$, and (3) comparing the similarity of the actual cascade of $u$ and the $u^\ast$ generated by each model. Since $u$ and $u^\ast$ are both trees, there exist several methods by which we can evaluate their topological distance. We start with simple metrics including cascade size (in number of nodes), depth, and breadth.

We also compute and compare the structural virality of $u$ and $u^\ast$. Also known as the Weiner index, the structural virality is defined as the average distance between all pairs of nodes in a tree [26]. Then, $\textrm{vir}(u)$ can be defined as follows for trees with $n > 1$ nodes:

Mean relative error (MRE) of cascade size at time observed = 0 hours for the CTPM at three training set sizes - 1000, 5000, and 10000 posts (lower is better). Larger training set sizes indicate training examples further away (temporally) from the test set. Larger training set sizes generally improve performance.

Percentage of total comments observed over the cascade lifetime (left) and over time (right) for posts with at least 10 comments. Most comments occur within the first few hours.

\begin{equation}
\textrm{vir}(u) = \frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n}d_{ij}
\end{equation}

Because the structural virality is only defined for trees with 2 or more nodes, we only compute and compare this metric for threads where both the true and simulated cascades contain at least one comment (since the initial post counts as a node).

For size, depth, breadth, and structural virality comparisons, we plot the mean relative error (MRE) of each metric, which is defined as:

\begin{equation}
\textrm{MRE} = \frac{1}{nr}\sum_{i=0}^{n}\sum_{j=0}^{r}\left|\frac{f(u_{i})-f(u^\ast_{ij})}{f(u_{i})}\right|
\end{equation}

where $n$ is the number of test posts, $r$ is number of repeated simulation runs, $f(x)$ indicates the metric function (size, breadth, depth, or structural virality) applied to the cascade $x$, $u_i$ is a ground-truth cascade, and $u^\ast_{ij}$ is the corresponding simulated cascade for post $u_i$ in test run $j$. Simply put, the MRE measures how closely the predicted cascade matches the actual cascade over $r=5$ runs.

The Cascade Timeline. Discussion threads on Reddit start with the submission of a post, which may (or may not) produce any number of comments. Typically, most comments occur in the first few hours of a post, and nearly all comments occur in the first day. Observation of a cascade can be defined by either (1) the number of comments, or (2) the timespan observed. Fig. <ref> shows that there are subtle differences between these two approaches. The left-hand plot shows the percentage of a completed cascade's comments that are observed during a percentage of that cascade's lifetime; for all subreddits, roughly 75% of all comments occur in the first half of a thread's total lifetime. The right-hand figure also examines the growth of cascades, but instead defines the observation window using time instead of the percentage of a cascade's lifetime; 14 hours is sufficient to observe 75% or more of a cascade's comments. In the present work, we choose to capture our results using time (hours) as the independent axis. This decision allows for a more comprehensive, temporal analysis of the cascades.

The discussion threads generated by all models produce timestamps for each simulated comment event. To evaluate these timestamps, we compare the temporal distribution of predicted thread comments against the ground truth. For this, we use the Komolgrov Smirnov Test (KS-Test). The KS-test finds the widest difference between the cumulative distribution functions of the comparative distributions. To gauge how accurately each model captures the temporal dynamics of the comment threads, we perform a KS-test on the ground-truth and simulated comment times of each thread.

Results of KS-test applied to ground truth and simulated cascade lifetimes as observed time increases. Each subreddit evaluated independently.

Results of KS-test applied to ground truth and simulated cascade lifetimes as observed time increases for posts from /r/worldnews/.

Scatter plot of cascade lifetime versus total number of comments for 1000 test post set for each subreddit. not sure how to make this better... commented out most of the subs for now, since they make compiling take forever

Min and max fitted parameters for 1000-post training sets for each subreddit.

multicolumn names,
col sep=comma,
fixed zerofill,
set thousands separator=,
every head row/.style=after row=    2c$a$    2c$b$     2c$\alpha$     2c$\mu$     2c$\sigma$     2c$n_b$
subreddit     min     max     min     max     min     max     min     max     min     max     min     max
every last row/.style=after row=,
display columns/0/.style=column name=, column type = r, string type,
display columns/1/.style=column name=, column type = r,
display columns/2/.style=column name=, column type = r,
display columns/3/.style=column name=, column type = r,
display columns/4/.style=column name=, column type = r,
display columns/5/.style=column name=, column type = r,
display columns/6/.style=column name=, column type = r,
display columns/7/.style=column name=, column type = r,
display columns/8/.style=column name=, column type = r,
display columns/9/.style=column name=, column type = r,
display columns/10/.style=column name=, column type = r,
display columns/11/.style=column name=, column type = r,
display columns/12/.style=column name=, column type = r,

Mean fitted parameters for 1000-post training sets for each subreddit.

col sep=comma,
fixed zerofill,
set thousands separator=,
every head row/.style=after row=subreddit     $a$      $b$     $\alpha$     $\mu$     $\sigma$     $n_b$
every last row/.style=after row=,
display columns/0/.style=column name=, column type = r, string type,
display columns/1/.style=column name=, column type = r,
display columns/2/.style=column name=, column type = r,
display columns/3/.style=column name=, column type = r,
display columns/4/.style=column name=, column type = r,
display columns/5/.style=column name=, column type = r,
display columns/6/.style=column name=, column type = r,
display columns/7/.style=column name=, column type = r,

Mean relative error (MRE) on a log scale as a function of the time observed. Error bars represent 95% confidence interval. Lower is better. The CTPM described in the present work outperforms existing methods by a significant margin, especially when the observation time is small.

Mean relative error (MRE) of cascade size, depth, breadth, and structural virality on a log scale for the /r/worldnews/ subreddit as a function of the time observed. Error bars represent 95% confidence interval. Lower is better. The CTPM described in the present work outperforms existing methods by a significant margin, especially when the observation time is small.

§ RESULTS AND DISCUSSION

This section illustrates and discusses the results of our experiments comparing our Comment Thread Prediction Model (CTPM) against existing work and baselines.

Size of the Training Set. We begin with an evaluation of the various training set sizes. We created three training datasets for each subreddit with 1,000, 5,000, and 10,000 posts, all ending on November 30, 2017. The test set begins immediately after. In this scenario there are two competing dynamics: (1) training size and (2) recency. More training data is typically associated with better results, as more data usually provides better generalizability. On the other hand, in this temporal scenario, more data means more older data. As we increase the training set size, the additional data items are further and further away from the test set, and may therefore not reflect the current dynamics of the subreddit.

Our first experiment explores this trade-off by comparing the mean relative error (MRE) for the four different cascade metrics in each of the nine subreddits. The results illustrated in Fig. <ref> show that the MRE generally improves as the training set gets bigger, but the effect is small. We therefore use the 10,000 post training set for all remaining tasks.

Effect of Observation Time. As the cascade observation time increases, the amount of information known about the final size and shape of the comment cascade also increases. Recall that most comments occur in the first few hours after submission (Fig. <ref>) and that early comment velocity is very indicative of final comment size (Fig. <ref>). So it is important for a model to perform accurate predictions with as little time elapsed as possible.

The original Hawkes model requires at least 10 comments before any attempt to generate a thread can be made. The CTPM overcomes this via parameter inference on the post graph, allowing for cascade simulation given no observed comments. Here we ask: how does the CTPM compare with Hawkes and other baselines models, especially with little or no observation time?

Results showing the MRE of the comment thread size are illustrated in Fig. <ref> for individual subreddits. Here the Hawkes model was not run on threads with fewer than 10 comments. In larger threads the Hawkes parameter estimation still sometimes failed; these failed runs were also removed from results.

We find that the CTPM does indeed outperform the other models, especially at hour 0 when no comments are present. As expected, as time elapses, and more comment information is available, the models tend to improve. The Hawkes model, however, does not perform well even as the comment thread concludes. This lack of improvement in the Hawkes model is probably because of the abundance of small comment threads, which the Hawkes model has difficulty with.

We also observe a significant improvement in the performance of the CTPM after the first hour. An improvement was expected, but the amount of improvement reinforces our previous finding that the first hour in a comment thread's lifecycle is extremely important to its future size, and therefore has enormous predictive power.

Metric Comparison. The previous results in Fig. <ref> show only the MRE comparing the comment thread size for eight of the nine total subreddits. Using just the /r/worldnews/ subreddit, we also compare the depth, breadth, and structural virality metrics in Fig <ref>.

Mean relative error (MRE) of discussion thread size for various final thread sizes on a log scale for the /r/IAmA/ subreddit as a function of the time observed. Error bars represent 95% confidence interval. Lower is better. The CTPM performs consistently well across various thread sizes. The Hawkes model cannot be computed for small threads ($<$10 comments), so Hawkes results are absent in the left-most panel.

Again we find that CTPM outperforms the other models and baselines, especially when there is little or no observed data. This trend is consistent across all four comparison metrics.

Interestingly, we find that the AvgSim baseline performs rather well in later stages of the comment thread lifecycle, particularly for the structural virality metric. This is because the majority of cascades are very small (, 809  posts have fewer than 5 comments), and the parameters used by the AvgSim baseline tend to generate small cascades. Once the observed portion of the cascade surpasses this typical small size, particularly in the late stages of a comment thread, the AvgSim baseline tends to generate no further comments. The nearly-complete observed tree is then evaluated against the ground truth, yielding small error measurements. CTPM, on the other hand, is not biased towards a particular comment thread size. If a cascade exhibits highly viral behavior early in it's lifetime, the refined parameters will reflect this, causing the model to generate additional comments. These extra comments generated late in the cascade's lifetime allow the less sophisticated AvgSim baseline to overtake CTPM in some performance metrics - particularly structural virality, which is based on the structure of the comment cascade.

Comment Thread Size Dynamics. As we discussed earlier, most comment threads are small. But it is still important to predict both small and large comment threads accurately, and to understand the prediction errors produced by models under various size conditions.

Fig. <ref> shows how model performance varies as the size of the final comment thread changes. In the majority case, , when the final thread has fewer than 5 comments, we observe that CTPM performs significantly better than the other models and baselines, especially when there is little or no time observed in the comment thread's lifecycle. The Hawkes model proposed by Medvedev et al [7], does not appear in the far-left panel because it could not generate predictions with so few observed.

As the final comment thread grows larger, the advantage of CTPM decreases. These results indicate that existing models overestimate the comment thread size on the average case. CTPM does not appear to have this overestimation problem; it performs consistently across threads of different sizes.

Comment Time Dynamics. The previous experiments have compared the final size and/or shape of the actual comment thread compared to the predicted comment thread. However, these experiments do not consider the temporal aspect of the cascades. Each comment occurs at a specific time and after a specific delay. The Hawkes process used in comparative models, and CTPM, does indeed generate comments at specific times.

Here we ask: how well do the temporal dynamics of each model compare to the ground truth? To answer this question, we flatten each comment thread into a single timeline of events: the time of each comment relative to the parent post. We compare this linear timeline with the ground truth timeline using the Kolmogorov-Smirnov Test (KS-Test) and report the test statistic.

The mean KS-Test Statistic of comparing results from the /r/worldnews/ subreddit is illustrated in Fig. <ref>. CTPM outperforms the Hawkes model, and performs competitively against the AvgSim and RandSim baselines. As with the structural virality metric results in Fig. <ref>, the baseline model overtakes the CTPM when the observed time is high. This is still likely the result of occasional over-simulation by CTPM as compared to the baselines, which are biased towards small threads. Additionally, this KS-Test omits posts with fewer than 10 comments to ensure there are enough events for an accurate assessment. Given that the CTPM vastly outperforms the baseline models for small threads, these results are likely biased against CTPM.

Mean results of KS-tests comparing predicted with actual comment thread timestamps as observed time increases for /r/worldnews/ posts with 10 or more comments. Lower is better. The CTPM outperforms the Hawkes model, particularly for large observation windows.

Average relative cascade depth error at time observed = 0 hours for proposed model at three training set sizes - 1000, 5000, and 10000 posts.

Average relative cascade breadth error at time observed = 0 hours for proposed model at three training set sizes - 1000, 5000, and 10000 posts. should probably combine these three into subfigures, assuming we want them all

Average relative cascade structural virality error at time observed = 0 hours for proposed model at three training set sizes - 1000, 5000, and 10000 posts. Only posts where both true and simulated cascades have at least one comment are considered.

Count of posts in each size class by subreddit. Based on final size of true cascades.

col sep=comma,
set thousands separator=,
every head row/.style=after row=    4cnumber of comments
subreddit     $[0, 5)$     $[5, 50)$     $[50, 100)$     $[100, +\inf)$
every last row/.style=before row=, after row=,
display columns/0/.style=column name=, column type = r, string type,
display columns/1/.style=column name=, column type = r,
display columns/2/.style=column name=, column type = r,
display columns/3/.style=column name=, column type = r,
display columns/4/.style=column name=, column type = r,

Average relative size error for different /r/IAmA/ cascade sizes as observed time increases. make this pretty include other models here? would maybe need to break size classes into separate plots then, but might be worth it

§ RELATED WORK

§.§ Hawkes Processes for Popularity Prediction

[7] predicting Reddit cascades (including tree structure) from some number of observed comments (defined by time) - this is what our fit/sim code/process is based on, but we added the infer for 0 observed comments

[14] predict final retweet counts via self-exciting point process based on reshare history (defined by time) so far

[15] twitter prediction based on observation period, takes circadian rhythms into account, relies on observed retweets and social network structure, Hawkes for prediction

[12] general Hawkes info, retweet prediction example

[13] some Hawkes stuff with learning kernels, test on MemeTracker, lots of math here - READ MORE CLOSELY

<cit.> log-Gaussian Cox process to infer post frequencies, based on text, look at similar rumours - COME BACK HERE - USING TEXT

§.§ Other Approaches to Popularity Prediction

[10] link posts to existing knowledge-base entities, use this as context for popularity prediction; encode KB info in vector, predict with LSTM networks - COME BACK HERE, SIMILAR TO GRAPH INFER?

[9] predict popularity for news feed selection, natural language and deep reinforcement learning - COME BACK HERE, USING TEXT?

[16] twitter information diffusion based on tweet properties, but mostly user properties - COME BACK HERE, highly cited, needs a closer read

[25] predict final size and structure of Facebook image-share cascades using linear SVM model: lots of complicated features, relies on network structure (friendship connections); structural and temporal features most important for prediction - COME BACK

[8] predict Digg and YouTube final popularity from observation period, three different models: linear regression, constant scaling, growth profile - COME BACK, good comparison/baselines?

<cit.> less a prediction and more a diffusion dynamics study - some mention of parameter fit - but mostly proving that there are outside influences, not only diffusion - COME BACK HERE, see if relevant, highly cited

<cit.> again, not exactly prediction - looking at how information spreads, and the path it follows to do so - highly cited?

§.§ Node2Vec stuff

[11] original node2vec paper, must cite - COME BACK, look at other applications/modifications

<cit.> efficiency modifications to existing node2vec implementations - compute transition probs during random walks to reduce memory - as we do

§.§ Hawkes in general - not exactly relevant?

<cit.> special Hawkes for inhibitory relationships, not mutually-exciting

<cit.> general, fancy Hawkes stuff, very theoretical/mathy

<cit.> again, more general and mathy - multiple triggering patterns

<cit.> software for Hawkes in R

<cit.> meh, probably don't need this - financial application
<cit.> more trading/finance stuff

<cit.> EM Hawkes stuff, and complexity improvements

<cit.> much math

<cit.> approximating hawkes processes for a particular application to server queues

§.§ other maybe-not-related stuff

mixed weibull

our model doesn't use a mixed weibull distribution, but I considered it at one time - and logged a bunch of related papers

<cit.> mixing weibull distributions for better fit of failure times data

<cit.> theoretical, fitting mixed weibull distributions

<cit.> mixing parameter for multiple causes of failure

all the rest

<cit.> network reconstruction of data based on Hawkes processes - no idea how this would tie in at all

§ CONCLUSIONS

Online forums represent a large portion of discussion and communication on the Web. These comment threads allow users to express ideas and opinions that can color the interpretation of the content, making the mechanisms behind the growth of these discussions an important research topic. Existing popularity prediction models, particularly those designed to generate full discussion threads, rely on observations of a post's early comments to predict the remaining activity. This information requirement means these models are incapable of predicting threads for new posts, before comments are present.

In the present work, we introduce our Comment Thread Prediction Model (CTPM), which accurately predicts the size, shape, and temporal dynamics of discussion threads based only on the text of the initial post. This allows for the prediction and simulation of new posts without existing comments. If comments are present, this additional information can be used to improve the model's predictive power. Based on experiments performed on thousands of Reddit discussions, we find that CTPM outperforms existing models, particularly for new posts, or posts with few comments.

Future Work.
Though the CTPM introduced here consistently outperforms existing models for the prediction of discussion threads, particularly when there are no available comments, there are still avenues for potential improvement. First, CTPM currently uses a simple Jaccard coefficient to quantify the similarity between post titles; a more sophisticated method for determining edge weight in the post graph may potentially improve performance. Another potential area of improvement is in the parameter refinement procedure based on observed comments. The current method takes all observed comments into account, but if the dynamics of the cascade change during its lifetime, the earliest comments may not be a good predictor of the remaining growth. An alternative refinement procedure could give more weight to recent comments, and potentially better recognize the impending death of a cascade. The model could also be tuned specifically to a particular subreddit or domain, perhaps to improve simulation stopping conditions.

The CTPM could also be applied to other social network domains. Can the same mechanisms accurately predict comment threads on Facebook, or retweet cascades on Twitter, without underlying social network knowledge? The potential applications for a generalized popularity prediction model are certainly more widespread than demonstrated in this paper.

Finally, the network embedding techniques employed in the CTPM parameter inference procedure could be applied to other models and problems. The potential benefits of a network-based parameter fit, or embedding values with meaning, should be explored.

Acknowledgements. This research is supported by a grant from the US Defense Advanced Research Projects Agency (DARPA #W911NF-17-C-0094).

[1]
S. Gao, J. Ma, and Z. Chen, “Modeling and predicting retweeting dynamics on
microblogging platforms,” in ICDM.1em plus 0.5em minus
0.4emACM, 2015, pp. 107–116.

[2]
M. J. Salganik, P. S. Dodds, and D. J. Watts, “Experimental study of
inequality and unpredictability in an artificial cultural market,”
Science, vol. 311, no. 5762, pp. 854–856, 2006.

[3]
M. Glenski, G. Stoddard, P. Resnick, and T. Weninger, “Guessthekarma: A game
to assess social rating systems,” Proceedings of the ACM on
Human-Computer Interaction, vol. 2, no. CSCW, p. 59, 2018.

[4]
M. Glenski and T. Weninger, “Rating effects on social news posts and
comments,” ACM Trans. on Intelligent Systems and Technology, vol. 8,
no. 6, p. 78, 2017.

[5]
S. Goel, D. J. Watts, and D. G. Goldstein, “The structure of online diffusion
networks,” in EC.1em plus 0.5em minus 0.4emACM, 2012,
pp. 623–638.

[6]
D. Choi, J. Han, T. Chung, Y.-Y. Ahn, B.-G. Chun, and T. T. Kwon,
“Characterizing conversation patterns in reddit: From the perspectives of
content properties and user participation behaviors,” in COSN.1em plus 0.5em minus 0.4emACM, 2015, pp. 233–243.

[7]
A. N. Medvedev, J.-C. Delvenne, and R. Lambiotte, “Modelling structure and
predicting dynamics of discussion threads in online boards,” Journal
of Complex Networks, vol. 7, no. 1, pp. 67–82, 2018.

[8]
G. Szabo and B. A. Huberman, “Predicting the popularity of online content,”
Available at SSRN 1295610, 2008.

[9]
J. He, M. Ostendorf, X. He, J. Chen, J. Gao, L. Li, and L. Deng, “Deep
reinforcement learning with a combinatorial action space for predicting
popular reddit threads,” arXiv preprint arXiv:1606.03667, 2016.

[10]
H. Dou, W. X. Zhao, Y. Zhao, D. Dong, J.-R. Wen, and E. Y. Chang, “Predicting
the popularity of online content with knowledge-enhanced neural networks,”
in SIGKDD, 2018.

[11]
A. Grover and J. Leskovec, “node2vec: Scalable feature learning for
networks,” in SIGKDD.1em plus 0.5em minus 0.4emACM,
2016, pp. 855–864.

[12]
M.-A. Rizoiu, Y. Lee, S. Mishra, and L. Xie, “A tutorial on hawkes processes
for events in social media,” arXiv preprint arXiv:1708.06401, 2017.

[13]
K. Zhou, H. Zha, and L. Song, “Learning triggering kernels for
multi-dimensional hawkes processes,” in ICML, 2013, pp. 1301–1309.

[14]
Q. Zhao, M. A. Erdogdu, H. Y. He, A. Rajaraman, and J. Leskovec, “Seismic: A
self-exciting point process model for predicting tweet popularity,” in
SIGKDD.1em plus 0.5em minus 0.4emACM, 2015, pp.

[15]
R. Kobayashi and R. Lambiotte, “Tideh: Time-dependent hawkes process for
predicting retweet dynamics,” in ICWSM, 2016.

[16]
J. Yang and S. Counts, “Predicting the speed, scale, and range of information
diffusion in twitter,” in ICWSM, 2010.

[17]
D. J. Daley and D. Vere-Jones, An introduction to the theory of point
processes: volume II: general theory and structure.1em plus 0.5em
minus 0.4emSpringer Science & Business Media, 2007.

[18]
H. Lakkaraju, J. McAuley, and J. Leskovec, “What's in a name? understanding
the interplay between titles, content, and communities in social media,” in
ICWSM, 2013.

[19]
C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal, “Algorithm 778: L-bfgs-b: Fortran
subroutines for large-scale bound-constrained optimization,” ACM
Trans. on Mathematical Software, vol. 23, no. 4, pp. 550–560, 1997.

[20]
S. Khamis, L. Ang, and R. Welling, “Self-branding,‘micro-celebrity’and the
rise of social media influencers,” Celebrity Studies, vol. 8, no. 2,
pp. 191–208, 2017.

[21]
J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale
information network embedding,” in WWW.1em plus 0.5em minus
0.4emInternational World Wide Web Conferences Steering Committee,
2015, pp. 1067–1077.

[22]
B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social
representations,” in SIGKDD.1em plus 0.5em minus 0.4emACM, 2014, pp. 701–710.

[23]
T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed
representations of words and phrases and their compositionality,” in
NeurIPS, 2013, pp. 3111–3119.

[24]
J. Qiu, Y. Dong, H. Ma, J. Li, K. Wang, and J. Tang, “Network embedding as
matrix factorization: Unifying deepwalk, line, pte, and node2vec,” in
WSDM.1em plus 0.5em minus 0.4emACM, 2018, pp. 459–467.

[25]
J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, and J. Leskovec, “Can
cascades be predicted?” in WWW.1em plus 0.5em minus
0.4emACM, 2014, pp. 925–936.

[26]
S. Goel, A. Anderson, J. Hofman, and D. J. Watts, “The structural virality of
online diffusion,” Management Science, vol. 62, no. 1, pp. 180–196,