=Paper=
{{Paper
|id=Vol-2161/paper42
|storemode=property
|title=Temporal Recurrent Activation Networks
|pdfUrl=https://ceur-ws.org/Vol-2161/paper42.pdf
|volume=Vol-2161
|authors=Giuseppe Manco,Giuseppe Pirrò,Ritacco Ettore
|dblpUrl=https://dblp.org/rec/conf/sebd/MancoPR18
}}
==Temporal Recurrent Activation Networks==
<pdf width="1500px">https://ceur-ws.org/Vol-2161/paper42.pdf</pdf>
<pre>
       Temporal Recurrent Activation Networks

               Giuseppe Manco, Giuseppe Pirrò, and Ettore Ritacco

    ICAR - CNR, via Pietro Bucci 7/11C, 87036 Arcavacata di Rende (CS), ITALY,
                           {name.surname@icar.cnr.it}




        Abstract. We tackle the problem of predicting whether a target user
        (or group of users) will be active within an event stream before a time
        horizon. Our solution, called PATH, leverages recurrent neural networks to
        learn an embedding of the past events. The embedding allows to capture
        influence and susceptibility between users and places closer (the repre-
        sentation of) users that frequently get active in different event streams
        within a small time interval. We conduct an experimental evaluation on
        real world data and compare our approach with related work.


1     Introduction

There is an increasing amount of streaming data in the form of sequences of
events characterized by the time in which they occur and their mark. This gen-
eral model has instantiations in many contexts, from sequences of tweets char-
acterized by a (re)tweet time and identity of the (re)tweeter and/or the topic
of the tweet, to sequences of locations characterized by the time and location
of each check-in. We focus on influence-based activation networks, that is, event
sequences where the occurrence of an event can boost or prevent the occurrence
of another event. Understanding the structural properties of these networks can
provide insights on the complex patterns that govern the underlying evolution
process and help to forecast future events. The problem of inferring the topi-
cal, temporal and network properties characterizing an observed set of events
is complicated by the fact that, typically, the factors governing the influence of
activations and their dependency from times are hidden. Indeed, we only observe
activation times and related marks, (e.g. retweet time) while, activations can de-
pend on several factors including the stimulus provided by the ego-network of a
user or his attention/propensity towards specific themes. The goal of this paper
is to introduce PATH (Predict User Activation from a Horizon), which focuses on
scenarios where there is the need to predict whether a target user (or group of
users) will be active before a time horizon Th . PATH can be used, for instance, in
market campaigns where target users are the potential influencers that if active,
before Th , can contribute to further spread an advertisement and trigger the
activation of influencees that can consider a given product/service. PATH learns
    SEBD 2018, June 24-27, 2018, Castellaneta Marina, Italy. Copyright held by the
    author(s).
an embedding of the past event history via Recurrent Neural Networks that also
cater for the diffusion memory. The embedding allows to capture influence and
susceptibility between users and places closer (the representation of) users that
frequently get active in different streams within a small time interval.
Related Work. We conceptually separate related research into: (i) approaches
like DeepCas [9] and DeepHawkes [2] that tackle the problem of predicting the
length that a cascade will reach within a timeframe or its incremental popularity;
(ii) approaches like Du et al. [4] and Neural Hawkes Process (NHP) [10] model
and predict time event markers and time; (iii) approaches based on Survival Fac-
torization (SF) [1] that leverage influence and susceptibility for time and event
predictions; (iv) other approaches that do not use neural networks (e.g., [5, 3,
12]). PATH adopts a different departure point from these approaches: it focuses on
predicting the activation of (groups of) users before a time horizon. Differently
from (i) PATH considers time and uses an embedding to capture both influence
and susceptibility between users and predict future activations. Moreover, (i) fo-
cuses on the prediction of cumulative values only (e.g., cascade size). Differently
from (ii), we do not assume that time and event are independent. Besides, (ii)
focuses on predicting event types (e.g., popular users), which is not enough in the
scenarios targeted by PATH (e.g., targeted market campaigns) where one is inter-
ested in predicting the behavior of specific users and not their types. A for (iii),
it fails in capturing the cumulative effect of history while PATH captures by using
an embedding. As for (iv), the main difference is that PATH can automatically
learn (via neural networks) an embedding representing influence/susceptibility.
The contributions of the paper are as follows: (i) PATH, a classification-based
approach based on recurrent neural networks allowing to model the likelihood
of observing an event as a combined result of the influence of other events; (ii)
an experimental evaluation and a comparison with related work.
The remainder of the paper is organized as follows. We introduce the problem in
Section 2. We present PATH in Section 3. We compare our approach with related
research in Section 4. We conclude and sketch future work in Section 5.

