Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
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.
67455093d015d7e8717ff69e
Ali Behrouz
claimed_verified
2024-11-26T21:20:59.932Z
65cccd5134a5d74cbaa9446c
/avatars/5255b734628992106598eae4f2c5848f.svg
Ali Behrouz
user
AliBehrouz
67455093d015d7e8717ff69f
Ali Parviz
claimed_verified
2024-11-26T22:59:23.547Z
66b522b550b87d8449a1ce03
/avatars/5dab28c137dd6392ec6ed0ffdfb431cc.svg
Alip
user
Alip67
67455093d015d7e8717ff6a0
Mahdi Karami
67455093d015d7e8717ff6a1
Clayton Sanford
67455093d015d7e8717ff6a2
Bryan Perozzi
admin_assigned
2024-11-26T22:53:56.871Z
666c536c83571a7a051edfb8
/avatars/b7f0450eda1cf3f5de74ee4c340593f8.svg
Bryan Perozzi
user
bperozzi
67455093d015d7e8717ff6a3
Vahab Mirrokni
Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
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.
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.
Transformers linear RNNs message passing neural networks MPNNs Graph Sequence Model (GSM) Tokenization Local Encoding Global Encoding hierarchical affinity clustering HAC hybrid architecture GSM++