Supra-Laplacian Encoding for Transformer on Dynamic Graphs
Authors: Yannis Karmim
Marc Lafon
Raphael Fournier-S'niehotta
Nicolas THOME
Venue: NeurIPS 2024 poster (2024)
Keywords: Dynamic graphs
Link prediction
Transformer
supra-Lapacian encoding
Primary area: graph_neural_networks
TL;DR: New spectral spatio-temporal encoding for fully connected Dynamic Graph Transformer in dynamic link prediction

Abstract: Fully connected Graph Transformers (GT) have rapidly become prominent in the static graph community as an alternative to Message-Passing models, which suffer from a lack of expressivity, oversquashing, and under-reaching.
However, in a dynamic context, by interconnecting all nodes at multiple snapshots with self-attention,GT loose both structural and temporal information. In this work, we introduce Supra-LAplacian encoding for spatio-temporal TransformErs (SLATE), a new spatio-temporal encoding to leverage the GT architecture while keeping spatio-temporal information.
Specifically, we transform Discrete Time Dynamic Graphs into multi-layer graphs and take advantage of the spectral properties of their associated supra-Laplacian matrix.
Our second contribution explicitly model nodes' pairwise relationships with a cross-attention mechanism, providing an accurate edge representation for dynamic link prediction.
SLATE outperforms numerous state-of-the-art methods based on Message-Passing Graph Neural Networks combined with recurrent models (e.g, LSTM), and Dynamic Graph Transformers,
on~9 datasets. Code is open-source and available at this link https://github.com/ykrmm/SLATE.

Supra-Laplacian Encoding for Transformer on Dynamic Graphs
Yannis Karmim
Marc Lafon
Conservatoire National des Arts et Métiers
Conservatoire National des Arts et Métiers
CEDRIC, EA 4629
CEDRIC, EA 4629 F 75000, Paris, France
F 75003, Paris, France yannis. karmim@cnam.....
marc. marc.lafon@lecnam net
Raphaël Fournier S'niehotta
Nicolas Thome Sorbonne Université CNRS, ISIR
Conservatoire National des Arts et Métiers
CEDRIC, EA 4629 F 75003, Paris, France counieer@caam. fr
F-75005 Paris, France
nicolas. thome@isir www.::iiiii.........mmmmmmmmm fr
Abstract
Fully connected Graph Transformers (GT) have rapidly become prominent the static graph community as an alternative to Message-Passing models, which suffer from lack of expressivity, oversquashing, and under-reaching. However, in dynamic context, by interconnecting all nodes at multiple snapshots with self-attention, GT loose both structural and temporal information. this work, we encoding for spatio-temporal TransformErs (SLATE), a new spatio-temporal encoding to leverage the GT architecture while keeping ppatio-temporal information. Specifically, Graphs into multi-layer graphs and take advantage of the spectral properties of their associated supra- Laplacann matrix. Our second contribution explicitly model nodes' pairwise relationships with a cross-attention mechanism, providing an accurate edge representation for dynamic link prediction. SLATE outperforms numerous state-of- the-art methods based on Dessage-Passsngg Graph Neural Networks combined with recurrent models (e.g. LSTM), and Dynamic Graph Transformers, 9 datasets. Code is open-source and available at this link
introduce
transform Discrete Time Dynamic
Introduction
Dynamic graphs are crucial for modeling interactions between entities in various fields, from social sciences computational biology [58, 16, 19, 20]. Link prediction dynamic graphs is an all- important task, with diverse applications, such as predicting user actions in recommender systems, forecasting financial transactions, identifying potential academic collaborations. Dynamic graphs can be modeled as a time series of static graphs captured at regular intervals (Discrete Time Dynamic Graphs, DTDG) [41, 54].
Standard approaches for learning representations on DTDGs combine Message-Passinne GNNs (MP- GNNs) with temporal RNN-based models [59, 39, 34]. In static contexts, Graph Transformers (GT) 51, 26] offer a compelling alternative to MP-GNNs that faced several limitations [53, 42]. Indeed, their fully-con connectdd attention mechanism captures long-range dependencies, resolving issues such as oversquashing [1]. GT's directly connect nodes, using the graph structure as a soft bias through positional encoding [37]. Incorporating ioolacian-basedd encodings in GTs provably enhances their expressiveness compared to MP-GNNS [26, 11].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Supra Adjacency Matrix
A1 1.0
As
2.40
X mmax
9.92
1.00
0.75
0.60
0.25
6.00
-0.25
2 t
t= 2 t
t == 3
-1.00
Figure 1: SLATE is fully connected transformer for dynamic link prediction, which innovatively performs a joint spatial and temporal encoding of the dynamic graph. SLATE models DTDG as a multi-layer graph with temporal dependencies between a node and its past. Building the supra-adjacency matrix of mandomly-generatee toy dynamic graph with 3 snapshots (left) and analysing the spectrum of its associated supra- Sapra-Laplacian (right) provide fundamental spatio-temporal information. The projections on eigenvectors associated with smaller eigenvalues (Aς) capture global graph dynamics: node colors are different for each time step, Larger cigenvalues e.g. Amax), capture more localized spatio-temporal information (see Appendix A.I).
Exploiting GT's on dynamic graphs would require spatio-temporal encoding that effectively retains both structural and temporal information. The recent works that have extended GT's to dynamic graphs capture spatio-temporal dependencies between nodes by using partial attention mechanisms [31, 56, 47, 18]. Moreover, these methods also employ encodings which independently embed the graph structure and the temporal dimension. Given that the expressiveness of GTs depends on an accurate spatio-temporal encoding, designing one that interweaves time and position information could greatly enhance their potential and performance.
The vast majority of neural-based methods for dynamic link prediction rely node representation learning [34, 55, 38, 59, 39]. Recent works enrich node embeddings with pairwise information for a given node-pair using co-occurrence neighbors matching [60, 48] or cross-attention on historical sub-graphs [47]. However these methods neglect the global information of the graph by sampling different spatio-temporal substructures around targeted nodes.
Pioneering work in the complex network community has studied temporal graphs with multi-layers models and supra-adjacency matrices [44, 25]. The spectral analysis of such matrices can provide valuable structural and temporal information [8, 36). However, how adapt this formalism for learning dynamic graphs with transformer architectures remains widely open question.
In this work, we introduce Supra- Supra-LAplacins LAplacian encoding for ppatio-temporal TransformErs (SLATE), new unified spatio-tempore encoding which allows to fully exploit the potential of the GT architecture for the task of dynamic link prediction. As illustrated Figure 1, adapting supra-Laplacian matrices to dynamic graph can provide rich spatio-temport information for positional encoding. SLATE is based on the following two main contributions:
We bridge the gap between multi-layer networks and Discrete Time Dynamic Graphs (DTDGs) by adapting the spectral properties of supra-Laplacian matrices for transformers on dynamic graphs. By carefully transforming the supra-Laplacian matrices for DTDGs, we derive connected multi-layer graph that captures various levels of spatio-temporal information. We introduce colle-coneected spatio-temporal transformer that leverages this unified supra-Laplacian encoding.
The proposed transfomer captures dependencies between nodes across multiple time steps, creating dynamic representations.
To enhance link prediction, we introduce a lightweight edge representation module using cross-attention only between the temporal representations of node pairs, precisely cap- tuing their evolving interactions. This results unique edge embedding, significantly strcamlining the prediction process and boosting both efficiency and accuracy.

---

