Towards Better Dynamic Graph Learning:
New Architecture and Unified Library

The framework of our DyGFormer is shown in Figure 1, which employs Transformer [56] as the backbone. Given an interaction $\left(u,v,t\right)$, we first extract historical first-hop interactions of source node $u$ and destination node $v$ before timestamp $t$ and obtain two interaction sequences $\mathcal{S}_{u}^{t}$ and $\mathcal{S}_{v}^{t}$. Next, in addition to computing the encodings of neighbors, links, and time intervals for each sequence, we also encode the frequencies of every neighbor’s appearances in both $\mathcal{S}_{u}^{t}$ and $\mathcal{S}_{v}^{t}$ to exploit the correlations between $u$ and $v$, resulting in four encoding sequences for $u$/$v$ in total. Then, we divide each encoding sequence into multiple patches and feed all the patches into a Transformer for capturing long-term temporal dependencies. Finally, the outputs of the Transformer are averaged to derive time-aware representations of $u$ and $v$ at timestamp $t$ (i.e., $\bm{h}_{u}^{t}$ and $\bm{h}_{v}^{t}$), which can be applied in various downstream tasks like dynamic link prediction and dynamic node classification.

Learning from Historical First-hop Interactions. Unlike most previous methods that require nodes’ historical interactions from multiple hops (e.g., DyRep [55], TGAT [64], TGN [45], CAWN [60]), we only learn from the sequences of nodes’ historical first-hop interactions, turning the dynamic graph learning task into a simpler sequence learning problem. Mathematically, given an interaction $\left(u,v,t\right)$, for source node $u$ and destination node $v$, we obtain the sequences that involve first-hop interactions of $u$ and $v$ before timestamp $t$, which are denoted by $\mathcal{S}_{u}^{t}=\left\{\left(u,u^{\prime},t^{\prime}\right)|t^{\prime}<t\right\}\cup\left\{\left(u^{\prime},u,t^{\prime}\right)|t^{\prime}<t\right\}$ and $\mathcal{S}_{v}^{t}=\left\{\left(v,v^{\prime},t^{\prime}\right)|t^{\prime}<t\right\}\cup\left\{\left(v^{\prime},v,t^{\prime}\right)|t^{\prime}<t\right\}$, respectively.

Encoding Neighbors, Links, and Time Intervals. For source node $u$, we retrieve the features of involved neighbors and links in sequence $\mathcal{S}_{u}^{t}$ based on the given features to represent their encodings, which are denoted by $\bm{X}_{u,N}^{t}\in\mathbb{R}^{|\mathcal{S}_{u}^{t}|\times d_{N}}$ and $\bm{X}_{u,E}^{t}\in\mathbb{R}^{|\mathcal{S}_{u}^{t}|\times d_{E}}$. Following [64], we learn the periodic temporal patterns by encoding the time interval $\Delta t^{\prime}=t-t^{\prime}$ via $\sqrt{\frac{1}{d_{T}}}\left[\cos\left(w_{1}\Delta t^{\prime}\right),\sin\left(w_{1}\Delta t^{\prime}\right),\cdots,\cos\left(w_{d_{T}}\Delta t^{\prime}\right),\sin\left(w_{d_{T}}\Delta t^{\prime}\right)\right]$, where $w_{1},\cdots,w_{d_{T}}$ are trainable parameters. $d_{T}$ is the encoding dimension. The time interval encodings of interactions in $\mathcal{S}_{u}^{t}$ is denoted by $\bm{X}_{u,T}^{t}\in\mathbb{R}^{|\mathcal{S}_{u}^{t}|\times d_{T}}$. We use the same process to get the corresponding encodings for destination node $v$, i.e., $\bm{X}_{v,N}^{t}\in\mathbb{R}^{|\mathcal{S}_{v}^{t}|\times d_{N}}$, $\bm{X}_{v,E}^{t}\in\mathbb{R}^{|\mathcal{S}_{v}^{t}|\times d_{E}}$, and $\bm{X}_{v,T}^{t}\in\mathbb{R}^{|\mathcal{S}_{v}^{t}|\times d_{T}}$.

