WorksComputer Science
Edge-Gradient Augmentation under Reinforcement Learning for Temporal Graph
Abstract
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.
Introduction
Temporal link prediction forecasts future interactions from time-ordered observations, supporting recommendation, communication analysis, transaction monitoring, and knowledge-graph forecasting [1, 2]. Beyond interaction recency, a predictor must distinguish persistent activity, isolated encounters, and disappearance followed by reappearance. These patterns vary across domains, motivating representations that preserve temporal and structural context without assigning equal relevance to every historical observation.
Existing temporal graph methods model structural evolution through recurrent and snapshot updates [3, 4, 5, 6], temporal attention and event-driven memory [7, 8], and asynchronous propagation and motif-aware walks [9, 10]. Formation and dissolution are also considered in continuous-time temporal knowledge graphs [11]. We investigate a complementary question: can an explicit, interpretable encoding of observed edge transitions provide a useful inductive bias, and can selecting among the resulting augmented observations improve prediction within a simple temporal encoder?
Yongqing Zhou, Jiawei Chen, Wenjun Wang, Xinyu Wang, and Qiyao Peng are with Tianjin University, Tianjin, China (e-mail: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]). Wei Yu is with Zhejiang Yuexiu University, Shaoxing, China (e-mail: [email protected]). Corresponding author: Qiyao Peng.
Pairs with equally recent interactions can have different histories of presence, absence, and reappearance. Edge-Gradient Reinforced Learning (EG-RL) exposes these transitions through constructed edge-weight profiles. Linear interpolation maps a defined transition to an increasing profile and a transition to a decreasing profile (Figure 1). This parameter-free transformation reorganizes historical evidence alongside the original timing information; it adds no new observations.

Figure 1. Illustration of Edge-Gradient Augmentation. (a) Original temporal graph snapshots with binary edges at times . (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.
An edge gradient describes changes in recorded presence, not a measured relationship velocity or latent intensity: a slice without a recorded interaction does not establish that a relationship has ended. Its usefulness may depend on the observation regime. Repeated transitions may provide informative context, whereas interpolation is less well supported for isolated events, irregular coverage, or long gaps. Augmented observations are therefore candidates for selection, not uniformly useful inputs.
EG-RL uses a policy-based selector because retention is discrete, candidate utility depends on the jointly retained observations, and validation AP/AUC are not directly differentiable. The policy observes graph and candidate features within a bounded pool; a clipped relative validation-AUC reward supplies feedback, and a critic baseline aims to reduce policy-gradient variance. Credit is shared statistically across a selection episode, not observed separately for each decision. Attention, learned weighting, differentiable gates, and temporal sampling remain plausible alternatives; RL should therefore be compared with these and random or heuristic selection under matched candidates, encoders, and budgets. Held-out test scores are excluded from rewards and checkpoint selection.
Temporal validity requires both interpolation endpoints and their features to be available before the prediction cutoff; constructing profiles from the complete sequence before splitting would risk leakage. Original event clocks and observation granularity must remain explicit. Strong scores under easy negatives can also obscure weaknesses in temporal reasoning [12]. Chronological evaluation, historical negative sampling, and new-node inductive evaluation thus provide distinct, non-interchangeable evidence.
We use a GraphMixer-based encoder with node/link features, token/channel mixing, pooling, and an MLP predictor [13], keeping the backbone simple enough to examine augmentation and selection separately. Candidate construction, policy/critic evaluation, and validation feedback nonetheless add overhead, motivating assessment of runtime and peak memory alongside predictive gains. Our eight-dataset study includes baseline comparisons and component ablations.
Our main contributions are summarised as follows:
We formulate edge-gradient augmentation as an explicit,
parameter-free representation of defined binary-presence transitions, distinguishing constructed weights from latent relationship intensities and specifying the endpoint-availability condition required for causal prediction.
We combine a bounded, discrete policy-based selector with critic feedback and a GraphMixer backbone, separating candidate construction, candidate retention, and temporal encoding so that their individual roles can be examined.
We study temporal link prediction on eight public datasets with baseline comparisons and component ablations, interpreting the evidence in relation to observation semantics and evaluation protocols. The anonymous code reference is provided to support inspection and reproducibility.
Related Work
Temporal Link Prediction on Dynamic Graphs
CTDNE uses time-respecting walks [14], EvolveGCN recurrently updates GCN parameters [3], and DyRep couples node-state evolution with interaction processes [15]. TGN maintains event-driven memory [8], whereas TGAT uses functional time encodings [7]. Recent directions include community-guided walks [16], topology-aware transformers [17], and joint Euclidean–hyperbolic representations [18]. DyGPrompt uses node–time conditional prompts [19]; TAG combines time-aware edge dropping, recent-neighbor sampling, and contrastive learning [20]. TMetaNet guides adaptation across snapshots using dynamic topological features [21]. EG-RL instead constructs and selects explicit edge-transition augmentation.
Edge-Intensity and Gradient Modelling
Time-decayed line graphs weight interactions by temporal proximity [22]. TANGO models continuous-time knowledge-graph embeddings and explicitly encodes edge formation and dissolution [11]; GN-CDE jointly models node and structural dynamics using neural controlled differential equations [23]. TAMI addresses heterogeneous intervals and intermittent interactions through logarithmic time encoding and link-history aggregation [24]. Thus, prior work does model continuous dynamics and edge changes. EG-RL differs by constructing parameter-free linear weights from defined binary-presence transitions, then learning which augmented observations to retain. These weights are modelling signals, not measured latent interaction intensities.
Dynamic augmentation must preserve temporal consistency. DyAug separates rationale and environment representations and augments the latent environment [25]. Conda generates historical-neighbor embeddings using latent conditional diffusion [26]. EG-RL instead interpolates explicit edge weights and retains candidates with a policy. These approaches motivate separate tests of candidate construction, selection, and temporal validity.
Reinforcement Learning and Lightweight Mixers
Reinforcement learning supports graph explanation [27], and continual learning supports streaming graph updates [28]. EG-RL uses policy–critic feedback for augmentation selection. GraphMixer demonstrates effective MLP-based temporal prediction [13]; graph transformers and token mixers provide other encoder designs [29, 30, 31]. L-STEP combines learnable spatial–temporal positional encoding with an MLP [32], while CRAFT performs target-aware matching [33]. Frequency-domain alternatives include FreeDyG’s interaction-pattern modelling [34] and BandRank’s band-pass disentanglement for candidate ranking [35]. GraphSSM extends state-space modelling to temporal graphs [36], alongside scalable temporal relative positional encodings [37]. EG-RL focuses on augmentation and retention within a lightweight backbone.
Evaluation Protocols and Observation Regimes
TGB-Seq highlights repeated-edge bias and introduces more demanding sequential dynamics [38]; TGB 2.0 extends evaluation to large multi-relational temporal graphs [39]. UTG [40] and TGM [41] bridge event-based and snapshot-based modelling, emphasizing explicit temporal granularity and reproducible pipelines. Our eight-dataset evaluation, however, does not establish performance on these newer benchmark suites or against all recent architectures.
Summary. EG-RL combines explicit transition-based augmentation, reinforcement-guided selection, and a lightweight mixer; its evaluation must distinguish observation semantics from predictive gains.
Problem Definition and Methodology
Dynamic-Graph Notation and Task
We model a temporal graph as an ordered sequence , where is a fixed node set () and is the edge set observed at time . A binary indicator denotes whether edge exists at time . Given the observed history , the temporal link prediction task is to estimate the conditional probability that edge exists at a future time step :
where denotes the predicted probability of future edge existence. In our experiments, we set in Eq. (1). Evaluation follows prior work using Area Under the ROC Curve (AUC) and Average Precision (AP) on a held-out set balanced by time-matched negatives.
a) Observation semantics.: For timestamped event sources, each distinct original timestamp defines one slice . The index orders observations; it is not a physical time unit, and denotes the next supplied slice. Multiple records for the same directed pair within a slice contribute one binary presence. In this representation, absence means no recorded connection within the observed scope, not evidence that a latent relationship has permanently ended. Interpolation is a representation of observed transitions, rather than a measurement of unobserved physical edge dynamics. For prospective use, both transition endpoints and their associated features must already be available before the prediction cutoff; an unobserved endpoint cannot be used to reconstruct the past input of that prediction.
Edge-Gradient Interpolation
Binary snapshots solely record presence or absence, masking how fast interactions strengthen or fade. We explicitly construct edge-intensity curves.
Definition 1 (Edge-gradient). Let be the first and last timestamps of an edge transition ( is analogous). For every we assign
yielding a linear ramp from 0 to 1 (or 1 to 0).
The weights form a tensor that captures change intensity according to Eq. (2). The corresponding procedure is summarized in Algorithm 1.
The interpolation procedure is and parallelisable across edges.
EG-RL Architecture
EG-RL follows the encoder–mixer–classifier paradigm of GraphMixer [13] while extending it along two dimensions: (i) explicit edge-gradient signals III-B; (ii) a reinforcement loop III-D that adaptively selects the most informative edge-gradient snapshots. Figure 2 gives the full pipeline; we detail each component below.

