Towards an Understanding of Graph Sequence Models

Thank you so much for your time and constructive review. We really appreciate it. Please see below for our response to your comments:

W1: However, counting task does not seem to be sufficient to represent "naturally sequential tasks".

Response: Thank you for mentioning that. Here, by naturally sequential tasks, we meant tasks that do not require graph inductive bias. We agree that this term has been confusing, and following your suggestion, we have modified the writing and changed this term. We hope this has addressed your concern.

W1: Line 215 "Can causality resolve this issue?". This question is raised by the authors but there is no any follow-up.

Response: We want to kindly bring to your consideration that this question is followed by Theorem 1, which has answered this question. In fact, causal-transformers are similar to recurrent models and due to their causal nature can count the number of nodes with each specific color iff $m \geq C$, where m is the width and $C$ is the number of colors. To avoid any confusion and to further clarify the statements, we have revised this part in the revised version.

W1: The statement is based on causal transformers have no representational collapse, which is not argued in the context.

Response: Thank you for bringing this to our attention. Please note that non-causal transformers (traditional transformers) are permutation invariance and so the order of tokens cannot affect the final output after $L$ layers. Accordingly, they do not suffer from the representational collapse issue. Following your suggestion, we have added this argument in the revised version to further clarify this conclusion.

W1: Given that the transformer has constant sensitivity w.r.t. distances, I wonder why the dependency will still concentrate on the start of the sequence?

Response: Please note that these results correspond to different variants of Transformers. That is, non-causal transformers (traditional transformers) are permutation invariant and also have constant sensitivity issue. On the other hand, causal transformers (i.e., decoder-only or causal masked transformers) have the issue of representational collapse and will concentrate on the start of the sequence. Following your suggestion and to avoid any misinterpretation, we discuss this in the revised version in lines 258-274. This is one of the main motivations for presenting a hybrid model (causal SSM + non-causal transformer). That is. non-causal transformers do not have representational collapse and so combining them with causal SSMs is the best of both worlds, resulting in a model with linear sensitivity while avoiding representational collapse.

W2: what are the performance metrics shown in Table 1 and 2?

Response: Thank you for bringing this to our attention. Following previous studies (e.g., Sanford et al., NeurIPS 2024), the performance metric for node degree, cycle check, connectivity, and color counting is accuracy (all are balanced datasets), and the metric for triangle counting and shortest path is MSE. We have added all the performance metrics to the tables in the revised version. We hope this change has addressed the reviewer’s comment.

W2: what is specifically "MPNN" in Table 1?

Response: We thank the reviewer for bringing this to our attention. The MPNN module is the original Neural message passing model that comes from Gilmer et al. (ICML 2017). Accordingly, to further clarify and to address the reviewer’s concern, in the revised version, we have included this information.

W3: from ablation study Table 4, it seems the proposed HAC tokenization have very marginal improvement, while the main improvement comes from the simple hybrid of different models and tokenizations.

Response: Thank you very much for bringing this to our attention. We realize that in these ablation studies, we were using HAC-based hierarchical positional encoding, which results in taking advantage of the HAC and not fully removing it from the model. We have updated the results and also report the results for more challenging datasets, which can further show the significance of the presented modules. The results show that removing HAC can result in 1.5% performance drop on average. Also, please note that using hybrid models and mixture of tokenization are contributions of this study and to the best of our knowledge, no other studies have explored their effectiveness in graph learning tasks.

W1: empirical performance is not that excellent compared to recent baselines, e.g., Grit, Graph-Mamba (two concurrent works), GSSC, etc.

Response: We kindly bring to your consideration that GSM++ has provided 0.85 performance improvements on average over the best of these baselines. Please note that this is a larger improvement than what Graph-Mamba and GRIT have gained over their own baselines, which shows the significance of our contribution. Please note that when the best performance approaches near-perfect scores for a benchmark datasets, designing an architecture that results in a better performance becomes extremely more challenging. However, despite these challenges, GSM++’s design has resulted in a performance gain that is higher than the performance gain of earlier studies.

W2: But still, many results in Sec. 3 are not that original

Response: We kindly refer the reviewer to our previous reply. This paper has provided 10 distinct and new theorems with 5 corollaries, which to the best of our knowledge, result in one of the most extensive theoretical analyses of recent studies in top tier conferences. All these results are original and only 2 corollaries and 1 proposition are from previous studies. Moreover, many theoretical results presented in this paper are specifically tailored to graph learning tasks. This comprehensive theoretical exploration emphasizes the depth and novelty of our contributions.

W2: I still find it hard to compare recurrent models and transformers … limits itself to cases without properly using PE

