Topological Recurrent Neural Network for Diffusion Prediction

I Introduction

Information diffusion is a common phenomenon on social networks . Its modeling has many applications, such as helping to predict which user is an opinion leader , how much a cascade will grow , who are the diffusion sources , which user will digg a particular story , and so on. In this paper, we study the task of information diffusion prediction. The goal is to design an effective diffusion model, which can estimate the activation probability for an inactive node in a cascade. We consider the most standard setting of information diffusion, where we have inputs of: 1) a data graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of nodes and $\mathcal{E}$ is the set of edges; 2) a set of cascade sequences, each of which is an ordered sequence of node activation over $\mathcal{V}$. For example, in Fig. 1, the data graph $\mathcal{G}$ is a network of seven nodes; a cascade sequence $A\!\rightarrow\!B\!\rightarrow\!C\!\rightarrow\!D$ is a sequence of nodes ordered by their activation time stamps.

Early work assumes diffusion model as given, such as independent cascade (IC) and linear threshold (LT) . There are many extensions of the IC and LT models, such as continuous-time IC . Besides, the IC and LT models also enable an important research direction of influence maximization . Recent work tries to learn a diffusion model from the available cascade data. They often rely on explicitly engineering useful features to predict the activation probability of a node, such as network structure and temporal information , user nodes’ social roles , diffusion content and user nodes’ interactions . Although these methods have shown significant improvements in diffusion prediction performance, the feature engineering process requires much manual effort and extensive domain knowledge. With the recent development of neural networks, recent work starts to exploit deep learning, so as to avoid explicit feature engineering for diffusion modeling. A small number of pioneer work uses graph embedding to model diffusion. For example, Embedded-IC takes a cascade-based modeling approach, which considers each inactive node to be activated by the active nodes. It differentiates two kinds of roles for the nodes; i.e., an active node serves as a “sender”, and an inactive node serves as a “receiver”, so that the inactive node receives information from the active nodes in a diffusion cascade. For each role, it learns a vector as a node’s embedding. Then, it models an activation based on the closeness between an inactive node’s receiver embedding vector and the active nodes’ sender embedding vectors. DeepCas is designed to predict the future cascade size. It models the cascade at each time step with an induced subgraph over the active nodes. Then, it decomposes the subgraph into some random walk paths, and uses Gated Recurrent Unit (GRU) to learn an embedding vector of the subgraph. Based on this subgraph embedding vector, it predicts the cascade size in the future.

Despite the success of these deep learning methods for diffusion modeling, we find that they often underexplore the cascade structure. A cascade is not merely a sequence of nodes ordered by the activation time stamps; instead, it has a richer structure indicating the diffusion dynamics over the data graph. For example, in Fig. 1, to represent the cascade from $A$ to $D$, we shall describe how it spreads over the data graph $\mathcal{G}$. Particularly, when $A$ is activated at the first place, it has a chance to activate its neighbors in $\mathcal{G}$, which are $\{B,C,F\}$. By drawing an arrow from $A$ to each of its neighbors to show the possible activation attempts, we have a diffusion topology to characterize the cascade until the current time stamp in Fig. 1(a). Similarly, when $B$ is activated next, it also has a chance to activate its (inactive) neighbors $\{C,E\}$. As a result, we have another diffusion topology in Fig. 1(b) for the new time stamp. Such diffusion topologies are useful for diffusion prediction; e.g., a Twitter user is more likely to propagate a piece of news to her friends, if that news has been retweeted by many celebrities. However, the existing deep learning methods for diffusion modeling do not take diffusion topologies into consideration. For example, in Embedded-IC , an activation at time stamp $t$ is enabled between an inactive node and all the existing active nodes by $t$, regardless of the network structure. Therefore, the embedding of each sender (i.e., active node) is learned without the diffusion topologies. In DeepCas , the induced subgraph at each time step does not capture how the diffusion spreads; besides, each subgraph is further decomposed into paths and embedded independently, thus the resulting node embedding is only partially aware of the data graph structure.

In this paper, we study how to fully explore the cascade structure by deep learning for diffusion prediction. Generally, in cascade dynamics, the active nodes try to “send” information to the inactive nodes; upon successfully “receiving” the information, an inactive node becomes activated. Motivated by such cascade dynamics, we choose to differentiate two roles for each node; i.e., each active node acts as a “sender” and each inactive node acts as a “receiver”. Therefore, to enable deep learning for diffusion modeling, we try to embed each active node with a sender embedding vector, and each inactive node with a receiver embedding vector, such that we can simply predict a node activation based on these embedding vectors. Although such a “sender”-vs-“receiver” role differentiation is also adopted by Embedded-IC, we approach the embedding problem differently. In Embedded-IC, each sender (or receiver) embedding is considered as encoding the static preferences of a sender (or receiver). Such a formulation overlooks the dynamic context of diffusion topologies; i.e., once the sender embedding of an active node and the receiver embedding of an inactive node are fixed, the resulting activation probability based on these two embedding vectors is also fixed, regardless of how the cascade grows over time. As discussed earlier, such dynamic context of diffusion topologies are useful for diffusion prediction. Therefore, we should consider the sender embedding as encoding not only the active node’s static tendency, but also the dynamic context of the diffusion topology. As the inactive nodes have not participated in the cascade so far, it is reasonable to consider each receiver embedding as only encoding its inactive node’s static preferences.

