DyGMamba: Efficiently Modeling Long-Term Temporal Dependency on Continuous-Time Dynamic Graphs with State Space Models

## Abstract

Abstract Learning useful representations for continuous-time dynamic graphs (CTDGs) is challenging, due to the concurrent need to span long node interaction histories and grasp nuanced temporal details. In particular, two problems emerge: (1) Encoding longer histories requires more computational resources, making it crucial for CTDG models to maintain low computational complexity to ensure efficiency; (2) Meanwhile, more powerful models are needed to identify and select the most critical temporal information within the extended context provided by longer histories. To address these problems, we propose a CTDG representation learning model named DyGMamba, originating from the popular Mamba state space model (SSM). DyGMamba first leverages a node-level SSM to encode the sequence of historical node interactions. Another time-level SSM is then employed to exploit the temporal patterns hidden in the historical graph, where its output is used to dynamically select the critical information from the interaction history. We validate DyGMamba experimentally on the dynamic link prediction task. The results show that our model achieves state-of-the-art in most cases. DyGMamba also maintains high efficiency in terms of computational resources, making it possible to capture long temporal dependencies with a limited computation budget.

## 1 Introduction

Dynamic graphs store node interactions in the form of links labeled with timestamps (Kazemi et al., ). In recent years, learning dynamic graphs has gained increasing interest since it can be used to facilitate various real-world applications.
Dynamic graphs can be classified into two types, i.e., discrete-time dynamic graph (DTDG) and continuous-time dynamic graph (CTDG).
A DTDG is represented as a sequence of graph snapshots that are observed at regular time intervals, where all the edges in a snapshot are taken as existing simultaneously, while a CTDG consists of a stream of events where each of them is observed individually with its own timestamp.
Previous work (Kazemi et al., ) has indicated that CTDGs have an advantage over DTDGs in preserving temporal details, and therefore, more attention is paid to developing novel CTDG modeling approaches for dynamic graph representation learning.

Recent effort in CTDG modeling has resulted in a wide range of models.
However,
most of them are unable to model long-term temporal dependencies of nodes.
To solve this problem, Yu et al. () propose a CTDG model DyGFormer that can handle long-term node interaction histories based on Transformer (Vaswani et al., ). Despite its ability in modeling longer histories, employing a Transformer naturally introduces excessive usage of computational resources due to its quadratic complexity.
Another recent work CTAN (Gravina et al., ) tries to capture long-term temporal dependencies by propagating graph information in a non-dissipative way over time with a graph convolution-based model. Despite the model’s high efficiency, Gravina et al. () show that CTAN cannot capture very long histories
and is surpassed by DyGFormer on the CTDGs where learning from very far away temporal information is critical.
Based on these observations, we summarize the first challenge in CTDG modeling: How to develop a model that is scalable in modeling very long-term historical interactions?
Another point worth noting is that as longer histories introduce more temporal information, more powerful models are needed to identify and select the most critical parts.
This reveals another challenge: How to effectively select critical temporal information with long node interaction histories?

To address the first challenge, we propose to leverage a popular state space model (SSM), i.e., Mamba SSM (Gu & Dao, ) to encode the long sequence of historical node interactions. Since Mamba is proven effective and efficient in long sequence modeling (Gu & Dao, ), it maintains low computational complexity and is scalable in modeling long-term temporal dependencies. For the second challenge, we address it by learning temporal patterns of node interactions and dynamically selecting the critical temporal information based on them. The motivation can be explained by the following example. Consider a CTDG with nodes as people or songs and edges representing a person playing a song at a specific time. If a person $u$ frequently plays a hit song $v$ initially but decreases the frequency later on, the time intervals between plays increase. Ignoring this pattern can lead models to incorrectly predict that $u$ will still play $v$ at future timestamps due to their high appearances in each other’s historical interactions. If a CTDG model recognizes this pattern, it can prioritize other temporal information, such as $u$ increasingly listening to a new song $v^{\prime}$ before $t$, instead of focusing on $u$, $v$ interactions. Since each pattern corresponds to a specific edge, e.g., $(u,v,t)$, we name these patterns as edge-specific temporal patterns.

To this end, we propose a new CTDG model named DyGMamba. DyGMamba first leverages a node-level Mamba SSM to encode historical node interactions. Another time-level Mamba SSM is then employed to exploit the edge-specific temporal patterns, where its output is used to dynamically select the critical information from the interaction history.
To summarize: (1) We present DyGMamba, the first model using SSMs for CTDG representation learning; (2) DyGMamba demonstrates high efficiency and strong efectiveness in modeling long-term temporal dependencies in CTDGs; (3) Experimental results show that DyGMamba achieves new state-of-the-art on dynamic link prediction over most commonly-used CTDG datasets.

## 2 Related Work and Preliminaries

### 2.1 Related Work

#### Dynamic Graph Representation Learning.

Dynamic graph representation learning methods can be categorized into two groups, i.e., DTDG and CTDG methods. DTDG methods (Pareja et al., ; Goyal et al., ; Sankar et al., ; You et al., ; Li et al., ) can only model DTDGs where each of them is represented as a sequence of graph snapshots. Modeling a dynamic graph as graph snapshots requires time discretization and will inevitably cause information loss (Kazemi et al., ). To overcome this problem, recent works focus more on developing CTDG methods that treat a dynamic graph as a stream of events, where each event has its own unique timestamp. Some works (Trivedi et al., ; Chang et al., ) model CTDGs by using temporal point process. Another line of works (Xu et al., ; Ma et al., ; Wang et al., ; Gravina et al., ) designs advanced temporal graph neural networks for CTDGs. Besides, some other methods are developed based on memory networks (Kumar et al., ; Rossi et al., ; Liu et al., ), temporal random walk (Wang et al., ; Jin et al., ) and temporal sequence modeling (Cong et al., ; Yu et al., ; Besta et al., ; Tian et al., ). Since some real-world CTDGs heavily rely on long-term temporal information for effective learning, a number of works start to study how to build CTDG models that can do long range propagation of information over time (Yu et al., ; Gravina et al., ).
We compare them later in experiments with DyGMamba to show our model outperforms them in capturing long-term temporal information.

#### State Space Models.

Transformer (Vaswani et al., ) is a de facto backbone architecture in modern deep learning. However, its self-attention mechanism results in large space and time complexity, making it unsuitable for extremely long sequence modeling (Duman Keles et al., ). To address this, many works focus on building structured state space models that scale linearly or near-linearly with input sequence length (Gu et al., ; ; ; Smith et al., ; Peng et al., ; Ma et al., ; Gu & Dao, ). Most structured SSMs exhibit linear time invariance (LTI), meaning their parameters are not input-dependent and fixed for all time-steps. Gu & Dao () demonstrate that LTI prevents SSMs from effectively selecting relevant information from the input context, which is problematic for tasks requiring context-aware reasoning. To solve this issue, Gu & Dao () proposes S6, also known as Mamba, which uses a selection mechanism to dynamically choose important information from input sequence elements. Selection mechanism involves learning functions that map input data to SSM’s parameters, making Mamba both efficient and effective in modeling language, DNA sequences, and audio. In our work, we show how SSM can be used to achieve effective and efficient representation learning on CTDGs.

### 2.2 Preliminaries

#### CTDG and Task Formulation.

We define CTDG and dynamic link prediction as follows.

###### Definition 1 (Continuous-Time Dynamic Graph) .

Let $\mathcal{N}$ and $\mathcal{T}$ denote a set of nodes and timestamps, respectively. A CTDG is a sequence of $|\mathcal{G}|$ chronological interactions $\mathcal{G}=\{(u_{i},v_{i},t_{i})\}_{i=1}^{|\mathcal{G}|}$ with $0\leq t_{1}\leq t_{2}\leq...\leq t_{|\mathcal{G}|}$, where $u_{i},v_{i}\in\mathcal{N}$ are the source and destination node of the $i$-th interaction happening at $t_{i}\in\mathcal{T}$, respectively. Each node $u\in\mathcal{N}$ can be equipped with a node feature $\mathbf{x}_{u}\in\mathbb{R}^{d_{N}}$, and each interaction $(u,v,t)$ can be associated with a link (edge) feature $\mathbf{e}_{u,v}^{t}\in\mathbb{R}^{d_{E}}$. If $\mathcal{G}$ is not attributed, we set node and link features to zero vectors.

###### Definition 2 (Dynamic Link Prediction) .

Given a CTDG $\mathcal{G}$, a source node $u\in\mathcal{N}$, a destination node $v\in\mathcal{N}$, a timestamp $t\in\mathcal{T}$, and all the interactions before $t$, i.e., $\{(u_{i},v_{i},t_{i})|t_{i}<t,(u_{i},v_{i},t_{i})\in\mathcal{G}\}$, dynamic link prediction aims to predict whether the interaction $(u,v,t)$ exists.

###### Definition 1 (Continuous-Time Dynamic Graph) .

###### Definition 2 (Dynamic Link Prediction) .

#### S4 and Mamba SSM.

A structured SSM, i.e., S4 (Gu et al., ), is inspired by a continuous system described below:

$$ $\displaystyle\mathbf{z}(\tau)^{\prime}=\mathbf{A}\mathbf{z}(\tau)+\mathbf{B}q( \tau),\ \ r(\tau)=\mathbf{C}\mathbf{z}(\tau).$ (1a) $$

$q(\tau)\in\mathbb{R}$ and $r(\tau)\in\mathbb{R}$ are the 1-dimensional input and output over time $\tau$(^1^11We use $\tau$ rather than $t$ to indicate time in a continuous system to distinguish from the time in CTDGs.), respectively. $\mathbf{A}\in\mathbb{R}^{d_{1}\times d_{1}},\mathbf{B}\in\mathbb{R}^{1\times d
_{1}},\mathbf{C}\in\mathbb{R}^{d_{1}\times 1}$ are three parameters deciding the system. Based on it, an S4 includes a time-scale parameter $\Delta\in\mathbb{R}$ and discretizes all the parameters to adapt the model to processing sequences recurrently.

$$ $\displaystyle\mathbf{z}_{\tau}=\bar{\mathbf{A}}\mathbf{z}_{\tau-1}+\bar{ \mathbf{B}}p_{\tau},\ \ q_{\tau}=\mathbf{C}\mathbf{z}_{\tau},$ (2) where $\displaystyle\bar{\mathbf{A}}=\text{exp}(\Delta\mathbf{A}),\ \ \bar{\mathbf{B} }=(\Delta\mathbf{A})^{-1}\text{exp}((\Delta\mathbf{A})-\mathbf{I})\Delta \mathbf{B}.$ $$

Here, $\tau$ is also discretized to denote the position of an element in a sequence. When the dimension size of an input $d_{2}$ becomes higher (i.e., $d_{2}>1$), S4 is in a Single-Input Single-Output (SISO) fashion, processing each input dimension in parallel with the same set of parameters. Based on S4, Mamba SSM follows the SISO mode but changes its parameters into input-dependent by employing several trainable linear layers to map input into $\bar{\mathbf{A}}$, $\bar{\mathbf{B}}$ and $\Delta$. The system is evolving as it processes input data sequentially, making Mamba time-variant and suitable for modeling temporal sequences.

## 3 DyGMamba

Figure 1 illustrates the overview of DyGMamba. Given a potential interaction $(u,v,t)$, CTDG models are asked to predict whether it exists or not. DyGMamba extracts the historical one-hop interactions of node $u$ and $v$ before timestamp $t$ from the CTDG $\mathcal{G}$ and gets two interaction sequences $\mathcal{S}_{u}^{t}=\{(u,u^{\prime},t^{\prime})|t^{\prime}<t,(u,u^{\prime},t^{
\prime})\in\mathcal{G}\}\cup\{(u^{\prime},u,t^{\prime})|t^{\prime}<t,(u^{
\prime},u,t^{\prime})\in\mathcal{G}\}$ and $\mathcal{S}_{v}^{t}=\{(v,v^{\prime},t^{\prime})|t^{\prime}<t,(v,v^{\prime},t^{
\prime})\in\mathcal{G}\}\cup\{(v^{\prime},v,t^{\prime})|t^{\prime}<t,(v^{
\prime},v,t^{\prime})\in\mathcal{G}\}$ containing $u$’s and $v$’s one-hop temporal neighbors $\textit{Nei}_{u}^{t}=\{(u^{\prime},t^{\prime})|(u,u^{\prime},t^{\prime})\text{
or }(u^{\prime},u,t^{\prime})\in\mathcal{G},t^{\prime}<t\}$ and $\textit{Nei}_{v}^{t}=\{(v^{\prime},t^{\prime})|(v,v^{\prime},t^{\prime})\text{
or }(v^{\prime},v,t^{\prime})\in\mathcal{G}\}$ (link features are omitted for clarity). Then it encodes the neighbors in $\textit{Nei}_{u}^{t}$ and $\textit{Nei}_{v}^{t}$ to get two sequences of encoded neighbor representations for $u$ and $v$. To learn the edge-specific temporal pattern of $(u,v,t)$, we find the interactions between $u$ and $v$ before $t$, compute the time difference between each pair of neighboring interactions, and build a sequence of time differences $\mathcal{S}_{u,v}^{t}$. Finally, DyGMamba dynamically selects critical information from the encoded neighbors and incorporates the learned temporal pattern to achieve link prediction.

Figure: Figure 1: Model overview of DyGMamba.
Refer to caption: extracted/5900153/pics/overview.png

### 3.1 Learning One-Hop Temporal Neighbors

#### Encode Neighbor Features.

Given one-hop temporal neighbors $\textit{Nei}_{u}^{t}$ of the source node $u$, we sort them in the chronological order and append $(u,t)$ at the end to form a sequence of $\textit{Nei}_{u}^{t}+1$ temporal nodes. We take their node features from the dataset and stack them into a feature matrix $\tilde{\mathbf{X}}_{u}^{t}\in\mathbb{R}^{(|\textit{Nei}_{u}^{t}|+1)\times d_{N}}$. Similarly, we build a link feature matrix $\tilde{\mathbf{E}}_{u}^{t}\in\mathbb{R}^{(|\textit{Nei}_{u}^{t}|+1)\times d_{E}}$.
To incorporate temporal information, we encode the time difference between $u$ and each one-hop temporal neighbor $(u^{\prime},t^{\prime})$ using the time encoding function introduced in TGAT (Xu et al., ): $\sqrt{1/d_{T}}[cos(\omega_{1}(t-t^{\prime})+\phi_{1}),\dots,cos(\omega_{d}(t-t
^{\prime})+\phi_{d_{T}})]$. $d_{T}$ is the dimension of time representation. $\omega_{1}\dots\omega_{d_{T}}$ and $\phi_{1}\dots\phi_{d_{T}}$ are trainable parameters. The time feature of $u$’s temporal neighbors are denoted as $\tilde{\mathbf{T}}_{u}^{t}\in\mathbb{R}^{(|\textit{Nei}_{u}^{t}|+1)\times d_{T}}$.
We follow the same way to get $\tilde{\mathbf{X}}_{v}^{t}\in\mathbb{R}^{(|\textit{Nei}_{v}^{t}|+1)\times d_{N}}$, $\tilde{\mathbf{E}}_{v}^{t}\in\mathbb{R}^{(|\textit{Nei}_{v}^{t}|+1)\times d_{E}}$ and $\tilde{\mathbf{T}}_{v}^{t}\in\mathbb{R}^{(|\textit{Nei}_{v}^{t}|+1)\times d_{T}}$ for $v$’s temporal neighbors. Following Tian et al. (), we also consider the historical node interaction frequencies in the interaction sequences $\mathcal{S}_{u}^{t}$ and $\mathcal{S}_{v}^{t}$ of source $u$ and destination $v$. For example, assume the interacted nodes of $u$ and $v$ (arranged in chronological order) are $\{a,v,a\}$ and $\{b,b,u,a\}$, the appearing frequencies of $a$, $b$ in $u$/$v$’s historical interactions are 2/1, 0/2, respectively. And the frequency of the interaction involving $u$ and $v$ is 1. Thus, the node interaction frequency features of $u$ and $v$ are written as $\tilde{F}_{u}^{t}=[[2,1],[1,1],[2,1],[0,1]]^{\top}$ and $\tilde{F}_{v}^{t}=[[0,2],[0,2],[1,1],[2,1],[0,1]]^{\top}$, respectively. Note that the last elements ($[0,1]$ and $[0,1]$) in $\tilde{F}_{u}^{t}$ and $\tilde{F}_{v}^{t}$ correspond to the appended $(u,t)$ and $(v,t)$ not existing in the observed histories. We initialize them with $[0,\textit{number of historical interactions between}\ u,v]$.
An encoding multilayer perceptron (MLP) $f(\cdot):\mathbb{R}\to\mathbb{R}^{d_{F}}$ is employed to encode these features into representations: $\tilde{\mathbf{F}}_{u}^{t}=f(\tilde{F}_{u}^{t}[:,0])+f(\tilde{F}_{u}^{t}[:,1])
\in\mathbb{R}^{(|\textit{Nei}_{u}^{t}|+1)\times d_{F}}$, $\tilde{\mathbf{F}}_{v}^{t}=f(\tilde{F}_{v}^{t}[:,0])+f(\tilde{F}_{v}^{t}[:,1])
\in\mathbb{R}^{(|\textit{Nei}_{v}^{t}|+1)\times d_{F}}$.

