PaperlayerView exact revision on arXiv

Source-linked AI summary

Topological Recurrent Neural Network for Diffusion Prediction

Jia Wang, Vincent W. Zheng, Zemin Liu, Kevin Chen-Chuan Chang

arXiv:1711.10162v2cs.LGstat.ML

TL;DR

The paper addresses diffusion prediction when existing deep models underuse cascade structure. It represents cascades as evolving diffusion topologies and models them with Topo-LSTM, which improves state-of-the-art baselines across real-world datasets.

  • Problem

    Diffusion prediction must estimate the next activation probability, but existing deep learning methods often underexplore the cascade’s richer graph structure.

  • Method

    The paper introduces diffusion topologies and uses Topo-LSTM, a recurrent model for dynamic DAGs, to learn topology-aware sender and receiver embeddings.

  • Results

    Topo-LSTM improves the best baselines by 20.1%–56.6% relatively on MAP across all datasets.

  • Takeaways & Limitations

    Explicitly modeling diffusion as a dynamic DAG more effectively captures diffusion structure for activation prediction.

Abstract

from arXiv · show

In this paper, we study the problem of using representation learning to assist information diffusion prediction on graphs. In particular, we aim at estimating the probability of an inactive node to be activated next in a cascade. Despite the success of recent deep learning methods for diffusion, we find that they often underexplore the cascade structure. We consider a cascade as not merely a sequence of nodes ordered by their activation time stamps; instead, it has a richer structure indicating the diffusion process over the data graph. As a result, we introduce a new data model, namely diffusion topologies, to fully describe the cascade structure. We find it challenging to model diffusion topologies, which are dynamic directed acyclic graphs (DAGs), with the existing neural networks. Therefore, we propose a novel topological recurrent neural network, namely Topo-LSTM, for modeling dynamic DAGs. We customize Topo-LSTM for the diffusion prediction task, and show it improves the state-of-the-art baselines, by 20.1%--56.6% (MAP) relatively, across multiple real-world data sets. Our code and data sets are available online at https://github.com/vwz/topolstm.

I. INTRODUCTION

The paper argues that diffusion cascades contain richer graph structure than activation sequences alone and introduces diffusion topologies and Topo-LSTM to model that structure for activation prediction.

  • Problem: Diffusion prediction estimates the activation probability of an inactive node from a data graph and cascade sequences.The inputs are a graph G=(V,E) and node activation sequences ordered by timestamps.
  • Motivation: Deep learning methods often underexplore cascade structure by treating cascades mainly as time-ordered node sequences.The paper represents diffusion as spreading over the underlying data graph, including possible activation attempts.
  • Diffusion topology: A diffusion topology records active and inactive nodes and possible activation attempts at each cascade timestamp.The topology evolves as newly activated nodes create further possible activation attempts.
  • Challenge: Modeling these topologies is challenging because they are dynamic DAGs, while existing recurrent models primarily handle sequences, trees, or static DAGs.The paper states that simplifying the structures into independent nodes or random-walk paths would not fully exploit cascade topology.
  • Approach: Topo-LSTM is a DAG-structured recurrent model that generates topology-aware sender embeddings for active nodes.Receiver embeddings encode inactive nodes’ intrinsic preferences, and activation is predicted from their closeness to active-node sender embeddings.
  • Evaluation: The paper evaluates Topo-LSTM on public real-world datasets and reports significant improvements over state-of-the-art baselines.The contribution list identifies diffusion topology, dynamic-DAG modeling, and node activation prediction as the central components.

II. RELATED WORK

