A RECURRENT NEURAL CASCADE-BASED MODEL
Year: 2018

Abstract:
Many works have been proposed in the literature to capture the dynamics of diffusion in networks. While some of them define graphical markovian models to extract temporal relationships between node infections in networks, others consider diffusion episodes as sequences of infections via recurrent neural models. In this paper we propose a model at the crossroads of these two extremes, which embeds the history of diffusion in infected nodes as hidden continuous states. Depending on the trajectory followed by the content before reaching a given node, the distribution of influence probabilities may vary. However, content trajectories are usually hidden in the data, which induces challenging learning problems. We propose a topological recurrent neural model which exhibits good experimental performances for diffusion modelling and prediction.

heading: 1 INTRODUCTION
text: The recent development of online social networks enabled researchers to suggest methods to explain and predict observations of diffusion across networks. Classical cascade models, which are at the heart of the research literature on information diffusion, regard the phenomenon of diffusion as an iterative process in which information transits from users to others in the network (Saito et al., 2008; Gomez-Rodriguez et al., 2011), by a so-called word-of-mouth phenomenon. In this setting, diffusion modeling corresponds to learning probability distributions of content transmission. Various cascade models have been proposed in the literature, each inducing its own learning process to explain some observed diffusion episodes and attempting to extract the main dynamics of the network. However, most of these models rely on a strong markovian assumption for which the probabilities of next infections1 only depend on who is already infected at the current step, not on the past trajectories of the diffused content. We claim that the history of spread contains much valuable information that should be taken into account by the models. Past trajectories of the diffusion can give insights about the different natures of the contents. Also, the content may be changed during the diffusion, with different transformations depending on which nodes re-transmit the information.
On the other hand some recent approaches rely on representation learning and recurrent neural networks (RNN) to predict the future spread of diffusion given the past. A naive possibility would be to consider diffusion episodes as sequences of infections and propose temporal point process approaches to model the dynamics. Using the Recurrent Marked Temporal Point Process model (Du et al., 2016), the current hidden state of the RNN would embed the history of the whole diffusion sequence, which would be used to output the next infected node and its time of infection. However, since diffusion episodes are not sequences but trees, naive recurrent methods usually fail in capturing the true dynamics of the networks. Embedding the whole past in the state of a given node rather than restraining it to its specific ancestor branch leads to consider many independent and noisy events for future predictions. A model that would consider the true diffusion paths would be more effective, by focusing on the useful past. If the true diffusion paths were known, it would be possible to adapt works on recurrent neural models for tree structures such as successfully proposed in (Tai et al., 2015) for NLP tasks. Unfortunately, in most of applications the topology of diffusion is unknown while learning. In the task considered in this paper, the only observations available are the timestamps of the infected nodes.
1Throughout this paper, we refer to infection for denoting the participation of a node of the network in the diffusion.
To cope with it, (Wang et al., 2017a) proposed Topo-LSTM, a Long-Short Time Memory network that considers a known graph of relationships between nodes to compute hidden states and cells of infected nodes. The hidden state and cell of a given node at t depend on those from each of its predecessors that have been infected before t. Since nodes may have multiple predecessors that are infected at time t, the classical LSTM cannot be applied directly. Instead, (Wang et al., 2017a) proposed a cell function that aggregates infector candidate states via mean pooling. This allows to take the topology of the possible diffusion into account, but not the past trajectory of the content (it averages all possible paths). To overcome this, (Wang et al., 2017b) proposed a cascade attentionbased RNN, which defines a neural attention mechanism to assign weights to infector candidates before summing their contribution in the new hidden state at t. The attention network is supposed to learn to identify from whom comes the next infection based on past states. However, such an approach is likely to converge to most of attention weight vectors in the center of the simplex, since diffusion is a stochastic process with mostly very weak influence probabilities. The deterministic inference process of the approach limits its ability to produce relevant states by mixing from multiple candidates rather than sampling the past trajectories from their posterior probabilities. Note the similar approach in (Wang et al., 2018), which does not use a RNN but defines a composition module of the past via attention networks to embed the episode in a representation space from which the probability of the next infected node can be deduced. Beyond the limits discussed above w.r.t. deterministic mixing of diffusion trajectories, no delay of infection is considered in this work, which makes it impossible to use for diffusion modeling purposes.
Recently, many works in representation learning used random walks on graphs to sample trajectories that can be used to learn a network embedding which respects some topological constraints. While DeepWalk (Perozzi et al., 2014) only uses structural information, models proposed in (Nguyen et al., 2018) or (Shi et al., 2018) include temporal constraints in random walks to sample feasible trajectories w.r.t. observed diffusion episodes. The approach DeepCas from (Li et al., 2016) applies this idea for the prediction of diffusion cascades. However, such approaches require a graph of diffusion relations as input, which is not always available (and not always representative of the true diffusion channels of the considered network as reported in (Ver Steeg & Galstyan, 2013)). In our work, we consider that no graph is available beforehand. Moreover, no inference process is introduced in DeepCas to sample trajectories from their posterior probabilities given the observed diffusion sequences. The sampling of trajectories is performed in an initialization step, before learning the parameters of the diffusion model.
In this paper, we propose the first bayesian topological recurrent neural network for sequences with tree dependencies, which we apply for diffusion cascades modelling. Rather than building on a preliminary random walk process, the idea is to consider trajectory inference during learning, in order to converge to better representations of the infected nodes. Following the stochastic nature of diffusion, the model infers trajectories distributions from observations of infections, which are in turn used for the inference of infection probabilities in an iterative learning process. Our probabilistic model, based on the famous continuous-time independent cascade model (CTIC) (Saito et al., 2009) is able to extract full paths of diffusion from sequential observations of infections via black-box inference, which has multiple applications in the field. Our experiments validate the potential of the approach for modeling and prediction purposes.
The remaining of the paper is structured as follows. Section 2 presents some background and notations of the approach. Section 3 presents the proposed model. Section 4 reports experimental results of the approach compared to various baselines.