Response: Please note that theoretical analysis of graph sequence models have been extremely challenging and somewhat insightless. The reason is existing studies have tried to evaluate their expressive power using the WL test, which is widely used by other types of graph neural networks. Graph sequence models, however, with proper positional encoding are more powerful than any k-WL test, which made the comparison of their expressive power with respect to this test impossible. To mitigate this, and to provide further insight about the ability of sequence models, in this paper, in addition to general purpose theorems, we also aim to answer what type of sequence models has more inductive bias and is more suitable for the task at hand. We want to kindly bring to your consideration that the assumption of without proper PE is only taken for Proposition 1 and Theorem 1. Even without these two results, the paper has provided 9 theorems with 5 corollaries, which all can provide insight about which sequence model is useful.

Please note that our theorems cover different possible cases, providing insights for different setups. That is, Theorem 1 and Proposition 1 consider sequence models without specific tokenization (i.e., node tokenization) and positional encoding. Theorems 3, 4, and 5 consider sequence models without tokenization but with any arbitrary positional encoding, and finally Theorems 6 and 7 consider the complete setup. These theorems are complementary and all together provide new insights about the power of sequence models for graph tasks.

W2: It seems hard to conclude that recurrent models could be more efficient on connectivity tasks in practice … may not really show a significant difference in practical cases.

Response: Please note that if we fix the node locality to a reasonable number of 12 and the number of edges to 1M, then these results indicate that a recurrent model with hidden state size of 12 can solve this task, while a transformer requires at least 1M parameters. We believe in practice (on a reasonable graph with 1M edges), the difference of 12 and 1M is indeed a significant difference.

In addition to the above, we want to kindly bring to your consideration that the same argument can be said about the WL test, which is widely used in the literature, or most theoretical results. That is, one might argue that representation learning on most graphs does not require even 1 or 2- WL test as in practice graphs are not that challenging and similar to each other. However, theoretical results often present as the motivation/justification of empirical results and to support them. That is, theoretical results are mathematical facts about the power of architectures in the general (or worst) case, while empirical results are instances of performance on a subset of potential datasets. So theoretical results guarantee a good performance when in the future larger/complicated/challenging graphs come. Accordingly, we believe all the presented theoretical results can be valuable and result in better understanding of the graph sequence models.

Thank you so much for your time and constructive review. We really appreciate it. Please see below for our response to your comments:

W1: I'm a bit confused about the positioning of this paper

Response: Thank you for raising this point. Recently, there have been huge interests in designing efficient alternative architectures for transformers and accordingly, they all can be applied to graph data when we tokenize the graph. This results in a huge number of models based on different combinations of sequence models and tokenization methods (as well as their combination with local and global encoding). Although this can provide an interesting set of models with potentially good performance, it can also cause confusion about what constitutes a good sequence model for graphs and how one can compare these combinations. To address this, we provide extensive theoretical results and motivated by these results, we present a new architecture GSM++, that uses a hybrid sequence model with a novel tokenization process based on the HAC algorithm. We believe these contributions help position the paper not only as a source of theoretical guidance but also as a proposal for a new architecture that leverages these insights for practical performance improvement.

W1: which organizes some previous results and also provides a few new results … if we were to see the technical results of this paper, then they seem a bit limited

Response: We would like to draw your attention to the depth and breadth of the theoretical results presented in this work. Specifically, we have 10 distinct theorems, 7 corollaries, and 1 proposition, from which 2 corollaries and 1 propositions are cited from prior work. This leaves this paper with 10 distinct and new theorems and 5 corollaries, which to the best of our knowledge result in one of the most extensive theoretical analyses of recent studies in top tier conferences. The theoretical results span topics such as graph connectivity, k-locality, motif counting, color counting, and hierarchical tokenization, providing both novel insights and practical design guidelines. Furthermore, please note that these theorems are considerably non-trivial with about 3 + 8 pages of discussion and proofs. While a few theoretical results are revisited for completeness and to contextualize our contributions, the majority of results are new and directly inform the design of GSM++.

W1: the overall framework (tokenization + local + global) is not new

Response: We would like to clarify that to the best of our knowledge, none of the existing studies have explicitly presented this unifying framework. For example, graph mamba also discusses similar steps, but it lacks the global encoding step. Graph GPS also discusses a framework, but it lacks both tokenization and local steps, as it simply treats the graph as a sequence of nodes.

We, however, would be happy to discuss and consider any other model that has explicitly presented and formalized this framework. Also, we want to clarify that we do not claim the framework itself as a major contribution of this work, but we believe it is an important step and establish a clear structure that has allowed us to extensively evaluate (both theoretically and empirically) different sequence models and tokenizers. Please note that, as an example of extensive evaluation, Figure 3 alone is representing the results of 54 different (mostly new) models on 7 datasets!

W1: the usage of SSMs on graphs is not new

