Research map / Graph learning / Graph self-supervised learning
Enhancing Graph Transformers with Hierarchical Distance Structural Encoding
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 HDSE, a hierarchy-distance structural encoding built from graph coarsening that biases graph transformer attention, plus a high-level variant for linear transformers that scales to billion-node graphs.
Problem
Graph transformers lack strong inductive biases for long-range, hierarchical and community structure, and full attention does not scale to large graphs.
Approach
Define graph hierarchy distance (GHD) by measuring shortest-path distances between nodes' coarsened cluster representatives at multiple coarsening levels, encode the resulting vector with a learnable clipped embedding MLP as an additive attention bias, and extend it to high-level HDSE between input nodes and coarse clusters for linear transformers (GOAT).
Key results
- GT + HDSE reduces ZINC MAE from 0.226 to 0.159 and raises MNIST accuracy from 90.831 to 94.394 over the GT baseline.
- GraphGPS + HDSE reaches 0.7156 AP on Peptides-func versus 0.6535 for GraphGPS, a 6.21% relative gain.
- GOAT + HDSE improves node classification on ogbn-papers100M from 65.05 to 66.04 and on Actor from 32.1 to 38.0 accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add HDSE to GraphGPS | GraphGPS · Peptides-func | AP: 0.6535 -> 0.7156 | Helped |
| Add HDSE to GraphGPS | GraphGPS · Peptides-struct | MAE: 0.2500 -> 0.2457 | Helped |
| Add HDSE to GRIT | GRIT · PATTERN | accuracy: 87.196 -> 87.281 | Helped |
| Add HDSE to GRIT | GRIT · CLUSTER | accuracy: 80.026 -> 79.965 | Hurt |
| Add high-level HDSE to GOAT | GOAT · ogbn-products | accuracy: 82.00 ± 0.43 -> 83.38 ± 0.17 | Helped |
| Add high-level HDSE to GOAT | GOAT · Cora | accuracy: 82.1 ± 0.9 -> 83.9 ± 0.7; 71.6 ± 1.3 -> 73.1 ± 0.7; 78.9 ± 1.5 -> 80.6 ± 1.0 | Mixed |
| Remove high-level HDSE (equivalently, add high-level HDSE) (ablation) | GOAT + HDSE · Actor, ogbn-proteins, arxiv-year | accuracy / ROC-AUC: 34.6 ± 2.2 -> 38.0 ± 1.5; 79.4 ± 0.3 -> 80.3 ± 0.3; 53.6 ± 0.3 -> 54.2 ± 0.2 | Helped |
| Replace coarsening projection with GOAT's original projection (ablation) | GOAT + HDSE · Actor, ogbn-proteins, arxiv-year | accuracy / ROC-AUC: 32.1 ± 1.8 -> 38.0 ± 1.5; 78.3 ± 0.4 -> 80.3 ± 0.3; 53.5 ± 0.2 -> 54.2 ± 0.2 | Helped |
| Use maximum hierarchy level K=1 instead of K=0 (SPD) (ablation) | GraphGPS + HDSE · ZINC | MAE: 0.069 ± -> 0.062 ± | Helped |
| Increase maximum hierarchy level from K=1 to K=2 (ablation) | GOAT + HDSE · Squirrel | accuracy: 43.2 ± 2.4 -> 43.8 ± 2.1 | Helped |
| Increase maximum hierarchy level from K=1 to K=2 (ablation) | GOAT + HDSE · arxiv-year | accuracy: 54.23 ± 0.26 -> 54.51 ± 0.17 | Helped |
| Increase maximum hierarchy level from K=1 to K=2 (ablation) | GOAT + HDSE · ogbn-arxiv | accuracy: 73.26 ± 0.19 -> 73.36 ± 0.15 | Helped |
Surprising findings
- Coarsening-based HDSE with K=0 (equivalent to SPD) performs worse than K=1 on ZINC, and the best coarsening algorithm varies by backbone.
- SGFormer, tailored for large-scale node classification, underperforms on graph-level tasks.
Limitations
- Gains on large-graph node classification are modest for K=2 over K=1, suggesting limits of the coarsening algorithms.
- Improvement for GRIT is smaller since RRWP already encodes distance information.
- Graph transformers with hierarchy overfit on large-scale tasks according to the authors.
Experimental setup
Datasets: ZINC MNIST CIFAR10 PATTERN CLUSTER Peptides-func Peptides-struct Cora CiteSeer PubMed Actor Squirrel
Benchmarks: ZINC MNIST CIFAR10 PATTERN CLUSTER Peptides-func Peptides-struct Cora CiteSeer PubMed Actor Squirrel
Metrics: MAE accuracy AP ROC-AUC training time per epoch
Baselines: GT SAT GraphGPS GRIT GOAT SGFormer NodeFormer HSGT ANS-GT GIN-AK+
Builds on: GraphGPS GRIT SAT GOAT Linformer Generalized Distance Weisfeiler-Leman
Closest papers by meaning
- Simple Path Structural Encoding for Graph Transformers (ICML 2025 · similarity 0.88)
- Homomorphism Counts as Structural Encodings for Graph Learning (ICLR 2025 · similarity 0.87)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.87)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.86)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.85)
- Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework (NeurIPS 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.