title: Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
summary: Modern sequence models (e.g., Transformers, linear RNNs, etc.) emerged as
  dominant backbones of recent deep learning frameworks, mainly due to their
  efficiency, representational power, and/or ability to capture long-range
  dependencies. Adopting these sequence models for graph-structured data has
  recently gained popularity as the alternative to Message Passing Neural
  Networks (MPNNs). There is, however, a lack of a common foundation about what
  constitutes a good graph sequence model, and a mathematical description of the
  benefits and deficiencies in adopting different sequence models for learning on
  graphs. To this end, we first present Graph Sequence Model (GSM), a unifying
  framework for adopting sequence models for graphs, consisting of three main
  steps: (1) Tokenization, which translates the graph into a set of sequences;
  (2) Local Encoding, which encodes local neighborhoods around each node; and (3)
  Global Encoding, which employs a scalable sequence model to capture long-range
  dependencies within the sequences. This framework allows us to understand,
  evaluate, and compare the power of different sequence model backbones in graph
  tasks. Our theoretical evaluations of the representation power of Transformers
  and modern recurrent models through the lens of global and local graph tasks
  show that there are both negative and positive sides for both types of models.
  Building on this observation, we present GSM++, a fast hybrid model that uses
  the Hierarchical Affinity Clustering (HAC) algorithm to tokenize the graph into
  hierarchical sequences, and then employs a hybrid architecture of Transformer
  to encode these sequences. Our theoretical and experimental results support the
  design of GSM++, showing that GSM++ outperforms baselines in most benchmark
  evaluations.
paper_authors._id: 67455093d015d7e8717ff69e
paper_authors.name: Ali Behrouz
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-11-26T21:20:59.932Z
paper_authors._id: 65cccd5134a5d74cbaa9446c
paper_authors.avatarUrl: /avatars/5255b734628992106598eae4f2c5848f.svg
paper_authors.fullname: Ali Behrouz
paper_authors.type: user
paper_authors.user: AliBehrouz
paper_authors._id: 67455093d015d7e8717ff69f
paper_authors.name: Ali Parviz
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-11-26T22:59:23.547Z
paper_authors._id: 66b522b550b87d8449a1ce03
paper_authors.avatarUrl: /avatars/5dab28c137dd6392ec6ed0ffdfb431cc.svg
paper_authors.fullname: Alip
paper_authors.type: user
paper_authors.user: Alip67
paper_authors._id: 67455093d015d7e8717ff6a0
paper_authors.name: Mahdi Karami
paper_authors._id: 67455093d015d7e8717ff6a1
paper_authors.name: Clayton Sanford
paper_authors._id: 67455093d015d7e8717ff6a2
paper_authors.name: Bryan Perozzi
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-11-26T22:53:56.871Z
paper_authors._id: 666c536c83571a7a051edfb8
paper_authors.avatarUrl: /avatars/b7f0450eda1cf3f5de74ee4c340593f8.svg
paper_authors.fullname: Bryan Perozzi
paper_authors.type: user
paper_authors.user: bperozzi
paper_authors._id: 67455093d015d7e8717ff6a3
paper_authors.name: Vahab Mirrokni
paper_title: Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
paper_summary: Modern sequence models (e.g., Transformers, linear RNNs, etc.) emerged as
  dominant backbones of recent deep learning frameworks, mainly due to their
  efficiency, representational power, and/or ability to capture long-range
  dependencies. Adopting these sequence models for graph-structured data has
  recently gained popularity as the alternative to Message Passing Neural
  Networks (MPNNs). There is, however, a lack of a common foundation about what
  constitutes a good graph sequence model, and a mathematical description of the
  benefits and deficiencies in adopting different sequence models for learning on
  graphs. To this end, we first present Graph Sequence Model (GSM), a unifying
  framework for adopting sequence models for graphs, consisting of three main
  steps: (1) Tokenization, which translates the graph into a set of sequences;
  (2) Local Encoding, which encodes local neighborhoods around each node; and (3)
  Global Encoding, which employs a scalable sequence model to capture long-range
  dependencies within the sequences. This framework allows us to understand,
  evaluate, and compare the power of different sequence model backbones in graph
  tasks. Our theoretical evaluations of the representation power of Transformers
  and modern recurrent models through the lens of global and local graph tasks
  show that there are both negative and positive sides for both types of models.
  Building on this observation, we present GSM++, a fast hybrid model that uses
  the Hierarchical Affinity Clustering (HAC) algorithm to tokenize the graph into
  hierarchical sequences, and then employs a hybrid architecture of Transformer
  to encode these sequences. Our theoretical and experimental results support the
  design of GSM++, showing that GSM++ outperforms baselines in most benchmark
  evaluations.
paper_ai_summary: A unifying framework, Graph Sequence Model (GSM), and its hybrid variant (GSM++), provide insights into using sequence models for graph tasks, showcasing GSM++'s superior performance.
paper_ai_keywords: Transformers linear RNNs message passing neural networks MPNNs Graph Sequence Model (GSM) Tokenization Local Encoding Global Encoding hierarchical affinity clustering HAC hybrid architecture GSM++