# Hierarchical Graph Transformer with Adaptive Node Sampling

arXiv: https://arxiv.org/abs/2210.03930 · HTML: https://mlsanity.com/paper/2210.03930/

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 61 references that are in the map.
- First posted on arXiv 8 Oct 2022.

## Builds on (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [A Transformer-based Framework for Multivariate Time Series Representation Learning](https://mlsanity.com/paper/2010.02803/) (2020)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Focal Self-attention for Local-Global Interactions in Vision Transformers](https://mlsanity.com/paper/2107.00641/) (2021)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Graph-Bert: Only Attention is Needed for Learning Graph Representations](https://mlsanity.com/paper/2001.05140/) (2020)
- [Motif-based Graph Self-Supervised Learning for Molecular Property Prediction](https://mlsanity.com/paper/2110.00987/) (2021)
- [ProtGNN: Towards Self-Explaining Graph Neural Networks](https://mlsanity.com/paper/2112.00911/) (2021)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [Gophormer: Ego-Graph Transformer for Node Classification](https://mlsanity.com/paper/2110.13094/) (2021)

## Built on by (most cited first, 30 of 72)

- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [Backdoor Defense via Deconfounded Representation Learning](https://mlsanity.com/paper/2303.06818/) (2023)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections](https://mlsanity.com/paper/2403.16030/) (2024)
- [Relational Graph Transformer](https://mlsanity.com/paper/2505.10960/) (2025)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [FairGT: A Fairness-aware Graph Transformer](https://mlsanity.com/paper/2404.17169/) (2024)
- [Learning Subpocket Prototypes for Generalizable Structure-based Drug Design](https://mlsanity.com/paper/2305.13997/) (2023)
- [Graph Neural Networks for Financial Fraud Detection: A Review](https://mlsanity.com/paper/2411.05815/) (2024)
- [Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures](https://mlsanity.com/paper/2506.16654/) (2025)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [On Structural Expressive Power of Graph Transformers](https://mlsanity.com/paper/2305.13987/) (2023)
- [Hierarchical Transformer for Scalable Graph Learning](https://mlsanity.com/paper/2305.02866/) (2023)
- [HIGHT: Hierarchical Graph Tokenization for Molecule-Language Alignment](https://mlsanity.com/paper/2406.14021/) (2024)
- [Enhancing Graph Transformers with Hierarchical Distance Structural Encoding](https://mlsanity.com/paper/2308.11129/) (2023)
- [Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity](https://mlsanity.com/paper/2308.09517/) (2023)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [GraphFM: A generalist graph transformer that learns transferable representations across diverse domains](https://mlsanity.com/paper/2407.11907/) (2024)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [Topology-Informed Graph Transformer](https://mlsanity.com/paper/2402.02005/) (2024)
- [Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physics](https://mlsanity.com/paper/2402.12535/) (2024)
- [An Equivariant Generative Framework for Molecular Graph-Structure Co-Design](https://mlsanity.com/paper/2304.12436/) (2023)
- [A Hierarchical Spatial Transformer for Massive Point Samples in Continuous Space](https://mlsanity.com/paper/2311.04434/) (2023)
- [Graph Transformers for Large Graphs](https://mlsanity.com/paper/2312.11109/) (2023)
- [Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers](https://mlsanity.com/paper/2406.19258/) (2024)

## Abstract (arXiv)

The Transformer architecture has achieved remarkable success in a number of domains including natural language processing and computer vision. However, when it comes to graph-structured data, transformers have not achieved competitive performance, especially on large graphs. In this paper, we identify the main deficiencies of current graph transformers:(1) Existing node sampling strategies in Graph Transformers are agnostic to the graph characteristics and the training process. (2) Most sampling strategies only focus on local neighbors and neglect the long-range dependencies in the graph. We conduct experimental investigations on synthetic datasets to show that existing sampling strategies are sub-optimal. To tackle the aforementioned problems, we formulate the optimization strategies of node sampling in Graph Transformer as an adversary bandit problem, where the rewards are related to the attention weights and can vary in the training procedure. Meanwhile, we propose a hierarchical attention scheme with graph coarsening to capture the long-range interactions while reducing computational complexity. Finally, we conduct extensive experiments on real-world datasets to demonstrate the superiority of our method over existing graph transformers and popular GNNs.