Neighbor Co-occurrence Encoding Scheme. Existing methods separately compute representations of node $u$ and $v$ without modeling their correlations. We present a neighbor co-occurrence encoding scheme to tackle this issue, which assumes the appearing frequency of a neighbor in a sequence indicates its importance, and the occurrences of a neighbor in sequences of $u$ and $v$ (i.e., co-occurrence) could reflect the correlations between $u$ and $v$. That is to say, if $u$ and $v$ have more common historical neighbors in their sequences, they are more likely to interact in the future.

Formally, for each neighbor in the interaction sequence $\mathcal{S}_{u}^{t}$ and $\mathcal{S}_{v}^{t}$, we count its occurrences in both $\mathcal{S}_{u}^{t}$ and $\mathcal{S}_{v}^{t}$, and derive a two-dimensional vector. By packing the vectors of all the neighbors together, we can get the neighbor co-occurrence features for $u$ and $v$, which are represented by $\bm{C}_{u}^{t}\in\mathbb{R}^{|\mathcal{S}_{u}^{t}|\times 2}$ and $\bm{C}_{v}^{t}\in\mathbb{R}^{|\mathcal{S}_{v}^{t}|\times 2}$. For example, suppose the historical neighbors of $u$ and $v$ are $\left\{a,b,a\right\}$ and $\left\{b,b,a,c\right\}$. The appearing frequencies of $a$, $b$, and $c$ in $u$/$v$’s historical interactions are 2/1, 1/2, and 0/1, respectively. Therefore, the neighbor co-occurrence features of $u$ and $v$ are denoted by $\bm{C}_{u}^{t}=\left[\left[2,1\right],\left[1,2\right],\left[2,1\right]\right]^{\top}$ and $\bm{C}_{v}^{t}=\left[\left[1,2\right],\left[1,2\right],\left[2,1\right],\left[0,1\right]\right]^{\top}$. Then, we apply a function $f\left(\cdot\right)$ to encode the neighbor co-occurrence features by

$$\begin{split}\bm{X}_{*,C}^{t}=f\left(\bm{C}_{*}^{t}\left[:,0\right]\right)+f\left(\bm{C}_{*}^{t}\left[:,1\right]\right)\in\mathbb{R}^{|\mathcal{S}_{*}^{t}|\times d_{C}},\end{split}$$

(1)

where $*$ could be $u$ or $v$. The input and output dimensions of $f\left(\cdot\right)$ are 1 and $d_{C}$. In this paper, we implement $f\left(\cdot\right)$ by a two-layer perceptron with ReLU activation [37]. It is important to note that the neighbor co-occurrence encoding scheme is general and can be easily integrated into some dynamic graph learning methods for better results. We will demonstrate its generalizability in Section 5.3.

