State Space Models on Temporal Graphs: A First-Principles Study

We appreciate your valuable and insightful comments, and we provide our responses below.

W1: heterophilic graphs issues

Thank you for your question. We agree with you that equation (3) reflects a prior belief that the node representation generated by GHiPPO should be homophilic under the representation level [3] at any time point. While being empirically effective, it poses significant challenge when the underlying temporal graph has more complex characteristics, and we will discuss it in revisions of our paper. Indeed, we do think that defining a proper homophily metric when the underlying graph is treated as a process is itself a valuable future research question.

W2: Typos or misunderstandings in Line 67, Lines 74-77, Line 105, Lines 180-181, and Line 339

We appreciate the reviewer for pointing out the careless errors. In the revision, we will make thorough proofreading to enhance readability by correcting any typos and improving the writing.

W3: Table 1 may not be entirely accurate

Thank you for bringing this to our attention. We agree that Table 1 may not be entirely accurate in all cases. In this context, "Transformers" refers to traditional "softmax Transformers." We will include a note to clarify this and prevent any potential misunderstandings. We will also provide a comprehensive discussion on this matter, as outlined below:

Indeed, there are close relationships between transformers with finite kernel feature maps (which are essentially what efficient transformers rely on), RNNs and SSMs [1, 2]. All of the three allow a recurrent parameterization and constant-memory-linear-compute inference. The primary difference is the update rule during recurrence: Linear transformers essentially use a unitary state matrix that is not learnable, while standard RNNs use learnable but not well-controlled state matrix. SSMs use an improved and learnable state matrix by adopting more careful initializations.

W4: On semantics of node memory

We will add a more accessible and detailed introduction to the background on HiPPO abstraction in revisions of our paper. Specifically, by an $N$-dimensional node memory at time $t$ we mean the coefficients of some order-$N$ polynomial (under the orthogonal polynomial basis) that optimally approximate the node features (viewed as a function over time) up until time $t$. The rationale of this representation is that a finite dimensional function space spaned by polynomials are characterized by their coefficients, thereby allowing us to embed functions into finite dimensional vectors. Now we answer your question: The inputs to the approximation polynomial is time $t$. The coefficients $u(t)$ of the polynomial is determined by an optimal approximation criteria, and constitues the node memory at time $t$.

W5: Performance of GraphSSM-S5

Thank you for your suggestion. We will address it and provide clarification in the revisions.

W6: Ablation study on swapping SSMs with RNN and Transformer

Thak you for your insightful suggestion. We replaced the SSM architecture with RNN and Transformer and present the results below. As observed, SSMs prove to be a superior choice compared to RNNs and Transformers. While Transformers excel in NLP tasks, they are not well-suited for discrete graph sequences.

Q1: Link prediction results

Thank you for your suggestion. The results for the link prediction task are presented below. We follow the experimental settings of ROLAND, where the model leverages information accumulated up to time t to predict edges in snapshot t + 1.

[1] Transformers are rnns: Fast autoregressive transformers with linear attention. ICML, 2020.
[2] Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. arXiv 2024.
[3] Luan, Sitao, et al. "Is heterophily a real nightmare for graph neural networks to do node classification?." arXiv preprint arXiv:2109.05641 (2021).

We hope our responses were helpful in adequately addressing your earlier concerns. In case you have any further questions or comments, please let us know, and we will gladly respond.

Thank you for your response and for raising the score. We are pleased to address the concerns you have raised.

W1: Missing comparison of related works [1,2] and advanced methods

Thank you for your suggestions. We have throughly reviewed the literature in temporal graph learning and have awared of several advanced works such as [3] and [4]. However, to our best knowledge, they are focusing on the continuous-time tempora graph leanring research and it is unfair to consider them as baselines for comparison under the discrete-time settings. We have explicitly clarified the situation in Related Work, and we will add a brief discussion with GraphSSM and continus-time methods in the next revision.

W2: Performance improvement is marginal

First of all, we respectively disagree with that the performance improvement is marginal. GraphSSM consistently achieves state-of-the-art performance and outperforms the runner-up baselines by significant margins, especially on the Reddit dataset. Secondly, scientific research is not a race; it is essential to place strong emphasis on other aspects of a method besides a single performance metric. GraphSSM shows superior performance while also exhibiting lower memory and computational overheads compared to other methods. This is also an important contribution of our work.