Related work includes diffusion-model learning, sequence- and tree-based recurrent networks, static-DAG RNNs, and graph embedding; Topo-LSTM differs by targeting dynamic diffusion DAGs.

  • Diffusion prediction: Diffusion research includes fixed IC and LT models as well as approaches that learn diffusion models from cascade data.Learned approaches have modeled coverage functions, internal and external influences, and engineered network, temporal, social, content, or interaction features.
  • Recurrent architectures: Standard recurrent models target sequences, while tree-structured recurrent networks model hierarchical structures such as syntactic dependency trees.Examples include LSTM, GRU, DT-RNN, and Tree-LSTM.
  • DAG models: Earlier DAG-RNN and RNN-LE models address static DAGs in domains such as image scene labeling and protein structure prediction.Their inputs and application assumptions differ from information-diffusion graphs.
  • Topo-LSTM distinction: Topo-LSTM is designed for diffusion topologies whose DAGs evolve over time, unlike the static DAGs used by earlier DAG-structured RNNs.It also accommodates real graphs and multiple precedent types required by diffusion prediction.
  • Graph embedding: Graph embedding methods preserve different forms of proximity or represent edges, paths, structures, or whole graphs.The related work spans first-, second-, and high-order proximity, community-aware embeddings, and structure or graph embeddings.

III. DIFFUSION MODELING

The paper formalizes diffusion prediction from graphs and ordered cascades, distinguishes sender and receiver embeddings, and trains a model to estimate future activations.

  • Problem formulation: Diffusion prediction estimates which node to activate next from a cascade of node activations on a data graph.The data graph is G=(V,E), with V as nodes and E as edges.
  • Problem formulation: A cascade sequence is an ordered sequence of distinct node-timestamp tuples with strictly increasing timestamps.The paper denotes such a sequence as s={(v1,t1),...,(vT,tT)}.
  • Assumptions: The basic setting uses a data graph and training cascade sequences but excludes diffusion content and exact activation times.Only the order of nodes in each cascade is used, and content and exact times are left for future work.
  • Embeddings: The model learns sender embeddings for active nodes that encode node identity and the evolving cascade context.Receiver embeddings for inactive nodes encode only their static preferences and are independent of cascade sequences.
  • Training: Diffusion topologies are constructed from previously active nodes so sender embeddings can represent how the cascade spreads to each activated node.The paper uses ground-truth node activations as supervision to train Topo-LSTM.

A. Diffusion Topology as Data Model

Diffusion topologies represent cascades as evolving graph structures rather than activation sequences alone. Each topology is a DAG that captures possible activation attempts and grows monotonically over time, enabling recurrent sender-embedding learning.

  • Properties: The topology at time t is uniquely determined by the active nodes and cascade structure observed up to t.Different timestamps have different active-node sets and cascade structures, yielding one topology for each active node’s prediction time.
  • Definition: A diffusion topology contains directed edges for all possible activation attempts from previously active nodes at a given time.Edges to inactive nodes represent future activation attempts; edges to subsequently activated nodes record preceding activation attempts.
  • Properties: Each diffusion topology is a DAG because edges point from earlier-activated nodes to later-activated nodes, preventing cycles.
  • Implications: Diffusion topologies grow monotonically, so earlier topologies are subgraphs of later ones and earlier embeddings can support recurrent learning.
  • Motivation: The proposed data model captures more cascade structure than independent-node or sampled-path representations.Embedded-IC ignores data-graph structure, while each DeepCas path captures only part of the cascade.

B. Diffusion Topology Embedding

Topo-LSTM extends recurrent modeling to dynamic DAGs by producing topology-aware sender embeddings. It separates direct precedents from other active nodes and aggregates multiple embeddings for each input type.

  • Model: The model extends standard LSTM to dynamic DAGs, a setting not handled by standard or tree-structured LSTMs.
  • Model: Topo-LSTM is a DAG-structured RNN that maps dynamic diffusion topologies to topology-aware node embeddings.For diffusion prediction, it learns a sender embedding for each node activated in a cascade.
  • Inputs: Each sender embedding combines the node’s features, embeddings from precedent nodes, and embeddings from other previously activated nodes.
  • Architecture: Topo-LSTM separates directly linked active nodes from other active nodes because the two input types contribute differently.
  • Architecture: It aggregates multiple embeddings within each input type, unlike standard LSTM cells that receive one input from a precedent node.
  • Architecture: Topo-LSTM adds separate forget gates and aggregation functions for the two active-node input types.The implementation uses mean pooling for aggregation.

