Temporal link prediction is critical for understand- ing dynamic interactions in evolving networks, informing appli- cations ranging from social network analysis to recommendation systems. Existing methods typically rely on raw temporal graph data, often neglecting explicit edge-change information that can significantly improve predictive performance. To address this gap, we propose edge-gradient reinforced learning (EG-RL), a framework that explicitly encodes edge-gradient events (edge births and deaths) through dedicated node and link encoding modules. EG-RL uses a policy-driven reinforcement-learning mechanism to dynamically select and augment the most infor- mative edge snapshots, guided by critic-based feedback to opti- mize prediction accuracy. The model comprises distinct modules for node encoding, link encoding, token mixing, and channel mixing, integrated through global pooling and followed by a two-layer multilayer perceptron classifier. Extensive experiments on multiple dynamic graph datasets demonstrate substantial gains in area under the receiver operating characteristic curve and average precision. Ablation studies further confirm the necessity of adaptive edge-gradient augmentation and validate the effectiveness of the proposed encoding and reinforcement- learning mechanisms.
Figures & tables
Fig. 1 : Illustration of Edge-Gradient Augmentation. (a) Original temporal graph snapshots with binary edges at times t1,…,tn . (b) Constructed edge-weight profiles between observed transition endpoints. These are modelling signals, not measurements of latent relationship strength; both endpoints must be available before a prediction uses the profile.
Fig. 2 : Overview of the EG-RL architecture. The original temporal graph (top-left) is first converted into an edge-gradient–augmented sequence (bottom-left) that exposes the pace of interaction changes. Every snapshot is fed to a node encoder (static features + identity) and a link encoder (time encoding + 1-layer MLP with mean pooling). The resulting tokens are concatenated and channel-flagged ( αj ), then processed by a stack of Graph-Mixer blocks that alternate token-mix and channel-mix MLPs under pre-layer normalisation. A global mean pool followed by a two-layer MLP produces the link-existence logit yi . A reinforcement module observes graph embeddings and adaptively retains or discards augmented snapshots; its reward signal is fed back ( Update ) to refine the augmentation loop.
Dataset
Domain
#Nodes
#Links
#N&L Feat
Bipartite
Duration
Time Granularity
Wikipedia
Social
9,227
157,474
– & 172
True
1 month
Unix timestamps
Reddit
Social
10,984
672,447
– & 172
True
1 month
Unix timestamps
MOOC
Interaction
7,144
411,749
– & 4
True
17 months
Unix timestamps
LastFM
Interaction
1,980
1,293,103
– & –
True
1 month
Unix timestamps
Enron
Social
184
125,235
– & –
False
3 years
Unix timestamps
Social Evo.
Proximity
74
2,099,519
– & 2
False
8 months
Unix timestamps
TABLE I: Statistics of the datasets used in experiments. #N&L Feat denotes the dimensions of node and link features.
Fig. 3 : Comparison of loss landscapes on Wikipedia. Rows show DyGFormer, EG-RL, and TPNet, respectively. Left: 2D contour plots; right: 3D surfaces.
Metric
JODIE
DyRep
TGAT
TGN
CAWN
EdgeBank
TCL
GraphMixer
NAT
PINT
DyGFormer
TPNet
EG-RL
AP (%)
Wikipedia
96.50 ± 0.14
94.86 ± 0.06
96.94 ± 0.06
98.45 ± 0.06
98.76 ± 0.03
90.37 ± 0.00
96.47 ± 0.16
97.25 ± 0.03
98.03 ± 0.07
98.45 ± 0.04
99.03 ± 0.02
99.32 ± 0.03
99.99 ± 0.00
Reddit
98.31 ± 0.14
98.22 ± 0.04
98.52 ± 0.02
98.63 ± 0.06
99.11 ± 0.01
94.86 ± 0.00
97.53 ± 0.02
97.31 ± 0.01
99.13 ± 0.10
99.15 ± 0.02
99.22 ± 0.01
99.27 ± 0.00
99.99 ± 0.00
MOOC
80.23 ± 2.44
81.97 ± 0.49
85.84 ± 0.15
89.15 ± 1.60
80.15 ± 0.25
57.97 ± 0.00
82.38 ± 0.24
82.78 ± 0.15
85.88 ± 0.55
88.08 ± 0.86
87.52 ± 0.49
96.39 ± 0.09
99.99 ± 0.00
LastFM
70.85 ± 2.13
71.92 ± 2.21
73.42 ± 0.21
77.07 ± 3.97
86.99 ± 0.06
79.29 ± 0.00
67.27 ± 2.16
75.61 ± 0.24
88.02 ± 1.94
89.66 ± 1.81
93.00 ± 0.12
94.50 ± 0.08
96.69 ± 0.01
Enron
84.77 ± 0.30
82.38 ± 3.36
71.12 ± 0.97
86.53 ± 1.11
89.56 ± 0.09
83.53 ± 0.00
79.70 ± 0.71
82.25 ± 0.16
90.60 ± 0.66
92.20 ± 0.15
92.47 ± 0.12
92.90 ± 0.17
92.41 ± 0.05
Social Evo.
89.89 ± 0.55
88.87 ± 0.30
93.16 ± 0.17
93.57 ± 0.17
84.96 ± 0.09
74.95 ± 0.00
93.13 ± 0.16
93.37 ± 0.07
88.92 ± 3.45
94.42 ± 0.03
94.73 ± 0.01
94.73 ± 0.02
94.54 ± 0.04
TABLE II: Temporal link prediction on 8 benchmarks. Best result in bold ; runner-up underlined .
Variant
Wikipedia
Reddit
MOOC
LastFM
Enron
Social Evo.
Flights
UCI
AP/AUC
AP/AUC
AP/AUC
AP/AUC
AP/AUC
AP/AUC
AP/AUC
AP/AUC
Full EG-RL
99.99 / 99.99
99.99 / 99.99
99.99 / 99.99
96.69 / 97.71
92.41 / 93.05
94.54 / 95.10
96.63 / 96.81
98.86 / 98.95
w/o RL Selector
98.46 / 98.59
98.91 / 99.05
88.17 / 91.21
93.12 / 93.87
93.42 / 91.08
93.95 / 94.81
75.11 / 96.08
95.82 / 90.11
w/o Gradient
97.25 / 96.92
97.31 / 97.17
82.78 / 84.01
75.61 / 73.53
82.25 / 84.38
93.37 / 95.23
93.25 / 91.81
90.99 / 91.13
Fixed k
98.22 / 98.15
98.44 / 98.71
85.09 / 89.77
92.64 / 93.20
92.14 / 90.31
93.12 / 94.02
73.26 / 95.03
94.17 / 88.60
TABLE III : Ablation results on eight representative datasets (AP/AUC, %).
Figure 7
Reward
Wikipedia
Reddit
MOOC
LastFM
AP
AUC
AP
AUC
AP
AUC
AP
AUC
AUC (default)
99.99
99.99
99.99
99.99
99.99
99.99
96.69
97.71
AP
99.85
99.87
99.93
99.94
99.91
99.93
96.23
97.36
AUC&&AP (joint)
99.84
99.86
99.92
99.94
99.90
99.93
96.13
97.27
Reward
Enron
Social Evo.
UCI
Flights
AP
AUC
AP
AUC
AP
AUC
AP
AUC
TABLE IV : Effect of different reward metrics for the RL selector (Test AP / AUC, %).
Metric
JODIE
DyRep
TGAT
TGN
CAWN
EdgeBank
TCL
GraphMixer
NAT
PINT
DyGFormer
TPNet
EG-RL
AP (%)
Wikipedia
83.01 ± 0.66
79.93 ± 0.56
87.38 ± 0.22
86.86 ± 0.33
71.21 ± 1.67
73.35 ± 0.00
89.05 ± 0.39
90.90 ± 0.10
68.36 ± 4.47
91.33 ± 0.76
82.23 ± 2.54
81.55 ± 4.10
99.86 ± 0.02
Reddit
80.03 ± 0.36
79.83 ± 0.31
79.55 ± 0.20
81.22 ± 0.61
80.82 ± 0.45
73.59 ± 0.00
77.14 ± 0.16
78.44 ± 0.18
80.58 ± 0.91
83.93 ± 1.11
81.57 ± 0.67
81.02 ± 1.31
99.94 ± 0.01
MOOC
78.94 ± 1.25
75.60 ± 1.12
82.19 ± 0.62
87.06 ± 1.93
74.05 ± 0.95
60.71 ± 0.00
77.06 ± 0.41
77.77 ± 0.92
85.42 ± 3.26
84.80 ± 1.57
85.85 ± 0.66
92.69 ± 0.95
99.92 ± 0.03
LastFM
74.35 ± 3.81
74.92 ± 2.46
71.59 ± 0.24
76.87 ± 4.64
69.86 ± 0.43
73.03 ± 0.00
59.30 ± 2.31
72.47 ± 0.49
78.75 ± 1.63
84.95 ± 0.43
81.57 ± 0.48
87.74 ± 0.50
96.98 ± 0.05
Enron
69.85 ± 2.70
71.19 ± 2.76
64.07 ± 1.05
73.91 ± 1.76
64.73 ± 0.36
76.53 ± 0.00
70.66 ± 0.39
77.98 ± 0.92
72.90 ± 1.38
85.41 ± 0.84
75.63 ± 0.73
80.79 ± 1.68
90.27 ± 0.12
Social Evo.
87.44 ± 6.78
93.29 ± 0.43
95.01 ± 0.44
94.45 ± 0.56
85.53 ± 0.38
80.57 ± 0.00
94.74 ± 0.31
94.93 ± 0.31
91.29 ± 4.89
96.73 ± 0.29
97.38 ± 0.14
96.80 ± 0.41
98.53 ± 0.04
TABLE V: Transductive results for historical negative sampling. Best result in bold ; runner-up underlined .
Metric
JODIE
DyRep
TGAT
TGN
CAWN
EdgeBank
TCL
GraphMixer
NAT
PINT
DyGFormer
TPNet
EG-RL
AP (%)
Wikipedia
75.65 ± 0.79
70.21 ± 1.58
87.00 ± 0.16
85.62 ± 0.44
74.06 ± 2.62
80.63 ± 0.00
86.76 ± 0.72
88.59 ± 0.17
53.85 ± 6.25
82.39 ± 2.70
78.29 ± 5.38
79.35 ± 5.52
99.84 ± 0.02
Reddit
86.98 ± 0.16
86.30 ± 0.26
89.59 ± 0.24
88.10 ± 0.24
91.67 ± 0.24
85.48 ± 0.00
87.45 ± 0.29
85.26 ± 0.11
81.71 ± 1.03
87.59 ± 0.65
91.11 ± 0.40
88.19 ± 0.33
99.92 ± 0.01
MOOC
65.23 ± 2.19
61.66 ± 0.95
75.95 ± 0.64
77.50 ± 2.91
73.51 ± 0.94
49.43 ± 0.00
74.65 ± 0.54
74.27 ± 0.92
77.28 ± 1.94
75.70 ± 1.43
81.24 ± 0.69
88.18 ± 0.97
99.90 ± 0.02
LastFM
62.67 ± 4.49
64.41 ± 2.70
71.13 ± 0.17
65.95 ± 5.98
67.48 ± 0.77
75.49 ± 0.00
58.21 ± 0.89
68.12 ± 0.33
64.02 ± 1.48
72.24 ± 0.92
73.97 ± 0.50
77.99 ± 1.30
96.22 ± 0.05
Enron
68.96 ± 0.98
67.79 ± 1.53
63.94 ± 1.36
70.89 ± 2.72
75.15 ± 0.58
73.89 ± 0.00
71.29 ± 0.32
75.01 ± 0.79
70.34 ± 1.73
80.23 ± 1.37
77.41 ± 0.89
75.36 ± 1.81
89.55 ± 0.10
Social Evo.
89.82 ± 4.11
93.28 ± 0.48
94.84 ± 0.44
95.13 ± 0.56
88.32 ± 0.27
83.69 ± 0.00
94.90 ± 0.36
94.72 ± 0.33
92.12 ± 4.53
97.15 ± 0.25
97.68 ± 0.10
97.35 ± 0.32
96.96 ± 0.05
TABLE VI: Transductive results for inductive negative sampling. Best result in bold ; runner-up underlined .
Fig. 6 : Validation-loss dynamics on MOOC with and without edge-gradient augmentation. The complete augmentation includes RL-based selection. The same frozen validation set is evaluated before training and after each epoch. (a) BCE against encoder optimizer updates. (b) The same BCE against actual elapsed time for each run.
Fig. 7 : Case Study: observed edge evolution on MOOC for learner 322 and activity 7056. (a, b) Original binary presence at the actual observation slices. (c) Constructed increasing weights for an observed 0→1 transition. Hollow diamonds are virtual inputs, not recorded interactions. (d) Decreasing weights applied to the existing positive event rows for the subsequent 1→0 transition. The zero endpoint is a profile boundary, not an inserted event. The profiles are complete only at their closing timestamps and usable only for strictly later queries.
Fig. 8 : Candidate-budget sensitivity under the additional held-out protocol. Points show test AP/AUC of validation-selected checkpoints (mean and sample standard deviation, n=3 ). Retention remains learned.
Dynamic graphs are common in real-world systems such as social media, recommender systems, and traffic networks. Existing dynamic graph models for link prediction often fall short in capturing the complexity of temporal evolution. They tend to overlook fine-grained variations in temporal interaction order, struggle with dependencies that span long time horizons, and offer limited capability to model pair-specific relational dynamics. To address these challenges, we propose Graph2Video, a video-inspired framework that views the temporal neighborhood of a target link as a sequence of "graph frames". By stacking temporally ordered subgraph frames into a "graph video", Graph2Video leverages the inductive biases of video foundation models to capture both fine-grained local variations and long-range temporal dynamics. It generates a link-level embedding that serves as a lightweight and plug-and-play link-centric memory unit. This embedding integrates seamlessly into existing dynamic graph encoders, effectively addressing the limitations of prior approaches. Extensive experiments on benchmark datasets show that Graph2Video outperforms state-of-the-art baselines on the link prediction task in most cases. The results highlight the potential of borrowing spatio-temporal modeling techniques from computer vision as a promising and effective approach for advancing dynamic graph learning.
Hua Liu, Yanbin Wei, Fei Xing +3
Southern University of Science and Technology · The Hong Kong University of Science and Technology · City University of Hong Kong +2
Predicting links in sparse, continuously evolving networks is a central challenge in network science. Conventional heuristic methods and deep learning models, including Graph Neural Networks (GNNs), are typically designed for static graphs and thus struggle to capture temporal dependencies. Snapshot-based techniques partially address this issue but often encounter data sparsity and class imbalance, particularly in networks with transient interactions such as telecommunication call detail records (CDRs). Temporal Graph Networks (TGNs) model dynamic graphs by updating node embeddings over time; however, their predictive accuracy under sparse conditions remains limited. In this study, we improve the TGN framework by extracting enclosing subgraphs around candidate links, enabling the model to jointly learn structural and temporal information. Experiments on a sparse CDR, email, message dataset show that our approach increases average precision by at least 2% over standard TGNs, demonstrating the advantages of integrating local topology for robust link prediction in dynamic networks.
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran. · Tehran Institute for Advanced Studies, Khatam University, Tehran, Iran.
Future link prediction on temporal graphs involves both repeated interactions between previously connected node pairs and first-time interactions between pairs with no prior interaction. While repeated-edge prediction can exploit direct pairwise evidence, unseen-edge prediction must generalize beyond historical recurrence. Existing temporal graph models often exploit signals tied to recurring interactions or historical overlap, which are highly informative for repeated edges but become limited or unavailable for unseen edges, contributing to substantial performance degradation on unseen-edge prediction. Based on this observation, we identify two complementary signals for modeling sequential dynamics beyond historical recurrence: (1) historical-sequence evolution, which captures dependencies among the source node's chronologically ordered interactions, and (2) candidate--history compatibility, which captures how well a candidate fits the source node's evolving history. Based on the decomposition, we propose MambaTG, a candidate-aware Mamba-based framework that jointly models these two signals. Mamba provides a natural mechanism for this design: its selective recurrence captures the evolution of ordered interaction histories, while its input-dependent state transitions allow the history state to adapt to different candidate inputs. Extensive experiments on 13 temporal graph datasets against 13 representative baselines show that MambaTG achieves strong and consistent performance across both repeated and unseen edges while remaining computationally efficient.
Nguyen Hong Quan, Sitao Luan, Yilun Zheng +1
Nanyang Technological University, Singapore · University of Montreal · Mila – Quebec Artificial Intelligence Institute