Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Authors: Ali Behrouz
Ali Parviz
Mahdi Karami
Clayton Sanford
Bryan Perozzi
Vahab Mirrokni
Venue: ICML 2025 poster (2025)
Keywords: Graph Learning
Sequence Models
Graph Transformers
Hierarchical Clustering
Primary area: deep_learning->graph_neural_networks

Abstract: Modern sequence models (e.g., Transformers and linear RNNs) emerged as dominant backbones of recent deep learning frameworks, mainly due to their efficiency, representational power, and/or ability to capture long-range dependencies. Recently, adopting these sequence models for graph-structured data has 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 introduce the Graph Sequence Model (GSM), a unifying framework for applying sequence models to graph data.  The GSM framework allows us to understand, evaluate, and compare the power of different sequence model backbones in graph tasks. Building on this insight, we propose GSM++, a fast hybrid model that hierarchically tokenizes the graph using Hierarchical Affinity Clustering (HAC) and then encodes these sequences via a hybrid architecture. The  theoretical and experimental findings confirm that GSM++ outperforms baseline models on most benchmarks.

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Ali Behrouz' Ali Parviz Mahdi Karami
Clayton Sanford
Bryan Perozzi! Vahab Mirrokni
Abstract
the complexities of graph-structured data more effectively, Graph Transformers have demonstrated compelling results, particularly by leading in tasks like molecular property pre- diction (Ying et al., 2021; Hu et al., 2020; Masters et al., 2023). Their advantage over traditional MPNNs is often at- tributed to tendency of MPNNs to focus on local structures, making them less effective at capturing global or long-range relationships due to issues like over-smoothing (Li et al., 2018), over-squashing (Alon & Yahav, 2020; Di Giovanni et al., 2023; Dwivedi et al., 2022a), and restricted expressive power (Barceló et al., 2020). In contrast, GTs (Rampášek et al., 2022) can learn and capture the pairwise dependencies of nodes, and aggregate global information across the graph, reducing the local structural bias.
Modern sequence models (e.g.. Transformers and linear RNNs) emerged dominant backbones of recent deep learning frameworks, mainly due to their efficiency, representational power, and/or ability to capture long-range dependencies. Re- cently, adopting these sequence models for graph- structured data has gained popularity as the al- ternative to Message Passing Neural Networks (MPNNs). There is, however, lack of a common foundation about what constitutes a good graph sequence model, and mathematical description of the benefits and deficiencies in adopting dif- ferent sequence models for learning on graphs. To this end, we introduce the Graph Sequence Model (GSM), a unifying framework for apply- ing sequence models to graph data. The GSM framework allows us understand, evaluate, and compare the power of different sequence model backbones in graph tasks. Building on this insight, we propose GSM++, a fast hybrid model that hi- crarchically tokenizes the graph using Hierarchi- cal Affinity Clustering (HAC) and then encodes these sequences via a hybrid architecture. The theoretical and experimental findings confirm the efffectiveness of GSM++.
Despite the expressive power of traditional Transformer- based architectures, they face scalability issues in long- context tasks, mainly due to their quadratic computational complexity. Various strategies have been proposed to mit- igate quadratice complexity of Transformers (Tay et al., 2022), including sparsifying the dense attention matrix (Za- heer et al., 2020; Beltagy et al., 2020a; Roy et al., 2020; Kitaev al., 2020), low-rank approximations of the atten- tion matrix (Wang al., 2020), and kernel- based attention mechanisms (Choromanski et al., 2020b; Kacham et al., 2024). While these methods enhance computational effi- ciency, they often come at the expense of reduced expres- siveness (Mchta et al., 2022). In recent years, attention- freee sequence models have emerged as a promising alternative to Transformers for sequence modeling. Leveraging paralleliz- able recurrent neural networks (RNNs) (Peng al., 2023; Behrouz et al., 2024; 2025a;b) and long convolutions (Poli et al., 2023; Karami & Ghodsi, 2024), offer sub-quadratic Hardware-efficieer sequence mixing operators that can cap- ture long- dependencies with strong generalization to sequences of varying lengths.
1. Introduction
Message-passing graph neural networks (MPNNs) have been the leading approach for processing graph data (Kipf & Welling, 2016; Gilmer et al., 2017a; Chami et al., 2020; Morris al., 2020). However, with the increasing popu- larity of Transformer architectures (Vaswani al., 2017) and their success in natural language processing and com- puter vision, recent research has shifted towards developing graph Transformers (GTs), which are designed to handle
Given the promising potential of the sub-quadratic sequence models, there is growing interest in extending them to the graph domain an alternative to graph Transformers (Ding et al., 2023: Behrouz & Hashemi, 2024; Huang et al., 2024). However, a significant technical challenge arises from the inherent differences between graphs and other structured data, such as text, which is naturally causal. Graphs exhibit complex topology and lack a natural, linear node ordering. Attempting to impose naive tokenization strategy, such as
Google Research, USA Miila- Quebec AI Institute NNew Jersey Institute of Technology, NJ, USA. Correspondence to: Ali Behrouz <alibehrouz google.com.. Ali Parviz <ali- parviz mww..eiiila.uub.>>......mm Bryan Perozzi <bperozzi cetroozz@@cc.orgg acm.org>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
sorting nodes into a sequence, undermines the crucial in- ductive bias of permutation equivariance inherent graphs. This misrepresentation of graph structure can lead to poor generalization performance. Furthermore, there is a lack of a common foundation about what constitutes a good graph sequence model, and a mathematical description of the ben- efits and deficiencies of adopting different sequence models for learning on graphs.
models through the lens of connectivity tasks. We show that Transformers more effective than recurrent models in such tasks, but with a small modification of the tokens' or- der, recurrent models can become extremely efficient. In $F.1, we theoretically analyze the effect of tokenization methods (node or subgraph), and how it can help to improve the efficiency and solve the fundamental problem of motif counting in graphs. Given our theoretical observations and what we have learned from these results, in $4, present GSM++ that uses a novel tokenization based on the Hier- archical Affinity Clustering (HAC) tree. GSM++ further employs hybrid sequence model with two layers of SSM followed by a transformer block. We then present a Mixture of Tokenization (MoT), allowing the combination of differ- ent sets of tokenizations that are the best for each node, to further enhance the effectiveness and efficiency of GSM++,
We propose unified, flexible framework for graph-based learning that simplifies constructing and comparing diverse architectures. This approach enables comprehensive the- oretical and empirical evaluations on tasks such as graph connectivity and counting. Our findings reveal that although permutation equivariance in Transformer-baser models is generally seen as an advantage. it hampers counting per- formance on graphs. In contrast, SSM/RNN-basee models show unbounded capacity for color counting, emphasizing the power of recurrence in specific graph learning scenar- These findings are the first steps toward better under- standing of the power of graph sequence models beyond traditional metrics (e.g., WL. test) and can help to answer what types of sequence models are the best, given the type of the task at hand.
2. Encoding Graphs to Sequences
Despite a variety of GNNs with diverse modules that are designed based on sequence models, we find that cach part of these architectures is responsible for encoding a specific characteristic of the graph. To formalize this, we present our unified model consisting of three main stages: (1) Tok- enization, (2) Local Encoding, and (3) Global Encoding.
We identify limitations in existing tokenization strategies and introduce GSM++ novel graph learning method fea- turing hierarchical tokenization with proven theoretical ad- vantages. GSM++ pairs this tokenization with a hybrid se- quence model (a combination of recurrent and Transformer architectures) to achieve strong performance across diverse graph tasks. Notably, it is the first graph sequence model that merges Transformers and SSMs, offering a more flexi- ble and comprehensive solution than existing models. Our experiments validate this hybrid approach, enhancing under- standing of model capabilities and guiding the development of specialized methods for graph-based learning
2.1. Tokenization
Sequence models inherently designed process se- quenees of tokens. To adapt them for graph-structured data, the graph must first be translated into a set of se- quences (Müller et al., 2024; Behrouz & Hashemi, 2024; Ding et al., 2023). These approaches can be categorized into two main groups:
Node/Edge Tokenizers. Node or edge tokenization meth- ods treat the graph as a sequence of node/edges without considering how they are connected. Accordingly, these methods lack inductive bias about the graph structure and so they require be augmented with positional structural encoding to inject information about the graph structure. Let G = (V, E), be a graph, V = {ui,.... fivi} is the set of nodes, and P E R is the posittional/strucuural en- coding matrix, whose rows encode the position of nodes. In this case we translate the graph as a sequence of G := : Poy...., Paivi Similarly, for edge tokenization we can replace {ui,..., "vvi with [er, (er.....( The main drawback of methods based on node/edge tokeniza- tion is their computational complexity. That is, treating the graph sequence of nodes (resp. edges) results in having a sequence with length V (resp. [E]), meaning that for quadratic models (e.g., Transformers) the training time complexity is at least O (2) (resp. O ( (16)2))
Contributions and Roadmap. In $2, we present Graph Sequence Model (GSM) framework that can help us to sys- tematically study the power of GSMs in different scenarios. We then in $3 aim to understand strengths and weaknesses of different types sequence models for graph tasks. To this end, in 13.1, we show how recurrent nature of model can help it to perform tasks like counting more effectively, while permutation equivariance of Transformers make them un- able to count. In $3.2, we analyze sequence models through the lens of sensitivity: while linear recurrent models (c.g., SSMs) have a better inductive bias about the nodes' distance, this advantages can cause representational collapse in deep models. Using these results, motivate a combination of transformers and SSMs so the SSM module can enhance the inductive bias, and the permutation equivariance of Trans- former can avoid representational collapse in the model. In $3.3, we evaluate the reasoning capability of graph sequence
2

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
Subgraph Tokenizers. To reduce the computational cost
2.3. Global Encoding
of node tokenization and incorporate inductive bias, sev- sequence or
As discussed, the local encoding stage serves two key roles: (I) It encodes the local characteristics of the graph, injecting inductive bias in the model; and (2) it vectorizes the tokens, preparing them for a sequence encoder in the Global Encod- ing stage. Here, the main objectíve is to learn dependencies across all tokens, enabling the model to capture long-range relationships. Formally, let 5(t)s s be the sequences of en- codings obtained from the local encoding stage, for each = ..... T, we have:
eral methods propose treating the graph sequences of subgraphs and then encode these sequences us-
ing a sequence model. Formally, given a graph G = (V. F),, the graph can be represented as a set of sequences of sub- graphs G : (SO), S(x)), ). where:
5(1) = G ................................ " and H SV.
(1) When T < [V1, we refer to this process as patching. A pioneer approach in this direction is DeepWalk (Perozzi et al., 2014), which uses random walks to sample from the graph and tokenize it into a set of sequences. A more recent method is the k-hop neighborhood tokenization used by NAGphormer (Chen et al., 2023), where each node's ' hierarchical neighborhood is treated as its representative sequence. For further discussion and examples of these methods, see Appendix B. Since using T = [V l = 1, "r,...,IV]j IV],, reduces subgraph
y = V. (AcG, ($ 812) ....,,,......................... ......,))) )())
(3)
where V.(.) are sequence models and (.G are aggre- gator functions, In most existing node tokenization-basee methods (.G - CONCAT(.) (concatenation), while in most subgraph tokeniztion- methods AGG;(.) = ()), (broadcasting i-th element). However, sequence models themselves can be used as aggregator functions, as demon- strated by Behrouz & Hashemi (2024).
and H = } for i = (1,..., tokenization to node tokenization, unless stated otherwise, we will use this formulation moving forward.
In Appendix C, we illustrate that several well-known meth- ods for learning on graphs are special instances of this Graph Sequence Model (GSM) framework.
Although there is a variety of studies across the aforemen- tioned categories, a common foundation is still lacking re- garding what constitutes effective tokenization and what diffcrentiates them with respect to the task. In Section 3, we theoretically show that each of node and subgraph tok- Accordingly, the
3. Choosing a Sequence Model
One critical question remains- - what sequence model should one use? Following the above mentioned framework, one can simply replace different sequence encoders in the global encoding stage and combine them with different tokeniza- tion methods, resulting in hundreds of potential graph leam- ing models. However, there is a lack of a common founda- tion about what constitutes a good model in each of these stages, and a mathematical description of the benefits and deficiencies of adopting different sequence models for learn- ing on graphs. In this section, we theoretically discuss the ddis)advantager of different sequence models and tok- enizations in several downstream graph tasks, providing a guideline for the future research and model developments.
enizations offer their own (dis)advantagen) choice between node tokenization, subgraph tokenization, or a combination of both depends on the specific task at hand (see Section 4.3). We further validate this theoretical foundation using several experiments in Section 5.1.
2.2. Local Encoding
Following the tokenization step, where the graph is trans- lated into a set of sequences (representing nodes, edges, or subgraphs), the main objective of the Local Encoding step is to capture and learn the graph's local characteris- ties by vectorizing these tokens. Formally, given a graph G (V. F.), let G denote the set of all subgraphs, and (Local)) (.) : 9 + ddd represent a GNN encoder. With the graph tokenized as Equation 1, we define the local encoding as dLocal (G) = (501, ((T,, where:
3.1. Counting Tasks Graphs
In the first part, we focus on counting tasks, where the ob- jective is to count the number of nodes with each particular color in a node-colored graph. Such tasks are analogous to the copying tasks in sequence modeling, which are com- mon benchmarks to measure the abilities of a sequence model (Arjovsky et al., 2016; Gu & Dao, 2023; Barbero et al., 2024), in the sense that counting tasks require con- sidering all nodes and even missing single node's ' color can potentially result in incorrect prediction. Hence, let's 's first recall proposition on the inability of Transformers in counting tasks:
g(0 &rocal (GLE((")
Local (c
(2)
While the choice of encoder ((.) is arbitrary, convolutional MPNNs are typically preferred due to their ability to effec- tively learn local dependencies around each node, As an illustrative example, assume that the k-hop neighborhood tokenization was used in the previous step, then each 51(1 represents a sequence describing the hierarchical neighbor- hood around node U; and @Local (G) is the encoding of j-th hop neighborhood of v;..
PROPOSITION 1 (PROPOSITION 6. OF BARBERO ET AL.
3

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
(2024)). A Transformer model based on non-causal atten- tion and without proper positional encodings is immediately unable to count.
where Biow is:
L-1 Clu EAm 1, (I A 112
-, 1, 1,8)
This limitation of non-causal Transformers in counting tasks raises an important question: Can the inherent causality of recurrent models resolve this issue, and are they better suited for such tasks? The next theorem answers this:
COROLLARY 1. In SSMs, the sensitivity of the output with respect to a previous token, i.e. 8yk, is a decreasing func- 8x: tion of their distance (i.e., d = k - i). Therefore, closer tokens have higher impact on each others' encodings.
THEOREM 1. Let C be the number of colors, and m be the width of recurrent model, the recurrent model can count the number of nodes with each specific color iff m 2 C.
Takeaway. Contrary to Transformers that relies on posi- tional encodings, recurrent models' inherent inductive bias make them capable of handling such sequential tasks. Ac- cordingly, when dealing with sequential tasks that are less dependent on the graph's 's topology and permutation equivari- ance, recurrent models are more powerful than non-causal Transformers.
Notably, this property is distinctive trait of SSMs and contrasts with Transformers, which exhibit constant sensi- tivity (Song et al., 2024). However, the following corollary to Theorem 2 reveals that SSMs also suffer from represen- tational collapse as the number of layers grows, a behavior which was also observed in causal Transformers (Barbero et al., 2024). Hence, SSMs offer no advantage in this aspect.
COROLLARY 2. Let L be the number of layers in the recur- rent model. As L - oc, the output representation depends only on the first token.
3.2. Importance of Node Ordering
As discussed earlier, due to the sequential nature of some graph tasks, the permutation equivariant property of non- causal Transformers can undermine their representational power. Beyond simple counting tasks, several important and complex graph datasets and tasks-such as neural al- gorithmic reasoning tasks in sequential algorithms (Xu & Veličković, 2024) and CLRS dataset (Bentley, 1984; Gavril, 1972)-involl naturally ordered nodes, requiring causal encoder to effectively capture their inherent order. On the other hand, most subgraph tokenizers produce sequences with an implicit order (e.g., k-hhop neighborhoods), which requires a causal model to capture their hierarchy. Given the causal nature of most powerful modern sequence models, in this section, we analyze how node ordering can impact the performance of the model, and if there is an ordering mechanism for nodes that can enhance the performance of causal sequence models.
In both causal Transformers and SSMs, the information about tokens located near the start of the sequence have more opportunity to be maintained at the end. This might seem counter-intuitive for recurrent models like SSMs, which are expected to exhibit a recency bias towards the recent tokens due to their constant size hidden state. However, note that this result differs from recency bias in recurrent models as it concerns the information flow along the sequence dimension rather than across the model's depth. Interestingly, together with their recency bias, this new result indicates a U-shape effect in SSMs, meaning that information from tokens at both the beginning and end of sequence is better preserved, a phenomenon also observed in causal Transformers (Bar- bero et al., 2024).
Takeaway. This part yields three key insights: (1) When nodes are naturally ordered, SSMs posses a stronger in- ductive bias than Transformers, as they are sensitive the tokens' distance. (2) Both causal Transformers and SSMs can suffer from representational collapse, limiting their rep- resentational power. The fact that non-causal Transformer are permutation equivariant and so does not suffer from rep- resentational collapse motivates the exploration of hybrid models that combine SSMs with non-causal Transformers to take advantage of SSMs' inductive bias while avoiding representational collapse (see Section 4.2). (3) When order- ing nodes (e.g. to model hierarchy or for sequential tasks), it is advantageous to place relevant nodes close together as it results in high sensitivity with respect to similar nodes and less sensitivity with respect to less relevant, dissimilar ones. To this end, in Section 4.1, we present a tokenization method that implicitly orders nodes based on similarity.
Sensitivity Analysis. Over-squashing is an undesirable phenomenon in GNNs that is related to representational collapse. One way to analyze over- squushing in a model is to study how sensitive is the final output token to an input token at position é: i.e., äy, where yj and x, are output and ox,"
input of the model at position j and i, respectively. Next, we bound the sensitivity of SSMs after L layers:
THEOREM 2. For any k i let i(k, = -1-
...... (1- })} t) i < n, the grudient norm of the HiPPO operator for the output of layer L at time n + 1 (i.e., y yott) with respect to imput at time i (i.e., X:) satisfies:
and L be the number of layers. For any
(L),
1y (L)
Biom S
<11
@ynt1
S
C(LL up
1
i x
n
4

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
3.3. Connectivity Tasks on Graphs
ditional hardness of solving cCmploee problems with constant depth transformers (Merrill & Sabharwal, 2023).
This section addresses the graph connectivity task, which requires the sequence model to capture global understand- ing of the graph. We frame graph connectivity classification problem, where the input is a tokenized graph G = (V, E), and the target output is 1 if G is connected and O otherwise. Using edge tokenization, we represent the graph as the sequence G := PeL...,, PETEr
THFOREM 5. Unless NC = TC,, any log-precision trans- former that solves graph connectivity on edge embeddings with |E] I N, and node locality 12 requires either depth (11) or width Nw(1).
binary
Takeaway. In graph connectivity, as an example of a global task, Transformers are more powerful than recurrent meth- ods in general cases. However, with a good choice of tok- enizer and ordering, recurrent models can become extremely efficient and powerful. See Appendix E for a detailed discus- sion and comparison of Transformers with recurrent models. Following this insight, in Section 4.1, we present new tok- enization that can provide us with such desirable ordering.
COROLLARY (COROLLARY 3.3 OF SANFORD ET AL.. (2024B)). For any N and e E (0, 1). there exists a trans- former with depth Oloog N) and embedding dimension ONN)) that determines whether any graph G = (V, with [VI, |E| S N is connected.
Next, we show that alternative architectures cannot solve graph connectivity with such low-dimensional parameteri- zation.
In Appendix E.3 we focus on motif counting and shortest path tasks and theoretically discuss what substitute good tokenizer. We present both positive and negative negative results for each type of tokenization, providing evidence that subgraph tokenizers are useful when extra attention on local structures is needed. On the other hand, when dealing with long-range dependencies and global graph tasks, node/edge tokenizers are more efficient choices.
THEOREM 3. A multi-layer recurrent model, a Transformer with kernel-based subqquarratic attention, or a Trans- former with locally masked attention units of radius r that solves graph connectivity on all graphs G (V.E) with IV [E| < N has either depth L = S(N11/8) or m = ((
As a result, these attempts to improve the quadratic com- putational bottleneck result in a lack of parameter-efficient connectivity solutions. All recurrent models, kernel-based transformers with kernel dimension
4. Enhancing Graph to Sequence Models
4.1. Hierarchical Affinity Clustering (HAC) Tokenization
(NN and all local transformers with window size r O(N1/8) require at least ((N2/8) parameters.
As discussed in Section 3.2, using a tokenizer that generates an ordered sequence, where similar nodes are positioned near each other, can improve the sensitivity of the method, thereby enhancing its representational power. Furthermore, as discussed in Section 4, when representing a graph as sequence with node locality k (Definition 1), powerful recurrent models become very efficient for global tasks like connectivity. Motivated by these results, we present a hierarchical tokenization based on the Hierarchical Affinity Clustering (HAC) (Bateni et al., 2017) algorithm and show that it satisfies the above desirable characteristics.
When are recurrent models more efficient? The main ben- efits of recurrent models, including SSMs, is when either the data comes with a natural ordering, or the encoding (in Tokenization and Local Encoding stages) has carefully embeded the graph structure in the order of tokens. To formalize this, we define notion of locality for edge embedding and show that this induces easy embeddings for recurrent models but not for transformers.
DEFINITION 1. Let the node locality of an edge embedding P......,PPo. PeLEy of a graph G = (V, E) denote the maxi- mum window size needed to contain all edges that adjoin each node. That is, we say that G has node locality if maxve vaarg (arg max, (ecv E Eei] ei)-arg min, (ecv E <e:)s k.
HAC is highly scalable and parallelizable cluster- ing algorithm based on Boruvka's algorithm (Boruuvka, 1926). Given a graph G = (V.E) and node encodings Po....., p the algorithm begins by treating each vertex as a singleton cluster, then at each step removes the cheapest edge (cost calculated by the similarity of node encodings) going out of each cluster and join these two clusters to form larger cluster. This process continues until a cluster in- cludes all the nodes. The stages of this algorithm form HAC tree, where the root represents the last cluster in the algorithm (entire graph), its two children are the last two clusters in one round before the end of the algorithm, and so forth. Accordingly, leaves are nodes of the graph, being our initial clusters. See Figure for an example of a HAC tree.
Next, we show that graphs with bounded node locality admit hine/parameter--fffiieee recurrent solutions:
THEOREM 4. There exists single-pas, magle--aas recurrent model with hidden state (kk) that determines whether edge em- bedding with node locality at most k reflects a connected graph.
Interestingly, no constant-size transformer that solves the above task exists. We prove this by a reduction to the con-
5

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Construct HAC Tree
DFS BFS Traverse
Local Encoding
Hybrid Sequence Encoder
Graph:
DFS: Each DPS path starting from the root ordered sequence that represents hierarcky of similar nodes around each vertex.
We simple Gated Graph Convolstional Network (GatedGCX) to encode each the tokens.
Motivated by theoretical results, hybrid sequence model that takes the advantage of both tramsformers and recurrent models.
Note: HAC toleoiiaation provides an ordered list of modes such that similar nodes are close to each other, resuiting in a higher sensitivity!
This is suberanh tokenisstion approachl
HAC Tree
Graph Level
BPS: Bach BPS path k-th lovel is hicrarchical mode tokmisation k-th level granalarity the graph.
One of the roles of this step la to vectoriae the subgraphs to propare sequence vectorn for the next step.
Architecbure the Hybrid Model
2 Clustera Level
Mamba
Seif Atlention
Looking at only log 2 (IV[)-th level, it is a simple mode tokenisation.
CltedGCC(()
Node Level
Figure I: Overview of GSM++ GSM++ uses: (1) HAC tokenization, (2) hierarchical PE, and (3) a hybrid sequence model.
HAC offers two key advantages for an effective tokeniza- tion. First, it orders nodes such that adjacent nodes (hav- ing the same parent node) in the tree are the most similar, which is aligned with our theoretical analysis. Second, it provides hierarchical clustering, allowing for graph en- coding different levels of gramularity. We propose two types of tokenization based Depth-First Search (DFS) and Breadth-First Search (BFS) traversals of the HAC tree.
This theorem, along with Theorem 4, motivates us to use HAC tokenization with recurrent model as the global encoder later in our final architecture design.
Hierarchical Positional Encoding. One of the main ad- vantages of HAC is its ability to provide us with rich in- formation about the hierarchy of structures in the graph. Inspired by recent studies that show the power of hierarchy- aware positional encodings (Luo et al., 2024), we present new PE based on the shortest path of clusters includ- ing two nodes of interest v, u E V. We define Pe.. = (al)) d ... du,
DFS Traverse of HAC Tree. After performing HAC and constructing the HAC tree, we perform DFS traverse and treat each path as a sequence. That is, given a graph G (V, E), let r be the root of the tree, DFS path the HAC V.
(log((V)) the relative positional encod-
ing of u and v such that d(f) is the length of the shortest between the clusters that include these nodes at the i-level of HAC tree. This positional encoding not only considers the shortest path of u and v (du, (Vl) is the length of their shortest path), but it also encodes their relative position in different levels of granularity. We experimentally show that this positional encoding very effective.
+ c = where represents the entire graph and cy represents node E V. This sequence represents hierarchy of clusters whose nodes are similar to uú and encodes the hicrarchical position of U; in the graph. This approach is a subgraph- based tokenization as discussed in Section 2.1.
tree is G = r + ci + 6
BFS Traverse of HAC Tree. In this approach, we perform BFS traverse the HAC tree. Note that the maximum depth of the tree is log2((V[) (Bateni et al., 2017). Let k < (VV), we treat k-th level of BFS traverse as path, representing the graph at k-th level of granularity. When k = 1, the length of the sequence is one and the only element is the root (entire graph). When & the depth of the tree, the sequence is the sequence of all nodes, but in order that similar nodes are close to each other. In this tokenization method, we construct the sequences for all values of < k < (VV') and encode the graph at different levels of granularity. We consider a simple average pooling to obtain the overall encodings.
4.2. Hybrid Models
As discussed in Section 3.2, sequential combinations of recurrent models with transformer layers can results in a model with higher representational power.
THEOREM (INFORMAL). There exists a hybrid recur- rent + Transformer model that solves an instance of graph connectivity more efficient than 2-layer recurrent model or transformers.
For a detailed theoretical discussion the importance of hybrid models see Appendix E.3. Motivated by these theo- retical results, we suggest a 2-layer hybrid block, where the first layer is Mamba (Gu & Dao, 2023) and the second layer is a Transformer block (Vaswani et al., 2017). We further experimentally show the significance of this hybrid design.
THEOREM 6. Given a graph with minimum node locality of k. there exists a node embedding that HAC (BFS) tokeniza- tion, order nodes a way that the sequence is k-local.
6

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Graph tasks that require global information'. The first and second best results of each type are highlighted. The best overall result for each task is marked *.
Table 2:
Table 1: Graph tasks that require local information', The first and second best results of each type are highlighted. The best overall result for each task is marked *
Connectivity
Color Counting
Shortest Path
Model
Node Degree
Cycle Check
Triangle Counting
1K
100K
IK
100K
IK RMSE
10K
Model
Accuracy 1
Accuracy 1
IK Accuracy
100K
IK 100K
Erdos- Frdos-Renyi Regular
Accuracy
RMSE! 4
Reference Baselines
Reference Baselines
GCN
63.3
70.8
52.7
55.9
2.38
2.11
GatedGCN
74.9
77.5
55.0
56.6
1.98
1.93
GCN
9.3
9.5
80.3
80.2
0.841
2.18
MPNN
71.8
76.1
53.9
57.7
1.96
1.93
GatedGCN
29.8
11.6
86.2
83.4
0.476
0.772
GIN
71.9
74.6
52.4
55.1
2.03
1.98
MPNN
98.9
99.1
99.1*
99.9*
0.417
0,551
GIN
36.4
35.9
98.2
81.8
0.659
0.449"
Transtormers
Node
85.7
86.2
73.1
77.4
1.19
1.06"
Transformers
w/o
6.8
35.8
28.9
4.12
5,33
Node
29.9
30.1
30.8
31.2
0.713
1.19
HAC (DFS)
87.0
88.1
83.7
85.3
1.14
1.09
HAC (DFS)
31.0
31.0
58.9
61.3
0.698
1.00
k-hop
69.9
70.2
79.9
80.3
2.10
2.15
k-hop
97.6
98.9
91.6
94.3
0,521
0.95
HAC (BFS)
74.1
76.7
74.5
77.8
2.31
2.28
HAC (BFS)
98.1
98.6
91.9
92.5
0.574
0.97
Mamba
Mamba
Node
82.8
84.7
80.1
82.5
1.27
1.13
Node
30.4
30.9
31,2
33.8
0.719
1.33
w/o PE
9.2
7.5
78.9
81.3
4.09
5.22
HAC (DFS)
32.6
33.6
33.7
34.2
0.726
1.08
HAC (DFS)
83.6
85.2
85.2
85,4
1.12
1.15
k-hop
98.5
98.7
90.5
93.8
0.601
0.88
k-hop
70.9
71.0
82.6
83.5
2.03
2.11
HAC (BFS)
98.1
99.0
93.7
93.5
0,528
0.92
HAC (BFS)
76.3
77.4
83.7
84.1
2.24
2.18
Hybrid (Mamba + Transformer)
Hybrid (Mamba Transformer)
Node
31.0
31.6
31.5
31.7
0.706
1.27
Node
88.1
88.6
82.9
83.0
1.24
1.13
w/o PE
8.9
8.1
83.2
84.8
4.65
4.89
HAC (DFS)
32.9
33.7
33.9
33.6
0.717
1.11
HAC (DFS)
90.7"
91.4"
85.8"
86.2"
1.11"
1.93
k-hop
99.0"
99.2"
90.8
91.1
0,598
0.84
k-hop
70.8
73.3
83.7
84.6
1.99
2.04
HAC (BFS)
98.6
98.5
93.9
94.0
0.509
0.90
HAC (BFS)
78.0
79.5
83.1
83,7
2.16
2.13
4.3. Mixture of Tokenization (MoT)
tently outperforms other models? (See Figure 2) (3) What is the performance of GSM++ compared existing state- of-the-art methods on benchmark datasets? (See Table 3, and Table 5, 6) (4) How does each component of GSM++ contribute to its performance? (See Table 4)
Since each type of tokenization has its own (dis)advantages (see Appendix F.1 for theoretical results), we suggest using a Mixture of Tokenization (MoT) technique, where we al- low each node to use tokenization that best describes its position based on the task. For example, one node might be better to be represented by itself (along with a positional encoding) since its neighborhood extremely noisy, At the same time, another node might be better to be represented by its neighbors there is strong homophily in that area of the graph. Let T be the list of different tokenizers, we use a discrete router that chooses top-2 tokenizations from T for each node. We then concatenate the encodings of these tok- enizers to obtain the final encoding for the global encoding step. See Appendix A.4 for additional information.
Graph Tasks. We conduct experiments on: (1) Local tasks: node degree, cycle check, and triangle counting, and (2) Global Tasks: connectivity, color counting, and shortest path. These tasks are known for evaluating the ability of models in learning from graphs (Sanford al., 2024a; Fatemi et al., 2023). For the benchmark tasks on the comparison of GSM++ with baselines, we use node clas- sification and graph classification (Dwivedi et al., 2022a; 2023; Platonov et al., 2023; Rampášek & Wolf, 2021). See Appendix for the details of tasks and datasets.
Baselines. We use state-of-the-art GTss securrent-based and MPNNs as our baselines. We also perform ablation studies by replacing various sequence models with each other. The full list of the sequence models, and the details of baselines are in Appendix I.
5. Experiments
Research Questions. In our experiments, we aim to em- pirically validate the key claims of this paper and compare the performance of our final model, GSM++, with state- of-the-art methods. Specifically, we aim to answer: (1) Is there tokenizer that consistently outperforms other types of tokenization methods? (See Table and Table 2) (2) Is there Global Encoder (c.g., sequence model) that consis-
5.1. On the Effect of Tokenization and Global Encoder
Local Tasks. The results are reported in Table 1. Interest- ingly, MPNNs have outstanding performance due to their ability to capture local structures. Comparing node-based
7

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Table 3: GNN benchmark datasets (Dwivedi et al., 2023). The first, second, and third best results are highlighted.
Table 4: Ablation studies. The first and second best results for each model are highlighted.
MNIST
CIFARIO Accuracy
PATTERN
MalNet-Tiny
COCO-SP
PascalVOC-SP
PATTERN
Model
Model
Accuracy 1
Accuracy 1
Accuracy
FI score
F1 score 1
Accuracy
GCN
0.9071 40.0021
0.5571 20.0058
0.718920.003
0.8000
GPS Framework
GraphSAGE
0.9731 10.0009
0.6377 2000030
0.504900.000:
0.8030
Base
0.3774
0.3689
0.8664
GAT
0.955440.c021
0.6422::0.044
0.7027=000019
0.8509
+Hybrid
0.3789
0.3691
0.8665
SPN
0.8331 yu 0446
0.3722 2177222...0011 08.77
0.0037
0.6407 100001
+HAC
0,3780
0.3699
0.8667
GIN
0.964940.ozzz o02s
01.5566.0.013
0.8539
0.8898 10000s
+MoT
0.3791
0.3703
0.8677
GaNed-GCN
0.973440.000 0014
0.6731=0.0051
0.8357=0.008
0.0223-0.0005
NAGphormer Framework
CRaWi
0.979420.000
0.0901
Base
0.3458
0.4006
0.8644
NAGphermer
0.8641-0.0008
+Hybrid
0,3461
0.40446
0,8650
GPS
0.981 1 2010011
0.7226
0.8664-000011
0.9298 20.0047
+HAC
0.3507
0.4032
0.8653
GPS (BigBird)
0.9817 1.88170..00
0. 7..7080000000
0.8600=0.0014
0.9234
+MoT
0,3891
0,4105
0.8657
Exphormer
0.9855 0.00
0. 0.7469
0.8670=0.000s
0.0002
NodeFormer
0.8639
GSM++
DIFFormer
Base
0.3789
0.4128
0.8738
GRIT
0.9810g0.com
0.76 0.7646
0.871920-000
-PE
0.3780
0.4073
0.8511
GRED
0.9838
0.7685
0.8675go.o0rz
-Hybrid
0.3767
0.4058
0.8500
GMN
0.9783+0.c020
0. 0.714430.0009
0.86490000001
0.9352x0.0030
-HAC
0.3591
0.3996
0.8617
GSM++ (BFS)
0.98 0.9848_..oom 0012
0.765922.00m
0.873822.000
0.9417
GSM++ (DFS)
0.0820
0.7692:0.00m
0.8731
0.9389=a.0024
GSM++ (MoT)
0,9884-o.om
0,7781
0.8793=0.001s
tokenizer (i.e., Node and HAC (DFS)) with subgraph-based tokenizer (i.e., h-hop and HAC), subgraph-baser tokenizers perform significantly better in these tasks, mainly due to their local inductive bias about the structure of the graph. Models using node-based tokenizers lack implicit inductive bias and rely on the global positional encodings.
Spaa
Alteriio
(APS)
ITAC
SW
Global Tasks. The results are reported in Table 2. In global tasks, node tokenizers outperforms subgraph tok- enizers. The main intuition behind this result is that these tasks require global knowledge about the graph structure and looking subgraphs can results in missing information about far nodes (or missing long-range dependencies). The only exception is color counting, which is parallelizable task, meaning that the model can counts by aggregating information obtained from different subgraph tokens.
Kdeep
Paic
Figure 2: Normalized score of different combination of tokeniza- tion and global encoder (sequence models).
7 = 378 experimental results), we visualize the rank of the model (higher is better), instead of reporting them in a table. The normalized results are reported in Figure 2. These results indicate that there is no model that significantly outperforms others in most cases, validating our theoretical results that each of the sequence models well as the types of tokenization has their own advantages and disadvantages. Accordingly, we need to understand the spacial traits of these models and use them properly based on the dataset and the task. Following our results, we conjecture that the no free lunch theorem applics for the Graph2Sequence.
Takeaways. Considering both tables, we conclude that while none of Mamba or Transformer performs the best across all tasks, the hybrid model improves the perfor- mance in most cases, indicating the significance of hybrid approaches to take advantage both worlds. Note that we fix the number of parameters for all models. These results are also aligned with our theoretical discussions.
5.2. Is There Superior Model among Simple GSMs?
5.3. The Effect of Proposed Enhancements GSMs
To answer this question, perform extensive evaluation with all the combinations of 9 different sequence models and 6 types of tokenizers over 7 datasets of Citeseer, Cora, Computer, CIFAR1O, Photo, PATTERN, and Peptides-Fune from Dwivedi et al. (2022b; 2023); Chen et al. (2023). Due to the large number of cases (9 x 6 54 models with 54 x
We perform two types of ablation studies: (1) We start with two commonly used frameworks of GraphGPS (Rampášek et al., 2022) and NAGphormer (Chen et al., 2023) that use node-based and subgraph- based tokenization, respectively. We then (i) replace their transformer with a hybrid model, (ii) use HAC instead of their tokenization, and (iii) use
8

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
Table 6: Long-Range Datasets (Dwivedi et al., 2022b). The first, second, and third results are highlighted.
Table 5:
Heterophilic datasets (Platonov et al., 2023). The first, second, and third results are highlighted.
COCO-SP Fl score 1
PascalVOC-SP
Peptides-Func AP
Model
Roman-empire Accuracy 1
Amazon-ratings Accuracy
Minesweeper
F1 score
Model
ROC AUC f
GCN
0.084120.0010 10.0010
0.1268_o.oo
0.393020.0023
GCN
0.7369 0074
0.4870ga.0063
0.897510.0061
GIN
0. 0,133920.00
0.1265 200076
0.3498
GraphSAGE
0.8574 0067
0.5363 200
0.935120.00s7
Gated-GCN
20.0100
0.2873200.211
0.586420.0077
GAT
0.7973 0069
0.5270g0.0002
0.9391 0035
GAT
0.129622.000
U.1753_0.001
0.5308 20.0019
OrderedGNN
0.7768 0089
0.4729
0.8058+0.0108
MixHop
0.2500
0.68-33=0.004
IGNN
0.7995 oora
0,4821 #0.0088
0.9193 0.00
DIGL
0.2921 = o00as
0.6830
Gated-GCN
0.7446go.oom
0.0000
0.875440.0122
0.2056
0.6926
NAGphormer
0.7434 OU77
0.5126 2..166
0.8419 1: 000G
SAN+LapPE
0.259220.0155
0.3230
0.63842o.0121
GPS
0.8200 0001
0.53101a.00az
0.9063
NAGphormer
0.305820.0070
0. 4006=000001
Exphormer
0.8903 0087
0.5351 50.0000
0,907 00.0053
Graph VIT
0.685520.0049
NodeFormer
0.6449go 0073
0.1386 00.00
0,867 +0 0088
GPS
0.3 13774=00.1500
00.001
0.6575=0.00p
DIFFomner
0.7910 0002
0.4784
0. 40.008
Exphormer
0.3
0.3975_0.00s7
0.6527
GOAT
0.7150 0126
0.4461 #0.000
0.8109
NodeFormer
0.3275.0.0241
0.4015
GMN
0.821920.o0m
0.5327 20.0020
0.8992
DIPFormer
0.36202a.0012
0.3988
GRIT
20.082
GSM++ (BFS)
0.9003.1 0087
0.5381 00335
0.9109 2.0 0088
GRED
0.705510.00z
GSM++ (DFS)
0.9124_0 0023
0.5361 20000m
0.9145 0006
GMN
0.361820.065
0.4169
0.6860=0.0012
GSM++ (MoT)
0.9177=0 0040
0. 0.5390+0.0104
0.9149+0.0111
GSM++ (BFS)
0.3789 =0. 0160
0.41 0.41 0.0000
0.6991
GSM++ (DFS)
20.0277
0.417440.00m
0. 0.701920.0084
GSM++ (MoT) 0.3801 00222
0.41 1o.077
0.7092.0.0076
MoT: (2) We remove components of GSM++, one at time, to see the effect of (i) hierarchical positional encoding, (ii) hybrid sequence encoder, and (ii) HAC tokenization. The results are reported in Table 4. All the components of GSM++ have an impact on its superior performance, where most contribution comes from HAC tokenization, followed by hybrid sequence encoder, and hicrarchical PE. Also, we can conclude that using hybrid sequence models, HAC tokenization, and Mixture of Tokens, all have positive impact on the performance of other models, showing that the presented enhancement techniques are effective in practice. Supporting our theoretical results (Theorems and 6). HAC has a higher impact on recurrent models than Transformers.
and 6 types of tokenizers over 7 datasets of Citeseer, Cora, Computer, CIFARIO, Photo, PATTERN, and Peptides-Func from Dwivedi et al. (2022b; 2023); Chen et al. (2023). Due to the number of cases (9 x 6 54 models with 54 x = 378 experiments), we visualize the rank of the model (higher is better), instead of reporting them in a table. The normalized results are reported in Figure 2. These results indicate that there is no model that significantly outperforms others in most cases, validating our theoretical results that each of the sequence models as well as the types of tokenization has their own advantages and disadvantages. Accordingly, we need to understand the spacial traits of these models and use them properly based on the dataset and the task, Following our results, we conjecture that the no free lunch theorem applies for the Graph2Sequence problem.
5.4. Performance of GSM++ on Benchmark Tasks
We also followed the literature and compare the perfor- mance of GSM++ with state-of-the-an methods in node and graph classification tasks on commonly used benchmark datasets (Dwivedi et al., 2022b; 2023; Platonov et al., 2023). The results are reported in Tables 3, 5, and 6. These results show that GSM++ achieves a good performance and out- performs baselines in 8/10 cases. We attribute this superior performance of GSM++ to: (1) its ability to capture hierar- chical structure of the graph and having proper sensitivity with respect to important nodes through proper ordering, which is the result of HAC tokenization and hierarchical PE; and (2) using a hybrid sequence model.
6. Conclusion
We aim to understand Graph Sequence Models, a family of graph learning models that translate the graph into a (set) of sequence(s), vectorize it, and then employ powerful se- quence models to learn dependencies of nodes. We provide extensive theoretical results to show the importance of or- dering, when it is needed, and to show that there is no single sequence model or tokenization method that works strictly better for all graph algorithmic problems. Motivated by our thcoretical results, we present GSM++ model with new hierarchical graph tokenization method based on HAC, a new mixture of token (MoT) approach to take advantage of different tokenization, and hybrid sequence model based on Mamba and self-attention. Our experimental evaluations support the theoretical results and the design of GSM++.
5.5. Which GSM Is More Effective In Practice?
To answer this question, perform extensive evaluation with all the combinations of 9 different sequence models
9

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Impact Statement
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., and Hochreiter, S. xLSTM: Extended long short-term mem- ory. arXiv preprint arXiv:2405.0444 0.000.,041,... 2024.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Behrouz, A. and Hashemi, Graph mamba: Towards
learning on graphs with state space models. In Pro- ceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '24, pp. 119-130, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400704901. doi: 10. 1145/3637528.6672044, URL https: httpa://doo..rgg/ 10. N0.1145/363783 3672044.
References
Abboud, R., Dimitrov, R., and Ceylan, I. I. Shortest path networks for graph property prediction. In Learning Graphs Conference, pp. 5-1. PMLR, 2022.
Alman, J. and Song, Z. Fast attention requires bounded entries, 2023.
Behrouz, A., Zhong, P., and Mirrokni, V. Titans: Learning to memorize at test time, arXiv preprint arXiv:2501.0660 2024.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. ArXiv, abs/2006.05205. 2020.
Behrouz, A., Li, Z., Kacham, P., Daliri, M., Deng, Y., Zhong, P., Razaviyayn, M., and Mirrokni, V. Atlas: Learning to optimally memorize the context at test time. arXiv preprint arXiv:2505.237355 2025a.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In In- ternational Conference on Learning Representations, 2021. URL
Behrouz, A., Razaviyayn, M., Zhong, P., and Mirrokni, It's all connected: journey through test-time memoriza- tion, attentional bias, retention, and online optimization. arXiv preprint arXiv:2504.1 25ti:22244.11133,, 2025b.
id=i 800PhCCVH2.
Arjovsky, M., Shah, A., and Bengio, Y. Unitary evolution re- current neural networks. Balcan, M. F. and Weinberger, K. Q. (eds.), Proceedings of The 33rd International Con- ference on Machine Learning, volume 48 of Proceed- ings of Machine Learning Research, pp. 1120-11 128, New York, New York, USA, 20-22 Jun 2016. PMLR. URL httph:tt///// http:://poccceeeee pttpppeeeogg...../// mlr press/v48/ ar jovvkky16 16. html.
Beltagy, I., Peters, M. E., and Cohan, A. Long-
former: The long-document transformer. arXiv preprint arXiv:2004.057 1..0000..555, 2020a.
Beltagy, I., Peters, M. E., and Cohan, A. Longformer: The long-document transformer, 2020b.
Bentley, J. Programming pearls: algorithm design tech- niques. Commun. ACM, 27(9):865 8733, September 1984. ISSN 0001-0782. doi: 10.1145/358234.381166 URL https://doi.
Bar-Shalom, G., Bevilacqua. B., and Maron, H. Sub- graphormer: Subgraph GNNs meet graph transformers. In NewrIPS 2023 Workshop: New Frontiers in Graph Learning, 2023. URL https:////o// httt::://penreviee..o forum? feriumiideebaae 9Hu1mM.
10. 111..1.111//3822.388000 381162
Biswas, A. S., Eden, T., Liu, Q. C., Mitrović, S., and Rubin- feld, R. Massively parallel algorithms for small subgraph counting, 2022. URL https: http://xxvvv..///
Barbero, F., Banino, A., Kapturowski, S., Kumaran, D., Araújo, J. G., Vitvitskyi, A., Pascanu, R., and Veličković, P. Transformers need glasses! informa- tion over-squashing in language tasks. arXiv preprint 1rXi::2406604266,, 2024.
Boruuvka, O. O jistém problému minimálním, 1926.
Bresson, X. and Laurent, T. Residual gated graph convnets. 2017.
arXiv preprint
Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., and Silva, J. P. The logical expressiveness of graph neu- ral networks. In International Conference on Learning Representations, 2020.
Chami, I., Abu-El-Haija, S., Perozzi, B., Ré, C., and Mur- phy, K. P. Machine learning on graphs: A model and comprehensive taxonomy. J. Mach. Learn, Res., 23:89:1- 89:64, 2020.
Bateni, M., Behnezhad, S., Derakhshan, M., Hajiaghayi, M. T., Kiveris, R., Lattanzi, S., and Mirrokni, V. Affin- ity clustering: Hierarchical clustering at scale. In Neural Information Processing Systems, 2017.
Chen, D., O' O'Bray. L., and Borgwardt, K. M. Structure- aware transformer for graph representation learning. In International Conference on Machine Learning, 2022.
10

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Chen, D., Schulz, T., and Borgwardt, K. Learning long range dependencies graphs via random walks. In 13th International Conference Learning Representations (ICLR 2025), 2025.
Dwivedi, V. and Bresson, X. A generalization of trans- former networks to graphs. ArXiv, abs/2012.09699,, 2020.
Dwivedi, V. P. Luu, A. T., Laurent, T., Bengio, Y., and Bres- son, X. Graph neural networks with learnable structural and positional representations. ArXiv, abs/2110.07877, 2021.
Chen, J., Gao, K., Li, G., and He, NAGphormer: A tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations, 2023. URL https:// // openrevien net/ forum?? ? 8=8KYe 133...
Dwivedi, V. P., Rampavsek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. ArXiv, hass/2006.01164 2022a.
Choromanski, K., Likhosherstov, V., Dohan, D., Song. X., Gane, A., Sarlós, T., Hawkins, P., Davis, J., Mohiud- din, A., Kaiser, L., Belanger, D., Colwell, L. J., and Weller, A. Rethinking attention with performers. ArXiv, abs/2009. 14794, 2020a.
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph bench- mark. In Koyejo, S., Mohamed, S., Agarwal, A., Bel- grave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 22326 22340. Curran Associates, Inc., 2022b.
Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L., et al. Rethinking attention with performers. arXiv preprint ar arXiv:2009. 14794, 2020b.
Dwivedi, V. P., Joshi, K., Luu, T., Laurent, T., Ben- gio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1 48, 2023.
Chu, S. and Cheng, J. Triangle listing in massive net- works and its applications. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '11, pp. 672-680, New York, NY, USA, 2011. Association for Comput- ing Machinery. ISBN 978 1781450008177 doi: 10.1145/ 0020408.20205133 URL https:://oi.... org/0.. 0t2.::222008200022...22
Fatemi, B., Halcrow, J., and Perozzi, B. Talk like a graph: Encoding graphs for large language models, 2023. URL https: /eops://azeee //tp/aiivv//////////////////aav/ http://aavvv.ora////////a//a wttg/bs//////aeeeeeeeeeeeg 04560.
Gavril, F. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of chordal graph. SIAM Journal on Computing, 182):180-187, 1972. doi: 10.1137/0201013. URL https:tpps.. /tt.//ooiiioo///// org/ wtt.:///.............. www.:1113100100
Dao. I. and Gu, A. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. In International Conference on Machine Learning (ICML), 2024.
Ghaffari, M., Kuhn, F., and Uitto. J. Conditional hardness re- sults for massively parallel computation from distributed lower bounds. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pp. 1650- 1663, 2019. doi: 10. 10.11090OOS2S20..00000
Deng, C., Yue, Z., and Zhang, Z. Polynormer: Polynomial- expressive graph transformer in linear time. In The Twelfth International Conference on Learning Represen- tations, 2024. URL htttps://opereeee .net forum? saiiiiiid--mmiii hd-bhylphhhy........
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International Conference on Machine Learning, 2017a.
Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pp. 7865-7885. PMLR, 2023.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017b.
Ding, Y., Orvieto, A., He, B., and Hofmann, Recurrent distance-encoding neural networks for graph representa- tion learning. arXiv preprint arXiv:2312.01538, 2023.
Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks, 2016.
Ding, 7., Li, Y., He, Y., Norelli, A., Wu, J., Tresp, V., Ma, Y., and Bronstein, M. DyGMamba: Efficiently modeling long-term temporal dependency on continuous- time dynamic graphs with state space models. ArXiv, abs/2408 0iso24408.04713, 2024.
Gu, A. and Dao, T. Mamba: Linear-time seq-uence modeling with sele ctive state spaces. arXiv preprint 1rX0:22312.00752, 2023.

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Gu, A., Dao, T., Ermon, S., Rudra, A., and Ré, C. Hippo: Recurrent memory with optimal polynomial projections. Advances in neural information processing systems, 33: 1474-1487, 2020.
Karypis, G. and Kumar, V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20( (0(1):359339, 1998. doi: 10.1137/
SI $10648275952877997. URL https:
1 1137 /
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Kim, J., Nguyen, D., Min, S., Cho, S., Lcc, M., Lee, H., and Hong. S. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35: 14582-14595, 2022.
He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. A generalization of vit/mlp-mixer to graphs. In International Conference on Machine Learning, pp. 27724-12743 PMLR, 2023.
Kipf. T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016.
Hu, W. Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118-22111 2020.
Kitaev, N., Kaiser, I.., and Levskaya, A. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
Hua, C., Rabusseau, G., and Tang. J. High-order pooling for graph neural networks with tensor decomposition. Advances in Neural Information Processing Systems, 35: 6021-6033, 2022.
Kong, K., Chen, J., Kirchenbauer, J., Ni. R., Bruss, C. B., and Goldstein, T. Goat: A global transformer on large- scale graphs. In International Conference Machine Learning, pp. 17375 117390 PMLR, 2023.
Huang. Y., Lu, W., Robinson, J., Yang. Y., Zhang, M., Jegelka, S., and Li, P. On the stability of expressive posi- tional encodings for graphs. In International Conference on Learning Representations, 2023.
Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-21622 2021.
Huang, Y. Miao, S., and Li, What can we learn from state space models for machine learning on graphs? ArXiv, abs/2406.05815,, 2024.
Kuang. W., Zhen, W., Li, Y., Wei, Z., and Ding, B. Coar- former: Transformer for large graph via graph coarsening. OpenReview, 2021.
Jelassi, S., Brandfonbrener, D., Kakade, S. M., and Malach, E. Repeat after me: Transformers are better than state space models at copying, 2024.
Li, D., Tan, S., Zhang, Y., Jin, M., Pan, S., Okumura, M., and Jiang, R. DyG-Mamba: Continuous state space mod- eling on dynamic graphs ArXiv, abs/2408.066 2024.
Kacham, P., Mirrokni, V., and Zhong, P. PolySketch- Former: Fast transformers via sketching polynomial ker- nels. In Forty-first International Conference on Machine Learning, 2024. URL http:/t:///pppeeeeaaaaaaaaa .ee.e forum? d=g.h
Li, P., Wang, Y., Wang, H., and Leskovec, J. Distance en- coding: Design provably more powerful neural networks for graph representation learning. arXiv: Learning, 2020.
Li, Q. Han, 7.,, and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI Conference on Artificial Intelligence, 2018.
Karami, M. and Ghodsi, A. Orchid: Flexible and data- dependent convolution for sequence modeling. Thirty- eighth Conference on Advances in Neural Information Processing Systems, 2024. URL https:: //rxiv.. org/abs// awt.//////22 2402 18508.
Liao, T. and Poczos, B. Greener grass: Enhancing gnns with encoding, rewiring, and attention. The Thirteenth International Conference on Learning Representations, 2025.
Karami, M. and Mirrokni, V. Lattice: Learning efficiently compress the memory. arXiv preprint arXiv:2504.05644 2025.
Loukas, A. What graph neural networks cannot learn: depth vs width. ArXiv, abs/1907. .03199, 2019.
Karloff, H., Suri, S., and Vassilvitskii, S. A model of compu- tation for mapreduce. In Proceedings of the Twenty-Firs. Annual ACM-SIAM Symposium on Discrete Algorithmss, SODA '10, pp. 938-948, USA, 2010. Society for Indus- trial and Applied Mathematics. ISBN 978089871699 16966.
Luo, Y., Li, H., Shi, L., and Wu, X.-M. Enhancing graph transformers with hierarchical distance structural encod- ing. 2024. URL https:: / /arxiv. www.voor.//./..o........o..ooo.r aas//bb/aa 2308. 11129.
12

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph in- ductive biases in transformers without message passing. In International Conference on Machine Learning, pp. 23321 -23337. PMLR, 2023.
P., Kocoá, J., Kong, J., Koptyra, B., Lau, H., Mantri, K.
S. I., Mom, F., Saito, A., Tang, X., Wang, B., Wind, J. S., Wozniak, S., Zhang, R., Zhang, Z., Zhao, Q. Zhou, P., Zhu, J.. and Zhu, R. Rwkv: Reinventing mns for the transformer era. In Conference on Empirical Methods in Natural Language Processing, 2023.
Maskey, S., Parviz, A., Thiessen, M., Stärk, H., Sadikaj, Y., and Maron, H. Generalized laplacian positional encoding for graph representation learning, ArXiv, 00592210.119560 2022.
Perozzi, B., AI-Rfou, R., and Skiena, S. Deepwalk: line learning of social representations. In Proceed- ings of the 20th ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining, KDD '44 pp. 701-710, New York, NY, USA, 2014. Associa- tion for Computing Machinery. ISBN 9781 9781450329569. doi: 10.1145/2623330.222322.. URL https: /doi. org org/10 http:..1114//// 1et.i.1112222332 2623732..
Masters, D., Dean, J., Klaeser, K., Li, Z., Maddrell-Mander, S., Sanders, A., Helal, H., Beker, D., Fitzgibbon, A. W., Huang, S., Rampášek, L.,, and Beaini, D. GPS++: Re- viving the art of message passing for molecular prop- erty prediction. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https:// openreview net 1d=moVEUgJHH..
Perozzi, B., Fatemi, B., Zelle, D., Tsitsulin, A., Kazemi, M., Al-Rfou, R., and Halcrow, J. J. Let your graph do the talking: Encoding structured data for llms. ArXiv, abs/2402.05862, 2024.
Mehta, H., Gupta, A., Cutkosky, A., and Neyshabur, B. Long range language modeling via gated state spaces. arXiv preprint arXiv:2206.1394 13947, 2022.
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023. URL https: / openrevie...eeeeee net / forum? Jbbpruum----tttttoo-o------
Merrill, W. and Sabharwal, A. The parallelism trade- off: Limitations of log-precision transformers. Trans- actions of the Association for Computational Linguis- tics, 11:531-544 15451, 2023. ISSN 2307-387X. doi: 10. 1162/tacl 00562.. http://///dd http//ddddoooog//1/////
Poli, M., Massaroli, S., Nguyen, E., Fu, D. Y., Dao, T. Baccus, S., Bengio, Y., Ermon, S., and Ré, C. Hyena hierarchy: Towards larger convolutional language models. International Conference on Machine Learning, 2023.
Merrill, W., Petty, J., and Sabharwal, A. The illusion of state in state-space models, 2024.
Morris, C., Ritzert, M., Fey, M.. Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Pro- ceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T. Wolf, G., and Beaini, D. Recipe for general, powerful, scal- able graph transformer. Advances in Neural Information Processing Systems, 35: 15:14501-14515. 2022.
Morris, C., Rattan G., and Mutzel, P. Weisfeiler and Le- man go sparse: Towards scalable higher-order graph em- beddings. Advances in Neural Information Processing Systems, 04:21824-21840, 2020.
Rampášek, L. and Wolf, G. Hierarchical graph neu- ral nets capture long- rangrrane interactions. In 2021 IEEE 31st International Workshop Machine Learn- ing for Signal Processing (MLSP), pp. 1-6, 2021. doi: 10. 10910095553000.0000 1000219..966.....
Müller, L., Galkin, M., Morris, C., and Rampášek, L. Attending to graph transformers. Transactions on Machine Learning Research, 2024. ISSN 2835- 8856. URL httph::t/////tttt https:://peereeieer net/ id=HhbgfRRRrf..
Roy, A., Saffar, M., Vaswani, A., and Grangier, D. Efficient content-based sparse attention with routing transformers. Proceedings of TACL, 2020.
Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B., and Mirrokni, Under- standing transformer reasoning capabilities via graph al- gorithms, 2024a. URL httpst http:::///xxvvvv/ee abs/ 2405 18512.
Nisan, N. and Wigderson, A. Rounds in communication complexity revisited. SIAM Journal on Computing, 22(1): 211-219, 1993. doi: 17.1127/022001.. URL https: //doi. ///oo..og//0. 1137 /
Peng. B., Alcaide, E., Anthony, Q. G., Albalak, A., Arcad- inho, S., Biderman, S., Cao, H., Cheng, X., Chung, M.,
Sanford, C., Hsu, D., and Telgarsky, M. Transform- ers, parallel computation, and logarithmic depth. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A.,
Grella, M., Kranthikiran, G., He, X., Hou, H., Kazienko,
13

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Pro- ceedings of the 41st International Conference on Ma-
Wang, C. X., Tsepa, O., Ma, J., and Wang, B. Graph- Mamba: Towards long-range graph sequence modeling with selective state spaces. ArXiv, abs/2402.00789,, 2024.
chine Learning, volume 235 of Proceedings of Ma-
chine Learning Research, pp. 091776-4332.. PMLR, 21- 27 Jul 2024b. URL https: https: /tattt::://rrreeeee http:///oocddddeeeooo www.ddinnmll.......m.....mmm. 1ttss///235//aaaa/e html.
Wang. H., Yin, H., Zhang, M., and Li, P. Equivariant and stable positional encoding for more powerful graph neu- ral networks. In International Conference on Learning Representations, 2022. URL https: http::::////peeeieire.. net / forum (aeeuummiiiiee -ed.d=119955hh)1
Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland,
D. J., and Sinop, A. K. Exphormer: Sparse transformers for graphs. arXiv preprint arXiv:2303.06147, 2023.
Wang. S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.000 04768, 2020.
Song, Y., Zhou, C., Wang, X., and Lin, Z. Ordered GNN: Ordering message passing to deal with heterophily and over-smoothing. In The Eleventh International Confer- ence on Learning Representations, 2023. URL ht https: //openreview. http:/iiwwweeeeeeeeeeeeeeeeeeeee forum/ormmmm/// PdW P BHSnT6. 6.
Wu, Q. Zhao, W., Li, Z.,, Wipf, D. P., and Yan, J. Node- former: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27444 2022.
Song, Y., Huang. S., Cai, J., Wang. X., Zhou, C., and Lin, Z. S4g: Breaking the bottleneck on graphs with structured state spaces, 2024. URL ttttps://cpenreeee /ppprevieneeeeeeeeeeeeeee net/
Xu, K. and Veličković, P. Recurrent aggregators in neural algorithmic reasoning. arXiv preprint 2490:2409,.7154, 2024.
Sun, Y., Li, X., Dalal, K., Xu, J., Vikram, A., Zhang, G., Dubois, Y., Chen, X., Wang. X., Koyejo, S., et al. Lear- ing to (learn at test time): Runs with expressive hidden states. arXiv preprint 2rXiv:2407.04620, 2024.
Xu, K., Hu, W., Leskovee,, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https:// openreview net / wwwumoorrddaareee GyGs 61A5Km.
Suri. S. and Vassilvitskii, S. Counting triangles and the curse of the last reducer. In Proceedings of the 20th International Conference on World Wide Web, WWW '11,
Yang, S., Wang, B., Shen, Y., Panda, R., and Kim, Y. Gated linear attention transformers with hardware-efficicnt train- ing. In Forty-first International Conference on Machine Learning, 2024. URL httpt: https:://pperreeeeew wpwprevieeeeeeeeeeeeeeeeeeeoeeee .ne//
pp. 607-614, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 978 17834333363. doi: 10. 1145/1963405 1955/199334055116499 URL https: : org/
Ychudai, G., Kaplan, H.,, Ghandeharioun, A.,
Geva, M., and Globerson, A. When can transformers count to n?, 2024. URL https:tp///// http///xxivv.rr/ org. www.oo////////////oo///oooo/eae/ aa////b/////400 /2407 111611660
Tay, Y., Dehghani, M., Bahri, D., and Metzler, D. Efficient transformers: A survey. ACM Computing Surveys, 55(6): 1-28, 2022.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
Tönshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Walking out of the Weisfeiler Leman hierarchy: Graph learning be- yond message passing. Transactions Machine Learn- ing Research, 2023. ISSN 2835-8856. URL https: //openreview net/ / forum? weeiiiiigggnnnnenneee
Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., and Leskovec, J. Hierarchical graph representation learning with differentiable pooling. Advances in neural informa- tion processing systems, 31, 2018.
Vaswani, A., Shazeer, N. M., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L.,, and Polosukhin, I. Attention all you need. In Neural Information Process- ing Systems, 2017.
Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Al- berti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q. Yang, L., et al. Big bird: Transformers for longer se- quences, Advances in neural information processing systems, 33:17283-17297 2020.
Velickovic, P. Cucurull, G., Casanova, A., Romero, A., Lio', P., and Bengio, Y. Graph attention networks. ArXiv, abs/1710. 10903, 2017.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018. URL htttps://ppezeee http://ppppeeeeeeee/e//e net//frun? i ddr.JXMpikC..
Zhang, 7.,, Bu, J., Ester, M., Zhang, J., Yao, C., Yu, Z.,, and Wang, C. Hierarchical graph pooling with structure learning. arXiv preprint 19Xiv:1911.05990 2019.
14

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Tokenization
Theoretical/ Eexprrmmntaa Results
Enhancements
Role: Translate the graph into a set of sequence.
Local Tasks
Subgraph Tolenstation
HAC Clustering:
Node Tokenization: Treats the greph aequenoe noder, soken node.
BFS and DFS on the HAC lzee provide both aubgraph pode tolsenzzation!
Global Taaks
Node Takenisation
Subgraph I'olenisation: Treatt the graph as set of requeecess Each Teken is subgraph
Local Encoding
Ordered Tasks
Sequesce
* MoT:
Models
tokenination allows
Role: Allows the model to learn local dependencies by escoding tokens.
us to adaptively use different encoding for each mode.
Connectivity Tasks
Transformera
Global Encoding
Allows model learn global characteriticc and long range dependescies.
Role:
Counting
Recurrent Modals
*
Hybrid Bacoders:
Tasks
Trannformers and recurrent models complementt So we use bothl
Globall encoder is sequence model (e.g. RNN, Transfommes, etc.)
Complex
Tranuformet
Tasks
Modela
Figure 3: Overview of Graph Sequence Model (GSM). GSM Consists of three stages: (1) Tokenization, (2) Local Encoding, and (3) Global Encoding. We provide foundation for strengths and weaknesses of different tokenizations and sequence models. Finally, we present three methods enhance the power of GSMs.
A. Backgrounds
A.1. Graph Transformers
The Transformer architecture (Vaswani al., 2017), consists of sequential chain of layers, each layer being composed of two primary sub-layers: multi-head attention mechanism and fully-connected feed forward network. These layers arranged alternately to form the backbone of the model. Let G be graph with node feature matrix X E Rexdd_
In each layer > 0 of a graph Transformers, given node feature matrix X (f) E Raxd a single attention head computes the following:
QK Vdl
()) Softmax
V,
(4)
where the Softmax() is applied row-wise, dy denotes the feature dimension of the query (Q) and key (K) matrices, with ( = X. The matrices Q K, and V are the result projecting ((!) linearly,
Q = x K = x"0 and V==x
using three matrices Wo. WK E Raxd4 and Wv V E Rdxd where optional bias terms omitted for clarity. This attention mechanism forms the foundation of the Transformer architecture (also referred as non-causal Transformers or Softmax Transformers throughout this work while causal Transformers refers to use of causal masking in attention). The extension to multi-head attention, where multiple attention heads operate in parallel, is standard and straightforward. Equation 4 fails to take into account the graph topology, leading to the development of various Positional Encoding (PE) and Structural Encoding (SE) methods aimed at integrating essential structural information into Graph Transformers (GTss. Notably, several approaches have adopted the top-k Laplacian eigenpairs as node PEs, despite the substantial computational demands involved resolving the sign ambiguity of Laplacian eigenvectors. Likewise, SE. methods face considerable computational challenges in determining the distances between all node pairs or in the sampling of graph substructures. Moreover, the standard attention mechanism in Equation 4 generates dense attention matrix, leading to quadratic complexity with respect to the number of nodes. Recent innovations in Graph Transformers (GTs) have introduced scalable models by linearizing the attention matrix and eliminating the need for PE/SE. However, these models have not been extensively analyzed for their practical expressiveness and might underperform compared to the state-of-the-art Graph Neural Networks (GNNs).
A.2. Recurrent Models
Recurrent Neural Networks (RNNs) are particularly adept at handling sequential data thanks to their inherent capability to maintain an internal memory state. This allows RNNs to preserve contextual information from previous inputs within a sequence, making them ideal for tasks such as language modeling, time-series prediction, and speech recognition.
Specifically, at each discrete time step 1, the standard RNN processes a vector X; E TR. along with the previous step's
15

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
hidden state h₂-1 RR produce an output vector Or E Ro and update the hidden state to h2 R The hidden state serves as the network's memory, retaining information about the past inputs it has encountered. This dynamic memory capability allows RNNs to process sequences of varying lengths. Formally, the updates can be described as follows:
h, = o (W Na + Wanh + ba).
(5) where WA E R is the weight matrix responsible for processing model inputs into hidden states, WAr E RNNN represents the recurrent connections between hidden states, and Wor E ROxN is used to generate outputs derived from hidden states. The biases by E R and b, E TRO along with the hyperbolic tangent activation function tanh, introduce non-linearity to the model. In essence, RNNs are nonlinear recurrent models that effectively capture temporal patterns by harnessing the historical knowledge stored in hidden states.
O, = Woth + +b,,
In our theoretical results, however, we refer to recurrent model that has general recurrent formula to make the use of the theoretical results to a broader context. That is, we define a recurrent model as:
h; = f
(6)
0g = g(h,, #x):
(7)
where f and g are arbitrary functions. As an illustrative example, in Equation 5, we have:
[(h-11 oWWnnoWn Xt + Wish + by), g(h, 21) = Woth + bb.
(8)
(9)
A.3. Hierarchical Affinity Clustering (HAC) Algorithm
Hierarchical Affinity Clustering (HAC) (Bateni et al., 2017) is a powerful algorithm used to group data points based on their similarity or affinity, often represented by a distance measure such as Fuclidean distance or cosine similarity. HAC organizes data in a hierarchical structure, either through an agglomerative (bottom-up) process, where each data point starts as its own cluster and the closest clusters are progressively merged, or a divisive (top-down) process, which begins with all data points in a single cluster that is repeatedly split. The result of the clustering process can be visualized using a dendrogram, showcasing the nested relationships between clusters at different levels of similarity.
Finding the affinity clustering of a given graph G is closely tied to the task of identifying its Minimum Spanning Tree (MST). In fact, the information encoded in the MST of G is enough to determine its affinity clustering, Consequently, once the MST computed, the affinity clustering or single linkage can be obtained in a single step.
THEOREM 8. (Bateni et al., 2017) Let G = EV denote an arbitrary graph, and let G' =V, denote the minimum spanning tree of G. Rumning the affinity clustering algorithm on G produces the same clustering of V as running the algorithm on G'.
A.4. Mixture of Expert
In this paper, inspired by the idea of Mixture of Expert (MoE), we present Mixture of Tokenization (MoT). In Section F. we show that there is not a single type of tokenization that works best in all the cases. We further experimentally observe the same in Section 5.2. To this end, we suggest using a Mixture of Tokenization (MoT) technique, where we allow each node to use a tokenization that best describe its position based on the task. For example, one node might be better to be represented by itself (along with a positional encoding) since its neighborhood extremely noisy. At the same time, another node might be better be represented by its neighbors as there is strong homophily in that area of the graph. Let 7 be the list of different tokenizers, we use discrete router that choose top-2 tokenizations from T for each node. We then concatenate the encodings of these tokenizers to obtain the final encoding for the global encoding step. That is, given T and X as the input, we use a linear router with learnable weight W,, such that:
= a (XW+),
(10)
I = Top-2 (ST) P = hot-hot (1),
(11)
(12)
where (-) is non-linearity, Top-2(.) returns the index two rows with largest values, and one-hot(.) returns the one-hot encoding of the indices. These weights are learned in an end-to-end manner along with the other parameters in the model.
16

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
B. Related Work
Graph Neural Networks and Graph Transformers. utilize different approaches for processing graph data. GNNs typically employ a pesssag-ppassing mechanism that collects and synthesizes information from adjacent nodes into up- dated node representations (Kipf & Welling, 2016; Xu et al., 2019; Velickovic al., 2017). Despite their utility, these models exhibit limitations in expressiveness, equivalent to that of the 1-WL test, traditional algorithm for testing graph isomorphism (Morris et al., 2019; Xu et al., 2019; Loukas, 2019). They also encounter challenges like over-smoothing and over-squashing, and struggle with capturing long-range dependencies (Alon & Yahav, 2021; Dwivedi et al., 2022a). In contrast, Graph Transformers make use of an attention mechanism (Dwivedi & Bresson, 2020; Kim et al., 2022; Kreuzer et al., 2021) that enables attention to all nodes within a graph. Since utilizing full attention can obscure graph topology and render nodes non-distinguishable, numerous studies have concentrated on ereating effective node encodings such as Laplacian positional encodings (Dwivedi et al., 2023; 2021; Maskey et al., 2022; Huang et al., 2023; Wang al., 2022), shortest path distance/random walk distance (Ying et al., 2021; Li et al., 2020; Perozzi et al., 2014), among others. Addition- ally, some approaches merge Message Passing Neural Networks (MPNNs) with full attention capabilities (Rampášek et al., 2022; Chen et al., 2022). However, this full attention model scales quadratically with the size of the graph. To mitigate this complexity, certain studies have applied general linear attention techniques to Graph Transformers (Choromanski et al., 2020a; Rampášck et al.. 2022), along with other specific strategies intended to optimize performance (Perozzi et al., 2024; Sanford et al., 2024b; Wu et al., 2022). Also, several studies suggest the use of hierarchical pooling such as the work of Ying et al. (2018), Zhang et al. (2019). These works are different from our tokenization as our tokenization is based on HAC algorithm.
Sequence Models for Graphs. Efforts to integrate State Space Models (SSMs) into graph processing have led to innovative approaches in graph Transformers, shifting from traditional attention mechanisms to SSM applications. Initially, these methods tokenize graphs, which then allows for the application of any SSM-inspired model to process the data. In one approach for tokenization (Wang et al., 2024), the nodes are ordered into sequences according to their degrees, and Mamba (Gu & Dao, 2023)is then applied. Due to the common occurrence of nodes with identical degrees, it becomes necessary to randomly permute these sequences during training. which results in a model that lacks permutation equivariance with respect to the reordering of node indices. Another variant (Behrouz & Hashemi, 2024), constructs sequences by extracting neighborhoods up to M hops from a root node, treating each hop as a distinct token, and applying Mamba to model the root node's 's representation. This method, however, is computationally intensive as it requires pre-processing each neighborhood token with a Graph Neural Network (GNN) before applying Mamba. Additionally, the final layer of this model also applies Mamba to nodes arranged by their degree, preserving the issue of non non-permutation equivariance. Graph State Space Convolution (GSSC) (Huang et al., 2024), leverage global permutation -qquivaionn set aggregation and factorizable graph kernels that rely on relative node distances as the convolution kernels. Recent advancements have been made in extending SSM-based models to accommodate temporal graphs, introducing two variants known as DyG-Mamba one (Ding et al., 2024; Li et al., 2024), each integrating the Mamba model with GNN encoders. Using our framework, future research can incorporate more complex sequence models (Behrouz et al., 2024; 2025b; Karami & Mirrokni, 2025; Peng et al., 2023) to capture long-range dependencies.
C. Special Instances of GSMs
Table 7 illustrates that several well-known methods for learning on graphs are special instances of the Graph Sequence Model (GSM) framework, highlighting its universality. GSM consists of three stages: (1) Tokenization, (2) Local Encoding, and (3) Global Encoding. In this section, we demonstrate how GSM can handle each of these models based on these three stages. We categorize the existing architectures into four general families: Traditional Methods, Graph Transformers, Non-MPNN GNNs, and Recurrent-based Models. For each representative model within these families, we show how it can be formalized within the GSM pipeline.
REMARK (TRADITIONAL. METHODS). DeepWalk (Perozzi et al., 2014) and Node2Vec (Grover Leskovee, 2016) can be formulated as GSMs.
(GRAPH TRANSFORMERS) Most popular GTs, including GraphGPS (Rampášek et al., 2022), Ex- phormer (Shirzad et al., 2023), GOAT (Kong et al., 2023), NAGphormer (Chen et al., 2023), SubGraphormer (Bar-Shalom el al., 2023), GPS++ (Masters et al., 2023), Nodeformer (Wu et al., 2022), TokenGT (Kim et al., 2022), Graphormer ( (Ying et al., 2021),, Coarformer (Kuang et al., 2021), and SAN (Kreuzer et al., 2021), I), can be formulated as GSMs.
REMARK 2
REMARK 3. (NON-MPNN GNNs). Several popular non-MPNN methods for learning on graphs, including
17

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
Table 7: How are different models special instances of GSM framework
Method
Tokenization
Local Encoding
Global Encoding
DeepWalk (2014)
Random Walk
IDENTITY()
SkipGram
2 Order
Node2Vec (2016)
IDENTITY()
SkipGram
Random Walk
GraphTransformn (2020)
Node
IDENTITY()
Transformer
GraphGPS (2022)
Node
IDENTITY()
Transformer
NodeFormer (2022)
Node
GUMBEL-SOFTMAXX)
Transformer
METIS Clustering
Graph-Vi ViT (2023)
GCN(.)
VIT
(Patching)
Exphormer (2023)
Node
IDENTITY()
Sparse Transformer
CRaWI (2023)
Random Walk
ID Convolutions
MLP(.)
NAGphormer (2023)
k-hop neighborhoods
GCN()
Transformer
SP-MPNNs (2022)
k-hop neighborhoods
IDENTITY()
GIN()
GRED (2023)
k-hop neighborhood
MLP()
RNN()
S4G (2024)
k-hop neighborhood
IDENTITY()
S4(.
Union Random Walks
Graph Mamba (2024)
GATED-GON()
Bi-Mamba(.)
(With varying length)
18

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
CRaWl (Tönshoff et al., 2023), Graph-MLPMizer and Graph-ViT ViT (He al., 2023) can be formulated GSMs.
REMARK 4 (RECURRENT-BASED MODELS). Recent graph learning methods based modern recurrent models, including Graph Mamba (Behrouz, & Hashemi, 2024), GRED (Ding et al., 2023), and S4G (Song et al., 2024) can be formulated as GSMs.
D. Proofs of Theoretical Results
Note that the proof of other theorems are in Appendix E and Appendix F,
D.I. Color Counting
THEOREM Let C be the number of colors, and m be the width of a recurrent model, the recurrent model can count the number of nodes with each specific color iff m 2 C.
Proof. We consider linear recurrent models (the same process be done by any non-linear recurrent models):
ht Ah4-1 Bx,
(13)
Ch+
(14)
We let ze (input features) be the one-hot encoding of colors that say what is the color of this input. Using B = I and A = I and ho 0, and if mC, then i-th channel in h, is responsible to count i-th color. For input with color its input
feature is
where only the i-th channel and others are 0, and so we have:
h4 = The 1 +
(15)
which means hıj h for + i and he; = h4-1 This shows recurren models with m 2 C can count.
D.2. Representational Collapse in State Space Models
THEOREM 10. For any let A(k, (1 - )1 _
1)} and be the number of layers. For any <, n,
(L)
the gradient norm of the HiPPO operator for the output of layer L at time n + 1 (i.e., y yoth) with respect to input at time i (i.e., x:) satisfies:
i y Yutll <
1
cLL
E...
11 1,k1) II A (ke
1, A(ka 1,
I C(L)
x;
ki2t kz2kL-1
t=2
Proof. We use the recurrent formulation of state space models:
h Ah4-1 + Bx,
(16)
y: Ch+-
(17)
Based on this formulation, we take the gradient
||
0 we have: 9x.
i y
yynt1
(2)
11-
A
A
)
1
A
(1-
(1-
i+1)
A B
(18)
8 x;
n
n1
n
i
19

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Next, we need how using more layers affect this gradient. Let L be the layer of interest, similar the above, since the output of the (T. 1- layer is the input of L-thh layer, then we have:
i n+
1 A)
(r r n
A 11
(1
A
A
B i
1
(19)
0 y I-11
n1
.
i ++1
1
and so usign chain rule, we have:
y (L) ①
0y L-1 1 0yk. 0yk
(0)
(1)
Σ
(20)
i x;
yyk
(
y (t-1) 0x:
kg 2
kp2kz-3
R
2=
ki-1
Now, since we are using HIPPO (Gu et al., 2020), we can see that all I discussed by Gu et al. (2020) we have:
A for j n. n...., + are diagonizable and as
( n m)
(1 n ( ...
T
)
A
B
E
(1 (1- b ... (1
1
(21)
i
i+1
i
A(k,i)
which means there are Coow and Cup such that:
Coo x A(k, s -1(
n ( I 1- n (---1)
A
(1
A
B
S
Cup x A(k;;)).
(22)
i+1
Note that, it is simple to see:
1 ) ).....
1 }
A(k, i) = (1
(1
-
(23)
n
Using Equation 20 and the above bounds, we can conclude that:
L-1
i yy <11
1
clU
E.... A. 1,
II
Ake 1, 1, 1e - 1,
C(L)
(24)
x;
77
t=2
which completes the proof.
Similar to Barbero et al. (2024), who provide this upper bound for Softmax attention, next, we derive the upper-bound for linear attentions:
PROPOSITION 2. Given an input sequence XI...., Xn. let L be the number of layers, y be the i-th output in layer L.
then the sensitivity of of any linear attention satisfies:
Tyn Ox:
C(L)
Σ
Σ
nnk
(L-1)
O
(t-1) ky Ke kt
(25)
R1
1L2kL-1
2-2
where of,, (l((.." 200) P..))) Σ, o 1x .......))
weights of the attention.
This indicates that the discussions about representational collapse for full attention is also valid for linear transformers.
E. Comparisons between Transformers and Recurrent Models
The trade-offs computational cost and model capability between standard transformers and alternative architectures have been well studied theoretically and empirically. For instance, the capabilities of state space and sub-quadratic models fall short of transformers in copying context (Jelassi et al., 2024), multistep reasoning (Sanford et al., 2024b), and nearest
20

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
neighbor search (Alman & Song, 2023). Despite this, state space models learn certain tasks, such the compositions of permutations, in a more depth-efficient manner than transformers (Merrill al., 2024).
Because this paper designs graph sequence model architectures that employ state space models and other alternatives, it is useful to understand the trade-offss between these architectures and transformers at fundamental graph algorithmic tasks. In this section, we provide explicit the trade-offs between transformers and alternative (e.g. Mamba, Gu & Dao, 2023), linear attention (e.g. ForySke Kacham et al., 2024), and sparse attention (e.g. Longformer, Beltagy et al., 2020b). We discuss two particular particular architectural separations for graph connectivity tasks that illuminate broader trade-offs in architectural capability.
state space models
1. Section E. discusses the existence of more parameter-efffcieet transformers that solve graph connectivity than sub-quadratic architectures and state space models.
2. Section E.2 contrasts these results by showing that for certain category and presentation of graphs, recurrent models are more efficient in terms of both parameter count and computational time.
3. Section E.3 motivates hybrid models by suggesting instances of graph connectivity that are easily solved mixtures of RNN and transformer layers.
Taken together, these sections show that there is no one sequential modeling architecture that is strictly better for all graph algorithmic problems (or even all connectivity instances). Rather, the properties of the sequential representation of the graph matter great deal to the comparative successes of neural architectures. If the graph structure is captured primarily by the ordering of nodes, then state space models are likely to more easily parse that structure than softmax attentions. In contrast, transformers may offer advantages for graph algorithms that benefit from parallel computation applied inputs with complex structure. Hybrid models are best for inputs with both properties.
Throughout this section, we frame graph connectivity sequential modeling task with an edge tokenization. An undirected graph G = (V, E)) is provided as input G := Pa..... Pein and the target output is 1 if G' is connected and 0 if not. The theoretical results that follow are largely consequences of existing analyses about sequential reasoning tasks, such as k-hop induction heads (Sanford et al., 2024b) and the composition of permutations from the S group (Merrill et al., 2024).
E.1. Transformers Admit More Efficient Connectivity Solutions
The capabilities of standard softmax attention to efficiently compute graph connectivity for arbitrary graphs in edge tokenization were previously established. We provide these results as follows.
COROLLARY 4 (COROLLaRY 3.3 OF (SANFORD ET AL.., 2024B)). For any N and e (0, there exists a transformer with depth Ollog N) and embedding dimension ONN)) that determines whether any graph G = EV, with [VI,EE| s N is connected.
Transformers can thus solve graph connectivity with only O(N*) parameters. Moreover, the depth of this construction is asymptotically optimal among small-width transformers; see Corollary 3.5 of the same paper for more details.
On the other hand, alternative architectures cannot solve graph connectivity with such low-dimensional parameterization.
COROLLARY 5. Neural architectures of the following topologies that solve graph connectivity on all graphs G = (V, F) with VV, |E| < N satisfies the following:
1. multi-layer recurrent neural networks (RNN) have either depth L = 2(N2/8) or hidden state m = 51((N//4).
2. Transformers with dernel-based sub- sub-quadratic attention have either depth L = 1(N1/88 or mr = 51(N1/4) for embedding dimension m and kernel dimension r.
3. Transformers with locally masked attention units of radius and sparse long-range connections have either depth I = ((N1/8) or mr (2(2/A)) for embedding dimension m.
See Section 5 of (Sanford al., 2024b) for precise theoretical definitions of all models herein. We assume that all parameters and intermediate products use Olog bbit precision numbers.
21

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
As a result, these attempts to improve the quadratic computational bottleneck result in a lack of parameter-efficient connectivity solutions. All RNNs, kernel-based transformers with kernel dimension ( and all local transformers with window size = (NN//8 require at least (2(11/5) parameters. In contrast, since can take any constant positive value, transformers can be much smaller in parameter count for large N.
Proof. The proof of Corollary 5 derives from Corollaries 5.2-5.4 of (Sanford et al., 2024b) and rely on embedding well known communication task-the pointer chasing problem of (Nisan & Wigderson, 1993) -as graph connectivity instances.
In brief, the input to pointer chasing task is a (b, k) -layered graph G = (V1 U...U. V E U....UU Ex) with disjoint vertex layers V....., Va+1 with Vi = b and edge layers Ei...., Es where E is a perfect matching between Vj and V5+1- Fix some Uk+1 C VK+1 and some 01 E V/. The goal of the task is determine whether the unique vertex vx-1 E Vi+1 connected 01 in UR+1.
Let k (88 and b = ((V7/5). Consider embedding of the pointer-chasing task into any graph embedding of the form P.j ... Pe g) where Cbj+1..... Eb(++) encode all edges in F By Proposition E.3 and Corollaries 5.2-5.4 of (Sanford et al., 2024b), the pointer chasing task can only be solved on these embeddings by RNNs, kernel-based transformers, and locally masked transformers that satisfy the parameter scalings of Corollary 5.
remains to show that pointer chasing instances G can be converted into connectivity instances G' = (V, E') with [VI. = ((N) using a single round of computation without communication between inputs. We construct G' by adding (b) edges between ii and each vertex in V \. Uk+1 and between adjacent pairs of vertices in Uk+1- The ensures the bound on |E|| and can be done by performing element-wise computation on blank input tokens, since consider V1 and V k+1 fixed. Note that G' is connected if and only G' satisfies uk+1 Uk+1- Hence, solutions to graph connectivity imploy solutions to pointer chasing.
E.2. RNNs Admit More Efficient Connectivity Solutions on "Localized" Graphs
In contrast, the benefits of RNNs and state space models are pronounced on graph connectivity instances presented as token sequences that embed graph structure carefully in their ordering. (In some cases, graphs of this form may be produced by the HAC tokenization method of Section 4.1.) We define a notion of locality for an edge embedding and show that this induces easy embeddings for RNNs but not for transformers.
Let the node locality of an edge embedding Pe....., Peigi of a graph G = (V, denote the maximum window size needed to contain all edges that adjoin each node. That is, we say that G has node locality if
DEFINITION 2.
argminfer::vee)) u veei)) Sk.
max vEV
arg max((sx : uuu.eeee Eeee - arg
We show that graphs with bounded node locality admit time- and parameter-efffiieent RNN solutions.
THEOREM 11. There exists a single-pass RNN with hidden state (kk) that determines whether edge embedding with node locality at most ls reflects connected graph.
Proof. We first define the desired hidden state of the RNN, hy for any E [[E]]. It will naturally follow that an RNN that simulates a "last-in first-out" queue that stores edges can compute these hidden states with multi-layer perceptron with (k) parameters.
For each i E [[8]], denote e;- (u: of) and let G denote the subgraph of G containing edges ei- 6 and vertices 1/ k. 22 11-111....... ui uf. Let Gh2 denote the subgraph with edges fi....,eikk-1 We let
h = (G az ki.k...., b,),,
where
a4 E (0, }} denotes whether all edges in G are connected to some edge in C/; and
bg E [k] denotes the index of the connected component that edge e; belongs to with respect to G2 U GJ; that is by bi.., then there exists path connecting e, and ep among the edges C1, c1,...: Pi-
22

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
We argue inductively that each h can be constructed from h4. At initialization, we set 01 and bj 1.
G can be trivially constructed from G and e, by "forgetting" ci-k-1.
Let a, 0 if and only if (1) a;-1 0 or (2) k is unique among b²=1, For (1), if some edge in G <i- is not connected to G locality demands that is also not connected to G For (2), since 6;-k-1 1 is not connected to any of ki-ko.... - via G U G
and cannot share an edge with e, it is thus disconnected C.
If e; adjoins any of ei. 6i-1, we update the b/ 's to reflect the new clusters.
By induction, we determine that haa can be constructed as desired. We conclude by noting that G is connected if d|lp = 1 and -
In the case when k = O1), there exists constant-size RNN that solves graph connectivity on such graph instances.
In contrast, no constant-size transformer that solves the task exists. We prove this by a reduction to the conditional hardness of solving NC NC1 complete problems with constant depth transformers (see e.g. Merrill & Sabharwal, 2023).
THEOREM 12. Unless NC TCO, any log-precision transformer that solves graph connectivity on edge embeddings for graphs = (V, E) with |E| S N with node locality 12 requires either depth w1) or width Nw(1),
Proof. This proof is a consequence of Corollary 1.1 (Merrill Sabharwal, 2023), which establishes that all log-precision constant-depth transformers can be simulated by circuits in TC
Consider the task of composing permutations from the symmetric group of cardinality 5, S.-- That is, given 01...., On Sg. compute o,
Ø1- This task is NC' ccompeete and is widely believed not belong to TC".
If we show that this Sş composition task can be solved by evaluating the connectivity of ((1) graphs with node locality 12, then we can prove that graph connectivity on these instances is hard for constant-depth transformers. We first consider the subtask of determining whether (o,, .... 01) = t for some s, t E [5].
Given a sequence of permutations 01,...,, and some 8, t, we define graph = (V, F)) with V = [6n + 3] and edges 46n43 e.....:
E' as follows:
We establish a path from node to node 6n + (o,, .... o (1) for each E [5]. For every [n] and E [5). let
eb(r-1)+z = {6(i - 1) + + + (t))
We create a path from s to Let eg = {s, 6), eoi = 16i, 6(1 + 1)} for E [n - 1], and cGn = {6n,t].
Let 66n+1, +2, 46n+3 connect the four nodes 6(i - 1) + where & * t.
Thus, the graph is connected iff (an o... 01) * l. Observe that each node appears exclusively in edges within a window of size 12. Thus, this is an instance of graph connectivity with node locality 12.
Suppose there existed a constant-depht transformer with polynomial width that solves connectivity with constant node locality. Then, we could solve the 5 composition task constant depth by constructing graphs for all 25 (s, 1) pairs and evaluating the connectivity of each.
E.3. Motivating Hybrid RNN-Transforme Models with Connectivity Instances
In the preceding sections, we demonstrated that different instances of the graph connectivity task highlight the parametric advantages of both softmax transformers and recurrent neural networks. Transformers perform best in worst-case instances, where their logarithmie-depth dependence is more favorable than the polynomial size lower bound for RNNs. In contrast, RNNs are superior for graphs whose input edge encodings reflect a highly local structure.
A natural follow-up question asks whether there are any intermediate instances where the hybrid of Section 4.2 perform better than each component in isolation. In this section, we provide examples of those instances by considering a hybridization of worst case graphs and graphs with node locality and show that those instances are best suited for hybrid models. We first introduce this family of graphs by construction.
models
23

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
DEFINITION 3. For some n, k;, and we define a k-local (n,n') na)nn''oooooddd graph as any graph G (V, E) with [E| n22m' and edge embedding Pet.--.. PajEs satisfying the following conditions.
n')
1. There exists a "kernel graph" G. = (V,,E.) with [VG] = n. and "super-edge graphs"
G = (fu1, U Vol,e2 E2y,22)
for each "super-node" pair (11, v2) E V? with [m n'.
2. Each super-edge graph Go has the property that (a) if (U1, U2) E., then G is connected; and (b) if (v1, E., then Guy has two connected components, one containing and one with o2.
3. Each super-edge graph Gus has an n' -tokn edge encoding Pen that satisfies node locality
4. G EV has nodes and edges satisfying
Ü
Ü Evi V1.02EV2
= V.Ù
Venes
and
E
For any ordering (oi, u)).......... (uf ug²) over super-node pairs V?, the edge encoding of G
P PE "I .8²
Note that G is connected if and only if G. is connected. However, the kemel graph G. is not immediately apparent from the input edge encoding, since identifying whether any (2),0)) E, requires determining the connectivity of Gu This property motivates a two phase approach for hybrid architecture:
An RNN determines the connectivity of each G.y.z subgraph using the model of Theorem 11.
A transformer determines the connectivity of G..
The capabilities of this approach is summaried by the following corollary of Theorem 11 and Corollary 4.
COROLLARY 6. There exists a hybrid RNN-transformer model that solves graph connectivity on k-local (n, n' )-fcctored graphs that uses single RNN layer of hidden dimension (lk) and Ollo((n) transformer layers of embedding dimension (nz)).
Let N n'nn' denote the total number of edges such graph. Critically, this has dependence the parameter n', excepting the fact that the model will require bit-precision 22log N). In the setting where is small (but still non-negligible), we can demonstrate a substantial parameter count gap comparison to the best known constructions of both transformers and RNNs.
For example, let A: = (11) and n O(exp(Vlog N)).
Because these diameter of the graph may be as large as O(n n') O exp( (op(voog_. N)), a standard transformer is only known to solve the task using O (log N) layers and O(Ne) width.
Even if RNN successfully determine G. in single pass, the task of determining whether whether G. is connected requires either depth 18) 1(exp( N /)) or width (2(n2/44 [(exp(( (loooooog N N/4)).
In contrast, a hybrid RNN-transformer model can solve the task with depth O n) OV N) and width O(exp(e/log N)).
While the definition of k-locaa (n, factored graphs is somewhat contrived, they represent a formalization graphs whose edge embeddings are "nearly local," but which require some analysis global structure. Graphs with such properties are likely be produced by clustering-bant sequencing approaches, such Hierarchical Affinity Clustering.
24

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
F. Advantages and Disadvantages of Local Encoding
F.I Choosing the Right Tokenizer: Node, Edge, or Subgraph
While so far we have compared different sequence models for use in Global Encoding stage, one critical question remains: What type of tokenization is the best? In this section, we show that there is no universally best tokenization, and depending on the task, the best tokenizer is different. First, we start with the task of finding the length of the shortest path, and show that GSMs more parameter efficient when using subgraph tokenizer. This is an important task in graph learning, as awareness of the shortest path can enhance the power of the model (Abboud et al., 2022).
THEOREM 13. There exists a GSM with subgraph tokenizer and I-layer Transformer as its global encoder with width m O (log dG) and precision p O (log de) that performs the above shortest path task for all input graphs of of (V, E) with diameter up to de. Using node tokenizer, the Transformer must have at least width = O (log (Vl) and precision O (log) VV).
Next, we focus on motif counting (e.g., triangles), which is a well established graph task.
THEOREM 14. For any fixed subgraph H of diameter at most k. there exists k-hop local encoding Lhoccal and single- layer Transformer f of constant width such that J a &Local counts the number of occurrences of H in any input graph G.
We discuss theoretical trade-offs of the k-hop local embedding introduced in Section 2.2. Concretely, we show that k-hop local embeddings offer simple solutions to subgraph counting problems that are more parameter-efficient than known transformer constructions. In contrast, these embeddings offer no asymptotic benefits on hard instances of graph connectivity. Like the preceding section, the results herein are largely applications of prior theoretical results on transformer capabilities and limitations.
F22 Local Encodings Efficiently Count Subgraphs
Computing the number of small subgraphs--eppccially triangles or other cliques- is well established graph algorithmic task. Triangle counting was included fundamental graph reasoning problem in the GraphQA benchmark of Fatemi al. (2023), and the ability solve triangle counting with transformers with edge embeddings was investigated by Sanford et al. (2024a). While those results successfully converted existing parallel algorithms into transformer constructions, each construction had substantial polynomial dependency on the size of the input graph. In contrast, pairing local encodings with transformers enables easy counting of not only triangle counting but also any bounded-diamete subgraph counting task.
THEOREM 15.
For any fixed subgraph H of diameter at most k. there exists a k-hop local encoding &Local and a single-layer transformer f of constant width such that f @Local counts the number of occurrences of H in any input graph G.
Proof. We set the local encoding such that &Local (G); includes a normalized count the number of H subgraphs in the k-hop subgraph including node i:
#
Σ
1 ssubgraph of G(H with vertices V is isomorphic to H),
ZH
(y 1 ieV'
where [H] is the number of nodes in and Z is a normalization term set to ensure double-counting does not occur. (For example, if H is the triangular graph, let Zh = 3 to reflect the fact that a triangular subgraph {i1, i2, ig} will be counted thrice, in $ 1/2 s
It remains to provide a transformer that computes Σ ff This can be implemented by augmenting a single-layer masked attention unit that solves counting to compute sums by including the s terms in the value embeddings. (See e.g. the counting construction Proposition 5.3 of Yehudai et al. (2024).)
In contrast, all known transformer constructions without h-p encodings of even triangle counting tasks have unfavorable width or depth scalings on the size of the graph. These constructions are generated by simulating algorithms in the Massively Parallel Computation (MPC) model of Karloff et al. (2010) with transformers via Theorem of Sanford et al. (2024a). We
25

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
provide the architectural scalings of the resulting transformers for several MPC algorithms below. In the following regimes, there exist transformer that solves triangle counting for constant >> O:
Depth (11) and embedding dimension (((E)1/2+() the edge encoding setting (Suri & Vassilvitskii, 2011);
Depth ((VV)) and embedding dimension (((V['=)) in the node encoding setting (Chu & Cheng, 201 1).
Depth (log log El). embedding dimension (( and ((VV)-IE)) extra blank tokens in the edge encoding setting (Biswas et al., 2022).
All of these have much more dramatic model size scalings as a function of [E| and [V] than the local encoding construction in Theorem 15. While is unknown whether these represent the optimal solutions to subgraph counting with edge and node encodings, the fact that these are the state-of-the-art theoretical results indicates that local encoding substantially aids with tasks that involve aggregating local structural information.
E33 Local Encodings Offer No Improvement for Worst-Case Connectivity
In contrast, the limitations of local encodings are apparent in the analysis of worst-case graph connectivity, We show that k-hop local encodings offer no asymptotic improvements in graph connectivity parameter complexity over the construction of Corollary 4. We generalize Corollary 3.5 of Sanford et al. 22024b-whieh establishes that sub-logarithmic-dppt polynomial-width transformers cannot solve graph connectivity if the well-known "one-cyclee versus two-cycle" conjecture (see, e.g., Ghaffari et al., 2019) holds.
COROLLARY 7. Suppose any MPC algorithm with polynomial global memory and sub-linear local memory that distin- guishes cycle graph of size n. from two cycle graphs of size 2/2 in the edge encoding uses Mloog rounds of computation. Then, any transformer with k-hop local encoding (for k = ((NI=c) for some E (0, 1)) that solves graph connectivity on all graphs of size Vl, [B| & N requires either depth depth L = Mlog N) or width m = 22( N1-=)
This implies that using OkkN input tokens to represent graph offers representational benefits standard edge encoding, since the same logarithmic dependence persists. For large choices of ki the quadratic attention bottleneck causes the computational burden to scale with O(A²N' N2 log N) rather than O(N² log N).
Proof. The proof adapts the corresponding proof of Corollary 3.5 by Sanford et al. (2024b).
For N k. we let G = (V, E) be some instance of the one-cycle vs two-cycle identification task. We assume for simplicity that this is the directed variant of the task, where the cycles are directed. That is, we represent its input as a fixed ordering of edges e C|E1- Each vertex has degree exactly two.
We embed in an instance of one-cycle vs two-cycle identification G' = (V',E)) of size N by adding "phantom edges." We replace each vertex E with linear subgraph length & containing vertices v² ...., w E V and edges (v' vf+1) E E'. If (u, v) E F, then we add the edge (u o-)) E F.. Thus, if G' has cycle of length N if and only if G has eycle of length N.
Because all edges of the form (v', ( exist for all instances G', we can create an edge encoding of G' from an edge encoding of G using a single layer of attention with - I blank tokens, a positional encoding, and a constant embedding dimension. Likewise, we can compute the k-hop local encoding of G' using an additional attention layer with with N N blank tokens.
Since the existing hardness results for constructing transformers that solve the one-cycle versus two-cycle problem of size pertain to all transformers of depth o(log r.), width O(n--s), and number of blank tokens poly(n), the corollary follows as written for the case when A: = ((N-t))
G. Overview of GSM++
The overview of the GSM and GSM++ is illustrated Figure and Figure 1.
26

---

Best of Both Worlds; Advantages of Hybrid Graph Sequence Models
H. Time Complexity of GSM++
In this section, we analyze the time complexity of GSM++ and compare it with state-of-the-art efficient models. We let n be the number of tokens, dn be the dimension of the feature vectors (or PE), dsm be the first dimension of the SSM layers' output (or the input dimension of the transformer layer). C' be the number of channels. and B, be the batch size. Given the fact that the input of the transformer block has the dimension of d the complexity of the training for transformer block is O (d=))) The input of the SSM blocks has the dimension of the n x din and so given the fact that Mamba has a linear-time training (Gu & Dao, 2023), the training time for SSM layers is O (n x d Therefore, the training time cost of GSM++ is O (dh X n + ) which is linear with respect to the graph size n. For the BFS traverse, GSM++ (BFS), we have n = |V] and so the time complexity is O (dh, x |V| + d In the case of DFS traverse, nt is the number of tokens, which is at most log (IV)). Therefore, for GSM++ (DFS) the time complexity is O (de, x log (VV))V] | VV). which is sub-quadratic. In practice, log ([VI) < 11 and so one can argue GSM++ (DFS) also has a linear time complexity. Finally, note that for the MoT, we concatenate the outputs of two different tokenization and so requires a projection from 2 x din to da, which requires O (2dg,) additional parameters. In practice, dn z 100 and so this results in about 10,000 additional parameters, which is negligible.
dasm
I. Experimental Setup
Benchmark Tasks. The nature of the task can be understood to involve assigning unique color each class and subsequently counting the number of nodes within each class, effectively treating the count of nodes the number of nodes with specific assigned color. For example, in cases where two distinct colors are present, one might determine that there are 2000 red nodes and 1000 blue nodes. The objective of the task then becomes to provide a graph as input and generate an output in the form of a vector, where each entry corresponds to the number of nodes belonging to a particular class. This output vector enumerates the count of nodes for each class, reflecting the distribution of nodes across the different classes. We evaluate the empirical performance of our approach across a diverse set of graph datasets, focusing on both graph-level and node-level prediction tasks. Specifically, we conduct experiments on image-based graph datasets, including PascalVOC-SP, which exemplifies long-range dependencies with moderate complexity (21 classes), and COCO-SP SP, which presents more challenging long-range dependencies with 81 classes. Additionally, we include synthetic SBM datasets (PATTERN) and heterophilic graph datasets Goomnn-Empire, Minesweeper), which vary in difficulty, with 18 and 2 classes respectively.
Color-connectivty task. Four Color- Cone--Connettiitty datasets partitioned the nodes of graph into two groups: one half of the nodes was randomly assigned a color, such as red, while the remaining nodes were assigned blue. In this setup, the red nodes either form a single connected component or two disjoint components. The goal of the binary classification task is to distinguish between these two scenarios. The node colorings were produced by initiating two independent random walks, starting from two randomly selected nodes, to assign the red color.
GSMs Variants. As the sequence encoder in the global encoding stage, we use: (1) xLSTM (Beck et al., 2024), (2) TTT (Sun et al., 2024), (3) Mamba (Gu & Dao, 2023), (4) Mamba2 (Dao & Gu, 2024), (5) PolySketchFormer (Kacham et al., 2024), (6) Transformers (Vaswani et al., 2017). (7) GLA (Yang et al., 2024), and (8) Sparse attention (Beltagy et al., 2020a).
As the tokenization, we use: (1) Node (Rampášek et al., 2022), (2) Edge Node, (3) Edge, (4) k-hop Neighborhood (Chen et al., 2023), (5) Simple random walk (Kuang et al., 2021), (6) Multiple Random Walks (Behrouz & Hashemi, 2024), (7) HAC (this study), and (8) METIS (Karypis & Kumar, 1998)
Since the focus of our study is mostly on global encoding and tokenization, we use the same local encoding (GatedGCN) for all the cases to ensure a fair comparison.
Baselines. We compare our GSM++ with (1) MPNNs, e.g., MPNN (Gilmer et al., 20176), GCN (Kipf & Welling, 2016), GIN (Xu et al., 2019), GAT (Veličković et al., 2018), GraphSAGE (Hamilton et al., 2017). OrderedGNN (Song et al., 2023). IGNN (Hua et al., 2022), and Gated-GCN (Bresson & Laurent, 2017), (2) Random walk based method CRaWI (Tönshoff et al., 2023), (3) state-of-the-a GTs, e.g., SAN (Kreuzer et al., 2021), NAGphormer (Chen et al., 2023), Graph VIT (He et al., 2023), two variants of GPS (Rampāšek et al., 2022), GOAT (Kong et al., 2023), GRIT (Ma et al., 2023), and Exphormer (Shirzad et al., 2023), and (4) recurrent-based models: e.g., Graph Mamba (GMN) (Behrouz & Hashemi, 2024)
27

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Table Dataset Statistics.
Sctup
Dataset
#Graphs
Average #Nodes
Average #Bdges
#Class
Metric
Input Level
Task
Long-range Graph Benchmark (Dwivedi et al., 2022b)
COCO-SP
123,286
476.9
2693.7
81
Node Node Gruph Graph
Classification
Fl score
PascalVOC-SP
11,355
479,4
2710.5
21
Classification
Fl score
Peptides-Func
15,535
150.9
307.3
10
Classificution Regression
Averuge Precision
Peptides-
Peptides-Struct Struct
15,535
150.9
307.3
11 (regression)
Mean Absolute Error
GNN Benchmark (Dwivedi al., 2023)
Pattern
14,000
118.9
3,039.3
Node
Classification
Accuracy
MNIST
70,000
70.6
564.5
10
Graph
Classification
Accuracy
CIFARIO
60,000
117.6
9411
10
Graph
Classification
Accuracy
MulNet-Ting
5,000
1,410.3
2,859,9
Gruph
Classificution
Accuracy
Hetemphilic Benchmark (Platonov al., 20233
Roman-empire
22,662
32,927
Node
Classification
Accuracy
Amazon-ratings
24,492
93,050
Node
Classificution
Accuracy
Minesweeper
10,000
39,402
Node
Classification
ROC AUC:
Tolokers
11,758
519,000
Node
Classification
ROC AUC
Very Lurge Dutaset (Hu ul., 2020)
urXiv-aghn products-ogba
169,343
1,166,243
Node Node
Classificution Classification
Accuracy
2,449,029
61,859,140
Accuracy
Color-connectivy task (Rampášck Wolf, 2021)
C-C 16x16 grid
15,000
256
480
Node
Classification
Accuracy
C-C 32x32 grid
15,000
1,024
1,984
Node
Classification
Accuracy
Euroroad
15,000
1,174
1,417
Node
Classification
Accuracy
Minnesota 6,000
2,642
3,304
Classificution
Accuracy
and GRED (Ding et al., 2023).
L.1. Details of Datasets
The statistics of all the datasets are in Table 8. For additional details about the datasets, we refer to the Long-rane rangerange graph benchmark (Dwivedi et al., 2022b), GNN Benchmark (Dwivedi et al., 2023), Heterophilic Benchmark (Platonov et al., 2023), Open Graph Benchmark (Hu et al., 2020) and Color-connectivity task (Rampášek Wolf, 2021). When dealing with products-ogbn, we use local attentions instead of softmax attention (Deng al., 2024) to enhance the scalability.
1.2. Efficiency for Large Datasets
In this section, we compare the training time, memory usage, and performance of the variants of GSM++ with other efficient graph sequence models on large graphs. The results are reported in Table 9. With respect to scalability, all variants of GSM++ can scale these large graphs. With respect to the performance, GSM++ variants achieve all first three places (except the second place products-ogbn dataset), which shows the effectiveness of this architecture design.
These results further shows the effectiveness and efficiency of MoT approach. Since this method uses router, it is more memory efficient than GSM++ with BFS traverse, and it's training time is competitive with GSM++ with DFS traverse. Notably, these efficiency results are achieved byb GSM++ with MoT while ouperforms all the baselines in both datasets.
28

---

Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Table Efficiency evaluation large graphs. The first, second, and third results each metric are highlighted. OOM: memory,
GSM++
Model
GatedGCN
NAGphormer
GPS
Exphormer
GOAT
GRIT
GMN
BFS
DFS
MoT
urXiv-ogbn
Performance
0.7141
0.7013
OOM
0.7228
0.7196
OOM
0.7248
0.7297
0.7261
0.7301
Memory Usage (GB)
11.87
6.81
OOM
37.01
13.12
OOM
5.63
24.8
4.7
Training l'ime/Epoch (s)
1.94
5.96
0OM
2.15
8.69
OOM
1.78
2.33
1.95
4.16
products-ogbi
Performance Memory Usage (GB)
0.7329
OOM
OOM
0.8200
OOM
OOM
0.8071
0.8080
0.8213
11.13
10.04
OOM
OOM
12.06
OOM
OOM
38.14
9.15
11.96
Training Time//ppoch (s)
1.92
12.08
OOM
OOM
29.50
OOM
OOM
6.97
12.19
11.87
I.3. Efficiency HAC Tokenization
In this section, we evaluate the efficiency of the HAC tokenization and compare its computing time with other commonly used positional encodings (PEs) in the literature (Rampášek et al., 2022; Behrouz & Hashemi, 2024; Ma al., 2023). Please note that the construction of positional encoding one-time cost, which can be done as a preprocessing before training, and so cannot significantly affect the total training time. We compare the computing time of HAC (Bateni et al., 2017) with random-walk-basee walk-based PE (Behrouz & Hashemi, 2024), Laplacian-based (Rampášek et al., 2022), and Relative Random Walk PE (Ma et al., 2023). The results are reported Figure 4. HAC's computing time competitive with other PEs's and scales more smoothly with the number of nodes. That is, the main efficiency gain of HAC is when are dealing with large graphs. Furthermore, note that in practice, HAC is highly parallelizable and can scale to graphs with billions of nodes and trillion of edges in less than one hour (Bateni et al., 2017).
Time
Hir Saniaa
Lasft
10000
20000 Number of Nodes
30000 60000
Figure 4: The effect of number of nodes on the preprocessing time for the con- struction of positional encodings.
L.4. Comparison with Concurrent Studies
We further compare model with NeuralWalk (Chen al., 2025) and GRASS (Liao & Poczos, 2025). Since the contribution of these two works are orthogonal to ours and can also be used to further enhance GSM++, we use these techniques and report the results in Table 10.
Table 10: The results of concurrent models.
Model
Peptides-fune
PascalVOC-SP
COCO-SP
MNIST
PATTERN
GRASS
67.37
56.70
47.52
98.93
89.17
NeuralWalker
70.96
49.12
43.98
98.76
86.97
GSM++
71.82
49.33
48.25
90.08
29


Reviews:
[{"review_id": "ApzpvAdpa9", "reviewer": "Reviewer_pYLA", "summary": "This paper transforms graph data into sequential data through tokenization, global encoding, and local encoding, and applies GSM for graph learning. The paper also analyzes the strengths and weaknesses of different sequence models in handling various tasks. Furthermore, they enhance the model by proposing GSM++, which generates ordered sequences using the HAC algorithm and combines recursive models (e.g., Mamba) with Transformer models, balancing efficiency and sequential information preservation. Additionally, the author introduces MoT, allowing each node to select the most suitable tokenization method based on task requirements. Extensive experiments validate the effectiveness of different tokenization methods and sequence models, demonstrating the superior performance of GSM++ on multiple benchmark datasets.\n\n## update after review\nThe feeback has fulfill my concerns. I raised my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and constructive review. \n\n> *The ablation studies fail to sufficiently isolate and quantify the individual impacts of key contributions (HAC and MoT).*\n\n\nWe kindly want to bring to your consideration that the ablation for both HAC and MoT are already reported in the submission. In Table 4 (last line), while keeping other parts unchanged, we replace HAC tokenization with standard tokenization of GTs (i.e., node tokenization) and shows that HAC has the most contribution to the performance of GSM++ (please see lines 425 - 431). Regarding MoT, we have ablation studies in Table 3, 7, and 8 (last line of each), where we have GSM++ (MoT) variant, in which the only change is to replace the tokenization part with MoT. It improves the performance on all datasets.\n\nWe also go further and even perform ablation on other existing architectures of GPS and NAGPhormer frameworks and while keeping other parts unchanged, we replace their tokenization with HAC/MoT and show that these changes improve their performance (Table 4 rows 3, 4, 7 and 8). \n\nIn all these ablations, we isolate the individual impact of MoT and HAC and so we believe these experiments not only support the importance of HAC/MoT in our framework, but it shows their significance even when utilized in other frameworks.\n\n\n> *Scalability and concerns about BFS and DFS.*\n\nWhile we understand the concerns about computational cost, the HAC tree algorithm is a well-established clustering method known for its high parallelizability and efficiency, which is capable of scaling to graphs with billions of nodes and trillions of edges in less than an hour! Also, this clustering algorithm, similar to other positional encodings, is a one-time computation and can be done as the preprocessing step, ensuring that it does not impact runtime efficiency during model training. Following your suggestion and to fully address your concern, we compare the construction time of HAC with common positional encodings:\n\n\n| Graph Size | 10K |  20K | 30K|  40K | 60K |\n|-----------|-----------|-----------|-----------|-----------|-----------|\n| LapPE | 25 | 94 | 197 | 286  | 333 |\n| Random Walk | 103 | 217 | 329  |  447 | 709 |\n| HAC | 105 | 230 |  314 | 345  | 368 |\n\n\nPlease also note that our general approach can scale to larger graphs with millions of nodes, while most baselines can scale to at most tens or hundreds of thousand nodes. Here we report the results on large graphs of arXiv-ogbn and products-ogbn (We will add the full results in the final version of the paper): GSM++ achieves the best result while maintaining the best efficiency. In addition to GPS, several other baselines like Grit and GMN face OOM issues.\n\n\n|  | NAGPhormer  | Exphormer |  GOAT | GSM++ |\n|-----------|-----------|-----------|-----------|-----------|\n| arxiv |  70.13 | 72.28 |  71.96 | 72.61 |\n| Time |  5.96 |  2.15 |  8.16 | 1.95 |\n| product | 73.29 |  OOM | 82.00  | 82.13 |\n| Time | 12.08  | OOM  |  29.50 | 11.87 |\n\n\n> *Novelty and Contribution*\n\nIn addition to our novel graph learning method of GSM++ (where it achieves the best performance while maintaining the efficiency), one of the important aspects of our study is its novel theoretical contributions that help better understand sequence models in a wide range of graph tasks. We comprehensively discuss how different types of architectures can be useful for graph tasks and support our claims with both theoretical and experimental results. \n\n\n> *Introduction of both GSM and GSM++*\n\nWe appreciate the author highlighting ambiguity between GSM and GSM++. We intend to clarify in a final version of the paper that GSM is the name of our framework that unifies graph sequence models, while GSM++ is one of its variants supported based on our theoretical and practical findings. Therefore, we believe that GSM++ model complements all the discussions and intuitions that we build upon the GSM framework.", "claims_and_evidence": "Yes, but with limitations. While the paper is supported by extensive experimental results and theoretical proofs, the ablation studies fail to sufficiently isolate and quantify the individual impacts of key contributions (HAC and MoT). This creates uncertainty about their true significance in achieving the reported performance.", "methods_and_evaluation_criteria": "The methods generally make sense but have scalability concerns. The proposed subgraph partitioning method is practical for handling local/global graph properties, but the reliance on DFS/BFS for graph construction raises scalability issues for larger graphs due to their slow performance.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Similar to \"Claims And Evidence\", the experimental designs are generally sound but lack crucial ablation analysis. While the extensive experimental results demonstrate effectiveness, the failure to properly isolate the impacts of hybrid method/HAC/MoT through ablation studies weakens the validity of causal claims.", "relation_to_broader_scientific_literature": "The hierarchical global-local partitioning approach shows limited novelty as similar strategies have been explored in prior research. The integration of recursive models with Transformers builds effectively on existing work regarding combining sequential processing and global attention mechanisms.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "The concurrent introduction of GSM and GSM++ risks diluting the paper's focus. Consolidating these advancements into a single cohesive framework would strengthen the presentation.", "questions_for_authors": "1. Could you provide detailed runtime metrics for each experiment/task?\n\n2. Have you considered combining MPNN (local processing) with Transformer (global processing) given their comparable performance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DXeuqw5fcf", "reviewer": "Reviewer_wtrm", "summary": "The paper introduces a general Graph Sequence Model (GSM) framework aimed at systematically studying graph-based learning methods utilizing sequence models. It identifies core limitations in existing approaches, notably their inability to simultaneously capture local structures and long-range dependencies efficiently. To address these issues, the authors propose GSM++, a hybrid sequence model combining Transformers and State-Space Models (SSMs). GSM++ incorporates a novel tokenization strategy based on Hierarchical Affinity Clustering (HAC), using hierarchical clustering to produce meaningful node orderings. Additionally, a \"Mixture of Tokenization\" (MoT) is proposed to select the most suitable tokenization per node. The authors claim superior empirical performance and present theoretical arguments regarding the advantages of hybrid architectures.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and constructive review. \n\n> *Broad applicability*\n\nPlease see the response in our message to `Reviewer psEP`.\n\n> *The performance gain attributed to hybridization*\n\nPlease note that we follow the original benchmarks. We use 100K for MNIST and CIFAR, while using 500K parameters for all other cases. Therefore, the performance gains are not a result of more parameters.  Also, our ablation study in Table 4 shows the importance of hybrid models +1.3% performance gain, which is quite non-trivial in such benchmarks. The most important aspects of using hybrid models are in (1) efficiency: Please see our efficiency response to `Reviewer pYLA`. GSM++ achieves the best performance while maintaining the best efficiency; and (2) graph understanding tasks, where hybrid models improve the performance by +1.5% on average. \n \n\n> *Some recent baselines*\n\nWe would be happy to discuss these papers in our final version. For the purposes of evaluating the existing paper, we wish to note that  the source code for the GRASS paper was made public **after the ICML submission deadline**. Furthermore, both of the mentioned studies are recently published by ICLR 2025 (Jan 22 one day before ICML deadline). Therefore, we did not have the opportunity to make a formal comparison in our paper submission.\n\nIn addition, these works consider different goals than our own. While our focus has been on introducing new alternative graph learning architectures, GRASS proposes techniques (e.g., rewiring) aimed at enhancing existing models. Such techniques could also be applied to our architecture and may further improve its performance. \n\nRe-using the results in their original paper is not a fair comparison as they did not follow the standard range and use more than 500K parameters. Comparing their results with ours, even in the case that they use considerably more parameters, our GSM++ performs on par. For final version of the paper, we would be happy to include an extensive discussion about these papers.\n\nDue to space limit, we cannot include the results for an extensive list of baselines. But we have focused on a subset of SOTA models that have shown to outperform others. Please note that it's been uncommon to compare with all the baselines and usually a subset are chosen. The two studies mentioned by the reviewer also each compare with only one random-walk based model (we have Crawl and GMN, which is more than both)\n\n> *Choice of HAC*\n\nIn Fig 3, we have already justified the choice of HAC rigorously, and compared it with 4 different existing tokenizations, including random-walk. Also, our CraWL and GMN baselines are both random-walk based models. Also please see our provided scalability results in our response to `Reviewer pYLA`. The HAC algorithm is scalable to graphs with billions of nodes in less than an hour (see their original algorithm paper). Therefore, the real world applicability of our approach is very promising.  \n\n\n> *Theoretical work hinge on idealized settings*\n\nWhile the problems considered in our theoretical settings are more precisely defined and consistent than real-world noisy data, we would like to call attention to the fact that our theoretical results prove tight bounds for nearly identical tasks as the ones we investigate empirically. If there are any particular theoretical assumptions that trouble the reviewer, we are happy to have an extended conversation about why we made those assumptions and the feasibility of loosening them.  \n\n\n> *Ablation Study*\n\nOur comprehensive ablation study in Table 4 isolates the benefits of individual components. We also go further and add our contributions to existing frameworks like GPS and NAGPhormer and show even our contributions can improve other frameworks performance.\n\n\n> *The performance gains shown in many benchmarks are marginal*\n\nWe kindly bring to your attention that GSM++ achieves +1.9 performance gain on average and consistently outperforms SOTA baselines, which is not marginal and shows its applicability. \n\n\n> *Scalability and large graphs*\n\nPlease see our response to `Reviewer pYLA` for scalability of HAC and the results on large graphs. \n\n\n> *Fair Comparison*\n\nWe have re-used the original reported results by the paper. Also, for our own configuration we have followed the original configuration of the benchmarks. \n\n\n> *Novelty and Contribution*\n\nPlease note that in this paper, we present: (1) a unifying framework, (2) a novel tokenization, (3) a novel mixture tokenization technique, (4) a new positional encoding, (5) a new hybrid usage of sequence models, and (6) a rigorous theoretical analysis of graph sequence models. We ask that you consider the extent and novelty of our contributions in comparison to other recently published studies, which often include only a small share of these components.\n\n\n> *Complexity of the model*\n> *The use of the hybrid model*\n> *For datasets from LRGB*\n\nPlease see the response in our message to `Reviewer psEP`.", "claims_and_evidence": "Several claims, particularly those asserting the general superiority of GSM++ across a broad range of tasks, appear overstated. While GSM++ shows good empirical results on certain benchmarks, these results do not provide sufficient evidence of broad applicability, and crucial comparative evaluations are lacking. For instance, 1) the performance gain attributed to hybridization is not uniformly substantial, and it is not clear whether the gain comes from using additional parameters. 2) The number of parameters for GSM++ is not given, it is not clear whether the improved performance is brought by using larger models. 3) Some recent but highly relevant baselines are not compared to, such as NeuralWalker [Chen'25] and GRASS [Liao'25]. 4) For datasets from LRGB, the authors don't seem to follow the suggestions provided by [Tonshoff'23], leading to significantly worse performance than state-of-the-art methods.", "methods_and_evaluation_criteria": "The proposed hierarchical tokenization (HAC) method, while theoretically appealing, lacks rigorous experimental justification for its necessity over simpler alternatives, such as simple DFS or random walks. The evaluation primarily relies on synthetic and standard datasets, and there is insufficient discussion of real-world applicability or scalability. For instance, random walk-based tokenization used in NeuralWalker [Chen'25] seems to work better in most benchmark tasks.\n\nThe use of the hybrid model combining SSMs and transformers is motivated by the representational collapse of SSMs. However, this argument does not justify the choice of using a transformer. In fact, some cheaper layers seem to work as well as a transformer, e.g., a virtual node layer [Rosenbluth'24].", "theoretical_claims": "The theoretical results presented, although mathematically sound, often hinge on assumptions or idealized settings that may not translate effectively into practical scenarios. The provided theoretical insights, such as representational collapse and sensitivity analysis, are insightful but remain somewhat detached from practical implications.", "experimental_designs_or_analyses": "The experimental section has significant shortcomings. In addition to the issues that I mentioned in \"Claims and evidence\", there are some additional weaknesses that I will list here. 1) The paper lacks thorough ablation studies that isolate the benefits of individual components comprehensively. 2) The performance gains shown in many benchmarks are marginal, calling into question the practical significance of the proposed approach. 3) There is also no explicit discussion and evaluation about the scalability of GSM++. It is not clear whether GSM++ is scalable to very large graphs with millions of nodes.", "relation_to_broader_scientific_literature": "While the paper acknowledges relevant Transformer and recurrent neural network literature, it insufficiently relates its contributions to recent graph Transformer variations, random walk-based models, or hierarchical methods beyond HAC. For instance, random walk-based models are less discussed compared to other subgraph based models. There is a growing line of research using sequence models to encode random walks represented as sequences, such as CraWL and [Chen'25]. However, the presented paper doesn't properly relate its contributions to this line of research.", "essential_references_not_discussed": "Critical works on random walk-based models using sequence models are missing, such as NeuralWalker [Chen'25]. Works on hierarchical graph pooling methods, including DiffPool [Ying'18] and other pooling methods, are notably absent. Some recent baseline methods are not discussed and compared to, such as NeuralWalker [Chen'25] and GRASS [Liao'25].\n\n[Chen'25]: Learning Long Range Dependencies on Graphs via Random Walks, ICLR 2025.\n\n[Liao'25]: Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention, ICLR 2025.\n\n[Ying'18]: Hierarchical Graph Representation Learning with Differentiable Pooling, NeurIPS 2018.\n\n[Tonshoff'23]: Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark, TMLR 2024.\n\n[Rosenbluth'24]: Distinguished in uniform: Self-attention vs. virtual nodes, ICLR 2024.", "other_strengths_and_weaknesses": "### Strengths:\n- Provides an interesting theoretical angle on hybrid model performance.\n- Introduces a potentially useful framework (GSM).\n\n### Weaknesses:\n- Limited novelty due to incremental combinations of existing techniques.\n- Insufficient empirical validation. \n- Potential reproducibility issues due to missing details about model hyperparameters.\n- Lack of direct comparison with simpler, computationally cheaper methods. Lack of comparison with some recent but highly relevant baselines.\n- Potential scalability issues.", "other_comments_or_suggestions": "- A clearer discussion of computational complexity, particularly regarding scalability and practical runtime costs of HAC, is necessary.\n- L22: could the authors elaborate on the meaning of \"local structural bias\"? I don't think it's commonly known concept.\n- Figure 1 and 2 should be included in the main paper.\n\nTypos (not extensive as there are a lot of small typos):\n- L14: **the** tendency\n- L45: promising potential -> potential \n- L96: types **of** sequence models\n- L103: this advantages -> this advantage\n- L105: so the -> so that the\n- L97: Let $G=(V, E)$, be a graph -> Let $G=(V, E)$ be a graph\n- L282: can results -> can result\n- L410: GSM++ with **the** state-of-the-art methods", "questions_for_authors": "1. How does the HAC-based tokenization perform in terms of scalability and runtime efficiency on large-scale real-world graph datasets? And how about the full model?\n2. Can the authors empirically demonstrate the necessity and benefits of their hybrid model over purely Transformer-based or purely recurrent models more rigorously? How does it compare to other combinations such as SSM + Virtual node?\n3. How does GSM++ compare to recent highly relevant baseline methods, such as NeuralWalker [Chen'25] and GRASS [Liao'25]?\n4. Can the authors reevaluate GSM++ on LRGB using the better practice from [Tonshoff'23]?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uQFLFzmhTc", "reviewer": "Reviewer_psEP", "summary": "This paper introduces GSM++, a hybrid graph sequence model that combines Mamba (RNN) and Transformer architectures for graph learning. It leverages Hierarchical Affinity Clustering (HAC) for efficient graph tokenization and Hierarchical Positional Encoding (HPE) to enhance structural representations. Experimental results show GSM++ outperforms existing models on local and global graph tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and constructive review. We are also glad that the reviewer has found our work novel and effective.  \n\n> *Missing study*\n\nThank you for bringing this relevant paper to our attention. We will make sure to properly discuss this paper in the final version of our submission. \n\n\n> *Reproducibility and Code*\n\nFollowing your suggestion, we will provide the details of hyperparameters and will open source the code upon acceptance of the paper to further enhance the reproducibility of the experimental findings.\n\n\n---- \n---- \n----\n\nIn the next part, following the guideline, we reply to `Reviewer wtrm`'s comment.\n\n\n> *Broad applicability*\n\nWe want to kindly bring to your consideration that we have performed experimental results on 18 different datasets ranging 5 different benchmarks and diverse tasks ranging from node classification, graph classification/regression, shortest path, cycle check, triangle counting, etc. We kindly bring to your consideration that performing experiments in such diverse tasks has not often happened in recent studies. For example, the papers mentioned by the reviewer (both published in ICLR 2025), only consider a subset of our baselines, tasks, and datasets. \n\n\n> *For datasets from LRGB*\n\nFollowing your suggestion, we follow this study and tune hyperparameters for baselines and our model and will report the results in the final version of the paper. However, please note that: (1) Even using the reported results in this paper, our model outperforms all the baselines with a significant margin. Therefore, the main message of the paper will remain the same and won’t be changed. (2) using hyperparameter tuning will also improve the performance of our models, leading to even a bigger gap with baselines. \n\n\n> *Complexity of the model*\n\nPlease note that as mentioned above, HAC is a very scalable algorithm and one-time procedure. Our overall time complexity remains the same as other graph sequence models in theory, but in practice, GSM++ uses less memory and is faster. Please see our response to `Reviewer pYLA.`\n\n\n> *The use of the hybrid model*\n\nPlease note that we have provided theoretical justification that why SSMs suffer from representation collapse and why the use of full transformers can mitigate this. Therefore, we believe we fully support our claims and choices. We are not aware of an existing study that combines virtual nodes with SSMs to prevent this issue. If there is, we would be happy to discuss and compare. Please note that there are definitely more interesting ideas that might or might not work, which could be an interesting future work, but out of the scope of this paper. \n\nBy local structural bias, we mean understanding the structure around each node.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, it makes sense to use Accuracy to evaluate the classification performance.", "theoretical_claims": "Yes, the theoretical claims about the effectiveness are correct.", "experimental_designs_or_analyses": "The experiments and the result analysis are sound and extensive.", "relation_to_broader_scientific_literature": "This work proposes a novel tokenization based on the Hierarchical Affinity Clustering(HAC) tree. This idea is quite novel.", "essential_references_not_discussed": "In the text, the authors mentioned the over-smoothing issue in GNNs, and one recent study [1] on this issue is missing in the discussion.\n\n[1] \"SkipNode: On alleviating performance degradation for deep graph convolutional networks.\" IEEE Transactions on Knowledge and Data Engineering (2024).", "other_strengths_and_weaknesses": "**One More Weakness**: It would be better to provide the source code to improve the reproducibility of the experimental findings in this work.", "other_comments_or_suggestions": "None", "questions_for_authors": "Please refer to the issues mentioned above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a hybrid framework for applying sequence models to graph learning. The main concerns raised by the reviewers were: (1) potentially limited scalability, (2) limited technical novelty, (3) missing comparisons to recent state-of-the-art methods, and (4) an incomplete benchmark evaluation.

In the rebuttal, the authors provided clarifications regarding their contributions and addressed most of these concerns adequately by presenting additional results on scalability, new datasets, and comparisons to previously missing baselines. While some concerns remain—particularly regarding the scalability of the Transformer component and the reliability of certain experiments—these issues are not considered critical. 

Therefore, the AC recommends acceptance. The authors are encouraged to incorporate the new results and clarifications from the rebuttal into the final version of the paper.
Decision: Accept (poster)