Patching Technique. Instead of focusing on the interaction level, we divide the encoding sequence into multiple non-overlapping patches to break through the bottleneck of existing methods in capturing long-term temporal dependencies. Let $P$ denote the patch size. Each patch is composed of $P$ temporally adjacent interactions with flattened encodings and can preserve local temporal proximities. Take the patching of $\bm{X}_{u,N}^{t}\in\mathbb{R}^{|\mathcal{S}_{u}^{t}|\times d_{N}}$ as an example. $\bm{X}_{u,N}^{t}$ will be divided into $l_{u}^{t}=\lceil\frac{|\mathcal{S}_{u}^{t}|}{P}\rceil$ patches in total (note that we will pad $\bm{X}_{u,N}^{t}$ if its length $|\mathcal{S}_{u}^{t}|$ cannot be divided by $P$), and the patched encoding is represented by $\bm{M}_{u,N}^{t}\in\mathbb{R}^{l_{u}^{t}\times d_{N}\cdot P}$. Similarly, we can also get the patched encodings $\bm{M}_{u,E}^{t}\in\mathbb{R}^{l_{u}^{t}\times d_{E}\cdot P}$, $\bm{M}_{u,T}^{t}\in\mathbb{R}^{l_{u}^{t}\times d_{T}\cdot P}$, $\bm{M}_{u,C}^{t}\in\mathbb{R}^{l_{u}^{t}\times d_{C}\cdot P}$, $\bm{M}_{v,N}^{t}\in\mathbb{R}^{l_{v}^{t}\times d_{N}\cdot P}$, $\bm{M}_{v,E}^{t}\in\mathbb{R}^{l_{v}^{t}\times d_{E}\cdot P}$, $\bm{M}_{v,T}^{t}\in\mathbb{R}^{l_{v}^{t}\times d_{T}\cdot P}$, and $\bm{M}_{v,C}^{t}\in\mathbb{R}^{l_{v}^{t}\times d_{C}\cdot P}$. Note that when $|\mathcal{S}_{u}^{t}|$ becomes longer, we will correspondingly increase $P$, making the number of patches (i.e., $l_{u}^{t}$ and $l_{v}^{t}$) at a constant level to reduce the computational cost.

Transformer Encoder. We first align the patched encodings to the same dimension $d$ with trainable weight $\bm{W}_{*}\in\mathbb{R}^{d_{*}\cdot P\times d}$ and $\bm{b}_{*}\in\mathbb{R}^{d}$ to obtain $\bm{Z}_{u,*}^{t}\in\mathbb{R}^{l_{u}^{t}\times d}$ and $\bm{Z}_{v,*}^{t}\in\mathbb{R}^{l_{v}^{t}\times d}$, where $*$ could be $N$, $E$, $T$ or $C$. To be specific, the alignments are realized by

$$\bm{Z}_{u,*}^{t}=\bm{M}_{u,*}^{t}\bm{W}_{*}+\bm{b}_{*}\in\mathbb{R}^{l_{u}^{t}\times d},\bm{Z}_{v,*}^{t}=\bm{M}_{v,*}^{t}\bm{W}_{*}+\bm{b}_{*}\in\mathbb{R}^{l_{v}^{t}\times d}.$$

(2)

Then, we concatenate the aligned encodings of $u$ and $v$, and get $\bm{Z}_{u}^{t}=\bm{Z}_{u,N}^{t}\|\bm{Z}_{u,E}^{t}\|\bm{Z}_{u,T}^{t}\|\bm{Z}_{u,C}^{t}\in\mathbb{R}^{l_{u}^{t}\times 4d}$ and $\bm{Z}_{v}^{t}=\bm{Z}_{v,N}^{t}\|\bm{Z}_{v,E}^{t}\|\bm{Z}_{v,T}^{t}\|\bm{Z}_{v,C}^{t}\in\mathbb{R}^{l_{v}^{t}\times 4d}$.