#### Patching Neighbors.

We employ the patching technique proposed by (Yu et al., ) to save computational resources when dealing with a large number of temporal neighbors. We treat $p$ temporally adjacent neighbors as a patch and flatten their features. For example, with patching, $\tilde{\mathbf{X}}_{u}^{t}\in\mathbb{R}^{(|\textit{Nei}_{u}^{t}|+1)\times d_{N}}$ results in a new patched feature matrix $\mathbf{X}_{u}^{t}\in\mathbb{R}^{\lceil(|\textit{Nei}_{u}^{t}|+1)/p\rceil
\times(p\cdot d_{N})}$ (we pad $\tilde{\mathbf{X}}_{u}^{t}$ with zero-valued features when $|\textit{Nei}_{u}^{t}|+1$ cannot be divided by $p$). Similarly, we get
$\mathbf{E}_{\theta}^{t}\in\mathbb{R}^{\lceil(|\textit{Nei}_{\theta}^{t}|+1)/p
\rceil\times(p\cdot d_{E})}$, $\mathbf{T}_{\theta}^{t}\in\mathbb{R}^{\lceil(|\textit{Nei}_{\theta}^{t}|+1)/p
\rceil\times(p\cdot d_{T})}$ and $\mathbf{F}_{\theta}^{t}\in\mathbb{R}^{\lceil(|\textit{Nei}_{\theta}^{t}|+1)/p
\rceil\times(p\cdot d_{F})}$ ($\theta$ is either $u$ or $v$). Each row of a feature matrix corresponds to an element of the input sequence sent into an SSM later. Recall that SSMs process sequences in a recurrent way. Patching decreases the length of the sequence by roughly $p$ times, making great contribution in saving computational resources.

#### Node-Level SSM Block.

We first map the padded features of $u$’s and $v$’s one-hop temporal neighbors to the same dimension $d$:

$$ $\displaystyle\mathbf{X}_{\theta}^{t}:=f_{N}(\mathbf{X}_{\theta}^{t}),\ \ \mathbf{E}_{\theta}^{t}:=f_{E}(\mathbf{E}_{\theta}^{t}),\ \ \mathbf{T}_{\theta }^{t}:=f_{T}(\mathbf{T}_{\theta}^{t}),\ \ \mathbf{F}_{\theta}^{t}:=f_{F}( \mathbf{F}_{\theta}^{t}).$ (3) $$

$f_{N}(\cdot):\mathbb{R}^{p\cdot d_{N}}\to\mathbb{R}^{d}$, $f_{E}(\cdot):\mathbb{R}^{p\cdot d_{E}}\to\mathbb{R}^{d}$, $f_{T}(\cdot):\mathbb{R}^{p\cdot d_{T}}\to\mathbb{R}^{d}$, $f_{F}(\cdot):\mathbb{R}^{p\cdot d_{F}}\to\mathbb{R}^{d}$ are four MLPs for different types of neighbor features. We take the concatenation of them as the encoded representations of the temporal neighbors, i.e., $\mathbf{H}_{\theta}^{t}=\mathbf{X}_{\theta}^{t}\|\mathbf{E}_{\theta}^{t}\|
\mathbf{T}_{\theta}^{t}\|\mathbf{F}_{\theta}^{t}\in\mathbb{R}^{\lceil(|\textit
{Nei}_{\theta}^{t}|+1)/p\rceil\times 4d}$. We input $\mathbf{H}_{u}^{t}$ and $\mathbf{H}_{v}^{t}$ separately into a node-level SSM block to learn the temporal dependencies of temporal neighbors. The node-level SSM block consists of $l_{N}$ layers, where each layer is defined as follows (Eq. 4-5).
First, we input $\mathbf{H}_{\theta}^{t}$ into a Mamba SSM

$$ $\displaystyle\mathbf{B}_{1}=\mathbf{H}_{\theta}^{t}\mathbf{W}_{\mathbf{B}_{1}} \in\mathbb{R}^{\lceil(|\textit{Nei}_{\theta}^{t}|+1)/p\rceil\times d_{\text{ SSM}}},\ \ \mathbf{C}_{1}=\mathbf{H}_{\theta}^{t}\mathbf{W}_{\mathbf{C}_{1}} \in\mathbb{R}^{\lceil(|\textit{Nei}_{\theta}^{t}|+1)/p\rceil\times d_{\text{ SSM}}};$ (4a) $\displaystyle\Delta_{1}=\text{Softplus}(\text{Broadcast}_{4d}(\mathbf{H}_{ \theta}^{t}\mathbf{W}_{\Delta_{1}})+\text{Param}_{\Delta_{1}})\in\mathbb{R}^{ \lceil(|\textit{Nei}_{\theta}^{t}|+1)/p\rceil\times 4d};$ (4b) $\displaystyle\bar{\mathbf{A}}_{1}=\text{exp}(\Delta_{1}\mathbf{A}_{1}),\ \ \bar{\mathbf{B}}_{1}=(\Delta_{1}\mathbf{A}_{1})^{-1}\text{exp}((\Delta_{1} \mathbf{A}_{1})-\mathbf{I})\Delta_{1}\mathbf{B}_{1};$ (4c) $\displaystyle\mathbf{H}_{\theta}^{t}:=\mathbf{H}_{\theta}^{t}+\text{SSM}_{\bar {\mathbf{A}}_{1},\bar{\mathbf{B}}_{1},\mathbf{C}_{1}}(\mathbf{H}_{\theta}^{t}).$ (4d) $$

$\mathbf{W}_{\mathbf{B}_{1}},\mathbf{W}_{\mathbf{C}_{1}}\in\mathbb{R}^{4d\times
d
_{\text{SSM}}}$ and $\mathbf{W}_{\Delta_{1}}\in\mathbb{R}^{4d\times 1}$. $\bar{\mathbf{A}}_{1},\bar{\mathbf{B}}_{1}\in\mathbb{R}^{\lceil(|\textit{Nei}_{
\theta}^{t}|+1)/p\rceil\times 4d\times d_{\text{SSM}}}$ are discretized parameters. $\text{Param}_{\Delta_{1}}\in\mathbb{R}^{\lceil(|\textit{Nei}_{\theta}^{t}|+1)/
p\rceil\times 4d}$ is a parameter defined by Gu & Dao (). $\mathbf{I}$ is an identity matrix, and Eq. 4d denotes the SSM forward process similar to Eq. 2. Then we use an MLP $f_{\text{node}}(\cdot):\mathbb{R}^{4d}\to\mathbb{R}^{4d}$ on SSM’s output

$$ $\displaystyle\mathbf{H}_{\theta}^{t}:=\mathbf{H}_{\theta}^{t}+f_{\text{node}} \left(\text{LayerNorm}({\mathbf{H}_{\theta}^{t})}\right).$ (5) $$

After $l_{N}$ layers, we have $\mathbf{H}_{u}^{t}$ and $\mathbf{H}_{v}^{t}$ that contain the encoded information of all one-hop temporal neighbors for the entities $u$ and $v$ as well as the information of themselves.
Since we sort temporal neighbors chronologically, our node-level SSM block can directly learn the temporal dynamics for graph forecasting.

### 3.2 Learning from Edge-Specific Temporal Patterns

#### Time-Level SSM Block.

To capture edge-specific temporal patterns, we use another time-level SSM block consisting of $l_{T}$ layers. We first find out $k$ temporally nearest historical interactions between $u$ and $v$ before $t$ and sort them in the chronological order, i.e., $\{(u,v,t_{0}),...,(u,v,t_{k-1})|t_{0}<...<t_{k-1}<t\}$. Then we construct a timestamp sequence $\{t_{0},t_{1},...,t_{k-1},t\}$ based on these interactions and the prediction timestamp $t$. We compute the time difference between each neighboring pair of them and further get a time difference sequence $\{t_{1}-t_{0},t_{2}-t_{1},...,t-t_{k-1}\}$, representing the change of time interval between two identical interactions. Each element in this sequence is input into the time encoding function stated above to get a edge-specific (specific to the edge $(u,v,t)$) time feature. The features are stacked into a feature matrix $\mathbf{H}_{u,v}^{t}\in\mathbb{R}^{k\times d_{T}}$ and mapped by an MLP $f_{\text{map}1}(\cdot):\mathbb{R}^{d_{T}}\to\mathbb{R}^{\gamma d}$ ($\gamma\in[0,1]$ is a hyperparameter), i.e., $\mathbf{H}_{u,v}^{t}:=f_{\text{map}1}(\mathbf{H}_{u,v}^{t})$. A time-level SSM layer takes $\mathbf{H}_{u,v}^{t}$ as input and computes

$$ $\displaystyle\mathbf{B}_{2}=\mathbf{H}_{u,v}^{t}\mathbf{W}_{\mathbf{B}_{2}}\in \mathbb{R}^{k\times d_{\text{SSM}}},\ \ \mathbf{C}_{2}=\mathbf{H}_{u,v}^{t} \mathbf{W}_{\mathbf{C}_{2}}\in\mathbb{R}^{k\times d_{\text{SSM}}};$ (6a) $\displaystyle\Delta_{2}=\text{Softplus}(\text{Broadcast}_{\gamma d}(\mathbf{H} _{u,v}^{t}\mathbf{W}_{\Delta_{2}})+\text{Param}_{\Delta_{2}})\in\mathbb{R}^{k \times\gamma d};$ (6b) $\displaystyle\bar{\mathbf{A}}_{2}=\text{exp}(\Delta_{2}\mathbf{A}_{2}),\ \ \bar{\mathbf{B}}_{2}=(\Delta_{2}\mathbf{A}_{2})^{-1}\text{exp}((\Delta_{2} \mathbf{A}_{2})-\mathbf{I})\Delta_{2}\mathbf{B}_{2};$ (6c) $\displaystyle\mathbf{H}_{u,v}^{t}:=\mathbf{H}_{u,v}^{t}+\text{SSM}_{\bar{ \mathbf{A}}_{2},\bar{\mathbf{B}}_{2},\mathbf{C}_{2}}(\mathbf{H}_{u,v}^{t}).$ (6d) $$

$\mathbf{W}_{\mathbf{B}_{2}},\mathbf{W}_{\mathbf{C}_{2}}\in\mathbb{R}^{\gamma d
\times d_{\text{SSM}}}$ and $\mathbf{W}_{\Delta_{2}}\in\mathbb{R}^{\gamma d\times 1}$. $\bar{\mathbf{A}}_{2},\bar{\mathbf{B}}_{2}\in\mathbb{R}^{k\times\gamma d\times d
_{\text{SSM}}}$ are discretized parameters. $\text{Param}_{\Delta_{2}}\in\mathbb{R}^{k\times\gamma d}$ is a parameter defined as same as $\text{Param}_{\Delta_{1}}$. In practice, we set $k$ to a number much smaller than $|\textit{Nei}_{\theta}^{t}|$, e.g., $10$. This ensures that time-level SSM will not incur huge computational burden and the model focuses more on the recent histories. Note that we cannot always find $k$ recent interactions between $u$ and $v$. To enable batch processing, we set the time difference without a found historical interaction to a very large number $10^{10}$. For example, if $k=2$, and for $(u,v,t)$ we can only find $(u,v,t_{0})$. The time difference sequence will be $\{10^{10},t-t_{0}\}$. $10^{10}$ is much larger than $t-t_{0}$, indicating that $u$ and $v$ have not had an interaction for an extremely long time, same as existing no historical interaction.

#### Dynamic Information Selection with Temporal Patterns.

After the time-level SSM block, we compute a compressed representation to represent the edge-specific temporal pattern by averaging over $k$ encoded time intervals: $\mathbf{h}_{u,v}^{t}=\text{MeanPooling}(\mathbf{H}_{u,v}^{t})$.
As a result, we have $\mathbf{h}_{u,v}^{t}\in\mathbb{R}^{\gamma d}$ to represent the temporal pattern specific to the edge $(u,v,t)$. To leverage learned temporal pattern, we use it to dynamically select the information from the encoded temporal neighbors $\mathbf{H}_{\theta}^{t}$

$$ $\displaystyle\hat{\mathbf{h}}_{u,v}^{t}=f_{\text{map}2}(\mathbf{h}_{u,v}^{t}) \in\mathbb{R}^{4d};$ (7a) $\displaystyle\hat{\mathbf{h}}_{\theta}^{t}={\mathbf{w}_{\text{agg}}}^{\top} \mathbf{H}_{\theta}^{t}\in\mathbb{R}^{4d},\ \text{where}\ \mathbf{w}_{\text{ agg}}=f_{\text{map}3}(\mathbf{H}_{\theta}^{t})\in\mathbb{R}^{\lceil(|\textit{ Nei}_{\theta}^{t}|+1)/p\rceil};$ (7b) $\displaystyle\alpha_{u}=f^{\prime}(\hat{\mathbf{h}}_{v}^{t})*\hat{\mathbf{h}}_ {u,v}^{t}\in\mathbb{R}^{4d},\ \alpha_{v}=f^{\prime}(\hat{\mathbf{h}}_{u}^{t})* \hat{\mathbf{h}}_{u,v}^{t}\in\mathbb{R}^{4d};$ (7c) $\displaystyle\mathbf{h}_{\theta}^{t}={\beta_{\theta}}^{\top}\mathbf{H}_{\theta }^{t},\ \text{where}\ \beta_{\theta}=\text{Softmax}(\mathbf{H}_{\theta}^{t} \alpha_{\theta})\in\mathbb{R}^{\lceil(|\textit{Nei}_{\theta}^{t}|+1)/p\rceil}.$ (7d) $$

$f_{\text{map}2}(\cdot):\mathbb{R}^{\gamma d}\to\mathbb{R}^{4d}$ and $f_{\text{map}3}(\cdot):\mathbb{R}^{4d}\to\mathbb{R}^{1}$ are two mapping MLPs. $f^{\prime}(\cdot):\mathbb{R}^{4d}\to\mathbb{R}^{4d}$ is another MLP introducing training parameters.
Note that $\alpha_{u}$/$\alpha_{v}$ is computed by considering both the edge-specific temporal pattern and the opposite node $v$/$u$. In the node-level SSM block, we separately model the one-hop temporal neighbors of each node $\theta$, making it hard to connect $u$ and $v$. Computing $\alpha_{\theta}$ as Eq. 7c helps to strengthen the connection between both nodes and meanwhile incorporates the learned temporal pattern. $\beta_{\theta}$ is derived by transforming the queried results based on $\alpha_{\theta}$ into weights. It is then used to compute a weighted-sum of all temporal neighbors for representing $\theta$ at $t$, i.e., $\mathbf{h}_{\theta}^{t}$. Finally, we output the representations of $u$, $v$ and the edge-specific temporal pattern by employing two output MLPs $f_{\text{out}1}(\cdot):\mathbb{R}^{4d}\to\mathbb{R}^{d_{N}}$ and $f_{\text{out}2}(\cdot):\mathbb{R}^{\gamma d}\to\mathbb{R}^{d_{N}}$