Technically, it is not trivial to learn sender embedding with diffusion topologies. This is because each diffusion topology is a directed acyclic graph (DAG) and it evolves over time. On the one hand, we cannot over-simplify the dynamic DAGs into a set of independent nodes or a set of random walk paths for learning the sender/receiver embedding, since these over-simplified formulations are unable to fully exploit the topologies of cascades on the network. On the other hand, due to the dynamic nature of diffusion topologies, we are looking for a recurrent neural network (RNN) formulation. To the best of our knowledge, however, there is no RNN that is able to handle such dynamic DAG structure of a diffusion. For example, the existing RNN models mainly focus on either sequence-structured inputs, such as Long Short-Term Memory (LSTM) and GRU, or tree-structured inputs, such as Tree-LSTM . There are a handful of RNN models that try to model static DAGs designed for different application domains; e.g., DAG-RNN models each 2D image as a DAG for scene labeling, while RNN-LE models each contact map over a protein’s amino acids as a DAG for protein structure prediction. However, both DAG-RNN and RNN-LE are based on the plain RNN architecture, and are unable to capture the peculiarities of a diffusion process. Thus, an RNN architecture tailed for diffusion is required.

To model the diffusion topologies, we propose a novel Topological LSTM (Topo-LSTM) model. Topo-LSTM is a DAG-structured RNN, which takes dynamic DAGs as inputs and generates a topology-aware embedding for each node in the DAGs as outputs. In the application of diffusion prediction, we use Topo-LSTM to learn the sender embedding for each node $v_{t}$ activated at time $t$ in a cascade. We ensure the learned sender embedding of $v_{t}$ as fully aware of which other nodes have been activated so far and how the diffusion spreads to reach $v_{t}$. For example, in Fig. 1, the sender embedding of an active node $C$ knows that $A$ and $B$ have been activated, and the diffusion spreads like Fig. 1(b) before activating $C$. We consider each inactive node as having a receiver embedding, which is independent of the cascade to indicate the node’s intrinsic preference. We also learn the receiver embedding for each inactive node, and use it to predict an activation based on its closeness to the active nodes’ sender embeddings. It is worth noting that, our model has few hyperparameters, including an embedding dimension and a trade-off parameter for model regularization. This makes our model easy to tune in practice, compared with other graph-based deep learning methods, which require additional hyperparameters for either graph sampling or objective functions .

We summarize our contributions as follows.

We propose a new data model, namely diffusion topology, to fully explore the diffusion structure.

We propose a novel Topo-LSTM model, which is able to handle the dynamic DAG structure of diffusion topologies and tailored for the task of node activation prediction.

We evaluate Topo-LSTM on several public real-world data sets, and show that Topo-LSTM significantly outperforms the state-of-the-art baselines.

II Related Work

In diffusion prediction, early work assumes the diffusion model as given. For example, in , IC and LT models are used for influence maximization. Some other work tries to learn the diffusion model from the cascade data. For example, in , the diffusion model is formulated as a learnable coverage function. In , both the internal and external influences are modeled, with some parameters to be learned. In this paper, we focus on the task of diffusion prediction, and aim to learn an activation function from the data. In diffusion prediction, most existing work relies on extracting useful features for activation prediction. For example, in , various features are exploited, including content, user, time and network structure. Some recent studies use deep learning to avoid feature engineering for diffusion prediction. As introduced in Sect. I, both Embedded-IC and DeepCas are shown to significantly improve the diffusion prediction. Wang et al. proposes a model similar to Embedded-IC which computes two low-dimensional vectors for each node to capture its influence and susceptibility. However, they tend to underexplore the cascade structure. In comparison, we try to fully explore the diffusion dynamics with diffusion topologies. Recently, Du et al. uses RNN to model linear sequences of events with timestamps. However, their model cannot be applied to information diffusion in networks.

In the recent development of recurrent and recursive neural networks, multiple types of data structures are considered. Standard RNNs are designed for sequences; e.g., LSTM and GRU are used to model music and speech . Tree-structured RNN are exploited especially in natural language processing. For example, to model the dependency tree in word embedding, a DT-RNN is proposed . In , a tree-LSTM is introduced to model the syntactic properties of combining words to phrases. In , a RNNG is developed to encode a parse tree. There are a handful of RNNs designed for DAGs in various applications. For example, in scene labeling , an image is segmented into a 2D lattice, from which several DAGs are extracted by a tree-reweighted max-product algorithm; then, a DAG-RNN is introduced for modeling. In protein structure prediction , a contact map over the amino acids of a protein is decomposed into a DAG by traversing the map in certain directions; then another DAG-RNN is developed. In face detection from images , a region adjacency graph with labeled edges is first extracted from each image; then, the graph is decomposed into an edge-labeled DAG by breadth-first search, and modeled by a RNN-LE model.

