We thank reviewer n3Tf for their meaningful and valuable comments.

Q.1) How does the model perform as the size of the graph increases?

Scaling 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. Following 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. We 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]).

W.1) Regarding performance on CanParl:

While 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.

[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.

We thank reviewer G1C1 for their questions and remarks, we hope the explanations below will answer their concerns.

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.

Having 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.

Additionally, 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.

More 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.

W2.) The description of how to construct the supra-Laplacian is not comprehensive enough.

The 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].

Q2.) When adding virtual nodes, are multiple virtual nodes created?

As 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.

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.

Figure 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).

Q3.) What are the theoretical advantages of Supra-Laplacian encoding compared to existing graph positional encoding methods?

As 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. Our 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.

W4.) This paper discloses all data and code upon acceptance, which limits the ability to verify the reproducibility of this paper. All 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.

Q4.) What would be the impact of using sparse attention mechanisms instead of fully connected transformers?

As 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.

Our 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)

[8] Radicchi, et al. Abrupt transition in the structural formation of interconnected networks. Nature Physics 2013

[9] Cozzo et al. Multilayer networks: metrics and spectral properties. arxiv preprint (2015)

[10] Liu et al. Anomaly Detection in Dynamic Graphs via Transformer. IEEE Transactions on Knowledge and Data Engineering 2021.

Thanks for answering my follow-up question. The additional explanation helped me understand your virtual nodes. I think it would be good if you could revise the paper to make this part a little more clear. I raise my score to 4.

We thank reviewer nC2C for their meaningful and valuable comments.

W1 on scalability:

As 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.

To 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.

We 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.

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.

W2.1 on pre-processing isolated nodes:

This 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. To 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.

Table 4: AUC Performance of SLATE Compared to SLATE with Isolated Nodes, Considering Only Eigenvectors Associated with Strictly Positive Eigenvalues.

W2.2 on virtual nodes:

Transformers 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. Based 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.

Table 5: AP and AUC Performance of SLATE With and Without Virtual Nodes on the Enron dataset.

To 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.

[7] Cai et al. On the Connection Between MPNN and Graph Transformer. ICML 2023

We thank reviewer kt1z for their meaningful and valuable comments.

W1 on scalability: Like 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.

To 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.

We 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.

Regarding 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.

W2 on time window selection

The 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. To 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. To 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.

Table 3: AUC Performance Based on Temporal Window Size on the UNVote Dataset

Q1 on MRR:

The 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.

MRR 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.

Extending 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.

Q2 on typo:

Thank you for catching that typo. We have corrected it.

Q3 on CTDG performances:

In 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.

[3] Kreuzer et al. Rethinking Graph Transformers with Spectral Attention. NeurIPS 2021

[4] Poursafaei et al. Towards Better Evaluation for Dynamic Link Prediction. NeurIPS 2022

[5] Yang et al. Evaluating Link Prediction Methods. Knowledge and IS 2015

[6] Yu et al. Towards Better Dynamic Graph Learning: New Architecture and Unified Library. Neurips 2023