Figure 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 (), 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 . 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.
Algorithm 1: Edge-Gradient Interpolation
Input: snapshots
Output: tensor with intensities
initialise
foreach edge do
identify all birth–death intervals
for to do
if then
else
Fixed time encoding.
Instead of learning a positional encoder, we adopt the cosine lattice used in GraphMixer. For any timestamp and encoding dimension , we define the fixed time encoding as
where and denotes the -th frequency. Following GraphMixer, we use the fixed setting and set throughout. Here, and control how the frequencies decay across dimensions, while determines the size of the time encoding. This parameterization yields a smoothly decaying bank of multi-scale frequencies: lower-index channels vary faster and capture fine-grained temporal differences, whereas higher-index channels vary more slowly and capture coarse temporal patterns. Setting keeps the encoding sufficiently expressive while maintaining modest computational overhead. This fixed encoding has two desirable properties: (i) nearby timestamps yield highly correlated , supporting interpolation; (ii) as grows, , so higher-index channels vary more smoothly and remain distinguishable even for large .
Node & link encoders.
For each node , we construct three components: a raw node feature , a one-hot identity embedding , and the fixed time encoding . When no raw node attributes are available, we use the zero vector for . Since all three components are vectors, they can be concatenated into a single input in and passed to a two-layer MLP:
where the identity embedding provides a lightweight way to distinguish nodes even when raw attributes are weak or unavailable.
For every edge , we analogously combine its interpolated gradient weight , optional raw edge feature , and the same time encoding . If edge attributes are unavailable, we use the zero vector for . Their concatenation therefore lies in and is mapped by a one-layer MLP:
Because nodes participate in variable-length interaction sequences, we zero-pad to a fixed window (recent first) and average over spatial hops:
where padding length also encodes activity frequency: sparsely interacting nodes receive more zeros, a signal absent from attention-based models.
Token/channel mixer.
Stacking GraphMixer blocks, we alternately mix along the token (axis over nodes/edges) and channel (feature) dimensions. For block with input matrix :
where LN is pre-layer normalization and both MLPs use depth-wise linear projections and GELU activations. The residual structure (7)–(8) preserves gradient flow and requires no self-attention, yielding parameter cost per block.
Graph embedding and classifier.
After blocks, we mean-pool the token matrix to obtain a compact graph-level summary . For a candidate link at time , we use the endpoint node representations and from Eq. (4), together with the pair-specific edge representation from Eq. (6). A two-layer MLP with hidden size then outputs the link-existence logit:
Interface to RL selector.
During each RL epoch the selector proposes a set of candidate edge-gradient snapshots. Accepted edges simply enter (6); rejected ones are masked out by setting before the mixer. Because time encoding (3) and padding are differentiable, gradients propagate through the selector’s decisions, enabling policy updates via the critic reward.
Complexity.
Let be the number of edges in the selected snapshot, the feature width, and the mixer depth. Node/edge encoders cost , each mixer block , and RL sampling . The overall is linear in both edges and snapshots.
Reinforcement-Guided Edge-Gradient Selection
Markov decision process (MDP).
Snapshot selection is framed as a Markov decision process, . At step the agent evaluates the next candidate gradient ; state , action and if .
Policy & Critic .
Both share graph embedding of concatenated with an edge embedding of ; each is a two-layer MLP.
Reward.
After an episode we fine-tune the classifier for one epoch with encoder frozen and compute validation AUC. Reward is the relative gain , clipped to . d) Updates.: REINFORCE with baseline:
minimises TD(0); both use Adam. Section III-F introduces a distinct terminal-reward extension; it does not replace this relative-reward, TD(0) formulation.
Training Objective and Complexity
The joint loss
combines supervised BCE, policy gradient loss and regularisation. Forward/backward cost is for the mixer plus for RL sampling—linear in edges and snapshots—making EG-RL more scalable than message-passing temporal GNNs.
Terminal-Reward Training Extension
Algorithm 2 gives the extended training loop. It uses the signed, unnormalized validation AUC difference (not its absolute value) and regresses the critic to the episode’s terminal reward, without TD bootstrapping. This differs from the relative-AUC and TD(0) formulation in Section III-D; the two configurations must be identified separately in comparisons. The reward-metric study varies AUC/AP signals, not these critic objectives.
Experiments
We benchmark EG–RL on 8 public dynamic-graph datasets and compare with 12 established baselines spanning recurrent, attention and mixer families. The main prediction results are averaged over three seeds; numbers are reported as mean s.d.
Datasets
We evaluate on eight widely-used temporal graph benchmark datasets curated by Yu et al. [42], covering diverse domains including social, interaction, transportation, and proximity networks. Specifically, Wikipedia, Reddit, and MOOC are bipartite interaction graphs with edge features; LastFM models user–song listening events; Enron captures email communications; Social Evolution records mobile proximity with low-dimensional link features; UCI is an online communication network; and Flights tracks airport traffic during COVID-19.
Baselines
We compare twelve baselines: JODIE [4], DyRep [15], and TGN [8] for recurrent/event-state modelling; TGAT [7], CAWN [43], TCL [44], and DyGFormer [42] for temporal attention or walk encoding; NAT [45], PINT [46], GraphMixer [13], and TPNet [47] for neighborhood, expressive, mixer, or walk-matrix representations; and the EdgeBank heuristic [12]. Recent methods discussed in Section II are not additional evaluated baselines.
TPNet [47] uses time-decayed temporal-walk matrices and random-feature propagation. EG-RL instead constructs edge-transition weights and learns which causally available augmentation candidates to retain.
These baselines cover a broad spectrum of approaches and represent strong competitors for temporal link prediction.
Algorithm 2: Terminal-Reward EG-RL Training Extension
Input: dynamic graph , epochs , policy , critic
Output: trained parameters
for epoch to do
// Stage 0: edge-gradient interpolation
// Stage I: RL sampling of augmented snapshot
;
foreach candidate edge do
sample
if then
insert with weight into
store in buffer
// Stage II: supervised update (encoder mixer)
compute logits on via (4)–(8)
update encoder & mixer params with Adam on
// Stage III: one-step fine-tune & reward
freeze ; fine-tune classifier 1 epoch on
// Stage IV: policy & critic update (REINFORCE)
foreach do
Experimental Setup and Reproducibility
The main benchmark experiments are implemented in PyTorch 2.0 with PyTorch Geometric 2.3 and torch_scatter. Encoder and mixer parameters are optimized with Adam (learning rate , dropout 0.1, weight decay ), while the policy and critic use separate Adam optimizers with a learning rate of . Temporal edges are time-sorted and processed in mini-batches of 2,000; each positive event is paired with one on-the-fly negative during training and ranked against 100 degree-matched negatives at test time. The RL selector examines at most candidate gradients per snapshot (capped at 512). We report results averaged over three random seeds and release anonymous code and processed datasets at https://anonymous.4open.science/r/EG-RL-671D.
| Dataset | Domain | #Nodes | #Links | #N&L Feat | Bipartite | Duration | Time Granularity |
| Wikipedia | Social | 9,227 | 157,474 | – & 172 | True | 1 month | Unix timestamps |
| 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 |
| UCI | Social | 1,899 | 59,835 | – & – | False | 196 days | Unix timestamps |
| Flights | Transport | 13,169 | 1,927,145 | – & 1 | False | 4 months | days |
Table I. Statistics of the datasets used in experiments. #N&L Feat denotes the dimensions of node and link features.