Response: Please note that we are not using SSMs alone for graphs. While standalone usage of state-space models (SSMs) in various tasks has been explored, tTo the best of our knowledge, this paper is the first study that presents a hybrid model (SSMs+attention) for graph structured data and shows its effectiveness.

In addition to this fact, we want to kindly bring to your consideration that before the recent interest in SSMs, graph transformers, based on self-attention, have been the only graph sequence models for several years, and several models based on graph transformers have been published in top-tier conferences due to their unique contributions in design or application. The novelty of a method comes from the combination of its proposed elements, as in our case is HAC + hybrid model + mixture of tokenization which is motivated by theoretical analysis. To the best of our knowledge, none of these elements has been discussed in the existing methods. Please see our general response about the significance of our contributions.

We hope this clarifies how GSM++ constitutes a significant and novel contribution to the field beyond a simple application of SSMs to graphs.

Q1: Why are the color counting problem important for graphs?

Response: Please note that there are four aspects to answer this question:

• (1) The color counting is a fundamental task that we expect any effective graph learning model should be able to handle. The reason for this is that counting is a seemingly simple, yet important, reasoning task that requires only keeping track of a single scalar for each color.
• (2) The task is structured and simple enough to be studied theoretically, while it is still hard enough for the model as counting tasks require aggregating information from all nodes and even missing a single node's color can potentially result in an incorrect prediction. Please note that theoretically analysis of a task is a highly non-trivial process and most theoretical studies (even in a broader context) focus on the tasks that can simply be modeled while they are still hard enough for ML models.
• (3) The color counting is related to important concepts in graph learning like color refinement and the Weisfeiler-Lehman (WL) test.
• (4) As mentioned by Barbero et al. (NeurIPS 2024), counting is a problem that requires some notion of ‘unboundedness’ of the representations, whilst the normalisations used inside a Transformer work against this. As discussed/motivated in our paper (lines 206 - 211), color counting can be considered as the graph counterpart to the popular copying task in sequence modeling, widely studied in language models (e.g., Mamba, Gu el al., 2023).

Also, please note that our study is not the first study to use color counting tasks. As we also have cited in the initial submission, several papers including (Barbero et al., NeurIPS 2024) also use graph counting tasks to theoretically analyze the power of the deep learning architectures. For example, Barbero et al., (NeurIPS 2024) use this task to understand the reasoning capability of Transformers. The simplicity for theoretical understanding, its connection to several fundamental concepts (e.g., color refinement, WL test, and copying task), and being a least expectation from models for reasoning on a scalar feature, all make color counting an important and suitable problem for theoretical analysis of graphs.

Q2: Why does non-causal transformers solve the representational collapse issue?

Response: Thank you for mentioning that. Please note that the position of a token in non-causal transformers (traditional transformers) cannot affect its encoding due to the fact that Transformers are permutation equivariance. Since the order of tokens cannot affect the final output after L layers, Transformers do not suffer from the representational collapse issue. Following your suggestion, we have made this point clearer in the revised paper.

Q3: This work appears incomplete in several respects. For example, although the authors introduce a variety of tasks, such as node- and graph-level tasks, and discuss relevant datasets in Table 6, they do not present corresponding results

Response: We respectfully disagree with the statement that the paper is incomplete. The results for both node-level and graph-level tasks were already included in the initial submission, specifically in: Tables 3 (page 10), 7 (page 30), and 8 (page 30). In the revised version, these tables can be found in Tables 3 (page 10), 8 (page 33), and 9 (page 33). In the main text, we also have referred to these results in line 524 (line 521 in revised version). As you also mentioned, the details for these experiments are also presented in Table 6.

Thank you so much for your time and constructive review. We really appreciate it. Please see below for our response to your comments:

W1: Most of the theoretical foundations in this paper are derived from prior work focused on sequence models, such as Transformers and RNNs. … The paper lacks theoretical adaptations specifically tailored to graphs

Response: We kindly bring to your attention that many theoretical results presented in this paper are indeed specifically tailored to graph learning tasks. For instance, graph connectivity (e.g., Theorem 3), its variant based on k-locality (e.g., Theorems 4 and 5), and motif counting (e.g., Theorem 7) directly address graph-specific tasks, and so are theoretical results about learning on graphs. To the best of our knowledge, none of these contributions are mentioned or used by other studies.

In total, the paper introduces 10 distinct theorems, 7 corollaries, and 1 proposition, of which only 2 corollaries and 1 proposition are derived from prior work. This comprehensive theoretical exploration emphasizes the depth and novelty of our contributions.

Furthermore, please note that some results, such as our Theorems 1 and 2, that are non-speciality tailored to graphs, are indeed strength of our results as they provide a general theorem for a general machine learning model when applied to arbitrary data form, resulting in a broader impact on diverse sub-communities. Moreover, these analyses lay the foundation to the understanding and logical flow of the paper and are important in the design of the final GSM architecture.

