FTM: A Frame-Level Timeline Modeling Method for Temporal Graph Representation Learning

Bowen Cao, Qichen Ye, Weiyuan Xu, Yuexian Zou

Abstract: Learning representations for graph-structured data is essential for graph analytical tasks. While remarkable progress has been made on static graphs, researches on temporal graphs are still in its beginning stage. The bottleneck of the temporal graph representation learning approach is the neighborhood aggregation strategy, based on which graph attributes share and gather information explicitly. Existing neighborhood aggregation strategies fail to capture either the short-term features or the long-term features of temporal graph attributes, leading to unsatisfactory model performance and even poor robustness and domain generality of the representation learning method. To address this problem, we propose a Frame-level Timeline Modeling (FTM) method that helps to capture both short-term and long-term features and thus learns more informative representations on temporal graphs. In particular, we present a novel link-based framing technique to preserve the short-term features and then incorporate a timeline aggregator module to capture the intrinsic dynamics of graph evolution as long-term features. Our method can be easily assembled with most temporal GNNs. Extensive experiments on common datasets show that our method brings great improvements to the capability, robustness, and domain generality of backbone methods in downstream tasks.

Introduction

Representing data that changes over time—such as social network interactions, political event logs, or shopping behaviors—is a frontier in graph machine learning. While static graphs are well-understood, temporal graphs introduce a "temporal-structure inconsistency": a node’s neighbor today might not have been a neighbor yesterday and might disappear tomorrow. Predicting future states requires understanding these underlying dynamics.

An example of temporal graph modeling: predicting future behavior based on past dynamics across multiple days.

The Bottleneck in Temporal Modeling

Most existing temporal graph models fall into two primary categories: snapshot-based (slicing the timeline into discrete chunks) or random walk-based (sampling paths through time). Both approaches have significant flaws. Snapshots often treat each chunk as a static graph, losing the fine-grained "short-term" order of events within that chunk. Random walks, while flexible, are stochastic and often struggle to balance immediate interactions with long-term trends, leading to representations that are either too focused on the most recent event or too diluted by the distant past.

The core bottleneck lies in the neighborhood aggregation strategy. To create truly informative embeddings, a model must explicitly capture the intrinsic dynamics of how a node's neighborhood evolves over time.

The FTM Method

FTM (Frame-level Timeline Modeling) is a plug-and-play enhancement for temporal Graph Neural Networks (GNNs) that uses a signal-processing-inspired "framing" technique to organize graph interactions. It introduces a two-stage architecture that can be wrapped around almost any existing temporal GNN (like TGAT or TGN).

  1. Link-based Framing Technique: Borrowing from signal processing, FTM decomposes a node's history into overlapping "frames." Instead of slicing by fixed time intervals—which can be sparse or crowded depending on activity—it slices by a fixed number of links ($k$). This ensures each frame has a consistent density of information.
  2. Stage 1: Frame Aggregator: Each frame is processed in parallel by a backbone GNN. This stage extracts short-term features from the local neighborhood within that specific window of time.
  3. Stage 2: Timeline Aggregator: The representations from successive frames are fed into a "Timeline Aggregator" (such as an LSTM or Self-Attention module). This stage learns the "intrinsic dynamics"—how the node's representation changes from one frame to the next—capturing long-term evolution.
Comparison of neighborhood construction strategies: Snap-shot vs. Random Walk vs. FTM's link-based framing approach.

Key Insights and Results

FTM was evaluated across seven diverse datasets, including Reddit, Wikipedia, and Bitcoin trust networks. The experiments yielded several key insights:

  • Performance and Stability: FTM consistently outperformed baseline models. On the Wikipedia dataset, adding FTM to TGN achieved a state-of-the-art Average Precision (AP) of 98.82%. Furthermore, FTM produces more stable embeddings over time compared to snapshot methods, indicating it has learned the underlying behavioral patterns of nodes.
  • Robustness to Noise: In adversarial tests where Gaussian noise was added to link features, FTM-enabled models showed remarkable resilience. While baselines saw performance craters, FTM maintained high accuracy, providing an average gain of ~18% in AUC under high-intensity noise. The framing technique effectively "scrubs" irregular links or outliers.
  • Domain Generality: FTM significantly improves a model's ability to generalize across different domains. A model trained on Reddit and tested on political event data (Icews14) saw an AP jump from 46.89% to 82.21% just by adding FTM. This suggests the method helps models learn how graphs evolve generally, rather than just memorizing specific dataset patterns.

Conclusion

FTM addresses the limitations of existing temporal graph representation learning by capturing both short-term local features and long-term evolutionary dynamics. While the method requires hyperparameter tuning for frame length and introduces some computational overhead due to parallel frame processing, its improvements in robustness and domain generality make it a powerful tool for modeling complex, time-varying graph data.

Summary updated

Abstract

Learning representations for graph-structured data is essential for graph analytical tasks. While remarkable progress has been made on static graphs, researches on temporal graphs are still in its beginning stage. The bottleneck of the temporal graph representation learning approach is the neighborhood aggregation strategy, based on which graph attributes share and gather information explicitly. Existing neighborhood aggregation strategies fail to capture either the short-term features or the long-term features of temporal graph attributes, leading to unsatisfactory model performance and even poor robustness and domain generality of the representation learning method. To address this problem, we propose a Frame-level Timeline Modeling (FTM) method that helps to capture both short-term and long-term features and thus learns more informative representations on temporal graphs. In particular, we present a novel link-based framing technique to preserve the short-term features and then incorporate a timeline aggregator module to capture the intrinsic dynamics of graph evolution as long-term features. Our method can be easily assembled with most temporal GNNs. Extensive experiments on common datasets show that our method brings great improvements to the capability, robustness, and domain generality of backbone methods in downstream tasks. Our code can be found at https://github.com/yeeeqichen/FTM.
BibTeX
@inproceedings{cao2023ftm,
  author = {Bowen Cao and Qichen Ye and Weiyuan Xu and Yuexian Zou},
  title = {{FTM: A Frame-Level Timeline Modeling Method for Temporal Graph Representation Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=cCXvZstNuJ},
}
Figure