Towards an Understanding of Graph Sequence Models

Authors: Ali Behrouz, Ali Parviz, Mahdi Karami, Clayton Sanford, Bryan Perozzi, Vahab Mirrokni
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Learning, Sequence Models, Graph Transformers, Hierarchical Clustering

Abstract:
Modern sequence models (e.g., Transformers, linear RNNs, etc.) emerged as dominant backbones of recent deep learning frameworks, mainly due to their efficiency, representational power, and/or ability to capture long-range dependencies. Adopting these sequence models for graph-structured data has recently gained popularity as the alternative to Message Passing Neural Networks (MPNNs). There is, however, a lack of a common foundation about what constitutes a good graph sequence model, and a mathematical description of the benefits and deficiencies in adopting different sequence models for learning on graphs. To this end, we first present Graph Sequence Model (GSM), a unifying framework for adopting sequence models for graphs, consisting of three main steps: (1) Tokenization, which translates the graph into a set of sequences; (2) Local Encoding, which encodes local neighborhoods around each node; and (3) Global Encoding, which employs a scalable sequence model to capture long-range dependencies within the sequences. This framework allows us to understand, evaluate, and compare the power of different sequence model backbones in graph tasks. Our theoretical evaluations of the representation power of Transformers and modern recurrent models through the lens of global and local graph tasks show that there are both negative and positive sides for both types of models. Building on this observation, we present GSM++, a fast hybrid model that uses the Hierarchical Affinity Clustering (HAC) algorithm to tokenize the graph into hierarchical sequences, and then employs a hybrid architecture of Transformer to encode these sequences. Our theoretical and experimental results support the design of GSM++, showing that GSM++ outperforms baselines in most benchmark evaluations.

Decision: reject
Reviewer scores: 6, 3, 3, 3

Reviews and discussion:
<thread>
creation date:
1730298580064

thread_type:
official_review

<thread_object>
creator: reviewer_42gl

<content>
summary:
This work aims to study graph sequence model (GSM) in a unified framework. A GSM in this framework consists of the tokenization, local encoding (e.g., GNN)  and global encoding (e.g., recurrence models or transformers). The authors discuss the pros and cons of recurrence models v.s. transformers in global encoding stage, as well as node/edge/subgraph tokenizer in tokenization stage. Besides, they propose a hierarchical tokenization technique using Hierarchical Affinity Clustering, allowing for a graph encoding at different levels of granularity.

strengths:
1. a comprehensive theoretical analysis on different ingredients of graph sequence model
2. a novel hierarchical tokenizer with hierarchical positional encodings

weaknesses:
1. the theory part (Section 3) does not seem well-organized, self-consistent and clear enough to follow. For examples,
	- Line 219 "Based on the above results, we can see that when dealing with naturally sequential tasks, recurrent models are more powerful than softmax non-causal Transformers". The "above result" is that softmax non-causal transformer cannot resolve counting task while recurrence model can. However, counting task does not seem to be sufficient to represent "naturally sequencetial tasks". In fact, the counting of node colors in a graph is a permutation invariant function, since node ordering does not impact the counting. 
	- Line 215 "Can causality resolve this issue?". This question is raised by the authors but there is no any follow-up.
	- Line 268 "This result motivates us to explore hybrid models, combining SSMs with non-causal Transformers to take advantage their inductive bias while avoiding representational collapse by self-attention layers". The statement is based on causal transformers have no representational collaspse, which is not argued in the context.
	- Line 251 "Transformers have constant sensitivity on the tokens distances" and Line 257 "In both Transformers and SSMs, the information about tokens located near the start of the sequence have more opportunity to be maintained at the end". 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?
2. the experiment part misses some details:
	- what are the performance metrics shown in Table 1 and 2?
	- what is specifically "MPNN" in Table 1?
3. 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.

questions:
- Line 303, Defintition 1 $\arg\max_i\\{e_i:v\in e_i\\}$: what does it mean to take maximium over an edge set?
- in Table 1, does node degree task refer to compute the node degree of each node? If so, why GIN cannot perform well on the task?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730380953365

thread_type:
official_review

<thread_object>
creator: reviewer_7fvs

<content>
summary:
This paper aims to enhance the understanding of graph sequence models. It tries to draw insights via theoretical analysis to see which sequence models and node tokenization strategies would be more suitable for certain graph tasks. Then, the paper proposes to utilize Hierarchical Affinity Clustering (HAC) for graph tokenization and conducts experiments with different sequence models. Results on multiple standard datasets show good performance of the proposed method.

strengths:
1. The manuscript is well-written and easy to follow.
2. Sec. 3 is interesting to read, which provides some insights into the capability of different sequence models on graph tasks.