We conduct an extensive experimental validation of our method across 11 real and synthetic discrete- time dynamic graph datasets. SLATE outperforms state-of-the results by large margin. We also validate the importance of our for optimal performances. Finally, SLATE remains efficient since it uses single-layer transformer, and we show impressive results on larger graph datasets, indicating good scalability, and limited time-memory overhead.
unified spatio-temporal encoding and the edge module
2 Related work
Dynamic Graph Neural Networks on DTDGs. The standard approach to learn on DTDGs [41, 54] involves using two separate spatial and temporal models. The spatial model is responsible for encoding the structure of the current graph snapshot, while the temporal model updates the dynamic either of the graph representations [39, 40, 59, 30, 28] the graph model parameters [5). Recently, ROLAND [59] introduced a generic framework to use any static graph model for spatial encoding coupled with recurrent-basee (LSTM [17]. RNN, GRU) or attention-based temporal model. These above methods mainly use a MP-GNN as spatial model [23, 46, 583. However, MP-GNNs are known to present critical limitations: they struggle to distinguish simple structures like triangles or cycles [33, 4], and fail to capture long-range dependencies due to oversquashing [1, 42]. To overcome these limitations, some works have adopted a fully-com connectdd GT as spatial model, benefiting from its global attention mechanism [6. 50, 61]. In [39], the local structure is preserved by computing the attention on direct neighbors. In contrast these works, SLATE uses a unique spatio-temporal graph transformer model, greatly simplifying the learning process.
Graph Transformer. In static contexts, Graph Transformers have been shown to provide a com- pelling alternative MP-GNNs [11]. GTs [51, 37, 22, 57] enable direct connections between all nodes, using the graph's 's structure as soft inductive bias, thus resolving the oversquashing issue. The expressiveness of GTs heavily depends on positional or structural encoding [11, 32, 12, 3]. In [11], the authors use the eigenvectors associated with the k-lowest cigenvalues of the Laplacian matrix, which allows GTs distinguish structures that MP-GNNs are unable differentiate. Following the success of Laplacian positional encoding on static graphs, SLATE uses the eigenvectors of the supra- supra-Laplacian of a multi-layer graph representation of DTDGs as spatio-temporal encoding.
Dynamic Graph Transformers. To avoid separately modelling structural and temporal information as dynamic Graph Neural Networks usually do on DTDGs, recent papers have adopted a unified model based spatio-temporal attention [31, 18]. This novel approach make those models close to wransformer-baeed methods classically employed to learn on Continuous Time Dynamic Graphs (CTDG) [52. 47, 49]. Among them, some preserve the local structure by computing attention only on direct neighbors [52, 39J. while others sample local spatio-temporal structures around nodes [47, 31, 56, 18] and perform fully-connected attention. However, their spatio-temporal encoding is still built by concatenating spatial and a temporal encoding that are computed independently. The spatial encoding either based on a graph-basee distance [47, 18] or on a diffusion- based measure [31]. The temporal encoding is usually sinus-based [52, 49, 2] as in the original transformer paper [45]. Another drawback of these methods [31, 47, 18, 49] is that they use only sub-graphs to represent the local structure around a given node. Therefore, their representations of the nodes are computed on different graphs and thus fail to capture global and long-range interactions. Contrary to those approaches, our SLATE model uses the same graph to compute node representations in fully-connected GT between all nodes within temporal windows. features a unified spatio-temporal encoding based on the supra-Laplacian matrix.
Dynamic Link Prediction methods. For dynamic link prediction, many methods are based only on node representations and use MLPs cosine similarity to predict the existence of link [39, 40, 38). Recent approaches complement node representations by incorporating pairwise information. Techniques like co-occurrence neighbors matching [60, 48] or cross- cooss-tttention on historical sub-graphs [47] are employed. However, these methods often overlook the global graph structure by focusing on sampled spatio-temporal substructures. For instance, CAW-N [48] uses anonymous random walks around a pair of nodes and matches their neighborhoods, while DyGformer [60] applies transformers to one-hop neighborhoods and calculates co-occurrences. These localized approaches fail to capture the broader graph context. TCL [47] is the closest to SLATE, using cross-attention between spatio-
3

---

temporal representations of node pairs. TCL samples historical sub-graphs using BFS and employs contrastive learning for node representation. However, it still relies on sub-graph sampling, missing the full extent of the global graph information. In contrast, SLATE leverages the entire graph's ss spectral properties through the supra-Laplacian, incorporating the global structure directly into the spatio-temporal encoding. This holistic approach allows SLATE to provide richer understanding of dynamic interactions, leading to superior link prediction performance.
3 The SLATE Method
In this section, we describe fully- conneetedd dynamic graph transformer model, SLATE, for link prediction. The core idea in section 3.1 is to adapt the supra-Laplacian matrix computations for dynamic graph transformer (DGTs), and to introduce spectral analysis. In section 3.2, we detail our full-attention transformer to capture the spatio-temporal dependencies between nodes different time steps. Finally, detail our edge representation module for dynamic link prediction in section 3.3. Figure illustrates the overall SLATE framework.
spatio-temporal encoding based on its
Supra-Laplacian
Teesoor (b) Encoding (Sec.
(c) Fully-connected Graph Transformer 3.2)
(d) Edge representation
(a) Computation (Sec.
Proas-Ateaation (Sec. 3.3)
Laym o² Ad = Ae)
(Nw)
2
80
Nodes positions wardd
R
R
Cross-Attention
A
A
Ac
Zu
Zuot
Ze,
Zu.t
Ze,
Nodes positions wordt:
O4
LayerNorm PKA
Eucoder
A
A
A.
Ndid Vistual Nodo
2
Zud Eny
MLP
6xa
Ar-1
0
Eun
Add: Tempperal Connection
Time Pooling
A
Au
x
Cov
A
Linear OcT
Temporal Aggrogation
MLP
Taga D 1/2 1/8
SLE
The SLATE model for link prediction with dynamic graph transformers (DGTs). To recover the lost spatio-tempont structure in DGTs, we adapt the supra-Laplacian matrix computation DGT' by making the input graph provably connected (a), and use its spectral analysis to introduce specific encoding for DGT's (b). (c) Applies fully connected ppatio-temporal transformer between all nodes at multiple time-step. Finally, we design in (d) an edge representations module dedicated to link prediction using cross-attention on multiple temporal representations of the nodes.
Figure 2:
Notations. Let us consider a DTDG G as an undirected graph with fixed number of N nodes across snapshots, represented by the set adjacency matrices A = (A..... Ar Its supra-graph, the multi-layer network G (V. E), is associated to supra-adjacency matrix A. obtained by stacking A, diagonally (see Eq. (7) in Appendix A. Then, the supra-Laplaciat matrix is defined 1-1/2 AD- where the identity matrix and D the degree matrix of G. Let x, E F be the feature vector associated with the node (which remains fixed among all snapshots). Finally, let consider the random variable y E (0,1) such that y = 1 if nodes u and v are connected and y 0 otherwise.
as L,

---

3.1 Supra-Laplacian as Spatio-Temporal Encoding
In this section, we cast Discrete Time Dynamic Graphs (DTDGs) multi-layce networks, and use the spectral analysis of their supra-graph and generate a powerful spatio-temporal encoding for our fully-connected transformer.
DTDG multi-layer graphs. If graph is connected, its spectral analysis provides rich information of the global graph dynamics, as shown in Figure 1. The main challenge in casting DTDG as multi- layer graphs relates its disconnectivity, which induces as many zero eigenvalues components, DTDG have in practice a high proportion of isolated nodes per snapshot (see Figure 3 in experiments), making the spectral analysis the raw disconnected graph useless. Indeed, it mainly indicates positions relative to isolated nodes, losing valuable information on global dynamics and local tempooll structures. We experimentally validate that mandatory to compute the supra-Laplacian matrix on a connected graph to recover a meaningful spatio-temporal structure.
connected
Supra-Laplacian computation. To overcome this issue and make the supra-grajy connected, follow three steps: (1) remove isolated nodes in each adjacency matrix, (2) introduce a virtual node in each snapshot connect clusters, and (3) add temporal self-connection between node and its past if it existed in the previous timestep. We avoid temporal dependencies between virtual nodes to prevent artificial connections. These 3 transformation steps make the resulting supra-graph provably connected. This process is illustrated in Figure 2a, and we give the detailed algorithm in Appendix A.3.
Spatio-temporal encoding. With a connected G. the second smallest eigenvalue d of the supra- Laplacian L is guaranteed to be non-negative (see proof in Appendix A.3), and its associated Fiedler vector Φ1 reveals the dynamics of & (Figure 1). In practice, similar to many static GT models [26, 37, 12], retrieve the first & eigenvectors of the spectrum of L,, with & being hyper-paraments The spectrum can be computed in DIANN') and have a memory complexity of O(&N') where N' is the size of A, and we follow the literature normalize the eigenvectors and resolve sign ambiguities [26]. The supra-Laplacia spatio-temporal encoding vector of the node u at time is:
SLE,,, = {
90st (Lm., (d), $2...., dul @ diag(A)) if tt is not isolated yosr (Ox @ (Aa)
(I)
otherwise
where denotes the concatenation operator. Lu,t (0 22.... ou] [6" 02 ..... 6% contains the projections of the node at time / in the eigenspace spanned by the k first eigenvectors of L, diag(A) contains the eigenvalues of L (which are the same for all nodes) and Dög is a linear layer allowing to finely adapt the supra-graph spectrum features to the underlying link prediction task. Note that because we did not include isolated nodes in the computation of the supra-Laplacian, we replace the eigenvector projections by null vector 0 for these nodes. All the steps involved in constructing our spatio-temporal encoding are illustrated Figure 2b.
3.2 Fully-connected spatio-temporal transformer
In this section, we describe the architecture of our fully-connected spatio-temports transformer, fer- to construct node representations that captures long-range dependencies between the nodes each time step. We illustrate our fully-connected GT in Figure 2c. We employ a single transformer block, such that architecture remains lightweight. This is in line with recent findings showing that single encoder layer with multi-head attention is sufficient for high performance, even for dynamic graphs [51].
The input representation of the node de is the concatenation of the node embeddings (which remains the same for each snapshot) and our supra- supra-Laplacian spatio-tempone encoding:
Zu,t = gog (xn) @ SLE,,t
where 9o, is a linear projection layer and O denotes the concatenation operator. Then we stack all the representations of each nodes at each time step within time window of size to obtain the input sequence, Z e [d
xd of the GT.
5

---

The fully-connected ppatio-temporrs transformer, for, then produces a unique representation ž [N for each node at each time-step:
2 = fo (Z).
Surprisingly, considering all temporal snapshots did not yield better results in our experiments (see Figure in section 4.2).
Unlike previous DGT methods that sample substructures around each nodes [31, 56, 47], SLATE leverages the full structure of the DTDG within the time window. This approach ensures that nodes are arbitrarily discarded in the representation learning process, as we use the same information source Z for all nodes.
3.3 Edge Representation with Cross-Attentie
In this section, we present our innovative edge representation module Edge. It designed for efficient dynamic link prediction and leverage the node representations learned by our fully-connected spatio- temporal GT. We illustrated our module in Figure 2d. This module is composed of a cross-attention model, Jitx: that captures pairwise information between the historical representation of two targeted nodes followed by classifier to determine the presence of link.
For a link prediction time on given node pair (u, v). we aggregate all temporal representations of u and resulting in two sequences Zu,: [uu,t-ws Zu,t] and Z,,, /,,tt-wy.... 2r,r]. We use these multiple embeddings build pairwise representation that captures dynamic relationships over time, Then, the cross-attention module Soxa produces pairwise representation of the sequence E,, Roxd;
Eu, = (Zu,t; Zr,t).
We obtain the final edge representation Cu.v Rd by applying an average time tnee-pooligg operator and we compute the probability that the nodes u4411 and U1+1 are connected with:
ply = 1| eu,v) = o (MLP((eu.))
(5)
SLATE differs from methods that enrich node and edge representations with pairwise information by sampling substructures around each node [47, 60, 48, 18]. Instead, we first compute node representations based on the same dynamic graph information contained in Z. Then, we capture fine-grained dynamics specific to each link (u, v) through a cross-attention mechanism.
Our training resort the standard Binary Cross- Pross-Entropy loss function. In practice, for node u, sample a negative pair Uney and a positive pair Upos:
Co BCE(p(y v/e..,,..)) +CCE(p(y Oleu.v.a))
(6)
In this context, {0xa, fr, 2TT, 6z) represents all the parameters within the edge representation module OXA. the fully-connected transformer 0r, the spatio-temporal linear layer OST and the node embedding parameters 0F as illustrated Figure 2.
3.4 SLATE Scalability
The theoretical complexity of attention computation is O(N2) per snapshot, scaling ((NT)) when considering all 7' snapshots. However, as shown in our experiments (Figure 4) and consistent with recent works [21], large temporal context often unnecessary. By using time window w with w & T (similar to other DGT architectures [31, 56)), we reduce complexity to O((Nw)?). For predictions time ++1 we focus only on snapshots from Gi-w G., Ablation studies confirm that smaller time windows deliver excellent results across various real-world datasets. We further leverage FLASH Attention [9] to optimize memory usage and computation. Additionally, we incorporate Performer [5], which approximates the softmax computation of the attention matrix, reducing the complexity to (Nw).. This enables us to scale efficiently to larger graphs, as shown in Table while maintaining high performance (sce Table 15) with manageable computational resources.

---

Experiments
We conduct extensive experiments to validate SLATE for link prediction discrete dynamic graphs, including state-of-the-an comparisons section 4.1. In section 4.2, we highlight the benefits of our two main contributions, the importance of connecting our supra-graph, and the ability of SLATE to scale to larger datasets with reasonable time and memory consumption compared to MP-GNNS.
Implementation details. We one transformer Encoder Layer [45]. For larger datasets, employ Flash Attention [9] for improved time and memory efficiency. Further details regarding model parameters and their selections are provided in Table 8. We fix the token dimension at d 128 and the time window at w = 3 for all our experiments. We use an SGD optimizer for all of our experiments. Further details syper-parameters search, including the number of eigenvectors for our spatio-temporal encoding, are in Appendix D.
4.1 Comparison to state-of-the-art
Since both the continuous and discrete communities evaluate on similar data, we compare SLATE to state-of-the-art DTDG (Table 1) and CTDG (Table 2) models. Best results are in bold, second best are underlined. More detailed results and analyses are presented in Appendix E.
Baselines and evaluation protocol. To compare the benefits of fully connected spatio-temporal attention with a standard approach using transformers, we designed the ROLAND-GTT model based on the ROLAND framework [59]. This model follows the stacked-GNN approach [41], equipped with the encoder for described in section 3 including static Laplacian positional encoding [1 1J, and LSTM [17] updating the node embeddings.
We adhere to the standardized evaluation protocols for continuous models [60] and discrete mod- els [55]. Our evaluation follows these protocols, including metrics, data splitting, and the datasets provided. Results in Table and Table are from the original papers, except those marked with We report the average results and standard deviations from five runs to assess robustness. Additional results, including hard negative sampling evaluation, are in Appendix E.2.
Datasets. In Table 6 Appendix C, we provide detailed statistics for the datasets used in our exper- iments. An in-depth description of the datasets is given Appendix C. We evaluate on DTTGGs datasets provided by [60] and [55], we add synthetic dataset SBM based on stochastic block model [29], to evaluate on denser DTDG.
Table I: Comparison to DTDG models on discrete data. ROC-AUC
Method
HepPh
AS733
Enron
Colab
SBM!
Arg.
GCN! [23]
74.52 0.80
96.65 0.05
91.31 0.45
88.28 0.58
95,96 0.32
89.34 0.44
GINt [53]
71.47 0.556
91.16 1.17
85,38
0.61
88.86 0.46
86.08
0.67
EvolveGCN [34]
76.82 = 1.46
92.47 a 0.04
90.12
83.88 a 0.53
94.21 a 0.66
87.50 0.68
GRUGCN [40]
82.86
94.96
92.47
84.60
92.55
89.48 0.51
DySat [39]
81.02 0.25
95.06 0.21
93.06 0.97
87.25 + 1.70
91.92 0.39
89.67 0.70
VGRNN [1S]
77.65 =: 0.99
95.17 a 0.62
93.10 0.57
85.95 a: 0.49
93.88 à: 0.07
89.15 1: 0.55
HTGN [55]
9..13
98.75 0.03
94.17 + 0.17
89.26 + 0.17
94.80 0.23
93.62 0.15
ROLAND-GT [59]
81.40
94.75 0.87
94.88
0.64
SLATE
93.21 0.37
97.46 0.45
96.39 0.17
90.84 = 0.41
97.69 = 0.21
95.12 0.32
Comparison to discrete models, on DTDG. Table 1 We showcases the performance of SLATE against various discrete models on DTDG datasets, highlighting its superior performance across multiple metrics and datasets. SLATE outperforms all state of the art models on the HcpPh, Enron, and Colab datasets, demonstrating superior dynamic link prediction capabilities. Notably, it surpasses HTGN by +2.1 1 points in AUC on HepPh and +1.1 points in AP on Enron. Moreover, SLATE shows remarkable improvement of +7.6 points in AUC over EvolveGCN on Colab. It also performs competitively on the AS733 dataset, with scores that are closely second to HTGN, demonstrating its robustness across different types of dynamic graphs. What also emerges and validates our method from this comparison is the average gain of +6.29 points by our fully connected spatio-temporal attention model over the separate spatial attention model and temporal model approach, as used in ROLAND-GT. We also demonstrate significant gains against sparse attention models like DySat, with
7

---

an increase of +6.45. This study, conducted on the protocol from [55], emphasizes SLATE capability in handling discrete-time dynamic graph data, offering sigmificant improvements over existing models.
Table 2: Comparison to CTDG models discrete data using [60] protocol (AUC).
Method
CanPar
USLegis
Flights
Trade
VNte
Contact
Avg.
JODIE [27]
78.21 + 0.23
82.85 # 1.07
96.21 # 1.42
69.62 + 0.44
68.53 # 0.95
96.66 0.89
82.01 = 0.83
DyREP [43]
73.35
82.28 0.32
95.95 0.62
6.84
67.18
1.04
96.48
0.14
80.45 1.10
TGAT [52]
75.69 a: 0.78
75.84
1.99
64.01 0.12
52.83 + 1.12
96.95 a 0.08
76.58 0.71
TON [38]
76,99 1,80
83.34
0.43
0.13
69.10 1.67
69.71 + 2.65
97.54
82.48 = 1.17
CAWN [48]
3.27
77.16
1166+0.33 0.39
08.45
6.154
53,09 = 0.22
89.99
77.16 0.74
EdgeBank [35]
64.14 0.00
62.57 0.00
0.00
6,.75
62.97 0.00
94.34 + 0.00
73.50 0.00
TCL [47]
72.46 4 3.23
76.27
a 0.63
91.21
6.05
51.88 4: 0.36
94.15 a: 0.09
75.11 2: 0.73
GraphMixer [7]
83.17 +: 0.53
76.96
4 0.79
91.13 0.01
65.52
$2.46 4: 0.27
93.94 4: 0.02
77.20 0.36
DyGformer (60)
97.76 0.41
77.90 4 0.58
98.93
20.20 1.44
0.62
98.53
83:41 0.51
SLATE
92.37 +:
95.80 0.11
99.07 0.41
99.94 0.05
98.12
96.88 0.26
Comparison to continuous models, on DTDG. Table 2 In dynamic link prediction, SLATE outper- forms models focused on node (TGN, DyRep, TGAT), edge (CAWN), and combined node- pade-pairwise information (hyGFormer,TCL) Notably, it surpasses TCL by over 21 points in average, showcasing the benefits of our temporal cross attention strategies. SLATE's advantage stems from its global attention mechanism, unlike the sparse attention used by TGAT, TGN, and TCL. By employing fully-connected spatio-temports attention, SLATE directly leverages temporal dimensions through its Edge module. This strategic approach allows SLATE to excel, demonstrated by its consistent top performance and further evidenced in Appendix with hard negative sampling results (see Table 17 and Table 16 in Appendix E) We demonstrate average results that are superior by 13 points compared to the most recent model on DTDG, DyGFormer [60].
4.2 Model Analysis
Impact of different SLATE component. Table 3 presents the AUC results of different configurations of SLATE on four datasets. This evaluation demonstrates the impact of our proposed spatio-temporal encoding and the Edge module on dynamic link prediction performance.
Encoding
Edge Module
Enron
CanParl
USLegis
UNtrade
LapPE[]]] + sinus-hased [45]
89.18 + 0.33
82.98 + 0.71
85,22 # 0.24
90.24 + 1.05
SLATE LapPE []]]+ + sinus-based [45]
x
90.57 # 0.27
89.45 : 0,38
93.30 0.29
94.01 = 0.73
V
90.75 + 0.08
90.23 a 0.41
87.50 + 0.50
90.56 + 0.69
SLATE
96.39 = 0.18
92.37 + 0.51
95.80 + 0.11
96.73 = 0.29
Table 3:
Validation of different SLATE component. Results in AUC over 4 datasets.
First, we show the naive spatio-temporal encoding approach using the first l Laplacian eigenvectors associated with the & lowest values [11] (Appendix A.4), combined with sinusoidal unparametrized temporal encoding [45] (Appendix A.5), without the Edge module. The Laplacian is computed sequentially on the w snapshots, then concatenated with the temporal encoding indicating the position of the snapshot, with A = 12 for both SLATE and the naive encoding. The AUC scores across all datasets are significantly lower, highlighting the limitations of this naive encoding method in capturing complex spatio-temporal dependencies.
Replacing the baseline encoding with our proposed SLATE encoding, still without the Edge module, results in significant improvements: +6.47 points on CanParl, +8.08 points on USLegis, and +3.77 points on UNtrade. These improvements demonstrate the effectiveness of our spatio-temporal encoding. Adding the Edge module to the naive encoding bascline yields further improvements: +7.25 points on CanParl and +1 +1.57 points on Enron. However, it still falls short compared to the enhancements provided by the SLATE encoding.
Finally, the complete model, SLATE with the Edge module, achieves the highest AUC scores across all datasets: +9.39 points on CanParl and +10.58 points on USLegis. These substantial gains confirm that integrating our unified spatio-temporal encoding and the Edge module effectively captures intricate dynamics between nodes over time, resulting in superior performance.
8

---

60
Isolated Nodes
Dataset
SLATE w/o trsf
SLATE
50
Colab
85.03 0.72
90.84 + 0.41
USLegis
63.35 1.24
95.80 + 0.11
UNVote
78.30 2.05
99.94 + 0.05
20
AS733
81.50 1.35
97.46 x 0.45
Colab
USLegis
UNVote
AS733
Table 4: Importance of connectivity transfor- mations steps to connect the supra-adjacency matrix. AUC performance in dynamic link prediction.
Figure Average percentage of isolated nodes per snapshot on real world dynamic graphs data.
Critical role of supra-adjacency transformation. Here, we demonstrate the importance of the transformation steps of the supra-adjacency matrix, as detailed in section 1. by removing isolated nodes, adding virtual nodes, and incorporating temporal connections (Figure 2). Table presents the performance of SLATE with and without transformation (trsf) on four datasets. Without these critical transformations, there a systematic drop in performance, particularly pronounced in datasets with high number of isolated nodes, shown in Figure 3 (27% in Colab, 53% in USLegis, 35% in UNVote, and 59% in AS733). These results clearly highlight the significant improvements brought by proposed transformations. More detailed experiments regarding each transformation, particularly on the importance of removing isolated nodes and adding a virtual node, are presented in Tables 12 and 13.
Models
Mem.
t/ep.
Nb params.
EvolveGCN
46Go
1828s
1.8 M
DySAT
42Go
1077s
1.8 M
95
VGRNN
21Go
931s
0.4 M
ROLAND-GT w/o Flash
OOM
1.9
90
ROLAND-GT
44Go
1152s
1.9 M
85
Co ab
SLATE w/o Flash
OOM
2.1 M
USLegis
SLATE
48Go
1354s
2.1 M
UNVotee
SLATTE-erformer
17Go
6978
2.1 M
5
Window Size
Table 5: analysis of model efficiency com- paring the memory usage (Mem.), training time per epoch (t/p.) and the number of pa- rameters (Nb params) on Flights dataset
Figure 4: Model performance based on the win- dow size, w Do corresponds considering all snapshots. Results in average precision (AP).
Impact of the time-window size. We demonstrate in Figure the impact of the time window size on the performance of the SLATE model. A window size of 1 is equivalent to applying global attention transformer to the latest snapshot before prediction, and an infinite window size equivalent considering all the snapshots for global attention. This figure highlights the importance of temporal context for accurate predictions within dynamic graphs. We observe that, in most cases, too much temporal context can introduce noise into the predictions. The USLegis, UNeote and CanParl datasets are political graphs spanning decades (72 years for UNVote), making it unnecessary to look too far back. For all of our main results in Table 2 and Table 1 we fix for simplicity However, our ablations have identified w = 4 as an optimal balance, capturing sufficient temporal context without introducing noise into the transformer encoder and ensuring scalability for model. Therefore, SLATE performances could further be improved by more systematic gross-validation of its hyper-parameters, e.g.
3.
Model efficiency. The classic attention mechanism, with a complexity of O(N2), can be memory- consuming when applied across all nodes at different time steps. However, using Iash-AAtention [9] and light transformer architecture with just one encoder layer, we successfully scaled to the Flights dataset, containing 13,000 nodes and window size of 3. By using the Performer encoder [5], which approximates attention computation with linear complexity, memory usage is reduced to 17GB. Our analysis shows that our model empirically matches the memory consumption of various

---

DTDG architectures while maintaining comparable computation times (Table 5). Furthermore, is over-vvranne per-parameterized relative existing methods. We trained on NVIDIA AVIDIA-Quadro RTX A6000 with 49 GB of total memory.
4.3 Qualitative results
We present qualitative results Figure 5 comparing the graph and its spectrum before and after applying the proposed transformation in SLATE. The projection is made the eigenvector associated with the first non-zero eigenvalue. Before transformation, the DTDG contains isolated nodes (7, 23 and 26) and spatial, as there are no temporal connections, and some projections also occur on isolated nodes due the presence of distinct connected components. After the proposed transformation into connected multi-layer graph, the projection captures richer ppaporl properties of the dynamic graph. By connecting the clusters with a virtual node and adding temporal edges, our approach removes the influence of isolated nodes and enables the construction of an informative spatio-temporal encoding that better reflects the dynamic nature of the graph.
distinet clusters in the snapshot at 3. In this case, the projection is purely
-335
t=1
t=2
t=3
t=1
t=
Figure 5: Projection of the eigenvector associated with the first non-zero eigenvalue on a toy DTDG before and after transformation. On the left, the DTDG unprocessed, showing only spatial projections due to the lack of temporal connections. On the right, after applying the SLATE transformation, the graph captures rich spatio-temporal properties, allowing for more informative spatio-temporal encoding
5
Conclusion
We have presented the SLATE method, an innovative spatio-temporal encoding for transformers on dynamic graphs, based on supra-Laplacian analysis. Considering discrete-time dynamic graphs as multi-layer networks, we devise an extremely efficient unified spatio-temporal encoding thanks to the spectral properties of the supra-adjacency matrix. We integrate this encoding into a fully-connected transformer. By modeling pairwise relationships in new edge representation module, we show how it enhances link prediction on dynamic graphs. SLATE performs better than previous state-of-the-an approaches various standard benchmark datasets, setting new state-of-the-ane art results for discrete link prediction.
Despite its strong performances, SLATE currently operates in a transductive setting and cannot generalize to unseen nodes. We aim to explore combinations with MP-GNNs to leverage the strengths of local feature aggregation and global contextual information. On the other hand, SLATE scales reasonably well graphs up to a certain size but, as is often the case with transformers, future work is required to scale to very large graphs.
10

---

6 Acknowledgement
We acknowledge the financial support provided by PEPR Sharp (ANR-23-PEIA-ON ANR. FRANCE 2030). We would also like to thank the LITIS laboratory in Rouen and especially Leshan- shui Yang, who helped better position our method. We also thank Elias Ramzi for his feedback on the paper and assistance in writing the abstract.
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[2] Soumyanil Banerjee, Ming Dong, and Weisong Shi. Spatial-Tempon Synchronous Graph Transformer network (STSGT) for COVID-19 forecasting, Smart Health, 26, October 2022.
[3] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pages 748-758. PMLR, 2021.
[4] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances neural information processing systems, volume 33, pages 10383-10395, 2020.
[5] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers, 2022.
[6] Peng Chu, Jiang Wang, Quanzeng You, Haibin Ling, and Zicheng Liu. Transmot: Spatial- temporal graph transformer for multiple object tracking. In Proceedings of the IEEE/CVF Winter Conference on upplications of computer vision, pages 1870-4880 2023.
[7] Weilin Cong, Si Zhang Meta, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou Meta, Hang- hang Tong, and Mehrdad Mahdavi. GraphMixer: Do We Really Need Complicated Model Architectures For Temporal Networks? arXiv preprint arXiv:2302.1 /636, 2023.
[8] Emanuele Cozzo, Guilherme Ferraz de Arruda, Francisco A Rodrigues, and Yamir Moreno. Multilayer networks: metrics and spectral properties. Interconnected networks, pages 17-35, 2016.
[9] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. In Advances in Neural Information Processing Systems, volume 35, pages 16344-16359, 2022.
[10] Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov. Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds. IEEF Transactions on Signal 2014.
Processing, 62(4):905-916
[11] Vijay Prakash Dwivedi and Xavier Bresson. A Generalization of Transformer Networks Graphs. arXiv preprini orXiv:20/2.09663 2020.
[12] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29,
2022. OpenReview.net, 2022.
[13] Paul Erdós and Alfréd Rényi. On random graphs I. Publ. math. debrecen, 6(290-297):18, 1959.
[14] Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2):298-305, 1973.
[15] Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. Advances in neural information processing systems, 32, 2019.
[16) Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development Information Retrieval, pages 638,648, 2020.
11

---

[17] Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Term Memory. Neural Computation, 9(8):1735-1788) 11 1997.
[18]
Shengxiang Hu, Guobing Zou, Shiyi Lin, Liangrui Wu, Chenyang Zhou, Bofeng Zhang, and Yixin Chen. Recurrent Transformer for Dynamic Graph Representation Learning with Edge Temporal States. arXiv preprint arXiv:2304. 2rx0w:2304.100791,,, 4 2023.
[19] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A.A. Kohl, Andrew J. Ballard, Andrew Cowie, Bernardino Romera-Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski, Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure predic- 7 2021.
tion with AlphaFold. Nature 2021 596:7873, (96(7777))5883-355
[20] Oumar Kaba and Siamak Ravanbakhsh. Equivariant networks for erystal structures. Advances in Neural Information Processing Systems, 35:4150-4166 2022.
[21] Yannis Karmim, Leshanshui Yang, Raphaël Fournier S'Nichotta, Clément Chatelain, Sébastien
Adam, and Nicolas Thome. Temporal receptive field in dynamic graph learning: A comprehen- sive analysis, 2024.
[22] Jinwoo Kim, Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Se- unghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35: 35:14582-14595, 2022.
[23] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks, arXiv preprint arXiv:1609.00 (1660.02907,99 9 2016.
[24] Thomas N. Kipf and Max Welling. Variational Graph Auto-Encoders. arXiv preprint
161.v:361..073000 11 2016.
[25] Mikko Kivelä, Alex Arenas, Mare Barthelemy, James Gleeson, Yamir Moreno, and Mason A Porter. Multilayer networks. Journal of complex networks, 2(3):203-271, 2014.
[26] Devin Kreuzer, Dominique Beaini, William L., Hamilton, Vincent Létourneau, and Pruden- cio Tossou. Rethinking Graph Transformers with Spectral Attention. Advances in Neural Information Processing Systems, 26:21618-21622
2021.
[27] Srijan Kumar, Xikun Zhang, and Jure Leskovec. JODIE: Predicting dynamic embedding trajectory in temporal interaction networks. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1269-1278, 8 2019.
[28] Ai-Te Kuo, Haiquan Chen, Yu-Hsuan Kuo, and Wei-Shinn Ku. Dynamic Graph Representation Learning for Depression Screening with Transformer. arXiv preprint arXiv:2305.006 56.44v.1, 5 2023.
[29] Clement Lee and Darren J. Wilkinson. A review of stochastic block models and extensions for graph clustering. Applied Network Science 2019 4:1, 4(1):1-50, 12 2019.
[30] Jia Li, Jiao Su, Zhichao Han, Pengyun Wang, Lujia Pan, Hong Cheng, and Jianfeng Zhang. Pre- dicting Path Failure In Time-EEvolvig Graphs. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1279-1289, 5 2019.
[31] Yixin Liu, Shirui Pan. Yu Guang Wang, Fei Xiong, Liang Wang, Qingfeng Chen, and Vincent CS Lee. Anomaly Detection in Dynamic Graphs via Transformer. IEEE Transactions on Knowledge and Data Engineering, (1 1 200 120944, 2021.
[32] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding Graph Structure in Transformers. arXiv preprint I 6 2021.
[33] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[34] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kaneza- shi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 5363-5370, 2020.
12

---

[35] Farimah Poursafaei, Shenyang Huang, Kellin Pelrine, and Reihanch Rabbany. Towards better evaluation for dynamic link prediction. Advances in Neural Information Processing Systems, 35:32928-3293 2022.
[36] Filippo Radicchi and Alex Arenas. Abrupt transition in the structural formation of interconnected networks. Nature Physies, (11):7177770, 7 2013.
[37] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-144111 2022.
[38] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. TGN: Temporal Graph Networks for Deep Learning on Dynamic Graphs. arXiv preprint arXiv: 10637, 2020.
[39] Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural representation learning on dynamic graphs via self-attention networks. In James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang, editors, WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3-7, 2020, pages 519-527. ACM, 2020.
[40] Youngjoo Seo, Michaël Defferrrrd, Pierre Vandergheynst, and Xavier Bresson. Gconv: Struc- tured sequence modeling with graph convolutional recurrent networks. In Neural Information Processing: 25th International Conference, ICONIP 2018, Siem Reap, Cambodia, December 13-16, 2018, Proceedings, Part 25, pages 362-373. Springer, 2018.
[41] Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial. Foundations and Modeling of Dynamic Networks Using Dynamic Graph Neural Networks: A Survey. IEEE Access, 9:79143- 79168, 2021.
[42] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[43] Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. DyRep: Represen- tation Learning over Dynamic Graphs. ICLR 2019, 3 2018.
[44] Eugenio Valdano, Luca Ferreri, Chiara Poletto, and Vittoria Colizza. Analytical computation of the epidemic threshold on temporal networks. Physical Review X, 5(2), 2015.
[45] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. arXiv preprint arXiv:1706.03762, 2017.
[46] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[47] Lu Wang. Xiaofu Chang, Shuang Li, Yunfei Chu, Hui Li, Wei Zhang, Xiaofeng He, Le Song, Jingren Zhou, and Hongxia Yang. TCL: Transformer-hased Dynamic Graph Modelling via Contrastive Learning. arXiv preprint arXiv:2
2021.
[48] Yanbang Wang, Yen Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In ICLR 2021 9th International Conference on Learning Representations, 2021.
[49] Zehong Wang, Qi Li, Donghua Yu, and Xiaolong Han. Temporal graph transformer for dynamic network. In International Conference on Artificial Neural Networks, pages 694-705. Springer, 2022.
[50] Siqi Wei, Bin Wu, Aoxue Xiang, Yangfu Zhu, and Chenguang Song. DGTR: Dynamic graph transformer for rumor detection. Frontiers in Research Metrics and Analytics, 7:1055348, 1 2022.
[51] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for hurge-graph representations. Advances in Neural Information Processing Systems, 36, 2024.
[52] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. TGAT: Inductive Representation Learning Temporal Graphs. ICLR 20, 2020.
13

---

[53] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[54]
Leshanshui Yang, Clement Chatelain, and Sebastien Adam. Dynamic Graph Representation Learning With Neural Networks: A Survey. IEEE Access, 0143460043488 2024.
[55] Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete- time Temporal Network Embedding via Implicit Hicrarchical Learning in Hyperbolic Space. Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, 17:1975-1985, 7 2021.
[56) Yu Yang, Hongzhi Yin, Jiannong Cao, Tong Chen, Quoc Viet Hung Nguyen, Xiaofang Zhou, and Lei Chen. Time-aware Dynamic Graph Embedding for Asynchronous Structural Evolution. IEEE Transactions on Knowledge and Data Engineering, 35(9):955--677,, 7 2022.
[57] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie Yan Liu. Graphormer: Do Transformers Really Perform Bad for Graph Representation? Advances Neural Information Processing Systems, 34:28877-2588
2021.
[58] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[59] Jiaxuan You, Tianyu Du, and Jure Leskovee. ROLAND: Graph Learning Framework for Dynamic Graphs. KDD, 2022.
[60] Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library. Advances in Neural Information Processing Systems, 36:67686-67700, 2023.
[61] Ge Zheng, Wei Koong Chai, Jiankang Zhang, and Vasilis Katos. VDGCNeT: A novel network- wide Virtual Dynamic Graph Convolution Neural network and Transformer-based traffic predic- tion model. Knowledge- Based Systems, 275:1 10676, 9 2023.
14

---

A Supra-Laplacian and other positional encoding
A.1 Spectral Theory on multi-layer networks
To leverage the benefits of fully-connected spatio-temporal attention across all nodes at multiple timestamps, encode the spatio-temporal structure by considering a DTDG multi-layer graph. For a simple DTDG G = {G1, G2. G33 with a fixed number of nodes, we define the square symmetric supra-adjacency matrix R as follows:
A1
I
0
A
I
A2
1 Aa
Then, we can utilize the rich spectral properties associated with its supra-Laplacian L D A. Several studies have analyzed the spectrum those multi-layer graphs [8, 10, 36]. Especially, [36] demonstrated that Φ1. the Fiedler vector, associated with the second smallest eigenvalue λ1 known as the algebraic connectivity or Fiedler value, highlights structural changes between each layer. For DTDG, this provides valuable information about the graph 's dynamics over time. We verified this property experimentally by generating a DTDG containing 3 snapshots of random Erdōs-Rényí graph [13] with 10 nodes each and connecting them temporally according to Eq. (7) (see illustration on Figure 1). We then project all nodes the DTDG onto different vectors associated with eigenvalues Å with Àe λ1 S ... I Amaa We observe that projecting onto Φ1 provides dynamic information, while projecting onto Φb associated with larger eigenvalues X; reveals increasingly localized structures. These properties strongly motivate the use of spectral analysis of multi-layer graph derived from a DTDG to achieve unified spatio-temporal encoding.
A.2 Supra-graph construction
Algorithm I: Computation of supra-laplacian spectrum
Input: G, w.k, t+1
Output: é, A
adjacencies []
for i from max(0,t w) to do
A GetAdjacency(C:]
A + RemoveIsolated((A)
A; AddVirtualNode A,)
adj (aa.enccie..pppen(AA..
Ā < BlockD/ag//a/jaccccces///// Eq. (7)
A + AddTTempCommectionn..)
// Add temporal self-connection only if nodes aren't isolated
L --112
of Aø = (etdFFrreddiiieectosssskk))))
In practice, when isolated nodes are removed, we obtain mask of size N. This mask helps us identify which nodes are isolated at each time step and determines whether their positional encoding the basis of the & eigenvectors. The mask also guides in adding
will be 0* or the projection temporal connections between a node and its past, as isolated nodes do not have temporal connections. In summary, the matrix A has different size from N x W because we remove isolated nodes and add virtual nodes. The masks help us map the actual indices in G to the rows in A.
In Figure 6, we illustrate the process of transforming a random DTDG into connected multi-layer network. the left, we see three independent snapshots, with several isolated nodes (6, 23, and 26) and multiple clusters in the snapshot at = 3. The proposed transformation in SLATE ensures that the resulting luyti-layer graph becomes fully connected by adding temporal connections, removing isolated nodes, and introducing virtual node to bridge the different clusters within each snapshot.
15

---

39
t=1 t=
3
1
= 2
t = 3
Figure Transformation of a random DTDG into connected multi-layer network. The left side shows independent snapshots with isolated nodes and disconnected clusters. The proposed transformation (right) ensures connectivity by introducing temporal edges, removing isolated nodes, and adding virtual node to connect the clusters within each snapshot.
A.3 SupraLaplacian Positional Encoding
Proof the positivity A when the graph is connected [14]
Theorem 1:
The second smallest eigenvalue, A (the Fiedler value), is strictly positive if and only the graph is connected.
Proof 1: Assume that the graph is not connected. This implies that it can be divided into at least two disjoint connected components without any edges connecting them. For such a graph, it is possible to construct vector whose entries correspond to these connected components such that the product o7 Lo: = 0, where Φ; is an eigenvector. This demonstrates that X = 0. On the contrary, if X > O, the only vector that satisfies of Ló; = under normal conditions muon-zero Φ,) is the constant vector, indicating that the graph cannot be divided without cutting edges, thus it is connected.
A.4 Laplacian Positional Encoding
I = T- T- A,D, 1/2 o7 No.
(8)
LapPE = (0i, 2i.2.... a
(9)
L, represents the Laplacian matrix of the graph G.. It is obtained by decomposing the graph as the product of eigenvectors Φr and eigenvalues A,. The Laplacian positional encoding defined in Eq. (9) provides a unique positional representation of the node u,, with respect to the eigenvectors of G..
A.5 Unparameterized temporal encoding
sin
k is even
10000 23, danee
timePE(L,
(10)
cos
10000((Xk+1)/mmm)))
le is odd
In Eq. (10), refers the 1-th snapshot of our DTDG G, and encoding vector of size dime- This temporal is from [45]. To build the ROLAND-GT separate spatío- temporal encoding we concatene the positional encoding LapPE (Eq. (9)) and the time encoding (Eq. (10)).
dimension in our temporal
16

---

A.6 GCN Positional Encoding
We add in our comparison in Figure 7, the GCN positional encoding against our SLATE Model. This encoding is derived from 2-layer GCN as designed by Kipf and Welling [23]. This method aggregates the local neighborhood information around a target node with message passing. We use the node embedding as positional encoding to enhance the transformer's awareness of the local structural context. This approach aims to integrate structural insights into the transformer model. is inspired by the prevalent hybrid architectures combining MP-GNNs and transformers in static Graph Transformers [37]. It reflects an evolving trend in graph neural network research, where the strengths of both MP-GNNs in capturing local graph structures and transformers in modeling complex data dependencies are leveraged to enhance model performance on graph-based tasks. However, in our experiments, found that SLATE significantly outperformed the GCN-based positional encoding.
B
Baselines
Discrete Time Dynamic Graphs Link Prediction models We describe the DTDG models from [55]:
GIN and GAT [24]: : We use static models [53, 46] to showcase the necessity of dynamic model for efficient learning on dynamic graph. GAT is a sparse attention- model, and GIN is MP-GNN model design to have a the maximal expressivity of 1 L.
GRUGCN [40] GRUGCN is one of the first discrete dynamic graph GNN models. They introduced the now standard approach which combines a GNN to process the snapshot, and updating embeddings using a temporal model, in their case GRU.
EvolveGCN [34]: EvolveGCN is an innovative approach adapting the Graph Convolutional Network (GCN) model for dynamically evolving graphs without relying on node embed- dings, effectively capturing the dynamic nature of graph sequences through an RNN to update GCN parameters.
DySat [39]: DySAT use self-attention mechanisms to learn node representations dynamic graphs. It applies self-attention both structurally and temporally with separate module for time and space, the space module similar to GAT [46], and the temporal model is a 1-D transformer.
VGRNN [15]: VGRNN introduce node embedding techniques for dynamic graphs, focusing on variational graph recurrent neural networks to capture temporal dynamics. They employ latent variables for node representation, with SI-VGRNN advancing the model through semi-implicit variational inference for better flexibility. The method suited for sparse graphs.
HTGN [55]: They introduce a novel approach for embedding temporal networks through a hyperbolic temporal graph network (HTGN), effectively utilizing hyperbolic space to capture complex, evolving relationships and hierarchical structures in temporal networks.
ROLAND [59]: ROLAND is a generic framework for graph representation learning on DTDG. They allow to efficiently implement any static graph models combine with RNN- based temporal module.
Continuous Time Dynamic Graphs Link Prediction models We report the description of the CTDG baselines provided in [60].
JODIE [27]:
Tailored for user-item interaction dynamics within bipartite networks, JODIE utilizes dual recurrent neural networks to refresh user and item states, introducing a projec- tion technique predict future state trajectories.
DyRep [43]: Introduces recurrent mechanism for real-time node state updates, comple- mented by a temporal attention module to assimilate evolving structural insights dynamic graphs effectively.
TGAT [52]: Enhances node representations through the aggregation of temporal-topological neighbor features, leveraging local self-attention mechanism and time encoding to discern temporal dynamics.
17

---

TGN [38]; TGN dynamically updates node memories during interactions using sophisti- cated mechanism comprising a message function, aggregator, and updater, thereby crafting temporal node representations through an embedding module.
CAWN [48]: Initiates by extracting causal anonymous walks per node to delve into network dynamics and identity correlations, followed by encoding these walks with recurrent neural networks to synthesize comprehensive node representations.
EdgeBank [35]; Adopts non--onramee non-parametric, memory-centric strategy for dynamic link pre- diction, maintaining a repository of interactions for memory updates and utilizing retention- based prediction distinguish between positive and negative links.
TCL [47] TCL applies contrastive learning to dynamic graph, using transformer- based architecture to capture temporal and topological information. It introduces dual-stream encoder for processing temporal neighborhoods and employs attention mechanisms for semantic inter-dependencies, optimizing through mutual information maximization.
DyGFormer [60]: DyGFormer introduces novel transformer-basee architecture for dy- namic graph learning, focusing on first-hop interactions to derive node representations. employs neighbor co-occurrence encoding scheme capture node correlations and patching technique for efficient processing of long temporal sequences. This approach ensures model effectiveness in capturing temporal dependencies and node correlations.
Datasets
C.1
Datasets description
Table 6: Dataset statistics used in our experiments, with horizontal bar separating datasets from [60] and datasets from [55].
Datasets
Domains
Nodes
Links
Snapshots
CanParl
Politics
734
74,478
14
USLegis
Politics
225
60,396
12
Flights
Transports
13,169
1,927,145
122
Trade
Economics
255
507,497
32
UNVote
Politics
201
1,035,742
72
Contact
Proximity
692
2,426,279
8064
HepPh
Citations
15,330
976,097
36
AS733
Router
6,628
13,512
30
Enron
Mail
184
790
11
Colab
Citations
315
943
10
SBM
Synthetic
1000
4,870,863
50
CanParl: Can. Parl. is a network that tracks how Canadian Members of Parliament (MPs) interacted between 2006 and 2019. Each dot represents an MP, and a line connects them if they both said "yes" to bill. The line's thickness shows how often one MP supported another with "yes" votes year.
UsLegis:
USLegis is a Senate co-sponsorship network that records how lawmakers in the US Senate interact socially. The strength of each connection indicates how many times two senators have jointly supported bill during a specific congressional session
Flights: Flights is dynamic flight network that illustrates the changes in air traffic through- out the COVID-19 pandemic. In this network, airports are represented as nodes, and the actual flights are represented as links. The weight of each link signifies the number of daily flights between two airports.
Trade: UNTrade covers the trade in food and agriculture products between 181 nations over span of more than 30 years. The weight assigned to each link within this dataset reflects the cumulative sum of normalized import or export values for agricultural goods exchanged between two specific countries.
18

---

VNe documents roll-call votes conducted in the United Nations General Assembly. Whenever two nations cast "yes" vote for an item, the link's weight connecting them is incremented by one.
UNVote:
Contact: Contact dataset provides insights into the evolving physical proximity among approximately 700 university students over the course of month. Each student is uniquely identified, and links between them indicate their close proximity. The weight assigned to each link reveals the degree of physical proximity between the students
Enron:
Enron consists of emails exchanged among 184 Enron employees. Nodes represent employees, and edges indicate email interactions between them. The dataset includes 10 snapshots and does not provide node edge-specific information
Colab represents an academic cooperation network, capturing the collaborative efforts of 315 researchers from 2000 to 2009. In this network, each node corresponds an author, and an edge signifies a co-authorship relationship.
Colab:
HepPH:
citation network focused on high-energy physics phenomenology, sourced from the e-print arXiv website. Within this dataset, each node represents research paper, while edges symbolize one paper citing another. The dataset encompasses papers published between January 1993 and April 2003, spanning total of 124 months.
HepPh
AS733: AS733 represents an Internet router network dataset, compiled from the University of Oregon Route Views Project. This dataset consists of 733 instances, covering the time period from November 8, 1997, to January 2, 2000, with intervals of 785 days between data points.
SBM: SBM is synthetic dynamic datasets generated with Stochastic Block Models methods. It contains 1000 nodes and 50 snapshots. We added this datasets, because unlike most of real world datasets, SBM is not a sparse graph.
C.2 Datasets split
For the datasets from [60], we follow the same graph splitting strategy, which means 70% of the snapshots for training, 15% for validation, and 15% for testing. We use the same number of snapshots as in HTGN [55], the value varies for each dataset (Table 7).
Datasets
HepPh
AS733
Enron
Colab
(number snapshots in test)
10
3
3
Table 7: 1 represents the number of snapshots in the test dataset. The DTDG is split temporally, following [55]
D Implementation details and parameters search
For each of our experiments, we used fixed embedding size of d 128, a time window w 3, and a single layer of transformer Encoder. Additionally, for the calculation of our positional encoding vectors, we consider that the graph always undirected. In Table we provide the remaining hyperparameters that we adjusted based on the datasets. We selected these datasets by choosing the hyperparameters that yielded the best validation performance AP. k the number linearly independent eigenvectors we retrieve, it's important to note that d does not increase when dim_pe nhead_ is the number of head inside the Edge Representation module define in section 3.3. nhead_ encoder is the number of head inside SLATE section 3, dim_ ffn is the dimension of the feed forward networks SLATE and norm_fire first is condition SLATE to weither not applying a layer norm before the full attention.
grow because d'
19

---

Parameters
Search Range
k nhead_xa
[4.6,10,12,14]
[1,2.4,8]
nhead_encodee encoder
[1,2,4,8]
dim dim_ffn
[128,512.1024)
norm_ first
[True,False]
learning_ratee
weight_decas
[0,5e-7]
Table 8: Hyperparameter search range.
E Experiments: Additionnal results
E.1 AP results for DTDG models
We present additional results with Average Precision metrics to evaluate the dynamic link prediction capibility of models. SLATE outperforms all other DTDG models across various datasets, achieving the highest average precision (AP) scores. Specifically, SLATE surpasses the best-performing model, HTGN, with significant improvements: +1.22 1.22 on HepPh, +1 .009 on Enron, and +3.33 on SBM. This highlights the effectiveness of our approach in dynamic link prediction tasks.
Table 9: Comparison to DTDG models on discrete data. AP
Method
HepPh
AS733
Enron
Colab
SBM
Avg
GCN
73.67 1.05
97.11 + 0.01
91.00 + 0.73
90.17 0.25
94.57 = 0.30
89.30 : 0.47
GIN
70.55 0.84
93.43
89.47 : 1.52
87.82 = 0.52
85.64 0.11
85.38 = 0.69
ExolveGCN
81.18
95.28 0.01
92.71 + 0.34
87.53 + 0.22
9.174
89.81 = 0.33
GRUGCN
85.87 +5.87
96.64 1.4400.20
93.38 + 0.24
87.87 0.58
91.73 0.46
91.09 0.35
DySat
0.23
93.06 1.05 0.12
90.40 1.47
9.47
91.07 0.66
VGRNN
80.95 0.94
96.69 0.31
93.29 + 0.69
87.77 0.79
90.53
89.85 + 0.57
HTGN
89.52 0,28
0.00
94.31 + 0.26
91.91
0.13
93.77 = 0.15
ROLAND-GT
82.75 + 0.31
93.66 + 0.14
89.86 + 0.29
85.03 1.96
93.62 = 0.28
88.98 = 0.59
SLATE
90.74 0.51
98.16 0.36
95.40 + 0.29
92.15 + 0.28
98.04 = 0.29
94.90 + 0.34
E.2 Comparison state of the art: Hard Negative Sampling
We present a extensive set of results for our method in comparison to CTDG models in the task of dynamic link prediction on discrete-time dynamic graphs in Table 17 and Table 16. Here, we emphasize the effectiveness of our model when employing hard historical negative sampling. Historical negative sampling technique (hist) was introduced in [35] to enhance the evaluation of model's dynamic capability by selecting negatives that occurred in previous time-steps but are not present at the current time for prediction. Inductive negative sampling evaluating the capability of models to predict new links that never occured before. Our results demonstrate that our model excels distinguishing hard negative edges compared to other CTDG models, evidenced by improved performance both AP and AUC metrics. SLATE also consistently outperforms other models using the indudctive (ind) sampling method across multiple datasets, showcasing its superior capability in capturing dynamic graph interactions. Notably, SLATE achieves significant improvements on datasets such USLegis and Trade, demonstrating its robustness and effectiveness in dynamic link prediction tasks.
E.3
Model Analysis: Additional results
Figure provides a comparison between SLATE spatio-temporal encoding and separate spatial and temporal encodings, including the Laplacian [12] (Lap Eq. (8)) and GCN (Appendix A.6) encodings. For calculating the spatial encoding, we selected two common strategies; the first involves using, as we do, the first & eigenvectors of the Laplacian [12], but only for the current snapshot. Empirically,
20

---

Table 10:
Impact of Edge module on Dy- namic Link Prediction task. ROC-AUC.
SLATE
LapPE+Timer TimePE
GCNPE +imePE
Average Precision
Datasets
SLATE w/o Edge
SLATE
CanParl
89.45 + 0.38
92.37 # 0.51
USLegis
93.30 + 0.29
95.80 = 0.11
Flights
99.04 0.61
99.07 = 0.41
Trade
94.01 = 0.73
96.73 0.29
UNeo
93.56 # 0.68
99.94 = 0.05
Contact
97.41 + 0.10
98,12 = 0.37
HepPh
90.44 + 1.07
93.21 + 0.37
Enron
CanPart
USLegis
Tlade
AS733
96.84 0.26
97.46 + 0.45
Figure 7: Comparison of SLATE encoding against separate structural/positional encoding and time encoding.
Enron
90.57 0.27
96.39 0.18
COLAB
86.34 0.34
90.84 = 0.41
we found that the GCN encoding did not yield satisfying results, in contrast to the hybrid architecture strategies widely used for static Graph Transformers [37].
We show Table 10 SLATE, with its cross-attention mechanism for edge representation, significantly enhances the predictive accuracy of the SLATE w/o Edge model. We show improvement across various datasets, further emphasizing the importance of modeling temporal interactions explicitly, we gain for example +6.4 points on UNVote, +2.6 points on USLegis and +5.8 points on Enron. SLATE's ability to capture intricate dynamics between two nodes across time dimensions results in substantial performance gains, making it valuable addition to our model architecture.
Impact the time-pooling function. In Table 11, we present the performance of the time-pooling function used in section 3.3, across the US Legis, UN Vote, and Trade datasets, with the time window set to w = 3. Using & = corresponds to averaging over all snapshots within the window, whereas k focuses exclusively the last element of Eus- The results indicate that averaging (mean pooling) consistently outperforms max pooling, irrespective of the value. For our primary analysis, therefore adopt k
Table 11: Comparison of SLATE for several time pooling methods (random sampling), on USLegis,
UNVote and Trade.
USLegis AUC
UNvote
Trade
Pool
AP
AUC
AP
AUC
AP
Max
93.03
88.68
87.92
87.72
93.37
93.32
Avg. 3
94.50
89.67
99.72
99.75
96.71
96.88
Avg. 2
95.35
92.17
99.69
99.67
96.76
96.93
Avg. 94.67
91.28
99.59
99.44
96.78
96.97
Detailed analysis of the DTDG-to-multi-ayy transformation in SLATE We provide a closer examination of the performance SLATE under various transformations applied to the DTDG during its conversion into multi luyti graph. The Table 12 demonstrates the negative effect of retaining isolated nodes, which leads to a significant drop in performance on both the Colab and USLegis datasets. By removing these nodes and focusing the spectrum associated with the first non-zero eigenvalue, SLATE achieves a substantial performance improvement.
The Table 13 highlights the importance of introducing virtual node (VN) that connects clusters within each snapshot. Without the VN, the model underperforms, as shown in the results for the Enron dataset. This confirms that each transformation step, from removing isolated nodes to adding temporal connections and VNs, plays a critical role in enhancing the quality of the spatio-temporal encoding.
AUC: Impact of time window on multiple models The analysis Table 14 demonstrates that the impact of the time window on model performance is consistent across different types of models, including our transformer-basee approach and two MP-GNNs (EGCN and DySAT). Interestingly, we observe that relatively short time window produces optimal results for all models the UNVote
21

---

Models
Colab
USLegis
Models
AP
AUC
SLATE with isolated nodes
86.73
66.57
SLATE w/o VN
93.74
95.18
SLATE
90.84
95.80
SLATE
95.40
96.39
Performance impact AUC of keeping isolated nodes on Colab and egis datasets. Removing isolated nodes and focus- ing on the first non-zero eigenvalue spectrum leads to a significant performance boost.
Table 12:
Table 13: Effect of introducing virtual node (VN) on the Enron dataset. The addition of the VN improves SLATE's performance in terms of both AP and AUC.
dataset, which spans 72 snapshots. Specifically, both EGCN and DySAT achieve their highest AUC with W = 4, while SLATE achieves peak performance at W = 2. This indicates that capturing spatio-temporal dynamics does not necessarily require long temporal windows, and in fact, shorter windows can often lead to better performance by focusing on more immediate temporal interactions.
Model
Nb param.
W
W =
W = 3
W = 4
W 5
W 0O
EGCN
1.8M
86.96
86.48
86.74
87.66
85.26
86.74 74
DySAT 1.8M
83.93
81.90
86. 15
88.71
80.08
77.04
SLATE 2.1M
96.68
99.73
98.74
95.90
95.79
92.24
Table 14: Effect of time window size on AUC for different models. Shorter windows provide optimal results across all models.
E.4 More qualitative analysis
We conduct fine- Ene-grained analysis of the impact of not processing the DTDG correctly. Figure demonstrates that without temporal connections, the result is purely spatial projections with no spatio-temporal information, as the three snapshots remain independent. Figure illustrates the effect of retaining isolated nodes while adding temporal connections. Keeping these nodes leads to multiple disconnected components the graph, where many projections focus solely on the isolated nodes, neglecting the core structure of the DTDG. This issue is further intensified by the fact that we consider only the cigenvectors associated with the first non zeroro eigenvalue, limiting the ability to capture the full ppatio-temport dynamics.
A =
A = 0.93
=
Figure 8: Effect of missing temporal connections in DTDG. Without temporal edges, the figure illustrates that the projections are purely spatial, and the three snapshots remain independent, with no spatio-temporal interaction captured.
E.5 Scalability
In Table 5, we demonstrate that Performer [5] significantly reduces memory consumption and speeds up training time per epoch. Moreover, as shown in Table 15, using Performer efficient
22

---

A5 1.0
A 1.0
A 1.0
8 f t
t= 1 8 t 3 t
2
3
Figure 9: Effect of retaining isolated nodes in a DTDG with added temporal connections. The figure shows that keeping isolated nodes results in multiple disconnected components, where many projections focus on these nodes, obscuring the overall spatio-temporal structure of the graph.
approximation of the attention matrix with linear complexity does not significantly degrade the results compared to the standard Transformer encoder. Performer is a highly advantageous solution for scaling to larger graphs while maintaining the benefits of dynamic graph transformers. Its linear complexity allows it to handle larger datasets efficiently, without sacrificing performance.
does
Models
AS733
USLegis
UNtrade
LLATE-Transfommet
97.46 0.45
95.80 0.11
96.73 0.29
95.39 + 0.61
95.14 + 0.84
96.21 # 0.77
Table 15: AUC performance comparison between SLATE using a standard Transformer encoder ([45)) and a Performer encoder ([5])
23

---

Table 16: Comparison CTDG models discrete data. ROC-AUC
NSS
Method
CanParl
USLegis
Flights
Trade
UNVote
Contact
JODIE
78.21 0.23
82.85
1.07
96.21 1.42
69.62 + 0.44
68.53 0.95 96.66 0.89
DyREP
73.35 3.67
95.95 1.99 0.78 0.62
82.28 0.32
67.44 +..4
67.18
1.04 96.48 0.14
TGAT
94.13
64.01
0.12
52.83
1.12 96.95 # 0.08
TGN
1.80
83.34
9..12
6..10
69.71
89.99 # 0.34 #
97.54 + 0.35
CAWN
3.227
0.39
98.45
6.154
53.09
rms
EdgeBank
6.004
02.57
90.23
6.075
62.07
94.34 + 0.00 0.38
TCL.
73.46
76.27
91.21
64.72
94.15 + 0.09
GraphMixer
0.53
7.796
91.13
6.55
93.94 0.22
0.02
DyGformer
9..4
0.58
9.09
1.42
5..12
98.53 = 0.01
SLATE
0.11
99.07 - 0.41
96.73 0.29
99.94 0.05
98.12 + 0.37
JODIE
62.44 + 1.11
68.97 6.44
68.92
76.84
1.01
96.35 + 0.92
DyREP
70.16
9.144
69.43
64.36
74.72
1.43
96.00 + 0.23
TGAT
7.94
73.47
72.20
6.637
53.95 3.15
95.39 0.43
TGN
23.08
84.53
68.39
63.43
73.40
93.76 1.29
CAWN
7..96
7.462
66.11
6.74
51.27
83.06 0.32
hist
EdgeBank
63.04
67.41
70.04
8.00
89.62
0.00 92.17 0.00
TCL
09.95
83.97
3.71
70.57
1.04
52.29
2.39 93.34 0.19
GraphMixer
79.03 # 1.01
85.17 0.70
7.23
63.20
52.61 # 1.44
93.14 0.34
DyGformer
97.61 0.40
90.77 1.96
68.09
1.18
64.27 1.78
97.17 0.05
SLATE
88.71 + 0.43
90.69
0.50
76.83
92.14 92.114.......
98.62
0.49 94.29 + 0.09
JODIE
52.88 + 0.80
59.05 +
69.99
(99.99
66.82
73.73 1.61
94.47 1.08
DyREP
63.53
05414 72.80
94.23 0.18
TGAT
72.47 1.1.177722255577777411111166333
5.
94.10 0.41
TGN
2.81
72.69 +.77 91.64 1.72
CAWN
52.75 87.68 0.24
ind
EdgeBank
61.41 0.00 68.66 01:00000000000000000000000000000 74.20 00110000000000000000000000000000
72.85
85.87 0.00
TCL
# 70.52 0.94 84.22 0:21
120 91.23
52.02
GraphMixer
66.33 0222
51.89 51.89
90.9609..6000000 0.27
DyGformer 96.70 + 0.59 055
53.37 $8.33 95.01 0.15
SLATE
93.74 0.08 33334440889999233000000116614419
92.78 0.06 94.03 -
24

---

Table 17: Comparison CTDG models discrete data. Average Precision.
NSS
Method
CanParl
USLegis
Flights
Trade
UNVote
Contact
JODIE
69.26 0.31 75.05 1 95.60 1.73 64.94 0.31 63.91 = 0.81 95.31 1.33
DyREP
66.54 2.76 0.39 95.29 0.72 63.21 0.93 62.81
95.98 0.15
TGAT
70.73
61.7 01. # 41 65.77222... 96.89
0.98 96.28 #.09
TGN
CAWN
69.82 (00 65.3...2222.
98.51
52.8 90.26
EdgeBank
# 00010000000000000000000011110000 58.49 92.58 0.00
rms
TCL
# 35001122000000440400000000001113 5.090 92.
GraphMixer
77.04 = 77700400077777100000000000001010 010.0//0000000000000000000000110 91.2
97.36 |1 04.22
SLATE
92.44 0,4 98.61
0.41
96.01
99.91 97.68 0.13
JODIE
70.00.2 95.31
DyREP
67. 0..9 59.
86.88 67.61
19.30
96.39
TGAT
67.13 TTT1444286..44440022230000554114
96.05
TGN
6.07 44444417766611114444444444441113 69.37 6.937 93.05 92
CAWN
66.53 68.82 03 51.26 0.04 0.0466664.444 84.16
hist
EdgeBank
63.84
00.0 01.32
84.89 0.00 88.81 0.00
TCL.
6.00 5555
70.68
52.30
93.86
GraphMixer
1.
93.36
DyGformer
97.00
66.59 83.30
60.84 6..41
97.57 0.06
SLATE
84.38
83.53
75.09
84.05
96.85 93.58
48.42 4 0TA.36166660.722.100000000000143
1.78
DyREP
58.61 1 0.86 83.44
TGAT
TGN
65544422277.33441111222222221110 67. 97..882277777888332
2.87
CAWN
67.75 +
52.4444433 89.31
ind
EdgeBank
62.16 0.00 0101
85.20
TCL
65.85 11111111111133333111111101111110
91
GraphMixer
69.48 0.63
74.87 52. 51.60 90.87 0.35
DyGformer
95.44 + 0.57 |0
94.75 0.28
SLATE
0.51 039
=
92.87
03.74 9
94.52 0.86
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper focuses on a unified spatio-temporal encoding based on the spectrum the supra-Laplacian, as developed in section 3.1. We also introduce a fully-connected architecture utilizing this spatio-tempp temporal encoding section 3.2 for the task of link prediction section 3.3. Each of these claims is validated in Table 3, as well as the claim better SLATE performance against state-of-the-ar methods in Tables and 2.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of SLATE in the conclusion section 5, where we list multiple negative points our work and suggest possible improvements, particularly in terms of better scalability and evaluating SLATE on other graph node-based tasks.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
26

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We state in section 3.1 that connected graph has its second eigenvalue strictly positive. We include this proof and its source in Appendix Appendix A.3.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in Appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide a comprehensive overview of our model Figure Detailed discussions of our architecture can be found in sections 3.2 and 3.3. Also, algorithm of our supra-Laplacian computation in Appendix A.3. Implementation specifics are outlined in the implementation details section of section 4 and further elaborated in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
27

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code of SLATE is provided at this link:
Our code is designed to be comprchensible, ensuring that all presented results are repro- ducible.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ ctaaps.cc/ubblicee det/ggddee//ooeeuubiiiii /oode/ubdiesseeeeeeeeee wwtbbbmmsssoonPee ssinnoolicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The selection of datasets, their splitting, and descriptions presented in Appendix C. We use the same evaluation protocols as papers well-recognized by the com- munity [60, 55]. Hyperparameter optimization is detailed in Appendix D, and the optimizer settings are described at the beginning of section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
28

---

Following the protocols we are based on, all results in the paper, including those from ablation studies, are averaged over runs with the standard deviation reported.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The analysis of the time-memory efficiency our model is presented in Table 5, where also compare it with other state-of-the- of-the-art models. We also detailed the number of parameters SLATE.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://neet //tner/nnne..p/ee oc
Answer: [Yes]
Justification: Our research adheres strictly to the NeurlPS Code of Ethics. Our study does not involve sensitive data or unethical practices, and we have followed all relevant guidelines ensure ethical compliance throughout work.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
29

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our model is discriminative model for link prediction on academic datasets, which do not contain any private or sensitive information.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymenn of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We don't release new data or harmful generative models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-us, should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
30

---

Justification: We properly cite all the datasets and baselines used in our paper. Each dataset and model is credited its original creators, and we adhere to the specified licenses and terms of use. The evaluation protocols we employ are based on established standards from previous works, ensuring compliance with the original authors' conditions.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datase has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification: Our paper introduces new assets, including code implementations and datasets for DTDG. Detailed documentation is provided alongside these assets, following structured templates that include information about training and licensing.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not conduct research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
31

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We do not conduct research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "yxdXqqJutt", "reviewer": "Reviewer_kt1z", "summary": "This work introduces Supra-Laplacian encoding for spatio-temporal Transformers (SLATE) which aims to learn both spatio and temporal information in a dynamic graph with a transformer architecture. The key is to convert Discrete Time Dynamic Graphs into multi-layer networks and then extract the spectral features of their supra-Laplacian matrix to improve upon existing dynamic graph transformer designs. Additionally, SLATE employs a cross-attention mechanism to accurately model nodes' pairwise relationships, improving dynamic link prediction. The proposed SLATE model performs competitively to both CTDG and DTDG methods on discrete graphs.", "questions": "- In the ROLAND paper, which is a close competitor to this work, the MRR metrics is used for evaluation, why is the AUROC adapted in this work instead as it has been shown to be very limited and biased towards the 1 negative sample that is compared against each positive test edge. \n\n- there are types in the paper for example \"loose\" on line 5 should be \"lose\"\n\n- how are the CTDG methods applied on the discrete datasets, some performance looks low.", "limitations": "The limitations are discussed sufficiently in the paper. More discussion on negative societal impact might be included such as downstream applications of anomaly detection or recommendation systems for temporal graph learning methods,", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- **originality**: connecting DTDGs into a multi-layer graph and then compute spectral properties of a Supra-Laplacian matrix is a novel approach in the literature. The empirical performance also demonstrates that this approach can outperform existing methods with its spatio-temporal reasoning capabilities. \n\n- **extensive evaluation**: The proposed SLATE method compares favorably to both CTDG and DTDG methods on discrete datasets with existing evaluation of testing 1 positive edge against 1 negative edge. In addition, model analysis experiments and ablation studies provides insights into the model components and choices. Additional experiments with hard negative samples are also included in the appendix.\n\n- **clear presentation**: the paper is easy to follow and the main idea is presented well", "weaknesses": "- **scalability**: my main concern is the scalability of the method as the authors also pointed out as a limitation. Even with the time window (which truncates the history of the temporal graph), the $N^2 w^2$ complexity remains very high and only feasible for networks with up to thousands of nodes, In addition, there is a large amount of precomputation needed for the supra-Laplacian and computing its eigenvectors. \n\n- **window size**: one of the core hyperparameter of SLATE is the choice of window size, as the study in Figure 4 shows that there are some common optimal window size for the CanParl Colab and USLegis datasets. These datasets mostly contains a small number of snapshots thus might be why 4 is a good choice. In practice though, it might be difficult to tell which window size is optimal without extensive experiments to select it. It would also be interesting to see if the length of the window is related to other factors in the architecture, size of the multi-layer network, transformer dimension etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank reviewer kt1z for their meaningful and valuable comments.**\n\n**W1 on scalability:**\nLike any Transformer model, SLATE's primary scalability bottleneck is the quadratic complexity of the attention matrix. However, as noted by reviewer nC2C, we mitigate this with FlashAttention, allowing SLATE to handle dynamic graphs with over 10k nodes. As shown in ***Table 1*** of the global response, SLATE's memory usage on Flights is comparable to that of several state-of-the-art dynamic link prediction methods, *e.g.,* EvolveGCN and DySAT.\n\nTo further test SLATE's scalability on larger graphs, we use Performer (applied for static graphs in GraphGPS), which approximates softmax calculations with Random Fourier Features and reduces attention's complexity from quadratic to linear. With Performer, SLATE scales to datasets like FB with over 45k nodes. In preliminary experiments using Performer's default hyperparameters, SLATE achieved a 77.5% AUC score on the FB dataset, above EvolveGCN and DySAT. We expect to improve these results with more careful parameter tuning.\n\nWe also applied Performer to several datasets used in the submission, such as AS733, Legis, and Trade. As shown in ***Table 2*** of the global response, SLATE/Performer's performance remains close to SLATE's and significantly exceeds state-of-the-art results on these datasets. We believe attention approximation is a promising way to scale SLATE to larger datasets while maintaining excellent performance. We would be glad to include these new results and discussions in the final paper if accepted.\n\nRegarding the scalability of the eigenvector calculation, its complexity is $\\mathcal{O}(k^{2}N^{'})$  [3], with $k$ the number of kept eigenvectors and $N^{’}$ the number of nodes in the supra-adjacency matrix after removing isolated nodes. Note that $k$ is relatively small in our experiments (around 10-15). In practice, the eigenvector calculation is small in SLATE's computation: on the Facebook dataset, our model ran in 303 seconds per epoch ($k=6$) without pre-computing the eigenvectors compared to 577 seconds for VGRNN.\n\n\n**W2 on time window selection** \n\nThe time window is indeed an important hyper-parameter; however, we obtained stable results using a fixed window size $W$ of 3 for all experiments. An extensive grid search across all datasets could improve performance; for example, on CanParl, a window size of 4 yields better results.\nTo explicitly fulfill the reviewer's request regarding the impact of W on datasets with a larger number of snapshots, we conducted several experiments on UNVote, which contains 72 snapshots. As shown in the ***Table 3*** below, we observed similar trends for SLATE than those on Figure 4 in the paper. The optimal window size in these runs is 3. \nTo address the reviewer's questions about the relationship between model and window size, we evaluate models of different nature and complexity than SLATE. We observed a similar trend among different models, *i.e.,* a local temporal window is preferable than keeping the full history, *e.g,* DySAT performances dropped by 9 points with $W=\\infty$, where $\\infty$ considers all snapshots for predictions. We would be glad to elaborate this interesting discussion in the final paper.\n\n***Table 3: AUC Performance Based on Temporal Window Size on the UNVote Dataset***\n| Model | # of parameters  | W \\= 1  | W \\= 2  | W \\= 3  | W \\= 4  | W \\= 5  | W \\= $\\infty$ |\n| :---- | :---- | :---- | :---- | :---- | :---- | :---- | :---- |\n| SLATE | 2.1 M | 96.68 | 98.77 | 98.74 | 95.90 | 95.79 | 92.24 |\n| EGCN | 1.8M | 86.96 | 86.48 | 86.74 | 87.66 | 85.26 | 86.14 |\n| Dysat | 1.8M | 83.93 | 81.90 | 86.15 | 88.71 | 80.08 | 77.04 |\n\n**Q1 on MRR:**\n\nThe choice of evaluation metrics is crucial and reflects the specific task we are addressing. In our work, we focus on dynamic link prediction as a classification task, while the Mean Reciprocal Rank (MRR) metric is typically used for ranking tasks. Dynamic link prediction aims to classify whether a link between nodes exists. For such tasks, metrics like AUROC are preferred because they provide a threshold-independent measure of model performance across all classification thresholds [4,5]. This is the standard evaluation of models like TGAT or TGN.\n\nMRR is suitable for ranking tasks, such as user-item recommendation (bipartite graphs), when the objective is to rank nodes according to some relevance measure. Papers like JODIE employ MRR to evaluate dynamic link prediction within bipartite graphs like Wikipedia or LastFM, where ranking tasks differ from our classification focus.\n\nExtending SLATE's evaluation to other tasks, such as link ranking, is greatly insightful. Due to the short duration of the rebuttal period, it was challenging to obtain results for these additional tasks. For link ranking, we would need to compute $N \\times (N-1)$ links per node. However, we look forward to exploring this in future work.\n\n**Q2 on typo:** \n\nThank you for catching that typo. We have corrected it.\n\n**Q3 on CTDG performances:**\n\nIn the evaluation of CTDG models, as described in [4,6], discrete datasets like CanParl and USLegis are treated as continuous datasets, with timestamps at regular intervals. For instance, in a dataset with 3 snapshots, timestamps might be $t_1=100$  $t_2=200$, and $t_3 = 300$. CTDG models (e.g., TGAT, DyRep) use these integer values to calculate temporal embeddings, similar to how they process continuous datasets.The performance of CTDG models on these discrete datasets has been taken from [6] as mentioned in l-243 to 247 of our paper. We followed the same evaluation protocol.\n\n[3] Kreuzer et al. Rethinking Graph Transformers with Spectral Attention. NeurIPS 2021\n\n[4] Poursafaei et al. Towards Better Evaluation for Dynamic Link Prediction. NeurIPS 2022\n\n[5] Yang et al. Evaluating Link Prediction Methods. Knowledge and IS 2015\n\n[6] Yu et al. Towards Better Dynamic Graph Learning: New Architecture and Unified Library. Neurips 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PJkEfIZjkx", "reviewer": "Reviewer_nC2C", "summary": "This paper proposes a spatial-temporal encoding for transformers on dynamic graphs. Specifically, graphs at each time step are treated as a single multilayer graph and packed into a larger adjacency matrix, with temporal self-connections between each node and its past. Eigenvectors of the constructed Laplacian are used as positional encoding and concatenated with node features. A standard transformer encoder layer then generates all representations for each node at each time step within a selected time window. To predict a link between two nodes, the model does cross-attention between their representations within the time window. Experimental results show that the proposed model performs better than existing methods.", "questions": "Please see my 2nd point in Weaknesses", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The positional encoding proposed by this paper aims to jointly model spatial and temporal dependencies, which is a plausible improvement over existing methods.\n* The proposed model shows strong empirical performance compared with existing approaches. In particular, the proposed positional encoding works better than simply concatenating LapPE and sin/cos", "weaknesses": "* Scalability/efficiency may still be a concern on large graphs, though the paper shows good engineering (e.g., Flash-Attention) can help\n* Some finer-grained ablation studies are missing. For example:\n    * Instead of removing isolated nodes in preprocessing, can we keep the disconnected graph and just use eigenvectors corresponding to non-zero eigenvalues?\n    * The transformer itself can already get global information and I see no strong reason to use virtual nodes additionally. How would the model behave without virtual nodes? How would \"virtual nodes + GNN\" behave?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank reviewer nC2C for their meaningful and valuable comments.**\n\n**W1 on scalability:**\n\nAs any Transformer model, SLATE’s main bottleneck in terms of scalability is the quadratic complexity of the attention matrix. However, as you pointed out, we use Flash attention to mitigate this issue. Based on this efficient engineering technique, we manage to apply SLATE to dynamic graphs having more than 10k nodes, with a broad-audience GPU device (NVIDIA RTX A6000 with 49 GB memory). We show in ***Table 1*** of the global response on Flights (13,169 nodes) that the memory demand of SLATE is comparable to several state-of-the-art methods for dynamic link prediction, *e.g.*,  EvolveGCN, Dysat, ROLAND-GT with Flash attention.\n\nTo further challenge the scalability of STATE to larger-scale graphs and explicitly address reviewers’ concerns, we propose to apply attention approximations to reduce our memory consumption. Specifically, we explore the use of the Performer method [2], which approximates the softmax calculation using Random Fourier Features, thus breaking the quadratic complexity to linear complexity. Using Performer, SLATE is able to scale to datasets like Facebook containing over 45,000 nodes with the same NVIDIA RTX A6000 (49 GB). We conducted preliminary experiments on this Facebook dataset using the default Performer’s hyperparameters, and reached 77.5% AUC score, which is already above EvolveGCN and Dysat. We expect to significantly improve these results by a more careful parametrization. \n\nWe also apply Performer on several datasets used in the submission, *i.e.*, AS733, USLegis and Trade, and show that the performance of SLATE/Performer remains close to the performance of SLATE, and remain significantly above state-of-the-art results on those datasets (see ***Table 2*** of the global answer). We believe that the application of such attention approximation is a very promising way of scaling SLATE to larger datasets, while maintaining excellent performances. We would be glad to include these new results and discussion in the final paper if accepted.\n\n**W2 on ablation studies:** Following RnC2C’s request, we provide finer-grained ablation studies regarding supra-Laplacian’s computation. We would be glad to include those results in the final paper.\n\n**W2.1 on pre-processing isolated nodes:**\n\nThis is an excellent question, and one that we've studied extensively. To fulfill *RNc2c’s* request, we evaluated the spectral analysis obtained when keeping isolated nodes but only considering eigenvectors associated with non-zero eigenvalues. Qualitatively, we provide visualizations (see the visualization 2 of the pdf file attached to the rebuttal) showing that the resulting spectrum is significantly more noisy than that obtained after removing isolated nodes, especially because many eigenvectors encode a projection on the kept isolated nodes. Those projections do not capture meaningful information on the spatio-temporal structure of the dynamic graph.\nTo consolidate the comparison, we also provide a quantitative ablation study on the ***Table 4*** below on the USLegis dataset: we can see that that there is a huge drop in performance (~30 pts in AUC) when not removing isolated nodes but ignoring 0 eigenvectors (‘SLATE with isolated nodes 0’) compared to removing them in SLATE. This clearly validates the importance of this pre-processing step.\n\n***Table 4: AUC Performance of SLATE Compared to SLATE with Isolated Nodes, Considering Only Eigenvectors Associated with Strictly Positive Eigenvalues.***\n\n| Models | Colab | USLegis |\n| :---- | :---- | :---- |\n| SLATE with isolated nodes 0 | 86.73 | 66.57 |\n| SLATE | **90.84** | **95.80** |\n\n**W2.2 on virtual nodes:**\n\nTransformers can indeed capture global information without virtual nodes (VNs). Although recent works use virtual nodes with static GNNs to get global information [7], the purpose and motivation in our paper is fundamentally different. Indeed, we use virtual nodes as one step to ensure that our multi-graph is connected, which is crucial for designing a relevant spatio-temporal encoding based on the supra-Laplacian matrix, enabling us to extract meaningful information from the spectral analysis of the supra-Laplacian. In this context, the second smallest eigenvalue represents the graph's dynamics. This is particularly important in cases where a snapshot contains multiple clusters of nodes and remains disconnected even after removing isolated nodes.\nBased on RNc2c’s recommendation, we experimentally demonstrate the importance of virtual nodes. As shown in the ***Table 5*** below, this approach yields a gain of +1.21 points in AUC on the Enron dataset. \n\n***Table 5: AP and AUC Performance of SLATE With and Without Virtual Nodes on the Enron dataset.***\n| Models | AP | AUC |\n| :---- | :---- | :---- |\n| SLATE w/o VN | 93.74 | 95.18 |\n| SLATE | **95.40** | **96.39** |\n\nTo answer RNc2c’s request on \"virtual nodes + GNN\", we implemented the addition of a virtual node per snapshot on a standard DTDG architecture already included in the article, namely GRUGCN, which combines a spatial GCN and a temporal RNN. However, in contrast to results reported on static graphs, we were not able to improve performances over GRUGCN in our dynamic context.\n\n[7] Cai et al. On the Connection Between MPNN and Graph Transformer. ICML 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aZcu8rwbaI", "reviewer": "Reviewer_G1C1", "summary": "This paper proposes SLATE, a novel method for link prediction in dynamic graphs. SLATE transforms dynamic graphs into multi-layer networks and generates a unified spatio-temporal encoding by leveraging the spectral properties of the supra-Laplacian matrix. It uses a fully connected transformer architecture to capture long-range dependencies between nodes across multiple time steps. The authors introduce a cross-attention-based edge representation module for dynamic link prediction. They claim that SLATE significantly outperforms existing state-of-the-art methods on several benchmark datasets", "questions": "Q1. The depiction of adding temporal connections in Figure 2 is difficult to understand. The explanation for adding temporal connections seems inadequate, especially the description of AddTempConnection in Algorithm 1.\n\nQ2. When adding virtual nodes, are multiple virtual nodes created? The explanation regarding virtual nodes appears to be insufficient.\n\nQ3. What are the theoretical advantages of Supra-Laplacian encoding compared to existing graph positional encoding methods?\n\nQ4. What would be the impact of using sparse attention mechanisms instead of fully connected transformers?", "limitations": "This paper discloses all data and code upon acceptance, which limits the ability to verify the reproducibility of this paper.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The idea of transforming dynamic graphs into multi-layer networks and utilizing the supra-Laplacian is innovative.\n\n2. Extensive experiments were conducted on various datasets and baselines.\n\n3. The method shows superior performance compared to state-of-the-art approaches on multiple datasets.", "weaknesses": "W1. The explanation for adding temporal connections in the supra-Laplacian construction stage seems insufficient.\n\nW2. The description of how to construct the supra-Laplacian is not comprehensive enough.\n\nW3. The characteristics of the SLATE model are not clearly defined. For example, the necessity of each step (a)-(d) in Figure 2 lacks convincing arguments.\n\nW4. This paper discloses all data and code upon acceptance, which limits the ability to verify the reproducibility of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank reviewer G1C1 for their questions and remarks, we hope the explanations below will answer their concerns.**\n\n**Q1 & W1.) The explanation for adding temporal connections seems inadequate, especially the description of *AddTempConnection()* in Algorithm 1. The explanation for adding temporal connections in the supra-Laplacian construction stage seems insufficient.**\n\nHaving temporal connections between a node and itself at previous timesteps allows us to build a connected graph, whose spectral analysis provides relevant information of the spatio-temporal structure of the dynamic graph. A single eigenvector incorporates information about the dynamics of the graph, *i.e.* the first non-zero eigenvector if this multi-graph is connected (see Figure 1 left). In the simple case where there are no isolated nodes, this amounts to stacking the adjacency matrices diagonally, as illustrated in Equation 7 (appendix A.1). In practice, we only add a temporal connection if the nodes are not isolated, that is the role of *AddTempConnection()* in Algorithm 1 (Appendix A.2). We checked the correctness of this algorithm. \n\nAdditionally, we have included a visualization (numbered 3) in the PDF attached to the rebuttal to better illustrate the importance of temporal connections. This visualization shows that the spectrum associated with the discrete dynamic graph does not capture spatio-temporal structure, unlike when inter-layer connections are added to model temporal dependencies between nodes.\n\nMore generally, the core of our method is to transform a discrete dynamic graph (DTDG) into a multilayer graph in order to exploit their rich spectral properties, as motivated in lines 42 to 45 of our paper. A dynamic graph can be seen as a MultiLayerGraph, each snapshot of the dynamic graph is represented by a layer of the multilayer graph. In such graphs, identical nodes are connected to each other [8]: in a dynamic graph, this is represented by a connection between a node and its past. \n\n**W2.) The description of how to construct the supra-Laplacian is not comprehensive enough.**\n\nThe construction of the supra-Laplacian is detailed in section 3.1 of the paper and illustrated on Figure 2. We give theoretical and technical precisions in Appendix A (especially sections A1 and A2), and we also resort to common background knowledge on (multi-layer) graphs, *e.g.*, the definition of a supra-laplacian matrix [8,9].\n\n**Q2.) When adding virtual nodes, are multiple virtual nodes created?**\n\nAs indicated on lines 151-152, we add as many virtual nodes as there are snapshots; if $W = 3$, then we add 3 virtual nodes. The purpose of these virtual nodes is to make our snapshot connected in case there are several clusters in it. We've illustrated the need for virtual nodes in Figure 2.a (1 page pdf, global response): at time $t$, there are two clusters, so adding a virtual node connects these two clusters. We also show in ***Table 5*** of the answer to RN2C2 the experimental improvement of adding virtual node. \n\n\n**W3.) The characteristics of the SLATE model are not clearly defined. For example, the necessity of each step (a)-(d) in Figure 2 lacks convincing arguments.**\n\nFigure 2 is the main figure describing the details of the method. Each step is detailed in the text, with references to the precise sections at the top of the columns on the Figure (*e.g.*, step (c) is detailed in section 3.2). In each of those sections, we motivate the necessity of each step (*e.g.*, in section 3.3, we explain how we compute an edge representation from the output of the fully-connected transformer).\n\n **Q3.) What are the theoretical advantages of Supra-Laplacian encoding compared to existing graph positional encoding methods?**\n\nAs detailed in lines 142-145 in the submission, we remind that the main objective of our pre-processing steps is to obtain a connected graph. This ensures that the spectral analysis of the supra-Laplacian matrix provides relevant information about the global dynamics of the graph, which can then be utilized as a powerful spatio-temporal encoding mechanism in graph transformers.\nOur Supra-Laplacian encoding offers a unified approach that captures both spatial and temporal information simultaneously, unlike previous graph positional encoding methods, which separately computed spatial and temporal encodings (*e.g.*, Taddy [10] in the context of anomaly detection). As demonstrated in our ablative experiment (***Table 3*** of the paper), this unified spatio-temporal encoding significantly enhances performance.\n\n**W4.) This paper discloses all data and code upon acceptance, which limits the ability to verify the reproducibility of this paper.**\nAll datasets used in our study comes from public datasets, such as those presented in [6]. In our paper, we have also taken care to detail all the parameters we optimized (see Table 8 in the appendix). SLATE’s source code will released to the community. We are currently working on providing the Area Chair with an anonymized and easily executable version of the code to verify the performance of our model.\n\n **Q4.) What would be the impact of using sparse attention mechanisms instead of fully connected transformers?**\n\nAs indicated in l-262, we have compared our method to state-of-the-art approaches using sparse attention mechanisms, either discrete models such as DySAT, or continuous ones, such as  TGAT, TGN and TCL.\n\nOur experimental results show that SLATE performs significantly better than those methods (*e.g.*, see in the paper ***Tables 1 and 9*** for SLATE *vs* DySat, see ***Tables 2 and 12*** for SLATE vs TGAT)\n\n[8] Radicchi, et al. Abrupt transition in the structural formation of interconnected networks. Nature Physics 2013\n\n[9] Cozzo et al. Multilayer networks: metrics and spectral properties. arxiv preprint (2015)\n\n[10] Liu et al. Anomaly Detection in Dynamic Graphs via Transformer. IEEE Transactions on Knowledge and Data Engineering 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KGO0gnONop", "reviewer": "Reviewer_n3Tf", "summary": "This paper introduces a new method called Supra-Laplacian Encoding for spatio-temporal Transformers(SLATE) to deal with dynamic graph challenges. Its core approach is to enhance the graph transformer(GT) architecture by integrating spatio-temporal information more efficiently. It deploys a new technology to convert discrete-time dynamic graphs into multiplayer graphs and exploit the spectral properties of their associated super-laplacian matrices. SLATE also implements a cross-attention mechanism to explicitly model pairwise relationships between nodes. SLATE can capture the dynamic nature of graphs more accurately with this implementation. SLATE provides a powerful tool for applications ranging from social network analysis to understanding complex biological networks.", "questions": "How does the model perform as the size of the graph increases?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1.SLATE applies spectral graph theory to the dynamic graph domain in a novel way. \n2.The quality of this study is evident in the rigorous experimental setup and the comparion with SOTA methods. It is able to outperform many existing models on nine datasets. \n3.The authors provide a detailed explanation of the method and the underlying theoretical concepts. And the open-source code and the instructions for reproducing the results enhances the clarity and accessiblility.", "weaknesses": "1. The experimental results of CanParl in Table 2 is not very good.\n2.The permutation setting of SLATE may limit its ability to generalise to unseen nodes and large-scale graph data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank reviewer n3Tf for their meaningful and valuable comments.**\n\n**Q.1) How does the model perform as the size of the graph increases?**\n\nScaling our SLATE method to graphs with ~10, 000 nodes has been one central objective in our submission. Through engineering techniques like using FlashAttention and a temporal window, we were able to achieve strong performance on the HepPh (15k nodes) and Flights (13k nodes) datasets, outperforming the baselines on both.\nFollowing reviewer n3Tf's requests on the possibility to apply SLATE to even larger graphs, we conducted several experiments using Performer, a method that approximates attention computation with linear complexity in the number of nodes instead of the quadratic complexity of a classic Transformer. This allowed us to significantly reduce memory usage while maintaining stable performance, as shown in the results presented in ***Table 2*** of the global answer. We show that SLATE/Performer was still able to significantly outperform state-of-the-art results on USLegis and Trade.\nWe also successfully scaled our model on the Facebook dataset containing ~45k nodes, with a memory usage of 31 GB on our NVIDIA RTX A6000 (49 GB) card. Due to the dataset's size, we only had time to run a single trial of our model, achieving an AUC performance of 77.5\\% AUC. This is a very promising result, which still outperforms strong baselines such as EvolveGCN and DySat on this large-scale dataset (as per the results reported for those methods in the HTGN paper [11]).\n\n**W.1) Regarding performance on CanParl:**\n\nWhile SLATE's performance on the CanParl dataset is not the highest, it consistently outperforms other models on the remaining datasets, such as USLegis, Flights, Trade, and UNVote. Overall, SLATE achieves an average performance that is 13 points higher than the second-best baseline across all datasets. This demonstrates SLATE's robustness and effectiveness in capturing the dynamics of various graph structures.\n\n[11] Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete-time Temporal Network Embedding via Implicit Hierarchical Learning in Hyperbolic Space. ACM SIGKDD 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global response to reviewers

We would like to thank all the reviewers for their excellent feedback, their relevant questions, the enthusiastic reception of our SLATE method and their encouragement.

We would like to clarify here some key points raised by the reviewers along the two main lines of concerns: i) the scalability of SLATE and ii) the construction of the multilayer graph from the discrete dynamic graph. We also individually respond to each reviewer below their reviews.