W1: Additionally, several theorems (e.g., Theorems 3, 5, 6, and 7) are presented without proof

Response: We kindly bring to your consideration that all the proofs for the mentioned theorems were already provided in the Appendix. Specifically: (1) Theorem 3: Proof presented on page 23, line 1220 (revised version: page 26, line 1365). (2) Theorem 5: Proof presented on page 25, line 1300 (revised version: page 27, line 1444). (3) Theorem 6: Proof presented on page 28, line 1469 (revised version: page 30, line 1611). (4) Theorem 7: Proof presented on page 27, line 1417 (revised version: page 29, line 1557).

Please note that for some theorems, since we have provided more extensive theoretical analysis in the appendix, we have discussed their proofs in separate sections. This has allowed us to clearly and cohesively discuss and motivate theoretical results. We have mentioned this after each theorem that where the reader can find additional details.

We hope this response addresses the Reviewer’s concern and highlights the rigorous theoretical foundation of our work.

W2: The logical flow of the paper is unclear. …

Response: Following Reviewer suggestion and to enhance the logical flow of the paper, we have revised the presentation and made sure to explain all the required steps for the derived conclusion. Specifically, we have updated the Takeaway summaries and discussed all the required steps. These Takeaway paragraphs at the end of subsections, distill the key results and insights, and clarifies how subsections connect to subsequent subsections and the overall narrative of the paper. We have further added a “Contributions and Roadmap” paragraph at the end of the Introduction that provides a clear outline of the paper’s structure.

We hope the current revised version has addressed the Reviewer’s concern. We, however, would be happy to clarify any additional concerns about any specific conclusion that is not clear.

Thank you so much for your time and constructive review. We really appreciate it. Please see below for our response to your comments:

W1: experimental details such as hyper-parameter are missing

Response: Thank you for bringing this to our attention. To improve the clarity of the paper, in the revised version, we have added a new table (Table 7 in the revised paper) and reports all the hyper-parameter configurations.

W2: The architectural design choices in GSM++ lack comprehensive ablation studies.

Response: Thank you for mentioning this interesting point. We want to kindly bring to your consideration that in the paper we have not claimed that the current order of hybrid architecture is the best possible case, and so in fact we left this exploration for future studies. However, following your suggestion and to address your concern, we have added additional case studies on the different stacking patterns of the hybrid approach. The results of these ablations are reported in Appendix J. Based on these results the proposed SSM+attention can be both more effective and efficient than other variants (e.g., attention + SSM).

W2:The superior performance of the ensemble approach, though noteworthy, is an expected outcome rather than a novel contribution.

Response: Please note that this study, to the best of our knowledge, is the first study that suggests a hybrid model (SSM + Attention) for graphs, whose effectiveness is non-trivial due to the small scale of graph learning models. We also want to kindly bring to your consideration that neither the mixture of experts (here mixture of tokens) nor hybrid architecture are an ensemble approach. In fact, in the ensemble method, we have different models and all nodes go through all models and the average (or voting) of all models will be considered as the final output. In our hybrid model, we use SSM and attention sequentially, rather than as two separate models. In the mixture of tokens (as a variant of the mixture of experts), also, nodes do not go through all models (as in ensemble method) and instead, there is a router that decides which type of tokenization is the best for each node. Therefore, the effectiveness of both of these approaches for graph sequence models are non-trivial, not fully expected, and novel.

W3: the empirical performance of baselines (such as graph mamba and GRED) are missing

Response: We kindly bring to your attention that the empirical performance of graph mamba were presented in Tables 3, 7, and 8 in the initial submission. Please note that in the original paper, their model is called GMN (graph mamba networks) and so we have used GMN in the tables. Also, the results of GRED are already reported in and outperformed by graph mamba paper, which we have already compared with. However, following your suggestion, we have included the results of GRED and a new efficient graph transformer (GRIT) in the revised version.

W4: MoT requires concatenation of sequence encodings generated by two different tokenizers …

Response: Please note that concatenation of these two vectors only results in $d_{in}^2$ additional parameters, which is negligible in practice as $d_{in} <= 100$ ($d_{in}$ is the dimension of the input of the sequence model). To further address your concern, we have provided a theoretical discussion in Appendix K. We further have experimented the efficiency of MoT in Table 10 (page 34).

W5: The efficiency and complexity of the proposed GSM++ is missing.

Response: Thank you for mentioning this. Following your suggestion, we have provided the theoretical time complexity of GSM++ in Appendix K of the revised version. It’s worth mentioning that because of the linear time training of SSMs, the time complexity of GSM++ is linear with respect to the graph size. We further provide the empirical results of efficiency comparison on two large-scale datasets in Appendix K.