mlsanityData to 14 Oct 2026

Enhancing Graph Transformers with Hierarchical Distance Structural Encoding

arXiv 2308.11129 ↗First posted 22 Aug 2023cs.LG cs.AI cs.SIcited by 16

Not on the map. Why?

Abstract (arXiv)

Graph transformers need strong inductive biases to derive meaningful attention scores. Yet, current methods often fall short in capturing longer ranges, hierarchical structures, or community structures, which are common in various graphs such as molecules, social networks, and citation networks. This paper presents a Hierarchical Distance Structural Encoding (HDSE) method to model node distances in a graph, focusing on its multi-level, hierarchical nature. We introduce a novel framework to seamlessly integrate HDSE into the attention mechanism of existing graph transformers, allowing for simultaneous application with other positional encodings. To apply graph transformers with HDSE to large-scale graphs, we further propose a high-level HDSE that effectively biases the linear transformers towards graph hierarchies. We theoretically prove the superiority of HDSE over shortest path distances in terms of expressivity and generalization. Empirically, we demonstrate that graph transformers with HDSE excel in graph classification, regression on 7 graph-level datasets, and node classification on 11 large-scale graphs, including those with up to a billion nodes.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 65 of its 97 references that are in the map. First posted on arXiv 22 Aug 2023.

Builds on

65 of 97 references.

References · 65

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  4. 2017Graph Attention Networkscited by 8,923
  5. 2017Inductive Representation Learning on Large Graphscited by 6,320
  6. 2018How Powerful are Graph Neural Networks?cited by 4,393
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  9. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  10. 2019Simplifying Graph Convolutional Networkscited by 1,477
  11. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  12. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
38 more
  1. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  2. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  3. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  4. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  5. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  6. 2020Benchmarking Graph Neural Networkscited by 680
  7. 2020A Generalization of Transformer Networks to Graphscited by 661
  8. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  9. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  10. 2019Multi-scale Attributed Node Embeddingcited by 548
  11. 2019Graph U-Netscited by 492
  12. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  13. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  14. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  15. 2019Self-Attention Graph Poolingcited by 421
  16. 2018GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Modelscited by 413
  17. 2017Residual Gated Graph ConvNetscited by 346
  18. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  19. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  20. 2020SIGN: Scalable Inception Graph Neural Networkscited by 284
  21. 2022Long Range Graph Benchmarkcited by 263
  22. 2018Learning Deep Generative Models of Graphscited by 229
  23. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  24. 2023NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classificationcited by 210
  25. 2020Hierarchical Generation of Molecular Graphs using Structural Motifscited by 208
  26. 2022Structure-Aware Transformer for Graph Representation Learningcited by 194
  27. 2023Exphormer: Sparse Transformers for Graphscited by 170
  28. 2019ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representationscited by 156
  29. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  30. 2021Equivariant Subgraph Aggregation Networkscited by 154
  31. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  32. 2022NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphscited by 137
  33. 2023SGFormer: Simplifying and Empowering Transformers for Large-Graph Representationscited by 133
  34. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  35. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 114
  36. 2022Transformer for Graphs: An Overview from Architecture Perspectivecited by 107
  37. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  38. 2022Vision Transformers provably learn spatial structurecited by 93

50 most cited of 65 All 65 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 8; 2026: 3.

16 papers.

Sort:

By area:

  1. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 85
  2. 2025When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformerscited by 38
  3. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  4. 2025Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellencecited by 26
  5. 2024Spatio-Spectral Graph Neural Networkscited by 17
  6. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  7. 2025A Survey of Graph Transformers: Architectures, Theories and Applicationscited by 14
  8. 2024Best of Both Worlds: Advantages of Hybrid Graph Sequence Modelscited by 6
  9. 2025Molecular Fingerprints Are Strong Models for Peptide Function Predictioncited by 5
  10. 2025DualEquiNet: A Dual-Space Hierarchical Equivariant Network for Large Biomoleculescited by 5
  11. 2025How Can Mamba Learn In Context with Outliers and Generalize Provably?cited by 2
  12. 2025Simple Path Structural Encoding for Graph Transformerscited by 1
4 more
  1. 2025ReSSFormer: A Recursive Sparse Structured Transformer for Scalable and Long-Context Reasoningcited by 0
  2. 2026Heterogeneous Graph Alignment for Joint Reasoning and Interpretabilitycited by 0
  3. 2026Transformers Learn the Optimal DDPM Denoiser for Multi-Token GMMscited by 0
  4. 2026Adaptive Multi-Agent Feature Selection for Personalized Fall Risk Preventioncited by 0