heading: 2 BACKGROUND

heading: 2.1 INFORMATION DIFFUSION
text: Information diffusion is observed as a set of diffusion episodes D. Classically, episodes considered in this paper only contain the first infection event of each node (the earlier time a content reached the node). Let U = {u0, u1, ...., uN−1} be a set of N nodes, u0 standing for the world node, used to model influences from external factors or spontaneous infections (as done in (Gruhl et al., 2004) for instance). A diffusion episodeD = (UD, TD) reports the diffusion of a given content in the network as a sequence of infected nodes UD = ( UD0 , ..., U D |D|−1 ) and a set TD = {tDu ∈ N+∞|u ∈ U} of
infection time-stamps for all u ∈ U . UD is ordered chronologically w.r.t. the infection time-stamps TD. Thus, UDi ∈ U corresponds to the i-th infected node in D for all i ∈ {0, ..., |D| − 1}, with |D| the number of infected nodes in the diffusion. Every episode in D starts by the world node u0 (i.e., UD0 = u0 for all episodes D). We note t D u the infection time-stamp in D for any node in U ,∞ for nodes not infected in D. Time-stamps are relative w.r.t. to tD1 , arbitrarily set to t D 1 = 1 in the data. Note that we also set tD0 = 0 for every episode D. In the following, Di = (U D i , t
D UDi ) denotes the i− th infected node in U with its associated time-stamp. Cascades are richer structures than diffusion episodes, since they describe how a given diffusion happened. The cascade structure stores the first transmission event (u→ v) that succeeded from any node u to each infected node v. Thus, a cascadeCD = (UD, TD, ID) corresponds to a transmission tree rooted in u0 and reaching nodes in UD during the diffusion, according to a sequence ID of infector indices in UD: for any j ∈ {1, ..., |D|−1} and any i ∈ {0, ..., |D|−2}, IDj equals i iff UDj was infected by UDi in the diffusion D (i.e., U D i is the infector of U D j ). We arbitrarily set I D 0 = 0 (no infector for the world node). Note that ID1 is always equal to 0, since there is no other candidate for being the infector of UD1 than the world u0. For convenience, we note I
D(i) ∈ UD the infector of UDi for i ∈ {0, ..., |D| − 1}. Note that the cascade structures respect that tDID(j) < t
D UDj for every
D and all j ∈ {1, ..., |D| − 1} (the infector of a node v is mandatory a node that was infected before v). Several different cascade structures are possible for a given diffusion episode. Cascade models usually perform assumptions on these latent diffusion structures to learn the diffusion parameters.