### Scalability (RNc2c, Rn3Tf, Rkt1z)

Reviewers raised concerns on the scalability of our SLATE model due to the quadratic complexity of the Transformer's attention matrix computation.

Firstly, we want to highlight that based on efficient engineering techniques, especially FlashAttention [1], we manage to apply SLATE to dynamic graphs having more than 10k nodes, with a broad-audience GPU device (NVIDIA RTX A6000 with 49 GB memory). In this setting, the memory demand is comparable to several state-of-the-art methods for dynamic link prediction, *e.g.*,  EvolveGCN, Dysat, ROLAND-GT with Flash attention — as shown in the ***Table 1*** (below).

***Table 1 : Memory demand for different models on the Flights dataset (13k nodes), with NVIDIA RTX A6000 (49 GB)***

| Models | Memory usage | Time / epoch |
|---|:---:|:---:|
|EvolveGCN | 46 GB | 1828 s | 
|Dysat | 42 GB | 1077 s |
|VGRNN | 21 GB | 931 s |
|ROLAND-GT w/of Flash |OOM | - |
| ROLAND-GT | 44 GB | 1152 s |
| SLATE w/o Flash | OOM | - |
|SLATE - Flash | 48 GB | 1354 s |
|**SLATE - Performer** | 17 GB | 697 s |