Compared with the above DAG-structured RNNs, we have two major differences. First, our Topo-LSTM is designed for dynamic DAGs, where the DAGs (i.e., diffusion topologies) evolve over time. In contrast, the input DAGs of both DAG-RNNs and RNN-LE are static (e.g., images and protein structures). Second, our Topo-LSTM is designed for a different application. Due to domain differences, we cannot directly apply DAG-RNNs and RNN-LE to our diffusion prediction task. For example, DAG-RNNs are customized for images, which are 2D lattices with fixed orders, instead of a real graph as used in information diffusion. RNN-LE requires the DAGs to have edge labels, which are not available in our problem. Also, at each time step, in their models a recurrent unit can take only take a single type of inputs from their precedents, whereas the diffusion problem requires our model to take inputs from different types of precedents (i.e., predecessors of the current node v.s.others in the diffusion topology), in order to account for the different types of influences from previously activated nodes on the current node. Third, they are based on the plain RNN architecture, which are insufficient to model the complexity of a diffusion process, and suffer from the vanishing/exploding gradient issues.

Finally, there is a relevant line of research on graph embedding. Most graph embedding aims to output a vector representation for each node in the graph, such that two nodes “close” on the graph have similar vector representations in a low-dimensional space. Specifically, earlier node embedding methods, such as LLE , often focus on preserving first-order proximity, where two nodes directly linked in the graphs have similar embedding vectors. More recent methods, such as DeepWalk and Node2Vec , start to consider preserving second-order proximity, where two nodes sharing similar “neighbors” have similar embedding vectors. LINE tries to preserve both first- and second-order proximity. GraRep and HOPE preserve high-order proximity by learning node embedding from a high-order adjacency matrix. ComE further considers community-aware high-order proximity for node embedding and community embedding. There is also some graph embedding work that focuses on either edge embedding (e.g., TransE ), path embedding (e.g., ProxEmbed ), structure embedding (e.g., topoLSTM ) or whole graph embedding (e.g., Graph Convolutional Network ). A comprehensive survey of graph embedding with different types of outputs is in . Although the above methods are successful for many applications, they are designed for general purpose graph embedding to preserve the data graph structure, thus it is unable to incorporate the cascade information for diffusion modeling.

III Diffusion Modeling

We study the task of diffusion prediction that aims to estimate which node to activate next based on a cascade of node activations on a data graph. To formalize our problem, we first introduce some terminologies. We also summarize our notations in Table I for reader’s reference.

A data graph is $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the node set, and $\mathcal{E}$ is the edge set.

A cascade sequence is an ordered sequence of tuples $s=\{(v_{1},t_{1}),...,(v_{T},t_{T})\}$, where each $v_{j}$ is a distinct node in $\mathcal{V}$, and each $t_{j}$ is a time stamp such that $t_{j}<t_{j+1}$.

As problem input, we have a data graph $\mathcal{G}$ and a set of training cascade sequences $\mathcal{S}=\{s_{1},...,s_{n}\}$. It is worth noting that, in this paper we consider the most basic setting of information diffusion . Specifically, we do not assume the diffusion content information as available in the data graph and the cascade sequences. Besides, we do not assume the exact time information (i.e., what time each $t_{j}$ refers to) in each cascade sequence as known either; instead, we only rely on the order of the nodes in each cascade sequence, and thus we could equivalently rewrite the cascade as $s=\{(v_{1},1),...,(v_{T},T)\}$. We leave incorporating content and exact time information as future work. As problem output, we have a diffusion model $\mathcal{M}$, which is able to predict a node to activate at time $t$, given a test cascade sequence $s^{\prime}=\{(v_{1}^{\prime},1),...,(v_{t-1}^{\prime},t-1)\}$.

The challenge of learning $\mathcal{M}$ is that, we need to make the sender embedding be fully aware of the cascade dynamics, which describes how a cascade sequence spreads over the data graph. To address this challenge, we introduce a new data model, namely diffusion topology, to model the cascades (Sect. III-A). Then we develop a novel Topo-LSTM model to learn the sender embedding for active nodes and the receiver embedding for inactive node with the diffusion topologies (Sect. III-B). Finally, we use both the sender embeddings and the receiver embeddings to develop an activation function, and use the ground truth node activation as supervision to train the Topo-LSTM (Sect. III-C).