W3: Link prediction results

Thank you for your suggestion. The results for the link prediction task are presented below. We follow the experimental settings of ROLAND, where the model leverages information accumulated up to time t to predict edges in snapshot t + 1.

Q1: On remark 1 and degenerate solutions

Thank you for pointing out the degenerate solution and we shall restate the remark in future revisions of our paper. Technically, the minimizers of Laplacian quadratic forms shall satisfy a smoothness condition over connected components of the underlying graph (please refer to our discussion in appendix B.1). It is correct that zero is a trivial solution that satisfies the smoothness requirement yet contains no useful information. Therefore the optimal solution is only non-trivial when the objective is a combination of $\ell_2$ approximation and Laplacian regularization. Under such scenarios, the node features might be noisy themselves, and the Laplacian regularizer serves as a way to use neighborhood features as a (dynamic) denoiser.

Q2: What are nice properties of GHiPPO solutions? The GHiPPO solutions are desirable in the following aspects:

• It allows a linear dynmaical system (LDS) representation under specific choice of approximation configurations, which is a nice property of HiPPO framework that is inherited by GHiPPO. Without a reasonable ODE representation, the approximation framework would have been only technically of interest but impractical.
• ODE representations allow a constant memory update rule via utilizing a suitably defined discretization procedure. This ensures that the inference time memory and computational complexity is well-controlled.
• GHiPPO also inherits the versatility of HiPPO in that the LegS configuration is not the only one that allows ODE parameterization. Indeed we may use alternative approximation schemes such as fourier approximation and the resulting framework is still efficiently computable and practical.

Q3: The semantics of discretization

This is a very good question, and we think this is an important algorithmic challenge raised by the GHiPPO abstraction. In our framework, we view the underlying temporal graph as a collection of node feature processes together with a dynamically-changing topological relation among them. Under this framework, we regard graph snapshots as discrete observations of this underlying graph process. The objective of discretization is thus to develop a node state update rule that respects the graph dynamics, which is the central topic we discussed in section 3.2 of our paper. In particular, the existence of dynamic topological relations brings significant challenges to the discretization scheme (note that without topological relations, we can directly apply the ZOH discretization rule in a node-wise fashion) due to unobserved mutations of the underlying temporal graph which is conceptually depicted in equation (7) and figure 2 in our paper. Therefore, to study what should be a good discretization in this case, we first establish a dicretization rule in hindsight (the oracle discretization in theorem 2) and propose approximations to the oracle discretization thereafter.

[3] DyGFormer: Towards Better Dynamic Graph Learning: New Architecture and Unified Library, NeurIPS 2023

[4] SimpleDyG: On the Feasibility of Simple Transformer for Dynamic Graph Modeling, WWW 2024

Thank you again for taking the time to review our paper. We hope our responses could clarify your concerns, and hope you will consider increasing your score. If we have left any notable points of concern unaddressed, please do share and we will attend to these points.

The comparison CTDG baselines include memory-based methods TGN and TIGER (as you mentioned in the initial review), as well as attention-based methods TGAT and DyGFormer. Results for the node classification tasks are presented below:

Due to time and space limitation, we are currently presenting the experimental results of the node classification task on the four datasets. Further experiments are being conducted and can be presented in a few days if it is necessary. As observed, CTDG methods demonstrate relatively poor performance on the four datasets, which is inline with our above claims. Indeed, many CTDG methods require fine-grained time information to capture the evolution patterns between edges, which is impractical for DTDGs with coarsened snapshot information.

Response to Q2: Firstly, we acknowledge that the learning setting in ROLAND differs from that of other works [1, 2]. The main differences arise from diverse contexts of dynamic graphs, as detailed below:

• ROLAND focus on the discrete-time dynamic graphs (DTDG), which is also the main focus of our work. In this setting, our goal is to predict edges in snapshot 𝑡 + 1 based on the snapshots accumulated up to time 𝑡. This is the general setting in discrete-time temporal graphs and is widely used in literature including several representative works, e.g., EvolveGCN[4].
• For TGB[1] and DGB[2], both benchmarks focus on the continuous-time dynamic graphs (CTDG), whose goal is to predict the occurenc of a link between two given nodes at a specific time point.
• While we agree that "Continuous vs. discrete are often modeling choices most of the time", there are differences in terms of the associated time information in the graphs for modeling. In the context of CTDG, link prediction is fine-grained, with each link being associated with an exact timestamp. This allows for predicting evolving edge streams at specific time points. However, in DTDG, link prediction is coarse-grained. Each edge in a snapshot has relative time information, and we can only predict whether a link will occur in the next time span, such as in the next week or month. In this regard, we were unable to perform link prediction under the setting of [1,2].

