Research map / Graph learning / GNN architectures
Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Graph Sequence Model (GSM), a tokenize-encode-aggregate framework for graph sequence models, analyzes trade-offs of Transformers vs. recurrent models, and presents GSM++, a hybrid Mamba+Transformer model over hierarchical affinity clustering (HAC) tokenization with mixture of tokenization.
Problem
There is no common foundation for what makes a good graph sequence model, nor a mathematical account of the benefits and deficiencies of Transformers versus modern recurrent/SSM models for graph learning.
Approach
Unifies graph-to-sequence models into Tokenization, Local Encoding, and Global Encoding stages; proves expressivity trade-offs between Transformers and recurrent models on counting, connectivity, and shortest-path tasks; and proposes GSM++, which uses HAC-based hierarchical tokenization, hierarchical positional encoding, a Mamba-then-Transformer hybrid global encoder, and a top-2 mixture of tokeni
Key results
- GSM++ (MoT) reaches 0.9884 on MNIST, 0.7781 on CIFAR10, 0.8793 on PATTERN and 0.9437 on MalNet-Tiny, the best reported in the GNN benchmark table.
- On synthetic global tasks, the hybrid Mamba+Transformer with HAC (DFS) tokenization reaches 90.7% accuracy on connectivity at 1K vs. 85.7% for a Transformer with node tokenization.
- Ablations show removing HAC tokenization causes the largest drop on COCO-SP (0.3789 to 0.3591 F1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GSM++ (MoT) instead of Exphormer | graph classification models · MNIST | accuracy: 0.9855 -> 0.9884 | Helped |
| use GSM++ (MoT) instead of GRED | graph classification models · CIFAR10 | accuracy: 0.7685 -> 0.7781 | Helped |
| use GSM++ (MoT) instead of GRIT | graph classification models · PATTERN | accuracy: 0.8719 -> 0.8793 | Helped |
| use GSM++ (MoT) instead of Exphormer | graph classification models · MalNet-Tiny | accuracy: 0.9402 -> 0.9437 | Helped |
| add hierarchical positional encoding (ablation) | GSM++ · PATTERN | accuracy: 0.8511 -> 0.8738 | Helped |
| add hybrid sequence encoder (ablation) | GSM++ · PATTERN | accuracy: 0.8500 -> 0.8738 | Helped |
| add HAC tokenization (ablation) | GSM++ · PATTERN | accuracy: 0.8617 -> 0.8738 | Helped |
| add HAC tokenization (ablation) | GSM++ · COCO-SP | F1 score: 0.3591 -> 0.3789 | Helped |
| add hierarchical positional encoding (ablation) | GSM++ · PascalVOC-SP | F1 score: 0.4073 -> 0.4128 | Helped |
| add hybrid sequence encoder (ablation) | GSM++ · PascalVOC-SP | F1 score: 0.4058 -> 0.4128 | Helped |
| add MoT to GraphGPS | GraphGPS framework · PATTERN | accuracy: 0.8664 -> 0.8677 | Helped |
| add HAC tokenization to NAGphormer | NAGphormer framework · COCO-SP | F1 score: 0.3458 -> 0.3507 | Helped |
Surprising findings
- Subgraph (k-hop, HAC BFS) tokenizers perform worse than node tokenizers on global tasks such as connectivity and shortest path, while they excel on local tasks.
- Non-causal Transformers without proper positional encoding perform very poorly on connectivity (around 9% accuracy).
Limitations
- The paper conjectures a no-free-lunch principle for graph sequence models without a formal proof.
- GSM++ does not win on all benchmarks; the PascalVOC-SP and COCO-SP results and the CIFAR10 single-model results trail some baselines in places.
Experimental setup
Datasets: Citeseer Cora Computer CIFAR10 Photo PATTERN Peptides-Func MNIST COCO-SP PascalVOC-SP MalNet-Tiny synthetic graph tasks (node degree, cycle check, triangle counting, connectivity, color counting, shortest path)
Benchmarks: MNIST CIFAR10 PATTERN MalNet-Tiny COCO-SP PascalVOC-SP Peptides-Func Citeseer Cora Computer Photo
Metrics: accuracy F1 score RMSE
Baselines: GCN GatedGCN MPNN GIN GraphGPS NAGphormer Exphormer GRIT GRED GMN CRaWl NodeFormer
Builds on: Mamba GraphGPS NAGphormer GatedGCN Hierarchical Affinity Clustering
Closest papers by meaning
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.86)
- Generative Graph Pattern Machine (NeurIPS 2025 · similarity 0.86)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.85)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.85)
- GLBench: A Comprehensive Benchmark for Graph with Large Language Models (NeurIPS 2024 · similarity 0.85)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.