Next, we employ a Transformer encoder to capture the temporal dependencies, which is built by stacking $L$ Multi-head Self-Attention (MSA) and Feed-Forward Network (FFN) blocks. The residual connection [20] is employed after every block. We follow [14] by using GELU [21] instead of ReLU [37] between the two-layer perception in each FFN block and applying Layer Normalization (LN) [3] before each block rather than after. Instead of individually processing $\bm{Z}_{u}^{t}$ and $\bm{Z}_{v}^{t}$, our Transformer encoder takes the stacked $\bm{Z}^{t}=\left[\bm{Z}_{u}^{t};\bm{Z}_{v}^{t}\right]\in\mathbb{R}^{(l_{u}^{t}+l_{v}^{t})\times 4d}$ as inputs, aiming to learn the temporal dependencies within and across the sequences of $u$ and $v$. The calculation process is

	$$\displaystyle\text{Attention}\left(\bm{Q},\bm{K},\bm{V}\right)=\text{Softmax}\left(\frac{\bm{Q}\bm{K}^{\top}}{\sqrt{d_{k}}}\right)\bm{V},$$		(3)
	$$\displaystyle\text{FFN}\left(\bm{O},\bm{W}_{1},\bm{b}_{1},\bm{W}_{2},\bm{b}_{2}\right)=\text{GELU}\left(\bm{O}\bm{W}_{1}+\bm{b}_{1}\right)\bm{W}_{2}+\bm{b}_{2},$$		(4)
	$$\displaystyle\bm{O}_{i}^{t,l}=\text{Attention}\left(\text{LN}(\bm{Z}^{t,l-1})\bm{W}_{Q,i}^{l},\text{LN}(\bm{Z}^{t,l-1})\bm{W}_{K,i}^{l},\text{LN}(\bm{Z}^{t,l-1})\bm{W}_{V,i}^{l}\right),$$		(5)
	$$\displaystyle\bm{O}^{t,l}=\text{MSA}\left(\bm{Z}^{t,l-1}\right)+\bm{Z}^{t,l-1}=\left(\bm{O}_{1}^{t,l}\|\cdots\|\bm{O}_{I}^{t,l}\right)\bm{W}_{O}^{l}+\bm{Z}^{t,l-1},$$		(6)
	$$\displaystyle\bm{Z}^{t,l}=\text{FFN}\left(\text{LN}\left(\bm{O}^{t,l}\right),\bm{W}_{1}^{l},\bm{b}_{1}^{l},\bm{W}_{2}^{l},\bm{b}_{2}^{l}\right)+\bm{O}^{t,l}.$$		(7)

$\bm{W}_{Q,i}^{l}\in\mathbb{R}^{4d\times d_{k}}$, $\bm{W}_{K,i}^{l}\in\mathbb{R}^{4d\times d_{k}}$, $\bm{W}_{V,i}^{l}\in\mathbb{R}^{4d\times d_{v}}$, $\bm{W}_{O}^{l}\in\mathbb{R}^{I\cdot d_{v}\times 4d}$, $\bm{W}_{1}^{l}\in\mathbb{R}^{4d\times 16d}$, $\bm{b}_{1}^{l}\in\mathbb{R}^{16d}$, $\bm{W}_{2}^{l}\in\mathbb{R}^{16d\times 4d}$ and $\bm{b}_{2}^{l}\in\mathbb{R}^{4d}$ are trainable parameters at the $l$-th layer. We set $d_{k}=d_{v}=4d/I$ with $I$ as the number of attention heads. The input of the first layer is $\bm{Z}^{t,0}=\bm{Z}^{t}\in\mathbb{R}^{(l_{u}^{t}+l_{v}^{t})\times 4d}$, and the output of the $L$-th layer is denoted by $\bm{H}^{t}=\bm{Z}^{t,L}\in\mathbb{R}^{(l_{u}^{t}+l_{v}^{t})\times 4d}$.

Time-aware Node Representation. The time-aware representations of node $u$ and $v$ at timestamp $t$ are derived by averaging their related representations in $\bm{H}^{t}$ with an output layer,

$$\begin{split}\bm{h}_{u}^{t}&=\text{MEAN}\left(\bm{H}^{t}[:l_{u}^{t},:]\right)\bm{W}_{out}+\bm{b}_{out}\in\mathbb{R}^{d_{out}},\\ \bm{h}_{v}^{t}&=\text{MEAN}\left(\bm{H}^{t}[l_{u}^{t}:l_{u}^{t}+l_{v}^{t},:]\right)\bm{W}_{out}+\bm{b}_{out}\in\mathbb{R}^{d_{out}},\\ \end{split}$$

(8)

where $\bm{W}_{out}\in\mathbb{R}^{4d\times d_{out}}$ and $\bm{b}_{out}\in\mathbb{R}^{d_{out}}$ are trainable weights with $d_{out}$ as the output dimension.

