betaFeedback

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 0→10 \to1 transition to an increasing profile and a 1→01 \to0 transition to a decreasing profile (Figure 1). This parameter-free transformation reorganizes historical evidence alongside the original timing information; it adds no new observations.

Illustration of Original Temporal Graph and Edge-Gradient Augmentation

Figure 1. Illustration of Edge-Gradient Augmentation. (a) Original temporal graph snapshots with binary edges at times t1,…,tnt_1,\ldots,t_n. (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.

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 G1:T={Gt=(V,Et)}t=1T\mathcal{G}_{1:T} = \{G_t=(V,E_t)\}_{t=1}^{T}, where VV is a fixed node set (∣V∣=N|V|=N) and Et⊆V×VE_t \subseteq V \times V is the edge set observed at time tt. A binary indicator euv∈{0,1}e_{uv} \in\{0,1\} denotes whether edge (u,v)(u,v) exists at time tt. Given the observed history G1:T\mathcal{G}_{1:T}, the temporal link prediction task is to estimate the conditional probability that edge (u,v)(u,v) exists at a future time step T+ΔT+\Delta:

puv(T+Δ)=Pr⁡(euv(T+Δ)=1∣G1:T)(1)p_{uv}^{(T+\Delta)} = \Pr(e_{uv}^{(T+\Delta)} = 1 \mid\mathcal{G}_{1:T}) \tag*{(1)}

where puv(T+Δ)∈[0,1]p_{uv}^{(T+\Delta)} \in[0,1] denotes the predicted probability of future edge existence. In our experiments, we set Δ=1\Delta= 1 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 τi\tau_i defines one slice Gi\mathcal{G}_i. The index ii orders observations; it is not a physical time unit, and Δ=1\Delta= 1 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 (ts,te)(t_s,t_e) be the first and last timestamps of an edge transition 0→10\to1 (1→01\to0 is analogous). For every ts<t<tet_s < t < t_e we assign

wuv(t)={t−tste−ts,for a 0→1 transition,1−t−tste−ts,for a 1→0 transition,ts<t<te,(2)w_{uv}^{(t)} = \begin{cases} \dfrac{t-t_s}{t_e-t_s}, & \text{for a }0\to1\text{ transition},\\ 1-\dfrac{t-t_s}{t_e-t_s}, & \text{for a }1\to0\text{ transition}, \end{cases} \qquad t_s < t < t_e, \tag*{(2)}

yielding a linear ramp from 0 to 1 (or 1 to 0).

The weights form a tensor W∈RN×N×TW \in\mathbb{R}^{N \times N \times T} that captures change intensity according to Eq. (2). The corresponding procedure is summarized in Algorithm 1.

The interpolation procedure is O(∣E∣T)O(|E|T) 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.

Overview of the EG-RL architecture

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 (αj\alpha_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 yiy_i. 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 {Et}1:T\{E_t\}_{1:T}

Output: tensor WW with intensities

  1. initialise Wuvt←1[euv(t)=1]W_{uvt} \leftarrow1[e_{uv}^{(t)} = 1]

  2. foreach edge (u,v)(u,v) do

  3. identify all birth–death intervals (ts,te)(t_s,t_e)

  4. for t←ts+1t \leftarrow t_s + 1 to te−1t_e - 1 do

  5. if euv(ts)=0e_{uv}^{(t_s)} = 0 then

  6. Wuvt←(t−ts)/(te−ts)W_{uvt} \leftarrow(t-t_s)/(t_e-t_s)

  7. else

  8. Wuvt←1−(t−ts)/(te−ts)W_{uvt} \leftarrow1-(t-t_s)/(t_e-t_s)

Fixed time encoding.

Instead of learning a positional encoder, we adopt the cosine lattice used in GraphMixer. For any timestamp t∈R≥0t \in\mathbb{R}_{\ge0} and encoding dimension dd, we define the fixed time encoding as

ϕ(t)=[cos⁡(tωi)]i=1d,ωi=α−i−1β,(3)\phi(t) = [\cos(t\omega_i)]_{i=1}^{d}, \qquad\omega_i = \alpha^{-\frac{i-1}{\beta}}, \tag*{(3)}

where ϕ(t)∈Rd\phi(t) \in\mathbb{R}^{d} and ωi\omega_i denotes the ii-th frequency. Following GraphMixer, we use the fixed setting α=β=d\alpha= \beta= \sqrt{d} and set d=100d = 100 throughout. Here, α\alpha and β\beta control how the frequencies decay across dimensions, while dd 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 d=100d = 100 keeps the encoding sufficiently expressive while maintaining modest computational overhead. This fixed encoding has two desirable properties: (i) nearby timestamps yield highly correlated ϕ(t)\phi(t), supporting interpolation; (ii) as ii grows, ωi→0\omega_i \to0, so higher-index channels vary more smoothly and remain distinguishable even for large tt.

For each node vv, we construct three components: a raw node feature xv∈Rdxx_v \in\mathbb{R}^{d_x}, a one-hot identity embedding 1v∈{0,1}∣V∣\mathbf{1}_v \in\{0,1\}^{|V|}, and the fixed time encoding ϕ(t)∈Rd\phi(t) \in\mathbb{R}^{d}. When no raw node attributes are available, we use the zero vector for xvx_v. Since all three components are vectors, they can be concatenated into a single input in Rdx+∣V∣+d\mathbb{R}^{d_x+|V|+d} and passed to a two-layer MLP:

hv(t)=MLP⁡n([xv∥1v∥ϕ(t)]),(4)h_v^{(t)} = \operatorname{MLP}_n([x_v \mathbin\Vert\mathbf{1}_v \mathbin\Vert\phi(t)]), \tag*{(4)}

where the identity embedding provides a lightweight way to distinguish nodes even when raw attributes are weak or unavailable.

For every edge (u,v)(u,v), we analogously combine its interpolated gradient weight wuv(t)∈Rw_{uv}^{(t)} \in\mathbb{R}, optional raw edge feature xuv∈Rdex_{uv} \in\mathbb{R}^{d_e}, and the same time encoding ϕ(t)∈Rd\phi(t) \in\mathbb{R}^{d}. If edge attributes are unavailable, we use the zero vector for xuvx_{uv}. Their concatenation therefore lies in R1+de+d\mathbb{R}^{1+d_e+d} and is mapped by a one-layer MLP:

h~uv(t)=MLP⁡ℓ([wuv(t)∥xuv∥ϕ(t)]).(5)\tilde{h}_{uv}^{(t)} = \operatorname{MLP}_{\ell}([w_{uv}^{(t)} \mathbin\Vert x_{uv} \mathbin\Vert\phi(t)]). \tag*{(5)}

Because nodes participate in variable-length interaction sequences, we zero-pad to a fixed window KK (recent first) and average over kk spatial hops:

huv(t)=MeanPool⁡≤k hops([h~uv(t),…]),(6)h_{uv}^{(t)} = \operatorname{MeanPool}_{\leq k\ \mathrm{hops}}\left([\tilde{h}_{uv}^{(t)},\ldots]\right), \tag*{(6)}

where padding length also encodes activity frequency: sparsely interacting nodes receive more zeros, a signal absent from attention-based models.

Token/channel mixer.

Stacking LL GraphMixer blocks, we alternately mix along the token (axis over nodes/edges) and channel (feature) dimensions. For block ℓ\ell with input matrix Z∈RN×CZ \in\mathbb{R}^{N \times C}:

Z′=Z+MLP⁡token(LN⁡(Z)),(7)Z' = Z + \operatorname{MLP}_{\mathrm{token}}(\operatorname{LN}(Z)), \tag*{(7)}
Zℓ+1=Z′+MLP⁡chan(LN⁡(Z′)),(8)Z_{\ell+1} = Z' + \operatorname{MLP}_{\mathrm{chan}}(\operatorname{LN}(Z')), \tag*{(8)}

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 O(N+C)O(N+C) parameter cost per block.

Graph embedding and classifier.

After LL blocks, we mean-pool the token matrix to obtain a compact graph-level summary g=Mean⁡(ZL)g = \operatorname{Mean}(Z_L). For a candidate link (u,v)(u,v) at time tt, we use the endpoint node representations hu(t)h_u^{(t)} and hv(t)h_v^{(t)} from Eq. (4), together with the pair-specific edge representation huv(t)h_{uv}^{(t)} from Eq. (6). A two-layer MLP with hidden size 12dim⁡(g)\frac{1}{2}\dim(g) then outputs the link-existence logit:

y^uv=MLP⁡c([g∥hu(t)∥hv(t)∥huv(t)]).(9)\hat{y}_{uv} = \operatorname{MLP}_c([g \mathbin\Vert h_u^{(t)} \mathbin\Vert h_v^{(t)} \mathbin\Vert h_{uv}^{(t)}]). \tag*{(9)}

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 wuv(t)=0w_{uv}^{(t)} = 0 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 ∣E∣|E| be the number of edges in the selected snapshot, CC the feature width, and LL the mixer depth. Node/edge encoders cost O(∣E∣)O(|E|), each mixer block O(∣E∣C)O(|E|C), and RL sampling O(kT)O(kT). The overall O(∣E∣LC+kT)O(|E|LC+kT) 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, M=(S,A,T,R)\mathcal{M} = (\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R}). At step tt the agent evaluates the next candidate gradient et∈ECe_t \in E_C; state st=(Gtaug,et)s_t = (G_t^{\mathrm{aug}},e_t), action at∈{0,1}a_t \in\{0,1\} and Gt+1aug=Gtaug∪{et}G_{t+1}^{\mathrm{aug}} = G_t^{\mathrm{aug}} \cup\{e_t\} if at=1a_t = 1.