$$ $\displaystyle\mathbf{h}_{\theta}^{t}:=f_{\text{out}1}(\mathbf{h}_{\theta}^{t}) \in\mathbb{R}^{d_{N}},\ \mathbf{h}_{u,v}^{t}:=f_{\text{out}2}(\mathbf{h}_{u,v} ^{t})\in\mathbb{R}^{d_{N}}.$ (8) $$

### 3.3 Leveraging Learned Representations for Link Prediction

We leverage $\mathbf{h}_{\theta}^{t}$ and $\mathbf{h}_{u,v}^{t}$ for dynamic link prediction. We employ a prediction MLP, i.e., $f_{\text{LP}}(\cdot):\mathbb{R}^{3d_{N}}\to\mathbb{R}$, as the predictor. The probability of existing a link $(u,v,t)$ is computed as $y^{\prime}(u,v,t)=\text{Sigmoid}(f_{\text{LP}}(\mathbf{h}_{u}^{t}\|\mathbf{h}_
{v}^{t}\|\mathbf{h}_{u,v}^{t}))$. For model parameter learning, we use the following loss function

$$ $\mathcal{L}=-\frac{1}{2M}\sum_{2M}\left(y(u,v,t)\log(y^{\prime}(u,v,t))+(1-y(u ,v,t))\log(1-y^{\prime}(u,v,t))\right).$ (9) $$

$y(u,v,t)$ is the ground truth label denoting the existence of $(u,v,t)$ ($1$/0 0 means existing/non-existing). $M$ is the total number of edges existing in the training data (positive edges). We follow previous work (Yu et al., ) and randomly sample one negative edge for each positive edge during training. Therefore, in total we have $2M$ edges considered in our loss $\mathcal{L}$.

## 4 Experiments

In Sec. 4.2, we validate DyGMamba’s ability in CTDG representation learning by comparing it with baseline methods on dynamic link prediction(^2^22To supplement, we also validate on the dynamic node classification task. Since current mainstream datasets of this task requires no long-term temporal reasoning, we put the discussion in App. F). We do further analysis to show the effectiveness of model components, in particular the time-level SSM block. In Sec. 4.3, we further show DyGMamba’s efficiency. We also show that it achieves much stronger scalability in modeling long-term temporal information compared with DyGFormer.

### 4.1 Experimental Setting

#### CTDG Datasets and Baselines.

We consider seven real-world CTDG datasets collected by (Poursafaei et al., ), i.e., LastFM, Enron, MOOC, Reddit, Wikipedia, UCI and Social Evo.. Dataset statistics are presented in App. A.1. Among them, we take LastFM, Enron and MOOC as long-range temporal dependent datasets because according to Yu et al. (), much longer histories are needed for optimal representation learning on them. We compare DyGMamba with ten recent CTDG baseline models, i.e., JODIE (Kumar et al., ), DyRep (Trivedi et al., ), TGAT (Xu et al., ), TGN (Rossi et al., ), CAWN (Wang et al., ), EdgeBank (Poursafaei et al., ), TCL (Wang et al., ), GraphMixer (Cong et al., ), DyGFormer (Yu et al., ) and CTAN (Gravina et al., ). Among them, only DyGFormer and CTAN are designed for long-range temporal information propagation. Detailed descriptions of baseline methods are presented in App. B. We also implemented FreeDyG (Tian et al., ) by using its official code repository, however, on LastFM, we find that FreeDyG’s loss cannot converge and the reported results are not reproducible. So we do not report its performance in our paper.

#### Implementation Details and Evaluation Settings.

We use the implementations and the best hyperparameters provided by Yu et al. () for all baseline models except CTAN. For CTAN, we use its official implementation, fixing the number of layers to 5. All models are trained with a batch size of 200 for fair efficiency analysis.
For DyGMamba, we report the number of sampled one-hop temporal neighbors $\rho$ and the patch size $p$ here. On Wikipedia, Social Evo., and UCI, $\rho\ \&\ p=$ 32 & 1. On Reddit, $\rho\ \&\ p=$ 64 & 2. On MOOC, $\rho\ \&\ p$ = 128 & 4. On Enron, $\rho\ \&\ p=$256 & 8. On LastFM, $\rho\ \&\ p=$ 512 & 16.
Note that to fairly compare DyGMamba’s efficiency with DyGFormer, we keep the sequence length $\rho/p$ input into the SSM as same as the length input into Transformer in Yu et al. (), i.e., $\rho/p=$ 32.
All experiments are implemented with PyTorch (Paszke et al., ) on a server equipped with an AMD EPYC 7513 32-Core Processor and a single NVIDIA A40 with 45GB memory. We run each experiment for five times with five random seeds and report the mean results together with error bars. Further implementation details including complete hyperparamter configurations are presented in App. C.
We employ two evaluation settings following previous works: the transductive and inductive settings.
As suggested in (Poursafaei et al., ), we do link prediction evaluation using three negative sampling strategies (NSSs): random, historical and inductive. Historical NSS is only considered under the transductive setting. See App. D for detailed explanations. We employ two metrics, i.e., average precision (AP) and area under the receiver operating characteristic curve (AUC-ROC)

**Table 1: AP of transductive dynamic link prediction. The best and the second best results are marked as bold and underlined, respectively. CTAN cannot be trained before 120 hours timeout on Social Evo. so is ranked bottom on this dataset.**
| NSS | Datasets | JODIE | DyRep | TGAT | TGN | CAWN | EdgeBank | TCL | GraphMixer | DyGFormer | CTAN | DyGMamba |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Random | LastFM | 70.95 $\pm$ 2.94 | 71.85 $\pm$ 2.44 | 73.30 $\pm$ 0.18 | 75.31 $\pm$ 5.62 | 86.60 $\pm$ 0.11 | 79.29 $\pm$ 0.00 | 76.62 $\pm$ 1.83 | 75.56 $\pm$ 0.19 | 92.95 $\pm$ 0.14 | 86.44 $\pm$ 0.80 | 93.35 $\pm$ 0.20 |
| Enron | 84.85 $\pm$ 3.13 | 79.80 $\pm$ 2.28 | 70.76 $\pm$ 1.05 | 86.98 $\pm$ 1.05 | 89.50 $\pm$ 0.10 | 83.53 $\pm$ 0.00 | 85.41 $\pm$ 0.71 | 82.13 $\pm$ 0.30 | 92.42 $\pm$ 0.11 | 92.52 $\pm$ 1.20 | 92.65 $\pm$ 0.12 |  |
| MOOC | 81.04 $\pm$ 0.83 | 81.50 $\pm$ 0.77 | 85.71 $\pm$ 0.20 | 89.15 $\pm$ 1.69 | 80.30 $\pm$ 0.43 | 57.97 $\pm$ 0.00 | 83.89 $\pm$ 0.86 | 82.80 $\pm$ 0.15 | 87.66 $\pm$ 0.48 | 84.71 $\pm$ 2.85 | 89.21 $\pm$ 0.08 |  |
| Reddit | 98.31 $\pm$ 0.06 | 98.18 $\pm$ 0.03 | 98.57 $\pm$ 0.01 | 98.65 $\pm$ 0.04 | 99.11 $\pm$ 0.01 | 94.86 $\pm$ 0.00 | 97.78 $\pm$ 0.02 | 97.31 $\pm$ 0.01 | 99.22 $\pm$ 0.01 | 97.21 $\pm$ 0.84 | 99.32 $\pm$ 0.01 |  |
| Wikipedia | 96.51 $\pm$ 0.22 | 94.88 $\pm$ 0.29 | 96.88 $\pm$ 0.06 | 98.45 $\pm$ 0.10 | 98.77 $\pm$ 0.01 | 90.37 $\pm$ 0.00 | 97.75 $\pm$ 0.04 | 97.22 $\pm$ 0.02 | 99.03 $\pm$ 0.03 | 96.61 $\pm$ 0.79 | 99.15 $\pm$ 0.02 |  |
| UCI | 89.28 $\pm$ 1.02 | 66.11 $\pm$ 2.75 | 79.40 $\pm$ 0.61 | 92.33 $\pm$ 0.64 | 95.13 $\pm$ 0.23 | 76.20 $\pm$ 0.00 | 86.63 $\pm$ 1.30 | 93.15 $\pm$ 0.41 | 95.74 $\pm$ 0.17 | 76.64 $\pm$ 4.11 | 95.91 $\pm$ 0.15 |  |
| Social Evo. | 89.88 $\pm$ 0.40 | 88.39 $\pm$ 0.69 | 93.33 $\pm$ 0.06 | 93.45 $\pm$ 0.29 | 84.90 $\pm$ 0.11 | 74.95 $\pm$ 0.00 | 93.82 $\pm$ 0.19 | 93.36 $\pm$ 0.06 | 94.63 $\pm$ 0.07 | Timeout | 94.77 $\pm$ 0.01 |  |
|  | Avg. Rank | 8.29 | 9.29 | 7.00 | 4.29 | 6.00 | 9.43 | 5.57 | 6.43 | 2.43 | 6.29 | 1.00 |
| Historical | LastFM | 74.38 $\pm$ 6.27 | 71.85 $\pm$ 2.91 | 71.60 $\pm$ 0.36 | 75.03 $\pm$ 6.90 | 69.93 $\pm$ 0.33 | 73.03 $\pm$ 0.00 | 71.02 $\pm$ 2.07 | 72.28 $\pm$ 0.37 | 81.51 $\pm$ 0.14 | 82.29 $\pm$ 0.94 | 83.02 $\pm$ 0.16 |
| Enron | 69.13 $\pm$ 1.66 | 72.58 $\pm$ 1.83 | 64.24 $\pm$ 1.24 | 74.31 $\pm$ 0.99 | 65.40 $\pm$ 0.36 | 76.53 $\pm$ 0.00 | 72.39 $\pm$ 0.61 | 77.35 $\pm$ 1.22 | 76.93 $\pm$ 0.76 | 77.24 $\pm$ 1.53 | 77.77 $\pm$ 1.32 |  |
| MOOC | 78.62 $\pm$ 2.43 | 75.14 $\pm$ 2.86 | 82.83 $\pm$ 0.71 | 85.46 $\pm$ 2.32 | 74.46 $\pm$ 0.53 | 60.71 $\pm$ 0.00 | 78.51 $\pm$ 1.24 | 77.09 $\pm$ 0.83 | 85.65 $\pm$ 0.89 | 67.73 $\pm$ 2.08 | 85.89 $\pm$ 0.94 |  |
| Reddit | 79.96 $\pm$ 0.30 | 79.40 $\pm$ 0.30 | 79.78 $\pm$ 0.25 | 81.05 $\pm$ 0.32 | 80.96 $\pm$ 0.28 | 73.59 $\pm$ 0.00 | 77.38 $\pm$ 0.20 | 78.39 $\pm$ 0.40 | 81.63 $\pm$ 1.08 | 89.77 $\pm$ 2.28 | 81.80 $\pm$ 1.52 |  |
| Wikipedia | 81.16 $\pm$ 0.73 | 79.46 $\pm$ 0.95 | 87.31 $\pm$ 0.36 | 87.31 $\pm$ 0.25 | 66.77 $\pm$ 6.62 | 73.35 $\pm$ 0.00 | 86.12 $\pm$ 1.69 | 90.74 $\pm$ 0.06 | 70.13 $\pm$ 11.02 | 95.91 $\pm$ 0.10 | 81.77 $\pm$ 1.20 |  |
| UCI | 74.77 $\pm$ 5.35 | 55.89 $\pm$ 2.83 | 66.78 $\pm$ 0.77 | 81.32 $\pm$ 1.26 | 64.69 $\pm$ 1.78 | 65.50 $\pm$ 0.00 | 74.62 $\pm$ 2.70 | 83.88 $\pm$ 1.06 | 80.44 $\pm$ 1.16 | 76.62 $\pm$ 0.33 | 81.03 $\pm$ 1.09 |  |
| Social Evo. | 91.26 $\pm$ 2.47 | 92.86 $\pm$ 0.90 | 95.31 $\pm$ 0.30 | 93.84 $\pm$ 1.68 | 85.65 $\pm$ 0.11 | 80.57 $\pm$ 0.00 | 95.93 $\pm$ 0.63 | 95.30 $\pm$ 0.34 | 97.05 $\pm$ 0.16 | Timeout | 97.35 $\pm$ 0.52 |  |
|  | Avg. Rank | 6.57 | 8.14 | 6.57 | 4.14 | 9.29 | 8.71 | 7.00 | 4.71 | 4.00 | 4.71 | 2.14 |
| Inductive | LastFM | 62.63 $\pm$ 6.89 | 62.49 $\pm$ 3.04 | 71.16 $\pm$ 0.33 | 65.09 $\pm$ 7.05 | 67.38 $\pm$ 0.57 | 75.49 $\pm$ 0.00 | 62.76 $\pm$ 0.81 | 67.87 $\pm$ 0.37 | 72.60 $\pm$ 0.06 | 80.06 $\pm$ 0.85 | 73.63 $\pm$ 0.54 |
| Enron | 69.51 $\pm$ 1.06 | 66.78 $\pm$ 2.21 | 63.16 $\pm$ 0.59 | 73.27 $\pm$ 0.58 | 75.08 $\pm$ 0.81 | 73.89 $\pm$ 0.00 | 70.98 $\pm$ 0.96 | 74.12 $\pm$ 0.65 | 78.22 $\pm$ 0.80 | 72.02 $\pm$ 2.64 | 80.86 $\pm$ 1.24 |  |
| MOOC | 66.56 $\pm$ 1.49 | 61.48 $\pm$ 0.96 | 76.96 $\pm$ 0.89 | 77.59 $\pm$ 1.83 | 73.55 $\pm$ 0.36 | 49.43 $\pm$ 0.00 | 76.35 $\pm$ 1.41 | 74.24 $\pm$ 0.75 | 80.99 $\pm$ 0.88 | 64.93 $\pm$ 3.31 | 81.11 $\pm$ 0.63 |  |
| Reddit | 86.93 $\pm$ 0.21 | 86.06 $\pm$ 0.36 | 89.93 $\pm$ 0.10 | 88.12 $\pm$ 0.13 | 91.89 $\pm$ 0.18 | 85.48 $\pm$ 0.00 | 86.97 $\pm$ 0.26 | 85.37 $\pm$ 0.26 | 91.06 $\pm$ 0.60 | 90.99 $\pm$ 2.19 | 91.15 $\pm$ 0.54 |  |
| Wikipedia | 74.78 $\pm$ 0.56 | 70.55 $\pm$ 1.22 | 86.77 $\pm$ 0.29 | 85.80 $\pm$ 0.15 | 69.27 $\pm$ 7.07 | 80.63 $\pm$ 0.00 | 72.54 $\pm$ 4.69 | 88.54 $\pm$ 0.20 | 62.00 $\pm$ 14.00 | 94.15 $\pm$ 0.08 | 79.86 $\pm$ 2.18 |  |
| UCI | 66.02 $\pm$ 1.28 | 54.64 $\pm$ 2.52 | 67.63 $\pm$ 0.51 | 70.34 $\pm$ 0.72 | 64.08 $\pm$ 1.06 | 57.43 $\pm$ 0.00 | 73.49 $\pm$ 2.21 | 79.57 $\pm$ 0.61 | 70.51 $\pm$ 1.83 | 66.25 $\pm$ 0.51 | 71.95 $\pm$ 2.51 |  |
| Social Evo. | 91.08 $\pm$ 3.29 | 92.84 $\pm$ 0.98 | 95.20 $\pm$ 0.30 | 94.58 $\pm$ 1.52 | 88.50 $\pm$ 0.13 | 83.69 $\pm$ 0.00 | 96.14 $\pm$ 0.63 | 95.11 $\pm$ 0.32 | 97.62 $\pm$ 0.12 | Timeout | 97.68 $\pm$ 0.42 |  |
|  | Avg. Rank | 8.29 | 9.57 | 5.43 | 5.43 | 6.57 | 7.57 | 6.00 | 5.00 | 4.00 | 5.71 | 2.43 |