We discuss how to prepare the cascade data for learning the sender embedding for each active node. For a cascade sequence $s=\{(v_{1},1)$, …, $(v_{T},T)\}$, we denote $Q_{1:t-1}$ as the set of active nodes in $s$ before time $t$; i.e., $Q_{1:t-1}=\{v_{1},...,v_{t-1}\}$. Ideally, as the sender embedding of $v_{t}$, $\mathbf{h}_{t}$ needs to be fully aware of the cascade dynamics; i.e., it knows not only which nodes are in $Q_{1:t-1}$, but also how the diffusion spreads to reach $v_{t}$. Let us consider the cascade sequence in Fig. 1. $C$’s sender embedding $\mathbf{h}_{C}$ is supposed to encode the cascade dynamics that, $Q_{1:2}=\{A,B\}$ have been activated and the diffusion, before activating $C$, has spreaded like Fig. 1(b). In general, a diffusion topology such as Fig. 1(d) is not explicitly available in $Q_{1:t-1}$; instead, it needs to be constructed from $Q_{1:t-1}$ and the data graph $\mathcal{G}$. We remark that, for each $v_{t}$, there is only one unique diffusion topology; this is because at different time stamps, the set of active nodes and their cascade structures are different.

For a cascade $s=\{(v_{1},1),...,(v_{T},T)\}$ and a data graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, the diffusion topology of $s$ at time $t$ is a directed graph $\mathcal{G}^{*}_{t}=(\mathcal{V},\mathcal{E}^{*}_{t})$, where $\mathcal{E}^{*}_{t}=\{(v_{i},u)|(v_{i},u)\in\mathcal{E},v_{i}\in Q_{1:t-1},u\in(\mathcal{V}\backslash Q_{1:t-1})\cup Q_{i+1:t-1}\}$ is a set of directed edges, indicating all the possible activation attempts until $t$.

For an edge $(v_{i},u)\in\mathcal{E}^{*}_{t}$, $v_{i}$ already became active at time $i\leq t-1$. Depending on whether $u$ is active or not by the time $t-1$, this edge $(v_{i},u)$ has different kinds of semantics. Specifically, if $u\in(\mathcal{V}\backslash Q_{1:t-1})$, i.e., $u$ is inactive by time $t-1$, then $(v_{i},u)$ indicates a possible “future activation” attempt from $v_{i}$ to $u$. If $u\in Q_{i+1:t-1}$, i.e., $u$ became active after time $i$ and before time $t-1$, then it indicates a possible “past activation” from $v_{i}$ to $u$. Because in both of the above cases, $v_{i}$ always tries to activate $u$, we call $v_{i}$ as a precedent of $u$, for each $(v_{i},u)\in\mathcal{E}^{*}_{t}$. Given the diffusion topology $\mathcal{G}^{*}_{t}=(\mathcal{V},\mathcal{E}^{*}_{t})$ at time $t$, we denote the precedent set of each $v\in\mathcal{V}$ at time $t$ as $\mathcal{P}_{v,t}=\{v_{i}|(v_{i},v)\in\mathcal{E}^{*}_{t}\}$. As we can see, a diffusion topology fully characterizes the cascade structure on the data graph, thus it is suitable for us to use as a data model for diffusion representation learning.

Properties and implications. We conclude two important properties of diffusion topology from Def. 3:

Each diffusion topology is a directed acyclic graph (DAG). This is because the directed edges in a diffusion topology are always from a node activated earlier, to another node which is to be activated later; there is strictly no cycle.

The diffusion topologies for a cascade are monotonically growing over time. This is because the diffusion topology at time $t$ is always a supergraph of that at time $t-1$, due to its introducing new edges.

The two properties of diffusion topology has important implications. Firstly, learning $\mathbf{h}_{t}$ with dynamic diffusion topologies is not trivial, because no prior RNNs are designed for dynamic DAGs. This motivates us to design a novel neural network model. Secondly, $\mathbf{h}_{t}$ can be learned recurrently from the earlier $\mathbf{h}_{i}$’s $(i=1,...,t-1)$, since these $\mathbf{h}_{i}$’s have encoded the diffusion topologies before time $t$, which are essentially subgraphs of the diffusion topology at time $t$.

In all, we propose to use diffusion topologies as our data model to learn the sender embedding. We emphasize that our diffusion topology data model is new. In the existing literature, Embedded-IC’s data model is a set of independent nodes , which are not aware of the data graph structure; DeepCas’s data model is a set of independent paths sampled from the induced subgraph over the active nodes at each time $t$ , and each path alone only partially captures the cascade structure.

III-B Diffusion Topology Embedding

Next we discuss how to learn $v_{t}$’s sender embedding $\mathbf{h}_{t}$ from the diffusion topology $\mathcal{G}^{*}_{t}$ at time $t$ and the earlier activated nodes $Q_{1:t-1}$’s sender embeddings $\{\mathbf{h}_{1},...,\mathbf{h}_{t-1}\}$. As discussed in Sect. III-A, $\mathbf{h}_{t}$ can be learned recurrently from $\{\mathbf{h}_{1},...,\mathbf{h}_{t-1}\}$. This motivates us to extend a Recurrent Neural Network (RNN) framework to develop our embedding model.