2    Problem Definition

We focus on network of individuals who react to solicitations along a timeline.
An activation network can be viewed as an instance of a marked point processes
on the timeline, defined as a set X = {(th , sh )}1≤h≤m . Here, th ∈ R+ denotes the
events of the point process, and sh ∈ M denote the marks in the measurable space
M. Relative to activation networks, the specification of sh occurs by means of the
realizations uh , ch and xh , where uh ∈ V (with |V| = N ) represent individuals,
ch ∈ I (with |I| = M ) represent solicitations and xh is side information which
characterizes of the reaction of the entity, described as an instance relative to a
feature space of interest. For example, V can represent users who are engaged in
online discussions I, and the tuple (th , (uh , ch , xh )) represents the contribution
of uh to discussion ch with the post xh . It is convenient to view the process
as a set of cascades: that is, for each c ∈ I we can consider the subset Hc =
{(t, u, x)|(t, (u, c, x)) ∈ X} of elements marked by c, with mc = |Hc |. Also, tc and
U c represent the projections on the first and second column of Hc . We also denote
       c            c
by H<t      (resp. H≤t ) the set of events ei ∈ Hc such that ti < t (resp., ti ≤ t). The
           c         c
terms t<t and U<t can be defined accordingly. The relationship u ≺c v denotes
that both u and v are active in Hc and there are some events relative to u and
v such that u precedes v in some events. Finally, C = {H1 , · · · HM } denote a
collection of M cascades over V and I.
Modeling diffusion. We start from the observation that what is likely to hap-
pen in the future (viz. which user will be active and when) depends on what
happened in the past (viz. the chain of previously active users). One impor-
tant point to take into account is the susceptibility of users, that is, the extent
to which they are influenced by specific previously activated users. Our model
should be flexible enough to reflect both exciting and inhibitory effects. While
the former boosts the likelihood of observing u active in c, the latter actually
could prevent it to do so. Given a cascade Hc , a timestamp t ≥ 0 and a user
         c                                                                           c
u 6∈ U<t    , the goal is to obtain an estimate of the density function f (t, u|H<t    ),
which can be used to model the following evolution scenario: given a time horizon
Thc ; how likely is it that u will become active in c within Thc ?
The challenge, at this point, is how to concretely formulate the density f . We
can decouple its specification as follows:
                                 c              c           c
                        f (t, u|H<t ) = g(t|u, H<t ) · h(u|H<t ),                  (2.1)

where the first component represents the likelihood that u becomes active within
t, given the current history, and the second component represents the likelihood
that u activates (independent of the time) as a reaction to the current history.
              c
    As for H<t  , explicit information includes features like the sequence of user
activations, their activation times, the relative activation speed, and possibly
                                                                            c
the topic of the cascade. Nevertheless, our assumption is that H<t             can also
encode latent information including susceptibility and influence between users
that can be derived, for instance, from neighborhood information in a network
(e.g., follower/followee relations in Twitter) or user behaviors (e.g., users that
retweet after a certain set of other influential user (re)tweet). This is exactly
what we want to unveil in our modeling.
Embedding history. We want to learn and embedding of users in a latent
K-dimensional space such that users in the same cascade are closer in the em-
bedding, and users within different cascades are distant. We make usage of two
matrices S = [s1 , . . . , sN ], A = [a1 , . . . , aN ] ∈ RN ×K that represent the sus-
ceptibility and influence, respectively. Matrices are computed by relying on the
standard network architecture borrowed from the word2vec paradigm [11]:

                              av = We v        su = V e u

