Research map / Graph learning / Graph self-supervised learning
Less is More: on the Over-Globalizing Problem in Graph Transformers
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.
Identifies an over-globalizing problem in node-level Graph Transformers and proposes CoBFormer, which pairs METIS-based bi-level (intra/inter-cluster) global attention with a GCN and mutual-supervision collaborative training.
Problem
Global attention in Graph Transformers over-allocates attention to distant higher-order nodes while near, more informative nodes are weakened, hurting node classification on homophilic graphs.
Approach
Partition the graph with METIS and decouple attention into an intra-cluster Transformer and an inter-cluster Transformer over cluster means (approximating global attention), combined with a GCN trained by a collaborative loss in which each module supervises the other via soft labels.
Key results
- CoB-G and CoB-T reach 84.96% and 85.28% Micro-F1 on Cora, versus 81.48% for SGFormer (best baseline shown).
- On PubMed, CoB-T reaches 81.42% Micro-F1 and the BGA module cuts GPU memory by about 94% (8.42G to 0.50G).
- On Deezer, CoB-T reaches 66.96% Micro-F1, slightly above SGFormer's 66.68%, while on Actor SGFormer (37.72%) edges out CoB-T (37.41%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace vanilla global attention with BGA (ablation) | CoBFormer · Cora | test accuracy: 54.86 -> 68.72 | Helped |
| replace vanilla global attention with BGA (ablation) | CoBFormer · PubMed | test accuracy: 71.22 -> 74.52 | Helped |
| replace vanilla global attention with BGA (ablation) | CoBFormer · Deezer | test accuracy: 66.49 -> 66.56 | No clear effect |
| add collaborative training (ablation) | CoBFormer with vanilla global attention · Cora | test accuracy: 54.86 -> 83.82 | Helped |
| add collaborative training (ablation) | CoBFormer with BGA · Cora | test accuracy: 68.72 -> 85.28 | Helped |
| add collaborative training (ablation) | CoBFormer with vanilla global attention · PubMed | test accuracy: 71.22 -> 80.36 | Helped |
| add collaborative training (ablation) | CoBFormer with BGA · PubMed | test accuracy: 74.52 -> 81.42 | Helped |
| add collaborative training (ablation) | CoBFormer with vanilla global attention · Deezer | test accuracy: 66.49 -> 66.86 | Helped |
| add collaborative training (ablation) | CoBFormer with BGA · Deezer | test accuracy: 66.56 -> 66.96 | Helped |
| replace vanilla global attention with BGA (ablation) | CoBFormer · PubMed | GPU memory: 8.42G -> 0.50G | Helped |
| replace vanilla global attention with BGA (ablation) | CoBFormer · Deezer | GPU memory: 20.23G -> 3.97G | Helped |
| double attention scores between same-label nodes | Vanilla Transformer · Cora | Accuracy: 55.18 -> 82.12 | Helped |
Surprising findings
- Doubling attention scores between same-label nodes in a vanilla Transformer improves its accuracy on Cora (55.18 to 82.12), suggesting over-globalizing hurts.
- On Actor, CoB-G (GCN branch) and CoB-T are not uniformly best; SGFormer leads Micro-F1 there.
Limitations
- Performance depends on the number of METIS clusters and hyperparameters (alpha, tau), which must be tuned by grid search.
- Only node classification on seven datasets is evaluated; the theory relies on assumptions such as a linear classifier and uniform class priors.
- On heterophilic Actor, CoBFormer does not outperform SGFormer.
Experimental setup
Datasets: Cora CiteSeer PubMed Ogbn-Arxiv Ogbn-Products Actor Deezer
Benchmarks: Cora CiteSeer PubMed Actor Deezer Ogbn-Arxiv Ogbn-Products
Metrics: Micro-F1 Macro-F1 Attn-SNR GPU memory
Baselines: GCN GAT NodeFormer NAGphormer SGFormer
Builds on: NodeFormer SGFormer NAGphormer METIS
Closest papers by meaning
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.91)
- Relieving the Over-Aggregating Effect in Graph Transformers (NeurIPS 2025 · similarity 0.90)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.90)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.89)
- Graph External Attention Enhanced Transformer (ICML 2024 · similarity 0.89)
- Even Sparser Graph Transformers (NeurIPS 2024 · similarity 0.88)
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.