Secondly, while ROLAND studied and proposed a framework that is related to continual/incremental learning, the experimental setup for the link prediction task exactly follows the classic DTDG settings in previous works[4,5,6,7]. This is detailed in the ROLAND paper ("Task" section in Section 4.1).

Finally, to avoid any potential confusion, we detail our experimental setting for the link prediction task:

• Train-val-test splits: For each dataset, we use $G_1, G_2, · · · , G_{T −1}$ as the training data, $G_{T}$ as test graph. Also, we use $G_{T-1}$ as the validation graph during training for hyperparameter tuning. Each model leverages the T-1 visible graphs to prediction the occurence of edges in $G_T$.
• Positive and negative edges: For the link prediction problem, the positive test set consists of the edges that appear in $G_T$ and do not present in $G\_{T-1}$, while the negative test set consists of the edges that do not appear in $G\_{T-1}$ and $G_T$.
• Evaluation metrics: AUC and AP, two standard metrics in link prediction tasks.

If any concern still remains that might prohibit a positive recommendation of this work, we would appreciate if you could let us know.

Reference

[3] Kazemi, Seyed Mehran, et al. "Representation learning for dynamic graphs: A survey." Journal of Machine Learning Research 21.70 (2020): 1-73.

[4] Pareja, Aldo, et al. "Evolvegcn: Evolving graph convolutional networks for dynamic graphs." Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.

[5] You, Jiaxuan, Tianyu Du, and Jure Leskovec. "ROLAND: graph learning framework for dynamic graphs." Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. 2022.

[6] Zhang, Kaike, et al. "Dyted: Disentangled representation learning for discrete-time dynamic graph." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.

[7] Sankar, Aravind, et al. "Dysat: Deep neural representation learning on dynamic graphs via self-attention networks." Proceedings of the 13th international conference on web search and data mining. 2020.

Thanks for acknowledging our efforts in the rebuttal. We greatly appreciate your prompt response during the rebuttal period. We will now address your additional concerns and questions below.

Response to Q1: Thank you for the question regarding TGNNs. In our initial rebuttal, due to limited characters we only tried to answer your question in a somewhat conventional way by pointing out modeling on discrete-time dynamic graphs (DTDG) and continuous-time dynamic graphs (CTDG) are usually considered as different tasks[3]. We agree with you that there are more profound connections between the modeling of DTDG, CTDG and the GHiPPO abstraction we proposed. Our perspectives are three-fold:

• (i) We will show that DTDG and CTDG are two different lossy observation schemes of the underlying graph process in the GHiPPO abstraction.
• (ii) We discuss why the current SSM framework based on discretizations are not yet readily suitable for handling CTDGs.
• (iii) We return to CTDG models as you have mentioned, and present some empirical results suggesting that they might indeed be not an ideal solution to DTDG problems.

(i) DTDG, CTDG and GHiPPO

Recall that in our formulation of the underlying graph process, the node features evolve continuously and the topological relations among nodes allow finite (countable) mutations. Let's rewrite the process in equation (2) of the paper: $G(0) \overset{\mathcal{E}_1}{\longrightarrow} G(t_1) \overset{\mathcal{E}_2}{\longrightarrow} G(t_2) \longrightarrow \cdots \longrightarrow G(t\_{M-1}) \overset{\mathcal{E}_M}{\longrightarrow} G(t_M) = G(T).$

Now we take a closer look at DTDG and CTDG representations of the above process:

• DTDG: In DTDG representations, we do not directly observe the events, but we observe the entire graph at certain time spots resulting in a serious of snapshots. In this spirit, DTDG has complete latitudinal information, but is lossy regarding longitudinal information.
• CTDG: In CTDG representations, we have complete observations of events, but upon each event information, we do not observe the features of the rest of the nodes (that do not participate in those specific events). Therefore, CTDG has complete longitudinal information, but is lossy regarding latitudinal information.

Next we proceed to why we choose to only study the former one (DTDG).

(ii) Handing CTDGs using SSM discretizations is challenging