Here, u, v represents the one-hot encodings of u and v. The matrices We , Ve rep-
resent the embeddings, obtained by minimizing an adapted form of contrastive
loss [6] that penalizes the distance of users within the same cascades and the
closeness of users in different cascades.
Capturing the diffusion memory. To encode temporal relationship within
   c
H<t    we use recurrent neural networks (RNNs) An RNN is a recursive structure
that, at the current step, gets as input the previous network state (the outputs
form the hidden units) along with the current input to compute a new state.
The following picture provides an overview of a simple RNN cast to our context.
At each step k, we feed into the network
an event ek ∈ Hc that encodes the current
user (uk ) and its activation time (tk ). The
learned hidden state (hk ) represents the non-           f (t , u )
                                                             k    k  f (t   ,u
                                                                          k+1  )  k+1



linear dependency between these components hk 1             hk            hk+1
and past events, which can be used to model
             c
f (tk , uk |H<tk
                 ). In the following, we adopt                                   time

the LSTM instantiation of the RNN frame-                     ek           e k+1



work [7]. The idea of an LSTM unit is to
reliably transmitting important information
many time steps into the future. At every time step, the unit modifies the in-
ternal status by deciding which part to keep or replace with new information
coming from the current input. We use the shortcut hk = LSTM(zk , hk−1 ) to
denote a functional architecture that elaborates an input zk and outputs the
updated state.


3    PATH: Predicting User Activation from a Horizon

We now introduce PATH (Predicting User Activation from a Horizon), which fo-
                               c                                                 c
cuses on simplifying f (t, u|H<t ) as the binary response function I(t ≤ Th |u, H<t )
that denotes whether u becomes active in c within Th . We focus on events
ek ∈ Hc where where the features of interest xk are limited to the time de-
lay δk = tk − tk−1 relative to the previous activation within the cascade. This
allows us to capture the property that cascades may have intrinsically differ-
ent diffusion speeds causing some of them to concentrate users’ activations in a
short timeframe while others in a more extended interval. Given a partially ob-
                   c
served cascade H<t   l
                       (with tl < Thc representing the timespan of the observation
window), our objective is to predict, for a given entity u 6∈ Utl , whether u ∈ UThc .
    In order to uncover all the characteristics of the activations within cascades,
we consider a model built on all possible prefixes of the available cascades. Notice
that, in our reconstruction, we do not consider the first element within the
cascade, which we assume becomes “spontaneously” active. Finally, for each
u 6∈ U c , we associate the cascades H≤t c
                                           j
                                             ∪ {(tj , u, δj )} (with 1 ≤ j ≤ mc − 1)
        c       c       c
and H ∪ {(Th , ui , (Th − tmc ))} with negative labels. Again, the intuition is
that, since u is not active no partial cascade provides the sufficient intensity to
activate u within the given time horizon. Adding negative examples in the data
preparation represent an effective data augmentation process, which enlarges
the training data by inferring new inputs in the training set. This is crucial to
let the approach better fine tune separation between active and inactive users,
as well as better characterize the true activation time of active users. Let TC
denote the set of all pairs partial sequence/associated label that can be built
from the above discussion. Our idea is to exploit the embedding and LSTM
tools described in the previous section to solve the supervised problem at hand.
Figure 1 illustrates the basic ar-
chitecture of the model. Given a
pair hHi , yi i ∈ TC with |H|=n and
by considering ek = (tk , uk , δk ) ∈              ỹ               ŷ

H (with 1 ≤ k ≤ n), the architec-
                                       Output   Similarity      Activation
ture of the network can be cap-        Layer      Score         prediction