heading: 2.2 CASCADE MODELS
text: The Independent Cascade model (IC) (Goldenberg et al., 2001) considers the spread of diffusion as cascades of infections over the network. We focus in this paper on cascade models such as IC, which tend to reproduce realistic temporal diffusion dynamics on social networks (Guille et al., 2013). The classical version of IC is an iterative process in which, at each iteration, every newly infected node u gets a unique chance to infect any other node v of the network with some probability θu,v . The process iterates while new infections occur. Since the expectation-maximization algorithm proposed in (Saito et al., 2008) to learn its parameters, IC has been at the heart of diffusion works.
However, in real life, diffusion occurs in continuous time, not discrete as assumed in IC. (Lamprier et al., 2016) proposed DAIC, a delay-agnostic version of IC, where diffusion between nodes is assumed to follow uniform delay distributions rather than occurring in successive discrete timesteps. A representation learning version of DAIC has been proposed in (Bourigault et al., 2016), where nodes are projected in a continuous space in a way that the distance between node representations render the probability that diffusion occurs between them. This allowed the authors to obtain a more compact and robust model than the former version of DAIC. Beyond uniform time delay distributions, two main works deal with continuous-time diffusion. NetRate (Gomez-Rodriguez et al., 2011) learns parametric time-dependent distributions to best fit with observed infection timestamps. As NetRate, CTIC (Saito et al., 2009) uses exponential distributions to model delays of diffusion between nodes, but rather than a single parameter for each possible relationship, delays and influence factors are considered as separated parameters, which leads to more freedom w.r.t. to observed diffusion tendencies. Delays and influence parameters are learned conjointly by an EMlike algorithm. Note the continuous-time cascade model extension in (Zhang et al., 2018), which embeds users in a representation space so that their relative positions both respect some structural community properties and can be used to explain infection time-stamps of users.
In our model we consider that diffusion probabilities from any infected node v depend on a latent state associated to v, which embeds the past trajectory of the diffused content. This state depends on the state of the node u who first transmitted the content to v. Therefore, we need to rely on a continuous-time model such as CTIC (Saito et al., 2009), which serves as a basis for our work. In CTIC, two parameters are defined for each pair (u, v) of nodes in the network: ku,v ∈]0; 1[, which corresponds to the probability that node u succeeds in infecting v, and ru,v > 0, which corresponds to a time-delay parameter used in an exponential distribution when u infects v. If u succeeds in infecting v in an episode D, v is infected at time tDv = t D u + δ, where δ ∼ ru,v exp (−ru,vδ). These parameters are learned via maximizing the following likelihood on a set of episodes D: p(D) =
∏ D∈D p(D) = ∏ D∈D ∏ v∈UD hDv ∏ v 6∈UD gDv (1)
where hDv stands for the probability that v is infected at t D v by previous infected nodes in D and g D v is the probability that v is not infected by any infected node in D.
We build on this in the following, but rather than considering a pair of parameters ku,v and ru,v for each pair of nodes (u, v) (which implies 2 × |U| × (|U| − 1) parameters to store), we propose to consider neural functions which output the corresponding parameters according to the hidden state of the emitter u, depending on its ancestor branch in the cascade, and a continuous embedding of the receiver v.

heading: 3 RECURRENT NEURAL DIFFUSION MODEL
text: This section first presents our recurrent generative model of cascades. Then, it details the proposed learning algorithm.

heading: 3.1 RECURRENT DIFFUSION MODEL
text: As discussed above, we consider that each infected node v in an episode D owns a state zDv ∈ Rd depending on the path the content followed to reach v in D, with d the dimension of the representation space. Knowing the state zDu of the node u that first infected v, the state z D v is computed as: zDv = fφ(z D u , ω (f) v ) (2) with fφ : Rd × Rd → Rd a function, with parameters φ, that transforms the state of u according to a shared representation ω(f)v ∈ Rd of the node v. This function can either be an Elman RNN cell, a multi-layer perceptron (MLP) or a Gated Recurrent Unit (GRU). An LSTM could also be used here, but zDv should include both the cell and the state of v in that case.
Given a state z for an infected node u in D, the probability that u succeeds in transmitting the diffused content to v is given by:
ku,v(z) = σ ( < z, ω(k)v > ) (3)
where σ(.) stands for the sigmoid function and ω(k)v an embedding of size d for any node v ∈ U . Similarly to the CTIC model, if a node u succeeds in infecting another node v, the delay of infection depends on an exponential distribution with parameter ru,v . To simplify learning, we assume that the delay of infection does not depend on the history of diffusion, only the probability of infection does. Thus, for a given pair (u, v), the delay parameter is the same for every episode D:
ru,v = exp(−| < ω(r,1)u , ω(r,2)v > |) (4) with |x| the absolute value of a real scalar x and ω(r,1)u and ω(r,2)v correspond to two embeddings of size d for any node u ∈ U , ω(r,1) for the source of the transition and ω(r,2) for its destination in order to enable asymmetric behavior.
We set Θ = ( φ, z0, (ω (f) u )u∈U , (ω (r,1) u )u∈U , (ω (r,2) u )u∈U , (ω (k) u )u∈U ) as the parameters of our
model. The generative process, similar to the one of CTIC, is given in appendix in algorithm 1. In this process, the state of the initial node, the world node u0, is a parameter vector z0 to be learned. The process iterates while there remains some nodes in a set of infectious nodes (initialized with u0). At each iteration, the process selects the infectious node u with minimal time-stamp of infection, removes it from the set of infectious nodes, records it as infected and attempts to infect each non infected node v according to the probability ku,v(zDu ). If it succeeds, a time t is sampled for v with an exponential law with parameter ru,v . If the new time t for v is lower than its current time tDv (initialized with t D v = ∞), this new time is stored in tDv , v is added to the set of infectious nodes and its new state zDv is computed according to its new infector u.

heading: 3.2 LEARNING THE MODEL
text: As in CTIC, we need to define the probability that the node u ∈ UD infects the node v ∈ UD at time tDv with our model. Given a state z for u in D, we have:
aDu,v(z) = ku,v(z)ru,v exp −ru,v(tDv −t D u ) (5)
Also, the probability that u does not infect v before tDv given a state z for u in D is:
bDu,v(z) = 1− ku,v(z) ∫ tDv tDu ru,v exp −ru,v(t−tDu ) dt = ku,v(z) exp −ru,v(tDv −t D u ) +1− ku,v(z) (6)
The probability density that node v is infected at time tDv given a set of states z for all nodes infected before v is:
hDv (z) = ∑
u∈U,tDu <tDv aDu,v(zu) ∏ x∈U\{u},tDx <tDv bDx,v(zx) (7)
= ∏
x∈U,tDx <tDv bDx,v(zx) ∑ u∈U,tDu <tDv aDu,v(zu)/b D u,v(zu) (8)
where zu is the state of node u in z. Similarly, the probability density that node v is not infected in D at the end of observation time T given a set of states z for all nodes infected in D is:
gDv (z) = ∏ u∈UD (ku,v(zu) exp −ru,v(T−tDu ) +1− ku,v(zu)) ≈ ∏ u∈UD (1− ku,v(zu)) (9)
where the approximation is done assuming a sufficiently long observation period.
The learning process of our model is based on a likelihood maximization, similarly to maximizing eq.1 in the classical CTIC model. However, in our case the infection probabilities depend on hidden states z associated to the infected nodes. Since observations only contain infection time-stamps, this requires to marginalize over every possible sequence of ancestors I for every D ∈ D:
log p(D) = ∑ D∈D log p(D) = ∑ D∈D log ∑ I∈ID p(D, I) (10)
where ID is the set {v ∈ N|D|−1|v0 = 0 ∧ ∀i > 0, vi < i} of all possible ancestors sequences for D. p(D, I) corresponds to the joint probability of the episode D and an ancestor sequence I ∈ ID. Taking p(D, I) = p(I)p(D|I) would lead to an intractable computation of p(D|I) using our recurrent cascade model, since it would imply to estimate the probability of any infection in D according to the full ancestors sequence. Fortunately, using the bayesian chain rule, the joint probability can be written as:
p(D, I) = |D|−1∏ i=1 p(Di|D<i, I<i) p(Ii|D≤i, I<i) ∏ v 6∈UD p(v 6∈ UD|D≤|D|−1, I) (11)
where D<i = (Dj)j∈{0,...,i−1} corresponds to the sequence of the i first components of D (the i first components in UD with their associated time-stamps) and I<i = (Ij)j∈{0,...,i−1} stands for the vector containing the i first components of I . We have for every i ∈ {1, ..., |D| − 1}: p(Di|D<i, I<i) = hDUDi (z D <i), where z D <i is a set containing the states of the i first infected nodes in D, which can be deduced from D<i and I<i using the equation 2. We also have: p(v 6∈ UD|D≤|D|−1, I) = gDv (zD≤i). The probability p(Ii|D≤i, I<i) is the conditional probability that I(UDi ) was the node who first infected U D i , given all the previous infection events and the fact that UDi was infected at t D UDi
by one of the previously infected nodes in D. It can be obtained, according to formula 8, via:
p(Ii|D≤i, I<i) = aD I(UDi ),U D i
( zD I(UDi ) ) /bD I(UDi ),U D i ( zD I(UDi ) ) ∑
u∈U,tDu <tDUD i
aD u,UDi (zDu ) /b D u,UDi
(zDu ) (12)
with I(UDi ) ∈ UD the infector of UDi stored in I . Unfortunately the log-likelihood from formula 10 is still particularly difficult to optimize directly since it requires to consider every possible vector I ∈ ID for each training episode D at each optimization iteration. Moreover, the probability products in formula 11 would lead to zero gradients because of decimal representation limits. Therefore, we need to define an approach where the optimization can be done via trajectory sampling. Different choices would be possible. First, MCMC
approaches such as the Gibbs Sampling EM could be used, but they require to sample from the posteriors of the full trajectories of the cascades, which is very unstable and complex to perform. The full computation of the posterior distributions could be avoided by using simpler propositional distributions (such as done for instance via importance sampling with auxiliary variables in (Farajtabar et al., 2015) for diffusion source detection), but this would face a very high variance in our case. Another possibility is to adopt a variational approach (Kingma & Welling, 2013), where an auxiliary distribution q is learned for the inference of the latent variables. As done in (Krishnan et al., 2016) for the inference in sequences, a smoothing strategy could be developed by relying on a bi-directional RNN that would consider past and future infections for the inference of the ancestors of nodes via q(Ii|D, I<i) for every infected node i in an episode D. However, learning the parameters of such a distribution is particularly difficult (episodes of different lengths, cascades considered as sequences, etc.). Also, another possibility for smoothing would be to define an independent distribution qDi for every episode D ∈ D and every infection i ∈ {1, ..., |D| − 1}. However, this induces a huge number of variational parameters, increasing with the size of the training set (linearly in the number of training episodes and quadratically in the size of the episodes). Thus, we propose to rather rely on the conditional distribution of ancestors given the past for sampling (i.e, qDi (Ii) = p(Ii|D≤i, I<i)), which corresponds to a filtering inference process. From the Jensen inequality on concave functions, we get for a given episode D:
log p(D) = log ∑ I∈ID p(D, I)
≥ EI∼qD [ log p(D, I)− log qD(I) ] = EI∼qD |D|−1∑ i=1 log p(Di|D<i, I<i) + ∑ v 6∈UD log p(v 6∈ UD|D≤|D|−1, I)
 ∆ = L(D; Θ) (13)
where qD = |D|−1∏ i=1 p(Ii|D≤i, I<i). This leads to a lower-bound of the log-likelihood, which corresponds to an expectation from which it is easy to sample: at each new infection of a node i in a episode D, we can sample from a distribution depending on the past only. Maximizing this lower-bound (also called the ELBO) encourages the process to choose trajectories that explain the best the observed episode. To maximize it via stochastic optimization, we refer to the score function estimator (Ranganath et al., 2014), which leverages the derivative of the log-function (∇θ log p(x; θ) = ∇θp(x;θ)p(x;θ) ) to express the gradient as an expectation from which we can sample. Another possibility would have been to rely on the Gumbel-Softmax and the Concrete distribution with reparametrization such as done in (Maddison et al., 2016), but we observed greatly better results using the log-trick. The gradient of the ELBO function for all the episodes is given by:
∇ΘL(D; Θ) = ∑ D∈D EI∼qD [( log pI(D)− b ) ∇Θ log qD(I) +∇Θ log pI(D) ] (14)
where pI(D) is a shortcut for ∏|D|−1 i=1 p(Di|D<i, I<i) ∏ v 6∈UD p(v 6∈ UD|D≤|D|−1, I) and b is a moving-average baseline of the ELBO per training episode, used to reduce the variance (taken over the 100 previous training epochs in our experiments). This stochastic gradient formulation enables to obtain unbiased steepest ascent directions despite the need to sample the ancestor vectors for the computation of the node states (with the replacement of expectations by averages over K samples for each episode). It contains two terms: while the first one encourages high conditional probabilities for ancestors that maximize the likelihood of the full episodes, the second one leads to improve the likelihood of the observed infections regarding the past of the sampled diffusion path.
The optimization is done using the ADAM optimizer (Kingma & Ba, 2014) over mini-batches of M episodes ordered by length to avoid padding (M = 512 and K = 1 in our experiments). Our full efficient algorithm is given in appendix 2.
2The code is publicly available at XXX Anonymous.

heading: 4 EXPERIMENTS

heading: 4.1 SETUP
text: We perform experiments on two artificial and three real-world datasets:
• Arti1: Episodes generated on a scale-free random graph of 100 nodes. The generation process follows the CTIC model. But rather than only one transmission probability k parameter per edge, we set 5 different ki depending on the diffusion nature. Before each simulation a number i ∈ {1, ..., 5} is sampled, which determines the parameters to use. 10000 episodes for training, 5000 for validation, 5000 for testing. Mean length of the episodes=7.55 (stdev=5.51);
• Arti2: Episodes sampled on the same graph as Arti1, also with CTIC but where each ku,v is a function of the transmitted content and the features of the receiver v. A content z ∈ R5 is sampled from a Dirichlet with parameter α = 0.1 before each simulation and the sigmoid of the dot product between this content and the edge features determines the transmission probabilities. Features of the hub nodes (nodes with a degree greater than 30) are sampled from a Dirichet with α = 10 (multi-content nodes), while those of other nodes are sampled from a Dirichet with α = 0.1 (content-specific nodes). 10000 episodes for training, 5000 for validation, 5000 for testing. Mean length of the episodes=6.89 (stdev=7.7).
• Digg: Data collected from the Digg stream API during one month. Infections are the ”diggs” posted by users on links published on the media. We kept the 100 most active users from the collected data. 20000 episodes for training, 5000 for validation, 5000 for testing. Mean length of the episodes=4.26 (stdev=9,26).
• Weibo: Retweet cascades extracted from the Weibo microbloging website using the procedure described in (Leskovec et al., 2009). The dataset was collected by (Fu et al., 2013). 4000 nodes, 45000 episodes for training, 5000 for validation, 5000 for testing. Mean length of episodes=4.58 (stdev=2.15).
• Memetracker: The memetracker dataset described in (Leskovec et al., 2009) contains millions of blog posts and news articles. Each website or blog stands as a user, and we use the phrase clusters extracted by Leskovec et al. (2009) to trace the flow of information. 500 nodes, 250000 for training, 5000 for validation, 5000 for testing. Mean length of episodes=8.68 (stdev=11.45).
We compare our model recCTIC to the following temporal diffusion baselines:
• CTIC: the Continuous-Time Independent Cascade model in its original version (Saito et al., 2009);
• RNN: the Recurrent Temporal Point Process model from (Du et al., 2016) where episodes are considered as sequences that can be treated with a classical RNN outputting at each step the probability distributions of the next infected node and its time-stamp;
• CYAN: Similar to RMTPP but with an attention mechanism to select previous states (Wang et al., 2017b);
• CYAN-cov: The same as Cyan but with a more sophisticated attention mechanism using an history of attention states, to give more weights to important nodes;
• DAN: the attention model described in (Wang et al., 2018). It is very similar to CYAN but uses a pooling mechanism rather than a recurrent network to consider the past in the predictions. In the version of (Wang et al., 2018), the model only predicts the next infected node at each step, not its time of infection. To enable a comparison with the other models, we extended it by adding a time prediction mechanism similar to the temporal head of CYAN.
• EmbCTIC: a version of our model where the node state z is replaced in the diffusion probability computation (eq. 3) by a static embedding for the source (similarly to the formulation of the delay parameter in eq. 4). This corresponds to an embedded version of CTIC, similarly to the embedded version of DAIC from (Bourigault et al., 2016).
Note that to adapt baselines based on RNN for diffusion modeling and render them comparable to cascade-based ones, we add a ”end node” at the end of each episode before training and testing them. In such a way, these models are able to model the end of the episodes by predicting this end node as the next event (no time-delay prediction for this node however).
Our model and the baselines were tuned by a grid search process on a validation set for each dataset (although the best hyper-parameters obtained for Arti1 remained near optimal for the other ones). For every model with an embedding space (i.e., all except CTIC), we set its dimension to d = 50 (larger dimensions induce a more difficult convergence of the learning without significant gain in accuracy). The reported results for our model use a GRU module as the recurrent state transformation function fφ.
We evaluate our models on three distinct tasks:
• Diffusion modelling: the performances of the methods are reported in term of negative loglikelihood of the test episodes (i.e., NLL = −(1/|Dtest|) ∑ D∈Dtest log p(D)). Lower
values denote models that are less surprised by test episodes than others, rendering their generalization ability. The NLL measure depends on the model, but for each it renders the probability of an episode to be observed according to the model, both on which nodes are eventually infected and at what time. For our model which has to sample trajectories, the NLL is approximated via importance sampling by considering p(D) ≈ 1S ∑S s=1 p(D,I(s)) qD(I(s)) computed on S infector vectors sampled from qD. We used S = 100 in our experiments;
• Diffusion generation: the models are compared on their ability to simulate realistic cascades. The aim is to predict the marginal probabilities of nodes to be eventually infected. The results are reported in term of Cross-Entropy (CE) taken over the whole set of nodes for each episode: CE = 1|Dtest|×|U| ∑ D∈Dtest ∑ u∈U log p(u ∈ UD)I(u∈U
D) + log p(u 6∈ UD)I(u 6∈U
D), where I(.) stands for the indicator function returning 1 if its argument is true, 0 else. p(u ∈ UD) is estimated via Monte-Carlo simulations (following the generation process of the models and counting the rate of simulations in which u is infected). 1000 simulations are performed for each test episode in our experiments.
• Diffusion Path prediction: the models are assessed on their ability to choose the true infectors in observed diffusion episodes. This is only considered on the artificial dataset for which we have the ground truth on who infected whom. The INF measure corresponds to the expectation of the rate of true infectors chosen by the models: INF =
1∑ D∈Dtest (|D|−1) ∑ D∈Dtest ∑ i∈{1,...,|D|−1} p(Ii = inf(i,D)|D≤i), with inf(i,D) the true infector of the i-th infected node in the episode D. For RNN, their is no selection mechanism, it is excluded from the results for this measure. For models with attention (CYAN and DAN), we consider the attention weights as selection probabilities. For cascade based models which explicitly model this, we directly use the corresponding probability p(Ii = inf(i,D)|D≤i). In our model, this corresponds to an expectation over previous infectors in the cascade (i.e., 1S ∑S s=1 p(Ii = inf(i,D)|D≤i, I (s) <i )), with I
(s) the s-th sampled vector from qD.
For each task, we report results with different amounts of initial observations from test episodes: infections occurred before a given delay τ from the start of the episode are given as input to the models, from with they infer internal representations, evaluation measures are computed on the remaining of the episode. In tables 1 to 4, 0 means that nothing was initially observed, the models are not conditioned on the start of the episodes. 1 means that infections at the first time stamp are known beforehand, prediction and modeling results thus concern time-stamps greater than 1 (models are conditioned on diffusion sources). 2 and 3 mean that infections occurred respectively before a delay of τ = maxT/10 and a delay of τ = maxT/20 from the start of the episode are known and used to condition the models. Details on how conditioning our model and the baselines w.r.t. starts of episodes are given in the appendix.

heading: 4.2 RESULTS
text: Results on the two artificial datasets are given in table 1. While our approach shows significant improvements over other models for NLL and CE results on the Arti1 dataset (except for CE with weak conditioning), its potential is fully exhibited on the Arti2 dataset, where embedding the history for predicting the future of diffusion looks of great importance. Indeed, in this dataset, there exists some hub nodes through which most of the diffusion episodes transit, whatever the nature of the diffusion. In that case, the path of the diffusion contains very useful information that can be leveraged to predict infections after the hub node: the infection of the hub node is a necessary condition for the infection of its successors, but not sufficient since this node is triggered in various kinds of situations. Depending on who transmitted the content to it, different successors are infected then. Markovian cascade models such as CTIC or embCTIC cannot model this since infection probabilities only depend on disjoint past events of infection, not on paths taken by the propagated content. RNN-based models are better armed for this, but their performances are undermined by their way of aggregating past information. Attention mechanisms of CYAN and DAN attempt to overcome this, but it looks quite unstable with errors accumulating through time. Our approach appears as an effective compromise between both worlds, by embedding past as RNN approaches, while maintaining the bayesian cascade structures of the data. Its results on the INF measure are very great compared to the other approaches. This is especially true on the Arti2 dataset, which highlights its very good ability for uncovering the dynamics of diffusion, even for such complex problems with strong entanglement between diffusions of different natures.
The good behavior of the approach is not only observed on the artificial datasets, which have been generated by the cascade model of CTIC on a graph of relationships, but also on real-world datasets. Tables 2 to 4 report results on the three real-world datasets. In these tables, we observe that RNN based approaches have more difficulties to model test episodes than cascade based ones. The attention mechanism of the CYAN and DAN approaches allow them to get sometimes closer to the cascade based results (especially on Digg), but their performances are very variable from a dataset to another. These methods are good for the task they were initially designed - predicting the directly next infection (this had been observed in our experimentations)-, but not for modeling or long term prediction purposes. This is a strong limitation since the directly next infection does not help much to understand the dynamics and to predict the future of a diffusion. Our approach obtains better results than all other methods in most of settings, especially for the dynamics modelling task (NLL), though infection prediction results (CE) are also usually good compared with its competitors. In-
terestingly, while embCTIC usually beats CTIC, recCTIC often obtains even better results. This validates that the history of nodes in the diffusion has a great importance for capturing the main dynamics of the network. Thanks to the black-box inference process and the recurrent mechanism of our proposal, the propositional distribution qD is encouraged to resemble the conditionnal probability of the full ancestors vector. Regarding the results, the inference process looks to have actually converged toward useful trajectories. This enables the model to adapt distributions regarding the diffusion trajectory during learning. This also allows the model to simulate more consistent cascades regarding sources of diffusion.

heading: 5 CONCLUSION
text: We proposed a recurrent cascade-based diffusion modeling approach, which is at the crossroads of cascade-based and RNN approaches. It leverages the best of both worlds with an ability to embed the history of diffusion for prediction while still capturing the tree dependencies underlying the diffusion in network. Results validate the approach both for modeling and prediction tasks.
In this work, we based the sampling of trajectories on a filtering approach where only the past observations are considered for the inference of the infector of a node. Outgoing works concern the development of an inductive variational distribution that rely on whole observed episodes for inference.

heading: 6 APPENDIX

heading: 6.1 JOINT PROBABILITY
text: In this section, we detail the derivation of p(D, I) whose formulation is given in equation 11. For each infected node at position i, we need to compute:
• the probability for UDi for being infected at its time of infections given the nodes D<i previously infected in D and the states associated to these nodes;
• the probability of the ancestor index Ii given the i-th infection Di, and the previous infections D<i associated to their states zD<i; • the probability that not infected nodes are actually not infected by the i-th infected node
given its state.
This gives: p(D, I) = p(D0|D<0, zD<0)p(I0|D≤0, zD<0) ∏
v 6∈UD p(v 6∈ UD|D0, zD0 ) (15)
× p(D1|D<1, zD<1)p(I1|D≤1, zD<1) ∏
v 6∈UD p(v 6∈ UD|D1, zD1 )
× p(D2|D<2, zD<2)p(I2|D≤2, zD<2) ∏
v 6∈UD p(v 6∈ UD|D2, zD2 )
...
× p(D|D|−1|D<|D|−1, zD<|D|−1)p(I|D|−1|D≤|D|−1, z D <|D|−1)∏
v 6∈UD p(v 6∈ UD|D|D|−1, zD|D|−1)
= |D|−1∏ i=1 p(Di|D<i, I<i) p(Ii|D≤i, I<i) ∏ v 6∈UD p(v 6∈ UD|D≤|D|−1, I)

heading: 6.2 GENERATION PROCESS
text: The generation process of our model is given in algorithm 1. The process iterates while there remains some nodes in a set of infectious nodes (initialized with u0). ⊕ denotes the concatenation between two lists. At each iteration, the process selects the infectious node u with minimal time-stamp of infection (all time-stamps but tDu0 are initialized to∞), removes it from the infectious set and records its infector and infection time-stamp in the cascade. Then, for each node v with time-stamp greater than the one of u, u attempts to infects v according to the probability ku,v(zDu ) (computed with eq 3). If it succeeds, v is inserted in the set of infectious nodes and a time t is sampled for v from an exponential law with parameter rDu,v . If the new time t for v is lower than its stored time t D v , this new time is stored in tDv , u is stored as the infector of v in the from table (used to build I D) and the new state zDv is computed according to its new infector u. The generation process outputs a cascade structure (as described in the introduction of the previous section). From the classical CTIC, the only changes are at lines 12, 14 and 19, respectively for the computation of ku,v , ru,v and zDv .

heading: 6.3 LEARNING PROCESS
text: The learning process of our model is depicted in algorithm 2. In this algorithm, the function makeBins first creates minibatches by ordering D in decreasing length and cutting this ordered list in bins of batchSize episodes each. Each bin contains 3 matrices with batchSize rows (except in the last bin which contains matrices for the remaining |D|%batchSize episodes):
• Inf : a matrix where the cell (i, j) contains the j-infected node in the i-th episode of the bin, or −1 if the corresponding episode contains less than j infected nodes. The width of the matrix is equal to the number of infected nodes in the longest episode in the bin (the episode in the first row of the matrix); • Times: a matrix where the cell (i, j) contains the infection time-stamp of the j-infected
node in the i-th episode of the bin, or −1 if the corresponding episode contains less than j infected nodes. The width of the matrix is equal to the number of infected nodes in the longest episode in the bin (the episode in the first row of the matrix); • NotInf : a binary matrix with |U| columns where the cell (i, j) equals 0 if the node j is
infected in the i-the episode of the bin, 1 otherwise;
At each epoch, the algorithm iterates on every bin. For each bin, it first initializes the states of the infected nodes using a function initStates which produces a tensor z of nbRows(Inf) matrices nbCols(Inf)×dwhose each row is filled by z0 (with nbRows(X) and nbCols(X) respectively the number of rows and columns in matrix X). For every step t of infection in the bin, the prosess first
Algorithm 1: Cascade Generation Process 1 Input: Θ, U 2 for u ∈ U do 3 tDu =∞ 4 end 5 UD = (); ID = (); tDu0 = 0; fromu0 = 0; Infectious = {u0}; 6 while Infectious 6= ∅ do 7 u← arg min
x∈Infectious tDx ;
8 Infectious← Infectious \ {u}; 9 UD ← UD ⊕ u ;
10 ID ← ID ⊕ fromu ; 11 for v ∈ U : tDv > tDu do 12 x ∼ Bernouilli (ku,v(zu)); 13 if x == 1 then 14 x ∼ Exp (ru,v); 15 t← tDu + t; 16 if t < tDv then 17 tDv ← t; 18 fromv ← |UD| − 1; 19 zv = fφ(zu, ω (f) v ); 20 Infectious← Infectious ∪ {v}; 21 end 22 end 23 end 24 end 25 Output: CD = (UD, (tDu )u∈U , I D);
determines in mask the rows of the matrices which correspond to not ended episodes (Times[:, t] refers to the column t of Times). Then, if the step is not the initial step t = 0, it uses functions computeLogA and computeLogB with nodes previously infected for each episode Inf [mask, : t] associated to their corresponding states z[mask, : t]. While the function computeLogA returns a nbRow(Inf [mask]) × t matrix where the cell (i, j) contains the log-probability for the j-th node in the i-th episode to infect Inf [i, t] at its infection time-stamp (using a matrix version of equation 5), the function computeLogB returns a same shape matrix where the cell (i, j) contains the log-probability that the j-th node in the i-th episode does not infect Inf [i, t] before its infection time-stamp (using a matrix version of equation 6).
Then, ancestors at step t are sampled from categorial distributions parameterized by P (It|D≤t, I<t) (deduced from logits A− B). From them, we compute the log-probability for each infected at step t to be actually infected at their time-stamp of infection by its corresponding sampled infector. (line 19, where sum(X, 1) is a function which returns the vector of the sums of each row from X). This quantity is added to the accumulator ll.
Line 22 then computes the states for the nodes infected at step t according to the states of the sampled ancestors in u (via the function computeStates which is a matrix version of equation 2).
At the end of each iteration t, the log-likelihood that not infected nodes in NotInf [mask] are actually not infected by infected nodes at step t is computed via computeLogG, which is a matrix version of equation 9. This quantity is added to the accumulator ll.
At the end of the bin (when t == nbCols), a control variate baseline is computed by maintaining a list bh of the quantity vectors considered in ∇ΘL(D). The baseline b considered in the stochastic gradient for any episode D is thus equal to the average of (logp(D) − 1) for this specific episode taken over the blength previous epochs.
Finally, the gradients are computed and the optimizer ADAM is used to update the parameters of the model. Note that this algorithm does not use the gradient update given in eq. 14. It is based on P (It|D≤t, I<t) and P (Dt, It|D<t, I<t) for every t ∈ {0, ..., nbCols(Inf)} (rather than based on the simplification P (Dt|D<t, I<t) as given in eq. 13). This is equivalent but greatly more efficient since in both cases P (It|D≤t, I<t) needs to be estimated for sampling and P (Dt, It|D<t, I<t) is much easier to compute than P (Dt|D<t, I<t) (P (Dt, It|D<t, I<t) involves a simple product while P (Dt|D<t, I<t) involves a sum of products).
Algorithm 2: Learning Process 1 Input: D, U , batchSize, nbEpochs, Θ, b length 2 bins← makeBins(D,U , batchSize); 3 for epoch ∈ {1, ..., nbEpochs} do 4 ibin← 0; 5 for (Inf,Times,NotInf) in bins do 6 ll← (0)nbRows(Inf); logq ← (0)nbRows(Inf); 7 z ← initStates(z0, nbRows(Inf), nbCols(Inf)); 8 for t ∈ {0, ..., nbCols(Inf)} do 9 mask ← (Times[:, t] >= 0);
10 if t > 0 then 11 A← computeLogA(z[mask, : t], Inf [mask, : t], Inf [mask, t]); 12 B ← computeLogB(z[mask, : t], Inf [mask, : t], Inf [mask, t]); 13 14 # Sample from P (It|D≤t, I<t) 15 u ∼ Categorical(logits = (A−B)); 16 logq[mask]← logq[mask] + logP i[mask,u] 17 18 # Compute P (Dt, It|D<t, I<t) 19 H ← A[mask,u]−B[mask,u] + sum(B, 1); 20 ll[mask]← ll[mask] +H; 21 22 z[mask, t]← computeStates(u, z[mask, : t], Inf [mask, : t], Inf [mask, t]); 23 end 24 ll[mask]← ll[mask] + computeLogG(z[mask, t], Inf [mask, t], NotInf [mask]); 25 end 26 bh[ibin]← h[ibin]⊕ (ll − logq − 1); 27 if epoch ≥ b length then 28 bh[ibin].pop(0); 29 end 30 b← sum(bh[ibin], 1)/min(epoch+ 1, b length);
31 ∇ΘL(D; Θ)← 1
nbRows(Inf) [sum((ll − logq − 1− b)∇Θlogq +∇Θ log ll)];
32 33 Θ← ADAM(∇ΘL(D; Θ)); 34 35 ibin← ibin+ 1; 36 end 37 end

heading: 6.4 CONDITIONED MODELS
text: Our experiments in tables 1 to 4 include results obtained with known starts of episodes (columns 1, 2 and 3, for which τ > 1). For these cases, one need to be able to condition the models according to right-censored episodes, which we note Dτ in the following (every infected node in u ∈ UD with tDu ≥ τ is reported as not infected in Dτ ). For the NLL measure, one need to be able to compute the negative log-likelihood of the end of any episode D given the beginning Dτ (which means estimating p(D|Dτ )). For the CE measure, one need to estimate the probabilities of final
infections in any episode D given its beginning Dτ (i.e., estimating p(u ∈ UD|Dτ ) via MonteCarlo simulations).
For models RNN, CYAN and DAN which have deterministic hidden representations, the conditioning on Dτ is direct: it suffices to traverse the episode from the start to the last infected node in Dτ to obtain the full representation of the input. Then, the model can be normally used from it on the remaining of the test episode for modeling or generation purposes (except for the time-stamp of the first next event for which one has to take into account that it cannot happen before τ ).
For CTIC and EmbCTIC, the conditioning is also easy since future infections from τ only depend on time-stamps of infections before τ without any need of trajectory modelling. For simulation purposes and the CE measure, the algorithm 1 can be applied with the infection time-stamps and the Infectious set initialized according to Dτ . Then, the only difference is that infection delays are sampled from a truncated exponential in order to ensure that new infections can not occur before τ . For the NLL measure, one need to reconsider the computation of the infection probabilities from nodes infected before τ , which must take into account that infections did not happened before τ . For each node v which is not infected in Dτ , its probability aDu,v of being infected by any infected node u in Dτ is divided by the probability that u did not succeed in infecting v before τ :
aD|D τ
u,v =  ku,vru,v exp −ru,v(tDv −t D u ) ku,v exp−ru,v(τ−t D u ) +1− ku,v if tDu < τ,
ku,vru,v exp −ru,v(tDv −t D u ) otherwise.
(16)
Also, for every v with tDv ≥ τ and every u with tDu < tDv , we rewrite the probability bDu,v that u does not succeed in infecting v at tDv as:
bD|D τ
u,v =  ku,v exp −ru,v(tDv −t D u ) +1− ku,v ku,v exp−ru,v(τ−t D u ) +1− ku,v if tDu < τ and t D v <∞, 1− ku,v ku,v exp−ru,v(τ−t D u ) +1− ku,v if tDu < τ and t D v =∞,
ku,v exp −ru,v(tDv −t D u ) +1− ku,v otherwise.
(17)
These quantities are used to compute the conditionnal likelihood p(D|Dτ ): p(D|Dτ ) = ∏
v∈UD,tDv ≥τ
hD|D τ
v
∏ v 6∈UD gD|D τ v (18)
where gD|D τ v = ∏ u∈UD b D|Dτ u,v and, similarly to eq.8 without the dependency in states z for CTIC, the conditionnal hD|D τ v is given as:
hD|D τ v = ∏
x∈U,tDx <tDv b D|Dτ x,v ∑ u∈U,tDu <tDv a D|Dτ u,v /b D|Dτ u,v (19)
At last, for the RINF measure, the only modification is that the statistic is computed solely on nodes i ∈ UD such that tDi ≥ τ . For our model, beyond the use of conditionnal probabilities (with similar definitions than those from eq.16, 17 and 19 but with k a function depending on the state z of the emitter such as in the section 3.2), we must consider the conditionnal distribution of the ancestors vector of nodes infected before τ , hereafter noted Iτ , given the inputDτ . As done for learning, Iτ is sampled from our propositional distribution qD τ (Iτ ) = ∏|Dτ |−1 i=1 p(I τ i |Dτ≤i, Iτ<i) and the measures are simple averages on a set of sampled Iτ . Given S samples of Iτ , the NLL is thus computed as:
NLL = −(1/|Dtest|) ∑
D∈Dtest
log 1
S S∑ s=1 p(D|Dτ , Iτ,(s)) (20)
= −(1/|Dtest|) ∑
D∈Dtest
log 1
S S∑ s=1 p(D, I(s)|Dτ , Iτ,(s)) qD(I(s)|Iτ,(s))
(21)
with qD(I(s)|Iτ,(s)) = qD(I(s))/qDτ (Iτ,(s)) and where p(D, I(s)|Dτ , Iτ,(s)) is computed same manner as in section 3.2 using conditionnal versions of probability formulations (as given above for CTIC). The last derivation is obtained according to samples of full ancestor vectors I , where I(s) is an ancestor vector starting with Iτ,(s) for the infections before τ . Similarly, the CE measure considers marginal probabilities p(u ∈ UD|Dτ ) for every node u ∈ U defined as averages on simulations performed given Dτ and sampled Iτ,(s) as input of the generation algorithm 1. Lastly, the INF measure is evaluated by considering:
INF = 1∑
D∈Dtest(|D| − |D τ |) ∑ D∈Dtest ∑ i∈{1,...,|D|−1},
t UD i ≥τ
p(Ii = fr(i,D)|D≤i, I(s)<i ) (22)
where I(s) is an ancestor vector sampled from qD.

Review summaries:
The problem that the paper tackles is very important and the approach to tackle it id appealing. The idea of regarding the history as a tree looks very promising. However, it’s noteworthy that embedding to a vector could be useful too if the embedding espace is representative of the entire history and the timing of the events.