Over the past few years, research on deep graph learning has shifted from static graphs to temporal graphs in response to real-world complex systems that exhibit dynamic behaviors. In practice, temporal graphs are formalized as an ordered sequence of static graph snapshots observed at discrete time points. Sequence models such as RNNs or Transformers have long been the predominant backbone networks for modeling such temporal graphs. Yet, despite the promising results, RNNs struggle with long-range dependencies, while transformers are burdened by quadratic computational complexity. Recently, state space models (SSMs), which are framed as discretized representations of an underlying continuous-time linear dynamical system, have garnered substantial attention and achieved breakthrough advancements in independent sequence modeling. In this work, we undertake a principled investigation that extends SSM theory to temporal graphs by integrating structural information into the online approximation objective via the adoption of a Laplacian regularization term. The emergent continuous-time system introduces novel algorithmic challenges, thereby necessitating our development of GraphSSM, a graph state space model for modeling the dynamics of temporal graphs. Extensive experimental results demonstrate the effectiveness of our GraphSSM framework across various temporal graph benchmarks.
Paper
Similar papers
Peer review
Summary
The paper proposes an approach for processing discrete-time temporal graphs via an extension of state-space models (SSMs). In this direction, the main contribution of the paper is a generalization of the HIPPO framework for graph structured data (named GHIPPO), which defines how the state of different nodes should be updated through time to compress the evolution of nodes features (a solution capable of dealing with multiple changes that might happen between two snapshots is additionally introduced in the paper). In experimental evaluation, an SSM-based solution implemented with the proposed GHIPPO framework (named GraphSSM) outperforms a variety of approaches on both the moderately sized DBLP-3, Brain, Reddit and DBLP-10 datasets, and the large-scale arXiv and Tmall datasets.
Strengths
While I’m personally not an expert in SSM models, I generally found the paper to be an interesting read (to the best of my knowledge there is not much work on applications of SSMs to graph-structured data, and as such the work highlights a research direction possibly worthy of further exploration). The presentation of the paper is generally understandable (albeit not always clear in some spots, see weaknesses), and allows a reader unfamiliar with the SSM literature to grasp the overall idea of the paper. The experimental evaluation of the paper appears well done (with the proposed approach outperforming prior art on a variety of different datasets), although there might be room for improvement.
Weaknesses
Generally I do not have many weaknesses to highlight in the paper. From a technical perspective, I would want to highlight that: 1) the proposed approach might face some issues with heterophilic graphs (as the smoothness in the node state imposed in equation (3) is not necessarily a good regularizer in that setting - see point 5 below) 2) the proposed methodology is limited to discrete-time temporal graphs, and further work would need to be done to extend the model to a continuous-time setting (this is also highlighted by the authors themselves in the paper). From a different perspective, a weakness of the paper is probably its exposition, which in some parts is a little confusing and could be improved. In this direction: 1) lines 67, I believe there is a typo and the authors should replace “features the dynamics” with “the features dynamics” 2) line 74 to 77 are quite unclear and should probably be refactored 3) line 105, “recurrence model” should probably be replaced with “recurrent model” 4) Table 1, while it is true that classic transformers have a quadratic space and time complexity, there are also efficient transformers (e.g. Performs) that show linear space and time complexity. I believe these are not mentioned in the paper and probably they should, in order to provide to the reader a complete picture of where we stand with transformer architectures. 5) I believe the smoothness in node state imposed in equation 3 with the dirichlet energy regularizer makes sense only on homophilic graphs, and might not be a meaningful prior to use when dealing with heterophily. This is not pointed out in the paper and probably it should be highlighted as a possible limitation. 6) Lines 180-181, the authors mention that what minimizes equation 3 is a piecewise vector. I believe what they mean is that the solution is piecewise over time, I think this should probably be clarified in the paper as it might be a source of confusion 7) line 184-185, how the nodes' memories are parameterized as polynomials is very unclear here. How are those polynomials defined? What is the input to such polynomials? It might be that a reader familiar with the HIPPO framework would be aware of such details, but the lack of an explanation in the text makes it hard to draw a complete picture here. 8) lines 335-336, GraphSSM with S5 doesn’t always achieve poor performance (it is indeed the best performing model on DBLP-3 in table 4). This should be clarified in the text. 9) line 339, I believe there is a typo and the “and” at the beginning of the sentence should be fixed.
Questions
One thing that I think would be helpful to improve the strength of the paper is to run some experiments where the proposed SSM module is swapped with a RNN or transformer architecture. As we can see from the ablation study of table 5, it appears that the mixing strategy one might decide to use is relevant to outperform prior art. As a result of this, I wonder what would be the performance that a comparable solution would have with the very same architecture used by the authors but without using any SSM approach. This will clearly provide an indication on whether using SSMs is beneficial for achieving the desired performance (which is the main claim of the paper) or whether the results we see in Table 2 and 3 are only due to the mixing strategy.
Rating
6
Confidence
3
Soundness
2
Presentation
2
Contribution
2
Limitations
Yes
Thank you for your response and for raising the score. We are pleased to address the concerns you have raised.
Summary
The paper introduces GRAPHSSM, a novel state space model framework for temporal graphs. GRAPHSSM extends state space models (SSMs) by incorporating structural information through Laplacian regularization to handle the dynamic behaviors of temporal graphs. The framework aims to overcome limitations of recurrent neural networks (RNNs) and Transformers in modeling long-range dependencies and managing computational complexity. The authors propose the GHIPPO abstraction for memory compression and various mixing mechanisms to handle unobserved graph mutations. Extensive experiments on multiple temporal graph benchmarks demonstrate the effectiveness and efficiency of GRAPHSSM.
Strengths
- The paper is well-written and I enjoy reading the paper. The derivation of the method and the extension from SSM is technically sound - The the overall research direction is well-motivated and interesting. SSM is indeed a good potential candidate for modelling temporal graph.
Weaknesses
- There already exists an important family of temporal graph neural networks (TGNNs) that use memory mechanism (see [1] and [2] for examples) and resemble a state transition model. The paper seems to neglect/be unaware of this line of related work. - There are parts of the method/extension that are not clear (see questions below for more details) - There are a couple of serious limitations regarding the empirical study: 1) the baselines for the paper are rather outdated. The paper did not compare with the more recent TGNN models (e.g. above-mentioned memory-based temporal graph neural network, which is the SOTA for TGNN) 2) the performance improvement from the proposed baselines is still marginal 3) the conical task for temporal graph neural should be link prediction which is missing from the current study [1] Rossi, Emanuele, et al. "Temporal graph networks for deep learning on dynamic graphs." arXiv preprint arXiv:2006.10637 (2020). [2] Zhang, Yao, et al. "Tiger: Temporal interaction graph embedding with restarts." Proceedings of the ACM Web Conference 2023. 2023.
Questions
- Q1: I fail to understand the second part of Eq.(3). Why does minimizing the second term of Eq.(3) amounts to increasing smoothness? In addition, I don't think the interpretation/remark given in line 179-180 are correct. If $\alpha$ goes to infinity, the whole objective, Eq.(3), is dominated by the second term. There is a degenerate solution $Z(s) = \mathbf{0}$ (zero vector) that would minimize the objective. Which part of the objective/model prevent this degenerate solution? - Q2: Theorem 1 is saying that GHIPPO is "nice" because its parameter update can be described by the given ODEs. Can you further explain why this property is nice? does the benefit comes from better efficiency or inference performance? and how? - Q3: the discretization in the HIPPO paper was for computation purposes. In the case of temporal graph, where event and snapshot are inherently discrete. What is the (optimization) objective for discretization? i.e., what should be considered as a "good discretization" in this case?
Rating
5
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
N.A
Response to Reviewer PUCW (Part 1/2)
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.
Response to Reviewer PUCW (Part 2/2)
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: ||**DBLP-3**||**Brain**||**Reddit**||**DBLP-10**|| |---------|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:| ||Micro-F1|Macro-F1|Micro-F1|Macro-F1|Micro-F1|Macro-F1|Micro-F1|Macro-F1| |TGN|80.43|80.08|89.50|89.59|40.66|40.50|70.01|68.83| |TIGER|81.53|81.74|90.49|90.33|41.17|40.98|72.48|71.14| |TGAT|82.59|82.14|90.98|90.25|42.79|42.40|73.15|72.02| |DyGFormer|84.77|84.51|92.01|91.32|45.24|44.51|72.40|71.86| |GraphSSM|**86.29±1.0**|**85.78±0.9**|**93.80±0.3**|**94.47±0.6**|**49.21±0.5**|**49.05±0.7**|**76.80±0.3**|**76.00±0.4**| 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.
Summary
This paper investigates SSM theory to temporal graphs by integrating structural information into the online approximation with laplacian regularization term.
Strengths
1. The proposed method has the theoretical support to show the effectiveness of the proposed method. 2. The experimental results show that the proposed method outperform most of the baseline methds. 3. This paper is well-motivated.
Weaknesses
1. Since one advantage of the SSM based methods is its small parameter size, then what's the size of the model compared with other baseline methods? It's better to list the number of parameters to show the efficiency of the proposed method. 2. The transformer based methods have better performance as shown in Table 1, do you include any transformer-based methods for the experimental comparison?
Questions
1. Since one advantage of the SSM based methods is its small parameter size, then what's the size of the model compared with other baseline methods? 2. The transformer based methods have better performance as shown in Table 1, do you include any transformer-based methods for the experimental comparison? 3. What is the time complexity of the GraphSSM?
Rating
6
Confidence
2
Soundness
3
Presentation
3
Contribution
3
Limitations
The authors provide the limitation in appendix E.
Thank you for your response. We greatly appreciate your thoughtful feedback and the time you dedicated to reviewing our paper!
I would like to thank the authors for their response. I don't have further question and I'm happy to raise my score to a 6
I would like first to thank the authors for their diligent response. However, I still found my main concerns not fully addressed after reading the response. 1. I don't think "they focus on modelling continuous graph" is a sufficient reason for not comparing them with the proposed method. Continuous VS discrete are often modelling choices most of the time, and memory-based TGNN have been applied to the dataset used in the paper [1,2]. I also think the modelling choice of this paper is also assuming the underlying process is continuous? The most appealing reason why I think a detailed comparison is necessary between memory-based TGNN and the proposed method is their memory mechanism. Memory-based TGNN captures dynamic/temporal information of the graph by incrementally processing information and distilling it into a so-called memory vector, which in a sense can be viewed as the state of the graph/node. Therefore, I think the mechanisms between memory-based TGNN and the method proposed are very similar. I am very keen to understand the fundamental difference and why we need this potentially new family of models for dynamic graphs. 2. I am very confused with the choice of experimental setting for the link prediction task. Based on my understanding, ROLAND actually focused on the efficiency of TGNN and studied a learning setting that is different from the typical ones (e.g., [1,2]). They studied and proposed a framework that is related to continual/incremental learning. [1] Huang, Shenyang, et al. "Temporal graph benchmark for machine learning on temporal graphs." Advances in Neural Information Processing Systems 36 (2024). [2] Poursafaei, Farimah, et al. "Towards better evaluation for dynamic link prediction." Advances in Neural Information Processing Systems 35 (2022): 3
Gentle Reminder
Dear Reviewer PUCW, We sincerely appreciate your insightful review and feedback comments. As the author-reviewer discussion deadline (Aug 13) is approaching, we would like to check if you have any other remaining concerns about our paper. **We have faithfully responded to ALL your comments. If our responses have adequately addressed your concerns, we kindly hope that you can consider increasing the score.** We understand that you have a demanding schedule, and we appreciate the time and effort you dedicate to reviewing our paper. Kind regards, Authors
Thank you for the diligent response. I have raise my score accordingly.
Thank you for raising the score
We are very happy to hear that you have raised the score. Your recognition of our efforts in the paper is greatly appreciated! We thank you again for the invaluable feedback and insights.
Reply to authors' rebuttal
I would like to thank the authors for the detailed response. I don't have further question.
Decision
Accept (poster)