DyTed: Disentangling Temporal Invariance and Fluctuations in Dynamic Graph Representation Learning

Kaike Zhang, Qi Cao, Gaolin Fang, Bingbing Xu, Hongjian Zou, Huawei Shen, Xueqi ChengarXiv 2022 · OpenReview

Introduction

In the real world, graphs are rarely static; social networks, transaction logs, and traffic patterns evolve constantly. Current unsupervised methods for learning dynamic graph representations typically squash all information—both a node's intrinsic, stable characteristics and its temporary, time-dependent preferences—into a single "mixed" vector.

This paper argues that this is a fundamental flaw. Imagine trying to predict a user's annual income (a stable trait) versus their likelihood of buying a coffee in the next hour (a transient preference). A single representation space often fails to capture both effectively, leading to poor explainability, reduced robustness to noise, and sub-optimal performance on downstream tasks. The authors introduce DyTed, a framework designed to separate these two factors without requiring explicit labels during training.

The DyTed Framework

DyTed (disenTangled representation learning for discrete-time Dynamic graphs) is a framework that can be wrapped around almost any existing dynamic graph backbone, such as DySAT or EvolveGCN. Its architecture consists of three main pillars:

  1. Time-invariant Representation Generator: This module identifies stable traits using a temporal-clips contrastive learning task. The core idea is that a node’s fundamental properties should remain consistent across different windows of time. It utilizes Bidirectional Bernoulli Sampling to select cost-effective pairs of time clips for training.
  2. Time-varying Representation Generator: This module captures fluctuations using structural-temporal modeling combined with pretext tasks like link prediction to learn how nodes change between snapshots.
  3. Disentanglement-aware Discriminator: To ensure the two generators do not overlap information, an adversarial learning framework is employed. A discriminator attempts to determine if a pair of representations belongs to the same node, forcing a clean separation by minimizing mutual information.
Conceptual framework of DyTed: Disentangling time-invariant and time-varying factors for improved downstream task performance.

Key Insights and Empirical Results

Performance Gains

DyTed was evaluated on seven datasets, including public benchmarks (UCI, Bitcoin, AS733, HepTh/HepPh) and massive real-world financial datasets from Tencent. The results demonstrate consistent improvements:

  • Node Classification: On Tencent data, DyTed improved Micro-F1 scores for stable traits (e.g., income) by 8.81% and for dynamic traits by 7.51%.
  • Link Prediction: The framework improved AUC by an average of 5.87% across all datasets.
  • Efficiency: Despite the added complexity of disentanglement, the model's computational requirements remain comparable to its backbone models.

Sampling and Robustness

A critical finding is that the choice of time windows matters significantly. The authors discovered that comparing non-overlapping, long-duration clips is the most effective way to learn stable features, whereas overlapping clips are better for learning short-term dynamics.

Impact of sampling strategies (overlapping vs. non-overlapping clips) on loss across UCI and HepTh datasets.

Furthermore, DyTed acts as a powerful regularizer. Because features are pre-sorted into stable and dynamic bins, downstream classifiers require less training data. The model is also remarkably resilient to "graph pollution"; in experiments with up to 50% randomized edges, DyTed’s performance degraded much more slowly than traditional mixed models.

Conclusion

DyTed successfully addresses the limitations of mixed representation learning by explicitly disentangling time-invariant and time-varying factors. While currently optimized for discrete-time snapshots, future work aims to extend this framework to continuous-time streaming data and explore its potential for solving "cold-start" problems in dynamic networks.

Summary updated

BibTeX
@misc{zhang2022dyted,
  author = {Kaike Zhang and Qi Cao and Gaolin Fang and Bingbing Xu and Hongjian Zou and Huawei Shen and Xueqi Cheng},
  title = {{DyTed: Disentangling Temporal Invariance and Fluctuations in Dynamic Graph Representation Learning}},
  year = {2022},
  url = {https://openreview.net/forum?id=-9clQuvCZ0x},
}
Figure