Policy πθ\pi_\theta & Critic QψQ_{\psi}.

Both share graph embedding of GtaugG_t^{\mathrm{aug}} concatenated with an edge embedding of ete_t; 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 η=(AUC⁡(GTaug)−AUC⁡(G))/AUC⁡(G)\eta= (\operatorname{AUC}(G_T^{\mathrm{aug}})-\operatorname{AUC}(G))/\operatorname{AUC}(G), clipped to [−1,1][-1,1]. d) Updates.: REINFORCE with baseline:

∇θJ=∑t(Rt−Qψ(st))∇θlog⁡πθ(at∣st).(10)\nabla_\theta J = \sum_t \left(R_t - Q_\psi(s_t)\right)\nabla_\theta\log\pi_\theta(a_t \mid s_t). \tag*{(10)}

QψQ_\psi 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

L=LBCE+λLRL+β∥Θ∥22\mathcal{L} = \mathcal{L}_{\mathrm{BCE}} + \lambda\mathcal{L}_{\mathrm{RL}} + \beta\lVert\Theta\rVert_2^2

combines supervised BCE, policy gradient loss and L2L_2 regularisation. Forward/backward cost is O(∣E∣L)O(|E|L) for the mixer plus O(kT)O(kT) 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 ±\pm 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 G1:TG_{1:T}, epochs NepN_{\mathrm{ep}}, policy πθ\pi_\theta, critic QψQ_\psi