In section 3.2 of our paper (especially theorem 2), we established the discretization scheme upon an ideal, discrete observation. (We observe the graph snapshot at each mutation events) We believe that this one reasonably hints tha gap between possible empirical approximations in either DTDG or CTDG scenarios. In DTDGs, we believe approximations using available snapshots are possible since from hindsight, the ideal representation is a convex combination of the snapshot representations at the mutation times. The approximation bias mostly comes from fewer snapshots, and we use mixing strategies to mitigate the biases.

However, in CTDG scenarios, we miss the majority of information in each snapshot. Up till now we have not yet figured out any practical and sound solutions to this issue. Besides, consturcting snapshots from CTDGs is itself a very impractical method. It is possible that the GHiPPO abstraction might not be a very good fit for a principled study of CTDGs (might be too stringent, in our opinion). Hence, we regard the modeling of CTDG to be beyond the scope of GraphSSM.

(iii) CTDG models and their performance on DTDG graphs

As you have pointed out, many CTDG models are based on a Message Passing combined with Recurrent State Update (MPRSU) scheme, which is closely related to GraphSSM (and indeed, related to many other DTDG methods like ROLAND as well). Recall that, SSMs are also a special case of linear RNNs from the computational viewpoint. However, SSMs utilize a finer-grained definition of memory (via deriving them from an online approximation problem) that yields more stable and performant RNN variants as compared to GRU or LSTM. This is indeed what we tried to establish in our paper---We equip the node-wise memory in a principled way that is formalized as the optimal approximation coefficients of the Laplacian-regularized online approximation problem. We have shown that this formulation leads to better DTDG modeling frameworks, and in our ablation study we also show the efficacy of using SSM schemes rather than ordinary RNNs or even softmax transformers. So far as we have noticed, most TGNN methods have no mechanistic interpretations of their memory mechanisms. Besides, as we have discussed earlier, it is unclear if SSM schemes are readily applicable to CTDG frameworks.

Finally, we have gained some additional empirical insights from additional experiments. We conducted evaluations of CTDG methods on the DBLP-3, Brain, Reddit, and DBLP-10 datasets.

We appreciate your positive reviews. Your concerns are addressed as follows:

W1 & Q1: Parameter size of GraphSSM and baseline models

Thank you for your insightful suggestion. Per your suggestion, we have now included the comparison of parameter sizes between GraphSSM models and baselines on a large dataset arXiv.

As observed from the table, GraphSSM, particularly GraphSSM-S5, shows superior parameter efficiency compared to other methods. This is attributed to the advantages offered by SSM models.

W2 & Q2: Comparison of transformer-based methods.

In this work, we focus on discrete-time temporal graphs, which typically have long sequence lengths and are not suitable scenarios for transformers. Current works on transformer-based temporal graph learning mainly focus on continuous-time temporal graphs, leaving a significant gap for discrete-time temporal graphs. In this regard, we did not and cannot include transformer-based baselines in our experiments. And it is unfair to directly apply continuous-time methods to our specific settings for comparison. Therefore, we conduct an ablation study on GraphSSM by substituting the SSM architecture with Transformer and present the results below.

As observed, GraphSSM-Transformer does not exhibit significantly superior performance in learning from discrete graph sequences compared to SSM-based architectures, despite introducing more memory and computation overheads.

Q3: Time complexity of the GraphSSM

GraphSSM is a discrete-time sequence model that performs a message passing step for each graph snapshot, followed by an SSM model for sequence learning. Assuming we have $L$ GNN layers and the sequence length is $T$, the full-batch training and inference time complexity for each graph snapshot with $L$ layers can be bounded by $\mathcal{O}(L|\mathcal{E}|d)$, which represents the total cost of sparse-dense matrix multiplication or message passing. We assume a hidden dimension of $d$ across all layers for simplicity.

The main bottleneck of GraphSSM is the graph message passing step, which can be further optimized using techniques such as graph sampling[1] or graph condensation[2].

[1] GraphSAINT: Graph Sampling Based Inductive Learning Method. ICLR 2020.

[2] Graph Condensation for Graph Neural Networks. ICLR 2022.

We would be grateful if you tell us whether the response answers your questipns of GraphSSM, if not, what we are lacking, so we can provide better clarification. Thank you for your time.

Thank you for your response. We greatly appreciate your thoughtful feedback and the time you dedicated to reviewing our paper!