Vocabulary-Free Next-Event Prediction on Temporal Graphs

Zhishang Luo, Venu Madhav Tammali, Amila Weerasinghe, Osso Vahabzadeh, Olcay Boz, Xue Hao, Yusu WangarXiv 2026 · arXiv

In the world of Large Language Models (LLMs), the "next-token prediction" objective is king. It has allowed models to scale to trillions of parameters and generalize across virtually any text. But when we try to apply this same logic to temporal graphs—networks where edges appear and change over time (like social interactions, financial transactions, or flight routes)—we hit a major roadblock: The Vocabulary Problem.

In a graph, "tokens" are usually node IDs. If your graph has a billion nodes, your "vocabulary" has a billion entries. This makes models massive, impossible to scale, and prevents them from transferring knowledge from one graph to another.

A new paper, "Vocabulary-Free Next-Event Prediction on Temporal Graphs," proposes a clever way out. The authors introduce GTGT (Generative Temporal Graph Transformer), a framework that ditches global node IDs entirely in favor of a "vocabulary-free" approach that is faster, smaller, and surprisingly transferable.

TL;DR

GTGT is a generative transformer that predicts the next event in a temporal graph without using a fixed node vocabulary. By using local identifiers and behavioral descriptors, it achieves state-of-the-art performance on link prediction tasks while being significantly cheaper to train and capable of zero-shot transfer to unseen graphs.

What Problem Does This Paper Address?

Most current temporal graph models are discriminative. Given a source node and a time, they rank potential destination nodes. While effective for specific tasks, this doesn't help us build "foundation models" for graphs that can forecast future events or generalize across different domains.

The primary challenge is scalability. Standard models use an embedding table for every node ID. This leads to two issues:

  1. Parameter Explosion: As the number of nodes grows, the model size balloons.
  2. Zero Transferability: A model trained on a social network (with its specific user IDs) is useless on a financial network (with different account IDs).

The authors ask: Can we design a scalable, efficient autoregressive framework that works across an arbitrary number of temporal graphs?

Methods

The core innovation of GTGT is how it "tokenizes" a graph event without using a global ID. Instead of saying "Node 123 connected to Node 456," GTGT describes the event using three shared components:

  1. Recency Slots: Instead of a name, the model refers to a node by its history with the source. "The source connected to the node it most recently interacted with" (Slot 1).
  2. Behavioral Descriptors: For nodes not in the recent history, the model predicts a "descriptor"—a quantized summary of the node's activity (e.g., its degree, age in the system, and frequency of interaction).
  3. Local Node Identifiers: To help the Transformer understand the graph's structure within a specific context window, the authors inject random, near-orthonormal unit vectors for each node. These aren't learned; they are sampled fresh for every context, allowing the attention mechanism to "match" occurrences of the same node without knowing who that node is globally.
Figure 1: GTGT predicts the next destination and time gap from event histories. Local identifiers let causal attention match shared endpoints without a learned node vocabulary.

The model is trained autoregressively: given a sequence of past events, it predicts the next destination (slot or descriptor), the time gap until the next event, and the event type.

Datasets

The authors evaluated GTGT on the Temporal Graph Benchmark (TGB), focusing on four diverse datasets:

  • tgbl-wiki: Wikipedia page edits.
  • tgbl-lastfm: User music listening history.
  • tgbl-flight: Commercial flight routes.
  • tgbl-coin: Cryptocurrency transactions.

These datasets vary wildly in size (from 157K to 23M events) and structure (bipartite vs. unipartite), providing a rigorous test for a "one-size-fits-all" model.

Key Insights and Ideas

  • Structure from Randomness: One of the most striking findings is that random identifiers are sufficient for a Transformer to capture graph topology. The authors prove theoretically that this setup can implement "time-respecting message passing," similar to specialized Graph Neural Networks (GNNs).
  • Generative > Discriminative: By training to predict the entire next event (who, when, and what), the model learns a richer representation of the graph's dynamics than models that only perform link ranking.
  • The "Foundation Model" Potential: Because the vocabulary (recency and behavior) is universal, you can train a single model on multiple disjoint graphs. A "joint" model trained on all four datasets performed nearly as well as specialists trained on just one.

Key Results

GTGT doesn't just match the performance of heavyweights like TGN or DyGFormer; it often beats them while being much more efficient.

  • Performance: On the tgbl-flight dataset, GTGT achieved a Mean Reciprocal Rank (MRR) of 0.884, outperforming the previous state-of-the-art.
  • Efficiency: Training GTGT is remarkably fast. For four datasets, GTGT took about 86 minutes to train, compared to 565 minutes for DyGFormer.
  • Zero-Shot Transfer: In a "leave-one-out" experiment, a GTGT model trained on three graphs was tested on a fourth it had never seen. On tgbl-flight, the zero-shot model reached 0.888 MRR, actually outperforming several baselines that were trained on that specific data.
Table 1: Link prediction on TGB (test Mean Reciprocal Rank, or MRR, higher is better). Results for all nine baselines are in Appendix G. Per-corpus uses separate models; joint shares one model. SimpleDyG is our implementation following the original paper. Bold marks the highest MRR. GTGT per-corpus: mean ± std over three seeds; joint: seed 0; budgets and test sets in Appendix F.

Limitations and Future Work

While a major step forward, the authors note a few areas for improvement:

  • Time-Gap Prediction: While GTGT outperforms simple baselines at predicting when the next event will happen, the margin is modest. Predicting exact timing in complex systems remains a "hard" problem.
  • Domain Gaps: Transferring to the tgbl-lastfm dataset was more difficult than others, likely because its user behavior patterns are significantly different from the other datasets.
  • Multi-step Forecasting: The current work focuses on the immediate next event. Extending this to long-term forecasting is the logical next step for a true temporal graph foundation model.

By proving that we don't need global node IDs to learn graph dynamics, GTGT opens the door to a new era of large-scale, cross-domain pretraining for the networks that run our world.

Summary updated

Abstract

Autoregressive transformer training through next-token prediction has driven remarkable advances in language modeling and has become increasingly effective for time-series modeling. Yet its success in temporal graph learning remains limited, and most temporal link-prediction methods are discriminative rather than autoregressive. While temporal graphs can have a natural serialization through chronological ordering edges, they lack an obvious graph-independent tokenization: existing node tokenization often uses a vocabulary that grows with the number of nodes, limiting scalability and cross-graph training. We propose GTGT, Generative Temporal Graph Transformer, a simple yet powerful vocabulary-free framework for self-supervised next-event prediction on temporal graphs. It predicts events for observed destinations, behavioral descriptors for novel destinations, and time gaps before new event. These targets have shared meanings across graphs, allowing one transformer to train across disjoint node sets without node-specific learned parameters. Local node identifiers let attention capture graph structure: Theoretically, we can show that our transformer-based model has the capacity for time-respecting message passing mechanisms. On Temporal Graph Benchmark (TGB), our GTGT not only achieves comparable or better link-prediction performance than established baselines, but also has much lower training cost. These results open the door to temporal graph pretraining for forecasting and other downstream tasks, providing a concrete step toward temporal graph foundation models.
BibTeX
@misc{luo2026vocabulary,
  author = {Zhishang Luo and Venu Madhav Tammali and Amila Weerasinghe and Osso Vahabzadeh and Olcay Boz and Xue Hao and Yusu Wang},
  title = {{Vocabulary-Free Next-Event Prediction on Temporal Graphs}},
  year = {2026},
  eprint = {2611.16063},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.16063},
}
Figure