Research map / Graph learning / Graph self-supervised learning
Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework
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 M$^3$Dphormer, a mixture-of-experts graph transformer built on a unified hierarchical attention-mask framework (local, cluster, global masks) with bi-level expert routing and a dense/sparse dual attention computation.
Problem
Existing graph transformers use architectures tailored to specific node interactions (local, cluster, global), limiting flexibility; efficient attention for irregular graph masks on large graphs is also hard.
Approach
Shows that GT architectures correspond to attention masks at local, cluster, and global levels; derives a bound showing classification probability grows with receptive field size and label consistency; combines three theory-guided hierarchical masks via bi-level MoE routing and switches between dense and sparse attention per region based on mask sparsity.
Key results
- M^3Dphormer achieves the best node classification accuracy on all 9 datasets, e.g., 88.48% on Cora, 98.27 ROC-AUC on Minesweeper, and 73.54% on Ogbn-Arxiv.
- Ablation: removing the local expert drops Minesweeper accuracy from 98.27 to 57.55 and Cora from 88.48 to 82.84.
- The dual attention scheme avoids OOM on all evaluated graphs, whereas the dense-only and sparse-only variants fail on some datasets (dense on four, sparse on Ogbn-Arxiv).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use M$^3$Dphormer instead of FAGCN | Cora node classification · Cora | accuracy: 88.36 -> 88.48 | Helped |
| use M$^3$Dphormer instead of CoBFormer | Citeseer node classification · Citeseer | accuracy: 77.05 -> 77.53 | Helped |
| use M$^3$Dphormer instead of PolyNormer | Pubmed node classification · Pubmed | accuracy: 89.48 -> 89.96 | Helped |
| use M$^3$Dphormer instead of PolyNormer | Computer node classification · Computer | accuracy: 91.85 -> 92.09 | Helped |
| use M$^3$Dphormer instead of GAT* | Photo node classification · Photo | accuracy: 95.73 -> 95.91 | Helped |
| use M$^3$Dphormer instead of GCN-MoE | Squirrel node classification · Squirrel | accuracy: 43.02 -> 44.34 | Helped |
| use M$^3$Dphormer instead of GCN-MoE | Chameleon node classification · Chameleon | accuracy: 44.57 -> 47.09 | Helped |
| use M$^3$Dphormer instead of GCN* | Minesweeper node classification · Minesweeper | ROC-AUC: 97.39 -> 98.27 | Helped |
| use M$^3$Dphormer instead of PolyNormer | Ogbn-Arxiv node classification · Ogbn-Arxiv | accuracy: 73.27 -> 73.54 | Helped |
| add the local expert (ablation) | M$^3$Dphormer on Cora · Cora | accuracy: 82.84 -> 88.48 | Helped |
| add the cluster expert (ablation) | M$^3$Dphormer on Cora · Cora | accuracy: 87.83 -> 88.48 | Helped |
| add the global expert (ablation) | M$^3$Dphormer on Cora · Cora | accuracy: 87.95 -> 88.48 | Helped |
Surprising findings
- Naive ensembles (Mean and Max) of single-mask GTs often underperform the best single-mask model.
- A 2-layer single-mask Transformer with 2 heads consumes 21 GB GPU memory on PubMed.
Limitations
- Theory and experiments restricted to node classification; graph-level and edge-level tasks not studied.
- Only hyperparameter is the number of clusters P; performance on small graphs like Chameleon fluctuates with P.
- Theoretical analysis relies on a Gaussian class-conditional model with orthogonal prototypes and assumed well-trained classifier conditions.
Experimental setup
Datasets: Cora Citeseer Pubmed Computer Photo Squirrel Chameleon Minesweeper Ogbn-Arxiv
Benchmarks: Cora Citeseer Pubmed Computer Photo Squirrel Chameleon Minesweeper Ogbn-Arxiv
Metrics: accuracy ROC-AUC GPU memory usage
Baselines: GCN GAT GraphSAGE GCN* GAT* SAGE* GPRGNN FAGCN NAGphormer Exphormer SGFormer CoBFormer
Builds on: NAGphormer CoBFormer Exphormer PolyNormer METIS
Closest papers by meaning
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.89)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.89)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.88)
- Even Sparser Graph Transformers (NeurIPS 2024 · similarity 0.88)
- Linear Transformer Topological Masking with Graph Random Features (ICLR 2025 · similarity 0.87)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.87)
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.