tured by the following equations:
                                              Recurrent              Cumulative
                                                                                                hk
    ak =We uk                       (3.1)      Layer                   sum
                                                                                                                    k=1,…, n

 hk =LSTM ([ak , tk , δk ], hk−1 )                                                                      Concatenate
                               (3.2)
                                               Input      Susceptibility           Influence
    ŷi =σ (Wo hn )         (3.3)              Layer       embedding              embedding
                           2
                              
                    n−1
                     X                                        un                    uk            tk           k

                                                            Target                  User       Activation Delta previous
    ỹi = exp − an −     ak                                  user                                 time      actvation
                             
                           k=1
                                    (3.4)
    Here, ŷi represents the proba-              Fig. 1: Overview of PATH.
bility that yi is positive, as pro-
vided by the network: that is, it
encodes the probability that un
becomes active within tn ; ỹi encodes the Paffinity  between un and all users pre-
                                             n−1
ceding it within Hi . The distance kan − k=1 ak k plays a crucial role here: since
the target user is on the tail of the cascade, the embedding should emphasize the
similarities with the predecessors that trigger an activation, and by the converse
minimize the similarities with those ones which do not trigger it. The loss is a
combination of cross-entropy and the embedding loss previously described:
            X
     L=              {y (γ log(ŷ) + β log ỹ) + (1 − y) (γ log(1 − ŷ) + β log(1 − ỹ))}
          hH,yi∈TC
                                                                                                                      (3.5)
           |H|=n


where γ and β are weights balancing cross-entropy and embedding.

4     Experiments
We validate our approach by analysing the algorithm on real-life datasets. In
particular, we analyse the capability of the algorithm at predicting the activation
time of users within an information cascade. The implementation we use in the
experiments can be found at https://github.com/gmanco/PATH.
Datasets. We evaluated the prediction capability of PATH by exploiting two
real-world datasets containing propagation cascades crawled from the timelines
of Twitter2 and Flixster.3 In particular, Twitter includes ∼32K nodes with
 ∼9K cascades while Flixster includes ∼2K nodes with ∼5K cascades.
2
    http://www.twitter.com/
3
    http://www.flixster.com/
    The information propagation mechanism on Twitter is expressed by retweet-
ing, in other words a chain of repetitions and transmissions of a tweet from a set
of users to their neighbors in a recursive process. Each activation corresponds to
a retweet. An activation in Flixster happens when a user rates a movie, while
a cascade is composed by all the activations related to the same movie. The two
datasets differ essentially for the following characteristics: Twitter includes a
larger number of users and shorter delays than Flixster. In addition, retweets
intuitively highlight two relevant aspects, namely the importance of the topic
and the single influence of the individual from which the retweet is performed.
By contrast, movie ratings are more likely to exhibit a cumulative effect: popular
movies are more likely to be considered than unpopular ones.
Evaluation Methodology. We evaluate PATH against two baseline models,
both relying on Survival Analysis [8]. The first instantiation implements a Cox
proportional hazard model (CoxPh in the following). We implement the model
using the lifelines4 package and extract, for each event ek ∈ Hc , the following
features: (1) size of the prefix; (2) last activation time; (3) average delay for
each active user so far; (4) number of neighbors in the history, and (5) coverage
percentage of them within the history; (6) the activation time of the most recent
neighbor, if any; (7) correlation between the activation of the current user an its
neighbors within the history, computed in previous cascades. This model repre-
sents an intuitive baseline where features are manually engineered and include a
mix of external information (coming from the underlying network neighborhood)
and information derived from the cascade itself. The second instantiation is given
by the Survival Factorization (SF in the following) framework described in [1].
The comparison is important since SF relies on the same guiding ideas of PATH
(influence/susceptibility) with the difference that there is no cumulative effect
      c
of H<t  k
          , but instead an influential user has to be detected for each activation.
     To evaluate the approaches we proceed as follows: given training and test
