Towards an Understanding of Graph Sequence Models
Graph Learning;Sequence Models;Graph Transformers;Hierarchical Clustering
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
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).
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.
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.
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.
Yes
No ethics review needed.
See above.
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.
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.
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.
Yes
No ethics review needed.
- 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?
1. a comprehensive theoretical analysis on different ingredients of graph sequence model
2. a novel hierarchical tokenizer with hierarchical positional encodings
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.
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.
@inproceedings{
anonymous2024towards,
title={Towards an Understanding of Graph Sequence Models},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=iaHghgG8NR},
note={under review}
}
Modern sequence models (e.g., Transformers, RNNs, gated convolutions, 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 of 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 an 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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Graph Learning Sequence Models Graph Transformers Hierarchical Clustering
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/6755c6f2ba6140a130a9475b6d7496338f07cf3e.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Towards an Understanding of Graph Sequence Models
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission