TAMI: Taming Heterogeneity in Temporal Interactions for Temporal Graph Link Prediction

AI summary

Overview

• Research area: Machine learning / graph representation learning, specifically temporal graph neural networks (TGNNs) for continuous-time temporal graphs (CTTGs) and the task of temporal link prediction.
• Technical level: Intermediate. The paper assumes familiarity with graph neural networks, node embeddings, time encoding functions, and link predictors, though the two proposed modules are conceptually simple.
• Scope: The paper identifies heterogeneity (highly skewed interaction intervals) in temporal graph interactions and proposes a two-module framework, LTE and LHA, that can be plugged into existing TGNNs to improve link prediction accuracy and training efficiency.

What This Paper Is About

Temporal link prediction asks whether two nodes will interact at a future time, based on their previous interactions. The authors observe that these interactions are highly uneven: a few node pairs account for most events, and the gaps between events vary enormously (a right-skewed, power-law-like distribution). This unevenness causes two problems for existing models — time encoding functions are hard to train on skewed time differences, and a node's embedding is dominated by its few frequent neighbors, so the history of rarely interacting pairs gets forgotten. TAMI is the authors' framework for handling both problems.

Key Contributions

1. First study of heterogeneity in temporal interactions of CTTGs. The authors identify that interaction intervals and temporal differences are highly right-skewed (e.g., power-law distributed on the UCI dataset, with Fisher's skewness reported as 2.385 for the temporal difference distribution), and investigate its impact on temporal link prediction.

2. TAMI, a framework with two modules. LTE (log time encoding function) rescales temporal differences with a logarithmic transformation, and LHA (link history aggregation) preserves the most recent k interactions for each target node pair so their history is not forgotten. Existing TGNNs can be seamlessly integrated into TAMI.

3. A theoretical result for LTE. Proposition 1 states that if Δt follows a Pareto distribution with shape parameter α > 3, whose skewness is always greater than 2, LTE reduces the skewness to 2. On the UCI dataset, LTE reduces the skewness of Δt from 2.385 to −1.14.

4. Extensive evaluation. Experiments on 13 classic datasets and three newest TGB datasets show consistent improvement in link prediction accuracy and training efficiency, with up to 87.05% improvement in link prediction accuracy and 76.7% reduction in total training time.

Main Findings

• Skewed interactions are the norm: The interaction intervals between any pair of nodes on the UCI dataset follow a power-law distribution with a high positive skewness, and the same right skew appears in the distribution of temporal differences Δt.

• LTE improves most datasets but not all: Replacing the original time encoding with LTE improves GraphMixer and DyGFormer on most datasets (e.g., +2.86% for GraphMixer on CP; +3.34% for DyGFormer on UT), but the paper also reports small negative changes, such as −0.46% for GraphMixer on LA, −0.75% on SE, −0.94% on US, and −0.35% for DyGFormer with LHA on CP.

• Random negative sampling: Under the random negative sampling strategy, both GraphMixer and DyGFormer improve on all 13 datasets, with improvement up to 16.64%.

• Other negative sampling strategies: TAMI improves the integrated models under the historical and inductive negative sampling strategies as well, with improvements up to 38.48% (historical) and up to 54.13% (inductive).

• TGB benchmarks: With TAMI, DyGFormer reaches 0.815 MRR on tgbl-wiki (rank 1, +2.13%), 0.419 on tgbl-review (rank 2, +87.05%), and 0.794 on tgbl-coin (rank 1, +5.59%).

• Robustness to more negative links: On the EN dataset, the improvement ratio for GraphMixer increases from 10.59% to 66.29% as the number of negative links per positive link grows from 1 to 50.

• Architecture adaptivity: TAMI also improves CAWN (random-walk based), TGAT, TGN, and JODIE. For example, TGAT improves by +25.35% on EN and JODIE by +25.33% on LA. Since JODIE does not use a time encoding function, only LHA is applied to it.

• Forgetting of history hurts specific pairs: The paper reports that a non-negligible portion of node pairs have forgotten their mutual interaction history, classified as "Exclusive" (neither node appears in the other's m recent interactions), "Isolated" (only one appears), or "Mutual" (both appear), and those with forgotten history have the worst link prediction accuracy.

• LHA's standalone gain: LHA improves the underlying TGNN by up to 25.33% in link prediction accuracy.

• Faster convergence and lower memory: TGNNs inside TAMI reach higher validation AP with fewer training epochs. DyGFormer in TAMI on the UC and EN datasets needs only 2 and 32 historical interactions for attention computation, respectively, versus the vanilla version using 16× and 8× more. This results in lower GPU memory usage (up to 53.22%) and up to 40.54% reduction in training time per epoch.

• Complexity of LHA: Total space complexity is O(N·d_r) where N is the number of target node pairs and d_r the historical edge embedding dimension; the additional GPU memory overhead is O(b·d_r) for mini-batch size b, since embeddings can be stored in CPU system memory and loaded dynamically.

Methodology in Plain English

The task is defined on a continuous-time temporal graph: a chronologically ordered sequence of interaction events between nodes up to time T. Given two target nodes and a target time τ, the goal is to estimate the probability that they interact at τ, using only events before τ.

Step one — encoding time. Most TGNNs attach a time encoding vector to each historical interaction, computed by taking the difference between the target time and the interaction time (Δt = τ − t) and passing Δt multiplied by learnable frequency parameters through a cosine function. Because Δt is highly right-skewed, these frequency parameters are slow and hard to learn. LTE simply applies a logarithmic transformation, Δt_l = ln(1 + Δt), before the cosine, producing a more balanced input distribution.

Step two — aggregating neighbors. Any existing TGNN computes a node's temporal embedding by aggregating information (node features, edge features, time encodings) from its m most recent neighbors or from random walks. The authors let the choice of aggregation function be whatever the underlying model already uses.

Step three — remembering the pair's own history. LHA stores the most recent k interactions for each target node pair as historical edge embeddings. A new edge embedding is computed as a weighted mix of the current node-pair embedding (an MLP over the two node embeddings) and the previous edge embedding, with the hyperparameter γ ∈ [0,1] controlling the forgetting rate (γ = 1 discards the entire history; for node pairs with no history, the previous edge embedding is set to zero). A "most-recent" aggregator is used, so the link probability is computed by an MLP over the concatenation of the two node embeddings and this history vector.

Evaluation protocol. Twelve/thirteen datasets are split chronologically into 70%/15%/15% for training/validation/testing, and average precision (AP) is the metric. The paper reports transductive results in the main tables and states that inductive results appear in Section D, along with random, historical, and inductive negative sampling strategies (random is the default). Standard deviations over five runs are reported in Table 21.

Why This Matters

Impact on research. The paper reframes skewness in temporal data as a first-class design problem rather than a preprocessing detail, and it shows that a simple log transform has both a theoretical justification (Proposition 1) and empirical benefit. Because LTE and LHA are plug-in modules, the work is complementary to rather than competing with existing TGNN architectures, and the reported gains on the TGB leaderboard give a standardized point of comparison.

Real-world applications:

• Social networks — predicting future connections or interactions among users.
• User-item interaction systems — anticipating a user's next purchase or consumption event.
• Traffic networks — forecasting interactions between entities in dynamic transportation systems.
• Physical systems — modeling dynamic interactions among components over time.

A concrete illustration given in the paper: it is natural to predict that a couple will eat hamburgers if that is one of their recent favorites (frequent interactions), but it makes more sense to predict turkey if Thanksgiving is coming (infrequent interactions).

Industry relevance. Sparse, high-negative-ratio link prediction is the realistic regime for recommendation and social platforms. The paper reports that TAMI's advantage grows as the ratio of negative to positive links increases (up to 66.29% improvement for GraphMixer on EN at NEG=50), and it reduces training time and GPU memory, both of which matter for deployed systems. The code is available at https://github.com/Alleinx/TAMI_temporal_graph.

Future Directions

• Extending LTE beyond the logarithmic transform. The paper uses a fixed log transform; whether other variance-stabilizing transformations or learned rescaling would work better, and how LTE behaves when Δt does not follow a Pareto distribution, are left open (the authors note it "may not strictly follow a Pareto distribution" in practice).
• Choosing k and γ. LHA keeps the most recent k interactions and mixes with weight γ, and the paper uses a most-recent aggregator rather than sum, mean, or attention. The sensitivity of results to these choices, and to alternative aggregators, is not fully characterized in the main text.
• Broadening the set of host architectures. The main experiments integrate GraphMixer and DyGFormer, with CAWN, TGAT, TGN, and JODIE tested for adaptivity. Applying TAMI to other families of temporal models and to tasks beyond link prediction remains to be explored.
• Understanding the cases where TAMI does not help. The ablation reports small negative changes for LTE on some datasets (LA, SE, US for GraphMixer; CP, MO, UT for DyGFormer with LHA), so identifying when each module is likely to hurt is an open question. The paper states that limitations are discussed in Section C.3.

Target Audience

Researchers and practitioners working on temporal graph learning, dynamic network analysis, and link prediction will benefit most, particularly those building or deploying TGNNs on sparse interaction data. The paper is also useful for readers interested in how distributional properties of time (skewness) affect neural network training, and for engineers who need faster-converging, lower-memory temporal models. A background in graph neural networks and basic probability is helpful; the two proposed modules themselves are simple enough to implement without deep mathematical preparation.

Authors’ abstract

Temporal graph link prediction aims to predict future interactions between nodes in a graph based on their historical interactions, which are encoded in node embeddings. We observe that heterogeneity naturally appears in temporal interactions, e.g., a few node pairs can make most interaction events, and interaction events happen at varying intervals. This leads to the problems of ineffective temporal information encoding and forgetting of past interactions for a pair of nodes that interact intermittently for their link prediction. Existing methods, however, do not consider such heterogeneity in their learning process, and thus their learned temporal node embeddings are less effective, especially when predicting the links for infrequently interacting node pairs. To cope with the heterogeneity, we propose a novel framework called TAMI, which contains two effective components, namely log time encoding function (LTE) and link history aggregation (LHA). LTE better encodes the temporal information through transforming interaction intervals into more balanced ones, and LHA prevents the historical interactions for each target node pair from being forgotten. State-of-the-art temporal graph neural networks can be seamlessly and readily integrated into TAMI to improve their effectiveness. Experiment results on 13 classic datasets and three newest temporal graph benchmark (TGB) datasets show that TAMI consistently improves the link prediction performance of the underlying models in both transductive and inductive settings. Our code is available at https://github.com/Alleinx/TAMI_temporal_graph.