Research map / Graph learning / Graph self-supervised learning
What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional 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.
Theoretical analysis of a shallow Graph Transformer (one self-attention layer with relative positional encoding plus a two-layer perceptron) trained by SGD for semi-supervised node classification, giving sample-complexity and iteration bounds and showing attention sparsifies and positional encoding finds the core neighborhood.
Problem
Lack of theoretical understanding of when Graph Transformers generalize and what self-attention and positional encoding contribute to learning and generalization for node classification.
Approach
Introduces a discriminative/non-discriminative graph data model with a majority-vote core neighborhood, and proves that SGD on a shallow GT with learnable relative PE concentrates attention on class-relevant nodes and drives PE to the core distance, yielding lower sample complexity and faster convergence than GCN.
Key results
- On synthetic data, sample complexity scales roughly linearly in gamma_d^{-2} for GT, while GCN needs roughly gamma_d^{-4} samples and GT's iteration count is independent of gamma_d.
- Attention mass on class-relevant nodes rises toward 1 during training on synthetic data, supporting the sparse attention claim.
- On real datasets, a four-layer GT with PE outperforms GT without PE and a four-layer GCN with a model size at most 10% larger, as reported in figures without exact numbers in the text.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the fraction of discriminative nodes | Graph Transformer · Semi-supervised node classification | sample complexity | Helped |
| Reduce the confusion ratio in the core neighborhood | Graph Transformer · Semi-supervised node classification | sample complexity | Helped |
| Sample more class-relevant nodes in the core neighborhood | Graph Transformer · Semi-supervised node classification | generalization | Helped |
| Add self-attention (ablation) | Graph Transformer · Semi-supervised node classification | sample complexity | Helped |
| Add self-attention (ablation) | Graph Transformer · Semi-supervised node classification | iterations | Helped |
| Add trainable relative positional embedding (ablation) | Graph Transformer · PubMed, Actor, PascalVOC-SP-1G, and Ogbn-Arxiv | test accuracy | Helped |
| Remove positional embedding and supply the known core neighborhood (ablation) | Graph Transformer · Semi-supervised node classification | generalization | No clear effect |
| Increase the fraction of inconsistent labels | Graph Transformer · Synthetic graph node classification | iterations to converge | Hurt |
| Train self-attention so its weights concentrate on class-relevant nodes | Graph Transformer · Semi-supervised node classification | test accuracy | Helped |
| Train positional embedding from zero initialization to emphasize the core neighborhood | Graph Transformer · Semi-supervised node classification | sample complexity | Helped |
Limitations
- Analysis is restricted to a shallow one-layer GT with fixed output layer and pretrained query/key/value initialization.
- Results are sufficient-condition bounds, not necessary conditions.
- Assumptions such as near-orthogonal patterns and the core-neighborhood majority vote may be strong for real graphs.
Experimental setup
Datasets: PubMed Actor PascalVOC-SP-1G Ogbn-Arxiv Cora synthetic graph
Benchmarks: PubMed Actor PascalVOC-SP-1G Ogbn-Arxiv
Metrics: test accuracy hinge testing loss sample complexity number of iterations
Baselines: GCN
Builds on: feature learning theory for shallow networks on structured data Transformer generalization analysis of ViTs GCN
Closest papers by meaning
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.91)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.90)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.90)
- Graph Convolutions Enrich the Self-Attention in Transformers! (NeurIPS 2024 · similarity 0.90)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.89)
- Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · similarity 0.89)
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.