LSTM is a popular neural network architecture designed for RNN to address the vanishing/exploding gradient issues . The unit of an LSTM network is the memory cell, which has an input gate, a neuron with a self-recurrent connection, a forget gate, and an output gate. The input gate allows incoming signal to alter the memory cell’s state or block it. The self-recurrent connection balances signals from the previous time step and the current time step. The forget gate modulates the memory cell’s self-recurrent connection, allowing the cell to remember or forget its previous state, as needed. The output gate allows the state of the memory cell to affect other neurons or prevent it. The standard LSTM is designed for sequences, but not DAGs. The recent Tree-LSTM cannot handle DAGs either. The existing RNN models that take DAGs as inputs, such as DAG-RNN and RNN-LE , do not exploit the LSTM architecture. To the best of our knowledge, LSTM has not been used to model DAGs before. Besides, these existing RNN architectures are designed for different application domains and are not applicable to our problem.

We extend standard LSTM to Topo-LSTM for modeling the diffusion topologies, which are DAGs. To assist model development, we use Fig. 1 as a running example. The overall architecture of the Topo-LSTM model is also illustrated in Fig. 2 using the diffusion topology in Fig 1(d) as an example.

Running Example. As in Fig. 1, we are given a cascade sequence $\{(A,1),(B,2),(C,3),(D,4)\}$. At time $t=1$, the diffusion topology is $\mathcal{G}^{*}_{1}=(\mathcal{V},\mathcal{E}^{*}_{1})$ with $\mathcal{E}^{*}_{1}=\emptyset$. Denote $\mathbf{x}_{i}\in\{0,1\}^{|\mathcal{V}|}$ as the feature vector for node $v_{i}$. For example, $\mathbf{x}_{i}$ could be the one-hot ID vector where $\mathbf{x}_{i}$ has 1 on its $i$th entry and all zeros elsewhere. As illustrated in the network slice at $t=1$ in Fig. 2, similar to standard LSTM, we take $A$’s feature vector $\mathbf{x}_{A}$ as input and transform it to a dense vector $\mathbf{h}_{A}$ as output. At $t=2$, as $A$ has been activated, we have $Q_{1:1}=\{A\}$ and $\mathcal{G}^{*}_{2}=(\mathcal{V},\mathcal{E}^{*}_{2})$ with $\mathcal{E}^{*}_{2}=\{(A,B),(A,C),(A,F)\}$, as shown in Fig. 1(a). The precedent set for $B$ is $\mathcal{P}_{B,2}=\{A\}$. To make $\mathbf{h}_{B}$ aware of the cascade structure so far, we infer $\mathbf{h}_{B}$ from both $B$’s feature vector $\mathbf{x}_{B}$ and the possible activation attempt from $\mathcal{P}_{B,2}$. These operations at $t=2$ are illustrated by the network slice at $t=2$ in Fig. 2. At $t=3$, we have $Q_{1:2}=\{A,B\}$ and $\mathcal{G}^{*}_{3}=(\mathcal{V},\mathcal{E}^{*}_{3})$ with $\mathcal{E}^{*}_{3}=\{(A,B),(A,C),(A,F),(B,C),(B,E)\}$, as shown in Fig. 1(b). Given $\mathcal{P}_{C,3}=\{A,B\}$, we infer $\mathbf{h}_{C}$ from $C$’s feature vector $\mathbf{x}_{C}$ and the possible activation attempts from $\mathcal{P}_{C,3}$. The network slice at $t=3$ in Fig. 2 depicts the above operations for $t=3$. At $t=4$, $Q_{1:3}=\{A,B,C\}$ but this time there is no link from $Q_{1:3}$ to $D$ on $\mathcal{G}$. As also shown in the slice at $t=4$ in Fig. 2, there is no incoming edge into Topo-LSTM unit corresponding to $t=4$. Thus $\mathcal{P}_{D,4}=\emptyset$ and $\mathcal{G}^{*}_{4}=(\mathcal{V},\mathcal{E}^{*}_{4})$ with $\mathcal{E}^{*}_{4}=\{(A,B),(A,C),(A,F),(B,C),(B,E),(C,G)\}$, as shown in Fig. 1(c). Then, we infer $\mathbf{h}_{D}$ from $D$’s feature vector $\mathbf{x}_{D}$ and the other already activated nodes $Q_{1:3}\backslash\mathcal{P}_{D,4}=\{A,B,C\}$. Note that in Fig. 2, we neglect the incoming edges from $D$’s non-neighbors into Topo-LSTM unit of $D$, in order to keep the diagram uncluttered.

