A Comparative Study on Dynamic Graph Embedding based on Mamba and Transformers

Ashish Parmanand Pandey, Alan John Varghese, Sarang Patil, Mengjia Xu · 2024

Read A Comparative Study on Dynamic Graph Embedding based on Mamba and Transformers by Ashish Parmanand Pandey, Alan John Varghese, Sarang Patil, Mengjia Xu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11293.txt.

Introduction

Ashish Parmanand Pandey and co-authors present a machine learning paper, published in 2024, comparing two designs for reading networks that change over time. Dynamic graphs model ties that appear and fade, from friendships to financial trades. Transformer models read such data well but grow costly as sequences lengthen, while a newer design called Mamba scales in a straight line.

The team built three new models mixing Mamba or transformer cores with graph layers, then tested them on predicting future links. Mamba based models matched or beat the transformer versions, with clear speed gains on long sequences. They did best on jumpy datasets such as messaging and bitcoin trades, and stayed competitive on steadier networks.

Catalog record

CREATORAshish Parmanand Pandey, Alan John Varghese, Sarang Patil, Mengjia Xu
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11293

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Comparative Study on Dynamic Graph Embedding based on Mamba and Transformers Ashish Parmanand Pandey, Alan John Varghese, Sarang Patil, Mengjia Xu Abstract Dynamic graph embedding has emerged as an important technique for modeling complex time-evolving networks across diverse domains. While transformer-based models have shown promise in capturing long-range dependencies in temporal graph data, they face scalability challenges due to quadratic computational complexity. This study presents a comparative analysis of dynamic graph embedding approaches using transformers and the recently proposed Mamba architecture, a state-space model with linear complexity. We introduce three novel models: TransformerG2G augmented with graph convolutional networks, 𝒟 ​ 𝒢 \mathcal{DG} -Mamba, and 𝒢 ​ 𝒟 ​ 𝒢 \mathcal{GDG} -Mamba with graph isomorphism network edge convolutions. Our experiments on multiple benchmark datasets demonstrate that Mamba-based models achieve comparable or superior performance to transformer-based approaches in link prediction tasks while offering significant computational efficiency gains on longer sequences. Notably, 𝒟 ​ 𝒢 \mathcal{DG} -Mamba variants consistently outperform transformer-based models on datasets with high temporal variability, such as UCI, Bitcoin-OTC, and Reality Mining, while maintaining competitive performance on more stable graphs like SBM. We provide insights into the learned temporal dependencies through analysis of attention weights and state matrices, revealing the models’ ability to capture complex temporal patterns. By effectively combining state-space models with graph neural networks, our work addresses key limitations of previous approaches and contributes to the growing body of research on efficient temporal graph representation learning. These findings offer promising directions for scaling dynamic graph embedding to larger, more complex real-world networks, potentially enabling new applications in areas such as social network analysis, financial modeling, and biological system dynamics. Journal: XXX 1 Introduction Studying the evolving dynamics exhibited in complex real-world graphs (or networks) across spatial and temporal scales plays a key role in diverse fields such as biological networks, social networks, e-commerce, transportation systems, functional brain connectomes, and financial markets. We can model these graphs as dynamic graphs in either continuous time or discrete time, based on the nature of the data. Understanding how these networks change over time and space can provide great insight into their underlying structures and behaviors, enabling more accurate future forecasting in areas such as disease progression modeling, transportation planning, anomaly detection, and risk assessment. Conventional graph neural networks (GNNs) [ 1 , 2 , 3 , 4 ] assume a fixed graph structure without considering evolving dynamics. Similarly, advanced static graph embedding methods, such as those preserving discriminative and geometric properties [ 5 ] , are limited to static structures and do not account for temporal evolution. However, time-aware temporal graph embedding techniques, including continuous-time [ 6 , 7 , 8 ] and discrete-time methods [ 9 , 10 , 11 , 12 , 13 , 14 ] , facilitate learning temporal information for future forecasting by integrating conventional GNNs with recurrent neural networks (RNNs) or long short-term memory (LSTM) or gated recurrent unit (GRU). However, RNN or LSTM-based temporal graph embedding models often suffer from issues like catastrophic forgetting, vanishing gradients, and exploding gradients. Moreover, these approaches face significant challenges while dealing with very large sequential graph snapshots. On the other hand, attention-based transformers [ 15 ] have empowered many advanced Large Language Models (LLMs) with impressive in-context learning (ICL) capability. Transformers have been increasingly applied to capture long-range dependencies across graph snapshots, enabling parallel processing of long graph sequences and significantly enhancing context awareness. Dynamic graph representation learning applications have made impressive progress with the development of attention mechanisms for diverse applications, such as learning temporal graph embeddings with uncertainty quantification [ 16 ] , anomaly detection [ 17 ] , traffic flow forecasting [ 18 , 19 ] , financial time series prediction [ 20 ] , weather forecasting [ 21 ] , heating environment forecasting [ 22 ] , and 3D object detection [ 23 ] . Diverse PyTorch implementations of the aforementioned temporal graph embedding methods can be found in https://pytorch-geometric-temporal.readthedocs.io/ . Nevertheless, the quadratic computational complexity of transformers when dealing with long graph snapshots remains a major shortcoming despite their promising performance and distinct advantage in capturing long-range dependency. More recently, an emerging alternative to transformers, known as “state-space sequence models (SSMs)” [ 24 , 25 ] , has gained substantial attention by addressing the “quadratic complexity” bottleneck inherent in the attention mechanism. In particular, a selective SSM architecture, Mamba [ 25 ] , achieved impressive performance on the Long Range Arena (LRA) benchmark with only linear complexity. The Mamba model outperformed the initially developed structured SSM model (i.e., S4 model [ 24 ] ) by incorporating the “selective scan” technique to compress the data selectively into the state and improved efficiency through the adoption of hardware-aware algorithms on modern hardware (e.g., GPUs and TPUs). Due to temporal graphs that can be modeled as continuous-time temporal events or discrete-time graph snapshots [ 26 ] , Li et al. [ 27 ] developed an SSM-based framework (i.e., GraphSSM) for learning temporal graph dynamics by integrating structural information into the online approximation objective with a Laplacian regularization term. Herein, we conducted a comparative study on dynamic graph embedding based on Mamba and Transformers for diverse benchmarks with smooth and heterogeneous temporal dynamics. 2 Preliminaries 2.1 Dynamic graph modeling Dynamic graphs provide a powerful framework for representing complex systems that evolve over time in various domains [ 28 , 29 ] . Unlike static graphs, dynamic graphs capture the temporal evolution of relationships between entities, offering a more realistic model of real-world networks [ 30 ] . Generally, a discrete-time dynamic graph G can be represented by a sequence of graph snapshots G=\{G_{1},G_{2},...,G_{T}\} , where G_{t}=(V_{t},E_{t}),t\in[0,T] denotes the state of the graph at time step t , where V_{t} is the set of nodes and E_{t} is the set of edges [ 30 ] . More precisely, \displaystyle V_{t} \displaystyle=\{v_{1},v_{2},...,v_{|V_{t}|}\},\;E_{t}\subseteq\{(u,v)|u,v\in V_{t}\}. (1) The discrete-time representation allows us to model systems where changes occur at specific intervals, such as daily social media interactions or weekly financial transactions [ 31 ] . In practice, the set of nodes V_{t} can change over time, reflecting the dynamic nature of entity participation in the system. These dynamics can be represented as V_{i}\neq V_{j} for time steps i\neq j , and i,j\in[0,T] . The corresponding adjacency matrix A_{t}\in\mathbb{R}^{|V_{t}|\times|V_{t}|} of graph G_{t} at time t can be defined as A_{t}=[a_{t}(u,v)],\text{ where }a_{t}(u,v)=\begin{cases}1\quad\text{or}\quad w_{uv}&\text{if }(u,v)\in E_{t};\\ 0&\text{otherwise}.\end{cases} (2) Here, w_{uv} denotes the weight associated with the edge between node pair ( u,v ) when the graph G_{t} is weighted; Otherwise, in an unweighted graph, the edge weight is uniformly 1 . The key challenge in dynamic graph modeling lies in effectively and accurately capturing both the spatial and temporal dependencies. The primary goal of temporal graph embedding is to learn a nonlinear mapping function f that maps each node v at time t to a low-dimensional embedding vector: f:(v,t)\rightarrow emb(v,t)\in\mathbb{R}^{L_{o}},v\in V_{t} (3) where L_{o} is the dimensionality of the node embedding vector, typically much smaller than |V_{t}| . To address the above challenges, sequence models such as RNNs and their variants (LSTMs and GRUs), as well as transformers, have demonstrated effectiveness in capturing temporal dynamics across various domains, e.g., machine translations, sentiment analysis, and

Read the complete text