(a) DyGFormer (2D)

(b) DyGFormer (3D)

(c) EG-RL (2D)

(d) EG-RL (3D)

(e) TPNet (2D)

(f) TPNet (3D)
Figure 3. Comparison of loss landscapes on Wikipedia. Rows show DyGFormer, EG-RL, and TPNet, respectively. Left: 2D contour plots; right: 3D surfaces.
a) Compute resources.: The reported training workstation has an Intel i7-13700K CPU, 32 GB RAM, and one RTX 5090 GPU (32 GB). A Reddit epoch takes approximately 12 seconds with 5.3 GB peak GPU memory. Preliminary tuning and ablations require additional compute.
Main Empirical Results
Table II reports the AP and AUC results of EG-RL and twelve strong baselines on eight temporal-graph benchmarks. Overall, EG-RL achieves the best average rank in both metrics and outperforms competing methods on most datasets.
| 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 |
| 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 |
| UCI | 89.43±1.09 | 65.14±2.30 | 79.63±0.70 | 92.34±1.04 | 95.18±0.06 | 76.20±0.00 | 89.57±1.63 | 93.25±0.57 | 93.40±0.26 | 96.45±0.11 | 95.79±0.17 | 97.35±0.04 | 96.63±0.04 |
| Flights | 95.60±1.73 | 95.29±0.72 | 94.03±0.18 | 97.95±0.14 | 98.51±0.01 | 89.35±0.00 | 91.23±0.02 | 90.99±0.05 | 98.57±0.12 | 98.80±0.02 | 98.91±0.01 | 97.73±0.02 | 98.86±0.03 |
| Avg. Rank | 9.63 | 10.75 | 9.38 | 6.13 | 7.00 | 13.00 | 10.50 | 9.13 | 6.00 | 3.88 | 2.75 | 2.25 | 1.75 |
| AUC (%) | |||||||||||||
| Wikipedia | 96.33±0.07 | 94.37±0.09 | 96.67±0.07 | 98.37±0.07 | 98.54±0.04 | 90.78±0.00 | 95.84±0.18 | 96.92±0.03 | 97.75±0.11 | 98.16±0.06 | 98.91±0.02 | 99.30±0.02 | 99.99±0.00 |
| 98.31±0.05 | 98.17±0.05 | 98.47±0.02 | 98.60±0.06 | 99.01±0.01 | 95.37±0.00 | 97.42±0.02 | 97.17±0.02 | 99.09±0.10 | 99.09±0.03 | 99.15±0.01 | 99.22±0.00 | 99.99±0.00 | |
| MOOC | 83.81±2.09 | 85.03±0.58 | 87.11±0.19 | 91.21±1.15 | 80.38±0.26 | 60.86±0.00 | 83.12±0.18 | 84.01±0.17 | 87.42±0.58 | 90.55±0.43 | 87.91±0.58 | 97.17±0.08 | 99.99±0.00 |
| LastFM | 70.49±1.66 | 71.16±1.89 | 71.59±0.18 | 78.47±2.94 | 85.92±0.10 | 83.77±0.00 | 64.06±1.16 | 73.53±0.12 | 86.92±2.72 | 89.28±1.63 | 93.05±0.10 | 94.39±0.04 | 97.71±0.02 |
| Enron | 87.96±0.52 | 84.89±3.00 | 68.89±1.10 | 88.32±0.99 | 90.45±0.14 | 87.05±0.00 | 75.74±0.72 | 84.38±0.21 | 91.68±0.83 | 92.87±0.34 | 93.33±0.13 | 93.98±0.26 | 93.05±0.05 |
| Social Evo. | 92.05±0.46 | 90.76±0.21 | 94.76±0.16 | 95.39±0.17 | 87.34±0.08 | 81.60±0.00 | 94.84±0.17 | 95.23±0.07 | 90.84±3.72 | 96.16±0.02 | 96.30±0.01 | 96.43±0.02 | 95.10±0.01 |
| UCI | 90.44±0.49 | 68.77±2.34 | 78.53±0.74 | 92.03±1.13 | 93.87±0.08 | 77.30±0.00 | 87.82±1.36 | 91.81±0.67 | 92.31±0.37 | 95.57±0.16 | 94.49±0.20 | 96.79±0.04 | 96.81±0.03 |
| Flights | 96.21±1.42 | 95.95±0.62 | 94.13±0.17 | 98.22±0.13 | 98.45±0.01 | 90.23±0.00 | 91.21±0.02 | 91.13±0.01 | 98.69±0.10 | 98.89±0.02 | 98.93±0.01 | 97.75±0.02 | 98.95±0.05 |
| Avg. Rank | 9.38 | 10.50 | 9.50 | 5.88 | 7.00 | 13.00 | 10.75 | 9.25 | 5.88 | 3.88 | 3.00 | 2.38 | 1.88 |
Table II. Temporal link prediction on 8 benchmarks. Best result in bold; runner-up underlined.
In particular, EG-RL shows especially strong performance on Wikipedia and Reddit, where it achieves the best AP and AUC among all compared methods. It also delivers clear improvements on sparse datasets such as MOOC and UCI, suggesting that edge-gradient augmentation is particularly beneficial when temporal interactions are limited. Even on denser datasets such as Flights, EG-RL remains highly competitive and consistently ranks among the top-performing methods.
The final row of Table II further confirms this trend: EG-RL attains an average rank of 1.75 in AP and 1.88 in AUC, outperforming all baselines overall. These results demonstrate the effectiveness of combining edge-gradient modeling with reinforcement-guided snapshot selection for temporal link prediction.
Ablation Study
To quantify the contribution of each design choice, we compare EG-RL with three simplified variants:
w/o Gradient: remove edge–gradient interpolation and use binary edges.
w/o RL Selector: keep all interpolated edges, i.e., disable the actor–critic module.
Fixed : keep RL but set the candidate window radius to a fixed , removing adaptivity.
Table III reports results on eight representative datasets that differ in scale and domain. All models share identical hyperparameters; we repeat each run with three seeds and report mean ± std.
| Variant | Wikipedia AP/AUC | Reddit AP/AUC | MOOC AP/AUC | LastFM AP/AUC | Enron AP/AUC | Social Evo. AP/AUC | Flights AP/AUC | UCI 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 | 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, %).
a) Findings:
Edge gradients are critical. Removing gradient interpolation reduces AP on Wikipedia from 99.99% to 97.25% (−2.74 percentage points) and on Flights from 96.63% to 93.25% (−3.38 points), confirming that continuous edge-change signals substantially improve prediction.
Adaptive selection matters. Disabling the RL selector drops AP on Wikipedia by 1.53 points (99.99% → 98.46%) and on Flights by 21.52 points (96.63% → 75.11%), indicating that many interpolated edges introduce noise without learned filtering.
Window adaptivity helps. Fixing the candidate window to reduces AP on Wikipedia by 1.77 points and on Flights by 23.37 points, showing that a dynamic selection radius is necessary to handle varying temporal densities. Each panel has its own color scale, so the visual comparison emphasizes local shape rather than absolute loss values across models or datasets.
These findings verify that both components—explicit edge-gradient encoding and adaptive RL-based selection—are indispensable to EG-RL’s state-of-the-art performance.
Loss Landscape Analysis
Figure 3 compares two-parameter-direction loss slices around converged Wikipedia solutions. EG-RL appears smoother than DyGFormer and TPNet within the displayed region; this is a qualitative local observation, not proof of global convexity, better generalization, or causation of prediction gains. Figures 4 and 5 provide 2D and 3D views on six additional datasets, respectively.
On Wikipedia, the nested contours of EG-RL form an elongated basin with a comparatively regular progression from its interior toward the boundary. The corresponding 3D view makes this gradual change in height visible along both plotted directions. In contrast, DyGFormer’s contours show several pronounced bends, and its surface contains alternating ridges and valleys. TPNet exhibits a broad central region together with sharper variation near parts of the boundary.
The additional datasets reveal different local geometries. Social Evolution has approximately elliptical contours and a broad basin, whereas LastFM and Reddit show stronger directional slopes. MOOC and UCI contain more localized undulations, and Enron combines a sloping region with changes in curvature. Thus, the cross-dataset plots do not simply reproduce the Wikipedia pattern: they show how the fitted objective varies with the underlying interaction data.
Reward Metric Study for the RL Selector
a) Motivation.: In EG-RL, the snapshot selector is optimized by a scalar reward computed after each RL episode. The original implementation uses the validation AUC gain as the reward signal. However, temporal link prediction is commonly reported with both AUC and Average Precision (AP). To examine the sensitivity of the selector to the choice of reward metric, we additionally evaluate (i) AP-based reward and (ii) a joint AUC&AP reward.
b) Reward variants.: We keep the RL training pipeline unchanged: after an episode, we freeze the encoder, fine-tune the classifier for one epoch on the augmented graph, and compute the reward on the validation split. The only difference is how the scalar reward is computed. Let denote the original training graph and denote the augmented graph produced by the selector. We define:
where truncates values to the interval .