Formulation of Topo-LSTM. We now formalize the running example to develop the Topo-LSTM model. For a cascade sequence $s=\{(v_{1},1),...,(v_{T},T)\}$, to infer $v_{t}$’s embedding $\mathbf{h}_{t}$, we consider three parts of information: (1) $v_{t}$’s feature vector $\mathbf{x}_{t}$; (2) the possible activation attempts from $v_{t}$’s precedent set $\mathcal{P}_{v_{t},t}$; (3) the other already activated nodes $Q_{1:t-1}\backslash\mathcal{P}_{v_{t},t}$. For (2) and (3), because all the nodes in $Q_{1:t-1}$ already have their embedding inferred by time $t$, we can just use their $\mathbf{h}_{i}$’s (for $i=1,...,t-1$).

Next we introduce Topo-LSTM, which makes two important changes to the standard LSTM to accommodate the dynamic DAG structure.

Different types of inputs: for each node $v_{t}$, there are two types of active nodes that can contribute to learn $v_{t}$’s sender embedding, including: 1) the active nodes that are directly linked with $v_{t}$, denoted as $v_{i}\in\mathcal{P}_{v_{t},t}$; 2) the other active nodes that are not linked with $v_{t}$, denoted as $v_{j}\in(Q_{1:t-1}\backslash\mathcal{P}_{v_{t},t})$. These two different types of active nodes are expected to contribute differently to $v_{t}$’s sender embedding learning, thus we should separate them. Comparatively, in standard LSTM all the cells consider the same type of inputs.

Multiple inputs in each type: for each node $v_{t}$, we have multiple inputs from each type of active nodes, including: 1) the send embedding $\mathbf{h}_{i}$’s for $v_{i}\in\mathcal{P}_{v_{t},t}$; 2) the sender embedding $\mathbf{h}_{j}$’s for $v_{j}\in(Q_{1:t-1}\backslash\mathcal{P}_{v_{t},t})$. Therefore, to compute the contribution of each type of active nodes, we need to aggregate its multiple inputs (either the $\mathbf{h}_{i}$’s or the $\mathbf{h}_{j}$’s). Comparatively, in standard LSTM each cell only takes one input from its precedent node.

To incorporate these two important differences, we change the memory cell design of the standard LSTM. Specifically, we separate the two types of inputs, and for each type of input, we aggregate the corresponding multiple nodes’ embeddings:

: To take the cell states from two different types of inputs, we also define two separate aggregation functions:

III-C Activation Prediction

In practice, there could also exist some node $v$, which becomes activated even though it does not have any edge to the already active nodes in the data graph; e.g., node $D$ in Fig. 1(d). This is possible because that some edges between this node $v$ and those already activated nodes are missing in the data graph. Therefore, to address this issue, we further extend Eq. 12 to include all the potential interactions between $v$ and all the already active nodes in $Q_{1:t}$:

Once we have computed the score for each inactive node $v\in\mathcal{V}\backslash Q_{1:t}$, we can define the probability of activating $v$ by

III-D Objective Function and Algorithm

Our ultimate task is to fit a model $\mathcal{M}$ from the training cascade sequences $\mathcal{S}=\{s_{1},...,s_{n}\}$. Since we have known how to estimate the activation probability for each node in a cascade at every time step, we can now develop the overall objective function for Topo-LSTM. Denote the $k$-th training cascade as $s_{k}=\{(v_{k,1},1),...,(v_{k,T_{k}},T_{k})\}$. We want $\mathcal{M}$ to maximize the activation probability at each time step for $v_{k,t}$ $(t=2,...,T_{k})$. Thus for $s_{k}$, we want to maximize

where $p(v_{k,t}|\mathcal{G}^{*}_{k,t})$, as defined in Eq. 14, relies on the sender embedding computed from Topo-LSTM in Sect. III-B. We denote the parameters for sender embedding as $\Theta^{(emb)}=\{W_{i},U_{i}^{(p)},U_{i}^{(q)},\mathbf{b}_{i},W_{f},U_{fp}^{(p)},U_{fq}^{(p)}$, $U_{fp}^{(q)},U_{fq}^{(q)},\mathbf{b}_{f},W_{c},U_{c}^{(p)},U_{c}^{(q)},\mathbf{b}_{c},W_{o},U_{o}^{(p)},U_{o}^{(q)},\mathbf{b}_{o}\}$, and the parameters for activation prediction as $\Theta^{(act)}=\{\mathbf{g}_{v},b_{v}\mid v\in V\}$. In all, our target model is characterized by $\mathcal{M}=\{\Theta^{(emb)},\Theta^{(act)}\}$. Finally, for all the cascade sequences $\mathcal{S}$, we can define the overall objective function to minimize as