We introduce a unified library with standard training pipelines, extensible coding interfaces, and comprehensive evaluating strategies for reproducible, scalable, and credible continuous-time dynamic graph learning research. The overall procedure of DyGLib is shown in Figure 3 in Section A.3.

Standard Training Pipelines. To eliminate the influence of different training pipelines in previous studies, we unify the data format, create a customized data loader, and train all the methods with the same model trainers. Our standard training pipelines guarantee reproducible performance and enable users to quickly identify the key components of different models. Researchers only need to focus on designing the model architecture without considering other irrelevant implementation details.

Extensible Coding Interfaces. We provide extensible coding interfaces for the datasets and algorithms, which are all implemented by PyTorch. These scalable designs enable users to incorporate new datasets and popular models based on their specific requirements, which can significantly reduce the usage difficulty for beginners and allow experts to conveniently validate new ideas. Currently, DyGLib has integrated thirteen datasets from various domains and nine continuous-time dynamic graph learning methods. It is worth noticing that we also found some issues in previous implementations and have fixed them in DyGLib (see details in Section B.3).

Comprehensive Evaluating Protocols. DyGLib supports both transductive/inductive dynamic link prediction and dynamic node classification tasks. Most previous works evaluate their methods on the dynamic link prediction task with the random negative sampling strategy but a few models already reach saturation performance under such a strategy, making it hard to distinguish more advanced designs. For more reliable comparisons, we adopt three strategies (i.e., random, historical, and inductive negative sampling strategies) in [44] to comprehensively evaluate the model performance.

Datasets and Baselines. We experiment with thirteen datasets (Wikipedia, Reddit, MOOC, LastFM, Enron, Social Evo., UCI, Flights, Can. Parl., US Legis., UN Trade, UN Vote, and Contact), which are collected by [44] and cover diverse domains. Details of the datasets are shown in Section B.1. We compare DyGFormer with eight popular continuous-time dynamic graph learning baselines that are based on graph convolutions, memory networks, random walks, and sequential models, including JODIE [28], DyRep [55], TGAT [64], TGN [45], CAWN [60], EdgeBank [44], TCL [57], and GraphMixer [12]. We give the descriptions of baselines in Section B.2.

Evaluation Tasks and Metrics. We follow [64, 45, 60, 44] to evaluate models for dynamic link prediction, which predicts the probability of a link occurring between two given nodes at a specific time. This task has two settings: the transductive setting aims to predict future links between nodes that are observed during training, and the inductive setting predicts future links between unseen nodes. We use a multi-layer perceptron to take the concatenated representations of two nodes as inputs and return the probability of a link as the output. Average Precision (AP) and Area Under the Receiver Operating Characteristic Curve (AUC-ROC) are adopted as the evaluation metrics. We adopt random (rnd), historical (hist), and inductive (ind) negative sampling strategies in [44] for evaluation, where the latter two strategies are more challenging. Please refer to [44] for more details. We also follow [64, 45] to conduct dynamic node classification, which estimates the state of a node in a given interaction at a specific time. A multi-layer perceptron is employed to map the node representations to the labels. We use AUC-ROC as the evaluation metric due to the label imbalance. For both tasks, we chronologically split each dataset with the ratio of 70%/15%/15% for training/validation/testing.

Model Configurations. For baselines, in addition to following their official settings, we also perform an exhaustive grid search to find the optimal configurations of some critical hyperparameters for more reliable comparisons. As DyGFormer can access longer histories, we vary each node’s input sequence length from 32 to 4096 by a factor of 2. To keep the computational complexity at a constant level that is irrelevant to the input length, we correspondingly increase the patch size from 1 to 128. Please see Section B.5 for the detailed configurations of different models.