Output: trained parameters Θ,θ,ψ\Theta, \theta, \psi

  1. for epoch =1=1 to NepN_{\mathrm{ep}} do

    // Stage 0: edge-gradient interpolation

  1. W←EdgeGradientAugmentation⁡(G1:T)W \leftarrow\operatorname{EdgeGradientAugmentation}(G_{1:T})

    // Stage I: RL sampling of augmented snapshot

  1. Gaug←GG^{\mathrm{aug}} \leftarrow G; B←∅B \leftarrow\varnothing

  1. foreach candidate edge et∈ECe_t \in E_C do

  1. st←(Gaug,et)s_t \leftarrow(G^{\mathrm{aug}}, e_t)

  1. sample at∼πθ(⋅∣st)a_t \sim\pi_\theta(\cdot\mid s_t)

  1. if at=1a_t = 1 then

  1. insert ete_t with weight wetw_{e_t} into GaugG^{\mathrm{aug}}

  1. store (st,at)(s_t,a_t) in buffer BB

    // Stage II: supervised update (encoder ⇒\Rightarrow mixer)

  1. compute logits y^\hat{y} on GaugG^{\mathrm{aug}} via (4)–(8)

  1. LBCE←BCE⁡(y^,y)\mathcal{L}_{\mathrm{BCE}} \leftarrow\operatorname{BCE}(\hat{y},y)

  1. update encoder & mixer params Θ\Theta with Adam on LBCE\mathcal{L}_{\mathrm{BCE}}

    // Stage III: one-step fine-tune & reward

  1. freeze Θ\Theta; fine-tune classifier 1 epoch on GaugG^{\mathrm{aug}}

  1. r←AUC⁡(Gaug)−AUC⁡(G)r \leftarrow\operatorname{AUC}(G^{\mathrm{aug}})-\operatorname{AUC}(G)

    // Stage IV: policy & critic update (REINFORCE)

  1. foreach (st,at)∈B(s_t,a_t)\in B do

  1. δ←r−Qψ(st)\delta\leftarrow r-Q_\psi(s_t)

  1. θ←θ+ηπδ∇θlog⁡πθ(at∣st)\theta\leftarrow\theta+\eta_\pi\delta\nabla_\theta\log\pi_\theta(a_t\mid s_t)

  1. ψ←ψ−ηQ∇ψ(Qψ(st)−r)2\psi\leftarrow\psi-\eta_Q\nabla_\psi(Q_\psi(s_t)-r)^2

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 1×10−31 \times10^{-3}, dropout 0.1, weight decay 5×10−55 \times10^{-5}), while the policy and critic use separate Adam optimizers with a learning rate of 3×10−43 \times10^{-4}. 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 0.1∣Et∣0.1|E_t| 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.