Topo-LSTM Algorithm. We summarize the learning algorithm for Topo-LSTM in Alg. 1. We use stochastic gradient descent (SGD) for optimization. We first initialize the model parameters $\mathcal{M}$. Then for each training cascade sequence $s_{k}$, we iterate through each of its nodes $v_{k,t}$’s to construct a diffusion topology. Specifically, we first extract the active nodes in $s_{k}$ so far by the time $t$ as $Q_{1:t}$ (line 5). After that, we construct the diffusion topology $G^{*}_{k,t}$ from the data graph $\mathcal{G}$ and $Q_{1:t}$ according to Def. 3 (line 6). Based on $G^{*}_{k,t}$, we can compute $\log p(v_{k,t})$ according to Eq. 14, and thus the loss. Finally, we compute gradient of $\mathcal{M}$ as $\nabla_{\mathcal{M}}$ and do gradient descent on $\mathcal{M}$, using for example Adam .

Complexity Analysis. We analyze the running complexity of Alg. 1. Finding $Q_{1:t}$ (line 5) can be done in constant time, since each cascade sequence generally has a limited length. To construct the diffusion topology (line 6), we make use of the monotonically growing property of diffusion topology (as discussed in Sect. III-A) to assist the complexity analysis. In particular, for a cascade sequence $s_{k}$, we can construct its $G^{*}_{k,t}$’s gradually, by adding directed edges based on the data graph $\mathcal{G}$. Thus the number of edges in $G^{*}_{k,T_{k}}$ is smaller than that of $\mathcal{G}$. This means the complexity is at most $|\mathcal{E}|$. It is worth noting that, although we perform the topology construction again and again for each timestep of each training cascade, in fact these $G^{*}_{k,t}$’s only need to be computed once. In SGD (line 11), we need to compute the activation probability $p(v_{k,t})$ and the regularization term of $\mathcal{M}$, both of which require a complexity of $O(|\mathcal{V}|)$. To compute the gradient w.r.t. $p(v_{k,t})$ and $\Omega(\mathcal{M})$, which again require a complexity of $O(|\mathcal{V}|)$. The gradient descent over $\mathcal{M}$ also requires a complexity of $O(|\mathcal{V}|)$. Therefore, we have the overall complexity as $O(|\mathcal{E}|+|\mathcal{V}|\sum_{k=1}^{n}T_{k})$. That is, our algorithm complexity is linear to the data graph size (i.e., $|\mathcal{E}|$ and $|\mathcal{V}|$) and the cascade size (i.e., $\sum_{k=1}^{n}T_{k}$).

IV Experiments

Datasets. We conduct experiments on three public real world datasets. The statistics of the datasets are listed in Table II.

Digg contains diffusions of stories as voted by the users, along with friendship network of the users.

Twitter contains the diffusion of URLs on Twitter during 2010 and the follower graph of users.

Memes contains the diffusion of memes in April 2009 over online news websites; we create a link between two websites if one of them appears earlier than the other in any cascade.

For all these data sets, we randomly sample 75% of all cascades to generate training examples and the rest for testing. We further randomly sample 10% of the training cascades for validation.

Baselines. We select four state-of-the-art and representative baselines for comparison with our Topo-LSTM model. The baselines can be regarded as under two categories: 1) representation learning methods: Embedded-IC, DeepCas, DeepWalk; 2) non-representation learning methods: IC-SB.

IC-SB infers the diffusion probability $p_{u,v}$ of each edge $(u,v)\in\mathcal{E}$ given training cascades, and predicts diffusion under the classical IC framework, with the probability of activating an inactive node $v$ at time $t$ given by $1-\prod_{u\in\mathcal{P}_{v,t}}(1-p_{u,v})$, where $\mathcal{P}_{v,t}$ is defined in Sect. III-A. We use the Static Bernoulli (SB) in their paper which shows the best performance for our problem setting.

Embedded-IC grounds in the IC framework. It embeds nodes in a latent diffusion space learned from the observed cascades. Then the diffusion probabilities between nodes are computed based on their distances in the embedding space.

DeepCas represents a diffusion by some sampled paths from the induced diffusion subgraph. A GRU network with an attention mechanism transforms the these paths into a single vector to represent the diffusion. We replace the diffusion size regressor at the end of their pipeline with a logistic classifier to predict node activations.

DeepWalk represents the simple baseline which computes the embedding of nodes without using the cascade information, and aggregate the embeddings of the active nodes by mean pooling to represent the diffusion. We then use a logistic classifier to predict diffusion.

We choose the hyperparamters for each baseline as follows. For Topo-LSTM and DeepCas, the hidden dimensionality $d$ is set to 512. For DeepCas, we generate 200 walks of length 10 for each cascade, the same setting as in . For Embedded-IC and DeepWalk, we set $d$ to 64 and 128 respectively, which give the best empirical performance on validation sets.

Evaluation metrics. Given the current diffusion, predicting the next active node can be viewed as a retrieval problem due to the large number of potential targets. Specifically, the model ranks the inactive nodes by their predicted activation probabilities, and the actual node to be activated next is the (single) relevant item. We regard predicting future activations as a retrival task and use ranking measures due to two main considerations: (1) since each unactivated node could possibly be activated next, there are massive potential targets, thus it is usually unrealistic to predict exactly the next node; (2) it is often useful enough to provide a short list of most likely future activations instead the exact single next node. For evaluation, we use two widely adopted ranking metrics (varying $k$ in $\{10,50,100\}$):