Implementation Details. For both tasks, we optimize all models (i.e., excluding EdgeBank which has no trainable parameters) by Adam [27] and use supervised binary cross-entropy loss as the objective function. We train the models for 100 epochs and use the early stopping strategy with a patience of 20. We select the model that achieves the best performance on the validation set for testing. We set the learning rate and batch size to 0.0001 and 200 for all the methods on all the datasets. We run the methods five times with seeds from 0 to 4 and report the average performance to eliminate deviations. Experiments are conducted on an Ubuntu machine equipped with one Intel(R) Xeon(R) Gold 6130 CPU @ 2.10GHz with 16 physical cores. The GPU device is NVIDIA Tesla T4 with 15 GB memory.

We report the performance of different methods on the AP metric for transductive dynamic link prediction with three negative sampling strategies in Table 1. The best and second-best results are emphasized by bold and underlined fonts. Note that the results are multiplied by 100 for a better display layout. Please refer to Section C.1 and Section C.2 for the results of AP for inductive dynamic link prediction as well as AUC-ROC for transductive and inductive dynamic link prediction tasks. Since EdgeBank can be only evaluated for transductive dynamic link prediction, we do not show its performance under the inductive setting. From the results, we have two main observations.

Firstly, DyGFormer usually outperforms baselines and achieves an average rank of 2.49/2.69 on AP/AUC-ROC for transductive and 2.69/2.56 for inductive dynamic link prediction across three negative sampling strategies. This is because: (i) The neighbor co-occurrence encoding scheme helps DyGFormer exploit correlations between the source node and destination node, which are often predictive for future links (see Section 5.5). (ii) The patching technique allows DyGFormer to access longer histories and capture long-term temporal dependencies (see Section 5.4). In Table 9 in Section B.5, the input sequence lengths of DyGFormer are much longer than those of baselines on several datasets, indicating that it can utilize longer sequences better. We also observe the varying results of DyGFormer across different negative sampling strategies and give an analysis in Section 5.7.

Secondly, some of our findings of baselines differ from previous reports. For instance, the performance of some baselines can be significantly improved by properly setting some hyperparameters. Additionally, some methods would obtain worse results after we fix the problems or make adaptions in their implementations. More explanations can be found in Section B.4. These observations highlight the importance of rigorously evaluating different methods by a unified library and verify the necessity of introducing DyGLib to facilitate the development of dynamic graph learning.

We also report the results of dynamic node classification in Table 15 in Section C.3. We observe that DyGFormer obtains better performance than most baselines and achieves an impressive average rank of 2.50 among them, demonstrating the superiority of DyGFormer once again.

Our Neighbor Co-occurrence Encoding scheme (NCoE) is versatile and can be easily integrated with dynamic graph learning methods based on sequential models. Hence, we incorporate NCoE with TCL and GraphMixer and show their performance in Table 2 and Table 16 in Section C.4. We find TCL and GraphMixer usually yield better results with NCoE, achieving an average improvement of 5.36% and 1.86% over all datasets. This verifies the effectiveness and versatility of the neighbor co-occurrence encoding, and highlights the importance of capturing correlations between nodes. Also, as TCL and DyGFormer are built upon Transformer, TCL w/ NCoE can achieve similar results with DyGFormer on datasets that enjoy shorter input sequences (in which cases the patching technique in DyGFormer contributes little). However, when datasets exhibit more obvious long-term temporal dependencies (e.g., LastFM, Can. Parl.), the performance gaps become more significant.

We validate the advantages of our patching technique in preserving the local temporal proximities and reducing the computational complexity, which helps DyGFormer effectively and efficiently utilize longer histories. We conduct experiments on LastFM and Can. Parl. since they can benefit from longer historical records. For baselines, we sample more neighbors or perform more causal anonymous walks (starting from 32) to make them access longer histories. The results are depicted in Figure 2, where the x-axis is represented by a logarithmic scale with base 2. We also plot the performance of baselines with the optimal length by unconnected points based on Table 9 in Section B.5. Note that the results of some baselines are incomplete since they raise the out-of-memory error when the lengths are longer. For example, TGAT is only computationally feasible when extending the input length to 32, resulting in two discrete points with lengths 20 (the optimal length) and 32.