DatasetDomain#Nodes#Links#N&L FeatBipartiteDurationTime Granularity
WikipediaSocial9,227157,474– & 172True1 monthUnix timestamps
RedditSocial10,984672,447– & 172True1 monthUnix timestamps
MOOCInteraction7,144411,749– & 4True17 monthsUnix timestamps
LastFMInteraction1,9801,293,103– & –True1 monthUnix timestamps
EnronSocial184125,235– & –False3 yearsUnix timestamps
Social Evo.Proximity742,099,519– & 2False8 monthsUnix timestamps
UCISocial1,89959,835– & –False196 daysUnix timestamps
FlightsTransport13,1691,927,145– & 1False4 monthsdays

Table I. Statistics of the datasets used in experiments. #N&L Feat denotes the dimensions of node and link features.

DyGFormer (2D)

(a) DyGFormer (2D)

DyGFormer (3D)

(b) DyGFormer (3D)

EG-RL (2D)

(c) EG-RL (2D)

EG-RL (3D)

(d) EG-RL (3D)

TPNet (2D)

(e) TPNet (2D)

TPNet (3D)

(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.

MetricJODIEDyRepTGATTGNCAWNEdgeBankTCLGraphMixerNATPINTDyGFormerTPNetEG-RL
AP (%)
Wikipedia96.50±0.1494.86±0.0696.94±0.0698.45±0.0698.76±0.0390.37±0.0096.47±0.1697.25±0.0398.03±0.0798.45±0.0499.03±0.0299.32±0.0399.99±0.00
Reddit98.31±0.1498.22±0.0498.52±0.0298.63±0.0699.11±0.0194.86±0.0097.53±0.0297.31±0.0199.13±0.1099.15±0.0299.22±0.0199.27±0.0099.99±0.00
MOOC80.23±2.4481.97±0.4985.84±0.1589.15±1.6080.15±0.2557.97±0.0082.38±0.2482.78±0.1585.88±0.5588.08±0.8687.52±0.4996.39±0.0999.99±0.00
LastFM70.85±2.1371.92±2.2173.42±0.2177.07±3.9786.99±0.0679.29±0.0067.27±2.1675.61±0.2488.02±1.9489.66±1.8193.00±0.1294.50±0.0896.69±0.01
Enron84.77±0.3082.38±3.3671.12±0.9786.53±1.1189.56±0.0983.53±0.0079.70±0.7182.25±0.1690.60±0.6692.20±0.1592.47±0.1292.90±0.1792.41±0.05
Social Evo.89.89±0.5588.87±0.3093.16±0.1793.57±0.1784.96±0.0974.95±0.0093.13±0.1693.37±0.0788.92±3.4594.42±0.0394.73±0.0194.73±0.0294.54±0.04
UCI89.43±1.0965.14±2.3079.63±0.7092.34±1.0495.18±0.0676.20±0.0089.57±1.6393.25±0.5793.40±0.2696.45±0.1195.79±0.1797.35±0.0496.63±0.04
Flights95.60±1.7395.29±0.7294.03±0.1897.95±0.1498.51±0.0189.35±0.0091.23±0.0290.99±0.0598.57±0.1298.80±0.0298.91±0.0197.73±0.0298.86±0.03
Avg. Rank9.6310.759.386.137.0013.0010.509.136.003.882.752.251.75
AUC (%)
Wikipedia96.33±0.0794.37±0.0996.67±0.0798.37±0.0798.54±0.0490.78±0.0095.84±0.1896.92±0.0397.75±0.1198.16±0.0698.91±0.0299.30±0.0299.99±0.00
Reddit98.31±0.0598.17±0.0598.47±0.0298.60±0.0699.01±0.0195.37±0.0097.42±0.0297.17±0.0299.09±0.1099.09±0.0399.15±0.0199.22±0.0099.99±0.00
MOOC83.81±2.0985.03±0.5887.11±0.1991.21±1.1580.38±0.2660.86±0.0083.12±0.1884.01±0.1787.42±0.5890.55±0.4387.91±0.5897.17±0.0899.99±0.00
LastFM70.49±1.6671.16±1.8971.59±0.1878.47±2.9485.92±0.1083.77±0.0064.06±1.1673.53±0.1286.92±2.7289.28±1.6393.05±0.1094.39±0.0497.71±0.02
Enron87.96±0.5284.89±3.0068.89±1.1088.32±0.9990.45±0.1487.05±0.0075.74±0.7284.38±0.2191.68±0.8392.87±0.3493.33±0.1393.98±0.2693.05±0.05
Social Evo.92.05±0.4690.76±0.2194.76±0.1695.39±0.1787.34±0.0881.60±0.0094.84±0.1795.23±0.0790.84±3.7296.16±0.0296.30±0.0196.43±0.0295.10±0.01
UCI90.44±0.4968.77±2.3478.53±0.7492.03±1.1393.87±0.0877.30±0.0087.82±1.3691.81±0.6792.31±0.3795.57±0.1694.49±0.2096.79±0.0496.81±0.03
Flights96.21±1.4295.95±0.6294.13±0.1798.22±0.1398.45±0.0190.23±0.0091.21±0.0291.13±0.0198.69±0.1098.89±0.0298.93±0.0197.75±0.0298.95±0.05
Avg. Rank9.3810.509.505.887.0013.0010.759.255.883.883.002.381.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:

  1. w/o Gradient: remove edge–gradient interpolation and use binary edges.

  2. w/o RL Selector: keep all interpolated edges, i.e., disable the actor–critic module.

  3. Fixed kk: keep RL but set the candidate window radius to a fixed k=1k = 1, 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.

VariantWikipedia AP/AUCReddit AP/AUCMOOC AP/AUCLastFM AP/AUCEnron AP/AUCSocial Evo. AP/AUCFlights AP/AUCUCI AP/AUC
Full EG-RL99.99 / 99.9999.99 / 99.9999.99 / 99.9996.69 / 97.7192.41 / 93.0594.54 / 95.1096.63 / 96.8198.86 / 98.95
w/o RL Selector98.46 / 98.5998.91 / 99.0588.17 / 91.2193.12 / 93.8793.42 / 91.0893.95 / 94.8175.11 / 96.0895.82 / 90.11
w/o Gradient97.25 / 96.9297.31 / 97.1782.78 / 84.0175.61 / 73.5382.25 / 84.3893.37 / 95.2393.25 / 91.8190.99 / 91.13
Fixed kk98.22 / 98.1598.44 / 98.7185.09 / 89.7792.64 / 93.2092.14 / 90.3193.12 / 94.0273.26 / 95.0394.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 k=1k=1 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 GG denote the original training graph and GaugG^{aug} denote the augmented graph produced by the selector. We define:

rAUC=clip⁡(AUC⁡(Gaug)−AUC⁡(G)AUC⁡(G),[−1,1]),(11)r_{\mathrm{AUC}}=\operatorname{clip}\left(\frac{\operatorname{AUC}(G^{aug})-\operatorname{AUC}(G)}{\operatorname{AUC}(G)},[-1,1]\right), \tag*{(11)}
rAP=clip⁡(AP⁡(Gaug)−AP⁡(G)AP⁡(G),[−1,1]),(12)r_{\mathrm{AP}}=\operatorname{clip}\left(\frac{\operatorname{AP}(G^{aug})-\operatorname{AP}(G)}{\operatorname{AP}(G)},[-1,1]\right), \tag*{(12)}
rAUC&AP=clip⁡(12rAUC+12rAP,[−1,1]),(13)r_{\mathrm{AUC\&AP}}=\operatorname{clip}\left(\frac{1}{2}r_{\mathrm{AUC}}+\frac{1}{2}r_{\mathrm{AP}},[-1,1]\right), \tag*{(13)}

where clip⁡(⋅,[−1,1])\operatorname{clip}(\cdot,[-1,1]) truncates values to the interval [−1,1][-1,1].

2D loss contours of EG-RL on six datasets

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.

3D loss surfaces of EG-RL on six datasets

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.

RewardWikipedia APWikipedia AUCReddit APReddit AUCMOOC APMOOC AUCLastFM APLastFM AUC
AUC (default)99.9999.9999.9999.9999.9999.9996.6997.71
AP99.8599.8799.9399.9499.9199.9396.2397.36
AUC&&AP (joint)99.8499.8699.9299.9499.9099.9396.1397.27
RewardEnron APEnron AUCSocial Evo. APSocial Evo. AUCUCI APUCI AUCFlights APFlights AUC
AUC (default)92.4193.0594.5495.1096.6396.8198.8698.95
AP90.9890.1596.9897.3094.8896.1596.7297.55
AUC&&AP (joint)90.5490.1196.9897.3094.4696.1196.6697.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.

MetricJODIEDyRepTGATTGNCAWNEdgeBankTCLGraphMixerNATPINTDyGFormerTPNetEG-RL
AP (%)
Wikipedia75.65±0.7970.21±1.5887.00±0.1685.62±0.4474.06±2.6280.63±0.0086.76±0.7288.59±0.1753.85±6.2582.39±2.7078.29±5.3879.35±5.5299.84±0.02
Reddit86.98±0.1686.30±0.2689.59±0.2488.10±0.2491.67±0.2485.48±0.0087.45±0.2985.26±0.1181.71±1.0387.59±0.6591.11±0.4088.19±0.3399.92±0.01
MOOC65.23±2.1961.66±0.9575.95±0.6477.50±2.9173.51±0.9449.43±0.0074.65±0.5474.27±0.9277.28±1.9475.70±1.4381.24±0.6988.18±0.9799.90±0.02
LastFM62.67±4.4964.41±2.7071.13±0.1765.95±5.9867.48±0.7775.49±0.0058.21±0.8968.12±0.3364.02±1.4872.24±0.9273.97±0.5077.99±1.3096.22±0.05
Enron68.96±0.9867.79±1.5363.94±1.3670.89±2.7275.15±0.5873.89±0.0071.29±0.3275.01±0.7970.34±1.7380.23±1.3777.41±0.8975.36±1.8189.55±0.10
Social Evo.89.82±4.1193.28±0.4894.84±0.4495.13±0.5688.32±0.2783.69±0.0094.90±0.3694.72±0.3392.12±4.5397.15±0.2597.68±0.1097.35±0.3296.96±0.05
UCI65.99±1.4054.79±1.7668.67±0.8470.94±0.7164.61±0.4857.43±0.0076.01±1.1180.10±0.5157.55±0.8183.61±0.2372.25±1.7177.26±1.5794.23±0.08
Flights69.07±4.0270.57±1.8275.48±0.2671.09±2.7269.18±1.5281.08±0.0074.62±0.1874.87±0.2159.16±1.4861.99±1.7070.92±1.7864.78±1.5097.23±0.04
Avg. Rank10.3810.756.256.388.388.507.126.3810.755.504.504.751.38
AUC (%)
Wikipedia70.96±0.7867.36±0.9681.93±0.2280.97±0.3170.95±0.9581.73±0.0082.19±0.4884.28±0.3052.11±5.8377.03±1.9375.09±3.7075.36±3.4199.86±0.02
Reddit83.51±0.1582.90±0.3187.13±0.2084.56±0.2488.04±0.2985.93±0.0084.67±0.2982.21±0.1376.01±1.0481.02±0.6886.23±0.5181.64±0.4299.94±0.01
MOOC66.63±2.3063.26±1.0173.18±0.3377.44±2.8670.32±1.4348.18±0.0070.36±0.3772.45±0.7275.56±2.3977.00±2.2480.76±0.7689.07±0.6399.93±0.02
LastFM61.32±3.4962.15±2.1263.99±0.2165.46±4.2767.92±0.4477.37±0.0046.93±2.5960.22±0.3258.54±2.3769.51±0.6169.25±0.3672.48±0.9097.35±0.04
Enron70.92±1.0568.73±1.3460.45±2.1271.34±2.4675.17±0.5075.00±0.0067.64±0.8671.53±0.8569.62±1.1278.91±0.9674.07±0.6475.44±1.3889.42±0.09
Social Evo.90.01±3.1993.07±0.3892.94±0.6195.24±0.5689.93±0.1587.88±0.0093.44±0.7294.22±0.3292.53±4.2097.10±0.2297.51±0.0697.59±0.2597.31±0.04
UCI64.14±1.2654.25±2.0160.80±1.0164.11±1.0458.06±0.2658.03±0.0070.05±1.8674.59±0.7449.73±1.2079.42±0.3165.96±1.1870.85±0.9695.57±0.05
Flights69.99±3.1071.13±1.5573.47±0.1871.63±1.7269.70±0.7581.10±0.0072.54±0.1972.21±0.2159.73±1.6159.61±1.6569.53±1.1764.21±1.3097.63±0.03
Avg. Rank9.2510.007.006.388.007.007.386.5011.126.125.625.381.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-kk 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.

MetricJODIEDyRepTGATTGNCAWNEdgeBankTCLGraphMixerNATPINTDyGFormerTPNetEG-RL
AP (%)
Wikipedia83.01±0.6679.93±0.5687.38±0.2286.86±0.3371.21±1.6773.35±0.0089.05±0.3990.90±0.1068.36±4.4791.33±0.7682.23±2.5481.55±4.1099.86±0.02
Reddit80.03±0.3679.83±0.3179.55±0.2081.22±0.6180.82±0.4573.59±0.0077.14±0.1678.44±0.1880.58±0.9183.93±1.1181.57±0.6781.02±1.3199.94±0.01
MOOC78.94±1.2575.60±1.1282.19±0.6287.06±1.9374.05±0.9560.71±0.0077.06±0.4177.77±0.9285.42±3.2684.80±1.5785.85±0.6692.69±0.9599.92±0.03
LastFM74.35±3.8174.92±2.4671.59±0.2476.87±4.6469.86±0.4373.03±0.0059.30±2.3172.47±0.4978.75±1.6384.95±0.4381.57±0.4887.74±0.5096.98±0.05
Enron69.85±2.7071.19±2.7664.07±1.0573.91±1.7664.73±0.3676.53±0.0070.66±0.3977.98±0.9272.90±1.3885.41±0.8475.63±0.7380.79±1.6890.27±0.12
Social Evo.87.44±6.7893.29±0.4395.01±0.4494.45±0.5685.53±0.3880.57±0.0094.74±0.3194.93±0.3191.29±4.8996.73±0.2997.38±0.1496.80±0.4198.53±0.04
UCI75.24±5.8055.10±3.1468.27±1.3780.43±2.1265.30±0.4365.50±0.0080.25±2.7484.11±1.3575.38±1.2893.96±0.2082.17±0.8286.34±0.8094.47±0.08
Flights66.48±2.5967.61±0.9972.38±0.1866.70±1.6464.72±0.9770.53±0.0070.68±0.2471.47±0.2664.74±1.8366.82±1.4466.59±0.4969.10±1.2797.99±0.04
Avg. Rank9.129.387.886.1211.3810.008.386.258.503.625.254.121.00
AUC (%)
Wikipedia80.77±0.7377.74±0.3382.87±0.2282.74±0.3267.84±0.6477.27±0.0085.76±0.4687.68±0.1769.32±2.7889.25±0.4978.80±1.9579.89±2.4799.87±0.01
Reddit80.52±0.3280.15±0.1879.33±0.1681.11±0.1980.27±0.3078.58±0.0076.49±0.1677.80±0.1279.36±0.3182.98±0.6380.54±0.2981.87±0.4999.95±0.01
MOOC82.75±0.8381.06±0.9480.81±0.6788.00±1.8071.57±1.0761.90±0.0072.09±0.5676.68±1.4084.93±2.8987.44±1.7487.04±0.3593.45±0.6799.94±0.02
LastFM75.22±2.3674.65±1.9864.27±0.2677.97±3.0467.88±0.2478.09±0.0047.24±3.1364.21±0.7375.89±2.2181.89±0.9678.78±0.3584.64±0.4597.88±0.04
Enron75.39±2.3774.69±3.5561.85±1.4377.09±2.2265.10±0.3479.59±0.0067.95±0.8875.27±1.1473.22±2.1883.80±0.6876.55±0.5281.16±1.2889.92±0.10
Social Evo.90.06±3.1593.12±0.3493.08±0.5994.71±0.5387.43±0.1585.81±0.0093.44±0.6894.39±0.3191.87±4.5296.82±0.2497.28±0.0797.22±0.3098.75±0.03
UCI78.64±3.5057.91±3.1258.89±1.5777.25±2.6857.86±0.1569.56±0.0072.25±3.4677.54±2.0271.52±1.6192.05±0.3676.97±0.2480.42±0.6496.13±0.07
Flights68.97±1.8769.43±0.9072.20±0.1668.39±0.9566.11±0.7174.64±0.0070.57±0.1870.37±0.2371.11±2.1669.52±0.9068.09±0.4371.82±0.8298.17±0.04
Avg. Rank7.389.008.885.6211.508.629.007.759.383.256.123.501.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 w+(t)=(t−84513)/19w_{+}(t) = (t - 84513)/19. 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 w−(t)=1−(t−84532)/9w_{-}(t) = 1 - (t - 84532)/9 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 BB 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 10−410^{-4} and weight decay 10−610^{-6}; actor and critic use 3×10−43 \times10^{-4}. 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 B=512B = 512, whereas UCI peaks at B=128B = 128 (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, n=3n = 3). 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [15]R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha, “Dyrep: Learning representations over dynamic graphs,” in International conference on learning representations, 2019.
  16. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_rywkp9f4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents