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