C. Activation Prediction

Activation prediction uses sender embeddings from active nodes and receiver embeddings for inactive nodes to score candidate activations. The probability model includes both graph-neighbor and broader potential interactions.

  • Prediction: At each time step, the model predicts an activation probability for every inactive node using sender embeddings and the current diffusion topology.
  • Prediction: The initial prediction assumption is that inactive nodes are activated by active neighbors in the data graph.For example, C may be activated by already active neighbors A and B.
  • Scoring: Receiver embeddings encode inactive nodes’ representations, while node-specific bias parameters contribute to activation scores.
  • Scoring: The model additionally includes potential interactions with all already active nodes to account for activations lacking observed graph edges.Node D exemplifies an activation without a data-graph edge to the active nodes.

D. Objective Function and Algorithm

Topo-LSTM is trained by maximizing the probability of each observed next activation across training cascades, with regularization and stochastic optimization. Its overall complexity is linear in graph size and total cascade size.

  • Objective: The objective maximizes the probability assigned to the observed activated node at every time step of each training cascade.
  • Objective: The model combines sender-embedding and activation-prediction parameters with a regularization term weighted by λ.
  • Algorithm: Training constructs diffusion topologies for each cascade timestep, forms mini-batches, and optimizes the objective with stochastic gradient descent.The algorithm initializes parameters before processing cascades and their time steps.
  • Complexity: The diffusion topology is constructed incrementally by adding directed edges, exploiting its monotonically growing property.
  • Complexity: The overall algorithm complexity is O(|E| + |V| ∑_{k=1}^n T_k), linear in data-graph size and total cascade size.

IV. EXPERIMENTS

Experiments evaluate Topo-LSTM on three real-world diffusion datasets against representation-learning and non-representation-learning baselines. The model improves retrieval-based diffusion prediction, while performance varies with dimensionality and cascade length.

  • Datasets: Experiments use Twitter, Memes, and Digg diffusion datasets, splitting cascades into training, validation, and testing sets.The datasets represent URL, meme, and story diffusion, respectively.
  • Evaluation: The evaluation ranks inactive nodes by predicted activation probability and reports Hits@k and MAP@k for k in {10, 50, 100}.Hits@k measures whether the next active node appears among the top-k results, while MAP@k is mean average precision.
  • Results: Topo-LSTM improves the best baselines by 20.1%–56.6% relatively on MAP across all datasets.The reported range spans Twitter MAP@100 through Digg MAP@10.
  • Results: Topo-LSTM improves the best baselines by 2.7%–42.3% relatively on Hits for Digg and Memes, and by 10.2% on Twitter Hits@10.The comparison includes representation-learning baselines such as DeepCas, DeepWalk, and Embedded-IC, plus IC-SB.
  • Sensitivity: Performance converges near d = 256 on Twitter but continues improving through d = 512 on Memes and Digg.The paper attributes the differing trends to dataset size and cascade-sequence length.
  • Sensitivity: Prediction accuracy generally decreases with cascade length on Digg and Memes, whereas this trend is absent on Twitter.The paper links the Digg and Memes trend to more potential future nodes and uncertainty, and suggests greater propagation-path variation for Twitter.

V. CONCLUSION

The paper proposes Topo-LSTM and diffusion topology modeling for predicting future node activations. Experiments report improvements over baselines, while future work identifies richer diffusion signals and differentiated active-node importance.

  • Contribution: Topo-LSTM is a dynamic-DAG extension of standard LSTM tailored to future node activation prediction.The model explicitly represents diffusion structure as dynamic directed acyclic graphs.
  • Conclusion: Diffusion topologies and Topo-LSTM more effectively capture diffusion structure as dynamic DAGs than the compared baselines.The conclusion reports this claim based on experiments on real-world datasets.
  • Future work: Future work plans to incorporate diffusion content, richer node features, and differentiated active-node importance based on interactions and activation timing.The proposed signals include interaction frequency, activation time, and how long an inactive node remains unactivated after exposure.
Loading 1711.10162v2…