TG-GAN: Continuous-time Temporal Graph Deep Generative Models with Time-Validity Constraints

Liming Zhang, Liang Zhao, Shan Qin, Dieter Pfoser, Chen Ling

Introduction

Real-world networks, such as human mobility patterns, social interactions, and cyber authentication logs, are inherently dynamic. Unlike static graphs, these temporal graphs have topologies and attributes that evolve continuously over time. Generating realistic synthetic versions of these graphs is crucial for privacy-preserving data sharing and robust system testing. However, existing deep generative models often struggle with the sequential nature of edge formation, the necessity of temporal causality, and the computational trade-offs between time resolution and efficiency.

TG-GAN (Temporal Graph Generative Adversarial Network) addresses these challenges by modeling temporal graphs as a collection of truncated temporal random walks, incorporating strict time-validity constraints and a non-parametric time sampler to achieve high-fidelity generation.

The Challenge of Temporal Graphs

Modeling dynamic networks requires overcoming three primary hurdles:

  1. Chronological Encoding: Capturing the specific order and timing of edge arrivals.
  2. Temporal Validity: Ensuring causality (e.g., a user cannot log out before logging in). Standard models often produce "impossible" sequences.
  3. Efficiency vs. Resolution: Snapshot-based methods are either too coarse to capture fine-grained dynamics or too computationally expensive at high resolutions.
Examples of real-world temporal graphs: human mobility and user authentication logs.

As shown in the figure above, real-world data like public transit trips or server authentication logs are defined by precise timestamps and intervals that must be preserved to maintain the graph's utility.

The TG-GAN Framework

Instead of attempting to generate a massive, time-evolving adjacency matrix, TG-GAN focuses on generating truncated temporal random walks. This approach shifts the complexity from the global graph structure to local, time-respecting sequences.

The TG-GAN architecture, showing the generation of truncated temporal random walks and the recurrent discriminator.

Key Components

  • The Generator: A recurrent architecture (LSTM) that jointly predicts node sequences and "time budgets." By treating the total time span as a depleting resource, the model naturally enforces end-time constraints.
  • Deep Temporal Random Sampler: Rather than assuming a standard distribution (like Gaussian), TG-GAN uses deconvolutional layers to learn a non-parametric distribution of time intervals directly from the training data, allowing it to mimic complex, multi-modal rhythms like commute patterns.
  • Temporal Validity Constraints: To ensure generated timestamps are always non-negative and chronologically ordered, the model employs specialized activation functions and bounding methods, such as Nested ReLU and Minimax Bounding.
  • The Discriminator: A recurrent-based classifier that distinguishes between real temporal walks (extracted via a specialized "temporal jump" sampler) and synthetic ones.

Key Insights and Innovations

  • Walks as Scalable Building Blocks: By decomposing the graph into random walks, TG-GAN achieves linear complexity $O(L_s)$ relative to walk length. This makes it significantly more scalable than snapshot-based methods that scale poorly with time resolution.
  • Time as a Budget: A critical innovation is the "time budget" concept ($t_{0} = t_{end} - t_{start}$). As the generator adds edges, it subtracts from this budget, ensuring the walk stays within the valid temporal window of the dataset.
  • Handling Sparsity: In datasets like the Washington D.C. metro system, where most potential station-to-station connections never occur, TG-GAN's walk-based approach allows it to capture sparse temporal patterns that overwhelm traditional models.

Results and Performance

TG-GAN was evaluated against state-of-the-art baselines like GraphRNN and NetGAN across synthetic scale-free graphs and real-world datasets (User Authentication and Public Transport).

  • Superior Accuracy: In terms of Maximum Mean Discrepancy (MMD) for metrics like Average Degree and Group Size, TG-GAN outperformed baselines by up to two orders of magnitude.
  • Visual and Structural Fidelity: Qualitative analysis shows that TG-GAN successfully mirrors the "arc" patterns of real-world temporal data, avoiding the noisy or overly dense results typical of competing models.
  • Scalability: The model maintained manageable runtimes even as node counts increased to 2,500, demonstrating its readiness for large-scale industrial applications.

Conclusion and Future Work

TG-GAN represents a significant step forward in temporal graph generation by prioritizing continuous-time validity and scalability. While the current model assumes constant edge durations for simplicity, future iterations could extend this framework to model edge duration as a continuous variable and incorporate more complex, high-dimensional edge features, such as data transfer volumes in network logs.

Summary updated

Abstract

Deep generative models of graph-structured data have become popular in very recent years. Although initial research has focused on static graphs in applications such as molecular design and social networks, many challenges involve temporal graphs whose topology and attribute values evolve dynamically over time. Sophisticated and unknown network processes that affect temporal graphs cannot be captured adequately by prescribed models. Application areas include social mobility networks and catastrophic cybersecurity failures. These web-scale applications challenge current deep graph generative models with the need to capture 1) time-validity constraints, 2) time and topological distributions, and 3) joint time and graph encoding and decoding. Here, we propose the “Temporal Graph Generative Adversarial Network” (TG-GAN) for continuous-time graph generation with time-validity constraints 1. TG-GAN can jointly generate the time, node, and edge information for truncated temporal walks via a novel recurrent-based model and a valid time decoder. The generated truncated temporal walks are then assembled into time-budgeted temporal walks for temporal graphs under the learned topological and temporal dependencies. In addition, a discriminator is proposed to combine time and node encoding operations over a recurrent architecture to distinguish generated sequences from real ones sampled by a truncated temporal walk sampler. Extensive experiments on both synthetic and real-world datasets confirm that TG-GAN significantly outperforms five benchmarking methods in terms of efficiency and effectiveness.
BibTeX
@inproceedings{zhang2021tg,
  author = {Liming Zhang and Liang Zhao and Shan Qin and Dieter Pfoser and Chen Ling},
  title = {{TG-GAN: Continuous-time Temporal Graph Deep Generative Models with Time-Validity Constraints}},
  booktitle = {The Web Conference},
  year = {2021},
  doi = {10.1145/3442381.3449818},
}
Figure