Hits@$k$: The rate of the top-$k$ ranked nodes containing the next active node.

MAP@$k$: The classical Mean Average Precision measure.

Comparisons with baselines. We compare Topo-LSTM with the baselines on diffusion prediction. As shown in Table III, the results show an overall trend that the accuracy improves as $k$ increases, as expected since the target is more likely to be included with more candidate nodes retrieved. In comparison with baselines, on the MAP measure, Topo-LSTM improves the best baselines by 20.1% (Twitter, MAP@100) to 56.6% (Digg, MAP@10) relatively across all datasets. On the Hits measure, Topo-LSTM improves the best baselines by 2.7% (Memes, Hits@100) to 42.3% (Digg, Hits@10) relatively on Digg and Memes. It also improves the best baselines by 10.2% relatively for Hits@10 on Twitter. These results shows that with explicit modeling of the dynamic DAG structure, Topo-LSTM can better use the topological information of a diffusion than DeepCas. The results also show that, by learning a dynamic sender embedding, Topo-LSTM can better capture the complex diffusion dynamics and interactions among active nodes, which are important to activation prediction, than Embedded-IC, IC-SB, and DeepWalk, which either learn static representations of active nodes or consider the influence of each active node independently. On the other hand, Embedded-IC shows better performance for Hits@$\{50,100\}$ on Twitter. A possible reason is that Twitter has a small number of training cascades; as Embedded-IC has the least number of parameters (node embeddings in a latent diffusion space), it is more robust against overfitting than other methods. In other cases Embedded-IC performs worse, possibly because its latent diffusion space cannot sufficiently capture the complexity of real world diffusions. We also note that the overall performances of all methods are better on the Memes dataset. We could explain this by the fact that the cascades in Memes are mostly short, thus their structure and dynamics are relatively simple for the model to capture.

Impacts of hyperparameters. We study how the number of hidden dimensions $d$ can affect the performance of Topo-LSTM. As shown in Fig. 3, on Twitter the performance begins to converges at $d$ = 256, possibly due to its small training set, while we could still see steady performance gain on Memes and Digg up to $d$ = 512, indicating that the model has not been saturated; given the large number of observed cascades in Memes and the longer cascade sequences of in Digg, there is room for us to learn with larger models.

Sensitivity to data characteristics. We also evaluate how the length of the given cascade could impact the accruacy of predicting future activations. The results are shown in Fig. 4. On Digg and Memes, we observe the trend that the prediction accuracy generally decreases as the length of the given cascade increases. That is, it is likely that, in general, future activations are harder to predict for larger cascades. This intuitively makes sense, since given a larger number of active nodes, there are also more potential future nodes to be actived, thus more uncertainty. It is also worth noting that similar phenomena is observed for sentence classification , where prediction tasks have better performance on shorter sentences. However, this phenomenon is not observed on Twitter. A possible explanation is that there is higher variation in the propagation paths of tweets, thus future activations for shorter cascades are as well unpredictable as in longer ones.

Running Time. We implement Topo-LSTM using Theano 0.9 and conduct all experiments on a machine with an Intel i7-6800K CPU, 32GB memory, and a GTX 1080 GPU. For all the datasets, it takes less than 10 minutes to generate the training examples and less 3 hours to train the model, with our default experiment setting. The detailed running time are reported in Table IV.

V Conclusion

In this paper, we study the problem of predicting future node activations in information diffusion. We adopt a representation learning approach and propose the novel Topo-LSTM model. Tailored for diffusion prediction, Topo-LSTM extends the standard LSTM architecture and is structured as a dynamic DAG. To better model the dynamics of a diffusion, we propose to use the diffusion topology as our new data model, and explicitly model its dynamic DAG structure using Topo-LSTM. As verified by experiments on real world datasets, TopoLSTM improves the best baselines by relatively 20.1%–56.6% (MAP) across all the data sets. It also improves the best baselines by relatively 2.7%–42.3% (Hits) on both Digg and Memes. Thus, we conclude that our new data model and Topo-LSTM architecture can more effectively capture the diffusion structure as dynamic DAGs.

In the future, we plan to incorporate the content of diffusions and richer node features into our model as additional signals help information diffusion prediction. Besides, we also want to differentiate the importance of each active node in activating a target inactive node, based on how often the active node interacts with the inactive node, when the active node was activated, how long the inactive node has remained unactivated since it was exposed to active neighbors.

Acknowledgment

We thank the support of: National Natural Science Foundation of China (No. 61502418), Research Grant for Human-centered Cyber-physical Systems Programme at Advanced Digital Sciences Center from Singapore A*STAR, and the National Science Foundation Grant No. IIS 16-19302. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the funding agencies.

References