Figure 4. 2D loss contours of EG-RL on six datasets. Panels (a)–(f): ENRON, LASTFM, MOOC, REDDIT, SOCIALEVO, and UCI. Color bars indicate loss magnitude.

Figure 5. 3D loss surfaces of EG-RL on the same six datasets, ordered as in Fig. 4. Color bars indicate loss magnitude.
c) Results.: tbl:IV reports the per-dataset scores. Overall, validation AUC remains the most reliable reward across datasets. The AP-based reward improves Social Evolution, but generally hurts Enron, UCI, and Flights. The joint AUC&&AP reward acts as a compromise, yet it does not consistently surpass the default AUC reward. These results indicate that validation AUC provides the most stable signal for snapshot selection in EG-RL.
| Reward | Wikipedia AP | Wikipedia AUC | Reddit AP | Reddit AUC | MOOC AP | MOOC AUC | LastFM AP | LastFM 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 AP | Enron AUC | Social Evo. AP | Social Evo. AUC | UCI AP | UCI AUC | Flights AP | Flights AUC |
| AUC (default) | 92.41 | 93.05 | 94.54 | 95.10 | 96.63 | 96.81 | 98.86 | 98.95 |
| AP | 90.98 | 90.15 | 96.98 | 97.30 | 94.88 | 96.15 | 96.72 | 97.55 |
| AUC&&AP (joint) | 90.54 | 90.11 | 96.98 | 97.30 | 94.46 | 96.11 | 96.66 | 97.47 |
Table 4. Effect of different reward metrics for the RL selector (Test AP / AUC, %).
Transductive Results under Alternative Negative Sampling
a) Motivation.: Beyond the random negative sampling protocol used in the main results, we further evaluate EG-RL under two more challenging transductive settings: historical negatives sampled from previously active nodes, and inductive negatives sampled from nodes that are inactive at the prediction time. These protocols change the candidate distribution and therefore test whether the advantage observed with random negatives persists under alternative evaluation conditions. We examine both the average rank across datasets and the margin over the strongest baseline within each dataset. All margins below are expressed in percentage points.
b) Historical negative sampling.: tbl:V shows that EG-RL ranks first on all eight datasets in both AP and AUC, yielding an average rank of 1.00 for each metric. The strongest competing average ranks are 3.62 in AP and 3.25 in AUC, both achieved by PINT. The advantage is particularly large on Flights: EG-RL reaches 97.99% AP and 98.17% AUC, exceeding the strongest baselines by 25.61 and 23.53 points, respectively. On Reddit, its AP of 99.94% and AUC of 99.95% improve over PINT by 16.01 and 16.97 points. LastFM also shows substantial gains of 9.24 points in AP and 13.24 points in AUC over TPNet. The gains are not uniform across datasets. On UCI, for example, the AP margin over PINT is 0.51 points, while the AUC margin is 4.08 points. Reporting both metrics thus reveals differences that a single aggregate score would obscure.
c) Inductive negative sampling.: Table VI gives EG-RL the best average ranks of 1.38 in AP and 1.25 in AUC. It achieves the highest AP and AUC on seven of the eight datasets. On MOOC, EG-RL obtains 99.90% AP and 99.93% AUC, exceeding TPNet by 11.72 and 10.86 points. On LastFM, its AP advantage over TPNet is 18.23 points, while its AUC advantage over EdgeBank is 19.98 points. Flights shows improvements of 16.15 and 16.53 points over EdgeBank. Social Evolution provides a contrasting case: EG-RL reaches 96.96% AP and 97.31% AUC, compared with the best scores of 97.68% and 97.59%. The respective gaps are 0.72 and 0.28 points. The strongest competing average ranks are 4.50 in AP for DyGFormer and 5.38 in AUC for TPNet, indicating a substantial separation in overall ranking across the eight datasets.
| 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 |
| 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 |
| UCI | 65.99±1.40 | 54.79±1.76 | 68.67±0.84 | 70.94±0.71 | 64.61±0.48 | 57.43±0.00 | 76.01±1.11 | 80.10±0.51 | 57.55±0.81 | 83.61±0.23 | 72.25±1.71 | 77.26±1.57 | 94.23±0.08 |
| Flights | 69.07±4.02 | 70.57±1.82 | 75.48±0.26 | 71.09±2.72 | 69.18±1.52 | 81.08±0.00 | 74.62±0.18 | 74.87±0.21 | 59.16±1.48 | 61.99±1.70 | 70.92±1.78 | 64.78±1.50 | 97.23±0.04 |
| Avg. Rank | 10.38 | 10.75 | 6.25 | 6.38 | 8.38 | 8.50 | 7.12 | 6.38 | 10.75 | 5.50 | 4.50 | 4.75 | 1.38 |
| AUC (%) | |||||||||||||
| Wikipedia | 70.96±0.78 | 67.36±0.96 | 81.93±0.22 | 80.97±0.31 | 70.95±0.95 | 81.73±0.00 | 82.19±0.48 | 84.28±0.30 | 52.11±5.83 | 77.03±1.93 | 75.09±3.70 | 75.36±3.41 | 99.86±0.02 |
| 83.51±0.15 | 82.90±0.31 | 87.13±0.20 | 84.56±0.24 | 88.04±0.29 | 85.93±0.00 | 84.67±0.29 | 82.21±0.13 | 76.01±1.04 | 81.02±0.68 | 86.23±0.51 | 81.64±0.42 | 99.94±0.01 | |
| MOOC | 66.63±2.30 | 63.26±1.01 | 73.18±0.33 | 77.44±2.86 | 70.32±1.43 | 48.18±0.00 | 70.36±0.37 | 72.45±0.72 | 75.56±2.39 | 77.00±2.24 | 80.76±0.76 | 89.07±0.63 | 99.93±0.02 |
| LastFM | 61.32±3.49 | 62.15±2.12 | 63.99±0.21 | 65.46±4.27 | 67.92±0.44 | 77.37±0.00 | 46.93±2.59 | 60.22±0.32 | 58.54±2.37 | 69.51±0.61 | 69.25±0.36 | 72.48±0.90 | 97.35±0.04 |
| Enron | 70.92±1.05 | 68.73±1.34 | 60.45±2.12 | 71.34±2.46 | 75.17±0.50 | 75.00±0.00 | 67.64±0.86 | 71.53±0.85 | 69.62±1.12 | 78.91±0.96 | 74.07±0.64 | 75.44±1.38 | 89.42±0.09 |
| Social Evo. | 90.01±3.19 | 93.07±0.38 | 92.94±0.61 | 95.24±0.56 | 89.93±0.15 | 87.88±0.00 | 93.44±0.72 | 94.22±0.32 | 92.53±4.20 | 97.10±0.22 | 97.51±0.06 | 97.59±0.25 | 97.31±0.04 |
| UCI | 64.14±1.26 | 54.25±2.01 | 60.80±1.01 | 64.11±1.04 | 58.06±0.26 | 58.03±0.00 | 70.05±1.86 | 74.59±0.74 | 49.73±1.20 | 79.42±0.31 | 65.96±1.18 | 70.85±0.96 | 95.57±0.05 |
| Flights | 69.99±3.10 | 71.13±1.55 | 73.47±0.18 | 71.63±1.72 | 69.70±0.75 | 81.10±0.00 | 72.54±0.19 | 72.21±0.21 | 59.73±1.61 | 59.61±1.65 | 69.53±1.17 | 64.21±1.30 | 97.63±0.03 |
| Avg. Rank | 9.25 | 10.00 | 7.00 | 6.38 | 8.00 | 7.00 | 7.38 | 6.50 | 11.12 | 6.12 | 5.62 | 5.38 | 1.25 |
Table VI. TABLE VI: Transductive results for inductive negative sampling. Best result in bold; runner-up underlined.
d) Summary.: Across the three reported protocols, EG-RL maintains the best average rank in both AP and AUC: 1.75/1.88 with random negatives, 1.00/1.00 with historical negatives, and 1.38/1.25 with inductive negatives. The strongest baseline also changes across datasets and protocols; for example, the Flights historical results favor TGAT in AP and EdgeBank in AUC, whereas EdgeBank leads the competing methods in both metrics under inductive sampling. EG-RL’s advantage therefore extends across different competitive reference points. These comparisons complement the ablations: interpolation supplies explicit transition cues, and learned retention selects useful augmented inputs.
Learning Dynamics
We compare EG-RL with its complete edge-gradient augmentation, including the RL-based retention mechanism, against an original-graph control trained without augmentation. Both models start from identical parameter initializations and use the same training examples, frozen negative samples, batch size of 600, and 20 complete epochs. These learning curves assess optimization, whereas the following case study examines the representation of observed edge-state changes. The original-graph control samples neighborhoods directly from the original binary history, before top- selection.
Figure 6 reports mean binary cross-entropy (BCE) over all labels of 61,762 fixed validation positives and their paired random negatives. This is a learning-dynamics diagnostic, not a historical-negative test result; no test labels are used. Following the initial loss increase, EG-RL exhibits faster validation-loss reduction. At 3,800 encoder updates, validation BCE is 1.920 with augmentation versus 2.469 without it. After five epochs, the augmented model reaches 2.189 in approximately 39 minutes, whereas the original-graph model records a similar value of 2.194 after 20 epochs and approximately 86 minutes. At epoch 20, validation BCE is 1.547 with augmentation versus 2.194 without it.
Figure 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.
Overall, RL-guided edge-gradient augmentation yields lower validation BCE at all 20 epoch-end evaluations. The reduction is 22.2% at 3,800 updates and 29.5% after 20 epochs (7,600 updates), demonstrating better validation-loss performance at a fixed update budget. Reaching a comparable BCE of approximately 2.19 in 39 rather than 86 minutes further shows that faster loss reduction can offset the augmentation overhead at this observed loss level. Figure 7 complements these empirical findings by showing how augmentation encodes the direction and progress of observed edge-state transitions.
Figure 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.
Case Study
We examine how edge-gradient augmentation represents observed edge evolution, rather than using the case study as another performance comparison. MOOC records time-stamped learner–activity interactions [4]. At each original global timestamp, a pair has state one if an interaction is recorded and zero otherwise. A zero therefore denotes no recorded interaction in that slice, not a verified termination of an underlying relationship.
Figure 7 follows learner 322 and activity 7056. We select the earliest completed appearance–disappearance cycle with a preceding observed interaction and at least two interior observation slices in each transition interval. This source-only rule yields the first of 236 eligible cycles; no prediction score or outcome determines the choice. All timestamps, event rows, and constructed weights are checked against the original event stream and the actual augmentation implementation.
| 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 |
| 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 |
| UCI | 75.24±5.80 | 55.10±3.14 | 68.27±1.37 | 80.43±2.12 | 65.30±0.43 | 65.50±0.00 | 80.25±2.74 | 84.11±1.35 | 75.38±1.28 | 93.96±0.20 | 82.17±0.82 | 86.34±0.80 | 94.47±0.08 |
| Flights | 66.48±2.59 | 67.61±0.99 | 72.38±0.18 | 66.70±1.64 | 64.72±0.97 | 70.53±0.00 | 70.68±0.24 | 71.47±0.26 | 64.74±1.83 | 66.82±1.44 | 66.59±0.49 | 69.10±1.27 | 97.99±0.04 |
| Avg. Rank | 9.12 | 9.38 | 7.88 | 6.12 | 11.38 | 10.00 | 8.38 | 6.25 | 8.50 | 3.62 | 5.25 | 4.12 | 1.00 |
| AUC (%) | |||||||||||||
| Wikipedia | 80.77±0.73 | 77.74±0.33 | 82.87±0.22 | 82.74±0.32 | 67.84±0.64 | 77.27±0.00 | 85.76±0.46 | 87.68±0.17 | 69.32±2.78 | 89.25±0.49 | 78.80±1.95 | 79.89±2.47 | 99.87±0.01 |
| 80.52±0.32 | 80.15±0.18 | 79.33±0.16 | 81.11±0.19 | 80.27±0.30 | 78.58±0.00 | 76.49±0.16 | 77.80±0.12 | 79.36±0.31 | 82.98±0.63 | 80.54±0.29 | 81.87±0.49 | 99.95±0.01 | |
| MOOC | 82.75±0.83 | 81.06±0.94 | 80.81±0.67 | 88.00±1.80 | 71.57±1.07 | 61.90±0.00 | 72.09±0.56 | 76.68±1.40 | 84.93±2.89 | 87.44±1.74 | 87.04±0.35 | 93.45±0.67 | 99.94±0.02 |
| LastFM | 75.22±2.36 | 74.65±1.98 | 64.27±0.26 | 77.97±3.04 | 67.88±0.24 | 78.09±0.00 | 47.24±3.13 | 64.21±0.73 | 75.89±2.21 | 81.89±0.96 | 78.78±0.35 | 84.64±0.45 | 97.88±0.04 |
| Enron | 75.39±2.37 | 74.69±3.55 | 61.85±1.43 | 77.09±2.22 | 65.10±0.34 | 79.59±0.00 | 67.95±0.88 | 75.27±1.14 | 73.22±2.18 | 83.80±0.68 | 76.55±0.52 | 81.16±1.28 | 89.92±0.10 |
| Social Evo. | 90.06±3.15 | 93.12±0.34 | 93.08±0.59 | 94.71±0.53 | 87.43±0.15 | 85.81±0.00 | 93.44±0.68 | 94.39±0.31 | 91.87±4.52 | 96.82±0.24 | 97.28±0.07 | 97.22±0.30 | 98.75±0.03 |
| UCI | 78.64±3.50 | 57.91±3.12 | 58.89±1.57 | 77.25±2.68 | 57.86±0.15 | 69.56±0.00 | 72.25±3.46 | 77.54±2.02 | 71.52±1.61 | 92.05±0.36 | 76.97±0.24 | 80.42±0.64 | 96.13±0.07 |
| Flights | 68.97±1.87 | 69.43±0.90 | 72.20±0.16 | 68.39±0.95 | 66.11±0.71 | 74.64±0.00 | 70.57±0.18 | 70.37±0.23 | 71.11±2.16 | 69.52±0.90 | 68.09±0.43 | 71.82±0.82 | 98.17±0.04 |
| Avg. Rank | 7.38 | 9.00 | 8.88 | 5.62 | 11.50 | 8.62 | 9.00 | 7.75 | 9.38 | 3.25 | 6.12 | 3.50 | 1.00 |
Table V. TABLE V: Transductive results for historical negative sampling. Best result in bold; runner-up underlined.
a) Observed appearance, 0 → 1. After an interaction at 84512 s (source row 4426), the pair is absent from the slice at 84513 s and remains unobserved in the intervening slices until 84532 s, when row 4439 records another interaction. The original representation shows a binary jump (Figure 7(a)). Over this 19-second interval, the constructed profile is . The seven actual interior slice times receive fractional weights; for example, 84514, 84521, and 84526 s receive 0.0526, 0.4211, and 0.6842, respectively (Figure 7(c)). These virtual inputs reuse the feature row of the observed endpoint, 4439. They explicitly encode increasing transition phase but are not additional learner actions.
b) Observed disappearance, 1 → 0. The pair is observed at 84532, 84536, and 84537 s (rows 4439, 4442, and 4445), but not at the next original slice, 84541 s. The binary representation stays at one across those three occupied slices before returning to zero (Figure 7(b)). The completed nine-second profile assigns weights 1, 0.5556, and 0.4444 to these same genuine event rows (Figure 7(d)). Thus, the implementation represents a decreasing phase by reweighting existing observations, without fabricating disappearance events.
c) Relation to learning dynamics. These phase cues offer a possible representation-level explanation for the faster post-initial validation-loss reduction in Figure 6, not proof of optimization speedup. Input-weight differences are not training losses. Efficiency is assessed by updates and measured time to comparable validation loss, including augmentation overhead, rather than by profile smoothness alone.
Candidate Budget Sensitivity
We vary the policy examination cap over 64, 128, 256, and 512 in an independent Enron/UCI study. Chronological splits and historical negatives (with random fallback) are fixed. The 4,206/5,932 test positives involve nodes excluded from positive training, with one negative per positive. Every cap trains for 20 epochs (batch size 600; seeds 0–2), with initial weights and training-negative draws matched within each seed. Uniform training negatives use the full node-ID namespace. We use PyTorch 2.7, causal gradient inputs, one-hot node encodings, and original edge features. Encoder Adam uses learning rate and weight decay ; actor and critic use . Rewards are clipped relative validation-AUC gains from epoch one. Caps apply per batch during training, validation, and testing; unexamined candidates retain constructed weights and recent neighborhoods remain fixed. Validation AP selects matching encoder/policy checkpoints before one test pass. AP/AUC equally weight frozen 200-link batches, including the final partial batch.
Figure 8 shows modest budget sensitivity. Enron mean AP/AUC span 72.77%–72.96% and 68.33%–68.81%, while UCI spans 81.77%–81.9% and 77.20–77.46%. Enron peaks at , whereas UCI peaks at (81.97±0.34% AP; 77.46±0.16% AUC). Increasing the cap thus yields dataset-dependent returns. Moderate caps achieve comparable observed scores with fewer candidate examinations; the preferred budget should be selected on validation data.
Figure 8. Candidate-budget sensitivity under the additional held-out protocol. Points show test AP/AUC of validation-selected checkpoints (mean and sample standard deviation, ). Retention remains learned.
Conclusion
We present EG-RL, a temporal link-prediction framework that enriches binary edge observations with linearly interpolated gradients and uses an actor–critic module to select informative snapshots. A token–channel Mixer encoder yields competitive AUC and average precision, while the original ablations examine the roles of interpolation and adaptive selection. Local loss-landscape views provide qualitative optimization evidence, not proof of global convexity or generalization. The evaluation on eight benchmarks yields the best average AP and AUC ranks across the reported protocols. Historical and inductive negative-sampling results further demonstrate effectiveness with challenging candidate sets. Ablations confirm the contributions of interpolation and adaptive selection. On MOOC, the matched comparison achieves a 29.5% reduction in final validation BCE at the same update budget and reaches a comparable loss earlier. The edge-evolution case study illustrates how increasing and decreasing weights encode observed appearance and disappearance phases. Together, these findings highlight the value of combining explicit temporal transition cues with learned retention in a lightweight encoder. Future work will investigate more flexible interpolation profiles and lower-cost selection strategies, and evaluate larger temporal graphs with different event densities and observation granularities.
References
References
- [1]S. M. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, P. Forsyth, and S. Poupart, “Representation learning for dynamic graphs: A survey,” Journal of Machine Learning Research, vol. 21, pp. 70:1–70:73, 2020.
- [2]Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A comprehensive survey on graph neural networks,” IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 1, pp. 4–24, 2021.DOI
- [3]A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi, T. Kaler, T. Schardl, and C. Leiserson, “Evolvegcn: Evolving graph convolutional networks for dynamic graphs,” in Proceedings of the AAAI conference on artificial intelligence, vol. 34, no. 04, 2020, pp. 5363–5370.arxiv.org/abs/1902.10191
- [4]S. Kumar, X. Zhang, and J. Leskovec, “Predicting dynamic embedding trajectory in temporal interaction networks,” in Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2019, pp. 1269–1278.DOI
- [5]A. Sankar, Y. Wu, L. Gou, W. Zhang, and H. Yang, “Dysat: Deep neural representation learning on dynamic graphs via self-attention networks,” in Proceedings of the 13th international conference on web search and data mining, 2020, pp. 519–527.
- [6]J. You, T. Du, and J. Leskovec, “Roland: graph learning framework for dynamic graphs,” in Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, 2022, pp. 2358–2366.arxiv.org/abs/2208.07239
- [7]D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan, “Inductive representation learning on temporal graphs,” in International Conference on Learning Representations, 2020.arxiv.org/abs/2002.07962
- [8]E. Rossi, B. Chamberlain, F. Frasca, D. Eynard, F. Monti, and M. Bronstein, “Temporal graph networks for deep learning on dynamic graphs,” arXiv preprint arXiv:2006.10637, 2020.arxiv.org/abs/2006.10637
- [9]X. Wang, D. Lyu, M. Li, Y. Xia, Q. Yang, X. Wang, X. Wang, P. Cui, Y. Yang, B. Sun et al., “Apan: Asynchronous propagation attention network for real-time temporal graph embedding,” in Proceedings of the 2021 international conference on management of data, 2021, pp. 2628–2638.DOI
- [10]M. Jin, Y.-F. Li, and S. Pan, “Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs,” Advances in Neural Information Processing Systems, vol. 35, pp. 19 874–19 886, 2022.DOI
- [11]Z. Han, Z. Ding, Y. Ma, Y. Gu, and V. Tresp, “Learning neural ordinary equations for forecasting future links on temporal knowledge graphs,” in Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2021, pp. 8352–8364.
- [12]F. Poursafaei, S. Huang, K. Perline, and R. Rabbany, “Towards better evaluation for dynamic link prediction,” Advances in Neural Information Processing Systems, vol. 35, pp. 32 928–32 941, 2022.
- [13]W. Cong, S. Zhang, J. Kang, B. Yuan, H. Wu, X. Zhou, H. Tong, and M. Mahdavi, “Do we really need complicated model architectures for temporal networks?” in International Conference on Learning Representations. ICLR, 2023, pp. 1–15.arxiv.org/abs/2302.11636
- [14]G. H. Nguyen, J. B. Lee, R. A. Rossi, N. K. Ahmed, E. Koh, and S. Kim, “Continuous-time dynamic network embeddings,” in Companion proceedings of the web conference 2018, 2018, pp. 969–976.DOI
- [15]R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha, “Dyrep: Learning representations over dynamic graphs,” in International conference on learning representations, 2019.
- [16]H. Yu and J. Liu, “Community-enhanced temporal walks: Debiasing locality representation learning on continuous-time dynamic graphs,” IEEE Transactions on Cybernetics, vol. 56, no. 3, pp. 1216–1229, 2026.DOI
- [17]X. Zhang, F. Cai, J. Zheng, P. Wen, H. Chen, and C. Chen, “Triangle matters! TopDyG: Topology-aware transformer for link prediction on dynamic graphs,” in Proceedings of the ACM Web Conference 2025, 2025, pp. 3607–3617.DOI
- [18]Y. Sun, X. Cao, I. Tsang, and H. T. Shen, “Analytical construction on geometric architectures: Transitioning from static to temporal link prediction,” in Proceedings of the 42nd International Conference on Machine Learning, vol. 267. PMLR, 2025, pp. 57 336–57 354.
- [19]X. Yu, Z. Liu, X. Zhang, and Y. Fang, “Node-time conditional prompt learning in dynamic graphs,” in International Conference on Learning Representations, 2025.
- [20]Z. Pan, H. Chen, W. Chen, F. Cai, and X. Liu, “Time-aware graph learning for link prediction on temporal networks,” IEEE Transactions on Neural Networks and Learning Systems, vol. 36, no. 6, pp. 10 619–10 634, 2025.DOI
- [21]H. Li, H. Wan, Y. Chen, D. Ye, Y. Ge, and H. Jiang, “TemmatNet: Topological meta-learning framework for dynamic link prediction,” in Proceedings of the 42nd International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 267. PMLR, 2025, pp. 35 977–35 999.arxiv.org/abs/2506.00453
- [22]S. Qian, R. A. Rossi, S. Kim, T. Yu, J. Hoffswell, N. Lipka, S. Guo, and C. Musco, “Direct embedding of temporal network edges via time-decayed line graphs,” in International Conference on Learning Representations, 2023. [Online]. Available: https://openreview.net/forum?id=Qamz7Q_Talk
- [23]T. Qin, B. Walker, T. Lyons, H. Yan, and H. Li, “Learning dynamic graph embeddings with neural controlled differential equations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 48, no. 2, pp. 2096–2103, 2026.DOI
- [24]Z. Yu, J. Wu, Z. Wu, S. Zhong, W. Su, C.-H. Lee, and W. Zhuo, “TAMI: Taming heterogeneity in temporal interactions for temporal graph link prediction,” in Advances in Neural Information Processing Systems, vol. 38, 2025.
- [25]G. Zhang, Y. Qi, Z. Cheng, Y. Yue, D. Cheng, and J. Guo, “Rationalizing and augmenting dynamic graph neural networks,” in International Conference on Learning Representations, 2025.
- [26]Y. Tian, A. Jiang, Q. Huang, J. Guo, and Y. Qi, “Latent diffusion-based data augmentation for continuous-time dynamic graph model,” in Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 2024, pp. 2900–2911.
- [27]C. Shan, Y. Shen, Y. Zhang, X. Li, and D. Li, “Reinforcement learning enhanced explainer for graph neural networks,” Advances in Neural Information Processing Systems, vol. 34, pp. 22 523–22 533, 2021.
- [28]J. Wang, G. Song, Y. Wu, and L. Wang, “Streaming graph neural networks via continual learning,” in Proceedings of the 29th ACM international conference on information & knowledge management, 2020, pp. 1515–1524.DOI
- [29]M. S. Hussain, M. J. Zaki, and D. Subramanian, “Global self-attention as a replacement for graph convolution,” in Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’22), 2022, pp. 655–665.DOI
- [30]G. Mialon, D. Chen, M. Selosse, and J. Mairal, “Graphit: Encoding graph structure in transformers,” arXiv preprint arXiv:2106.05667, 2021.arxiv.org/abs/2106.05667
- [31]X. He, B. Hooi, T. Laurent, A. Perold, Y. LeCun, and X. Bresson, “A robust generalization of vit/mlp-mixer to graphs,” in International conference on machine learning. PMLR, 2023, pp. 12 724–12 745.
- [32]K. Tieu, D. Fu, Z. Li, R. Maciejewski, and J. He, “Learnable spatial-temporal positional encoding for link prediction,” in Proceedings of the 42nd International Conference on Machine Learning, vol. 267. PMLR, 2025, pp. 59 570–59 597.arxiv.org/abs/2506.08309
- [33]L. Yi, R. Lei, F. Mo, Y. Zheng, Z. Wei, and Y. Ye, “Future link prediction without memory or aggregation,” in Advances in Neural Information Processing Systems, vol. 38, 2025.
- [34]Y. Tian, Y. Qi, and F. Guo, “FreeDyG: Frequency enhanced continuous-time dynamic graph model for link prediction,” in International Conference on Learning Representations, 2024.
- [35]Y. Li, Y. Xu, X. Lin, W. Zhang, and Y. Zhang, “Ranking on dynamic graphs: An effective and robust band-pass disentangled approach,” in Proceedings of the ACM on Web Conference 2025. ACM, 2025, pp. 3918–3929.DOI
- [36]J. Li, R. Wu, X. Jin, B. Ma, L. Chen, and Z. Zheng, “State space models on temporal graphs: A first-principles study,” in Advances in Neural Information Processing Systems, vol. 37, 2024, pp. 127 030–127 058.arxiv.org/abs/2406.00943
- [37]K. Cheng, L. Peng, P. Wang, H. Chang, J. Ye, and B. Du, “On the scalability of temporal relative positional encoding for dynamic link prediction,” in Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, 2025, pp. 298–309.DOI
- [38]L. Yi, J. Peng, Y. Zheng, F. Mo, Z. Wei, Y. Ye, Z. Yue, and Z. Huang, “TGB-Seq benchmark: Challenging temporal graph GNNs with complex sequential dynamics,” in International Conference on Learning Representations, 2025.arxiv.org/abs/2502.02975
- [39]J. Gastinger, S. Huang, M. Galkin, E. Loghmani, A. Parviz, F. Poursafaei, J. Danovitch, E. Rossi, I. Kontis, H. Stuckenschmidt, R. Rabbany, and G. Rabusseau, “TGB 2.0: A benchmark for learning on temporal knowledge graphs and heterogeneous graphs,” in Advances in Neural Information Processing Systems, vol. 37, 2024.
- [40]S. Huang, F. Poursafaei, R. Rabbany, G. Rabusseau, and E. Rossi, “UTG: Towards a unified view of snapshot and event based models for temporal graphs,” in Proceedings of the Third Learning on Graphs Conference, ser. Proceedings of Machine Learning Research, vol. 269. PMLR, 2025, pp. 28:1–28:16.arxiv.org/abs/2407.12269
- [41]J. Chmura, S. Huang, T. G. B. Ngo, A. Parviz, F. Poursafaei, J. Leskovec, M. Bronstein, G. Rabusseau, M. Fey, and R. Rabbany, “TGM: A modular and efficient library for machine learning on temporal graphs,” in International Conference on Learning Representations, 2026.arxiv.org/abs/2510.07586
- [42]L. Yu, L. Sun, B. Du, and W. Lv, “Towards better dynamic graph learning: New architecture and unified library,” Advances in Neural Information Processing Systems, vol. 36, pp. 67 686–67 700, 2023.arxiv.org/abs/2303.13047
- [43]Y. Wang, Y.-Y. Chang, Y. Liu, J. Leskovec, and P. Li, “Inductive representation learning in temporal networks via causal anonymous walks,” in International Conference on Learning Representations, 2021.arxiv.org/abs/2101.05974
- [44]L. Wang, X. Chang, S. Li, Y. Chu, H. Li, W. Zhang, X. He, L. Song, J. Zhou, and H. Yang, “Tcl: Transformer-based dynamic graph modelling via contrastive learning,” arXiv preprint arXiv:2105.07944, 2021.arxiv.org/abs/2105.07944
- [45]Y. Luo and P. Li, “Neighborhood-aware scalable temporal network representation learning,” in Proceedings of the First Learning on Graphs Conference, vol. 198. PMLR, 2022, pp. 1:1–1:18.arxiv.org/abs/2209.01084
- [46]A. Souza, D. Mesquita, S. Kaskia, and V. Garg, “Probably expressive temporal graph networks,” Advances in neural information processing systems, vol. 35, pp. 32 257–32 269, 2022.arxiv.org/abs/2209.15059
- [47]X. Lu, L. Sun, T. Zhu, and W. Lv, “Improving temporal link prediction via temporal walk matrix projection,” Advances in Neural Information Processing Systems, vol. 37, pp. 141 153–141 182, 2024. [Online]. Available: https://arxiv.org/abs/2410.04013v1