**Table 2: AP of inductive dynamic link prediction. EdgeBank cannot do inductive link prediction so is not reported.**
| NSS | Datasets | JODIE | DyRep | TGAT | TGN | CAWN | TCL | GraphMixer | DyGFormer | CTAN | DyGMamba |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Random | LastFM | 83.13 $\pm$ 1.19 | 83.47 $\pm$ 1.06 | 78.40 $\pm$ 0.30 | 81.18 $\pm$ 3.27 | 89.33 $\pm$ 0.06 | 81.38 $\pm$ 1.53 | 82.07 $\pm$ 0.31 | 94.17 $\pm$ 0.10 | 60.40 $\pm$ 3.01 | 94.42 $\pm$ 0.21 |
| Enron | 78.97 $\pm$ 1.59 | 73.97 $\pm$ 3.00 | 66.67 $\pm$ 1.07 | 78.76 $\pm$ 1.69 | 86.30 $\pm$ 0.56 | 82.61 $\pm$ 0.61 | 75.55 $\pm$ 0.81 | 89.62 $\pm$ 0.27 | 74.61 $\pm$ 1.64 | 89.67 $\pm$ 0.27 |  |
| MOOC | 80.57 $\pm$ 0.52 | 80.50 $\pm$ 0.68 | 85.28 $\pm$ 0.30 | 88.01 $\pm$ 1.48 | 81.32 $\pm$ 0.42 | 82.28 $\pm$ 0.99 | 81.38 $\pm$ 0.17 | 87.05 $\pm$ 0.51 | 64.99 $\pm$ 2.24 | 88.64 $\pm$ 0.08 |  |
| Reddit | 96.43 $\pm$ 0.16 | 95.89 $\pm$ 0.26 | 97.13 $\pm$ 0.04 | 97.41 $\pm$ 0.12 | 98.62 $\pm$ 0.01 | 95.01 $\pm$ 0.10 | 95.24 $\pm$ 0.08 | 98.83 $\pm$ 0.02 | 80.07 $\pm$ 2.53 | 98.97 $\pm$ 0.01 |  |
| Wikipedia | 94.91 $\pm$ 0.32 | 92.21 $\pm$ 0.29 | 96.26 $\pm$ 0.12 | 97.81 $\pm$ 0.18 | 98.27 $\pm$ 0.02 | 97.48 $\pm$ 0.06 | 96.61 $\pm$ 0.04 | 98.58 $\pm$ 0.01 | 93.58 $\pm$ 0.65 | 98.77 $\pm$ 0.03 |  |
| UCI | 79.73 $\pm$ 1.48 | 58.39 $\pm$ 2.38 | 79.10 $\pm$ 0.49 | 87.81 $\pm$ 1.32 | 92.61 $\pm$ 0.35 | 84.19 $\pm$ 1.37 | 91.17 $\pm$ 0.29 | 94.45 $\pm$ 0.13 | 49.78 $\pm$ 5.02 | 94.76 $\pm$ 0.19 |  |
| Social Evo. | 91.72 $\pm$ 0.66 | 89.10 $\pm$ 1.90 | 91.47 $\pm$ 0.10 | 90.74 $\pm$ 1.40 | 79.83 $\pm$ 0.14 | 92.51 $\pm$ 0.11 | 91.89 $\pm$ 0.05 | 93.05 $\pm$ 0.10 | Timeout | 93.13 $\pm$ 0.05 |  |
|  | Avg. Rank | 6.29 | 8.00 | 7.00 | 5.14 | 4.43 | 5.57 | 5.86 | 2.14 | 9.57 | 1.00 |
| Inductive | LastFM | 71.37 $\pm$ 3.45 | 69.75 $\pm$ 2.73 | 76.26 $\pm$ 0.34 | 68.47 $\pm$ 6.07 | 71.28 $\pm$ 0.43 | 68.79 $\pm$ 0.93 | 76.27 $\pm$ 0.37 | 75.07 $\pm$ 1.45 | 55.60 $\pm$ 3.91 | 76.76 $\pm$ 0.43 |
| Enron | 66.99 $\pm$ 1.15 | 62.64 $\pm$ 2.33 | 59.95 $\pm$ 1.00 | 64.51 $\pm$ 1.66 | 60.61 $\pm$ 0.63 | 68.93 $\pm$ 1.34 | 71.71 $\pm$ 1.33 | 67.21 $\pm$ 0.72 | 68.66 $\pm$ 2.31 | 68.77 $\pm$ 0.60 |  |
| MOOC | 64.67 $\pm$ 1.18 | 62.05 $\pm$ 2.11 | 77.43 $\pm$ 0.81 | 76.81 $\pm$ 2.83 | 74.36 $\pm$ 0.78 | 75.95 $\pm$ 1.46 | 73.87 $\pm$ 0.99 | 80.66 $\pm$ 0.94 | 57.49 $\pm$ 1.34 | 80.75 $\pm$ 1.00 |  |
| Reddit | 62.54 $\pm$ 0.52 | 61.07 $\pm$ 0.86 | 63.96 $\pm$ 0.25 | 65.27 $\pm$ 0.57 | 64.10 $\pm$ 0.22 | 61.45 $\pm$ 0.25 | 64.82 $\pm$ 0.30 | 65.03 $\pm$ 1.20 | 78.35 $\pm$ 5.03 | 65.30 $\pm$ 1.05 |  |
| Wikipedia | 68.22 $\pm$ 0.36 | 61.07 $\pm$ 0.82 | 84.19 $\pm$ 0.96 | 81.96 $\pm$ 0.62 | 62.34 $\pm$ 6.79 | 71.46 $\pm$ 4.95 | 87.47 $\pm$ 0.25 | 57.90 $\pm$ 11.05 | 92.61 $\pm$ 0.90 | 71.14 $\pm$ 2.44 |  |
| UCI | 63.57 $\pm$ 2.15 | 52.63 $\pm$ 1.87 | 69.77 $\pm$ 0.43 | 69.94 $\pm$ 0.50 | 63.44 $\pm$ 1.52 | 74.39 $\pm$ 1.81 | 81.40 $\pm$ 0.52 | 70.25 $\pm$ 2.02 | 52.31 $\pm$ 2.67 | 72.17 $\pm$ 2.20 |  |
| Social Evo. | 89.06 $\pm$ 1.23 | 87.30 $\pm$ 1.55 | 94.24 $\pm$ 0.36 | 90.67 $\pm$ 2.41 | 80.30 $\pm$ 0.21 | 95.94 $\pm$ 0.37 | 94.56 $\pm$ 0.24 | 96.73 $\pm$ 0.11 | Timeout | 96.83 $\pm$ 0.56 |  |
|  | Avg. Rank | 6.86 | 8.57 | 5.29 | 5.43 | 7.43 | 4.86 | 3.14 | 4.43 | 6.57 | 2.43 |

### 4.2 Performance Analysis

#### Comparative Study on Benchmark Datasets.

We report the AP of transductive and inductive link prediction in Table 1 and 2 (AUC-ROC reported in Table 12 and 13 in App. E). We find that: (1) DyGMamba constantly ranks top $1$ under the random NSS, showing a superior performance; (2) Under the historical and inductive NSS, DyGMamba can achieve the best average rank compared with all baselines. More importantly, it shows more superiority on the datasets where encoding longer-term temporal dependencies is necessary, e.g., on LastFM, Enron and MOOC.
(3) Among the models that can do long range propagation of information over time (i.e., DyGFormer, CTAN and DyGMamba), DyGMamba achieves the best average rank under any NSS setting in both transductive and inductive link prediction. On the long-range temporal dependent datasets, DyGMamba outperforms DyGFormer and CTAN in most cases; (4) CTAN achieves much better results in transductive than in inductive link prediction. This is because CTAN requires multi-hop temporal neighbors to learn node representations, which is difficult for unseen nodes. By contrast, DyGMamba and DyGFormer require only one-hop temporal neighbors, thus performing much better in inductive link prediction.

**Table 3: Ablation studies under transductive setting. R/H/I means random/historical/inductive NSS. Metric is AP.**
| Datasets | LastFM | Enron | MOOC | Reddit | Wikipedia | UCI | Social Evo. |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Models | R | H | I | R | H | I | R | H | I | R | H | I | R | H | I | R | H | I | R | H | I |
| Variant A | 93.14 | 80.30 | 71.29 | 91.35 | 70.07 | 75.44 | 87.78 | 83.25 | 77.04 | 99.19 | 81.60 | 90.70 | 98.99 | 80.99 | 79.26 | 94.88 | 79.37 | 70.43 | 94.59 | 96.97 | 97.42 |
| Variant B | 93.07 | 82.53 | 72.97 | 92.46 | 76.88 | 78.87 | 86.95 | 83.78 | 75.81 | 97.97 | 73.47 | 84.16 | 94.17 | 81.37 | 79.24 | 91.69 | 71.13 | 60.45 | 92.90 | 96.61 | 97.14 |
| DyGMamba | 93.35 | 83.02 | 73.63 | 92.65 | 77.77 | 80.86 | 89.21 | 85.89 | 81.11 | 99.32 | 81.80 | 91.15 | 99.15 | 81.77 | 79.86 | 95.91 | 81.03 | 71.95 | 94.77 | 97.35 | 97.68 |

**Table 4: Ablation studies under inductive setting. R/I means random/inductive NSS. Metric is AP.**
| Datasets | LastFM | Enron | MOOC | Reddit | Wikipedia | UCI | Social Evo. |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Models | R | I | R | I | R | I | R | I | R | I | R | I | R | I |
| Variant A | 94.12 | 73.03 | 85.97 | 61.43 | 84.25 | 76.16 | 98.84 | 65.19 | 98.49 | 70.98 | 93.23 | 70.84 | 92.99 | 96.54 |
| Variant B | 94.25 | 75.26 | 89.13 | 67.87 | 86.21 | 75.08 | 97.32 | 58.22 | 92.41 | 70.76 | 90.42 | 60.43 | 91.11 | 96.32 |
| DyGMamba | 94.42 | 76.76 | 89.67 | 68.77 | 88.64 | 80.75 | 98.97 | 65.30 | 98.77 | 71.14 | 94.76 | 72.17 | 93.13 | 96.83 |

#### Ablation Study.

We conduct two ablation studies to study the effectiveness of model components. In study A, we make a model variant (Variant A) by removing the time-level SSM block and restrain our model from learning temporal patterns (information selection is substituted by mean pooling over the output of Eq. 5). In study B, we make a model variant (Variant B) by removing the Mamba SSM layers (Eq. 4) in the node-level SSM block. We find that: (1) From Table 3 and 4, we observe that under any NSS setting, Variant A is constantly beaten by the complete model, proving the effectiveness of learning edge-specific temporal patterns;
(2) We also witness a performance drop from Table 3 and 4 if we switch DyGMamba to Variant B. This indicates the importance of encoding the one-hop temporal neighbors with SSM layers for capturing graph dynamics.

#### A Closer Look into Temporal Pattern Modeling.

We observe from ablation studies that time-level SSM block contributes to better model performance on real-world datasets.
To better quantify the benefits brought by temporal pattern modeling, we construct three synthetic datasets, i.e., S1, S2 and S3, that follow different patterns and compare our model with DyGFormer, CTAN as well as Variant A on them.
Each synthetic dataset contains 7 nodes, where the interactions of each pair of two nodes follow a certain pattern along time.
And for each node, we generate interactions with all the other nodes.
Assume we have a pair of node $u$ and $v$ and they have interactions at $\{t_{i}\}_{i=0}^{N}$, in S1, the time intervals between neighboring interactions $\{t_{1}-t_{0},...,t_{N}-t_{N-1}\}$ follow an increasing trend with a constant velocity of 0.05, i.e., $(t_{i+2}-t_{i+1})-(t_{i+1}-t_{i})=$ 0.05 . In S2, we set the time intervals to a decreasing trend with the same velocity, i.e., $(t_{i+1}-t_{i})-(t_{i+2}-t_{i+1})=$ 0.05. And in S3, we modify S1 by repeating several periods of increasing patterns taken from S1 to form a periodic dataset. In this way, we have three datasets demonstrating diverse temporal patterns: increasing/decreasing/periodic time intervals between neighboring interactions.
Details of dataset construction and statistics are provided in App. A.2. From Table 5, we observe that DyGMamba greatly outperforms DyGFormer and CTAN. More importantly, Variant A shows similar performance to DyGFormer, meaning that our time-level SSM block is able to capture temporal patterns and modeling such patterns is important in CTDG reasoning. For more implementation details on synthetic datasets, please refer to App. C.2.

**Table 5: Performance (Random NSS) on synthetic datasets.**
| Datasets | DyGFormer | CTAN | Variant A | DyGMamba |
| --- | --- | --- | --- | --- |
| S1 | 55.19 $\pm$ 0.98 | 51.25 $\pm$ 2.11 | 53.72 $\pm$ 0.04 | 81.58 $\pm$ 1.31 |
| S2 | 57.80 $\pm$ 4.61 | 51.17 $\pm$ 0.93 | 60.16 $\pm$ 2.20 | 85.36 $\pm$ 2.55 |
| S3 | 79.20 $\pm$ 0.60 | 51.46 $\pm$ 0.19 | 76.36 $\pm$ 0.45 | 86.59 $\pm$ 0.09 |

### 4.3 Efficiency Analysis

