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:
- Parameter Explosion: As the number of nodes grows, the model size balloons.
- 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:
- 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).
- 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).
- 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.
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-flightdataset, 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.
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-lastfmdataset 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