Edge-Gradient Augmentation under Reinforcement Learning for Temporal Graph

Yongqing Zhou, Jiawei Chen, Wenjun Wang, Xinyu Wang, Wei Yu, Qiyao PengarXiv 2026 · arXiv

TL;DR

Edge-Gradient Reinforced Learning (EG-RL) improves temporal link prediction by explicitly modeling the "pace" of edge births and deaths through linear interpolation. By using a reinforcement learning agent to selectively augment graph snapshots with these transition gradients, the framework achieves state-of-the-art performance across eight major benchmarks, particularly in challenging scenarios where interactions are sparse or irregular.

What Problem Does This Paper Address?

Predicting future links in a dynamic graph (like a social network or a recommendation system) requires understanding not just what happened, but how it evolved. Most existing methods treat edge presence as binary: an edge is either there or it isn't. This neglects the "edge-gradient"—the explicit information about how quickly a relationship forms (birth) or dissolves (death).

Without this context, models struggle to distinguish between persistent activities, one-off encounters, and reappearing links. The challenge lies in representing these transitions without introducing "leakage" (using future information to predict the past) and doing so efficiently enough to handle large-scale evolving networks.

Methods

The authors introduce EG-RL, which consists of three main pillars:

  1. Edge-Gradient Interpolation: Instead of binary 0/1 snapshots, EG-RL constructs "edge-weight profiles." For an edge transition from 0 to 1, it maps the interval to an increasing linear ramp; for 1 to 0, it uses a decreasing ramp. This parameter-free transformation reorganizes historical evidence to expose the pace of interaction changes.

    Fig. 1: Illustration of Edge-Gradient Augmentation. (a) Original temporal graph snapshots with binary edges at times t1, . . . , tn. (b) Constructed edge-weight profiles between observed transition endpoints. These are modelling signals, not measurements of latent relationship strength; both endpoints must be available before a prediction uses the profile.
  2. Reinforcement Learning (RL) Selector: Not every interpolated gradient is helpful; some might just be noise. EG-RL uses a policy-based RL agent (specifically, REINFORCE with a critic baseline) to dynamically select which augmented snapshots to retain. The agent receives rewards based on the relative gain in validation AUC, learning to filter out less informative candidates.

  3. GraphMixer Backbone: The underlying architecture uses a lightweight "Mixer" approach. It features dedicated node and link encoders, followed by a stack of blocks that alternate between "token mixing" (aggregating information across nodes/edges) and "channel mixing" (processing features). This avoids the high computational cost of traditional message-passing GNNs.
Fig. 2: Overview of the EG-RL architecture. The original temporal graph (top-left) is first converted into an edge-gradient– augmented sequence (bottom-left) that exposes the pace of interaction changes. Every snapshot is fed to a node encoder (static features + identity) and a link encoder (time encoding + 1-layer MLP with mean pooling). The resulting tokens are concatenated and channel-flagged (αj), then processed by a stack of Graph-Mixer blocks that alternate token-mix and channel-mix MLPs under pre-layer normalisation. A global mean pool followed by a two-layer MLP produces the link-existence logit yi. A reinforcement module observes graph embeddings and adaptively retains or discards augmented snapshots; its reward signal is fed back (Update) to refine the augmentation loop.

Datasets

The model was evaluated on eight diverse public dynamic graph datasets:

  • Interaction/Bipartite: Wikipedia, Reddit, MOOC, LastFM.
  • Social/Communication: Enron, UCI.
  • Proximity/Transport: Social Evolution, Flights.

These datasets vary significantly in scale, duration (from 1 month to 3 years), and time granularity (Unix timestamps to days).

Key Insights and Ideas

  • Gradients as a Powerful Inductive Bias: The "aha moment" is that explicit transition cues—even simple linear ones—provide a much stronger signal for temporal reasoning than raw binary data. Ablation studies showed that removing these gradients caused performance to plummet (e.g., a 3.38 point drop in AP on the Flights dataset).
  • The Necessity of Selective Attention: The RL selector is critical. Simply keeping all interpolated edges actually hurts performance in many cases because it introduces noise. The RL agent acts as a smart filter, identifying the "observation regimes" where gradients are most reliable.
  • Scalability: By using a Mixer-based backbone and a discrete RL selector, the framework maintains linear complexity $O(|E|LC + kT)$ relative to the number of edges and snapshots. This makes it more scalable than complex attention-based or recurrent temporal GNNs.

Key Results

EG-RL outperformed 12 established baselines (including TGN, TGAT, and DyGFormer) across almost all metrics:

  • Top Ranking: It achieved the best average rank (1.75 in Average Precision and 1.88 in AUC) across the eight benchmarks.
  • Robustness to Evaluation Protocols: The model showed particularly strong gains in "Historical" and "Inductive" negative sampling—settings designed to expose models that rely on simple heuristics. On the Reddit dataset, EG-RL improved AP by 16.01 points over the strongest baseline (PINT) under historical negative sampling.
  • Optimization Speed: On the MOOC dataset, the augmented model reached a comparable validation loss significantly faster than the control model, demonstrating that the added information helps the model converge more efficiently despite the overhead of the RL loop.

Limitations and Future Work

While highly effective, the authors note a few areas for growth:

  • Linearity: The current interpolation is strictly linear. Future work could explore more flexible, non-linear interpolation profiles to better capture complex relationship dynamics.
  • Selection Cost: While linear, the RL selection process still adds overhead. Investigating lower-cost selection strategies or differentiable gates could further improve efficiency.
  • Granularity: The model's performance varies with observation granularity; testing on even larger graphs with higher event densities (like the TGB 2.0 suite) remains an open challenge.

Summary updated

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.
BibTeX
@misc{zhou2026edge,
  author = {Yongqing Zhou and Jiawei Chen and Wenjun Wang and Xinyu Wang and Wei Yu and Qiyao Peng},
  title = {{Edge-Gradient Augmentation under Reinforcement Learning for Temporal Graph}},
  year = {2026},
  eprint = {2611.16678},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.16678},
}
Figure