Abstract
Dynamic graph embedding has emerged as an important technique for modelingcomplex time-evolving networks across diverse domains. While transformer-basedmodels have shown promise in capturing long-range dependencies in temporalgraph data, they face scalability challenges due to quadratic computationalcomplexity. This study presents a comparative analysis of dynamic graphembedding approaches using transformers and the recently proposed Mambaarchitecture, a state-space model with linear complexity. We introduce threenovel models: TransformerG2G augment with graph convolutional networks,\mathcal{DG}-Mamba, and \mathcal{GDG}-Mamba with graph isomorphism network edgeconvolutions. Our experiments on multiple benchmark datasets demonstrate thatMamba-based models achieve comparable or superior performance totransformer-based approaches in link prediction tasks while offeringsignificant computational efficiency gains on longer sequences. Notably,\mathcal{DG}-Mamba variants consistently outperform transformer-based models ondatasets with high temporal variability, such as UCI, Bitcoin, and RealityMining, while maintaining competitive performance on more stable graphs likeSBM. We provide insights into the learned temporal dependencies throughanalysis of attention weights and state matrices, revealing the models' abilityto capture complex temporal patterns. By effectively combining state-spacemodels with graph neural networks, our work addresses key limitations ofprevious approaches and contributes to the growing body of research onefficient temporal graph representation learning. These findings offerpromising directions for scaling dynamic graph embedding to larger, morecomplex real-world networks, potentially enabling new applications in areassuch as social network analysis, financial modeling, and biological systemdynamics.