Supra-Laplacian Encoding for Transformer on Dynamic Graphs

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.

Strengths

1.SLATE applies spectral graph theory to the dynamic graph domain in a novel way. 2.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. 3.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. 2.The permutation setting of SLATE may limit its ability to generalise to unseen nodes and large-scale graph data.

Questions

How does the model perform as the size of the graph increases?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes

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

Strengths

1. The idea of transforming dynamic graphs into multi-layer networks and utilizing the supra-Laplacian is innovative. 2. Extensive experiments were conducted on various datasets and baselines. 3. 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. W2. The description of how to construct the supra-Laplacian is not comprehensive enough. 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. W4. This paper discloses all data and code upon acceptance, which limits the ability to verify the reproducibility of this paper.

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. Q2. When adding virtual nodes, are multiple virtual nodes created? The explanation regarding virtual nodes appears to be insufficient. Q3. What are the theoretical advantages of Supra-Laplacian encoding compared to existing graph positional encoding methods? Q4. What would be the impact of using sparse attention mechanisms instead of fully connected transformers?

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

This paper discloses all data and code upon acceptance, which limits the ability to verify the reproducibility of this paper.

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.

Strengths

* The positional encoding proposed by this paper aims to jointly model spatial and temporal dependencies, which is a plausible improvement over existing methods. * 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 * Some finer-grained ablation studies are missing. For example: * Instead of removing isolated nodes in preprocessing, can we keep the disconnected graph and just use eigenvectors corresponding to non-zero eigenvalues? * 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?

Questions

Please see my 2nd point in Weaknesses

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

N/A

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.

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

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. - there are types in the paper for example "loose" on line 5 should be "lose" - how are the CTDG methods applied on the discrete datasets, some performance looks low.

Rating

6

Confidence

4

Soundness

3

Presentation

4

Contribution

3

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,

Response to Author Rebuttal

I thank the authors for their detailed rebuttal. Here are comments from my end: - W1: scalability. I agree that using transformers with linear complexity can address the scalability challenge to a certain extent. Some larger datasets with million of nodes such as those seen in OGB[1] and TGB[2] might still prove to be a problem. Nonetheless, my concern here is mostly addressed. - W2: addressed. - Q1: I understand the limitation on time and proper evaluation of ranking links require significant computational time. Despite many prior work treating temporal link prediction as binary classification due to low computational cost for this evaluation, it is not a realistic measure for practical applications. In any recommendation systems, there is no guarantee of having half positive links and half negative links (as assumed in binary classification), I hope the authors can include ranking results in future versions of the paper. Overall, I decide to retain my current score. [1] Hu W, Fey M, Zitnik M, Dong Y, Ren H, Liu B, Catasta M, Leskovec J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems. 2020;33:22118-33. [2] Huang S, Poursafaei F, Danovitch J, Fey M, Hu W, Rossi E, Leskovec J, Bronstein M, Rabusseau G, Rabbany R. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems. 2024 Feb 13;36.