From Figure 2, we conclude that: (i) most of the baselines perform worse when the input lengths become longer, indicating they lack the ability to capture long-term temporal dependencies; (ii) the baselines usually encounter expensive computational costs when computing on longer histories. Although memory network-based methods (i.e., DyRep and TGN) can handle longer histories with affordable computational costs, they cannot benefit from longer histories due to the potential issues of vanishing or exploding gradients; (iii) DyGFormer consistently achieves gains from longer sequences, demonstrating the advantages of the patching technique in leveraging longer histories.

We also compare the running time and memory usage of DyGFormer with and without the patching technique during the training process. The results are shown in Table 17 in Section C.5. We could observe that the patching technique efficiently reduces model training costs in both time and space, allowing DyGFormer to access longer histories. As the input sequence length increases, the reductions become more significant. Moreover, with the patching technique, we find that DyGFormer achieves an average improvement of 0.31% and 0.74% in performance on LastFM and Can. Parl. than DyGFormer without patching. This observation further demonstrates the advantage of our patching technique in leveraging the local temporal proximities for better results.

To verify the motivation of NCoE (i.e., nodes with more common historical neighbors tend to interact in the future), we compare the performance of DyGFormer and DyGFormer without NCoE. We choose 0.5 as the threshold and use TP, TN, FN, and FP to denote True/False Positive/Negative. Common Neighbor Ratio (CNR) is defined as the ratio of common neighbors in source node $u$’s sequence $S_{u}$ and destination node $v$’s sequence $S_{v}$, i.e., $|S_{u}\cap S_{v}|/|S_{u}\cup S_{v}|$. We focus on links whose predictions of DyGFormer w/o NCoE are changed by DyGFormer (i.e., FN→TP, FP→TN, TP→FN, and TN→FP). We define Changed Link Ratio (CLR) as the ratio of the changed links to their original set, which is respectively computed by $|$FN→TP$|/|$FN$|$, $|$FP→TN$|/|$FP$|$, $|$TP→FN$|/|$TP$|$, and $|$TN→FP$|/|$TN$|$. If NCoE is helpful, DyGFormer will revise more wrong predictions (more FN→TP and FP→TN) and make fewer incorrect changes (fewer TP→FN and TN→FP). We report CLR and average CNR of links in the above sets on five typical datasets in Table 3.

We find NCoE effectively helps DyGFormer rectify wrong predictions of DyGFormer w/o NCoE on datasets with significantly higher CNR of positive links than negative ones, which happens with most datasets. Concretely, for Wikipedia, UCI, and Flights, their CNRs of FN→TP are much higher than FP→TN (e.g., 37.09% vs. 2.28% on Flights) and DyGFormer revises most wrong predictions of DyGFormer w/o NCoE (e.g., 83.66% for positive links in FN and 83.83% for negative links in FP on Flights). Corrections made by our encoding scheme are less obvious on datasets whose CNRs between positive and negative links are similar, which occurs in only 2 of 13 datasets. For US Legis. and UN Vote, their CNRs between FN and FP are analogous (e.g., 69.92% vs. 62.13% on US Legis.), weakening the advantage of our neighbor co-occurrence encoding scheme (e.g., only 31.63%/23.67% of positive/negative links are corrected in FN/FP on US Legis.). Therefore, we conclude that the neighbor co-occurrence encoding scheme helps DyGFormer capture common historical neighbors in $S_{u}$ and $S_{v}$, and bring better results in most cases.