To further challenge the scalability of SLATE to larger-scale graphs and address reviewers’ concerns, we propose to apply attention approximations to reduce memory consumption. Specifically, we explore the Performer method [2], which approximates the softmax calculation using Random Fourier Features, thus reducing quadratic complexity to linear complexity. Using Performer, SLATE scales to datasets like Facebook with over 45,000 nodes on the same NVIDIA RTX A6000 (49 GB), while all tested methods but VGRNN are out of memory on this device. Preliminary experiments on this Facebook dataset using the default Performer’s hyperparameters reached a 77.5% AUC score, which is already above the EvolveGCN and DySAT results reported in the HTGN paper [11]. We expect to improve these results with careful parametrization. We also apply Performer on several datasets used in the submission, *i.e.*, AS733, USLegis, and Trade, and show SLATE/Performer performance remains close to SLATE and significantly above state-of-the-art results on those datasets (see ***Table 2*** below). We believe such attention approximation is a promising way of scaling SLATE to larger datasets, while maintaining excellent performance. We would be glad to include these results and discussion in the final paper if accepted.

***Table 2 : SLATE with a Transformer encoder vs a Performer encoder***

| Models    |  AS733 | Legis | Trade |
| --- | --- | --- |--- |
|  SLATE-Transformer   | 97.46 | 95.80 | 96.73 |
| SLATE- Performer     | 95.28 | 95.02 | 96.49 | 