weaknesses:
1. I'm a bit confused about the positioning of this paper. It seems to me the most interesting part is Sec. 3, which organizes some previous results and also provides a few new results. However, if we were to see the technical results of this paper, then they seem a bit limited. For example, the overall framework (tokenization + local + global) is not new, the usage of SSMs on graphs is not new, etc. Perhaps the use of HAC could be considered somewhat new, but the ablation studies cannot really show its benefits. In the meantime, the experiments exclude many recent baselines (even though they are actually cited), and it seems the empirical performance is not that excellent compared to recent baselines, e.g., Grit, Graph-Mamba (two concurrent works), GSSC, etc.
2. If we only look at Sec. 3, it seems the results are not comprehensive enough.
    - I do appreciate that Sec. 3 organizes some previous results well and also includes some new results. But still, many results in Sec. 3 are not that original.
    - After reading Sec. 3, it still remains hard to really draw practical insights. For example, 
        - I still find it hard to compare recurrent models and transformers from PROPOSITION 1 and THEOREM 1, because PROPOSITION 1 limits itself to cases without properly using PE, which may not be the cases in the graph domain.
        - It seems hard to conclude that recurrent models could be more efficient on connectivity tasks in practice, because the bounds in Sec. 3.3 may not really show significant difference in practical cases.
    - The other thing is that it seems the experiments (table 2) cannot sufficiently support the takeaway listed in Sec. 3. The selected datasets may not be challenging enough, and in most cases using different sequence models yields close performance.

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730693278837

thread_type:
official_review

<thread_object>
creator: reviewer_wpzs

<content>
summary:
This paper studies the sequence models such as Transformers, RNNs, SSMs on graphs. The authors unify graph sequence models by three operators: Tokenization, Local Embedding and Global Embedding. Then, the authors study the pros and cons of applying different sequence models on Counting and Connectivity tasks. The authors also propose a hybrid model, GSM++, which incorporates HAC-based tokenization, a GatedGCN as the local encoder, and a hybrid global encoder that combines Mamba and Transformer models sequentially.

strengths:
1. The exploration of sequence models on graphs is interesting.
2. The authors investigate the effects of different sequence models on graph-based tasks, specifically focusing on Counting and Connectivity.
3. The authors provide examination of different tokenization methods.

weaknesses:
1. Most of the theoretical foundations in this paper are derived from prior work focused on sequence models, such as Transformers and RNNs, originally designed for sequential data rather than graphs. The paper lacks theoretical adaptations specifically tailored to graphs, which limits its contribution in this area. Additionally, several theorems (e.g., Theorems 3, 5, 6, and 7) are presented without proof.

2. The logical flow of the paper is unclear. While several theorems are presented, many do not lead to the conclusions that the authors claim, which makes it difficult to follow the arguments effectively.

3.

questions:
1. Why are the color counting problem important for graphs?

2. The authors claim that "Both causal Transformers and SSMs can suffer from representational collapse, resulting in limited representational power. This result motivates us to explore hybrid models, combining SSMs with non-causal Transformers to take advantage their inductive bias while avoiding representational col- lapse by self-attention layers". Why does non-causal transformers solve the representational collapse issue?

3. 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. Additionally, most of the theorems lack experimental support.

4. The writing quality could be improved, as there are some typos, such as duplicate words (e.g., in line 137).
</content>
</thread_object>

</thread>
<thread>
creation date:
1731210217937

thread_type:
official_review

<thread_object>
creator: reviewer_brcn

<content>
summary:
This paper proposes a robust and unified model that offers both flexibility and adaptability for designing sequence models intended for learning on graphs. The architecture includes three main modules: (1) Tokenization, (2) Local Encoding, and (3) Global Encoding, which facilitates effortless and efficient comparison between graph sequence models in terms of their performance on graph learning tasks, including RNN, SSM, etc. The authors also provide a theoretical analysis of the recurrent models and transformer-based graph models. An enhanced model, GSM++, is proposed based on empirical findings. GSM++ is specifically designed with three enhancement techniques: Hierarchical Affinity Clustering, a mixture of tokenization, and hybrid encoders.

strengths:
1. The paper is well-written and easy to follow. Theorems are proved in appendix. 
2. The proposed framework (tokenizer, local encoding, and global encoding) unifies most existing graph sequence models, enabling effortless evaluation and creation of GSMs within a unified setting. 
3. Experimental results are promising. GSM++(MoT) achieves state-of-the-art performance in most cases.

weaknesses:
1. Critical experimental details are missing. The paper omits essential hyper-parameter configurations, including the number of self-attention layers and hidden dimensions utilized in GSM++. Such omissions hinder reproducibility and meaningful comparison with other models.
2. The architectural design choices in GSM++ lack comprehensive ablation studies. While the combination of Mamba and attention mechanisms demonstrate improved performance, alternative architectural variants (e.g., different stacking patterns of Mamba and attention layers) remain unexplored. The superior performance of the ensemble approach, though noteworthy, is an expected outcome rather than a novel contribution.
3. Appendix H (Line1544) mentioned that baselines include state-of-the-art GTs and recurrent graph models (e.g., graph mamba and GRED). However, the empirical performance of these baselines are missing.
4. MoT requires concatenation of sequence encodings generated by two different tokenizers, which significantly increases the computational complexity. GSM++ may suffer from scalability issues when applying larger datasets and more complex tasks.
5. The efficiency and complexity of the proposed GSM++ is missing. The paper should provide theoretical complexity analysis compared to existing Graph Transformers and recurrent models; training and inference time, memory cost, etc.