sets Ctrain and Ctest , we train the model on Ctrain and measure the accuracy
of the predictions on Ctest . The two sets are obtained by randomly splitting
the original dataset by ensuring that there is no overlap among the cascades of
the two sets, but there is no entity in the test that has not been observed in
the training. For the evaluation, we chronologically split each cascade c ∈ Ctest
into c1 and c2 such that, for each u ∈ c1 and v ∈ c2 , we have that u ≺c v.
Next, we pick a random subsample c3 ⊆ V − U c . Then, given a target horizon
Thc , we measure TP, FP, TN and FN by feeding the models on c1 and then
predicting the activation within Thc for each element in c2 ∪ c3 . The choice of Thc
can follow different strategies; Fixed horizon (Fixed horizon (FH): setting Tch as
the maximum observed activation time Thtest = max{t|t ∈ tc , c ∈ Ctest }; Variable
horizon (VH): varying Thc from the smallest to the largest activation time and
computing the activation probabilities associated to each possible value; Actual
Time (AT): a particular case of the VH strategy, where Thc , Thu,c is relative to
the true activation time in c of each user u ∈ c2 ∪ c3 .

4
    see http://lifelines.readthedocs.io for details.
    We plot the ROC and the F-Measure curves relative to the above alternatives
and report the AUC and F values. For PATH, the encoding of sequences as
described in section 3 already presumes that users are evaluated on intermediate
timestamps prior to their actual activation. Thus, VH and AT roughly coincide
in this case. Since both CoxPh and SF are capable of inferring, for each (u, H)
pair, the probability Su (t|H), the comparison with PATH is done by computing
1 − Su (t̃|H) where t̃ is the horizon timestamp. The parameter space for PATH
was explored by grid-search, measuring the loss on a separate portion of the
training set by 5-fold cross-validation. We report 5 different instantiations, which
differ from the number of cells in the LSTM (32/64), the dimensionality of the
embedding (32/64) and the batch size in the training (128/256/512). Concerning
SF, the number of factors was set to 16 for both datasets.


       0.96                                                                      0.96
       0.88                                                                      0.88
       0.80                                                                      0.80
       0.72                                                                      0.72
       0.64                                                                      0.64
       0.56                                             CoxPh(AT)                0.56                                             CoxPh(AT)
       0.48                                             CoxPh(FH)                0.48                                             CoxPh(FH)
       0.40                                             PATH(AT,64,64,256)       0.40                                             PATH(AT,64,64,256)
       0.32                                             PATH(AT,32,32,256)       0.32                                             PATH(AT,32,32,256)
       0.24                                             PATH(AT,32,32,512)       0.24                                             PATH(AT,32,32,512)
       0.16                                             PATH(AT,32,64,512)       0.16                                             PATH(AT,32,64,512)
       0.08                                             PATH(AT,32,32,128)       0.08                                             PATH(AT,32,32,128)
       0.00                                             SF(VH)                   0.00                                             SF(VH)
              0.00 0.08 0.16 0.24 0.32 0.40 0.48 0.56 0.64 0.72 0.80 0.88 0.96          0.00 0.08 0.16 0.24 0.32 0.40 0.48 0.56 0.64 0.72 0.80 0.88 0.96

                               (a) Flixster                                                               (b) Twitter
         Fig. 2: ROC Curves for PATH,CoxPh and SF on both datasets.
Evaluation Results. Figure 2 reports the ROC curves where we observe that
PATH outperforms the baselines and in particular exhibits a very good accuracy
on all configurations. This is especially true on Flixster, where by the converse
SF does not seem capable of correctly correlating previous activations times.
The cumulative influence effect is evident here, as a natural consequence of the
underlying domain where cascading effects are more likely as a consequence of a
“word of mouth” process. On Twitter, where the activation is more likely due
to the influence of a single user (as testified by the good performance of SF),
PATH still achieves the best scores, thus proving the capability of the recurrent
layer to adapt the influence to a single user. By analyzing Fig. 3, which displays
the F-measure curve for varying values of the threshold on the probabilities, we
can observe that, contrary to the baselines, higher thresholds do not cause a
significant drop of the recall. The only exception is CoxPh (FH), which seems
more stable on Flixster. This is a clear sign that the probabilities associated
with active and inactive users in PATH differ substantially, and in particular active
events are associated with significantly higher probabilities than inactive events.


5   Concluding Remarks and Future Work
We focused on the problem of predicting user activations in a given time horizon
and show that the embedding of the user activation history, where users that
                  0.96                                                                              0.96
                  0.88                                                                              0.88
                  0.80                                                                              0.80
                  0.72                                                                              0.72                                            CoxPh(AT)
                  0.64                                                                              0.64                                            CoxPh(FH)
                  0.56                                                                              0.56                                            PATH(AT,64,64,256)
      F-Measure




                                                                                        F-Measure
                                                                                                                                                    PATH(AT,32,32,256)
                  0.48                                                                              0.48                                            PATH(AT,32,32,512)
                                                                  CoxPh(AT)                                                                         PATH(AT,32,64,512)
                  0.40                                            CoxPh(FH)                         0.40
                                                                                                                                                    PATH(AT,32,32,128)
                  0.32                                            PATH(AT,64,64,256)                0.32                                            SF(VH)
                                                                  PATH(AT,32,32,256)
                  0.24                                            PATH(AT,32,32,512)                0.24
                  0.16                                            PATH(AT,32,64,512)                0.16
                                                                  PATH(AT,32,32,128)
                  0.08                                            SF(VH)                            0.08
                  0.00                                                                              0.00
                     0.00 0.08 0.16 0.24 0.32 0.40 0.48 0.56 0.64 0.72 0.80 0.88 0.96                  0.00 0.08 0.16 0.24 0.32 0.40 0.48 0.56 0.64 0.72 0.80 0.88 0.96
                                                  Threshold                                                                         Threshold
                                       (a) Flixster                                                                       (b) Twitter
          Fig. 3: F-Measure curves for PATH,CoxPh and SF on both datasets.


become active on the same cascades are placed close, can be effectively learned
via recurrent neural networks. Experiments performed on real datasets show
the effectiveness of the approach in accurately predicting next activations. It
is natural to wonder whether it is possible to cast the intuitions behind our
approach in a generative setting, to predict both which user is likely to become
active, and the time segment upon which s/he will become active.

References
 1. N. Barbieri, G. Manco, and E. Ritacco. Survival factorization on diffusion networks.
    In PKDD, pages 684–700, 2017.
 2. Q. Cao et al. Deephawkes: Bridging the gap between prediction and understanding
    of information cascades. In CIKM, pages 1149–1158, 2017.
 3. Peng Cui, Shifei Jin, Linyun Yu, Fei Wang, Wenwu Zhu, and Shiqiang Yang. Cas-
    cading outbreak prediction in networks: a data-driven approach. In KDD, pages
    901–909. ACM, 2013.
 4. N. Du, H. Dai, R. Trivedi, U. Upadhyay, M. Gomez-Rodriguez, and L. Song. Re-
    current marked temporal point processes: Embedding event history to vector. In
    KDD, pages 1555–1564, 2016.
 5. A. Guille and H. Hacid. A predictive model for the temporal dynamics of infor-
    mation diffusion in online social networks. In WWW, pages 1145–1152, 2012.
 6. R. Hadsell, S. Chopra., and Y. LeCun. Dimensionality reduction by learning an
    invariant mapping. In CVPR, pages 1735–1742, 2006.
 7. S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Computation,
    9(8):1735–1780, 1997.
 8. J.D. Kalbfleisch and L.P. Ross. The Statistical Analysis of Failure Time Data.
    Wiley Series in Probability and Statistics, 2002.
 9. C. Li, J. Ma, X. Guo, and Q. Mei. Deepcas: An end-to-end predictor of information
    cascades. In WWW, pages 577–586, 2017.
10. H Mei and J.M. Eisner. The neural hawkes process: A neurally self-modulating
    multivariate point process. In NIPS, pages 6757–6767, 2017.
11. T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean. Distributed repre-
    sentations of words and phrases and their compositionality. In NIPS, 2013.
12. L. Yu, P. Cui, F. Wang, C. Song, and S. Yang. From micro to macro: Uncovering
    and predicting information cascading process with behavioral dynamics. In ICDM,
    pages 559–568, 2015.

</pre>