### Clarifications on supra-Lapacian computation (RG1C1, RNc2c)

To compute the supra-Laplacian matrix from our dynamic graph, we apply 3 main pre-processing steps, as shown in Figure 2a: removing isolated nodes, adding virtual nodes, and adding temporal connections. We remind that the main objective of those pre-processings is to obtain a connected graph from which the spectral analysis of the supra-Laplacian matrix contains relevant information on the global graph’s dynamics to be used as a powerful spatio-temporal encoding in graph transformers (l. 142-145 in submission).

The reviewers raised questions related to the importance of those 3 pre-processing steps.

In the specific answer to RG1C1, we provide clarifications regarding the computation for adding temporal connections. To provide additional insights on the importance of those temporal connections, we add a one-page pdf with a visualization of the spectrum on a toy dynamic graph, which complements our Figure 1 in submission. Here, we show that not including temporal connection yields a spectrum whose eigenvectors are unable to capture the spatio-temporal structure of the dynamic graph.

RNc2c requested finer-grained ablation studies to validate the importance of removing isolated nodes and adding virtual nodes.

For the removal of virtual nodes and fulfilling RNc2c’s request, we evaluated the spectrum obtained when keeping isolated nodes but only considering eigenvectors associated with non-zero eigenvalues. Qualitatively, we provide new visualizations (see pdf file attached to the rebuttal) showing that the resulting spectrum is significantly more noisy than that obtained after removing isolated nodes, especially because many eigenvectors encode a projection on the kept isolated nodes. Those projections do not capture meaningful information on the spatio-temporal structure of the dynamic graph. We also provide a quantitative ablation study on the USLegis dataset that shows a massive drop in performances (30 pts) when not removing isolated nodes but ignoring 0 eigenvectors — see specific response to RNc2c.

