MambaTG improves future link prediction on changing networks

MambaTG: Candidate-Aware State Space Modeling for Future Link Prediction on Temporal Graphs

Machine Learning

Summary

Predicting new and repeated interactions in networks that change over time is challenging because methods often do well only if the interaction has happened before. The authors noticed that existing models rely heavily on past repeated patterns, which hurts their ability to predict new connections between nodes. They propose MambaTG, a method that learns how a node's interaction history evolves and how well potential new connections fit into this evolving context. Their approach works well for both repeated and unseen connections and runs efficiently across many datasets.

What this means in practice

  • For social network engineers: Improve recommendation algorithms by accurately predicting both repeated and new user interactions over time.
  • For cybersecurity analysts: Enhance detection of novel relationships in communication or transaction networks to better identify emerging threats.

Authors

Nguyen Hong Quan, Sitao Luan, Yilun Zheng, Lihui Chen

Abstract

Future link prediction on temporal graphs involves both repeated interactions between previously connected node pairs and first-time interactions between pairs with no prior interaction. While repeated-edge prediction can exploit direct pairwise evidence, unseen-edge prediction must generalize beyond historical recurrence. Existing temporal graph models often exploit signals tied to recurring interactions or historical overlap, which are highly informative for repeated edges but become limited or unavailable for unseen edges, contributing to substantial performance degradation on unseen-edge prediction. Based on this observation, we identify two complementary signals for modeling sequential dynamics beyond historical recurrence: (1) historical-sequence evolution, which captures dependencies among the source node's chronologically ordered interactions, and (2) candidate--history compatibility, which captures how well a candidate fits the source node's evolving history. Based on the decomposition, we propose MambaTG, a candidate-aware Mamba-based framework that jointly models these two signals. Mamba provides a natural mechanism for this design: its selective recurrence captures the evolution of ordered interaction histories, while its input-dependent state transitions allow the history state to adapt to different candidate inputs. Extensive experiments on 13 temporal graph datasets against 13 representative baselines show that MambaTG achieves strong and consistent performance across both repeated and unseen edges while remaining computationally efficient.