Figure: Figure 2: Efficiency comparison on four datasets among DyGMamba and five baselines in terms of number (#) of parameters, training time per epoch and GPU memory. The performance metric here is AP of transductive link prediction under random NSS. The greener, the better performance/efficiency. In contrast to other methods, DyGMamba consistently shows strong overall capability across different datasets. More explanations in Sec. 4.3.
Refer to caption: extracted/5900153/pics/Figure2_new.png

#### Model Size, Per Epoch Training Time and GPU Memory.

Fig. 2 compares DyGMamba with five baselines in terms of number of parameters (model size), per epoch training time and GPU memory consumption during training(^3^33The baselines not included here are either extremely inefficient (e.g., CAWN) or inferior in performance (e.g., DyRep). Complete statistics of all baseline models presented in App. G). We find that: (1) DyGMamba uses very few parameters while maintaining the best performance, showing a strong parameter efficiency. Only CTAN constantly uses fewer parameters than DyGMamba, however, its performance is much worse; (2) DyGMamba is much more efficient than DyGFormer with the same length of input sequence ($\rho/p=$32);
(3) Although DyGMamba generally consumes more GPU memory and per epoch training time compared with most baselines, the gap of consumption is not very large in most cases. To model more temporal neighbors for long-range temporal dependent datasets, DyGMamba naturally requires more computational resources, thus enlarging the consumption gap. DyGFormer shows the same trend as DyGMamba since it also captures long-term temporal dependencies by considering more temporal neighbors; (4) CTAN requires very few computational resources. However, on long-range temporal dependent datasets, it is beaten by DyGFormer and DyGMamba with a great margin. Besides, CTAN is also hard to converge. Although it requires very little per epoch training time, it requires much more epochs to reach the best performance, leading to a long total training time. See App. G.2 and G.3 for details.

#### Impact of Patch Size on Scalability and Performance.

Patching treats $p$ temporal neighbors as one patch and thus decreases the sequence length by $p$ times. This is very helpful in cutting the consumption of GPU memory and training/evaluation time. However, patching introduces excessive parameters because it is done through $f_{N}$, $f_{E}$, $f_{T}$ and $f_{F}$ (Eq. 3) whose sizes increase as the patch size grows. Fig. 3b shows the numbers of parameters of DyGFormer and DyGmamba with different patch sizes on a long-term temporal dependent dataset Enron. We find that patching greatly affects model sizes.
To further study how patching affects DyGMamba, we decrease the patch size gradually from 8 to 1 and track DyGMamba’s performance (Fig. 3a) as well as efficiency (Fig. 3b to 3d) on Enron. Meanwhile, we also keep track on DyGFormer under the same patch size for comparison. We have several findings: (1) Whatever the patch size is, DyGMamba always consumes fewer parameters, less GPU memory and per epoch training time, showing its high efficiency; (2) While both models require increasing computational budgets as the patch size decreases, the speed of increase is much lower for DyGMamba, demonstrating its strong scalability in modeling longer sequences; (3) Different trends in performance change are observed between two models. While DyGFormer performs worse, DyGMamba can benefit from a smaller patch size, indicating its strong ability to capture nuanced temporal details even if the sequence becomes much longer. Note that the models use fewer parameters under smaller patch size. This also shows that DyGMamba can achieve much stronger parameter efficiency by reducing patch sizes.
To further study the reason for finding (3), we plot the performance of Variant A (from ablation study A) under different patch sizes in Fig. 3a. We find that Variant A’s performance degrades when sequence length is more than $64$. This means that dynamic information selection based on edge-specific temporal patterns is essential for DyGMamba to optimally process long sequences.

Figure: (a) Enron performance.
Refer to caption: extracted/5900153/pics/dygmamba_enron_performance.png

#### Scalability in Modeling Increasing Number of Temporal Neighbors.

Sequence length is decided by the sampled temporal neighbors $\rho$ and the patch size $p$. If we want to model a huge

Figure: Figure 4: GPU memory consumption on Enron with increasing neighbors. For clarity, memory is shown only when neighbors are more than 512.
Refer to caption: extracted/5900153/pics/dygmamba_lastfm_more_neighbor_memory_ver4.png

number of temporal neighbors, e.g., $\rho=$4096, keeping the sequence length unchanged as 32 means we need to set $p$ to 128. This will greatly increase model parameters and cause burden in parameter optimization. Besides, as shown in Fig. 3a, bigger $p$ does not necessarily lead to better performance. Therefore, it is also important to see if a model is scalable to $\rho$, with a fixed $p$. In Fig. 4, we show the consumed GPU memory of DyGMamba and DyGFormer with $\rho$ varying from 64, 128, 256, 512, 1024, 2048, 4096 and 8192 on Enron, under a fixed patch size $p=$8. We find that DyGMamba shows superior scalability over DyGFormer. While DyGFormer can only process 2048 nodes, DyGMamba can deal with more than 8192 (at least 4 times) on a single 45GB NVIDIA A40 GPU.
This implies our model’s potential to process a huge number of temporal neighbors with a limited GPU memory budget.

#### DyGMamba vs. DyGFormer on Complexity.

In historical interaction modeling, DyGMamba holds a computational complexity linear to $\rho/p$, while DyGFormer’s complexity is quadratic to $\rho/p$. As a result, as the sequence length grows (either $\rho$ increases or $p$ decreases), DyGFormer is less scalable compared with DyGMamba.

## 5 Conclusion

We propose DyGMamba, an efficient CTDG representation learning model that can capture long-term temporal dependencies. DyGMamba first leverages a node-level SSM to encode long sequences of historical node interactions. It then employs a time-level SSM to learn edge-specific temporal patterns. The learned patterns are used to select the critical part of the encoded temporal information. DyGMamba achieves superior performance on dynamic link prediction, and moreover, it shows high efficiency and strong scalability compared with previous CTDG methods, implying a great potential in modeling huge amounts of temporal information with a limited computational budget. Our code is uploaded as supplementary materials. Please refer to it for reproducibility.

## Appendix A CTDG Dataset Details

### A.1 Real-World Benchmark Datasets

We present the dataset statistics of all considered CTDG datasets in Table 6. All the datasets in our experiments are taken from Yu et al. (). We chronologically split each dataset with the ratio of 70%/15%/15% for training/validation/testing. Please refer to it for detailed dataset descriptions.

**Table 6: Dataset statistics. # N&E Feat means the numbers of node and edge features.**
| Datasets | # Nodes | # Edges | # N&E Feat | Bipartite | Duration | # Timestamps | Time Granularity |
| --- | --- | --- | --- | --- | --- | --- | --- |
| LastFM | 1,980 | 1,293,103 | 0 & 0 | True | 1 month | 1,283,614 | Unix timestamps |
| Enron | 184 | 125,235 | 0 & 0 | False | 3 years | 22,632 | Unix timestamps |
| MOOC | 7,144 | 411,749 | 0 & 4 | True | 17 months | 345,600 | Unix timestamps |
| Reddit | 10,984 | 672,447 | 0 & 172 | True | 1 month | 669,065 | Unix timestamps |
| Wikipedia | 9,227 | 157,474 | 0 & 172 | True | 1 month | 152,757 | Unix timestamps |
| UCI | 1,899 | 59,835 | 0 & 0 | False | 196 days | 58,911 | Unix timestamps |
| Social Evo. | 74 | 2,099,519 | 0 & 2 | False | 8 months | 565,932 | Unix timestamps |

### A.2 Synthetic Datasets

For all of our three synthetic datasets, node and link features are not involved during dataset construction. The construction details are as follows:

- •
S1: For each interaction pair $u$ and $v$, their first interaction is at timestamp 0 0 and the second interaction is generated randomly. Thus, the first time interval is also determined. Starting from the second interval, they follow an increasing trend with a constant velocity of 0.05, i.e., $(t_{i+2}-t_{i+1})-(t_{i+1}-t_{i})$= 0.05. The number of interactions for each node pair is randomly determined and the interaction numbers of all node pairs sum up to 100000.
- •
S2: For each interaction pair $u$ and $v$, their first interaction is at timestamp 0 and the second interaction is generated randomly. However, it should be large enough so that the interval will not drop to zero or negative afterwards. Starting from the second interval, they follow a decreasing trend with a constant velocity of 0.05, i.e., $(t_{i+1}-t_{i})-(t_{i+2}-t_{i+1})=$ 0.05. The number of interactions for each node pair is randomly determined and the interaction numbers of all node pairs sum up to 100000.
- •
S3: S3 contains 8 periods. In each period, the interactions of each node pair $u$ and $v$ are generated following the same pattern in S1.
The number of interactions for each node pair is randomly determined and the interaction numbers of all node pairs sum up to 12000 in the period.

We present the statistics of all synthetic datasets in Table 7.
We chronologically split each dataset with the ratio of 70%/15%/15% for training/validation/testing. To better visualize the temporal patterns in each dataset, we pick one pair of interacting nodes and plot the time intervals between neighboring interactions in each dataset in Figure 5. Note that for the periodic dataset S3 (Figure 5c), each of the train, validation and test sets contains at least one start of a new period. This ensures that models have to capture periodic temporal patterns in order to achieve good performance during evaluation, rather than only learning the increasing time intervals as specified in S1.

Furthermore, we provide the information about the numbers of interactions regarding interacting node pairs in Table 8. We show that each node pair is equipped with a substantial number of interactions, meaning that temporal patterns in our synthetic datasets span across long time periods. This encourages models to consider long-term temporal dependencies for better graph reasoning.

**Table 7: Synthetic dataset statistics.**
| Datasets | # Nodes | # Edges | # Timestamps | Time Range |
| --- | --- | --- | --- | --- |
| S1 | 7 | 100,000 | 96,869 | 0 - 163241.65 |
| S2 | 7 | 100,000 | 98,004 | 0 - 1573561.52 |
| S3 | 7 | 95,657 | 95,370 | 0 - 1771300.40 |

**Table 8: Interaction information of node pairs in synthetic datasets. Complete Dataset includes the numbers of interactions across the whole datasets, including training, validation and testing.**
|  | Datasets | Avg. # Interactions | Min # Interactions | Max # Interactions |
| --- | --- | --- | --- | --- |
| Training Set | S1 | 1,428.57 | 1,205 | 1,663 |
| S2 | 1,428.57 | 1,424 | 1,433 |  |
| S3 | 1,367.91 | 1,364 | 1,372 |  |
| Complete Dataset | S1 | 2,010.20 | 1,879 | 2,150 |
| S2 | 2,010.20 | 1,921 | 2,097 |  |
| S3 | 1,952.18 | 1,721 | 2,193 |  |
| S3 (each period) | 244.02 | 215 | 274 |  |

Figure: (a) Synthetic dataset S1.
Refer to caption: extracted/5900153/pics/S1_interval_3.png

## Appendix B Baseline Details

We provide the detailed descriptions of all baselines here. The baselines can be split into two groups: the methods designed/not designed for long-range temporal information propagation.

### B.1 Baselines Not Designed for Long-Range Temporal Information Propagation

- •
JODIE (Kumar et al., ): JODIE employs a recurrent neural network (RNN) for each node and uses a projection operation to learn the future representation trajectory of each node.
- •
DyRep (Trivedi et al., ): DyRep updates node representations as events appear. It designs a two-time scale deep temporal point process approach for source and destination nodes and couples the structural and temporal components with a temporal-attentive aggregation module.
- •
TGAT (Xu et al., ): TGAT computes the node representations by aggregating each node’s temporal neighbors based on a self-attention module. A time encoding function is proposed to learn functional representations of time.
- •
TGN (Rossi et al., ): TGN leverages an evolving memory for each node and updates the memory when a node-relevant interaction occurs by using a message function, a message aggregator, and a memory updater. An embedding module is used to generate the temporal representations of nodes.
- •
CAWN (Wang et al., ): CAWN is a random walk-based method. It does multiple causal anonymous walks for each node and extracts relative node identities from the walk results. RNNs are then introduced to encode the anonymous walks. The aggregated walk information forms the final node representation.
- •
EdgeBank (Poursafaei et al., ): EdgeBank is a non-parametric method purely based on memory. It stores the observed interactions in its memory and updates the memory through various strategies. An interaction, i.e., link, will be predicted as existing if it is stored in the memory, and non-existing otherwise. EdgeBank uses four memory update strategies: (1) EdgeBank∞, where all the observed edges are stored in the memory; (2) EdgeBank${}_{\text{tw-ts}}$, where only the edges within the duration of the test set from the immediate past are kept in the memory; (3) EdgeBank${}_{\text{tw-re}}$, where only the edges within the average time intervals of repeated edges from the immediate past are kept in the memory; (4) EdgeBank${}_{\text{th}}$, where the edges with appearing counts higher than a threshold are stored in the memory. The results reported in our paper correspond to the best results achieved among the four memory update strategies.
- •
TCL (Wang et al., ): TCL first extracts temporal dependency interaction sub-graphs for source and interaction nodes and then presents a graph transformer to aggregate node information from the sub-graphs. A cross-attention operation is implemented to enable information communication between two source and destination nodes.
- •
GraphMixer (Cong et al., ): GraphMixer designs a link-encoder based on MLP-Mixer (Tolstikhin et al., ) to learn from the temporal interactions. A mean pooling-based node-encoder is used to aggregate the node features. Link prediction is done with a link classifier that leverages the representations output by link-encoder and node-encoder.

Note that TGN uses a memory network to store the whole graph history, making it able to preserve long-range temporal information. However, as discussed in Yu et al. (), it faces a problem of vanishing/exploding gradients, preventing it from optimally capturing long-term temporal dependencies. EdgeBank can also preserve a very long graph history, but we can observe from the experimental results (Table 1, 12) that without learnable parameters, it is not strong enough on long-range temporal dependent datasets.

### B.2 Baselines Designed for Long-Range Temporal Information Propagation

- •
DyGFormer (Yu et al., ): DyGFormer is a Transformer-based CTDG model. It takes the long-term one-hop temporal interactions of source and destination nodes and uses a Transformer to encode them. A patching technique is developed to cut the computational consumption and a node co-occurrence encoding scheme is used to exploit the correlations of nodes in each interaction. DyGFormer achieves long-range temporal information propagation by increasing the number of sampled one-hop historical interactions. The patching technique ensures that even with a huge number of sampled interactions, the length of the sequence input into Transformer will not be too long, making it possible to implement DyGFormer with a limited computational budget.
- •
CTAN (Gravina et al., ): CTAN is deep graph network for learning CTDGs based on non-dissipative ordinary differential equations. CTAN’s formulation allows for a scalable long-range temporal information propagation in CTDGs because its non-dissipative layer can retain the information from a specific event indefinitely, ensuring that the historical context of a node is preserved despite the occurrence of additional events involving this node.

## Appendix C Implementation Details

We train every CTDG model except for CTAN for a maximum number of 200 epochs. Maximum epochs for CTAN training is 1000. We evaluate each model on the validation set at the end of every training epoch and adopt an early stopping strategy with a patience of 20. We take the model that achieves the best validation result for testing.
We use the implementations(^4^44https://github.com/yule-BUAA/DyGLib) provided by Yu et al. () for all baseline models except CTAN. For CTAN, we use its official implementation(^5^55https://github.com/gravins/non-dissipative-propagation-CTDGs). All models are trained with a batch size of 200 for fair efficiency analysis.
All experiments are implemented with PyTorch (Paszke et al., ) on a server equipped with an AMD EPYC 7513 32-Core Processor and a single NVIDIA A40 with 45GB memory. We run each experiment for five times with five random seeds and report the mean results together with error bars.

### C.1 Hyperparameter Configurations on Real-World Datasets

For all the baselines except CTAN, please refer to Yu et al. () for the hyperparameter configurations on real-world datasets. For CTAN, we present its hyperparameter configurations in Table 9. We keep its hyperparameters unchanged for all real-world datasets. Note that we set the number of graph convolution layers (GCLs) in CTAN to its maximum, i.e., 5, in order to maximize its performance in capturing long-term temporal dependencies.

**Table 9: Hyperparameter configurations of CTAN on all real-world datasets. $\gamma$ here denotes the discretization step size introduced in Gravina et al. (), different from the one in DyGMamba.**
| Model | # GCL | $\epsilon$ | $\gamma$ | Embedding Dim |
| --- | --- | --- | --- | --- |
| CTAN | 5 | 0.5 | 0.5 | 128 |

We report the hyperparameter searching strategy of DyGMamba on real-world datasets and the best hyperparameters in Table 10. To achieve fair efficiency comparison with DyGFormer, we fix the length of the input sequence into the node-level SSM to $32$, i.e., $\rho\ \&\ p=$ 32. The results reported in Table 1, 2, 12, 13 are all achieved by DyGMamba with $\rho\ \&\ p=$ 32. In practice, we can decrease $p$ to have a better performance given more computational resources (as discussed in Sec. 4.3). DyGMamba keeps the embedding size as same as DyGFormer on all real-world datasets, i.e., $d_{N}=d_{E}=$ 172, $d_{T}=$ 100, $d_{F}=$ 50. We also set $\gamma=$ 0.5 for all experiments of DyGMamba. The dimension of SSMs $d_{SSM}$ = 16 remains the default value of mamba SSM’s official repository(^6^66https://github.com/state-spaces/mamba). For all experiments, we set the numbers of layers in both node-level and time-level SSMs as 2.

**Table 10: DyGMamba hyperparameter searching strategy on real-world datasets. The best settings are marked as bold.**
| Datasets | Dropout | $\rho\ \&\ p$ | $k$ |
| --- | --- | --- | --- |
| LastFM | {0.0, 0.1, 0.2} | {1024 & 32, 512 & 16, 256 & 8} | {30, 10, 5} |
| Enron | {0.0, 0.1, 0.2} | {512 & 16, 256 & 8, 128 & 4} | {30, 10, 5} |
| MOOC | {0.0, 0.1, 0.2} | {512 & 16, 256 & 8, 128 & 4} | {30, 10, 5} |
| Reddit | {0.0, 0.1, 0.2} | {128 & 4, 64 & 2, 32 & 1} | {30, 10, 5} |
| Wikipedia | {0.0, 0.1, 0.2} | {64 & 2, 32 & 1} | {30, 10, 5} |
| UCI | {0.0, 0.1, 0.2} | {64 & 2, 32 & 1} | {30, 10, 5} |
| Social Evo. | {0.0, 0.1, 0.2} | {64 & 2, 32 & 1} | {30, 10, 5} |

**Table 11: DyGFormer and DyGMamba hyperparameter searching strategy on synthetic datasets. The best settings are marked as bold.**
| Models | DyGFormer | DyGMamba |  |
| --- | --- | --- | --- |
| Datasets | $\rho\ \&\ p$ | $\rho\ \&\ p$ | $k$ |
| S1 | {512 & 16, 256 & 8, 128 & 4, 64 & 2, 32 & 1} | {512 & 16, 256 & 8, 128 & 4, 64 & 2, 32 & 1} | {30, 10, 5} |
| S2 | {512 & 16, 256 & 8, 128 & 4, 64 & 2, 32 & 1} | {512 & 16, 256 & 8, 128 & 4, 64 & 2, 32 & 1} | {30, 10, 5} |
| S3 | {512 & 16, 256 & 8, 128 & 4, 64 & 2, 32 & 1} | {512 & 16, 256 & 8, 128 & 4, 64 & 2, 32 & 1} | {30, 10, 5} |

### C.2 Hyperparameter Configurations on Synthetic Datasets

We use the same settings of CTAN on real-world datasets when we experiment it on synthetic datasets. For DyGFormer and DyGMamba, we fix the length of the input sequence into the Transformer and the node-level SSM to 32, i.e., $\rho/p=$ 32. For DyGFormer, we set the hyperparameters except $\rho$ and $p$ to the same default values as on real-world datasets, and search for the best $\rho\ \&\ p$ within {512 & 16, 256 & 8, 128 & 4, 64 & 2, 32 & 1}. For DyGMamba, we search for the best $\rho\ \&\ p$ within the same search range and further search for the best $k$. All the other hyperparameters are set as same as the setting on LastFM. We report the hyperparameter searching strategy as well as the best settings of DyGFormer and DyGMamba on synthetic datasets in Table 11. For all experiments with DyGMamba, we set the numbers of layers in both node-level and time-level SSMs as 2.

## Appendix D Negative Edge Sampling Strategies during Evaluation

We justify why we do not do historical NSS for inductive link prediction. As described in Poursafaei et al. (), historical NSS focuses on sampling negative edges from the set of edges that have been observed during previous timestamps but are absent in the current step. In the setting of inductive link prediction, models are asked to predict the links between the nodes unseen in the training dataset. This means when doing historical NSS, models only need to care about the previously observed edges in the test set (or validation set during validation) for choosing negative edges. This makes historical NSS the same as inductive NSS in the inductive link prediction, where inductive NSS samples negative edges that have been observed only in the test set, but not training set. Empirical results shown in Appendix C.2 Table 13 and 14 of Yu et al. () also prove that there is no difference between historical and inductive NSS in inductive link prediction. So we omit the results of historical NSS in our paper.

**Table 12: AUC-ROC of transductive dynamic link prediction.**
| NSS | Datasets | JODIE | DyRep | TGAT | TGN | CAWN | EdgeBank | TCL | GraphMixer | DyGFormer | CTAN | DyGMamba |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Random | LastFM | 70.89 $\pm$ 1.97 | 71.40 $\pm$ 2.12 | 71.47 $\pm$ 0.14 | 76.64 $\pm$ 4.66 | 85.92 $\pm$ 0.16 | 83.77 $\pm$ 0.00 | 71.09 $\pm$ 1.48 | 73.51 $\pm$ 0.14 | 93.03 $\pm$ 0.11 | 85.12 $\pm$ 0.77 | 93.31 $\pm$ 0.18 |
| Enron | 87.77 $\pm$ 2.43 | 83.09 $\pm$ 2.20 | 68.57 $\pm$ 1.46 | 88.72 $\pm$ 0.95 | 90.34 $\pm$ 0.23 | 87.05 $\pm$ 0.00 | 83.33 $\pm$ 0.93 | 84.16 $\pm$ 0.34 | 93.20 $\pm$ 0.12 | 87.09 $\pm$ 1.51 | 93.34 $\pm$ 0.23 |  |
| MOOC | 84.50 $\pm$ 0.60 | 84.50 $\pm$ 0.87 | 87.01 $\pm$ 0.16 | 91.91 $\pm$ 0.82 | 80.48 $\pm$ 0.41 | 60.86 $\pm$ 0.00 | 84.02 $\pm$ 0.59 | 84.04 $\pm$ 0.12 | 88.08 $\pm$ 0.50 | 85.40 $\pm$ 2.67 | 89.58 $\pm$ 0.12 |  |
| Reddit | 98.29 $\pm$ 0.05 | 98.13 $\pm$ 0.04 | 98.50 $\pm$ 0.01 | 98.61 $\pm$ 0.05 | 99.02 $\pm$ 0.00 | 95.37 $\pm$ 0.00 | 97.67 $\pm$ 0.01 | 97.17 $\pm$ 0.02 | 99.15 $\pm$ 0.01 | 97.24 $\pm$ 0.75 | 99.27 $\pm$ 0.01 |  |
| Wikipedia | 96.36 $\pm$ 0.14 | 94.43 $\pm$ 0.32 | 96.60 $\pm$ 0.07 | 98.37 $\pm$ 0.10 | 98.54 $\pm$ 0.01 | 90.78 $\pm$ 0.00 | 97.27 $\pm$ 0.06 | 96.89 $\pm$ 0.04 | 98.92 $\pm$ 0.03 | 97.00 $\pm$ 0.21 | 99.08 $\pm$ 0.02 |  |
| UCI | 90.35 $\pm$ 0.51 | 69.46 $\pm$ 2.66 | 78.76 $\pm$ 1.10 | 92.03 $\pm$ 0.69 | 93.81 $\pm$ 0.23 | 77.30 $\pm$ 0.00 | 85.49 $\pm$ 0.82 | 91.62 $\pm$ 0.52 | 94.45 $\pm$ 0.22 | 76.25 $\pm$ 2.83 | 94.77 $\pm$ 0.18 |  |
| Social Evo. | 92.13 $\pm$ 0.20 | 90.37 $\pm$ 0.52 | 94.93 $\pm$ 0.06 | 95.31 $\pm$ 0.27 | 87.34 $\pm$ 0.10 | 81.60 $\pm$ 0.00 | 95.45 $\pm$ 0.21 | 95.21 $\pm$ 0.07 | 96.25 $\pm$ 0.04 | Timeout | 96.38 $\pm$ 0.02 |  |
|  | Avg. Rank | 7.14 | 8.86 | 7.14 | 3.86 | 4.86 | 9.14 | 7.29 | 7.14 | 2.14 | 7.29 | 1.14 |
| Historical | LastFM | 75.65 $\pm$ 4.43 | 70.63 $\pm$ 2.56 | 64.23 $\pm$ 0.45 | 78.00 $\pm$ 2.97 | 67.92 $\pm$ 0.32 | 78.09 $\pm$ 0.00 | 60.53 $\pm$ 2.54 | 64.06 $\pm$ 0.34 | 78.80 $\pm$ 0.02 | 79.50 $\pm$ 0.82 | 79.82 $\pm$ 0.27 |
| Enron | 75.21 $\pm$ 1.27 | 76.36 $\pm$ 1.42 | 62.36 $\pm$ 1.07 | 76.75 $\pm$ 1.40 | 65.62 $\pm$ 0.49 | 79.59 $\pm$ 0.00 | 71.72 $\pm$ 1.24 | 74.82 $\pm$ 2.04 | 77.35 $\pm$ 0.64 | 81.95 $\pm$ 1.64 | 77.73 $\pm$ 0.61 |  |
| MOOC | 82.38 $\pm$ 1.75 | 80.71 $\pm$ 2.08 | 81.53 $\pm$ 0.79 | 86.59 $\pm$ 2.03 | 71.74 $\pm$ 0.88 | 61.90 $\pm$ 0.00 | 73.22 $\pm$ 1.21 | 77.09 $\pm$ 0.83 | 87.26 $\pm$ 0.83 | 73.87 $\pm$ 2.77 | 87.91 $\pm$ 0.93 |  |
| Reddit | 80.70 $\pm$ 0.20 | 79.96 $\pm$ 0.23 | 79.60 $\pm$ 0.09 | 81.04 $\pm$ 0.23 | 80.42 $\pm$ 0.20 | 78.58 $\pm$ 0.00 | 76.83 $\pm$ 0.12 | 77.83 $\pm$ 0.33 | 80.61 $\pm$ 0.48 | 90.63 $\pm$ 2.28 | 81.71 $\pm$ 0.49 |  |
| Wikipedia | 80.71 $\pm$ 0.64 | 77.49 $\pm$ 0.72 | 82.83 $\pm$ 0.27 | 83.28 $\pm$ 0.26 | 65.74 $\pm$ 3.46 | 77.27 $\pm$ 0.00 | 85.55 $\pm$ 0.47 | 87.47 $\pm$ 0.20 | 72.78 $\pm$ 6.65 | 95.43 $\pm$ 0.07 | 78.99 $\pm$ 1.24 |  |
| UCI | 78.21 $\pm$ 3.18 | 58.65 $\pm$ 3.58 | 57.12 $\pm$ 0.98 | 78.48 $\pm$ 1.79 | 57.67 $\pm$ 1.11 | 69.56 $\pm$ 0.00 | 65.42 $\pm$ 2.62 | 77.46 $\pm$ 1.63 | 75.71 $\pm$ 0.57 | 75.05 $\pm$ 0.13 | 75.43 $\pm$ 1.99 |  |
| Social Evo. | 91.83 $\pm$ 1.52 | 92.81 $\pm$ 0.60 | 93.63 $\pm$ 0.48 | 94.27 $\pm$ 1.33 | 87.61 $\pm$ 0.06 | 85.81 $\pm$ 0.00 | 95.03 $\pm$ 0.82 | 94.65 $\pm$ 0.28 | 97.16 $\pm$ 0.06 | Timeout | 97.27 $\pm$ 0.30 |  |
|  | Avg. Rank | 5.29 | 7.14 | 7.86 | 3.71 | 9.14 | 7.43 | 7.71 | 6.29 | 4.29 | 4.29 | 2.86 |
| Inductive | LastFM | 61.59 $\pm$ 5.72 | 60.62 $\pm$ 2.20 | 63.96 $\pm$ 0.41 | 65.48 $\pm$ 4.13 | 67.90 $\pm$ 0.44 | 77.37 $\pm$ 0.00 | 54.75 $\pm$ 1.31 | 59.98 $\pm$ 0.20 | 67.87 $\pm$ 0.53 | 78.70 $\pm$ 0.87 | 68.74 $\pm$ 0.55 |
| Enron | 70.75 $\pm$ 0.69 | 67.37 $\pm$ 2.21 | 59.78 $\pm$ 1.12 | 73.22 $\pm$ 0.42 | 75.29 $\pm$ 0.66 | 75.00 $\pm$ 0.00 | 69.74 $\pm$ 1.19 | 70.72 $\pm$ 1.08 | 74.67 $\pm$ 0.80 | 75.40 $\pm$ 1.92 | 75.47 $\pm$ 1.41 |  |
| MOOC | 67.53 $\pm$ 1.76 | 62.60 $\pm$ 1.27 | 74.44 $\pm$ 0.81 | 76.89 $\pm$ 2.13 | 70.08 $\pm$ 0.33 | 48.18 $\pm$ 0.00 | 71.80 $\pm$ 1.09 | 72.25 $\pm$ 0.57 | 80.78 $\pm$ 0.89 | 68.17 $\pm$ 3.73 | 81.08 $\pm$ 0.82 |  |
| Reddit | 83.40 $\pm$ 0.33 | 82.75 $\pm$ 0.36 | 87.46 $\pm$ 0.10 | 84.57 $\pm$ 0.19 | 88.19 $\pm$ 0.20 | 85.93 $\pm$ 0.00 | 84.41 $\pm$ 0.18 | 82.24 $\pm$ 0.24 | 86.25 $\pm$ 0.64 | 91.42 $\pm$ 2.18 | 86.35 $\pm$ 0.52 |  |
| Wikipedia | 70.41 $\pm$ 0.39 | 67.57 $\pm$ 0.94 | 81.54 $\pm$ 0.31 | 81.21 $\pm$ 0.30 | 68.48 $\pm$ 3.64 | 81.73 $\pm$ 0.00 | 73.51 $\pm$ 1.88 | 84.20 $\pm$ 0.36 | 64.09 $\pm$ 9.75 | 93.67 $\pm$ 0.11 | 75.64 $\pm$ 2.42 |  |
| UCI | 64.14 $\pm$ 1.25 | 54.10 $\pm$ 2.74 | 59.60 $\pm$ 0.61 | 63.76 $\pm$ 0.99 | 57.85 $\pm$ 0.59 | 58.03 $\pm$ 0.00 | 65.46 $\pm$ 2.07 | 74.25 $\pm$ 0.71 | 64.92 $\pm$ 0.83 | 66.51 $\pm$ 0.25 | 66.83 $\pm$ 2.83 |  |
| Social Evo. | 91.81 $\pm$ 1.69 | 92.77 $\pm$ 0.64 | 93.54 $\pm$ 0.48 | 94.86 $\pm$ 1.25 | 90.10 $\pm$ 0.11 | 87.88 $\pm$ 0.00 | 95.13 $\pm$ 0.83 | 94.50 $\pm$ 0.26 | 95.01 $\pm$ 0.15 | Timeout | 97.37 $\pm$ 0.26 |  |
|  | Avg. Rank | 7.86 | 9.57 | 6.14 | 5.43 | 6.29 | 6.43 | 6.71 | 6.00 | 5.14 | 3.86 | 2.57 |

## Appendix E AUC-ROC Results on Real-World Datasets

Table 12 and 13 presents the AUC-ROC results of all baselines and DyGMamba on real-world datasets. We have similar observations as the AP results shown in Table 1 and 2. DyGMamba still demonstrates superior performance and can achieve the best average rank under any NSS setting in both transductive and inductive link prediction.

**Table 13: AUC-ROC of inductive dynamic link prediction. EdgeBank cannot do inductive link prediction so is not reported.**
| NSS | Datasets | JODIE | DyRep | TGAT | TGN | CAWN | TCL | GraphMixer | DyGFormer | CTAN | DyGMamba |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Random | LastFM | 82.49 $\pm$ 0.94 | 82.82 $\pm$ 1.17 | 76.76 $\pm$ 0.22 | 82.61 $\pm$ 2.62 | 87.92 $\pm$ 0.15 | 76.95 $\pm$ 1.34 | 80.34 $\pm$ 0.14 | 94.10 $\pm$ 0.09 | 61.49 $\pm$ 2.78 | 94.37 $\pm$ 0.13 |
| Enron | 80.16 $\pm$ 1.50 | 75.82 $\pm$ 3.14 | 64.25 $\pm$ 1.29 | 79.40 $\pm$ 1.77 | 86.84 $\pm$ 0.89 | 81.03 $\pm$ 0.93 | 76.08 $\pm$ 0.92 | 89.59 $\pm$ 0.10 | 75.23 $\pm$ 2.24 | 89.76 $\pm$ 0.21 |  |
| MOOC | 83.82 $\pm$ 0.30 | 83.42 $\pm$ 0.77 | 86.67 $\pm$ 0.24 | 91.58 $\pm$ 0.74 | 81.76 $\pm$ 0.46 | 82.42 $\pm$ 0.71 | 82.76 $\pm$ 0.13 | 87.75 $\pm$ 0.42 | 66.38 $\pm$ 1.59 | 89.34 $\pm$ 0.12 |  |
| Reddit | 96.42 $\pm$ 0.13 | 95.87 $\pm$ 0.21 | 97.02 $\pm$ 0.04 | 97.30 $\pm$ 0.12 | 98.42 $\pm$ 0.01 | 94.63 $\pm$ 0.08 | 94.95 $\pm$ 0.08 | 98.70 $\pm$ 0.02 | 82.35 $\pm$ 4.03 | 98.88 $\pm$ 0.01 |  |
| Wikipedia | 94.43 $\pm$ 0.28 | 91.31 $\pm$ 0.40 | 95.93 $\pm$ 0.19 | 97.71 $\pm$ 0.19 | 98.05 $\pm$ 0.03 | 97.03 $\pm$ 0.08 | 96.26 $\pm$ 0.04 | 98.49 $\pm$ 0.02 | 92.59 $\pm$ 0.70 | 98.72 $\pm$ 0.03 |  |
| UCI | 78.78 $\pm$ 1.11 | 58.84 $\pm$ 2.54 | 77.41 $\pm$ 0.65 | 86.27 $\pm$ 1.49 | 90.27 $\pm$ 0.40 | 81.67 $\pm$ 1.01 | 89.26 $\pm$ 0.42 | 92.43 $\pm$ 0.20 | 48.58 $\pm$ 6.02 | 92.70 $\pm$ 0.19 |  |
| Social Evo. | 93.62 $\pm$ 0.36 | 90.20 $\pm$ 2.05 | 93.52 $\pm$ 0.05 | 93.21 $\pm$ 0.90 | 84.73 $\pm$ 0.20 | 94.63 $\pm$ 0.06 | 94.09 $\pm$ 0.03 | 95.30 $\pm$ 0.05 | Timeout | 95.36 $\pm$ 0.04 |  |
|  | Avg. Rank | 6.00 | 7.43 | 7.00 | 4.57 | 4.71 | 6.14 | 6.14 | 2.14 | 9.71 | 1.14 |
| Inductive | LastFM | 69.85 $\pm$ 1.70 | 68.14 $\pm$ 1.61 | 69.89 $\pm$ 0.41 | 67.01 $\pm$ 5.77 | 67.72 $\pm$ 0.20 | 63.15 $\pm$ 1.17 | 69.93 $\pm$ 0.17 | 69.86 $\pm$ 0.80 | 57.85 $\pm$ 3.67 | 70.59 $\pm$ 0.57 |
| Enron | 65.95 $\pm$ 1.27 | 62.20 $\pm$ 2.15 | 56.52 $\pm$ 0.84 | 64.21 $\pm$ 0.94 | 62.07 $\pm$ 0.72 | 67.56 $\pm$ 1.34 | 67.39 $\pm$ 1.33 | 66.07 $\pm$ 0.65 | 68.70 $\pm$ 1.82 | 68.98 $\pm$ 1.00 |  |
| MOOC | 65.37 $\pm$ 0.96 | 62.97 $\pm$ 2.05 | 74.94 $\pm$ 0.80 | 76.36 $\pm$ 2.91 | 71.18 $\pm$ 0.54 | 71.30 $\pm$ 1.21 | 72.15 $\pm$ 0.65 | 80.42 $\pm$ 0.72 | 58.06 $\pm$ 0.89 | 81.12 $\pm$ 0.63 |  |
| Reddit | 61.84 $\pm$ 0.44 | 60.35 $\pm$ 0.53 | 64.92 $\pm$ 0.08 | 65.24 $\pm$ 0.08 | 65.37 $\pm$ 0.12 | 61.85 $\pm$ 0.11 | 64.56 $\pm$ 0.26 | 64.80 $\pm$ 0.53 | 81.70 $\pm$ 4.71 | 64.93 $\pm$ 0.89 |  |
| Wikipedia | 61.66 $\pm$ 0.30 | 56.34 $\pm$ 0.67 | 78.40 $\pm$ 0.77 | 75.86 $\pm$ 0.50 | 59.00 $\pm$ 4.33 | 71.45 $\pm$ 2.23 | 82.76 $\pm$ 0.11 | 58.21 $\pm$ 8.78 | 91.12 $\pm$ 0.13 | 67.92 $\pm$ 2.23 |  |
| UCI | 60.66 $\pm$ 1.82 | 51.50 $\pm$ 2.08 | 61.27 $\pm$ 0.78 | 62.07 $\pm$ 0.67 | 55.60 $\pm$ 1.22 | 65.87 $\pm$ 1.90 | 75.72 $\pm$ 0.70 | 64.37 $\pm$ 0.98 | 51.68 $\pm$ 2.60 | 66.95 $\pm$ 2.22 |  |
| Social Evo. | 88.98 $\pm$ 0.81 | 86.43 $\pm$ 1.48 | 92.37 $\pm$ 0.50 | 91.66 $\pm$ 2.14 | 83.84 $\pm$ 0.21 | 95.50 $\pm$ 0.31 | 93.88 $\pm$ 0.22 | 94.97 $\pm$ 0.36 | Timeout | 96.65 $\pm$ 0.29 |  |
|  | Avg. Rank | 7.00 | 8.71 | 5.14 | 5.14 | 7.14 | 5.14 | 3.57 | 4.71 | 6.14 | 2.29 |

## Appendix F Dynamic Node Classification

We first give the definition of the dynamic node classification task.

###### Definition 3 (Dynamic Node Classification) .

Given a CTDG $\mathcal{G}$, a source node $u\in\mathcal{N}$, a destination node $v\in\mathcal{N}$, a timestamp $t\in\mathcal{T}$, and all the interactions before $t$, i.e., $\{(u_{i},v_{i},t_{i})|t_{i}<t,(u_{i},v_{i},t_{i})\in\mathcal{G}\}$, dynamic node classification aims to predict the state (e.g., dynamic node label) of $u$ or $v$ at $t$ in the condition that the interaction $(u,v,t)$ exists.

We follow Rossi et al. (); Xu et al. (); Yu et al. () to conduct dynamic node classification by estimating the state of a node in a given interaction at a specific timestamp. A classification MLP is employed to map the node representations as well as the learned temporal patterns to the labels. AUC-ROC is used as the evaluation metric and we follow the dataset splits introduced in Yu et al. () (70%15%/15% for training/validation/testing in chronological order) for node classification. Table 14 shows the node classification results on Wikipedia and Reddit (the only two CTDG datasets for dynamic node classfication), we observe that DyGMamba can achieve the best average rank, showing its strong performance. Note that both Wikipedia and Reddit are not long-range temporal dependent datasets, therefore we do not include this part into the main body of the paper. Nonetheless, DyGMamba’s great results on these datasets further prove its strength in CTDG modeling, regardless of the type of the dataset (whether long-range temporal dependent or not).

**Table 14: AUC-ROC of dynamic node classification.**
| Datasets | JODIE | DyRep | TGAT | TGN | CAWN | TCL | GraphMixer | DyGFormer | CTAN | DyGMamba |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Wikipedia | 88.10 $\pm$ 1.57 | 87.41 $\pm$ 1.94 | 83.42 $\pm$ 2.92 | 85.51 $\pm$ 3.28 | 84.59 $\pm$ 1.16 | 79.03 $\pm$ 1.18 | 85.60 $\pm$ 1.73 | 86.35 $\pm$ 2.19 | 87.38 $\pm$ 0.14 | 87.44 $\pm$ 0.82 |
| Reddit | 59.53 $\pm$ 3.18 | 63.12 $\pm$ 0.51 | 69.31 $\pm$ 2.18 | 63.21 $\pm$ 3.00 | 65.22 $\pm$ 0.79 | 68.04 $\pm$ 2.00 | 64.42 $\pm$ 1.15 | 67.67 $\pm$ 1.39 | 67.29 $\pm$ 0.15 | 67.70 $\pm$ 1.32 |
| Avg. Rank | 5.50 | 6.00 | 5.00 | 7.50 | 7.00 | 6.00 | 6.50 | 4.50 | 4.50 | 2.50 |

###### Definition 3 (Dynamic Node Classification) .

## Appendix G Efficieny Analysis Complete Results

We first provide the efficiency analysis results of all baselines in this section. We then provide a comparison of total training time among DyGFormer, CTAN and DyGMamba.

### G.1 Efficiency Statistics for all baselines

We provide the efficiency statistics for all baselines in Table 15.

**Table 15: Efficiency statistics for all baselines. EdgeBank is non-parameterized and not a machine learning model so we omit it here. # Params means number of parameters (MB). Time and Mem denote per epoch training time (min) and GPU memory (GB), respectively. The numbers in this table are the average results of five runs with different random seeds.**
| Datasets | LastFM | Enron | MOOC | UCI |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Models | # Params | Time | Mem | # Params | Time | Mem | # Params | Time | Mem | # Params | Time | Mem |
| JODIE | 0.75 | 4.4 | 2.28 | 0.75 | 0.07 | 1.30 | 0.75 | 0.78 | 2.36 | 0.75 | 0.03 | 1.44 |
| DyRep | 2.64 | 6.6 | 2.29 | 2.64 | 0.10 | 1.34 | 2.64 | 0.88 | 2.38 | 2.64 | 0.05 | 1.51 |
| TGAT | 4.02 | 22.75 | 4.15 | 4.02 | 1.28 | 3.46 | 4.02 | 4.08 | 3.64 | 4.02 | 0.60 | 3.42 |
| TGN | 3.68 | 12.14 | 2.21 | 3.68 | 0.15 | 1.45 | 3.68 | 1.03 | 2.54 | 3.68 | 0.08 | 1.51 |
| CAWN | 15.35 | 99.00 | 14.92 | 15.35 | 2.62 | 4.03 | 15.35 | 13.45 | 8.02 | 15.35 | 1.95 | 9.40 |
| TCL | 3.37 | 6.23 | 3.04 | 3.37 | 0.30 | 2.51 | 3.37 | 1.00 | 2.49 | 3.37 | 0.13 | 2.00 |
| GraphMixer | 2.45 | 16.35 | 2.78 | 2.45 | 1.20 | 2.23 | 2.45 | 4.02 | 2.40 | 2.45 | 0.73 | 2.19 |
| DyGFormer | 5.56 | 47.00 | 7.57 | 4.80 | 2.73 | 3.23 | 4.80 | 8.32 | 3.35 | 4.15 | 0.62 | 2.30 |
| CTAN | 0.45 | 3.33 | 1.44 | 0.47 | 0.50 | 1.33 | 0.68 | 3.22 | 2.30 | 0.50 | 0.38 | 1.30 |
| DyGMamba | 2.78 | 28.45 | 4.17 | 2.03 | 2.05 | 2.74 | 1.65 | 4.88 | 2.48 | 1.37 | 0.60 | 1.93 |

**Table 16: Comparison among DyGFormer, CTAN and DyGMamba on per epoch training time (T${}_{\text{ep}}$ (min)), number of epochs until the best performance (# Epoch) and the total training time (T${}_{\text{tot}}$ (min)). $\text{T}_{\text{tot}}=\text{T}_{\text{ep}}\times$ # Epoch. The numbers in this table are the average results of five runs with different random seeds.**
| Datasets | LastFM | Enron | MOOC | UCI |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Models | T${}_{\text{ep}}$ | # Epoch | T${}_{\text{tot}}$ | T${}_{\text{ep}}$ | # Epoch | T${}_{\text{tot}}$ | T${}_{\text{ep}}$ | # Epoch | T${}_{\text{tot}}$ | T${}_{\text{ep}}$ | # Epoch | T${}_{\text{tot}}$ |
| DyGFormer | 47.00 | 49.60 | 2331.20 | 2.73 | 32.80 | 89.54 | 8.32 | 64.20 | 534.14 | 0.62 | 34.80 | 21.58 |
| CTAN | 3.33 | 635.00 | 2114.55 | 0.50 | 173.00 | 86.50 | 3.22 | 138.00 | 444.36 | 0.38 | 236.00 | 89.68 |
| DyGMamba | 28.45 | 11.80 | 335.71 | 2.05 | 33.00 | 67.65 | 4.88 | 38.00 | 185.44 | 0.60 | 28.00 | 16.80 |

### G.2 Total Training Time Comparison among DyGFormer, CTAN and DyGMamba

We present the per epoch training time, number of epochs until the best performance and the total training time in Table 16. Total training time computes the total amount of time a model requires to reach its maximum performance, without considering the patience during training. We observe that CTAN requires much more epochs to converge, e.g., on LastFM it uses almost 54 times of epochs than DyGMamba to reach its best performance.

### G.3 Modeling an Increasing Number of Temporal Neighbors with Limited Total Training Time

Figure: Figure 6: Performance comparison among TGN, CAWN, DyGFormer, CTAN and DyGMamba on Enron, with an increasing number of encoded temporal neighbors. The metric is AP under random NSS on transductive link prediction. The time limit for training is 120 min. If a model fails to complete training within this limit, a cross $\times$ is used to mark the data point. Dashed lines indicate that models start to exceed time limit as neighbor number increases.
Refer to caption: extracted/5900153/pics/dygmamba_limited_budget.png

To further show DyGMamba’s superior efficiency against baseline methods, we do the following experiments. We train five best performing models (as shown in Table 1) on Enron with a gradually increasing number of temporal neighbors(^7^77For CTAN, by number of temporal neighbors we mean the sampler size in each graph convolutional layer, i.e., the size of the sampled temporal neighborhood for each node at a timestamp.) and report their performance. The number of sampled neighbors spans from 8, 16, 32, 64, 128 to 256 (Note that these numbers are different from the best hyperparameters reported in Yu et al. ()). We fix the patch size $p$ of DyGFormer and DyGMamba to $1$ in order to maximize their input sequence lengths. We set a time limit of 120 minutes for the total training time. We let all the experiments finish the complete training process and note down the ones that exceed the time limit. In this way, we not only care about the per epoch training time, but also pay attention to how long it takes for models to converge.
The experimental results are reported in Fig. 6. The points marked with crosses ($\times$) mean that the training process cannot finish within the time limit (although we still plot their corresponding performance). We find that only TGN and DyGMamba can successfully converge within the time limit when the number of considered neighbors increases to 256. DyGMamba can constantly achieve performance gain from modeling more temporal neighbors while TGN cannot. CAWN is extremely time consuming so it cannot finish training within the time limit even when it is asked to model 16 temporal neighbors. As for the methods designed for long-range temporal information propagation, DyGFormer and CTAN consume much longer total training time than DyGMamba. They fail to converge within 120 minutes when the number of considered neighbors reaches 128 and 256, respectively.
We also observe that CTAN’s performance fluctuates greatly with the increasing temporal neighbors, indicating that it is not stable to model a large number of temporal neighbors.
This also implies that increasing the amount of historical information will gradually make CTAN harder to converge, which might cause trouble in modeling long range temporal dependent datasets.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please consider the raised concerns in the above section.
soundness: 2
strengths: 1. The research problem is interesting, and the link prediction is a pragmatic and important application.

2. The study has the potential to solve the dynamic representation learning and applications from the Mamba perspective.

3. The paper's organization is not hard to follow.
summary: This paper studies how the Mamba model can solve the continuous-time dynamic graphs, especially focusing on the dynamic link prediction problem. The research problem is interesting, and investigating the new neural architecture for graph representation learning is exciting. A detailed review of the pros and cons can be seen in the following sections.
weaknesses: 1. [Minor] The preliminary section is not informative. In a better way, the preliminary should pave the way for illustrating the proposed method. So far, the illustration of Mamba is not clear, and the connection of the illustration with the proposed method is not well aligned. Also, the dimension in Eq (1a) seems inconsistent for the matrix computation.

2. For Eq. (4a) the computation procedure for $Broadcast\_{4d}$ is missing. Also, in Eq (4d), the computation procedure for $SSM\_{A,B,C}$ is also missing. Only the sentence "similar to Eq.2" is inadequate, for example, what is the relation between $H_{\theta}^{t}$ with $p_{\tau}$ and $q_{\tau}$?

3. The motivation and the necessity of using Mamba for dynamic graph learning are not that clear. Section 3.2 and Section 3.3 pay much attention to introducing the equation. However, the motivation and intuition for those equations are missing. For example, for the proposed "Dynamic Information Selection with Temporal Patterns", what is being selected and what is being filtered? Correspondingly, the ablation study design is reasonable, but the explanation is not adequate.

4. The experimental design follows the SOTA, i.e., DyGformer, which makes it good and easy to evaluate the performance of the proposed DyGMaba. Why are the selected datasets and sampling methods truncated from the full version of DyGformer? For example, 6 of 13 given datasets are not included, and one sampling method is not fully explored.

5. Between lines 526 to 529, more derivation for the complexity conclusion will be appreciated.

6. Overall, the theoretical contribution seems incremental.

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 2
questions: See the weakness.
soundness: 2
strengths: 1. The experiments are extensive.
summary: This paper proposes a novel continuous-time dynamic graphs (CTDGs) representation model named DyGMamba to address the challenges of learning long-term temporal dependencies. DyGMemba consists of a node-level state space model (SSM) and edge-level SSM, which aims to learn the node-level and edge-level representations, respectively. The outputs of node-level SSM and edge-level SSM are combined for future link prediction. The authors conduct extensive experiments to evaluate DyGMamba.
weaknesses: 1. The novelty of this work is low. Some important modules are highly similar to existing works. In specific: 
   - In Section 3.1,  The "Encode Neighbor Features" and " Patching Neighbors" sections are highly similar to DyGFormer [1]. 
   - The main network architecture is taken from original Mamba [2], without incorporating structure information of dynamic graph (see Eq. 5, 6 and 7).  

2. The authors claim that applying Mamba for dynamic graph learning is to address the challenge of computation complexity in capturing very long-term temporal dependencies. This raises several concerns: 

   - Why should we learn from very long history? Intuitively, very long history should be discarded since it has minor impact on current event. In addition, in Fig 3 (a), the performance of DyGFormer and variant A is not increasing as sequence length increases. This supports that the model performance does not necessarily increase as sequence length increases.

   - In addition, I think DyGFormer has address the problem of learning long-term dependencies by its patching technique. It can learn very long history if its patch size is large enough. 

3. What is "critical temporal information" mentioned in Line 54? How to define it? Is there evidence that DyGMamba can indeed capture this?  

4. The performance improvement of DyGMamba is marginal (Table 1 and 2). Most improvements are within 0.5\%.
 
5. In Fig.3, why the experiments are only conducted on Enron? More datasets should be included.  

[1] Yu L, Sun L, Du B, et al. Towards better dynamic graph learning: New architecture and unified library[J]. Advances in Neural Information Processing Systems, 2023, 36: 67686-67700. 

[2] Gu A, Dao T. Mamba: Linear-time sequence modeling with selective state spaces[J]. arXiv preprint arXiv:2312.00752, 2023.

---

confidence: 5
contribution: 3
initial_rating: 8
presentation: 3
questions: See weaknesses part.
soundness: 4
strengths: This is arguably the first Mamba model for dynamic graph representation learning, and I think the long context modeling ability of Mamba is suitable for temporal graph learning. I appreciate the designs of two types of SSM blocks that consider both node-level and edge-level information, both of which encode critical information about temporal patterns. The proposed DyGMamba has a satisfactory performance by outperforming baseline methods with higher accuracy in link prediction, shorter training time (per epoch and in total), and less memory usage compared to DyGFormer.
summary: This paper proposes a Mamba model for representation learning on continuous-time dynamic graphs. It has a node-level SSM to encode node interactions over time and a time-level SSM to encode edge-specific temporal information. Both representations are interleaved for dynamic information selection.
weaknesses: The overall design of DyGMamba makes sense to me, as it basically employs SSM block for node features and edge features. I have a few questions regarding the experiments in this paper.

* All datasets used in this paper do not have node features. Based on TGAT, I assume the authors are using all-zero vectors as node features. I wonder how DyGMamba would perform when there are node features, e.g., on GDELT dataset.

* Meanwhile, ablation study in Tables 3 and 4 are interesting. As you shift from transductive setting to inductive setting, Variant A has slightly worse performance compared to Variant B consistently on LastFM, Enron, and MOOC. Could the authors offer theoretical insights on why this happens? I do not see any specific patterns on these 3 datasets from the statistics in Table 6. Is there any specific design of node-level SSM or edge-level SSM would cause this 
performance change? If yes, is there any insights that could offer to users when deploying this model to other data?

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: Please check the questions mentioned in the weaknesses.
soundness: 2
strengths: S1. The introduction to the proposed method is detailed and useful for the readers to understand every module and architecture.
S2. The baseline methods used in this paper is state-of-the-art and recent.
S3. This paper includes 7 datasets with 3 different negative sampling strategies (NSS) which makes the experimental section comprehensive.
summary: This paper studies the link prediction problem on continuous-time dynamic graphs. The main technique this paper used is the Mamba state space model (SSM).
weaknesses: W1. Seems that the main body of the model is based on a mature model Mamba, e.g., Eqs. 4a-4d, and Eqs. 6a-6d. Looks like there are existing works using Mamba on graphs, e.g, [1], which undermines the novelty of the proposed method.

W2. Some of the model designs are not reasonable or questionable to me. I will detail them as follows.

W2.1 Lines 182-190 introduce the counting of interaction frequency. However, it is still pretty vague why the frequency features are formed like that in lines 184 and 185. E.g., why there are 5 rows in F_u^t, and why both F_u^t and F_v^t have 2 columns. In addition, why the encoding of 2 columns of F_u^t uses a shared MLP (in line 189)? In other words, why not use an MLP: from R^2 to R^{d_f}?

W2.2 Lines 191 and 192 mentioned that it can save computation resources. If I understood correctly, by such a patching, the time complexity to encode the X_u^t will increase because the matrix has more columns (features), but the SSMs module can be faster because there are fewer rows (in lines 198 and 199), right?

W2.3 The section named “Dynamic Information Selection with Temporal Patterns” (line 255) seems to be the core module of the proposed method, which is related to the “edge-specific temporal pattern”. However, I think the edge information has been included in the Node-Level SSM Block (Eq. 3). Then, why repeatedly use the edge information, and what is any rationale regarding this?

W3. Regarding the experimental results, looks like under the “random” negative sampling strategy (NSS) the proposed method performs very well, but under the historical and inductive NSS setting, the proposed method can only beat ~ half of the SOTAs. 

W4. The writing of this paper is somewhat sloppy. I detail them as follows.
W4.1 As some modules of this paper are modified from the standard S4 and Mamba SSM, I checked the dimension and introduction for the backbone model between lines 125 and 140. However, a lot of them are confusing. (i) In Eq 1a, do matrices Az(\tau) and Bq(\tau) with the same dimensions? Looks like Bq(\tau) is of the shape 1 x d1 but the matrix A is of the shape d1 x d1, so the matrix Az(\tau) is of the shape d1 x (?), which cannot have the same shape as Bq(\tau). The same problem to r(\tau), which is a scalar, but from the second eq in Eq 1a, r(\tau)=Cz(\tau), and the shape of the matrix C is d1 x 1; in other words, it is not clear whether r(\tau) is a scalar or vector.

W4.2 In line 136, I think d2 was not mentioned in previous content. Also, why is the model in a SISO fashion when d_2>1? I am not familiar with this backbone model, but this statement is not intuitive to me.

W4.3 The end of Line 161 should be |Nei_u^t| but not Nei_u^t.

[1] Behrouz, Ali, and Farnoosh Hashemi. "Graph mamba: Towards learning on graphs with state space models." Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: 1. In the experiment illustrated in Fig. 4, which evaluates the scalability with varying numbers of neighbors, the analysis is conducted using the Enron dataset. However, the Enron dataset has an average degree of 676, meaning that only a small number of nodes have more than 676 neighbors. Have you considered the implications of this situation, where only a few nodes exceed this average degree? Could you discuss how this may influence the results presented in Fig. 4?


2. In Figure 3a, why does the performance of DyGFormer decrease as the number of patches decreases, while the performance of DyGMamba increases? Could you provide some reasoning or discussion to explain this phenomenon?

3. DyGFormer is a general framework designed to address the Continuous-Time Dynamic Graph (CTDG) problem, employing mean pooling to merge final node representations. In contrast, DyGMamba utilizes a short time-difference sequence to parameterize a weighted pooling mechanism instead of mean pooling. Based on the results from Variant A, I believe that Section 3.2 contributes to the observed performance gains.
However, I have the following questions: 
- Is the Mamba structure necessary within the Time-Level SSM Block? From my perspective, both Mamba and Transformer can capture long-sequence dependencies, and Mamba has been shown to operate as a linear attention mechanism [2]. Therefore, the performance upper bound might be that of the Transformer itself or a Transformer with causal attention. **Could you explain why Mamba is used for such short sequences in Section 3.2? Additionally, please provide a comparison with the Transformer structure**. 
- Is time-difference encoding essential for the pooling strategy? After experimenting with your code and removing Equations (6a–7c) by setting $\beta=Softmax(Linear(H))$ in Eq. (7d) [1], I observed that the performance remains strong. This raises **the question of whether time-difference encoding is necessary in your design**. It seems likely that the performance gain results from weighted pooling versus mean pooling, rather than from time-difference encoded weighted pooling.
- To justify the inclusion of Mamba in Section 3.2, you should consider applying "Dynamic Information Selection" to DyGFormer. Possible comparisons could include: **1. DyGFormer with dynamic information selection; 2. DyGFormer with dynamic information selection using the Transformer structure instead;** 


4. As analyzed in W1, the introduction of Mamba appears to harm the performance of the DyGFormer structure, so further analysis of the reasons behind this would be helpful. More importantly, **beyond the efficiency gains from the Mamba structure and patching techniques, could you please clarify the contributions of DyGMamba?**



5. In Section 3.2, lines 250–254, the part regarding "enabling batch processing" is difficult to follow. It’s unclear how using only 10 neighbors could lead to such a large value. **Could you provide details on the batch processing—specifically, whether it follows the same batching process as DyGFormer?** Additionally, how was the figure $10^{10}$ derived?



6. The explanation of "Dynamic Information Selection" is generally unclear. There is no evidence about why the specific design in Equation 7 was chosen or what advantages it offers. Additionally, it’s not clear how this design effectively achieves selection. Could you provide a more thorough explanation of the intuition behind the Dynamic Information Selection mechanism and clarify **its benefits compared to other weighted pooling mechanisms?**


7. Furthermore, other references for the State space model on dynamic graph learning should be added, such as [3], and the state-space model's applications on graphs should be discussed, such as [4].

8. Finally, if the Mamba structure is not a key component of your design and the performance gains stem primarily from the pooling mechanism, demonstrating its effectiveness across other CTDG methods would be better for the paper. **Integrating "Dynamic Information Selection" with other methods**, such as FreeDyG, GraphMixer, and CTAN, to show performance improvements could clear the value of this component.


**References:** \
[1] Language Modeling with Gated Convolutional Networks, ICML, 2017. \
[2] Mamba: Linear-Time Sequence Modeling with Selective State Spaces, arxiv, 2023. \
[3] STG-Mamba: Spatial-Temporal Graph Learning via Selective State Space Model, arxiv, 2024. \
[4] Graph Mamba: Towards Learning on Graphs with State Space Models, KDD, 2024.
soundness: 2
strengths: 1. The efficiency improvement introduced by Mamba is sound compared to the Transformer.
2. This paper gives a clear and detailed description of the algorithm.
3. Both link prediction and node classification tasks are discussed.
4. The extensive experiments demonstrate that the Mamba structure significantly improves computational and memory efficiency compared to the Transformer.
summary: This paper presents DyGMamba, a modeling framework designed for continuous-time dynamic graphs. Built on a state space model (SSM), DyGMamba captures and leverages hidden temporal patterns from historical graph data. These temporal patterns guide the selection of critical information from a node’s temporal neighbors, enhancing the model's ability to predict dynamic links. DyGMamba achieves state-of-the-art results across seven datasets in dynamic link prediction tasks. Furthermore, extensive experiments have been conducted to demonstrate the framework's efficiency.
weaknesses: 1. **Low Novelty:** 
- Based on my understanding of the algorithm, Section 3.1 is identical to DyGFormer, except that it replaces the Transformer with Mamba. In Section 3.2, the mean pooling mechanism in DyGFormer is modified to a "Dynamic Information Selection" strategy
It appears, then, that **the primary contribution lies in the design of the pooling strategy**, which is more like a minor technical improvement and totally **unrelated to the Mamba structure**. This is somewhat misleading, given that both the name DyGMamba and the abstract emphasize the Mamba component as a key feature. 
- Furthermore, in the ablation study, Variant A uses mean pooling for the output in Equation 5. This modification makes Variant A essentially identical to DyGFormer, with the sole difference being the replacement of Transformer with Mamba. However, the performance of Variant A drops compared to DyGFormer, suggesting that incorporating the Mamba structure into DyGFormer negatively impacts performance. This observation implies that the performance improvements in DyGFormer stem from the "Dynamic Information Selection" mechanism, while the efficiency gains are due to the Mamba structure and the patching techniques utilized within DyGFormer.
For this reason, **DyGMamba’s design offers limited novelty, as its efficiency gains are entirely derived from prior studies**—specifically, the Mamba structure and the patching techniques originally developed for DyGFormer.  
- In addition, from Equation 6, the recent interaction number k is selected as a very small value, such as 10 or 30. Given this, is the Mamba block necessary in this context? Since Mamba primarily enhances efficiency, its advantages may not be realized with such short sequences. I argue that the Mamba structure is unnecessary in Section 3.2. And it contradicts the motivation of the paper, suggesting that **the Mamba structure may not necessary to your design**.




2. **Reference issues:** 
 - In line 176, from the description of the time encoding function, it is not the one from TGAT [1], but from GraphMixer [2]. 
 - In line 180, the Node Interaction Frequency Encoding is followed FreeDyG [3], which should be Yu et al. [4], as it closely aligns with Yu's neighbor co-occurrence scheme. Specifically, the only difference between your description and DyGFormer’s neighbor co-occurrence scheme is the appending of the self-node to the last position in the sequence, which DyGFormer also implements.



3. **Some key content illustrations are vague and hard to follow.** 
- In Section 3.2, lines 250–254, the part regarding "enabling batch processing" is difficult to follow. Specifically, how was the number $10^{10}$ derived? Is it accurate that using only 10 neighbors could result in such a large figure?
- The overall explanation of "Dynamic Information Selection" is also unclear. It’s not evident why this particular design of Eq.7 was chosen or what advantages it offers. Additionally, it’s unclear how this design effectively achieves selection.
- In the "Ablation Study," the design of Variant B is unclear, which is described as removing the Mamba SSM layers in Equation 4. Does this mean completely removing the layers, or does it involve replacing Mamba with Transformer? In my opinion, simply removing these layers lacks purpose, and replacing Mamba with Transformer would be more meaningful. 

4. **Lacking Experiments:** 
- From W1, it appears that the performance gains are entirely due to the "Dynamic Information Selection" mechanism. To thoroughly evaluate the impact of this design and the effectiveness of the time-difference encoding, a more detailed ablation study focused on this component would be beneficial. However, only the entirety of Section 3.2 is ablated as Variant A, which presents a rough experiment. To me, the only observation from Variant A is that the Mamba structure negatively affects DyGFormer’s performance.
- The paper lacks tuning key hyperparameters such as $\alpha$ and $\beta$ in time encoding, the $\gamma$ in Time-Level SSM Block. These hyperparameters are crucial for model performance, and optimal settings may vary across different datasets. Additionally, the reason behind the introduction of $\gamma$ is not discussed. 
- The model was only evaluated on seven datasets out of 13 datasets used in DyGFormer. Could be discussed more thoroughly about the statistics of data sparsity and give the reason why only seven datasets are used. This would improve the persuasion of the experiments part.
- Recently, a very related study, FreeDyG [3], has been proposed and might need to be compared in your experiments.


5. **There are no discussions regarding the limitations of this paper and possible solutions.**

**Conclusion:** \
This paper has a good example in the Introduction and is well-organized; however, the description of the key component in Section 3.2 is vague and difficult to follow. Additionally, the paper presents extensive experiments on efficiency comparisons, mainly attributed to the Mamba structure and patching techniques from the prior works. However, the effectiveness of the key component, "Dynamic Information Selection," is inadequately evaluated through experiments. \
Most importantly, the novelty of the work is low, and the design of the algorithm raises concerns, particularly regarding the use of Mamba. Such as the results from Variant A indicate that incorporating Mamba can negatively impact performance, and the use of mamba in very short sequences, as shown in Equation 6. Therefore, I think this paper is insufficient for ICLR.



**Reference**: \
[1] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks, ICLR, 2022. \
[2] Do We Really Need Complicated Model Architectures For Temporal Networks?, ICLR, 2023. \
[3] FreeDyG: Frequency Enhanced Continuous-Time Dynamic Graph Model for Link Prediction, ICLR, 2024. \
[4] Towards Better Dynamic Graph Learning: New Architecture and Unified Library, NIPS, 2023.

Meta-review: The paper employs the Mamba architecture to address the dynamic representation learning on graphs, which is arguably one of the first papers to do so. The experiments are extensive with a good range of datasets and SOTA baselines. The writing is generally detailed and clear.

However, reviewers find some concern in terms of the novelty of the approach. As the paper utilize an existing Mamba architecture, the contribution of this paper should be better clarified in terms how specifically the proposed approach leverages the unique characteristics of dynamic graphs. On a related note, reviewers also find the motivation of using Mamba to model dynamic graphs somewhat unconvincing, and remain doubtful if it is necessary to use mamba to model very long historical sequences.

Decision: Reject