questions:
1. The term "softmax non-causal Transformers" requires a clearer definition. What is the relation between non-causality and permutation equivariance? How does this property specifically benefit graph-based tasks?
2. The discrete router mechanism in the Model-of-Thought (MoT) framework requires further elaboration. Is it implemented as a learned component with trainable parameters, or does it follow predetermined heuristic rules?
3. The HAC tree implementation raises several computational concerns.  What is the time complexity for constructing the HAC tree, especially for large graphs? How computationally intensive is the hierarchical positional encoding computation? Are there any optimizations or approximations that can be used to make these steps more efficient?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732257495756

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
**We sincerely thank all the reviewers for their time and constructive reviews, which have helped us to improve the paper.**
$  $  
$  $

## Revisions
--- 
Here, we have summarized the changes in our revised version:
- **Presentation**: We really appreciate that Reviewers **brCn** and **7fVS** have found the presentation of our work **``well-written and easy to follow``** and **``interesting to read``**. We, however, following the reviews of Reviewers **WpZs** and **42GL**, have made some revisions to further improve the presentation of the paper as follows:
  - We consistently use the term of causal or non-causal Transformers, when differentiation is required, to avoid the confusion. 
  - We added a paragraph at the end of the Introduction section to further enhance the clarity of our goals and roadmap in the paper. 
  - We revised the takeaway paragraphs for all subsections, which can help the reader to better understand the main goals of each subsection. We further made sure that all the required steps for the conclusion are explained.
  - We have provided the used metrics for each table.
- **Additional Details about Mixture of Tokens**: We have provided additional details about the router we use in the Mixture of Tokens in Appendix A4.
- **Experimental Setups**: We have added all the used configurations for all the datasets in Table 7.
- **Additional Experiments**: 
  - We provide additional experiments on the effect of different stacking patterns of layers in the hybrid model. The results are presented and discussed in Appendix J.
  - We have performed additional experiments on two large-scale datasets to compare the efficiency of GSM++ with state-of-the-art methods.
  - We have performed additional experiments on the efficiency of our HAC tokenization and compared it with commonly used positional encodings. 
  - Using hyperparameter tuning, we have improved the results presented in the paper.
  - We have updated the results in Table 2 with a more challenging setup to better support our theoretical results.
  - We have added a new baseline (w/o PE) to Table 2 that supports Theorem 1.
  - We have updated the results of the ablation study for HAC as we used HAC-based positional encoding, which could not show the effect of fully removing HAC from the model. 
  - We present the results of more baselines, including GRED and GRIT. 
- **Theoretical Time Complexity**: We provided the theoretical time complexity of GSM++ in Appendix K.


## Contributions
----
We further want to kindly bring to your consideration the **main contributions of this paper**:
- Due to the recent interest in adapting sequence models for efficient graph learning, understanding their power beyond the WL test is important. This paper is a first step toward this direction.
- This paper has made different types of contributions:
   - First, we provide extensive and new theoretical results to better understand the power of sequence models for graph tasks. While the main focus of this paper is on graph learning, some of these results are generally about the power of sequence models, which have a broader impact on different communities. Most of these theorems are through the lens of circuit complexity, which can help understand graph sequence models’ power beyond the WL test.
  - Second, motivated by these theoretical results, we have presented a novel method that all its components (except message-passing) are new and novel! Particularly, we present (1) a novel tokenization method based on the HAC tree algorithm, (2) a new hierarchical positional encoding based on HAC, (3) a new hybrid architecture of SSM + Transformers, and (4) a new technique of mixture of tokenization that allows flexible graph tokenization. To the best of our knowledge, none of these contributions are mentioned or used by other studies. We want to kindly bring to your attention that coming up with an architecture in which most of its components are new is challenging and usually has not been done in the literature (For example, GraphGPS (NeurIPS, 2022) presents new positional encodings, NAGPhormer (ICLR, 2023) presents new tokenization, Graph-Mamba (KDD, 2024) presents the use of Mamba, GRIT (ICML, 2023) presents a new positional encoding, etc.) 
  - Third, our extensive experimental evaluation can be useful for the community as a benchmark of different existing sequence models on graph tasks. In particular, Figure 3 is the result of 378 experimental evaluations on 9 different sequence models and 6 different graph tokenizations.


Once again, we thank all the reviewers for their time and kind consideration. We hope that our responses have fully addressed their concerns. We would be happy to provide further information or address any remaining concerns.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732989960290

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers, ACs,

**We sincerely appreciate your time in helping us improve the paper.**

We want to kindly remind you that the discussion period is coming to an end. We believe this discussion is **particularly important** for our submission as there were some misunderstandings in the initial reviews and we have tried to clarify them in our rebuttal. We also, kindly bring to your attention that in our responses we **fully** addressed the reviewers' suggestions by providing new experiments to further support our claims, adding a discussion on time complexity, and improving the presentation.

**We hope you kindly consider a renewed assessment of the paper considering the addressed misunderstanding and the recent manuscript.**

Please let us know if you have any additional questions or doubts; we would be happy to address them.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Majority of the reviewers are concerned about this paper in major ways and the paper received weak support overall. Thus a reject is recommended.