Regarding virtual nodes, we clarify in the response to RNc2c that their motivation is fundamentally different to works adding them in GNNs, and that this pre-processing is thus not redundant to the full connections in transformers. To further validate the importance of virtual nodes, we provide new ablation studies showing degraded performances when not including them.

We hope that the work done in this rebuttal helps to clarify the reviewers’ concerns. We remain at their disposal for further discussions on this work.

[1] Dao et al. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. arxiv preprint (2022).

[2] Choromanski et al. Rethinking Attention with Performers. ICLR 2021

Meta-review: This paper proposes SLATE (Supra-Laplacian encoding for spatio-temporal Transformers) which aims to learn both spatial and temporal information in a dynamic graph with a transformer architecture. SLATE converts Discrete Time Dynamic Graphs into multi-layer networks and extracts the spectral features of their supra-Laplacian matrix to improve upon existing dynamic graph transformer designs. To predict a link between two nodes, the model does cross-attention between their representations within the time window. Experimental results show SLATE performs competitively to both CTDG and DTDG methods on discrete graphs. Reviewers think the proposed approach is novel, the experiments results are extensive and promising, and the presentation is clear. The main concerns include efficiency/scalability of the approach on large graphs even with truncated time window, and that the Improvement over baselines in some settings seem mediocre.
Decision: Accept (poster)