Note that DyGFormer is superior to baselines by 1) exploring the source and destination nodes’ correlations from their historical sequences by neighbor co-occurrence encoding scheme; 2) using the patching technique to attend longer histories. Thus, DyGFormer tends to perform better on datasets that favor these two designs. We define Link Ratio (LR) as the ratio of links in their corresponding positive or negative set, which can be computed by TP$/$(TP+FN), TN$/$(TN+FP), FN$/$(TP+FN), and FP$/$(TN+FP). As a method with more TP and TN (i.e., fewer FN and FP) is better, we report the results of LR and average CNR of links in TP and TN on five typical datasets in Table 5.

We observe when CNR of TP is significantly higher than CNR of TN in the datasets, DyGFormer often outperforms baselines (most datasets satisfy this property). For Wikipedia, UCI, and Flights, their CNRs of TP are much higher than those of TN (e.g., 59.09% vs. 0.01% on Wikipedia). Such a characteristic matches the motivation of our neighbor co-occurrence encoding scheme, enabling DyGFormer to correctly predict most links (e.g., 92.74% of positive links and 97.19% of negative links are properly predicted on Wikipedia). Moreover, as LastFM and Can. Parl. can gain from longer histories (see Figure 2 and Table 9 in Section B.5), DyGFormer is significantly better than baselines on these two datasets. When CNRs of TP and TN are less distinguishable in the datasets, DyGFormer may perform worse (only 2 out of 13 datasets show this property). For US Legis., the CNRs between TP and TN are close (i.e., 75.18% vs. 53.98%), making DyGFormer worse than memory-based baselines (i.e., JODIE, DyRep, and TGN). For UN Vote, its CNR of TP is even lower than that of TN (i.e., 56.24% vs. 76.02%), which is opposite to our motivation, leading to poor results of DyGFormer than a few baselines. Since these two datasets cannot obviously gain from longer sequences either (see Table 9 in Section B.5), DyGFormer obtains worse results on them. Thus, we conclude that for datasets with much higher CNR of TP than CNR of TN or datasets that can benefit from longer histories, DyGFormer is a good choice. Otherwise, we may need to try other methods.

Compared with the random (rnd) strategy, historical (hist) and inductive (ind) strategies will sample previous links as negative ones. This makes previous positive links negative, which may hurt the performance DyGFormer since the motivation of our neighbor co-occurrence encoding scheme is violated. As positive links are identical among rnd, hist, and ind, we compute LR and the average CNR of links in FP and show results in Table 5.

We find when hist or ind causes several magnitudes higher CNR of FP than rnd in the datasets, DyGFormer drops sharply. For Wikipedia, UCI, and Flights, the CNRs of FP with hist/ind are much higher than rnd (e.g., 14.00%/11.66% vs. 0.02% on Wikipedia). This misleads DyGFormer to predict negative links as positive and causes drops (e.g., 89.28%/94.53% of negative links are incorrectly predicted with hist/ind on Wikipedia, while only 2.81% are wrong with rnd). We also note the drops in UCI are milder since the changes in CNR caused by hist or ind vs. rnd are less obvious than changes in Wikipedia and Flights. When changes in CNR of FP caused by hist or ind are not obvious in the datasets, DyGFormer is less affected. Since hist/ind makes little changes in CNRs of FP on US Legis., we find it ranks second with hist/ind, which may indicate DyGFormer is less influenced by the neighbor co-occurrence encoding scheme and generalizes well to various negative sampling strategies. For UN Vote, although its CNRs of FP are not affected by hist and ind either, DyGFormer still performs worse due to its inferior performance with rnd. Hence, we deduce that our neighbor co-occurrence encoding may be sometimes fragile to various negative sampling strategies if its motivation is violated, leading to the varying performance of DyGFormer.

Finally, we validate the effectiveness of the neighbor co-occurrence encoding, time encoding, and mixing of the sequence of source node and destination node in DyGFormer. From Figure 4 in Section C.6, we observe that DyGFormer obtains the best performance when using all the components, and the results would be worse when any component is removed. This illustrates the necessity of each design in DyGFormer. Please refer to Section C.6 for detailed implementations and discussions.